# スペクトラルクラスタリング ## 定義 スペクトラルクラスタリング(spectral clustering)は、観測間の非負な類似度 $s_{ii'}$ から構成した無向類似度グラフ $G=\langle V,E\rangle$ をグラフ分割問題として捉え、グラフラプラシアンの下位固有ベクトルを特徴量として通常のクラスタリング(K-meansなど)を適用する手法である。類似度グラフは、放射カーネル $s_{ii'}=\exp(-d_{ii'}^2/c)$(スケールパラメータ $c$)による完全結合グラフか、あるいは対称最近傍集合 $N_K$(点 $i$ が $i'$ の $K$近傍、またはその逆)による疎グラフとして構成される。エッジ重み行列(隣接行列)$W=\{w_{ii'}\}$、次数 $g_i=\sum_{i'} w_{ii'}$ を対角に持つ次数行列 $G$ から、**グラフラプラシアン** $L=G-W$(非正規化版。正規化版は $\tilde L=I-G^{-1}W$)を定義する。任意ベクトル $f$ に対し $f^TLf=\frac{1}{2}\sum_{i,i'}w_{ii'}(f_i-f_{i'})^2$ が成り立つため、$L$ の最小固有値(自明な定数固有ベクトルを除く)に対応する固有ベクトルは、類似度の高い点同士が近い座標を持つような低次元埋め込みを与える。$m$ 個の連結成分を持つグラフでは、固有値0の固有空間が各連結成分の指示ベクトルで張られる(演習14.21)。正規化ラプラシアンを用いる場合、$P=G^{-1}W$ をランダムウォークの遷移確率行列とみなし、「群をまたいで遷移しにくい」ノード集合を見つける解釈もできる。標準的なK-meansが球状・楕円状の距離尺度しか扱えず同心円のような非凸なクラスタ形状を分離できないのに対し、スペクトラルクラスタリングはこの限界を克服するために設計された。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.5.3) ## 横断的知見 - 1 ソース目のため、他のソースとの突き合わせによる知見は今後の蓄積に委ねる。 ## 未解決の問い - 類似度グラフの種類(完全結合 vs. 最近傍)とスケールパラメータ $c$・近傍数 $K$ の選択は結果を大きく左右するが、体系的な選択指針は本章に示されていない。玩具例では $k\in[5,200]$ で良好、$k<5$ で劣化したという経験則のみが報告される(§14.5.3)。 - 固有ベクトルの選択数(何個の下位固有ベクトルを使うか)についても、玩具例で最小固有値と他の固有値の間に明確な分離が見られず、決定的な指針が欠けている。 - カーネルPCA(§14.5.4)との数理的な近さ(放射カーネル行列 $K$ とスペクトラルクラスタリングの類似度行列 $S$ が同形)にもかかわらず、実験上はスペクトラルクラスタリング(最近傍による打ち切り)が有効でカーネルPCA単独では非凸クラスタを分離できなかった。この差を生む「打ち切り」の効果を理論的に特徴づける議論は本章に含まれない。 - [[グラフニューラルネットワーク]]のようなグラフ上の表現学習手法とスペクトラルクラスタリングの関係(グラフラプラシアンのスペクトル分解が両者にどう関わるか)は未整理。今後のingestで確認する。 ## 関連 - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]](§14.5.3–14.5.4) - 概念: [[クラスタリング]](K-meansの非凸性の限界を克服する拡張として位置づけ)/ [[主成分分析]](カーネルPCAとの数理的近縁性)/ [[カーネル法]](放射カーネルを用いた類似度行列の構成)/ [[グラフニューラルネットワーク]](グラフラプラシアンを介した接続の可能性) ## 出典 - [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]](§14.5.3–14.5.4、式14.63–14.68)