Data Clustering: A Review A.K. Jain, M.N. Murty, P.J. Flynn ～5.12 Divide and Conquer Appoach～ 院生ゼミ ‘04年6月22日（火曜日） 谷津 哲平
大きいデータセット対策 進化的アプローチなどでは 学習，制御のパラメータを得ることが難しい データセットが大きいと時間がかかる 解決策のひとつ 分割統治法 (Divide and Conquer Approach) Two-level 手法による2,000 のパターンを含む データセットのクラスタリングの提示 [stahl 1986]
分割統治法 Divide and Conquer Approach 大きなサイズの問題をいくつかの小さなサイズの問題に分割し，小さなサイズの解から元の問題の解を得る． 分割が高速にできることと、 元の問題の解が部分問題の解から高速に求められることが必要 分割 例）マージソート，クイックソート Two-level algorithmなど 併合 マージソート
Two-level algorithm データの分割 代表の選択 k個 p個 補助記憶領域に n×d のデータを保持 主記憶領域 補助記憶領域 k個 p個 補助記憶領域に n×d のデータを保持 このデータを p 個のブロックに分割する 各ブロックには n/p 個のパターンがあると仮定する 主記憶領域に移してブロック毎に k 個のクラスタに分ける
Two-level algorithm データの分割 代表の選択 pk個 k個 p個 各クラスタから一つ以上の代表を選択する 主記憶領域 pk個 補助記憶領域 k個 p個 各クラスタから一つ以上の代表を選択する 1クラスタあたり1つの代表を選ぶと全代表は pk 個となる つまり，これらの代表 pk は，さらに k 個のクラスタに分けられている
Single-linkとの比較 距離計算の回数 計算の数を大きく節約できる ５つのクラスタに分けるときの n:データ数 p:分割数 各ブロックのポイントが合理的に均質なときにのみ有効
まとめ ・分割統治法は，大きなサイズの問題をいくつかの小さなサイズの問題に分割し，小さなサイズの解から元の問題の解を得る手法 ・Two-level アルゴリズムはレベルを広げることが可能 （データセットが非常に大きく， 主記憶領域が小さいならより多くのレベルが必要） レベルを増やせば，大きいデータセットにも使える