スペクトラルクラスタリング | グラフ固有ベクトルで分割する

直感 #

データ点をノード、類似度（距離の小ささやカーネル）をエッジ重みとするグラフを考えると、密に繋がった部分同士がクラスタ候補になります。
グラフラプラシアンの低次固有ベクトルは、クラスタ間の切断コストを最小化する方向を示すため、これを座標として並べ替え、最後に通常のクラスタリングを適用すれば複雑な構造も分離できます。

具体的な数式 #

類似度行列を \(W\)、次数行列を \(D = \mathrm{diag}(d_1, \dots, d_n)\)（\(d_i = \sum_j W_{ij}\)）とすると、非正規化ラプラシアンは

$$ L = D - W. $$

ノーマライズ版は $$ L_\mathrm{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}. $$

クラスタ数 \(k\) に対して、\(L_\mathrm{sym}\) の下位 \(k\) 個の固有ベクトルを列に持つ行列 \(U\) を作り、行単位で正規化した行列を k-means などで分割します。
これはグラフの切断問題（Normalized Cut）を緩和した解に相当します。

Pythonを用いた実験や説明 #

二重円（同心円）データを SpectralClustering で分割し、非線形構造でもクラスタリングできることを確認します。

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
from sklearn.datasets import make_circles
from sklearn.cluster import SpectralClustering

X, _ = make_circles(n_samples=500, factor=0.4, noise=0.05, random_state=0)

model = SpectralClustering(
    n_clusters=2,
    affinity="rbf",
    gamma=50,
    assign_labels="kmeans",
    random_state=0,
)
labels = model.fit_predict(X)

plt.figure(figsize=(6, 5))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap="coolwarm", s=20)
plt.title("スペクトラルクラスタリング")
plt.tight_layout()
plt.show()

参考文献 #