スペクトラルクラスタリングは次元圧縮しながらKmeansする手法

機械学習系のエントリを続けて書いてみる。クラスタリングについて知らない人は以下のエントリ読んでもちんぷんかんぷんだと思うので、クラスタリングという概念については知っているものとする。

それで、今日はスペクトラルクラスタリングの話。自然言語処理以外でも利用されているが、これはグラフのスペクトルに基づくクラスタリングの手法で、半教師あり学習への拡張がやりやすいのが利点。なにをするかというとクラスタリングをグラフの分割問題(疎であるエッジをカット)に帰着して解く手法で、どういうふうに分割するかによって Normalized cut (Ncut) とか Min-max cut (Mcut) とかいろいろある。

完全にグラフが分割できる場合はこれでめでたしめでたしなのだが、実世界のグラフはそんな簡単に切れないことが往々にしてある。それで近似してこのグラフ分割問題を解くのだが、Normalized cut の手法の近似はグラフの固有ベクトルを計算する問題として解けることが Meila and Shi (AISTAT-2001) で示されたので、要はグラフの固有ベクトル順にを求めればいいわけである。ちなみに同じ論文では、グラフ上のマルコフランダムウォークによって得られる遷移確率を類似度として解釈することができ、確率的な枠組みでスペクトラルクラスタリングを扱える、ということが示されている。また、グラフの正規化をすることである程度スムージングをする(正規化の方法はいろいろあるが、理論的な根拠を持った正規化だったりするので、調べるとおもしろい)。

また、2クラスの場合は最大固有ベクトル(定式化によっては最小固有ベクトルの小さい方から2番目)をそのまま使えばそれが最適な分割になっている(その固有ベクトルに対応する値が正か負かで分ければよい)が、Kクラスに分割する場合はK-1個の最大固有ベクトルを順番に使えばいい、ということが知られている。

クラスタリングの枠組みとしては、上位 K 個の最大固有ベクトルを用いて Kmeans すれば、最終的なクラスタリング結果を得ることができる。Kmeans は初期値に依存するとか全部のクラスタを同じくらいのサイズにしようとする(データが超球状になっていることを仮定)とかいう問題があるが、正規化するので Kmeans でもそこまでひどい結果にはならない(らしい)。

結局スペクトラルクラスタリングがやっているのは、正規化して PCA や SVD といった教師なしの次元圧縮(素性選択……と言っていいのか分からないが; ←記述削除しました。詳細はコメント参照)をかけたあとに Kmeans かけているだけなので、単純に Kmeans かけるのと比べると data sparseness に対するスムージングの効果が期待できるとか、最終的な固有ベクトルの結果だけ持っていればいいので分類(クラスタリング)のときに使うデータサイズを減らすことができる、という実用上の期待できる効果かな。

PCA や ICA や SVD は教師なしの距離(類似度)学習と考えることもできるが、やはり分類・クラスタリングに有効な素性(特徴量)はラベルつき事例があれば教師あり学習したほうがいいんじゃないかと思う。素性(パターン)の重み付けに自己相互情報量とか tf.idf を使ったりするのは、いわば正例だけから重みを学習しているようなものなので、それが最適化というと、迷惑メールだけからスパム判定するようなものなので……。もちろん適正なメールと紛らわしいスパムメールとを正しく分類するためには、迷惑メールだけでなく、迷惑でないメールもそれなりの数与えないと正しく学習できないのだが。(ここは昨日萩原さんとメールしていて考えたこと) 

去年一昨年としていた研究や Espresso というブートストラップアルゴリズムでは正規化した自己相互情報量を類似度尺度として用いていた(それはそれでそこそこ動く)が、この重みはちゃんと学習するべきだと思う(実用上は速度とのトレードオフかもしれないけど)。

どの論文を紹介するか悩みどころだが、理論的なことと解析的なことがバランスよくまとまっている論文としては

  • Qianjun Xu, Marie desJardins and Kiri L. Wagstaff. Active Constrained Clustering by Examining Spectral Eigenvectors. Proc of Discovery Science 2005.

かな。あと最近の論文で同様なのは

  • Tom Coleman, James Saunderson and Anthony Wirth. Spectral Clustering with Inconsistent Advance. ICML-2008.

も制約付きスペクトラルクラスタリングに対する(外れ値に対する対処が入っている)研究で参考なる。

スペクトラルクラスタリングに制約を入れる話のほうをメインで書きたかった(2月1日から東京に行くのでこの機械学習シリーズはこれで終わりにする予定だった)のだが、長くなってきたので次回乞うご期待。

cf.