On Spectral Clustering: Analysis and an algorithm

July 23, 2022

スペクトラルクラスタリングは、類似度を辺の重みとするグラフをデータから構築し、重みをもとにカットする辺を決めて、データをクラスタに分ける。 グラフラプラシアンのようなグラフを表現した行列をつくり、その固有ベクトルを求め、固有ベクトルを列ベクトルとして並べた行列にK-meansを適用する。 もとのデータに二重丸のような凸集合でないクラスタがあるときに、最初からK-meansを適用するよりも良い結果を期待できる。 また、データ分布に確率モデルにあてはめ、どのクラスタにデータを割りあてるか確率的に決めるクラスタリングと違い、データの分布を仮定しなくてよい。

\(\mathbb{R}^l\)上の\(S=\{s_1,\dots ,s_n\}\)を\(k\)個のクラスタに分ける。 データの類似度を表すアフィニティ行列\(A\in\mathbb{R}^{n\times n}\)を、 $$ A_{ij}= \begin{cases} \exp(-\mid\mid s_i - s_j\mid\mid^2 / 2\sigma^2) & i\neq j\\ 0 & i = j\\ \end{cases} $$ とする。

\(A\)の\(i\)番目の行の合計を\((i,i)\)番目の値とする対角行列\(D\)をもって $$ L=D^{-1/2}AD^{-1/2} $$ である\(L\)の固有値の大きい順に\(k\)個の直交する固有ベクトル\(x_1,x_2,\dots , x_k\)を求め、\([x_1,x_2,\dots x_k]\in\mathbb{R}^{n\times k}\)をつくる。 \(X\)を\(Y_{ij}=X_{ij}/(\sum_j X^2_{ij})^{\frac{1}{2}}\)で正規化した\(Y\)にK-meansを適用し、\(Y\)の\(i\)番目の行が所属するクラスタに\(s_i\)を割り当てる。

論文へのリンク