# 機能設計書 119-クラスタリング操作

## 概要

本ドキュメントは、TensorFlowにおけるK-Meansなどのクラスタリングアルゴリズムの操作の設計を記述する。

### 本機能の処理概要

K-Meansクラスタリングに関連する操作を提供する。クラスタ中心点の初期化（K-Means++、KMC2）と最近傍探索を含む。教師なし学習の基本的なクラスタリングアルゴリズムをTensorFlowのOp体系で実現する。

**業務上の目的・背景**：教師なし学習において、データの類似性に基づくグルーピング（クラスタリング）は最も基本的かつ重要な手法である。顧客セグメンテーション、異常検知、データ圧縮、特徴量の離散化など幅広いビジネスアプリケーションで利用される。特にK-Meansは計算効率と実用性のバランスに優れている。

**機能の利用シーン**：データのクラスタリング分析、K-Means++による初期化、特徴量のベクトル量子化、TensorFlowのEstimator API経由でのK-Means学習などで利用される。

**主要な処理内容**：
1. `KmeansPlusPlusInitialization` - K-Means++アルゴリズムによるクラスタ中心点の初期サンプリング
2. `KMC2ChainInitialization` - KMC2（Markov Chain Monte Carlo）による近似K-Means++初期化
3. `NearestNeighbors` - 各データ点から最近傍のクラスタ中心点を検索

**関連システム・外部連携**：TensorFlowのEstimator API（KMeansClustering）、数学演算と連携する。

**権限による制御**：特になし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | 該当なし | - | 本機能はバックエンドAPI機能 |

## 機能種別

計算処理 / クラスタリングアルゴリズム

## 入力仕様

### 入力パラメータ

#### KmeansPlusPlusInitialization

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| points | Tensor（float32） | Yes | データ点の集合（2Dテンソル） | - |
| num_to_sample | Tensor（int64） | Yes | サンプリングするクラスタ中心数 | - |
| seed | Tensor（int64） | Yes | 乱数シード | - |
| num_retries_per_sample | Tensor（int64） | Yes | サンプルあたりのリトライ回数 | - |

#### KMC2ChainInitialization

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| distances | Tensor（float32） | Yes | 各点の最近傍クラスタ中心までの距離 | - |
| seed | Tensor（int64） | Yes | 乱数シード | - |

#### NearestNeighbors

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| points | Tensor（float32） | Yes | データ点の集合 | - |
| centers | Tensor（float32） | Yes | クラスタ中心点の集合 | - |
| k | Tensor（int64） | Yes | 返却する最近傍数 | - |

### 入力データソース

Python API呼び出し

## 出力仕様

### 出力データ

#### KmeansPlusPlusInitialization

| 項目名 | 型 | 説明 |
|--------|-----|------|
| samples | Tensor（float32） | サンプリングされたクラスタ中心点 |

#### KMC2ChainInitialization

| 項目名 | 型 | 説明 |
|--------|-----|------|
| index | Tensor（int64） | 選択されたデータ点のインデックス（スカラー） |

#### NearestNeighbors

| 項目名 | 型 | 説明 |
|--------|-----|------|
| nearest_center_indices | Tensor（int64） | 最近傍クラスタ中心のインデックス |
| nearest_center_distances | Tensor（float32） | 最近傍クラスタ中心までの距離 |

### 出力先

呼び出し元への戻り値として返却

## 処理フロー

### 処理シーケンス

```
1. K-Means++初期化
   └─ 最初のクラスタ中心をランダムに選択
   └─ 各データ点から最近傍中心までの距離を計算
   └─ 距離に比例した確率で次のクラスタ中心を選択
   └─ num_to_sample個のクラスタ中心が選択されるまで繰り返し

2. KMC2初期化
   └─ Markov Chain Monte Carloにより近似的にK-Means++サンプリング
   └─ 計算コストを削減しつつK-Means++に近い品質を実現

3. 最近傍探索
   └─ 各データ点と全クラスタ中心の距離を計算
   └─ 上位k個の最近傍を返却
```

### フローチャート

```mermaid
flowchart TD
    A[データ点集合] --> B{初期化方法}
    B -->|K-Means++| C[距離ベースのサンプリング]
    B -->|KMC2| D[MCMC近似サンプリング]
    C --> E[クラスタ中心点]
    D --> E
    E --> F[NearestNeighbors]
    A --> F
    F --> G[最近傍インデックス + 距離]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-119-01 | K-Means++保証 | K-Means++は最適解に対してO(log k)の近似保証を持つ | KmeansPlusPlusInitialization使用時 |
| BR-119-02 | KMC2近似 | KMC2はK-Means++の計算コストを削減する近似手法 | KMC2ChainInitialization使用時 |
| BR-119-03 | スカラー出力 | KMC2の出力はスカラーインデックス | KMC2ChainInitialization使用時 |

### 計算ロジック

- **K-Means++**: D^2-weightedサンプリング。各点の選択確率は最近傍中心までの距離の二乗に比例
- **NearestNeighbors**: 総当たりの距離計算によるk-最近傍探索

## データベース操作仕様

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| InvalidArgument | 入力形状不正 | pointsが2Dでない場合 | 2Dテンソルを使用 |
| InvalidArgument | kが大きすぎる | kがクラスタ中心数を超える場合 | kを適切な値に設定 |

### リトライ仕様

該当なし

## トランザクション仕様

該当なし

## パフォーマンス要件

NearestNeighborsは総当たり計算のためO(n * m)（n: データ点数、m: クラスタ中心数）。大規模データには近似最近傍探索の使用を検討。

## セキュリティ考慮事項

特になし。

## 備考

- K-Meansの完全な学習ループ（初期化→割り当て→更新→収束判定）は、これらの基本操作を組み合わせてPython/Estimator層で実装される。
- float32型のみサポート。

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: Op定義を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | clustering_ops.cc | `tensorflow/core/ops/clustering_ops.cc` | 3つのクラスタリングOpの定義 |

**主要処理フロー**:
1. **21-27行目**: `KmeansPlusPlusInitialization` - 入力: points(float32), num_to_sample(int64), seed(int64), num_retries_per_sample(int64)。出力: samples(float32)。形状推論はUnknownShape
2. **29-33行目**: `KMC2ChainInitialization` - 入力: distances(float32), seed(int64)。出力: index(int64)。形状推論はScalarShape（スカラー出力）
3. **35-41行目**: `NearestNeighbors` - 入力: points(float32), centers(float32), k(int64)。出力: nearest_center_indices(int64), nearest_center_distances(float32)。形状推論はUnknownShape

**読解のコツ**: KMC2ChainInitializationのみScalarShapeで形状が確定している。これはMCMCチェーンの1ステップで1つのインデックスのみを返すため。

### プログラム呼び出し階層図

```
Python API (tf.compat.v1.estimator.experimental.KMeans等)
    │
    ├─ KmeansPlusPlusInitialization Op
    │      ├─ Input: points, num_to_sample, seed, num_retries
    │      └─ Output: samples (初期クラスタ中心)
    │
    ├─ KMC2ChainInitialization Op
    │      ├─ Input: distances, seed
    │      └─ Output: index (選択されたインデックス)
    │
    └─ NearestNeighbors Op
           ├─ Input: points, centers, k
           └─ Output: indices, distances
```

### データフロー図

```
[入力]                     [処理]                           [出力]

データ点(float32) ──▶ KmeansPlusPlusInit ──────────▶ クラスタ中心(float32)
                                │
                                ▼
データ点(float32) ──▶ NearestNeighbors ────────────▶ indices(int64)
クラスタ中心       ──▶                                    distances(float32)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| clustering_ops.cc | `tensorflow/core/ops/clustering_ops.cc` | ソース | クラスタリングOp定義（C++） |
| clustering_ops.py | `tensorflow/python/ops/clustering_ops.py` | ソース | Python ラッパー（存在する場合） |
| common_shape_fns.h | `tensorflow/core/framework/common_shape_fns.h` | ヘッダー | UnknownShape, ScalarShape関数 |
| op.h | `tensorflow/core/framework/op.h` | ヘッダー | REGISTER_OPマクロ定義 |
