淺談Spectral Clustering

Spectral Clustering，中文通常稱為“譜聚類”。由于使用的矩陣的細微差别，譜聚類實際上可以說是一“類”算法。

Spectral Clustering 和傳統的聚類方法（例如 K-means）比起來有不少優點：

1）和 K-medoids 類似，Spectral Clustering 隻需要資料之間的相似度矩陣就可以了，而不必像 K-means 那樣要求資料必須是 N 維歐氏空間中的向量。

2）由于抓住了主要沖突，忽略了次要的東西，是以比傳統的聚類算法更加健壯一些，對于不規則的誤差資料不是那麼敏感，而且 performance 也要好一些。許多實驗都證明了這一點。事實上，在各種現代聚類算法的比較中，K-means 通常都是作為 baseline 而存在的。 

3）計算複雜度比 K-means 要小，特别是在像文本資料或者平凡的圖像資料這樣次元非常高的資料上運作的時候。

Spectral Clustering 算法的全貌：

1）根據資料構造一個 Graph ，Graph 的每一個節點對應一個資料點，将相似的點連接配接起來，并且邊的權重用于表示資料之間的相似度。把這個 Graph 用鄰接矩陣的形式表示出來，記為 W 。

2)把 的每一列元素加起來得到N 個數，把它們放在對角線上（其他地方都是零），組成一個N*N的矩陣，記為D 。并令L = D - W 。

3)求出L的前k個特征值（在本文中，除非特殊說明，否則“前k個”指按照特征值的大小從小到大的順序）以及對應的特征向量。

4)把這k個特征（列）向量排列在一起組成一個N*k的矩陣，将其中每一行看作k維空間中的一個向量，并使用 K-means 算法進行聚類。聚類的結果中每一行所屬的類别就是原來 Graph 中的節點亦即最初的N個資料點分别所屬的類别。

下面是Spectral Clustering 的一個簡單的 Matlab 實作：

複制代碼

function idx = spectral_clustering(W, k)

    D = diag(sum(W));

    L = D-W;

    opt = struct('issym', true, 'isreal', true);

    [V dummy] = eigs(L, D, k, 'SM', opt);

    idx = kmeans(V, k);

end

      最後，我們再來看一下本文一開始說的 Spectral Clustering 的幾個優點：

1）隻需要資料的相似度矩陣就可以了。這個是顯然的，因為 Spectral Clustering 所需要的所有資訊都包含在W中。不過一般W并不總是等于最初的相似度矩陣——回憶一下， 是我們構造出來的 Graph 的鄰接矩陣表示，通常我們在構造 Graph 的時候為了友善進行聚類，更加強到“局部”的連通性，亦即主要考慮把相似的點連接配接在一起，比如，我們設定一個門檻值，如果兩個點的相似度小于這個門檻值，就把他們看作是不連接配接的。另一種構造 Graph 的方法是将 n 個與節點最相似的點與其連接配接起來。

2)抓住了主要沖突，忽略了次要的東西，Performance 比傳統的 K-means 要好。實際上 Spectral Clustering 是在用特征向量的元素來表示原來的資料，并在這種“更好的表示形式”上進行 K-means 。

3)計算複雜度比 K-means 要小。這個在高維資料上表現尤為明顯。例如文本資料，通常排列起來是次元非常高（比如，幾千或者幾萬）的稀疏矩陣，對稀疏矩陣求特征值和特征向量有很高效的辦法，得到的結果是一些 k 維的向量（通常 k 不會很大），在這些低維的資料上做 K-means 運算量非常小。但是對于原始資料直接做 K-means 的話，雖然最初的資料是稀疏矩陣，但是 K-means 中有一個求 Centroid 的運算，就是求一個平均值：許多稀疏的向量的平均值求出來并不一定還是稀疏向量，事實上，在文本資料裡，很多情況下求出來的 Centroid 向量是非常稠密，這時再計算向量之間的距離的時候，運算量就變得非常大，直接導緻普通的 K-means 巨慢無比，而 Spectral Clustering 等工序更多的算法則迅速得多的結果。

本文轉自Phinecos(洞庭散人)部落格園部落格，原文連結：http://www.cnblogs.com/phinecos/archive/2009/05/11/1453853.html，如需轉載請自行聯系原作者