譜聚類(Spectral Clustering, SC)是一種基于圖論的聚類方法。

將帶權(quán)無向圖劃分為兩個或兩個以上的最優(yōu)子圖，使子圖內(nèi)部盡量相似，而子圖間距離盡量距離較遠，以達到常見的聚類的目的。

"帶權(quán)無向圖"這個詞太學術(shù)了，我們換一種叫法，即：相似度矩陣。

假設(shè)我們有一個相似度矩陣，矩陣中存的是所有對象的兩兩相似度。

?

那么這個矩陣應該有如下性質(zhì)：

矩陣為N * N，N為對象總數(shù)

矩陣對角線的值為0，自己和自己相似個毛啊

矩陣為對稱矩陣，及相似度是無向的

我們將該矩陣記為：W。

?

譜聚類的任務就是根據(jù)這個相似度矩陣，將這一大堆對象，分成不同的小堆，小堆內(nèi)部的對象彼此都很像，小堆之間則不像。

?

譜聚類本身也提供了好幾種不同的分割(cut)方法，每種方法對應一種優(yōu)化目標。

本文只介紹其中比較常見，也是比較實用，而且實現(xiàn)起來也比較經(jīng)濟的一種：Nomarlized cut.

?

說白了，就是你最應該掌握和使用的一種，好了，進入正題。

?

當你得到一個相似度矩陣W后，即可通過以下幾個步驟，來得到對應的圖分割方案：

1. 計算對角矩陣D[N*N]。，公式如下：

?D矩陣為對角矩陣，對角線上的值為W矩陣中對應行或列的和。

?

2. 計算拉普拉斯矩陣(Laplacian) L：

3. ?歸一化L矩陣

4. 計算歸一化后L矩陣的K個最小特征值及對應的特征向量

? ? 將K個特征向量豎著并排放在一起，形成一個N*K的特征矩陣，記為Q。

?

5. 對特征矩陣Q做kmeans聚類，得到一個N維向量C。

? ? 分別對應相似度矩陣W中每一行所代表的對象的所屬類別，這也就是最終的聚類結(jié)果。

?

此外：

關(guān)于第3步中，對拉普拉斯矩陣歸一化時，歸一化公式進行變換得到：

??? 令：

?

則在第4步中，我們可以將求L的K個最小特征值及其對應的特征向量的問題，轉(zhuǎn)化為求矩陣E的K個最大的特征值及其對應的特征向量。

? ? ? ? ---可以證明：L的K個最小特征值對應的特征向量，分別對應于E的K個最大的特征值對應的特征向量。

? ? ? ? ? ? 且矩陣L的最小特征值為0，對應于矩陣E最大的特征值為1.矩陣L的第K小特征值等于1-矩陣E的第K大特征值

?

之所以要這么做，是因為在數(shù)值計算中，求矩陣的最大特征值，往往要比求最小特征值更方便和高效。

?

OK，至此，譜聚類就完成了，關(guān)于譜聚類的其他問題，諸如公式的推導，以及譜聚類的物理意義等，可參考博文：譜聚類算法。

譜聚類的實現(xiàn)很簡單，按照上述5個步驟按部就班即可，在matlab中只需寥寥數(shù)行：

?

function C = SpectralClustering(W, k)[n,m] = size(W) s = sum(W);D = full(sparse(1:n, 1:n, s));E = D^(-1/2)*W*D^(-1/2);[Q, V] = eigs(L, k);C = kmeans(Q, k); end

譜聚類的完整C代碼實現(xiàn)，可參考：https://code.csdn.net/u011531384/ml/tree/master/psc.c

?

總結(jié)

以上是生活随笔為你收集整理的谱聚类算法原理及实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。