IIR輪講復習 #17 Hierarchical clustering
お知らせ たつをさんによる補足情報 復習資料おきば http://chalow.net/clsearch.cgi?cat=IIR http://bloghackers.net/~naoya/iir/ppt/
参考 http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html 本資料は書籍の輪読会に向けたサマリ 本資料内で一部上記ドキュメント, スライドからの引用あり
本章のテーマ 階層型クラスタリング 前回: フラットクラスタリング 類似度の計算手法 計算量 クラスタへのラベリング
階層型クラスタリングとは 構造化されたクラスタリング デンドログラムの構築
階層型クラスタリングの特徴 デンドログラムの断面でクラスタが得られる フラットより精度が高い (反論あり) 計算量がフラットより多い
トップダウン or ボトムアップ 凝集クラスタリング 分岐型クラスタリング agglomerative clustering HAC (Hierarchical Agglomerative Clustering) 単元クラスタをまとめながら単一のクラスタにマージ ボトムアップ 18章で主に扱うのはこちら 分岐型クラスタリング divisive clustering フラットクラスタリングでクラスタを分割しながら階層を作る トップダウン
HACのアルゴリズム N x N 類似度行列 C を計算 N - 1 ステップのマージを実行 計算量 Θ(N3) 最も似ているクラスタ二つを見つけてマージ マージされた箇所の C の行と列を更新 計算量 Θ(N3) 優先度付きキューで改善 Θ(N2logN) ※フラットクラスタリングは線型 Θ(IKNM)
SIMPLEHAC
EFFICIENTHAC 優先度付きキューで計算量を改善
EFFICIENTHAC の例
階層クラスタリングの評価関数 評価関数 → 凝集時にどのクラスタをマージすべきかを判断する指標 最短距離法 最長距離法 群平均凝集法 重心法 single-linkage clustering 最長距離法 complete-linkage clustering 群平均凝集法 group average agglomerative clustering GAAC 重心法 centroid clustering ウォード法 Ward's method
評価関数における"距離" 距離は適当なものを使う ユークリッド距離、cos 類似度 etc
評価関数 ※ http://www.kamishima.net/jp/clustering/ より引用
評価関数 (IIR版)
各評価関数の違い
最短距離 Single-link 2クラスタ中にある、最も似ている要素の最短距離 局所的 ･･･ クラスタの一部しか考慮されない 空間濃縮の性質 → 外乱に極めて弱い チェイニング効果 ･･･ 大きなクラスタにどんどん吸い寄せられる
最長距離 Complete-link 2クラスタ中にある、最も似ていない要素間の類似度 局所的ではない ･･･ クラスタ全体を考察 空間拡散の性質 → 外れ値に対して敏感
群平均 GAAC 同じクラスタ内の対を含む、文書の全てについて計算 距離に内積を用いると、式変形により計算量減らすことができる IIR で紹介されている4つの中ではベスト?
重心 Centroid clustering 各クラスタの重心の類似度を利用 マージの最中で重心が移動するため「反転」が生じる
各評価関数の違い (再掲)
各評価関数の違いまとめ ※Single-link だけ Θ(N2) なのは、merge-best persistant の性質を利用して NBM 配列で最適化できるから
そのほかの話題 クラスタのラベリング 実装に関する小話 差分クラスタラベリング クラスタインターナルラベリング 小話程度 内積計算は転置インデックスを使うと良い 100,000 文書くらいが限界 HAC とフラットクラスタリングを組み合わせると良い K-means のシードを HAC で選ぶ