IIR17章まとめ

16章で、フラットクラスタリングについてまとめたのに引き続き、17章では階層的クラスタリングについて説明する。

階層的クラスタリングとは、以下のような階層を自動的に作り出すことである。

HAC

HAC(Hierarchical Agglomerative Clustering)は、ボトムアップな階層的クラスタリング手法である。

HACでは、まずドキュメントの数だけクラスタを作成し、類似クラスタをマージしながら、最終的に1つのクラスタにする。

これを表現するのに、以下のようなデンドログラムを用いる。

デンドログラムの断面でクラスタが得られる。(上図では0.1,0.4でカットしている)

そして、どのように類似度を定義するかがキーとなるが、それには様々な決め方がある。

最短距離法(Single-link)

すべてのドキュメントの組み合わせに関して距離を求め、最も近い距離をクラスタ間の距離とする。

計算量は。

最長距離法(Complete-link)

すべてのドキュメントの組み合わせに関して距離を求め、最も近い距離をクラスタ間の距離とする。

計算量は。

重心法(Centroid clustering)

各クラスタの重心を求めて、重心間の距離をクラスタの距離とする。

計算量は。

また、マージの最中で重心が移動するため、以下のような反転が生じることがある。

よって重心法は使わない方がよい。

群平均法(GAAC)

各クラスタ内のすべての対象間の距離の平均をとったものをクラスタ間の距離とする。

計算量は。

だいたいの場合、GAACが1番ベストな手法である。

分岐型クラスタリング

分岐型クラスタリングとは、トップダウンな階層的クラスタリング手法である。

Bisecting K-means

まず、ドキュメントセットをK-meansによって2つのクラスタに分ける。

そして、何らかの基準でクラスタを1つ選び(例えば1番大きなクラスタ)、それを同様に2つのクラスタに分ける。

これを、望んでいるクラスタ数になるまで繰り返す。

HACよりも効率はよいが、非決定的であるのが欠点である。

ラベリング

クラスタに自動的によいラベリングを行うにはどうすればよいか？

Discriminative labeling

他のクラスタとのはっきり区別できるようなタームをラベルにする。

Non-discriminative labeling

そのクラスタ内で最も重みの高いタームをラベルにする。

ただしこの手法だと、頻出タームが抽出される可能性がある。

タイトルを用いる

そのクラスタのセントロイドに近い何個かのドキュメントのタイトルをラベルにする。

上の2つの手法と比べて簡単である。