Spectral Rotation versus K-Means in Spectral Clustering - todo314 @ ウィキ

Spectral Rotation versus K-Means in Spectral Clustering

• Jin Huang, Feiping Nie, Heng Huang
• AAAI 2013

• Kindle 買ったし再開だよ

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

• $$ \sum_{i=1}^{K} \frac{s(C_i, \bar{C_i})}{\sigma(C_i)} $$
  • σは点の個数、重みの和等
  • sはカットの重み
• $$ \hat{q}_i $$をj要素がクラスタiに属するかを表すindicatorとすると
• 上の目的関数は行列とかで良さげに書ける
• 正規化とかすると↓みたいになる
• $$ \sum_{i=1}^{K}q_i^{\top}(D-W)q_i $$
• よくあるratio cut最適化問題に緩和できる
• 緩和問題を解いたらK-means！！！！

K-meansについて

• $$ \min \|Q-GH\|^2 $$の感じにかける
  • Gはindicator、Qは固有ベクトル行列
• 謎のHを固定すると、Gは求まる
• HはGが固定されると求まる
• というわけで、上2ステップをこれを反復する

Spectral Rotation

• 結局どうしたいの？
• $$ \min \|QR-G\|^2 $$
  • $$ s.t. R^{\top}R = I $$
• Rが直交行列
• ちょっと変形
• $$ \min \|Q-GR^{\top}\| $$
• K-meansとちょっとだけ違う
  • こっちには直交制約がある、それだけ
• QRを緩和で最適化した時、その後得られる解は最も良い近似だといっている？？？
• Rで回転するのがいいらしい、図を見ると

実験

• 省略
• 色々手法あるんだなあ
• 評価基準も色々あった

まとめ

• グラフはあんまり関係なかった
• 難しい・・・

AAAI k-means spectral clustering

2013-12-02 02:03:58 (Mon)