Introduction to Information Retrieval #17 の復習資料

Introduction to Information Retrieval 輪読会 17章の復習資料を以下にアップロードしました。

17章のテーマは "Hierarchical clustering" で、前回 16 章の非階層型クラスタリングに続き、階層型クラスタリングの話です。

階層型クラスタリング

階層型クラスタリングはその名の通り、階層構造を伴ったクラスタリングの手法です。例えば「はてなダイアリー」に関するクラスタと、「はてなブックマーク」に関するクラスタは、二つが合わさって上位に「はてな」というクラスタを形成し、更に上位に「ウェブサービス」というクラスタを形成するかもしれません。こうして階層構造はデンドログラムと呼ばれる二分木を構成します。

ウェブサービス -+- はてな  -+- はてなブックマーク
               |          +- はてなダイアリー
               +- Google  +- Google検索
                          +- Google Maps

適当な閾値でデンドログラムの断面を取ることで、クラスタを得ることができます。従って、階層型クラスタリングでは、デンドログラムを構築することが一つのゴールになります。

非階層型クラスタリングに比較すると、階層型クラスタリングは応用の範囲が広く、また一般的に精度が高いとも言われています。(ただし、これに関しては反論もあるそうです) また16章で見た非階層クラスタリングのアルゴリズム (K-means など) は非決定的なアルゴリズムで局所最適に落ち込む可能性があるのに対し、階層型クラスタリングは決定的です。

しかし、その分、階層型クラスタリングは計算量が大きいのが欠点です。非階層型クラスタリングのアルゴリズムである K-means は文書総数Nに対して線型( Θ(IKNM) ) であるのに対し、階層型クラスタリングでは Θ(N2) から Θ(N3) といったオーダーになります。

階層型クラスタリングのアルゴリズム

階層型クラスタリングのアルゴリズムは大きく二つに分けられます。

の二つです。前者はボトムアップのアプローチ、後者がトップダウンのアプローチになります。IIR で主に扱っているのは前者です。

HAC のアルゴリズムでは、文書が N 件あった場合、先に N * N の類似度行列 C を求めます。この行列 C から、特定のクラスタに着目したときにそのクラスタと次にマージすべき対を探します。最初は単元クラスタ、すなわち文書が一つだけのクラスタから始めます。対が見つかったらマージを行い、C を更新します。これを繰り返すことでデンドログラムが形成されます。

HAC は、何の工夫もなしに実装を行うと Θ(N3) です。優先度付きキューを利用することで Θ(N2logN) に改善することができます。

階層型クラスタリングの類似度評価関数

クラスタとクラスタの類似度の計算に利用する評価関数として IIR では 4 つの手法を紹介しています。

  • 単連結法 (single-link)
  • 完全連結法 (complete-link)
  • 群平均法 (group-average)
  • 重心法 (centroid)

どの評価関数を利用するかで、クラスタとクラスタの結びつき具合が変わってきます。計算量的には単連結が有利ですが、単連結は局所的な評価関数であるため、大きいクラスタにどんどん他のクラスタが吸い寄せられてしまい、偏りを持ったクラスタが形成されてしまう欠点(チェイニング効果)があります。完全連結は単連結とは異なりクラスタ全体の構造を加味した評価関数ですが、外れ値に対して敏感です。結局、群平均を使うのが、バランスもよく(反転も起きずに)ベストだとのことです。

本章の復習を行うにあたっては以下のページが参考になりました。

また、サイボウズラボの中谷さんが実際に Ruby で IIR の HAC を実装していて、単連結と群平均を使った場合の結果を公開されています。こちらもとても参考になりました。

次回輪講ほか

今日の輪読会、第18章は "Matrix decompositions and latent semantic indexing" でした。単語文書行列 (term document matrix) を、行列の特異値分解 (SVD) を使って低階数近似し、計算量を下げたり、適合率や再現率を向上させるという手法です。固有ベクトルを使った行列分解など線型代数の各種演算を多用する章で、個人的には大学で量子力学のテストに泣かされていた頃を思い出しつつも、かなり楽しめた章でした。IIR の章の中で、一番面白かった気がします。18章の内容については、後日この日記に書いてみようと思います。

なお、18章のテキストは id:sleepy_yoshi さんが気合いの入った和訳を作成されています (id:sleepy_yoshi:20081025:p1)。

次回の輪読会は 2/28 (土) 予定。次回輪読会後、いつも通り復習資料をアップします。次回はいよいよ IIR 輪読会一週目の最終回で、19章から21章まで合計3章を一気に駆け抜ける予定です。

過去の章の復習資料 ppt は同 URL のディレクトリ (http://bloghackers.net/~naoya/iir/ppt/) から一覧可能です。

Introduction to Information Retrieval

Introduction to Information Retrieval