🎨 直感で掴む — 「繋がりを断ち切る最良の場所」を探す

k-means が失敗するとき

2 つの 半月型データ を考えましょう。 人間の目には明らかに 2 つのクラスタですが、 k-means は「中心からの距離」で割り当てるため、 中心が両クラスタの中間に来てしまい、 上下半分でばっさり切る 失敗をします。

スペクトラルクラスタリングは違うアプローチを取ります：

1. 各点を 「ノード」、 近い点同士を 「エッジ」 で結んでグラフ化
2. 「エッジが少ない切れ目」＝クラスタの境界 を見つける
3. 半月内部は密に繋がり、 2 つの半月の間は疎なので、 ここを切れば自然な分離が得られる

「グラフカット」のアナロジー

SNS の友達ネットワークを思い浮かべてください。 同じサークルの人同士は密に繋がり、 別サークルとは疎。 ネットワーク全体を 2 グループに分けるとき、 「切るエッジが最も少ない場所」 で分割すれば、 サークル境界を自然に発見できます。 これがスペクトラルクラスタリングのアイデア：

3 ステップの全体像

📐 数式 — スペクトラルクラスタリングの定式化

STEP 1：類似度行列 $W$ の構築

$n$ 個のデータ点 $\{x_1, \dots, x_n\}$ から $n \times n$ の類似度行列 $W$ を作ります。 代表的な 3 つの構成法：

STEP 2：グラフラプラシアン $L$ の構築

次数行列 $D$ を $D_{ii} = \sum_j W_{ij}$（i 番目の点の総繋がり強度）とおいて、 3 種類のラプラシアンを定義：

STEP 3：固有値分解 + k-means

ラプラシアン $L$ の 下位 k 個（最小固有値に対応する） の固有ベクトル $u_1, u_2, \dots, u_k$ を列に並べて $U \in \mathbb{R}^{n \times k}$ を作ります。 $U$ の各行 $y_i \in \mathbb{R}^k$ が点 $x_i$ の 新しい埋め込み座標。 これに対して通常の k-means を実行してクラスタを得る。

🔬 数式を「言葉」で読み解く

類似度行列 $W$

次数行列 $D$

ラプラシアン $L = D - W$

固有ベクトル空間で k-means する理由

🧮 SSDSE-B で「47 都道府県を 4 クラスタに分ける」

SSDSE-B-2026 の数値指標から 47 都道府県の k-NN 類似度グラフを作り、 スペクトラルクラスタリングで 4 クラスタに分けます。

STEP 1：類似度グラフの構築

各県を多次元ベクトルとして、 k=10 の k-NN グラフ を作成。 つまり各県は自分と類似度の高い上位 10 県とエッジで結ぶ。

STEP 2：ラプラシアンの固有値分解

$L_{\text{sym}}$ の固有値を昇順に並べると、 典型的には：

固有値ギャップ法：4 番目と 5 番目の固有値が大きく離れる位置でクラスタ数を決める（eigengap heuristic）。

STEP 3：典型的なクラスタ分け結果

解釈：単純な k-means でも近い結果が得られますが、 スペクトラル手法は 「直接距離が遠くても、 共通の隣人を介して繋がる」 という関係性ベースの構造を捉えるため、 より自然な分類になります。 たとえば「秋田と高知は地理的に遠いが、 共に過疎・高齢化県という構造的類似性」がスペクトラル手法では強調されます。

🐍 Python 実装 — SSDSE-B でスペクトラルクラスタリング

① 基本：sklearn.cluster.SpectralClustering

🎯 このコードでやること: SSDSE-B-2026 全数値特徴量で sklearn の SpectralClustering を実行し 47 都道府県を 4 クラスタに分ける

import pandas as pd
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import SpectralClustering

# データ読込・前処理
df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='utf-8', skiprows=1)
df = df[df['年度'] == df['年度'].max()].copy()
df = df.set_index('都道府県')
features = df.select_dtypes(include=[np.number]).dropna(axis=1)

X = StandardScaler().fit_transform(features)

# スペクトラルクラスタリング（k-NN グラフベース、 4 クラスタ）
sc = SpectralClustering(
    n_clusters=4,
    affinity='nearest_neighbors',
    n_neighbors=10,
    assign_labels='kmeans',
    random_state=0
)
labels = sc.fit_predict(X)

# 結果表示
result = pd.DataFrame({'都道府県': features.index, 'cluster': labels})
for c in sorted(result['cluster'].unique()):
    members = result[result['cluster'] == c]['都道府県'].tolist()
    print(f'クラスタ {c} ({len(members)} 県): {", ".join(members)}')

💬 読み方: k-NN グラフをラプラシアンの固有値で分割するため、 k-means では捉えられない『東京 1 県だけ』『地方小規模 5 県』といった非凸構造を抽出できる。 グラフ理論を経由するスペクトラル法の真骨頂。

② RBF カーネル版

🎯 このコードでやること: RBF カーネルで類似度を全ペア計算するスペクトラルクラスタリングを実行

# RBF カーネルで類似度を作る
sc_rbf = SpectralClustering(
    n_clusters=4,
    affinity='rbf',
    gamma=1.0 / X.shape[1],  # 次元数の逆数（標準）
    assign_labels='kmeans',
    random_state=0
)
labels_rbf = sc_rbf.fit_predict(X)

💬 読み方: RBF カーネルは N²個のペア類似度をすべて作るため、 大規模データではメモリ爆発。 N≤数千なら RBF が滑らかな境界を作り、 N≫数千なら k-NN グラフ ('nearest_neighbors') が現実解。

③ 手動実装：ラプラシアン固有値分解を可視化

🎯 このコードでやること: 親和性行列 (Affinity) から正規化グラフラプラシアン L_sym を構築し固有値分解する

from sklearn.neighbors import kneighbors_graph
from scipy.sparse.linalg import eigsh
from scipy.sparse import diags
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import japanize_matplotlib

# === 1. k-NN グラフ ===
W = kneighbors_graph(X, n_neighbors=10, mode='connectivity', include_self=False)
W = (W + W.T) / 2  # 対称化

# === 2. 次数行列とラプラシアン ===
d = np.array(W.sum(axis=1)).flatten()
D = diags(d)
L = D - W  # 非正規化
# 対称正規化
D_inv_sqrt = diags(1.0 / np.sqrt(d + 1e-10))
L_sym = diags(np.ones(len(d))) - D_inv_sqrt @ W @ D_inv_sqrt

# === 3. 固有値分解（最小 k+1 個）===
k = 4
eigvals, eigvecs = eigsh(L_sym.astype(float), k=k+1, which='SM')
print('小さい順の固有値:', eigvals.round(4))

# 固有値ギャップを可視化
plt.figure(figsize=(8, 4))
plt.plot(range(1, len(eigvals)+1), eigvals, 'o-', markersize=10)
plt.xlabel('固有値の順位')
plt.ylabel('固有値')
plt.title('固有値スペクトル（ギャップでクラスタ数を判定）')
plt.grid(True)
plt.show()

# === 4. 下位 k 固有ベクトルで k-means ===
U = eigvecs[:, 1:k+1]  # 最小は 0 を除く
# 対称正規化版では行を単位ベクトル化
U_norm = U / (np.linalg.norm(U, axis=1, keepdims=True) + 1e-10)
labels_manual = KMeans(n_clusters=k, n_init=10, random_state=0).fit_predict(U_norm)

# === 5. PCA で 2 次元可視化 ===
from sklearn.decomposition import PCA
X_2d = PCA(n_components=2).fit_transform(X)
plt.figure(figsize=(12, 8))
scatter = plt.scatter(X_2d[:, 0], X_2d[:, 1], c=labels_manual, cmap='Set1', s=200)
for i, name in enumerate(features.index):
    plt.annotate(name, (X_2d[i, 0], X_2d[i, 1]), fontsize=10)
plt.title('スペクトラルクラスタリング結果（PCA で 2 次元表示）')
plt.xlabel('PC1')
plt.ylabel('PC2')
plt.legend(*scatter.legend_elements(), title='クラスタ')
plt.tight_layout()
plt.show()

💬 読み方: 正規化ラプラシアン L_sym = I - D^{-1/2} W D^{-1/2} の最小 k 固有値に対応する固有ベクトルをクラスタリングに使う。 固有値ギャップが大きいところでクラスタ数 k を決めるのが定石 (eigen-gap heuristic)。

④ クラスタ数の自動推定（Eigengap heuristic）

🎯 このコードでやること: 固有値ギャップを可視化し、 最適クラスタ数 k を選定する

# 多めに固有値を計算
eigvals_all, _ = eigsh(L_sym.astype(float), k=15, which='SM')
eigvals_all = np.sort(eigvals_all)

# 連続する固有値の差（ギャップ）が最大になる位置を見つける
gaps = np.diff(eigvals_all)
best_k = np.argmax(gaps[:10]) + 1  # +1 は 0 番目を除いたシフト
print(f'推定クラスタ数 k = {best_k}')

plt.figure(figsize=(8, 4))
plt.plot(range(1, len(eigvals_all)+1), eigvals_all, 'o-')
plt.axvline(best_k + 0.5, color='red', linestyle='--', label=f'推定 k={best_k}')
plt.xlabel('順位')
plt.ylabel('固有値')
plt.legend()
plt.show()

💬 読み方: λ_k と λ_{k+1} の差 (eigen-gap) が最も大きい場所がクラスタ境界。 ドメイン知識と一致するか確認しつつ k を選ぶ。 k=4 が地理的・経済的な日本のクラスタリングと整合する。

⑤ k-means との比較

🎯 このコードでやること: スペクトラル埋め込み (固有ベクトル空間) で k=4 のクラスタを 2D に可視化

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score, adjusted_rand_score

# k-means
labels_km = KMeans(n_clusters=4, random_state=0, n_init=10).fit_predict(X)
# スペクトラル
labels_sc = sc.fit_predict(X)

# シルエット係数で品質比較
print('シルエット（k-means）  :', silhouette_score(X, labels_km))
print('シルエット（spectral） :', silhouette_score(X, labels_sc))

# 2 つの結果の一致度
print('ARI:', adjusted_rand_score(labels_km, labels_sc))

💬 読み方: スペクトラル埋め込みは元の高次元空間では分かれないクラスタを、 線形分離可能な空間に変換する非線形マッピング。 散布図で人間が目視確認できるのが大きな利点。

⚠️ スペクトラルクラスタリングの 5 つの落とし穴

🌐 関連手法・派生

スペクトラル系手法のバリエーション

他のクラスタリング手法との比較

🧩 グラフカット理論との関係

スペクトラルクラスタリングは、 グラフを 2 つに分割する 「グラフカット問題」 の連続緩和として導出されます。

カットの定義

頂点集合を $V = A \sqcup B$ に分割するとき、 切り捨てるエッジの重み合計：

3 つのカット基準

連続緩和 → 固有値問題

NCut は NP 困難な離散最適化問題ですが、 「分割を表す 0/1 ベクトル」を 実数ベクトルに緩和すると、 ラプラシアンの第 2 固有値（Fiedler 値）問題に帰着します（Shi-Malik 2000）：

多クラスタへの拡張

k 分割の場合、 下位 k 個の固有ベクトル から構成される行列の 各行を k-means することで、 連続緩和解を離散クラスタに射影します。 これが現代スペクトラルクラスタリングの定式化です。

🗺 概念マップ — スペクトラル手法の数学的位置づけ

歴史的展開

🎓 SSDSE-B 完全パイプライン（保存版）

これまでの議論を全てまとめ、 SSDSE-B-2026 で「47 都道府県のスペクトラルクラスタリング」を End-to-End で実行する完全版コード：

🎯 このコードでやること: クラスタ妥当性指標 (Silhouette score, Calinski-Harabasz) で k=2..8 の候補を評価

import pandas as pd
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import SpectralClustering, KMeans
from sklearn.neighbors import kneighbors_graph
from sklearn.metrics import silhouette_score, adjusted_rand_score
from sklearn.decomposition import PCA
from scipy.sparse.linalg import eigsh
from scipy.sparse import diags
import matplotlib.pyplot as plt
import japanize_matplotlib

# === 1. データ取得 ===
df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='utf-8', skiprows=1)
df = df[df['年度'] == df['年度'].max()].copy()
df = df.set_index('都道府県')
features = df.select_dtypes(include=[np.number]).dropna(axis=1)
prefs = list(features.index)
print(f'データ形状: {features.shape}')  # (47, ~100)

# === 2. 標準化 ===
X = StandardScaler().fit_transform(features)

# === 3. 固有値スペクトルでクラスタ数推定 ===
W = kneighbors_graph(X, n_neighbors=10, mode='connectivity', include_self=False)
W = (W + W.T) / 2
d = np.array(W.sum(axis=1)).flatten()
D_inv_sqrt = diags(1.0 / np.sqrt(d + 1e-10))
L_sym = diags(np.ones(len(d))) - D_inv_sqrt @ W @ D_inv_sqrt

eigvals, _ = eigsh(L_sym.astype(float), k=15, which='SM')
eigvals = np.sort(eigvals)
gaps = np.diff(eigvals)
k_est = np.argmax(gaps[1:10]) + 2
print(f'推定クラスタ数 k = {k_est}')

# === 4. スペクトラルクラスタリング ===
sc = SpectralClustering(n_clusters=k_est, affinity='nearest_neighbors',
                        n_neighbors=10, assign_labels='kmeans',
                        random_state=0)
labels_sc = sc.fit_predict(X)

# k-means との比較
labels_km = KMeans(n_clusters=k_est, random_state=0, n_init=10).fit_predict(X)
print(f'シルエット（spectral） : {silhouette_score(X, labels_sc):.3f}')
print(f'シルエット（k-means）  : {silhouette_score(X, labels_km):.3f}')
print(f'ARI 一致度: {adjusted_rand_score(labels_sc, labels_km):.3f}')

# === 5. クラスタ別の都道府県リスト ===
for c in sorted(set(labels_sc)):
    members = [prefs[i] for i, l in enumerate(labels_sc) if l == c]
    print(f'クラスタ {c} ({len(members)} 県): {", ".join(members)}')

# === 6. PCA で 2D 可視化 ===
X_2d = PCA(n_components=2).fit_transform(X)
fig, axes = plt.subplots(1, 2, figsize=(20, 9))
for ax, labels, title in zip(axes, [labels_sc, labels_km],
                              ['Spectral Clustering', 'k-means']):
    scatter = ax.scatter(X_2d[:, 0], X_2d[:, 1], c=labels, cmap='Set1', s=300)
    for i, name in enumerate(prefs):
        ax.annotate(name, (X_2d[i, 0], X_2d[i, 1]), fontsize=9)
    ax.set_title(title)
    ax.set_xlabel('PC1')
    ax.set_ylabel('PC2')
plt.tight_layout()
plt.savefig('spectral_vs_kmeans.png', dpi=120)
plt.show()

💬 読み方: Silhouette は -1〜+1 で「クラスタの分離度」、 0.5 以上で良好な分割。 Calinski-Harabasz は分散比で大きいほど良い。 両指標が一致して k=4 を支持する場合、 自信を持って採用できる。

典型結果：スペクトラルクラスタリングは 「都市圏 / 地方経済 / 中規模 / 過疎」 という社会経済的に解釈しやすい 4 クラスタを抽出。 k-means と 7〜8 割は一致するが、 境界県の振り分け や 地理的に離れた似たプロファイル県（秋田と高知など）の扱いで差が出る。

🔗 関連用語（前提・並列・発展）

📥 前提

🔁 並列

🚀 発展・応用

🧪 「半月データ」古典実験 — k-means が完全失敗する場面

スペクトラルクラスタリングの教科書で必ず登場する「半月データ（two moons）」で、 k-means とスペクトラル手法の 劇的な差 を確認します。 SSDSE 都道府県データは比較的「球状」に近いため、 差が見えにくい。 そこでこの古典実験を併載します。

実装

🎯 このコードでやること: k-means とスペクトラルクラスタリングを比較し、 非凸データへの強さを示す

from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, SpectralClustering
import matplotlib.pyplot as plt
import japanize_matplotlib

# 200 点 × 2 半月（教育用の標準データセット、 sklearn 同梱）
X, y_true = make_moons(n_samples=200, noise=0.05, random_state=0)

# k-means
labels_km = KMeans(n_clusters=2, random_state=0, n_init=10).fit_predict(X)

# スペクトラル（k-NN グラフ）
labels_sc = SpectralClustering(
    n_clusters=2, affinity='nearest_neighbors',
    n_neighbors=10, random_state=0
).fit_predict(X)

# スペクトラル（RBF）
labels_sc_rbf = SpectralClustering(
    n_clusters=2, affinity='rbf', gamma=20, random_state=0
).fit_predict(X)

# 並べて可視化
fig, axes = plt.subplots(1, 3, figsize=(18, 6))
for ax, labels, title in zip(
        axes,
        [labels_km, labels_sc, labels_sc_rbf],
        ['k-means（失敗）', 'Spectral (k-NN)', 'Spectral (RBF)']):
    ax.scatter(X[:, 0], X[:, 1], c=labels, cmap='coolwarm', s=40)
    ax.set_title(title)
plt.tight_layout()
plt.savefig('moons_comparison.png', dpi=120)
plt.show()

💬 読み方: k-means は『各クラスタが球状』を仮定するため、 円環・三日月などの非凸形状で破綻。 スペクトラルはグラフ近傍関係を見るため、 連結成分として正しく分離できる。 これがスペクトラル法を使う最大の動機。

結果

渦巻きデータ、 環状データでも同様の優位性

同じ実験を make_circles（同心円）や 3 重渦巻きで繰り返すと、 k-means は常に失敗、 スペクトラル法は構造を捉えます。 これは 「ユークリッド距離での近さ」と「グラフ上の繋がりの近さ」が異なる 例です。 半月の凸側同士は直線距離で近いが、 三日月の輪郭をたどる「経路距離」では遠い。 スペクトラル法はこの「経路距離」を暗黙的に捉えます。

🔬 マニフォールド学習との関係

スペクトラルクラスタリングは、 「データは高次元空間に埋め込まれた低次元マニフォールド（多様体）上に乗っている」というマニフォールド仮説と密接に関係します。

Laplacian Eigenmaps（Belkin & Niyogi, 2003）

スペクトラルクラスタリングの「k-means する直前の固有ベクトル空間」をそのまま 次元削減の結果として使うのが Laplacian Eigenmaps。 数学的にはほとんど同じ枠組み：

1. 類似度グラフ $W$ を作る
2. ラプラシアン $L$ の下位 d 固有ベクトル $u_1, \dots, u_d$
3. $U \in \mathbb{R}^{n \times d}$ の各行が元データ点の 低次元埋め込み

マニフォールド学習手法の系譜

スペクトラルクラスタリングと Laplacian Eigenmaps は 「同じ計算の異なる出口」 です。 「固有ベクトル空間で k-means したらクラスタ」、 「固有ベクトル空間の座標をそのまま返したら次元削減」。 これが分野横断的な強力さの源泉。

カーネル PCA との等価性

正規化ラプラシアン $L_{\text{sym}}$ の固有ベクトル分解は、 正規化された類似度行列のカーネル PCA と数学的に等価であることが示されています（Bengio ら, 2003）。 つまり：

🌍 SNS グラフ・コミュニティ検出への応用

スペクトラルクラスタリングは「グラフのクラスタリング」が本質なので、 もともとグラフデータ（SNS、 共起ネットワーク、 引用ネットワーク）に強力です。

典型的ワークフロー

1. SNS から「フォロー関係」「いいね関係」を取得し、 隣接行列 $A$ を構築
2. $A$ を類似度行列 $W$ として扱い、 ラプラシアン $L$ を計算
3. 下位 k 固有ベクトルで k-means → コミュニティ検出

他のコミュニティ検出手法との比較

実例：Karate Club

Zachary's Karate Club（1977）は社会ネットワーク分析の古典データセット。 34 名の空手クラブが内部対立で 2 つに分裂した実際のデータ。 スペクトラル法は 分裂後の 2 派閥を 100% 正確に予測することが知られており、 教科書例として頻出：

🎯 このコードでやること: 47 都道府県のクラスタ結果を日本地図上にコロプレス図でプロットする

import networkx as nx
from sklearn.cluster import SpectralClustering
import numpy as np

G = nx.karate_club_graph()
A = nx.to_numpy_array(G)

# 真のラベル（分裂後の派閥）
true_labels = [G.nodes[i]['club'] for i in range(34)]
true_labels_num = [0 if x == 'Mr. Hi' else 1 for x in true_labels]

# スペクトラル
sc = SpectralClustering(n_clusters=2, affinity='precomputed', random_state=0)
pred = sc.fit_predict(A)

# 精度
from sklearn.metrics import adjusted_rand_score
print('ARI:', adjusted_rand_score(true_labels_num, pred))  # ~1.0 になる

💬 読み方: クラスタが地理的に隣接していれば、 地域経済・産業構造の類似性を捉えている可能性が高い。 散らばっていれば、 産業や人口など別軸でのクラスタリングと言える。 地図表示で解釈性が大きく向上する。

🎢 大規模化技法 — $n > 10^5$ でも回す

標準的スペクトラルクラスタリングは $O(n^3)$ の固有値分解を必要とし、 メモリも $O(n^2)$ を要するため、 数万件以上のデータでは現実的に動かない。 現代的には以下の近似手法が標準：

① Nyström 近似

$n$ 点から $m \ll n$ 個のサンプルだけをランドマークとして選び、 これらを用いて全点の固有ベクトルを近似する手法（Fowlkes ら, 2004）。 計算量を $O(m^2 n)$ に削減：

1. $n$ 点から $m$ 個をサンプリング
2. $m \times m$ の類似度行列の完全固有値分解
3. 残りの $n - m$ 点を「重み付き内挿」で埋め込み

典型的に $m = \sqrt{n} \sim n^{2/3}$ で十分。 sklearn の SpectralClustering でも内部使用可能。

② 疎グラフ + ARPACK

k-NN グラフは本質的に疎（各ノードが繋がる先は数十個）。 これを scipy.sparse で表現し、 ARPACK の eigsh で疎固有値分解すれば、 $n \approx 10^5$ 程度まで処理可能：

🎯 このコードでやること: スペクトラルクラスタリングの結果と階層クラスタリング (Ward 法) を比較

from scipy.sparse.linalg import eigsh
from sklearn.neighbors import kneighbors_graph

W = kneighbors_graph(X, n_neighbors=15, mode='distance', include_self=False)
W = (W + W.T) / 2  # 対称化
# RBF カーネルで重み付け
sigma = np.median(W.data)
W.data = np.exp(-W.data**2 / (2 * sigma**2))

# 疎ラプラシアン
n = W.shape[0]
d = np.array(W.sum(axis=1)).flatten()
D_inv_sqrt = sp.diags(1.0 / np.sqrt(d))
L = sp.eye(n) - D_inv_sqrt @ W @ D_inv_sqrt

# 疎固有値分解（最小 k+1 個）
eigvals, eigvecs = eigsh(L, k=k+1, which='SM')

💬 読み方: ARI = 0.62 は中程度の一致。 スペクトラル法はグラフ構造を、 Ward 法は距離分散を最小化するため、 視点が異なる。 ドメイン知識と照らして、 解釈しやすい方を選択するのが実務的判断。

③ Power Iteration Clustering（PIC）

固有値分解を陽に行わず、 累乗法（power iteration） で第 1 固有ベクトル相当を近似する手法（Lin & Cohen, 2010）。 数十回の行列ベクトル積で済むため超高速。 精度は劣るが、 数百万ノード規模で実用可能。

④ Coresets + スペクトラル

データ全体を代表する小さな 「コアセット」 をデータ圧縮で抽出し、 そこでスペクトラル法を実行 → 全データに割当を伝播する手法。 理論保証付き。

⑤ GPU + ランダム射影

類似度行列をランダム射影で低ランク近似し、 GPU で並列化（FAISS など）。 数億ノード規模の本番システムで使用。

🎯 スペクトラルクラスタリングの評価指標

クラスタリングは「正解」がないことが多いため、 評価指標の使い分けが重要です。

外的評価指標（真のラベルがある場合）

内的評価指標（真のラベルがない場合）

クラスタ数 k の選択指標

• Eigengap heuristic：固有値の大きなギャップで判定（理論的根拠あり、 von Luxburg 2007）
• Elbow 法：クラスタ内分散を k でプロットし「肘」を探す
• Silhouette 法：複数の k でシルエット係数を比較し最大化
• Gap 統計量：ランダムデータと比較した「クラスタ構造の強さ」
• BIC / AIC：確率モデル仮定下での情報量基準

🎨 画像セグメンテーションへの応用 — Normalized Cut の原点

スペクトラルクラスタリングの理論的進歩を最も大きく加速したのは、 1997-2000 年の Shi & Malik による Normalized Cut（NCut） の画像セグメンテーション応用です。 IEEE TPAMI 2000 の論文「Normalized Cuts and Image Segmentation」は被引用 25,000 回以上の歴史的論文。

画像のグラフ化

1 枚の画像をグラフに変換する方法：

• ノード＝各ピクセル（または superpixel）
• エッジ重み＝近隣ピクセル間の類似度（色、 テクスチャ、 位置）
• 典型的な類似度関数：$W_{ij} = \exp(-\frac{\|F_i - F_j\|^2}{\sigma_F^2}) \cdot \exp(-\frac{\|X_i - X_j\|^2}{\sigma_X^2})$（$F$＝色特徴、 $X$＝座標）

NCut の数学的意義

MinCut は「1 ピクセルだけ切り離す」極小カットを返す問題があった。 NCut は カットを「クラスタの体積」で正規化することで、 バランスの取れた分割を導きます：

現代の画像セグメンテーション

2010 年代以降、 画像セグメンテーションは深層学習（U-Net, Mask R-CNN, SAM）に主役を譲りましたが、 スペクトラル法は今でも：

• 医療画像のセグメンテーション（病変領域抽出）
• 衛星画像の土地利用分類
• 顕微鏡画像の細胞分離
• 深層学習の前処理として superpixel 生成（SLIC + NCut）

などで現役。 特に 「ラベル付きデータが少ない場合」に教師なし手法として有効です。

🧠 グラフニューラルネットワーク（GNN）との関係

2017 年以降、 GNN（Graph Neural Network）が爆発的に発達。 これとスペクトラルクラスタリングは 同じグラフラプラシアン を共有する近縁手法です。

スペクトラル GCN（Kipf & Welling, 2017）

有名な Graph Convolutional Network（GCN） は、 グラフ畳み込みを正規化ラプラシアン上で定義：

スペクトラルクラスタリングと GCN の対応

「スペクトラルクラスタリング」を GNN の文脈で見ると、 「1 層のラプラシアン演算 + 固有ベクトル抽出 + k-means」と理解できる。 一方 GCN は「複数層の非線形ラプラシアン演算 + 分類」。 学習可能性が異なるだけで、 数学的基盤は共通です。

現代のクラスタリング GNN

• DMoN（Deep Modularity Networks）— 学習可能なスペクトラルクラスタリング
• MinCutPool— GNN にスペクトラルカット制約を導入
• SCAN— Self-supervised Clustering Network
• DEC（Deep Embedded Clustering）— 埋め込み + クラスタリングを同時学習

🌌 ベンチマークデータでの体系的比較

スペクトラルクラスタリングの威力を体感するため、 sklearn 内蔵の代表的データセットで他手法と比較：

凡例：◎ 完璧／○ ほぼ正確／△ 部分的に正確／✗ 失敗

結論：sklearn 公式の「Comparing different clustering algorithms on toy datasets」のページが包括的で参考になります。 一般則：

• 球状クラスタなら k-means が最速・最安定
• 非凸形状なら DBSCAN かスペクトラル
• 樹形図が欲しいなら階層的
• 外れ値検出も同時にしたいなら DBSCAN
• グラフデータ・ネットワーク分析ならスペクトラル一択

🎢 パラメータチューニング実践ガイド

スペクトラルクラスタリングは パラメータ感度が高い 手法です。 「とりあえずデフォルト」では失敗することが多いため、 体系的なチューニング手順が重要。

調整すべき 5 つのパラメータ

Median heuristic（σ の自動選択）

RBF カーネルの幅 $\sigma$ を、 全点対距離の中央値に設定する経験則：

from scipy.spatial.distance import pdist
sigma = np.median(pdist(X))
gamma = 1.0 / (2 * sigma**2)
  

クラスタ数選択のロバスト戦略

1. Eigengap heuristic：第 k 固有値と第 k+1 固有値のギャップが最大の k を選ぶ（von Luxburg 推奨）
2. シルエット係数で検証：3, 4, 5, ... と試して最大化する k
3. 安定性検証：データを bootstrap してクラスタリング → 結果の Jaccard 類似度 ≥ 0.8 なら信頼できる
4. ドメイン知識：8 地方区分、 業界分類などの自然な数

パラメータ感度分析の自動化

from sklearn.cluster import SpectralClustering
from sklearn.metrics import silhouette_score
import itertools

best = {'score': -1, 'params': None}
for k, n_nbrs in itertools.product([3,4,5,6,7], [5,10,15,20]):
    sc = SpectralClustering(n_clusters=k, affinity='nearest_neighbors',
                            n_neighbors=n_nbrs, random_state=0)
    try:
        labels = sc.fit_predict(X)
        if len(set(labels)) < 2:
            continue
        score = silhouette_score(X, labels)
        print(f'k={k}, n_nbrs={n_nbrs}: silhouette={score:.3f}')
        if score > best['score']:
            best = {'score': score, 'params': (k, n_nbrs)}
    except Exception as e:
        pass

print(f'\\n最適: k={best["params"][0]}, n_nbrs={best["params"][1]}, score={best["score"]:.3f}')
  

📊 SSDSE での実用シナリオ — 「地域類型化」の活用例

スペクトラルクラスタリングで得た「47 都道府県の 4 クラスタ」は、 様々な実務応用に活かせます。

シナリオ 1：政策シミュレーション

同じクラスタの県は社会経済プロファイルが類似しているため、 1 県で実施した政策の効果を 同クラスタの他県に外挿できる可能性が高い。 例：「秋田で実施した高齢者支援策の効果」は「島根、 高知、 山形」でも類似結果が期待できる。 これは 合成統制法（synthetic control method）の前段として使われます。

シナリオ 2：マーケティング・地域分析

小売チェーンの出店戦略で、 既出店の県と「同クラスタの未出店県」を優先候補に。 顧客プロファイルが類似していると期待でき、 既存ノウハウの転用が利く。

シナリオ 3：ベンチマーク選択

地方自治体の比較分析で、 「自県と類似する県」をベンチマークとして選ぶことで、 客観的な比較が可能になる。 「東京と秋田を比較」は不公平だが、 「秋田と高知、 島根、 山形」なら同じクラスタ内での比較で意味がある。

シナリオ 4：欠損値補完

ある県で特定指標が欠損していたら、 同クラスタの他県の平均値で補完するのが、 全国平均で補完するより精度が高い。 これは k-NN imputationの応用版。

シナリオ 5：異常検知

「過去 5 年間、 クラスタ ④（過疎県）に属していた A 県が、 今年クラスタ ③（地方経済型）に移動した」というような変化は、 構造的転換のシグナル。 産業構造や人口動態の重要な変化を捉える指標になります。

クラスタリング結果の正当性確認 5 ステップ

1. 各クラスタの代表指標を要約：平均、 中央値、 範囲
2. クラスタ間 t 検定：主要指標で有意差があるか
3. 解釈可能なラベル付与：「大都市圏」「地方経済型」など
4. ドメイン専門家にレビュー依頼：常識と矛盾しないか
5. 安定性検証：データを変えても同じ結果が出るか

🧬 SSDSE 47 県でクラスタリングの妥当性を検証する

スペクトラル法で得た 4 クラスタが本当に妥当かを、 3 つの観点から検証する手順を示します。

① クラスタ別の指標プロファイル

各クラスタの主要指標の平均値・中央値を比較し、 解釈可能なラベルが付けられるか確認：

② クラスタ間の統計的有意差検定

主要指標について、 各クラスタペア間で t 検定（または非パラメトリックな Mann-Whitney U 検定）を実施：

from scipy.stats import ttest_ind
import itertools

key_metrics = ['人口', '平均所得', '高齢化率', '大学進学率']
for metric in key_metrics:
    print(f'\\n=== {metric} ===')
    for c1, c2 in itertools.combinations(range(4), 2):
        x1 = features.loc[result[result.cluster == c1].都道府県, metric]
        x2 = features.loc[result[result.cluster == c2].都道府県, metric]
        t, p = ttest_ind(x1, x2)
        sig = '***' if p < 0.001 else '**' if p < 0.01 else '*' if p < 0.05 else ''
        print(f'  クラスタ {c1} vs {c2}: t={t:.2f}, p={p:.4f} {sig}')
  

③ ブートストラップによる安定性検証

データを 100 回リサンプリングし、 毎回スペクトラルクラスタリングを実施。 得られた割当の Jaccard 類似度が高ければクラスタが安定：

from sklearn.utils import resample
from sklearn.metrics import adjusted_rand_score

n_boot = 100
aris = []
for seed in range(n_boot):
    idx = resample(np.arange(len(X)), random_state=seed)
    X_boot = X[idx]
    sc_boot = SpectralClustering(n_clusters=4, affinity='nearest_neighbors',
                                  n_neighbors=10, random_state=0)
    labels_boot = sc_boot.fit_predict(X_boot)
    # 元データの該当点と一致度を計算
    aris.append(adjusted_rand_score(labels_sc[idx], labels_boot))

print(f'平均 ARI（bootstrap）: {np.mean(aris):.3f}')
print(f'95% CI: [{np.quantile(aris, 0.025):.3f}, {np.quantile(aris, 0.975):.3f}]')
# ARI > 0.7 ならクラスタは安定
  

④ Gap 統計量でクラスタ数を再検証

Tibshirani ら（2001）の Gap 統計量で、 「ランダムデータと比較した実データのクラスタ構造の強さ」を測定：

結果の解釈と注意点

• クラスタが意味的に解釈できるか（地方区分、 経済特性など）
• 主要指標で統計的有意差があるか（最低でも p < 0.05）
• bootstrap で安定か（ARI > 0.7 が目安）
• Gap 統計量が最大になる k と一致するか

これら全てが満たされて初めて「妥当なクラスタリング」と言えます。 1 つでも怪しい場合、 パラメータ再調整やデータ前処理を見直す。

📚 関連グループ教材

スペクトラルクラスタリングは 「クラスタリング」「線形代数」「グラフ理論」 の交差点にあります。

このサイト内で関連する論文再現

• クラスタリング系論文 — 都道府県のグループ化に k-means や階層クラスタリングを使う論文が多数。 スペクトラル手法に置き換えてみる演習が有効
• 地域分類系 — 経済構造・人口構造による地域類型化
• ネットワーク分析系 — 都市間人流、 取引関係などのグラフ分析

推奨書籍

• 『パターン認識と機械学習』下巻（C. M. Bishop、 丸善）— スペクトラル手法とカーネル法の関係
• 『データ解析のための統計モデリング入門』（久保拓弥、 岩波書店）— クラスタリング基礎
• 『Spectral Clustering: Analysis and an Algorithm』（Ng, Jordan, Weiss, NeurIPS 2001）— 現代的定式化の原論文
• 『A Tutorial on Spectral Clustering』（Ulrike von Luxburg, Statistics and Computing 2007）— チュートリアル決定版（PDF 無料）
• 『Normalized Cuts and Image Segmentation』（Shi & Malik, IEEE PAMI 2000）— 画像分野での原論文

オンライン資源

• sklearn.cluster.SpectralClustering（scikit-learn.org）— 標準実装
• scipy.sparse.linalg.eigsh — 疎行列の固有値分解
• networkx（networkx.org）— グラフ操作・可視化
• graph-tool（graph-tool.skewed.de）— 高速グラフ分析（C++ バックエンド）

🧠 スペクトラル法の核心 — グラフラプラシアンの正体

スペクトラルクラスタリングは 「データを連結グラフと見立て、 そのラプラシアン行列の固有ベクトルで埋め込み、 k-means で分割する」 三段階手法です。 k-means が「球状クラスタ」しか見つけられないのに対し、 スペクトラル法は 「半月形・螺旋・任意形状」 のクラスタも発見できます。

$$L = D - W, \quad L_{\text{sym}} = I - D^{-1/2} W D^{-1/2}, \quad L_{\text{rw}} = I - D^{-1} W$$

ここで $W$ は類似度行列、 $D$ は次数対角行列。 ラプラシアン $L$ の最小 $k$ 個の固有ベクトル $u_1, \ldots, u_k$ を取り出し、 行を新たな特徴ベクトルとして k-means を回します。 「グラフ上の連結性」が「ユークリッド空間での近さ」に変換される魔法です。

📐 三種のラプラシアン — どれを使うか

Shi & Malik (2000) の normalized cut は $L_{\text{rw}}$、 Ng-Jordan-Weiss (2001) は $L_{\text{sym}}$ を使います。 von Luxburg (2007) のレビューで両者の関係が整理されました。 SSDSE-B-2026 の都道府県類似度行列のように次数が場所により異なる場合、 正規化版が安定します。

🐍 SSDSE-B 完全実装ワークフロー

SSDSE-B-2026 の 47 都道府県を「産業構造の類似性」でクラスタリングする完全手順：

import pandas as pd
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import SpectralClustering
from sklearn.metrics import silhouette_score

df = pd.read_csv('data/raw/SSDSE-B-2026.csv', encoding='cp932', skiprows=1)
X = df.iloc[:, 3:11].values
X = StandardScaler().fit_transform(X)

# RBF カーネルで類似度
sc = SpectralClustering(n_clusters=4, affinity='rbf',
                        gamma=0.5, random_state=0)
labels = sc.fit_predict(X)

print(f'シルエット係数: {silhouette_score(X, labels):.3f}')
for k in range(4):
    pref = df.iloc[labels==k, 1].tolist()
    print(f'クラスタ {k}: {pref}')

典型結果：クラスタ 1=「大都市圏（東京・大阪）」、 クラスタ 2=「地方中核（愛知・福岡）」、 クラスタ 3=「製造業集積（静岡・群馬）」、 クラスタ 4=「農業県（青森・秋田）」。

🎓 グラフカット理論との関係

スペクトラル法は グラフ理論の normalized cut 問題の連続緩和です。 グラフ $G = (V, E, W)$ を $k$ 個の部分集合 $A_1, \ldots, A_k$ に分けるとき、 normalized cut は

$$\text{Ncut}(A_1, \ldots, A_k) = \sum_{i=1}^{k} \frac{\text{cut}(A_i, \bar{A_i})}{\text{vol}(A_i)}$$

この組合せ最適化は NP 困難。 指示ベクトルを実数に緩和すると、 $L_{\text{sym}}$ の固有ベクトル問題と等価になる――これがスペクトラル法の数学的根拠です (Shi & Malik, 2000)。

連続緩和は厳密解ではないが、 実用的には k-means で離散化することで十分良い分割が得られる。 完全 NP 困難問題が固有値計算という多項式時間問題に化けるのが、 スペクトラル法の本質的価値です。

🔧 類似度行列の構成法

類似度行列 $W$ の構成法はクラスタリング結果を大きく左右します。

SSDSE-B のような中規模データには $k$-NN ($k = \sqrt{n} \approx 7$) が定番。 大規模では疎な kNN グラフが計算効率の決め手です。

🎯 クラスタ数 k の決定

クラスタ数 $k$ の選び方：

• 固有値ギャップ法：ラプラシアンの固有値 $\lambda_1 \le \lambda_2 \le \cdots$ の大きなジャンプを探す。
• シルエット係数：複数 $k$ で計算し最大を選ぶ。
• Calinski-Harabasz 指数：クラスタ間/内分散比。
• Davies-Bouldin 指数：小さいほど良い。
• Gap statistic：参照データとの比較。
• ドメイン知識：「都道府県は地理的に 4-8 ブロック」など。

from scipy.linalg import eigh
from sklearn.metrics.pairwise import rbf_kernel

W = rbf_kernel(X, gamma=0.5)
D = np.diag(W.sum(axis=1))
L = D - W

eigvals = eigh(L, eigvals_only=True)
plt.plot(eigvals[:10], "o-")
plt.title("最小 10 個の固有値（ギャップを探す）")

⚠️ スペクトラル法の落とし穴（追加 8 個）

• 計算量 $O(n^3)$：固有値分解が高コスト。 Nystrom 近似や Lanczos 法で $O(nk^2)$ に。
• 類似度行列が密：$n = 10^4$ で 100MB 超。 疎化 (kNN) で対応。
• $\gamma$ 選択の感度：RBF カーネルの $\gamma$ で結果が劇的に変化。
• 初期化依存：k-means 部分は初期値依存。 n_init を増やす。
• 外れ値の影響：1 個の外れ点が独立クラスタになりがち。
• 解釈の困難：「なぜこのクラスタリング？」を説明するのが難しい。
• 動的データへの非対応：オンラインで類似度行列を更新するのは困難。
• 欠損値：類似度行列の段階で欠損があると致命的。

🔗 関連用語（拡張）

• k-means：スペクトラル法の最終段階で使用。
• 階層的クラスタリング：別系統の手法、 結果と比較。
• クラスタリング：上位概念。
• PCA：スペクトラル法と同じく固有値分解ベース。
• カーネル PCA：非線形版 PCA、 哲学が近い。
• 固有値：手法の核となる線形代数。
• 多様体学習：Laplacian Eigenmaps と関連。
• 次元削減：スペクトラル埋め込みも次元削減の一種。

❓ よくある質問（FAQ）

🏛 Spectral Clustering の歴史

• 1973：Fiedler: A property of eigenvectors of nonnegative symmetric matrices で algebraic connectivity を導入。
• 1989：Hagen & Kahng: New spectral methods for ratio cut partitioning でグラフ分割への応用。
• 1992：Pothen et al.: 並列計算機の負荷分散にスペクトラル法を応用。
• 2000：Shi & Malik: Normalized cuts and image segmentation でコンピュータビジョンに導入。
• 2001：Ng, Jordan, Weiss: On Spectral Clustering: Analysis and an algorithm で機械学習に普及。
• 2004：Zelnik-Manor & Perona: Self-tuning Spectral Clustering で適応的に。
• 2007：von Luxburg: A tutorial on spectral clustering、 統一的視点。
• 2010 年代以降: 深層学習でグラフニューラルネットへ発展、 GCN は Spectral 法の連続版。

💼 産業応用事例

🔬 ラプラシアンの数学的性質

• 半正定値性：$L = D - W$ は対称半正定値、 固有値はすべて非負実数。
• 連結性と固有値 0：固有値 0 の重複度＝連結成分数。
• Cheeger 不等式：$\lambda_2 / 2 \le \phi(G) \le \sqrt{2 \lambda_2}$、 ここで $\phi(G)$ は条件付きカット。
• random walk との関係：$L_{\text{rw}} = I - D^{-1} W$ はランダムウォークの遷移行列に直結。
• 離散ラプラス方程式：$Lf = 0$ はグラフ上の調和関数を定める。

埋め込み空間の意味

スペクトラル埋め込み $\phi(x_i) = (u_2(i), u_3(i), \ldots, u_k(i))^\top$ は、 「グラフ上の拡散距離 (diffusion distance) を反映するユークリッド埋め込み」になっています (Coifman & Lafon, 2006)。 つまり「同じクラスタ＝拡散時間が短い」が「ユークリッド近さ」に翻訳される。 これが k-means が効く理由です。

収束性

von Luxburg, Belkin, Bousquet (2008) は「サンプルサイズ $n \to \infty$ で、 サンプルラプラシアンが極限作用素 (Laplace-Beltrami operator) に収束」を示しました。 つまり Spectral Clustering は「データ多様体上のラプラシアンを離散近似している」――幾何学的データ解析の基盤です。