スペクトラルクラスタリングの基本的な解説、および高速化手法のざっくりとした説明

久しぶりにブログを更新してみる。

以前スペクトラルクラスタリングについて記事を書いたが、そのときはだいぶ勉強不足で、少し見当違いのことを書いていた気がする。

スペクトラルクラスタリングは、本質的にはラプラシアン固有マップ法と同じことをしている。ラプラシアン固有マップ法は次元削減の手法で、もともとの高次元空間におけるデータ間の類似度が、低次元に写像した後にも反映されるように設計されている。それが結果的に類似度行列から定義されるグラフ・ラプラシアンの固有値問題に帰着されるのだ。具体的には、グラフ・ラプラシアンLの固有値を大きいほう（定式化によっては小さいほう）からk番目までをλ1, λ2, …,λk, それに対応する固有ベクトルをv1, v2, …, vk とすると、その固有ベクトルを列として並べた行列 V = (v1 v2 … vk)の各行が、各データ点の低次元空間における座標とする。このときkは、低次元空間の次元となる。

スペクトラルクラスタリングはこのデータの低次元表現に対して、k-meansなどのクラスタリングアルゴリズムを適用することによってクラスタ結果を得る。では最初からk-meansを高次元空間のデータに対して適用すればよさそうなものであるが、実はk-meansにはよく知られているように弱点がある。それは1.局所解に陥る可能性があること、2.線形分離不能なデータに対しては適切なクラスタリングができないこと、等である。スペクトラルクラスタリングの場合、k個のクラスタをつくる場合は、まずラプラシアン固有マップ法によってk次元の低次元空間へ写像する。この低次元空間において、データが線形分離になっているのがスペクトラルクラスタリングのうまいところで、これに対してk-meansを実行すれば、もともとのデータ空間においては線形分離不能でクラスタリングができなかったのに、適切にクラスタリングができるのだ。また、スペクトラルクラスタリングは正規化カットと呼ばれるコスト関数を最小化する最適化問題であり、大域解を得ることができることが理論的に保証されている。

このように、スペクトラルクラスタリングはいいことづくめのように思えるが、計算量が大きい（データ数の三乗のオーダー）といった弱点もある。最近は高速化アルゴリズムも研究されており、例えば

Fast approximate spectral clustering.
D. Yan, L. Huang, and M. I. Jordan. 15th ACM Conference on Knowledge Discovery and Data Mining (SIGKDD), Paris, France, 2009.

がある。これは、まず先に前処理としてデータに対してk-meansを実行し（クラスタ数はおおきめに）、ベクトル量子化を行う。ベクトル量子化を元のデータに対する摂動と解釈して、前処理なしのスペクトラルクラスタリングと前処理ありのスペクトラルクラスタリングの差、つまり誤分類の大きさを理論的に評価する。この誤分類の大きさをmis-clustering rateと呼んでおり、これを前処理のクラスタ数kの関数とみなす。これによって、許容できる誤分類率の範囲内でベクトル量子化が可能になる。もともとのデータ数をN,前処理におけるクラスタ数をKとすると、計算量はO（N^3）からO（K^3）に減る事になり、高速化が可能となる。

スペクトラルクラスタリングが正規化カットの最小化が帰着されることの厳密な数学的な証明は、

Learning spectral clustering.
F. R. Bach and M. I. Jordan. In S. Thrun, L. Saul, and B. Schoelkopf (Eds.), Advances in Neural Information Processing Systems (NIPS) 16, (long version), 2004.

にある。これにはまた、スペクトラルクラスタリングを教師あり学習にする方法も書いてある。
これらは両方ともMichael Jordan が共著者として入っているので、彼のページhttp://www.cs.berkeley.edu/~jordan/publications.html
から論文を読むことができる。

余談ながら、私はまだ機械学習のことを学び始めてから幾ばくもたっていないのでよくわからないのだが、このMichael Jordanはおそらく大御所なのだろう…。いろいろなところで名前が目に付く。いつかこういうようにオールラウンダーに活躍できるような研究者になりたい。