スペクトラルクラスタリング完全ガイド：ラプラシアンの選択と類似度構築から大規模データ対応まで
エバープレイ編集部スペクトラルクラスタリングとは — 概要
スペクトラルクラスタリング（spectral clustering）は、データ点間の類似度をグラフで表現し、そのグラフのラプラシアン行列の固有ベクトル（スペクトル情報）を利用してクラスタリングを行う手法です。距離や密度に基づく従来のクラスタリング（例：k-means）が直線的な分離や凸形状に弱いのに対し、スペクトラルクラスタリングは非線形構造や複雑な形状のクラスタ検出に強みを持ちます。画像分割やネットワーク解析、次元削減の前処理など幅広い応用があります。
基本的な考え方
まずデータ点を頂点とする類似度グラフを作り、隣接（類似度）行列 W を定義します。次に次数行列 D（対角成分が各頂点の類似度の総和）からグラフラプラシアン L を構成します。L の固有値・固有ベクトル（グラフのスペクトル）はクラスタ構造に関する情報を持っており、固有ベクトル空間にデータを写像した後、k-means 等で最終的なクラスタリングを行います。
ラプラシアンの種類と性質
非正規化ラプラシアン（unnormalized）：L = D − W。連結成分の個数は L の零固有値の重複度に一致します。小さい固有値に対応する固有ベクトルがクラスタ分割の手がかりになります。
対称正規化ラプラシアン（symmetric normalized）：L_sym = I − D−1/2 W D−1/2。数値的に安定で、異なる次数（重み合計）を持つノードを扱う際に有利です。
ランダムウォーク正規化ラプラシアン（random-walk）：L_rw = I − D−1 W。これは確率遷移行列 P = D−1 W に関係し、正規化カット（normalized cut）問題の緩和と密接に関連します。
代表的なアルゴリズムの流れ
代表的なスペクトラルクラスタリング（Ng-Jordan-Weiss 等）の一般的な手順は次の通りです：
1) 類似度行列 W を構築する（例：ガウシアンカーネル exp(−||xi−xj||^2 / (2σ^2))、k近傍グラフ、ε近傍グラフなど）。
2) 次数行列 D を計算する（Dii = Σ_j Wij）。
3) ラプラシアン行列を作る（L, L_sym, L_rw のいずれかを選択）。
4) ラプラシアン（もしくは D−1/2 W D−1/2 等）の固有ベクトルを上位 k 個（小さい固有値に対応するもの）取り出す。Ng-Jordan-Weiss では D−1/2 W D−1/2 の上位 k 個固有ベクトル（大きい固有値）を用いる実装が典型です。
5) 得られた n×k の行列（各データ点に対応する k 次元表現）を行単位で正規化する（手法による）。
6) k-means 等で最終クラスタを決定する。
グラフと類似度の構築（実務上最も重要）
スペクトラルクラスタリングの結果は類似度行列の作り方に非常に敏感です。代表的な方法：
ガウシアンカーネル（完全グラフ）：Wij = exp(−||xi−xj||^2 / (2σ^2))。σ（バンド幅）の選び方が結果を左右します。
k近傍グラフ：各点と距離上位k点を結ぶ（双方向にするか片方向にするかで変わる）。スパースで計算効率が良い。
ε近傍グラフ：距離がε以下の点をつなぐ。データ密度の差が大きい場合に注意が必要。
自己調整 (self-tuning) 手法：点ごとに局所的なσを決める手法（Zelnik-Manor & Perona）で、スケールが異なるクラスタに対処しやすくなる。
ラプラシアンとカット問題の関係
クラスタリングはグラフ分割（カット）の問題に帰着できます。最小カットはしばしば一方の小さな孤立を生むため、バランスを考慮した指標（RatioCut, NormalizedCut）が提案されました。Normalized Cut の緩和は固有値問題（L_rw の固有ベクトル問題）になり、それを計算してクラスタを得るのがスペクトラルクラスタリングの理論的根拠です。
固有値の解釈とクラスタ数の決定
ラプラシアンの固有値の分布（スペクトル）を見ることでクラスタ数 k を見積もるヒントが得られます。理想的には、k 個の小さい固有値（多くは零やゼロに近い値）があり、その後に大きなギャップ（スペクトルギャップ）が現れます。ただし実データでは明瞭なギャップがない場合も多く、経験的・問題依存の判断が必要です。
計算量と大規模データへの対処
固有分解は一般に O(n^3) の計算コストを要し、メモリも O(n^2)（W が密な場合）です。大規模データには次のような対策が必要です：
スパース類似度（k-NN グラフ等）を使うことでメモリと計算を削減。
部分的な固有値計算（Lanczos、ARPACK 等）で上位 k 個だけを求める。
Nyström 法などの近似手法によりランダムサンプリングで固有空間を近似しスケールアップ。
ミニバッチや階層的クラスタリングで前処理を行う等の工夫。
利点と欠点（実務視点）
利点：非線形形状のクラスタ検出が可能、グラフ理論に基づく明確な数理基盤、画像処理やネットワーク解析での強力な性能。
欠点：類似度の設計やパラメータ（σ, k 等）に敏感、固有分解の計算コスト、k-means に依存するため最後のラベリングが不安定になることがある。
実装上の注意とベストプラクティス
前処理で特徴量を標準化（スケーリング）する。距離ベースの類似度はスケールに敏感。
類似度行列は可能な限りスパース化する（k-NN など）と計算が実用的になる。
複数の σ や k を試し、固有値プロット（スペクトル）や可視化で結果を評価する。
最終の k-means は複数回初期化して最良解を採る。代替方法としてグラフに基づくクラスタ割当の直接法を検討する場合もある。
ノイズや外れ値に弱いため、前処理で外れ値処理やロバストな類似度設計を行う。
応用例
画像セグメンテーション（Shi & Malik の normalized cut）
コミュニティ検出やソーシャルネットワーク解析
次元削減や教師なし前処理（階層的クラスタリングの補助）
バイオインフォマティクス（遺伝子発現データのグルーピング）など）
まとめ
スペクトラルクラスタリングはグラフラプラシアンの固有構造を利用して、非線形かつ複雑なクラスタ構造を検出できる強力な手法です。その理論はグラフ分割問題に基づき、ラプラシアンの種類や類似度行列の作り方が結果を大きく左右します。計算コストとパラメータ選択が実装上の課題ですが、スパース化や近似法により大規模データにも適用可能です。実務では類似度設計・前処理・複数試行による評価が成功の鍵となります。
参考文献
- U. von Luxburg, "A Tutorial on Spectral Clustering" (2007). arXiv:0711.0189
- J. Shi and J. Malik, "Normalized Cuts and Image Segmentation" (2000).
- A. Y. Ng, M. I. Jordan, Y. Weiss, "On Spectral Clustering: Analysis and an algorithm" (2002).
- S. Zelnik-Manor and P. Perona, "Self-Tuning Spectral Clustering" (2004).
- S. Fowlkes, S. Belongie, F. Chung, J. Malik, "Spectral Grouping using the Nyström Method" (2004).
- ARPACK: Software for large scale eigenvalue problems (Lanczos等の実装)
投稿者プロフィール
