IIR輪講第17回 - WebCrawler2

IIR輪講の第17回です。本日は僕担当でした。わかりにくい説明ですみません・・・。

今回の内容はフラットクラスタリングです。クラスタリングとはなんぞや？から始めて、実際にはどう使うのかというお話が続き、最後に実際のアルゴリズムの紹介となります。

クラスタリングとはなんぞや？

まずクラスタリングとは何者か、の説明です。クラスタリングとは簡単に言ってしまうと、「複数のドキュメントをいくつかのグループに分ける」ことです。前回までのクラシフィケーションもその点では一緒なのですが、クラシフィケーションとの違いは、クラシフィケーションでは、これは社会、これはスポーツのように、最初にある程度人手で分けておいて、それに基づいてグループ分けしていくのですが、クラスタリングでは最初から機械的にグルーピングしていく方法になります。

クラスタリングの適用例

ただグルーピングをするだけのクラスタリングですが、その適用例はいろいろとあります。たとえば、検索結果をクラスタリングして見せることによって、検索結果をわかりやすく表示したり、クラスタリングをすることによって、ドキュメント集合をディレクトリっぽく見せることができます。

また、事前にクラスタリングしておいて、そのクラスタリングされた集合に対して、従来の転置インデックスによる検索を行うことにより、検索の速度向上なども行うことができます。

k-means

本章で紹介されているクラスタリングアルゴリズムはk-meansとEMアルゴリズムの2種類です。k-meansはよく使われているので、知っている人も多いのではないかと思いますが、各クラスタをそのクラスタに属するドキュメントの重心(centroid)を使って表して、その重心と各ドキュメントの距離の和を最小化させる方法です。このアルゴリズムは2段階で構成されており、1つめは各ドキュメントを最も近い重心に割り当てる段階、2つめは各割り当てられたドキュメントから重心を再計算する段階となります。この2段階を繰り返し適用することによって、漸近的にドキュメントのクラスタへの割り当てを決めていく方法です。

次回は階層的クラスタリングです。今回はクラスタ間に階層はなかったのですが、次回はクラスタ間に階層関係がある場合(たとえばスポーツ - オリンピックみたいな)のクラスタリングです。