# 機能設計書 61-二分K-Meansクラスタリング

## 概要

本ドキュメントは、Apache Spark MLlibにおける二分K-Means（Bisecting K-Means）クラスタリング機能の設計を記述する。階層的な分割アプローチによりデータを指定数のクラスタに分割するアルゴリズムの訓練・予測処理を対象とする。

### 本機能の処理概要

**業務上の目的・背景**：通常のK-Meansクラスタリングでは、初期化に依存して局所最適解に収束する場合がある。二分K-Meansは階層的に分割を行うため、より安定したクラスタリング結果を得ることができる。特に、階層構造を持つクラスタリング結果が必要な場合や、K-Meansでは不十分な品質のクラスタリングが求められる場面で有用である。

**機能の利用シーン**：大規模データの顧客セグメンテーション、文書クラスタリング、画像データの類似性グルーピングなど、階層的なクラスタ構造を探索的に分析したい場面で利用される。Spark MLlibのPipeline APIと組み合わせることで、前処理からクラスタリングまでの一連の処理をワークフローとして構築できる。

**主要な処理内容**：
1. 全データ点を含む単一クラスタから開始する
2. 最下層の分割可能なクラスタを発見し、各クラスタに対してK-Means（k=2）で分割する
3. 指定されたクラスタ数kに達するか、分割可能なクラスタがなくなるまで繰り返す
4. 同レベルの分割はグループ化して並列実行する
5. 学習済みモデルによる新規データのクラスタ予測を行う

**関連システム・外部連携**：MLlib内部のmllib.clustering.BisectingKMeansに処理を委譲する。Spark DataFrame APIおよびPipeline APIと統合されている。

**権限による制御**：特になし。Sparkアプリケーション実行権限に依存する。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | 該当なし | - | MLlib機能はWeb UIに専用画面を持たない |

## 機能種別

計算処理（機械学習アルゴリズム - クラスタリング）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| k | Int | No | 目標とするリーフクラスタ数（デフォルト: 4） | > 1 |
| maxIter | Int | No | 最大反復回数（デフォルト: 20） | > 0 |
| seed | Long | No | 乱数シード | - |
| featuresCol | String | No | 特徴量カラム名（デフォルト: "features"） | Vector型カラムが存在すること |
| predictionCol | String | No | 予測結果カラム名（デフォルト: "prediction"） | - |
| distanceMeasure | String | No | 距離尺度（デフォルト: "euclidean"） | "euclidean" または "cosine" |
| minDivisibleClusterSize | Double | No | 分割可能な最小クラスタサイズ（デフォルト: 1.0） | > 0.0 |
| weightCol | String | No | 重みカラム名 | 非負の数値型 |

### 入力データソース

Spark DataFrame。featuresColで指定されたカラムにVector型の特徴量データを含むこと。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| prediction | Int | 各データ点が割り当てられたクラスタのインデックス |
| clusterCenters | Array[Vector] | 各クラスタの中心点座標 |
| trainingCost | Double | 訓練データにおける各点から最近傍の重心までのコスト合計 |
| clusterSizes | Array[Long] | 各クラスタに属するデータ点数 |

### 出力先

入力DataFrameにpredictionカラムを追加したDataFrame。モデルはMLWriterを通じてHDFS等のファイルシステムに永続化可能。

## 処理フロー

### 処理シーケンス

```
1. スキーマバリデーション
   └─ featuresColがVector互換カラムか検証
2. 入力データの準備
   └─ 特徴量と重みを抽出し、RDDに変換
3. MLlibBisectingKMeansの設定
   └─ k, maxIter, seed, distanceMeasure等のパラメータを設定
4. モデル訓練実行
   └─ bkm.runWithWeight()で階層的分割を実行
5. BisectingKMeansModelの生成
   └─ 訓練済みMLlibモデルをラップ
6. サマリーの生成
   └─ 訓練データに対するクラスタリング結果・コスト・クラスタサイズを算出
```

### フローチャート

```mermaid
flowchart TD
    A[開始: fit呼び出し] --> B[スキーマ検証]
    B --> C[特徴量・重みRDD生成]
    C --> D[MLlib BisectingKMeans設定]
    D --> E[runWithWeight実行]
    E --> F[BisectingKMeansModel生成]
    F --> G[BisectingKMeansSummary生成]
    G --> H[モデル返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-61-01 | クラスタ数制約 | 最終的なリーフクラスタ数はk以下となる。分割可能なクラスタがない場合はk未満 | 常時 |
| BR-61-02 | 分割優先度 | 同レベルで複数のクラスタが分割可能な場合、より大きなクラスタが優先される | k超過防止時 |
| BR-61-03 | NaN検出 | 特徴量ベクトルにNaN値が含まれる場合はエラー | 訓練時 |
| BR-61-04 | 重み非負制約 | weightColが指定された場合、重み値は非負であること | 訓練時 |

### 計算ロジック

二分K-Means：全データを1つのクラスタとし、反復的にK-Means（k=2）で分割する。分割はクラスタコスト（各点から重心までの距離の二乗和）を最小化するように行われる。

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

### 操作別データベース影響一覧

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | データベース操作なし（インメモリ処理） |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | パラメータ検証エラー | k <= 1の場合 | kを2以上に設定 |
| IllegalArgumentException | パラメータ検証エラー | minDivisibleClusterSize <= 0 | 正の値を設定 |
| SchemaValidationError | スキーマエラー | featuresColがVector型でない | 正しいカラム名を指定 |
| SparkException | NaN検出 | 特徴量にNaN含有 | 入力データを前処理でクリーニング |

### リトライ仕様

リトライ機構は組み込まれていない。EMアルゴリズムの収束は最大反復回数で制御する。

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

トランザクション管理なし。分散RDD処理によるインメモリ計算。

## パフォーマンス要件

処理時間はデータサイズ、特徴量次元数、クラスタ数kに依存する。StorageLevelがNONEの場合は内部でキャッシュが自動管理される。

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

特段のセキュリティ制御なし。Sparkアプリケーションのアクセス制御に依存する。

## 備考

- Spark 2.0.0で導入
- mllib.clustering.BisectingKMeansに処理を委譲するラッパー実装
- ClusteringEvaluatorによる評価を推奨（computeCostメソッドは3.0.0で非推奨）

---

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

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

### 推奨読解順序

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

BisectingKMeansのパラメータ定義とモデル構造を把握する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | BisectingKMeans.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/BisectingKMeans.scala` | BisectingKMeansParamsトレイト（44-86行目）でパラメータ定義を確認 |

**読解のコツ**: Sparkのml APIではParamsトレイトによるパラメータ管理パターンが一般的。`Param`, `IntParam`, `DoubleParam`等でパラメータを宣言し、`$()` でアクセスする。

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

BisectingKMeansクラスのfitメソッドが訓練のエントリーポイント。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | BisectingKMeans.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/BisectingKMeans.scala` | BisectingKMeansクラス（238-329行目）のfit()メソッド |

**主要処理フロー**:
1. **288-289行目**: スキーマ検証
2. **296-301行目**: MLlibBisectingKMeansインスタンス生成とパラメータ設定
3. **303-307行目**: DataFrameからRDDへの変換（特徴量と重みの抽出）
4. **310行目**: bkm.runWithWeight()でモデル訓練実行
5. **311行目**: BisectingKMeansModelの生成
6. **313-322行目**: BisectingKMeansSummaryの生成

#### Step 3: モデルの推論処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | BisectingKMeans.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/BisectingKMeans.scala` | BisectingKMeansModelクラス（93-187行目） |

**主要処理フロー**:
- **121-127行目**: transform()でUDFを使い各データ点にクラスタ番号を割り当て
- **140行目**: predict()でMLlibモデルのpredict()に委譲
- **143行目**: clusterCenters()でクラスタ中心を取得

#### Step 4: モデルの永続化を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | BisectingKMeans.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/BisectingKMeans.scala` | BisectingKMeansModelWriterとReader（189-222行目） |

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

```
BisectingKMeans.fit(dataset)
    |
    +-- transformSchema(schema)
    |       +-- validateAndTransformSchema(schema)
    |
    +-- MLlibBisectingKMeans()
    |       +-- setK / setMaxIterations / setSeed / setDistanceMeasure
    |
    +-- dataset.select(...).rdd.map(...)  // RDD変換
    |
    +-- bkm.runWithWeight(instances)  // MLlib実行
    |
    +-- BisectingKMeansModel(uid, parentModel)
    |
    +-- BisectingKMeansSummary(...)
```

### データフロー図

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

DataFrame           BisectingKMeans.fit()          BisectingKMeansModel
(features,      --> RDD変換                    --> (clusterCenters,
 weight)            MLlib BisectingKMeans.run()      predict(),
                    階層的二分割実行                    summary)

DataFrame           BisectingKMeansModel           DataFrame
(features)     --> .transform()               --> (features + prediction)
                    UDF: parentModel.predict()
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| BisectingKMeans.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/BisectingKMeans.scala` | ソース | ml API層のEstimator/Model定義 |
| BisectingKMeans.scala | `mllib/src/main/scala/org/apache/spark/mllib/clustering/BisectingKMeans.scala` | ソース | 実際のアルゴリズム実装（MLlib層） |
| BisectingKMeansModel.scala | `mllib/src/main/scala/org/apache/spark/mllib/clustering/BisectingKMeansModel.scala` | ソース | MLlib層のモデル |
| ClusteringSummary.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/ClusteringSummary.scala` | ソース | クラスタリング結果のサマリー基底クラス |
