Data Clustering: A Review

Presentation on theme: "Data Clustering: A Review"— Presentation transcript:

1 Data Clustering: A Review
A.K. Jain, M.N. Murty, P.J. Flynn 院生ゼミ ‘04年4月27日（火曜日） 新納浩幸

2 本日の私の担当 第5章： （前ふりの部分は谷津君） 5.1 Hierarchical Clustering Algorithms
● Agglomerative (凝集的) Single-Link ● Agglomerative Complete-Link ○ Hierarchical Agglomerative Complete-Link

3 手法の概要 近いものを 集めてゆく手法

4 デンドログラム 階層的クラスタリング 類似度 の過程と結果はこの デンドログラムに要約 できる ある類似度で切ると 複数個のクラスタ結果
が得られる

5 ? 手法の位置づけ Clustering Hierarchical Partitional Complete Link
Single Link Minimum-Variance (省略) こっちはまた後でやる

6 Single-Link 最も近い要素の間の距離で クラスター間の距離を測る

7 Complete-Link 最も遠い要素の間の距離で クラスター間の距離を測る

8 参考）群平均法 クラスターの重心間の距離で クラスター間の距離を測る

9 Chain 効果 Single-Link の欠点 Complete-Link はこの問題を受けない， コンパクトなクラスターを作る傾向がある

10 Single-Link の長所 多目的に使える こんなのでもＯＫ でも通常は Complete-Link の方を つかうのが良い

11 Single-Link アルゴリズム （１） 各パターンをクラスタとみなす． パターン間の距離を測ってソートしておく．
距離を測り，最も距離が短いクラスタどうしを 併合する．この際，（１）で作ったソート結果を利用）． １つのクラスタにまとまったら終わり． （３）結果はデンドログラムで表現できる

12 Complete-Link アルゴリズム （１） 各パターンをクラスタとみなす． パターン間の距離を測ってソートしておく．
（２） Compete-Link の定義に従って，各クラスター間の 距離を測り，最も距離が短いクラスタどうしを 併合する．この際，（１）で作ったソート結果を利用）． １つのクラスタにまとまったら終わり． （３）結果はデンドログラムで表現できる

13 階層的クラスタリングのアルゴリズム （１） 各パターンをクラスタとみなす． クラスター間の近接行列を作成する．
（２） 近接行列に従って，最も距離が短いクラスタどうしを 併合する．結果を近接行列に反映させる． １つのクラスタにまとまったら終わり． （３）結果はデンドログラムで表現できる

14 分割的手法との比較 Partitional …. パターンが独立した島になっているときに うまく働く 計算に必要な時間とメモリは少ない．
Hierarchical …. 多目的，パターンが独立した島になって いなくてもＯＫ． 計算に必要な時間とメモリは多い．