PIC(Power Iteration Clustering)論文を読んだ

計算機科学

tsubosakaさんにPIC(Power Iteration Clustering)というのをお昼に紹介してもらったので、読んでみた。

Power Iteration Clustering
Frank Lin and William W. Cohen


例として文書のクラスタリングを考える。通常のクラスタリングはW=文書D×単語Tの行列の1行を1文書として、単語を要素とするベクトルで文書の近さを測る。
PICでは、W=D×Tを次元圧縮しW'=D×k(kは圧縮後の次元)という行列を使う。(←Wの説明間違いでした。参考)この圧縮された行列の各列は元の行列の固有ベクトルとなっていて、PI法(Power Iteration)で求めることができる。PI法については↓がわかりやすい。

http://aoki2.si.gunma-u.ac.jp/lecture/power-method/power.html

PI法では固有ベクトルvは

v(t+1) ∝ W * v(t)

のようにイテレーションして求めるが、vの時間変動が線形になったらイテレーションを打ち切って、k-meansでさくっとクラスタリングしてしまうというのが本手法の特徴らしい。
この方法を使うとデータ(この例では文書)に対して線形の時間・空間でクラスタリングできるらしい。でも、元々データ数に対しては線形な気がする(O(D*T^2)だと思う)ので、PICの特徴はイテレーション回数が少なくて済む以上のことはない気がしていて、実験で既存手法に比べて大幅に速くなっている理由がピンとこない。私の論文の理解が足りないせいかもしれない。気になる。。