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

直感 #

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

数学的定式化 #

スペクトラルクラスタリングは、データをグラフとして表現し、そのグラフの分割問題を固有値問題として解く手法です。以下にその数学的な流れを示します。

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

$n$個のデータ点$x_1, x_2, \dots, x_n$が与えられたとき、点$x_i$と$x_j$の類似度をガウスカーネル（RBFカーネル）で定義します。

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

2. 次数行列 #

各ノード$i$の次数$d_i$を、そのノードに接続するエッジ重みの合計として定義します。

これを対角に並べた対角行列が次数行列$D$です。

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

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

$L$は半正定値行列であり、最小固有値は0です。実用上よく使われるのが正規化ラプラシアン$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$内のノード次数の合計です。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$の各行を単位ベクトルに正規化した後、$k$-meansなどのクラスタリングを適用して最終的なクラスター割り当てを得ます。

Pythonを用いた実験や説明 #

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

 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()

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

クラスタ数を変えるとスペクトラルクラスタリングの結果がどう変わるか確認できます。

参考文献 #