Introduction to Information Retrieval輪講 第18回

11日はIIR輪講の第18回で、範囲は17章の「階層的クラスタリング」でした。場所は今回も百度さんの会議室でした。
担当の杉本さんが事前に超綺麗な和訳文書を作ってくれていました。

16章で扱われたフラットクラスタリングは構造がはっきりとしていないので、アプリケーションによっては不便な場合があります。
階層型クラスタリングは、フラットクラスタリングよりも処理コストが大きいのですが、そのような場合の選択肢になります。

どうやって階層を作るかですが、トップダウン型とボトムアップ型があります。多くボトムアップ型が使われているそうで、ここでもボトムアップ型を中心に解説されています。
ボトムアップ型は階層的凝集クラスタリング（HAC = Hierarchical agglomerative clustering）と呼ばれます。HACでは、まず個々の文書を一つのクラスタと考え、類似したクラスタ同士のマージを繰り返します。

HACのなかでは類似度の計算方法がいくつかあります。

• 単連結 - 最も近い文書同士の距離をクラスタの距離とする
• 完全連結 - 最も遠い文書同士の距離をクラスタの距離とする
• 群平均 - クラスタ間の全文書対の距離を平均し、クラスタの距離とする
• 重心 - クラスタの重心同士の距離をクラスタの距離とする

単連結や完全連結ではクラスタに偏りができる場合があり、重心クラスタリングは性質上扱いづらい部分があるということで、多くのアプリケーションにとっては群平均が最適なアルゴリズムのようです。
HACのアルゴリズムは疑似コードで詳しく紹介されていたので、実践的に使える章だと思います。

他にはフラットクラスタリングを応用しながらトップダウンでクラスタに分解する方法や、特徴語抽出によるクラスタへのラベル付けなどが軽く紹介されていました。

輪講の中では、ただビジュアル化してもつまらないよね、という話も出ました。構造をいかにエンドユーザーのニーズに合うように見せるかというのは、違う頭の使い方をしないといけないですね。