Data Clustering: A Review A.K. Jain, M.N. Murty, P.J. Flynn 院生ゼミ ‘04年4月27日（火曜日） 新納浩幸
本日の私の担当 第5章： （前ふりの部分は谷津君） 5.1 Hierarchical Clustering Algorithms ● Agglomerative (凝集的) Single-Link ● Agglomerative Complete-Link ○ Hierarchical Agglomerative Complete-Link
手法の概要 近いものを 集めてゆく手法
デンドログラム 階層的クラスタリング 類似度 の過程と結果はこの デンドログラムに要約 できる ある類似度で切ると 複数個のクラスタ結果 が得られる
? 手法の位置づけ Clustering Hierarchical Partitional Complete Link Single Link Minimum-Variance (省略) こっちはまた後でやる
Single-Link 最も近い要素の間の距離で クラスター間の距離を測る
Complete-Link 最も遠い要素の間の距離で クラスター間の距離を測る
参考）群平均法 クラスターの重心間の距離で クラスター間の距離を測る
Chain 効果 Single-Link の欠点 Complete-Link はこの問題を受けない， コンパクトなクラスターを作る傾向がある
Single-Link の長所 多目的に使える こんなのでもＯＫ でも通常は Complete-Link の方を つかうのが良い
Single-Link アルゴリズム （１） 各パターンをクラスタとみなす． パターン間の距離を測ってソートしておく． 距離を測り，最も距離が短いクラスタどうしを 併合する．この際，（１）で作ったソート結果を利用）． １つのクラスタにまとまったら終わり． （３）結果はデンドログラムで表現できる
Complete-Link アルゴリズム （１） 各パターンをクラスタとみなす． パターン間の距離を測ってソートしておく． （２） Compete-Link の定義に従って，各クラスター間の 距離を測り，最も距離が短いクラスタどうしを 併合する．この際，（１）で作ったソート結果を利用）． １つのクラスタにまとまったら終わり． （３）結果はデンドログラムで表現できる
階層的クラスタリングのアルゴリズム （１） 各パターンをクラスタとみなす． クラスター間の近接行列を作成する． （２） 近接行列に従って，最も距離が短いクラスタどうしを 併合する．結果を近接行列に反映させる． １つのクラスタにまとまったら終わり． （３）結果はデンドログラムで表現できる
分割的手法との比較 Partitional …. パターンが独立した島になっているときに うまく働く 計算に必要な時間とメモリは少ない． Hierarchical …. 多目的，パターンが独立した島になって いなくてもＯＫ． 計算に必要な時間とメモリは多い．