IIR輪講復習 #17 Hierarchical clustering

Presentation on theme: "IIR輪講復習 #17 Hierarchical clustering"— Presentation transcript:

1 IIR輪講復習 #17 Hierarchical clustering

2 お知らせ たつをさんによる補足情報 復習資料おきば http://chalow.net/clsearch.cgi?cat=IIR

3 参考 本資料は書籍の輪読会に向けたサマリ 本資料内で一部上記ドキュメント, スライドからの引用あり

4 本章のテーマ 階層型クラスタリング 前回: フラットクラスタリング 類似度の計算手法 計算量 クラスタへのラベリング

5 階層型クラスタリングとは 構造化されたクラスタリング デンドログラムの構築

6 階層型クラスタリングの特徴 デンドログラムの断面でクラスタが得られる フラットより精度が高い (反論あり) 計算量がフラットより多い

7 トップダウン or ボトムアップ 凝集クラスタリング 分岐型クラスタリング agglomerative clustering
HAC (Hierarchical Agglomerative Clustering) 単元クラスタをまとめながら単一のクラスタにマージ ボトムアップ 18章で主に扱うのはこちら 分岐型クラスタリング divisive clustering フラットクラスタリングでクラスタを分割しながら階層を作る トップダウン

8 HACのアルゴリズム N x N 類似度行列 C を計算 N - 1 ステップのマージを実行 計算量 Θ(N3)
最も似ているクラスタ二つを見つけてマージ マージされた箇所の C の行と列を更新 計算量 Θ(N3) 優先度付きキューで改善 Θ(N2logN) ※フラットクラスタリングは線型 Θ(IKNM)

9 SIMPLEHAC

10 EFFICIENTHAC 優先度付きキューで計算量を改善

11 EFFICIENTHAC の例

12 階層クラスタリングの評価関数 評価関数 → 凝集時にどのクラスタをマージすべきかを判断する指標 最短距離法 最長距離法 群平均凝集法 重心法
single-linkage clustering 最長距離法 complete-linkage clustering 群平均凝集法 group average agglomerative clustering GAAC 重心法 centroid clustering ウォード法 Ward's method

13 評価関数における"距離" 距離は適当なものを使う ユークリッド距離、cos 類似度 etc

14 評価関数 ※

15 評価関数 (IIR版)

16 各評価関数の違い

17 最短距離 Single-link 2クラスタ中にある、最も似ている要素の最短距離 局所的 ･･･ クラスタの一部しか考慮されない
空間濃縮の性質 → 外乱に極めて弱い チェイニング効果 ･･･ 大きなクラスタにどんどん吸い寄せられる

18 最長距離 Complete-link 2クラスタ中にある、最も似ていない要素間の類似度 局所的ではない ･･･ クラスタ全体を考察
空間拡散の性質 → 外れ値に対して敏感

19 群平均 GAAC 同じクラスタ内の対を含む、文書の全てについて計算 距離に内積を用いると、式変形により計算量減らすことができる
IIR で紹介されている4つの中ではベスト?

20 重心 Centroid clustering
各クラスタの重心の類似度を利用 マージの最中で重心が移動するため「反転」が生じる

21 各評価関数の違い (再掲)

22 各評価関数の違いまとめ ※Single-link だけ Θ(N2) なのは、merge-best persistant の性質を利用して NBM 配列で最適化できるから

23 そのほかの話題 クラスタのラベリング 実装に関する小話 差分クラスタラベリング クラスタインターナルラベリング 小話程度
内積計算は転置インデックスを使うと良い 100,000 文書くらいが限界 HAC とフラットクラスタリングを組み合わせると良い K-means のシードを HAC で選ぶ