# 機能設計書 60-KMeansクラスタリング

## 概要

本ドキュメントは、Apache Spark MLlibが提供するK-Meansクラスタリング機能の設計を記述する。本機能は、データポイントをk個のクラスタに分割する教師なし学習アルゴリズムを提供する。

### 本機能の処理概要

K-Meansは、各クラスタ中心からの距離を最小化するようにデータをk個のグループに分割するクラスタリング手法である。k-means++の並列化版（k-means||）による初期化とLloydのアルゴリズムによる反復最適化を組み合わせている。

**業務上の目的・背景**：大量のデータからパターンやグループを発見する教師なし学習は、顧客セグメンテーション、異常検知、特徴量エンジニアリング等で広く利用される。K-Meansはシンプルかつスケーラブルなクラスタリング手法として最も普及している。

**機能の利用シーン**：顧客セグメンテーション、文書分類（ベクトル空間モデル）、画像圧縮、異常検知の前処理、特徴量のビニングで利用される。

**主要な処理内容**：
1. 初期化: random または k-means|| によるクラスタ中心の選択
2. ソルバー選択: row（三角不等式ベース）または block（GEMMベース）
3. Lloydのアルゴリズムによる反復最適化
4. 距離尺度: ユークリッド距離またはコサイン距離
5. 訓練サマリー（クラスタサイズ、訓練コスト等）の生成

**関連システム・外部連携**：mllib KMeans実装、PMML形式でのモデルエクスポート。

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

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本機能に直接関連する画面はなし |

## 機能種別

計算処理（機械学習 - 教師なし学習・クラスタリング）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| k | Int | No | クラスタ数（デフォルト: 2） | > 1 |
| maxIter | Int | No | 最大反復回数（デフォルト: 20） | >= 0 |
| initMode | String | No | 初期化手法（デフォルト: "k-means\|\|"） | "random", "k-means\|\|" |
| initSteps | Int | No | k-means\|\|の初期化ステップ数（デフォルト: 2） | > 0 |
| tol | Double | No | 収束判定閾値（デフォルト: 1e-4） | >= 0 |
| distanceMeasure | String | No | 距離尺度（デフォルト: "euclidean"） | "euclidean", "cosine" |
| seed | Long | No | ランダムシード | - |
| weightCol | String | No | 重み列名 | - |
| solver | String | No | 最適化手法（デフォルト: "auto"） | "auto", "row", "block" |
| maxBlockSizeInMB | Double | No | ブロックサイズ（デフォルト: 0.0=自動1MB） | >= 0 |

### 入力データソース

DataFrame形式。特徴量列はVector型またはArray型。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| prediction | Int | 所属クラスタインデックス（0からk-1） |

### モデル属性

| 属性名 | 型 | 説明 |
|--------|-----|------|
| clusterCenters | Array[Vector] | k個のクラスタ中心 |

### 訓練サマリー

| 属性名 | 型 | 説明 |
|--------|-----|------|
| clusterSizes | Array[Long] | 各クラスタのデータポイント数 |
| numIter | Int | 収束までの反復回数 |
| trainingCost | Double | 訓練コスト（全ポイントの最近中心からの距離二乗和） |

### 出力先

入力DataFrameに予測列を追加。モデルはinternal形式またはPMML形式で永続化可能。

## 処理フロー

### 処理シーケンス

```
1. スキーマ検証
2. ソルバー選択（auto/row/block）
   └─ auto: データのスパース性に基づいて自動判定
3. 初期化
   └─ random: ランダムにk個のポイントを選択
   └─ k-means||: 並列k-means++
4. 反復最適化（Lloydのアルゴリズム）
   └─ 各データポイントを最近クラスタに割り当て
   └─ クラスタ中心を再計算
   └─ 収束判定（tol以下の変化で収束）
5. KMeansModel生成
6. サマリー生成
```

### フローチャート

```mermaid
flowchart TD
    A[開始: fit] --> B[スキーマ検証]
    B --> C{ソルバー選択}
    C -->|row| D[trainWithRow]
    C -->|block| E[trainWithBlock]
    C -->|auto| F{データスパース性判定}
    F -->|密| E
    F -->|疎| D
    D --> G[MLlibKMeans.runWithWeight]
    E --> H[初期化: k-means|| / random]
    H --> I[ブロック化・キャッシュ]
    I --> J[Lloyd反復: 割当+中心更新]
    J --> K{収束?}
    K -->|No + 反復中| J
    K -->|Yes / maxIter| L[KMeansModel生成]
    G --> L
    L --> M[サマリー生成]
    M --> N[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-60-01 | クラスタ数 | k > 1（2以上のクラスタが必要） | 常時 |
| BR-60-02 | 距離尺度 | euclidean（ユークリッド距離）またはcosine（コサイン距離） | 常時 |
| BR-60-03 | コサイン距離 | 入力ベクトルはゼロベクトルでないこと | distanceMeasure="cosine"時 |
| BR-60-04 | 予測ルール | 各データポイントを最近のクラスタ中心に割り当て | 予測時 |
| BR-60-05 | 自動ソルバー | auto時: 密データ/配列入力ならblock、疎データならrow | solver="auto"時 |

### 計算ロジック

- ユークリッド距離: `sqrt(sum((xi - ci)^2))`
- コサイン距離: `1 - dot(x, c) / (||x|| * ||c||)`
- 訓練コスト: 全データポイントの最近中心からの距離（二乗/コサイン）の重み付き合計
- 収束判定: 各クラスタ中心の移動距離が全てtol以下

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

本機能はデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | RequireError | k <= 1 | k > 1を設定 |
| - | RequireError | コサイン距離でゼロベクトル | ゼロベクトルを除外 |
| - | RequireError | 重みが負値 | 非負の重みを使用 |

### リトライ仕様

特になし。

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

Sparkの遅延評価に基づく。

## パフォーマンス要件

- blockソルバー: GEMMによる効率的な距離計算（密データに適）
- rowソルバー: 三角不等式による距離計算の省略（疎データに適）
- autoソルバーでデータ特性に応じた自動最適化
- ブロック化データはMEMORY_AND_DISKレベルでキャッシュ

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

Sparkの標準セキュリティ機構に従う。

## 備考

- Spark 1.5.0で導入
- k-means||初期化（Bahmani et al., VLDB 2012）
- blockソルバーはSpark 3.4.0で追加
- PMML形式でのエクスポートに対応
- 返却されるクラスタ数はk未満の場合がある（重複点が少ない場合）

---

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

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | KMeans.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/KMeans.scala` | KMeansParams（50-129行目）でk, initMode, initSteps, solver等のパラメータ定義 |
| 1-2 | KMeans.scala | 同上 | KMeansModel（137-254行目）でparentModel, clusterCenters, summary属性 |

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | KMeans.scala | 同上 | fit()（438-457行目） |

**主要処理フロー**:
1. **439行目**: スキーマ検証
2. **446-450行目**: preferBlockSolverでソルバー選択
3. **447行目**: trainWithBlock / trainWithRow分岐
4. **452行目**: KMeansModel生成
5. **454行目**: サマリー生成（transform + numIter + cost）

#### Step 3: ソルバー選択ロジックを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | KMeans.scala | 同上 | preferBlockSolver()（459-487行目） |

**主要処理フロー**:
- **460-462行目**: ROW/BLOCKの明示指定
- **463-486行目**: AUTO時のスパース性判定
  - VectorUDT: 非ゼロ要素率が50%以上ならblock
  - ArrayType: blockを選択

#### Step 4: row訓練処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | KMeans.scala | 同上 | trainWithRow()（489-507行目）でMLlibKMeans利用 |

#### Step 5: block訓練処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | KMeans.scala | 同上 | trainWithBlock()（509-623行目）でLloydアルゴリズムのブロック最適化版 |

**主要処理フロー**:
1. **515-519行目**: 初期化（k-means||/random）
2. **524-540行目**: 距離尺度に応じたInstance構築
3. **549-551行目**: ブロック化とキャッシュ
4. **561-609行目**: Lloyd反復: ブロードキャスト中心→距離計算→割当→中心更新→収束判定
5. **622行目**: MLlibKMeansModel生成

**読解のコツ**: euclidean距離の場合、Instance.labelにベクトルの二乗ノルムを格納する最適化が行われている（530行目）。

#### Step 6: KMeansAggregatorを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | KMeans.scala | 同上 | KMeansAggregator（729-846行目）でブロック単位の距離計算とクラスタ割当 |

**主要処理フロー**:
- **776-778行目**: GEMM(-2, blockMatrix, centerMatrix^T)で全ペアの距離相当量を計算
- **786-810行目**: euclideanUpdateInPlace: 二乗距離の最小値でクラスタ割当
- **813-845行目**: cosineUpdateInPlace: コサイン距離の最小値でクラスタ割当

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

```
KMeans.fit(dataset)
    |
    +-- transformSchema(schema)
    +-- preferBlockSolver(dataset)
    |
    +-- [分岐: ソルバー]
    |   +-- trainWithRow(dataset, instr)
    |   |       +-- MLlibKMeans.runWithWeight(instances)
    |   |
    |   +-- trainWithBlock(dataset, instr)
    |           +-- initialize(dataset) [k-means|| / random]
    |           +-- InstanceBlock.blokifyWithMaxMemUsage()
    |           +-- [Lloyd反復]
    |           |   +-- broadcast(centers)
    |           |   +-- blocks.mapPartitions { KMeansAggregator.add(block) }
    |           |   +-- reduceByKey -> 新クラスタ中心
    |           |   +-- 収束判定
    |           +-- MLlibKMeansModel(centers, cost, numIter)
    |
    +-- new KMeansModel(uid, oldModel)
    +-- model.createSummary()
```

### データフロー図

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

DataFrame          fit()
  (features,       +-- ソルバー選択                    KMeansModel
   weight)         +-- 初期化(k-means||/random)          (clusterCenters,
                   +-- Lloyd反復                           parentModel)
                   |   +-- 最近中心割当
                   |   +-- 中心再計算                   KMeansSummary
                   |   +-- 収束判定                       (clusterSizes,
                   +-- サマリー生成                        numIter,
                                                          trainingCost)

DataFrame          transform()
  (features)       +-- predict(最近中心)              DataFrame
                                                       (prediction: Int)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| KMeans.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/KMeans.scala` | ソース | ml API Estimator/Model/Params/Summary/Aggregator |
| KMeans.scala (mllib) | `mllib/src/main/scala/org/apache/spark/mllib/clustering/KMeans.scala` | ソース | rowソルバーのKMeans実装 |
| KMeansModel.scala (mllib) | `mllib/src/main/scala/org/apache/spark/mllib/clustering/KMeansModel.scala` | ソース | mllib KMeansModel（予測、PMML出力） |
| ClusteringSummary.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/ClusteringSummary.scala` | ソース | クラスタリングサマリーの基底クラス |
| InstanceBlock.scala | `mllib/src/main/scala/org/apache/spark/ml/feature/Instance.scala` | ソース | ブロック化データ構造 |
