スペクトラルクラスタリング - Never Stop Questioning

ここを編集

工事中

はじめに

　 ココ の内容を参考にしています（もし参考にするならこのページよりリンク先を見てください）。

スペクトラルクラスタリング

　データの類似度によってグラフが定義されるとして、(1)できる限り類似度の和の減少が小さく、(2)頂点数が小さくなりすぎない、ような辺の分割を行う（N-CutとかM-Cutとかバリエーションがある）。ただ、愚直にその問題を解こうとすると半端ない計算量（NP-Hard）になるので、グラフのラプラシアン行列の固有ベクトルをデータ代わりにしてクラスタリング（k-means）することで計算量を削減したのがスペクトラルクラスタリング。

　ちなみに、近似のポイントはクラスへの分類が本来離散値で表現されないといけないところを連続値もOKにしてしまうところ。（調べきれてないだけだと思うけど）この影響はいまいち不明。一例は参考のにあるラダー状のグラフの分割。

特徴

• ハードクラスタリング

（良いところ）

• ドーナッツ型などをうまく分割などでもうまく分けてくれる
• 行列ライブラリさえあれば実装は容易

（悪いところ）

• ラプラシアン行列、その固有値・固有ベクトルを計算するコストが高い
• （ソートされた固有値の変化を見ればある程度の情報は得られるが）クラスタ数を決める必要がある

アルゴリズム

前提

• Lをデータの類似度に基づくラプラシアン行列(n x n)とする。
• k個のクラスタ数に分割する。

非正規化版

　1) Lの小さい方からk番目までの固有ベクトル(u1, ..., uk)を計算する。
　2) 計算した固有ベクトル(u1, ..., uk)を各列に持つ行列U(n x k)を作る
　3) Uの各行を一つのデータ(yi)として、k-meansでクラスタリングする。
　　 （yiの所属するクラスタをCjとする）
　4) 結果A = {Am, j = 1,2,...,k}を出力する。ここでAm = {j, yi∈Cj}。

メモ

グラフのラプラシアン行列の特徴

• シンメトリックで半正定値
• 固有値は半正定値
• すくなくとも１つの固有値が0で、その固有ベクトルは[1,1,..,1]
• 0となる固有値の数がグラフの島の数と一致

なぜk番目までの小さい固有ベクトルを使うのか？

　スペクトラルクラスタリングはmin[A1, ... Ak] Tr(H'LH) s.t. HH = Iという最適化問題に落ちる。
で、（ちゃんとやってないが確か）Tr(H'LH)は、k=nならLの固有値の和。k<nで最小化したいなら、一番小さい組み合わせにする必要があるので小さい固有値をn個使う。ちなみに正確には2番目からk番目を使う。なぜならLが必ず持つ固有ベクトル[1,1,...,1]と直交するのしかだめという条件が付くから(リンク先文献のP10下の方)。ただし、式の上では合っても変わらない（ベクトルの先頭に1が付く）。

疑問

• 近似による誤差の程度は?
• 3つ目以降の固有値＆固有ベクトルはどんな分割に対応するのか？

延長線上にある技術

• ハッシュの文脈ではアンカーグラフを考えたり、カーネル化したりという感じの技術が出ている