# 機能設計書 64-Power Iteration Clustering

## 概要

本ドキュメントは、Apache Spark MLlibにおけるPower Iteration Clustering（PIC）機能の設計を記述する。グラフの類似度行列に対してPower Iteration法を適用し、スペクトルクラスタリングに類似したグラフベースのクラスタリングを行う機能を対象とする。

### 本機能の処理概要

**業務上の目的・背景**：Power Iteration Clusteringは、データ点間の類似度（親和度）情報のみからクラスタリングを行うグラフベースの手法である。特徴量空間における距離ではなく、ペアワイズの類似度に基づくため、非ユークリッド空間のデータや、グラフ構造を持つデータのクラスタリングに適している。スペクトルクラスタリングの計算効率の良い近似手法として位置づけられる。

**機能の利用シーン**：ソーシャルネットワークのコミュニティ検出、類似画像のグルーピング、テキスト文書間の類似度に基づくクラスタリング、推薦システムにおけるユーザー/アイテムのグルーピングなど。

**主要な処理内容**：
1. 入力としてソース・デスティネーション・重み（類似度）の3つ組を受け取る
2. 正規化された親和度行列を構築
3. Power Iteration法により疑似固有ベクトルを算出
4. 疑似固有ベクトルに対してK-Meansでクラスタリング
5. 各頂点にクラスタIDを割り当て

**関連システム・外部連携**：Spark DataFrame APIと統合。mllib.clustering.PowerIterationClusteringに処理を委譲する。Estimator/Transformerパターンではなく、assignClusters()メソッドでクラスタ割り当てを直接実行する。

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

## 関連画面

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

## 機能種別

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

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| k | Int | No | クラスタ数（デフォルト: 2） | >= 2 |
| maxIter | Int | No | Power Iterationの最大反復回数（デフォルト: 20） | > 0 |
| initMode | String | No | 初期化モード（"random" or "degree"、デフォルト: "random"） | "random" or "degree" |
| srcCol | String | No | ソース頂点IDカラム名（デフォルト: "src"） | - |
| dstCol | String | No | デスティネーション頂点IDカラム名（デフォルト: "dst"） | - |
| weightCol | String | No | エッジ重み（類似度）カラム名（デフォルト: "weight"） | 非負 |

### 入力データソース

Spark DataFrame。エッジリスト形式で、各行が(src, dst, weight)の3つ組を持つ。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| id | Long | 頂点ID |
| cluster | Int | 割り当てられたクラスタID |

### 出力先

(id, cluster)のペアを持つDataFrame。

## 処理フロー

### 処理シーケンス

```
1. 入力データの読み込み
   └─ (src, dst, weight)エッジリストを取得
2. 正規化親和度行列の構築
   └─ 行正規化された親和度行列を生成
3. Power Iteration実行
   └─ 疑似固有ベクトルの反復計算
4. K-Meansクラスタリング
   └─ 疑似固有ベクトルに対してK-Meansを適用
5. クラスタ割り当て結果の返却
   └─ (id, cluster)のDataFrameを生成
```

### フローチャート

```mermaid
flowchart TD
    A[開始: assignClusters呼び出し] --> B[エッジリスト読み込み]
    B --> C[正規化親和度行列構築]
    C --> D[Power Iteration実行]
    D --> E[K-Meansクラスタリング]
    E --> F[クラスタ割り当て結果返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-64-01 | クラスタ数制約 | kは2以上でなければならない | 常時 |
| BR-64-02 | 初期化モード | "random"はランダム初期化、"degree"は次数ベース初期化 | 常時 |
| BR-64-03 | 対称性 | 入力グラフは無向グラフとして扱われる | 常時 |

### 計算ロジック

Power Iteration法：正規化親和度行列Wに対し、v_(t+1) = W * v_t を反復。収束後の疑似固有ベクトルに対してK-Meansを適用してクラスタリング。

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

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | パラメータ検証エラー | k < 2 | kを2以上に設定 |
| IllegalArgumentException | パラメータ検証エラー | initModeが不正 | "random"または"degree"を指定 |

### リトライ仕様

リトライ機構は組み込まれていない。

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

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

## パフォーマンス要件

エッジ数に比例する計算コスト。密なグラフでは高い計算コストとなる。

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

特段のセキュリティ制御なし。

## 備考

- Spark 2.4.0でml API版が導入
- Estimator/Transformerパターンではなく、assignClusters()メソッドでクラスタ割り当てを直接実行
- Lin and Cohen, "Power Iteration Clustering" (ICML 2010) に基づく

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | PowerIterationClustering.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/PowerIterationClustering.scala` | PowerIterationClusteringParamsトレイトでパラメータ定義を確認 |

**読解のコツ**: PICは通常のEstimator/Modelパターンと異なり、assignClusters()メソッドが主要な処理エントリーポイントとなる。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | PowerIterationClustering.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/PowerIterationClustering.scala` | assignClusters()メソッド |

**主要処理フロー**:
1. パラメータの検証
2. DataFrameからエッジRDDへの変換
3. mllib.clustering.PowerIterationClustering.run()呼び出し
4. 結果のDataFrame変換

#### Step 3: MLlib層の実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | PowerIterationClustering.scala | `mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala` | Power Iterationアルゴリズムの実装 |

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

```
PowerIterationClustering.assignClusters(dataset)
    |
    +-- パラメータ検証
    |
    +-- DataFrame → エッジRDD変換
    |
    +-- mllib.PowerIterationClustering.run()
    |       +-- 正規化親和度行列構築
    |       +-- Power Iteration反復
    |       +-- K-Meansクラスタリング
    |
    +-- 結果DataFrame生成 (id, cluster)
```

### データフロー図

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

DataFrame               PowerIterationClustering         DataFrame
(src, dst, weight) --> .assignClusters()            --> (id, cluster)
                        Power Iteration + K-Means
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| PowerIterationClustering.scala | `mllib/src/main/scala/org/apache/spark/ml/clustering/PowerIterationClustering.scala` | ソース | ml API層の定義 |
| PowerIterationClustering.scala | `mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala` | ソース | MLlib層のPICアルゴリズム実装 |
