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個 補助記憶領域に n×d のデータを保持 このデータを p 個のブロックに分割する p個 各ブロックには n/p 個のパターンがあると仮定する 主記憶領域に移してブロック毎に k 個のクラスタに分ける Two-level algorithm データの分割 代表の選択 主記憶領域 pk個 補助記憶領域 k個 p個 各クラスタから一つ以上の代表を選択する 1クラスタあたり1つの代表を選ぶと全代表は pk 個となる つまり，これらの代表 pk は，さらに k 個のクラスタに分けられている Single-linkとの比較 ５つのクラスタに分けるときの 距離計算の回数 n:データ数 p:分割数 計算の数を大きく節約できる Single-linkは， 各ブロックのポイントが合理的に均質なときにのみ有効 まとめ ・分割統治法は，大きなサイズの問題をいくつかの小さな サイズの問題に分割し，小さなサイズの解から元の問題 の解を得る手法 ・Two-level アルゴリズムはレベルを広げることが可能 （データセットが非常に大きく， 主記憶領域が小さいならより多くのレベルが必 要） レベルを増やせば，大きいデータセットにも使える
© Copyright 2024 ExpyDoc
