Introduction to Information Retrieval #16 の復習資料

しばらく間が空いてしまいました。Introduction to Information Retrieval 輪読会 16章の復習資料を以下にアップロードしました。

• http://bloghackers.net/~naoya/iir/ppt/iir_16.ppt

16章のテーマは、"Flat Clustering" で話題はクラス分類からクラスタリングへと移ります。16章ではクラスタとクラスタの間に関係性がないフラットクラスタリングを扱い、続く 17章ではクラスタ間に階層的構造を見出す階層型クラスタリング (Hierachical clustering) を扱います。

クラスタリング

13章から15章までは Naive Bayes や SVM などによる "Classification" が話の主題でした。クラスタリングも同様に情報のグルーピングを行うものですが、Classification と Clustering は教師あり学習か、教師なし学習かという点が大きく異なります。クラスタリングは人手によるカテゴリ判定なしにグルーピングを行う、教師なし学習です。

16章ではクラスタリングの基礎概念、クラスタリングの分類、情報検索におけるクラスタリングの応用例、定量的な評価の手法などを解説した後、具体的な実現方法として K-means アルゴリズムと EM アルゴリムが紹介されています。

K-means アルゴリズムはフラットクラスタリングの基礎的かつ重要なアルゴリズムで、ベクトル空間上のベクトルを、ベクトルの重心との平均距離によってクラスタリングする手法です。最初にシードになる重心を適当に選んで、再帰的に重心を移動させながらクラスタの重心を算出します。クラスタ化のルールである目的関数には RSS (Residual sum of squares) という、各ベクトルの重心からの平均距離の二乗値を利用し、これを最小化することがクラスタリングのゴールになります。書籍内では2次元のベクトルの重心が K-means アルゴリズムによって移動していく様が図解されていて、面白いです。

K-means アルゴリズムの計算量は、重心の再計算回数I、クラスタの数K、ドキュメント数N、ベクトルの次元M (ドキュメントをbag of words モデルでベクトル化しているのであれば語彙数) に対して線形 Θ(IKNM) で、階層型クラスタリングに比較すると効率は良いです。ただし、ドキュメント数やベクトルの次元はシステムの規模に合わせて大きくなっていくので、転置インデックスからコサイン類似度を求めた時同様に、ベクトルがスパースであることや単語の重要度などを考慮して計算量を下げる工夫が必要です。

EM アルゴリズムは K-means を一般化して、K-means がハードクラスタリングであるのに対しソフトクラスタリングを実現するアルゴリズムです。

次回輪講ほか

今日の輪読会、第17章は引き続きクラスタリングがテーマで、階層型クラスタリングの話でした。担当の杉本さんの和訳文書のクオリティが高すぎ (Tex で数式まで綺麗にフォーマットした文書を作成されていました) て吹きました。続く18 章は Latent Semantic Indexing です。クラスタリングもそうでしたが、ここ最近の章では扱う検索モデルがベクトル空間モデル中心に戻っています。

次回の輪読会は 2/7 (土) 予定。次回輪読会後、いつも通り復習資料をアップします。

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

Introduction to Information Retrieval

お詫び

2回ほど輪読会に参加できない回が続いたので、まだ 13 から 15 章までの復習資料がありません。暇を見て追加できればと思っています。