譜聚類

在多元變量統計中，譜聚類（英語：spectral clustering）技術利用數據相似矩陣的譜（特徵值），在對數據進行降維後，以較少的維度進行聚類。相似矩陣作為輸入，提供了對數據集中每一對點相對相似性的定量評估。

在圖像分割中，譜聚類被稱為基於分割的物體分類。

算法

基本算法

1. 計算拉普拉斯矩陣 ${\displaystyle L}$ （或歸一化的拉普拉斯矩陣）
2. 計算前 ${\displaystyle k}$ 個特徵向量（這些特徵向量對應 ${\displaystyle L}$ 的 ${\displaystyle k}$ 個最小的特徵值）
3. 考慮由這 ${\displaystyle k}$ 個特徵向量組成的矩陣，矩陣的第 ${\displaystyle l}$ 行定義了圖節點 ${\displaystyle l}$ 的特徵
4. 根據這些特徵對圖節點進行聚類（例如使用k-均值聚類）

大型圖的（歸一化）拉普拉斯矩陣通常是病態的（ill-conditioned，即高條件數），這會減緩迭代求解的收斂速度。預處理（英語：Preconditioner#Preconditioning_for_eigenvalue_problems）（Preconditioning）可以加速收斂。通過首先確定結構，然後對群落進行聚類，譜聚類可以成功應用於大型圖。^[1]

譜聚類與非線性降維密切相關，局部線性嵌入（Locally-linear embedding）等降維技術可用於減少噪聲或異常值的誤差。^[2]

軟體

有不少大型開源項目實現譜聚類，包括Scikit-learn^[3]（使用帶有多網格預處理（multigrid method）或ARPACK的LOBPCG算法），MLlib（使用冪迭代法，Power iteration method）進行偽特徵向量聚類^[4]，以及R^[5]。

和其它聚類算法的關係

譜聚類算法它可以在核聚類方法的背景下進行描述，這顯示了它與其他方法的相似之處。^[6]

和k-means聚類算法的關係

加權核K-means問題與譜聚類問題的目標函數相同，可以通過多級方法直接優化。