跳至內容

譜聚類

維基百科,自由的百科全書

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

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

算法

[編輯]
基本算法
  1. 計算拉普拉斯矩陣 (或歸一化的拉普拉斯矩陣)
  2. 計算前 個特徵向量(這些特徵向量對應 個最小的特徵值)
  3. 考慮由這 個特徵向量組成的矩陣,矩陣的第 行定義了圖節點 的特徵
  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問題與譜聚類問題的目標函數相同,可以通過多級方法直接優化。

參考資料

[編輯]
  1. ^ Zare, Habil; P. Shooshtari; A. Gupta; R. Brinkman. Data reduction for spectral clustering to analyze high throughput flow cytometry data. BMC Bioinformatics. 2010, 11: 403. PMC 2923634可免費查閱. PMID 20667133. doi:10.1186/1471-2105-11-403. 
  2. ^ Arias-Castro, E. and Chen, G. and Lerman, G., Spectral clustering based on local linear approximations., Electronic Journal of Statistics, 2011, 5: 1537–1587, S2CID 88518155, arXiv:1001.1323可免費查閱, doi:10.1214/11-ejs651 
  3. ^ 2.3. Clustering. [2022-08-07]. (原始內容存檔於2015-05-15). 
  4. ^ Clustering - RDD-based API - Spark 3.2.0 Documentation. [2022-08-07]. (原始內容存檔於2017-07-03). 
  5. ^ Kernlab: Kernel-Based Machine Learning Lab. 12 November 2019 [2022-08-07]. (原始內容存檔於2017-06-27). 
  6. ^ Filippone M., Camastra F., Masulli, F., Rovetta, S. A survey of kernel and spectral methods for clustering (PDF). Pattern Recognition. January 2008, 41 (1): 176–190 [2022-08-07]. Bibcode:2008PatRe..41..176F. doi:10.1016/j.patcog.2007.05.018. (原始內容存檔 (PDF)於2022-08-16).