IIR輪講 第18回

IIR輪講の18回目です。ラスト3章は読み物なので一気にやろう−、ということなので、残り3回になります。本日は階層的クラスタリングのお話。前回はフラットなクラスタリングで、そのクラスタ間には特に関連性は無かったのですが、今回はクラスタ間に上下関係を入れてクラスタを作成するクラスタ構成法になります。


Introduction to Information Retrieval
Introduction to Information Retrieval
Christopher D. Manning (著)
Prabhakar Raghavan (著)
Hinrich Schutze (著)
¥ 7,198 (税込)


階層的クラスタリングとは、たとえば「社会 > 政治 > 選挙」のようなクラスタ間に上下関係(包含関係)があるようなクラスタを生成するためのクラスタリング手法です。大まかに言って全体をクラスタリングして、その各クラスタをさらに再帰的にクラスタリングしていくトップダウンな方法と、逆に似た要素を集めてクラスタを作り、さらにそのできあがったクラスタ同士で似たものをさらにクラスタリングしていくボトムアップな方法があります。

実際には計算量的な問題で、ボトムアップな方法が用いられることが大半のようです。この章でも個のボトムアップな方法の説明が大部分となります。

ボトムアップな階層的クラスタリングを用いる上で、最も考えなくてはならないのは、クラスタ同士の類似度をどうやって計算するかです。この章ではsingle-link、complete-link、centroid、group-averageの4種類の方法が紹介されています。

single-linkとはクラスタ内の一番近い点同士の類似度をクラスタ間の類似度とする方法です。complete-linkは逆にクラスタ内の一番遠い点同士の類似度をクラスタ間の類似度とする方法になります。centroidは2つのクラスタの全点同士の類似度の平均を取ったもので、今ある2つのクラスタの類似度の平均を取る方法です。group-averageはcentroid法に加えて、さらにクラスタ内の点の類似度も加えて平均を取ることによって、2つのクラスタをマージした後の類似度を用いる方法となります。

それぞれ一長一短があるようなので、状況によってうまく使い分ける必要がありそうです。

最後は階層的クラスタリングとは少し離れて、クラスタのラベリングの話。結局クラスタ内の特徴語を取ってきましょうというようなお話で、これはという手法があるわけではないようなので少し残念です。

次回はMatrix decompositions and latent semantic indexingです。よく知らない話なので、しっかり予習せねば。