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

直感 #

SNS の友達関係を考えます。誰と誰が仲良いかの線だけが分かっていて、GPS のような座標はありません。この人のつながりを「グループ内の線は多く、グループ間の線は少なく」なるように 2 つに分けるのがグラフ分割で、スペクトラルクラスタリングはデータ点にこの考えを持ち込みます。まず各点をノード、距離が近い（RBF カーネル値が大きい）点同士を重い辺でつないだグラフを作ります。同心円のデータなら、内側の円の点同士と外側の円の点同士は近くて重い辺でつながり、内外の円の間は遠くて軽い辺しかないので、「軽い辺だけを切る」分け方が円ごとの分割になります。

切る場所を全通り試すのは不可能なので、グラフラプラシアンの低次固有ベクトルを使います。固有ベクトルの各成分は「ノードが切断線のどちら側にいるか」を連続値で表した座標になっており、この座標に並べ替えた点は塊として分かれています。最後にその座標で k-means を走らせれば、元の空間では曲がっていた構造も分離できます。

式で書くとどこを切っているか #

スペクトラルクラスタリングは、データをグラフとして表現し、そのグラフの分割問題を固有値問題として解く手法です。類似度行列から固有ベクトルまで、5 つの段階で何を計算しているかを追います。

1. 類似度行列（ガウスカーネル） #

$n$ 個のデータ点 $x_1, x_2, \dots, x_n$ が与えられたとき、点 $x_i$ と $x_j$ の類似度をガウスカーネル（RBF カーネル）で定義します。距離が 0 なら 1、離れるほど 0 に近づく値です。

$\sigma$ はスケールパラメーターで、scikit-learn の gamma とは $\gamma = \frac{1}{2\sigma^2}$ の関係にあります。gamma=50 のように大きくすると、ごく近い点だけが重い辺でつながるグラフになります。この $w_{ij}$ を要素とする $n \times n$ の対称行列 $W = (w_{ij})$ が**類似度行列（重み付き隣接行列）**です。

2. 次数行列 #

各ノード $i$ の次数 $d_i$ は、そのノードに接続する辺の重みの合計で、「どれだけ多くの仲間と強くつながっているか」を表します。

$d_1, \dots, d_n$ を対角に並べた対角行列が次数行列 $D$ です。

3. グラフラプラシアン #

次数行列 $D$ と類似度行列 $W$ から、非正規化グラフラプラシアン $L$ を定義します。

$L$ は半正定値行列で、最小固有値は 0 です（対応する固有ベクトルは全成分が同じ値で、「全部を 1 つのクラスタにする」切り方に相当します）。実用上よく使われるのが正規化ラプラシアン $L_{\text{sym}}$ で、次数の大きいノードと小さいノードの影響をそろえます。

もう 1 つの正規化形式としてランダムウォークラプラシアン $L_{\text{rw}}$ もあります。

4. 正規化カット（NCut）目的関数 #

グラフを 2 つの部分集合 $A$ と $B$ に分割するとき、分割の良さを測る指標が**正規化カット（Normalized Cut）**です。

$\text{cut}(A, B) = \sum_{i \in A, j \in B} w_{ij}$ はクラスター間を横切る辺の重みの合計、$\text{vol}(A) = \sum_{i \in A} d_i$ は部分集合 $A$ 内のノード次数の合計です。分母で割るのは、1 点だけを切り離す「安いが無意味な切り方」に罰を与えるためです。NCut を最小化すると、クラスター間の結合が弱く、クラスター内の結合が強い分割が得られます。

5. 固有値問題への緩和 #

NCut の最小化は NP 困難な離散最適化問題ですが、「どちら側か」を表すインジケーターベクトルを実数値に緩和すると、次の一般化固有値問題に帰着されます。

これは正規化ラプラシアン $L_{\text{sym}}$ の固有値問題と等価です。

クラスター数 $k$ に対して、$L_{\text{sym}}$ の最小の $k$ 個の固有値に対応する固有ベクトル $u_1, u_2, \dots, u_k$ を列に並べた行列 $U \in \mathbb{R}^{n \times k}$ を作ります。$U$ の $i$ 行目が点 $x_i$ の新しい座標で、各行を単位ベクトルに正規化した後、$k$-means などのクラスタリングを適用して最終的なクラスター割り当てを得ます。scikit-learn の assign_labels="kmeans" がこの最終段です。

Pythonで確かめる #

次のコードは make_circles で内側と外側の 2 重円 500 点を作り、SpectralClustering(n_clusters=2, affinity="rbf", gamma=50) で分割します。k-means なら円を縦に半分に割るデータで、内側の円と外側の円が別の色になれば成功です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import numpy as np
import matplotlib.pyplot as plt
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()

実行結果の読み方 #

図では内側の小さな円と外側の大きな円がそれぞれ 1 色に塗られます。重心で分ける k-means では左右半分に割れるデータなので、この色分けが「グラフの軽い辺を切った」結果です。gamma を 5 まで下げると円の間の辺が重くなります。途中から k-means と同じ縦割りに戻るので、gamma の下限を探る目安になります。

クラスタ数とスペクトラルクラスタリング #

スライダーで n_clusters を 2 から 7 まで動かすと、月型の 200 点の分割とシルエット係数が変わります。2 では 2 つの月がそのまま分かれてシルエット係数 0.42、3 以上では月が途中で切られて係数が 0.33〜0.45 の間で揺れます。固有ベクトルの本数も n_clusters と同じだけ増えるので、クラスタ数はシルエット係数と元データの形を両方見て決めます。

使いどころと落とし穴 #

スペクトラルクラスタリングが向くのは、同心円や三日月のように重心では分けられない形で、点の数が数千以下の場面です。SNS のつながりや文書の引用関係のように、座標がなく「類似度」だけがある場合には affinity="precomputed" で類似度行列を直接渡せます。落とし穴は gamma の感度で、小さすぎると全点がつながって k-means と同じ結果に、大きすぎるとグラフが細かく分断されてノイズのような小クラスタが出ます。affinity="nearest_neighbors" にして n_neighbors を 10 前後にすると、距離スケールに依存しない近傍グラフになり調整が楽になります。点が数万を超えるなら、固有値分解の $O(n^3)$ を避けて DBSCAN や UMAP で埋め込んでからの k-means に切り替えます。

まとめ #

スペクトラルクラスタリングは、RBF カーネルで作った類似度行列 $W$ からラプラシアン $L = D - W$ を作り、小さい固有値 $k$ 個の固有ベクトルを新しい座標にして k-means で分ける手法です。この手順は、クラスター間を横切る辺の重みを次数で正規化した NCut を最小化する問題の連続緩和になっています。make_circles の同心円を gamma=50 で 2 つの円に分けられたのは、円の間の辺がほぼ 0 になって「軽い辺を切る」分割が円ごとになったからです。固有値分解の計算量から数千点が上限で、gamma や n_neighbors の調整が結果を左右します。

参考文献 #