🙋
k-means でクラスタリングしようとしたら、半月形のデータが全然うまく切れなくて…。スペクトラルクラスタリングだとなぜ綺麗に分かれるんですか？
🎓
k-means は「クラスター中心からのユークリッド距離」が基準だから、必ず凸（だいたい球状）な領域しか作れないんだ。半月形だと2つの月の重心はむしろ近くて、片方の端と端の方が遠い、なんてことが起こる。スペクトラルクラスタリングは発想を変えて、サンプル間に「親和度（仲の良さ）」を定義してグラフを作る。そのグラフのラプラシアン行列の固有ベクトルで低次元空間に埋め込むと、グラフ上で繋がっている塊は同じ場所に集まる。だから半月の中を順に辿れる経路があれば、形がどんなにねじれていても1つのクラスタに認識されるんだよ。
🙋
なるほど！じゃあ親和度ってどう作るんですか？左の選択肢にも RBF・k-NN・コサインって3種類あって、どれを使えばいいか迷います。
🎓
一番ポピュラーなのが RBF（ガウシアン）親和度で、W_ij = exp(-||x_i-x_j||²/(2σ²)) だ。距離が近いほど 1 に近づき、遠いほど指数関数的にゼロに落ちる。連続的で扱いやすい一方、σ の選択がシビアで、大きすぎると全部繋がって1個になり、小さすぎると孤立点だらけになる。k-NN グラフは「各点を k 個の近傍とだけ繋ぐ」シンプルな疎行列で、σ チューニング不要・大規模データ向き。コサインはテキストや高次元の方向データで使う。画像セグメンテーションなら RBF、社会ネットワークやレコメンドなら k-NN、自然言語処理ならコサイン、と用途で使い分けるのが定石だね。
🙋
本当に固有ベクトルでクラスタが見えるんですか？数学的にイメージしにくくて…
🎓
直感的に言うと、ラプラシアンの固有値はグラフ上の「振動モード」の周波数で、固有ベクトルはその振動形状なんだ。データが K 個の完全に分離した塊なら、最小の K 個の固有値は 0 で、対応する固有ベクトルは各塊の指示関数（その塊では一定値、他はゼロ）になる。だから固有ベクトルを並べた行列の行ベクトルを見ると、同じ塊の点は同じ点に重なり、k-means で一発分離。実データはノイズで完璧分離ではないけれど、近い性質を持つから、固有ベクトル空間に埋め込むと球状のクラスタになって k-means が効くようになるんだよ。
🙋
使う固有ベクトルの数 k はクラスター数 K と同じでいいんですか？
🎓
基本的には k=K で OK。Ng-Jordan-Weiss の標準アルゴリズムは最小 K 個の固有ベクトルを使う。ただし実務では「Spectrum chart の固有値を昇順に並べて、ジャンプが最大の位置で切る」eigengap heuristic で K を客観的に決められるのが強み。例えば固有値が 0.01, 0.02, 0.03, 0.5, 0.52… と4番目で急に飛んだら K=3 が最適。本ツールの右側の固有値スペクトラムを見ると、デフォルトの半月形では K=2〜3 でギャップが見えるはずだよ。
🙋
最後に、サンプル数 N=200 ならメモリ 0.3MB と表示されてますが、実務だと N が万単位ですよね？スケールしないんですか？
🎓
そこが古典的な弱点で、親和度行列 N×N と固有値分解 O(N³) があるから、素朴な実装は N=10000 で行列だけ 800MB、計算は数十分かかる。回避策は3つ：(1) k-NN グラフで W を疎行列化し、ARPACK や Lanczos 法で部分固有値だけ解く、(2) Nyström 近似で N×N を m 個のランドマーク列に圧縮（m≪N）、(3) ランダム射影で次元削減してから親和度を作る。scikit-learn の SpectralClustering は (1) を既定で実装していて、N=10万まで実用域。それを超えるとミニバッチ k-means や Power Iteration Clustering の方が現実的だね。
スペクトラルクラスタリングは k-means や階層クラスタリングと何が違いますか？
k-means や階層クラスタリングは「クラスター内のサンプル間距離が小さい」ことを前提にしており、データ空間で凸（だいたい球状）な塊しかうまく分離できません。半月形・同心円・スパイラル状のデータでは、距離が近いのに別クラスタ、離れているのに同クラスタ、という直感どおりに切れません。スペクトラルクラスタリングはサンプル間の「親和度行列 W」をグラフとみなし、正規化グラフラプラシアン L=D^-1/2(D-W)D^-1/2 の最小 k 固有値・固有ベクトルから低次元空間を作って k-means します。グラフ上で「つながっている塊」を切るため、非凸形状でも完璧に分離できます。
RBFのスケール σ はどう決めればよいですか？
RBF 親和度 W_ij = exp(-||x_i-x_j||²/(2σ²)) では σ がクラスタリング品質を決定します。σ が大きすぎると遠くの点まで強く結合し、すべてが1つの塊に潰れます。小さすぎると近傍以外がほぼゼロになり、孤立点が増えて k-means が失敗します。実務では「近傍点間距離の中央値」や「k-NN グラフでの k 番目近傍距離の平均」を初期値にし、固有値ギャップ（k 番目と k+1 番目の差）が最大になる σ を探します。本ツールでは σ≈0.3 で半月形データに対し品質スコア 0.95 を達成します。
計算量 O(N³) を大規模データで回避する方法は？
親和度行列が N×N で、その固有値分解は素朴には O(N³)、メモリは O(N²) です。N=10000 で約 800MB、N=100000 で 80GB と現実的でなくなります。回避策は3つ：(1) k-最近傍グラフで W を疎行列にし、Lanczos 法など反復固有値法を使う（O(N·k·iter)）、(2) Nyström 近似で N×N 行列を m 個のサンプル列で近似（m≪N）、(3) ランダム射影でデータ次元を圧縮してから親和度を作る。scikit-learn の SpectralClustering は ARPACK 反復ソルバを既定で使い、k-NN グラフと組み合わせて N=10万程度まで実用化されています。
クラスター数 K はどうやって決めますか？
スペクトラルクラスタリングには固有の「最適 K 判定法」があります — 固有値ギャップ（eigengap heuristic）です。ラプラシアンの固有値を昇順に並べ、λ_K と λ_{K+1} の差が最も大きくなる K を選びます。理論的には、データが K 個の完全に分離した連結成分から成るとき、L は K 個の固有値 0 を持ち、λ_{K+1}>0 となるため明確なギャップが現れます。実データはノイズで連結成分が「ほぼ分離」になり、ギャップは緩やかですが、肘（elbow）のように明確な飛びが見える K を選びます。クラスター数指定が難しい階層クラスタリングと違い、固有値スペクトルから客観的に決まる点が大きな利点です。
画像セグメンテーション（Shi-Malik 2000）： スペクトラルクラスタリングが大ブレイクした最初の応用領域です。画像のピクセルをノードにし、色やテクスチャの類似度＋空間距離で親和度を定義すると、Normalized Cut が物体と背景を綺麗に切ります。Berkeley Segmentation Dataset では今もベンチマークの基準。最近は深層特徴量と組み合わせた「Spectral Cluster on CNN features」が医療画像の臓器分割や衛星画像の土地利用分類で使われます。
社会ネットワークのコミュニティ検出： SNS のフォロー関係、共著ネットワーク、メール送受信ネットワークでは「コミュニティ＝密に繋がった部分グラフ」を見つけたい。隣接行列をそのまま W として正規化ラプラシアンの固有ベクトルを計算すると、Twitter のフォロワー圏や Wikipedia の話題クラスタが自然に分離されます。Modularity 最大化とは異なる視点を提供するため、両方を併用するのが一般的。
遺伝子発現データ・単細胞 RNA-seq 解析： 細胞をノード、遺伝子発現プロファイル間のコサイン類似度を W にすると、組織内の細胞種が固有ベクトル空間で別クラスタに分かれます。Seurat や Scanpy などの主要パッケージで標準採用されており、UMAP と組み合わせて細胞アトラスの作成に必須。t-SNE/UMAP は可視化用、クラスタリングはスペクトラル系（実装は k-NN グラフ + Louvain だが、思想は同じ）という分担が定着しています。
CAE 分野でのメッシュ分割・部分構造法： 有限要素メッシュを領域分割して並列計算するとき、要素隣接グラフのスペクトラルバイセクションが古典的手法。Fiedler ベクトル（2番目に小さい固有ベクトル）の符号で2分割し、再帰的に細分する。MeTiS や Scotch などのライブラリで実装され、ANSYS / OpenFOAM の並列ソルバの内部で動いています。クラスタリングと数値計算の橋渡しとなる興味深い応用例。
まず最大の落とし穴が、「RBFスケール σ を一度決めたら固定で良い」 と思い込むこと。実際は σ がクラスタリング結果を支配しており、データのスケールが変わるたびに最適 σ も変わります。例えば 0〜1 に正規化したデータで σ=0.3 が最適でも、生の値（0〜100）に戻すと σ=30 にしないと同じ振る舞いになりません。前処理（標準化・正規化）の段階で σ の絶対値の意味が変わる点に注意してください。実務では「近傍点距離の中央値」を σ の初期値にする、または k-NN グラフで σ チューニング自体を回避するのが安全策です。
次に、「固有値分解を毎回フル計算してしまう」 こと。SpectralClustering の eigen_solver='arpack'（既定）は最小 K 個の固有値だけを反復解法で求めるため、N が大きくても O(N·K) 程度で済みます。一方 eigen_solver='dense' は LAPACK で N 個全てを解くため O(N³)。N=10000 で前者は数秒、後者は数十分の差になります。新しめのライブラリでも、デフォルトを dense にしてしまうコード例があるので、必ず公式ドキュメントで確認してください。また k-NN グラフを使う場合は scipy.sparse の疎行列で W を渡し、行列が dense にコピーされないよう注意します。
最後に、「クラスタリング結果の安定性を確認しない」 こと。スペクトラルクラスタリングの最終段の k-means は初期値依存があり、n_init=10 程度で複数回試して最良を取るのが必須です。さらに ARPACK の収束も乱数初期値に依存するため、ランダムシードを変えると微妙に結果が変わります。論文や実務報告では、複数シードでの結果の Adjusted Rand Index（ARI）を測り、0.95 以上の安定性があることを示すのが標準です。シード依存性を無視すると「特定のシードでしか出ない綺麗な結果」を最終成果と誤解する危険があります。