通過譜聚類方法聚類時得出拉普拉斯矩陣之後如何繼續處理數據？

01-26

剛接觸機器學習想問下拉普拉斯矩陣得出之後是不是就直接用kmeans聚類？需要提取拉普拉斯矩陣的前k個特徵再kmeans嗎？另外在計算W矩陣時內部元素可以取距離或者高斯的形式這樣取法有什麼不一樣嗎？還有對拉普拉斯矩陣的normalize很重要嗎？如果不normalize有什麼影響呢？我寫了一段matlab的程序在針對多類別數據處理時效果很理想但是兩類的數據處理卻不穩定會是什麼造成的呢？

謝邀。

spectral clustering（譜聚類）的常見問題的答案在這篇綜述裡面都有：

A Tutorial on Spectral Clustering，包括演算法流程、不同的normalize等等

http://www.cs.cmu.edu/~aarti/Class/10701/readings/Luxburg06_TR.pdf

至於題目中提到的『兩類的數據處理卻不穩定』的情況，可能是由kmeans的不穩定造成的，多次計算取最好的情況即可。

首先，強調一下譜聚類是複雜網路和社群演算法或者說圖論裡面非常基礎也非常重要的一個演算法，在識別惡意團伙的效果上也是非常好的，計算的效率也是比GN或者infomap要強很多的，建議看看數學推導過程，想到用度矩陣-鄰接矩陣是亮點，最後拉普拉斯矩陣中的指示向量構造也非常非常有意思：

下面回答能回答的問題：

問題1:剛接觸機器學習想問下拉普拉斯矩陣得出之後是不是就直接用kmeans聚類？需要提取拉普拉斯矩陣的前k個特徵再kmeans嗎？

答：不是直接用拉普拉斯矩陣直接聚類，需要提取拉普拉斯矩陣的按照特徵值從小到大排列下的前k個對應的特徵向量進行kmeans。至於為什麼，我個人理解是，譜聚類最後的優化目標：argmin tr(H.T·L·H) s.t. H.T·H = I，H.T·L·H中H指示向量要麼是0要麼是指示向量h，而且H.T·L·H中，h其實就是L的特徵向量，所以解就自然出來了，特徵值最小的若干特徵值對應的特徵向量就是優化目標的解。

問題2:另外在計算W矩陣時內部元素可以取距離或者高斯的形式這樣取法有什麼不一樣嗎？

答：姑且認為這邊的W矩陣為鄰接矩陣，取距離和取高斯形式下的距離都是為了衡量不同feature下的不同樣本點的相似程度。高斯形式下數據計算的更快而且一定程度上有去量綱化效果實測衡量的效果更好。這邊的核心在於如何定義相似度，如果你的feature都是性別、學歷這些，餘弦相似度都是非常好的定義方式。

問題3:還有對拉普拉斯矩陣的normalize很重要嗎？如果不normalize有什麼影響呢？

答：重要。對於不同子集，樣本點之間的相似度大小可能會差異很大（這邊一來依賴你的樣本點分布二來依賴你問題2設計的相似度度量方式）；做normalize，可以保持量綱一致，對演算法迭代速度和準確度都是必不可少的。

最後，譜聚類不穩定的原因其實很多，不同初始similarity定義最後的結果效果不一致，不同的特徵值個數k，最後的效果差異很大，最後採取kmeans聚類還是採取局部密度或者PAM差異也很大，我用了37個數據集循環測試，目前沒有看到有什麼規律，攤手:(，歡迎知道的朋友指教一下，謝謝。

額，搜索自己專業的時候，碰到這個問題，我也是研究譜聚類的，你說的這個問題，我之前考慮了一下，

第一個，那個是需要取前k個，因為已經拉普拉斯變換了，這個過程需要去按照聚類要求，取出來K個分量

第二個，這個問題的實質跟為什麼高斯變比直接距離效果好，我主要研究的就是這個，其實高斯變換，拉長了距離，數據點之間的距離越大，拉長的距離越大，便於最後分解

第三個問題，我沒有想明白，因為我之前用人工數據集做了實驗，標準化和沒有標準化的結果一樣。。。。

一年前的問題，希望能夠討論

對了，想起來個事兒，譜聚類是不是機器學習的領域有待商榷，因為我看到有人說，聚類和分類，之間還是有區別的

拉普拉斯矩陣，求解這個矩陣有什麼好方法？1000X1000需要幾秒？