Co-clustering documents and words using Bipartite Spectral Graph Partitioning

Co-clustering documents and words using Bipartite Spectral Graph Partitioning

  • Inderjit S. Dhillon
  • KDD 2001

概要

  • 文書と単語の共クラスタリング
  • カット最小化として妥当な問題設定
  • スペクトラルグラフ理論の知見から固有ベクトル計算問題として緩和
  • 後はk-meansすると大体上手い

問題設定

  • $$ G=({\cal D}, {\cal W}, E) $$
    • 文書と単語の二部グラフ
    • 辺重みが謎…
  • 単語・文書クラスタリングの関係
    • 文書のクラスタが与えられた時、各単語は{最も重み和の大きい文書クラスタ}に対応する単語クラスタに属すると考える
    • というわけで、k-分割問題を考える事になる

グラフ分割

  • まずは二分割
  • ほぼいつものLaplacian二次形式を考えれば良い
  • $$ \min_{q \neq 0}\frac{q^\top L q}{q^\top W q} \text{ s.t. } q^\top We=0 $$を解きたい
    • qをいい感じにすると、大体目的関数は"cut(V1,V2)/weight(V1)+cut(V1,V2)/weight(V2)"になる
  • Lz=λWzの第二最小固有値に対応する固有ベクトルが(連続なら)答え

SVD

  • Lz=λDzの第二固有ベクトルが欲しい…どうやって解きましょうか
  • 二部グラフの場合にゴニョゴニョすると、$$ D_1^{-1/2}AD_2^{-1/2} $$の特異値分解になる
    • 扱う行列が小さいので、直接解くより速そう
    • 結局、特異ベクトルu2,v2が手に入ったら、
    • 固有ベクトルは$$ z_2 = \left[ \begin{array} \\ D_1^{-1/2}u_2 \\ D_2^{-1/2}v_2 \end{array}{} \right] $$で計算できる
  • 離散化しなければ
    • 二分割なら、z2についてk-meansするだけ
    • 多分割なら、$$ \ell = \lceil \log_2 k \rceil $$個の特異ベクトルを持ってきて、l-次元空間でk-means

まとめ

  • 頭が良い、共クラスタリングを考案したという意味でも
  • k-meansだけちょっと微妙な気がする
    • One way to approximate the optimal bipartitioningとしてsum-of-squares最小化
  • unsupervisedなものではこういうのが好きだなあ

KDD スペクトラルクラスタリング 共クラスタリング 文書クラスタリング

2017/04/26

最終更新:2017年04月26日 19:04