比起傳統的K-means算法，譜聚類對數據分布的適應性更強，計算量也要小很多。

1. 譜聚類概述

譜聚類是從圖論中演化出來，主要思想是吧所有的數據看作空間中的點，這些點之間可以用邊連接起來。距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的權重值較高，通過對所有數據點組成的圖進行切圖，讓切圖后不同子圖間邊權重和盡可能的低，子圖內的邊權重和盡可能的高，從而達到聚類的目的。

2. 譜聚類基礎之一：無向權重圖

對于一個圖G，我們一般用點的集合 V 和邊的集合E來描述。即為G(V,E)。其中 V 即為我們數據集里面所有的點(v1,v2,...vn)。對于V中的任意兩個點，可以有邊連接，也可以沒有邊連接。我們定義權重wij為點vi和點vj之間的權重。由于我們是無向圖，所以wij=wji。 對于有邊連接的兩個點vi和vj，wij>0,對于沒有邊連接的兩個點vi和vj，wij=0。對于圖中的任意一個點vi，它的度di定義為和它相連的所有邊的權重之和

利用每個點度的定義，我們可以得到一個nxn的度矩陣D,它是一個對角矩陣，只有主對角線有值，對應第i行的第i個點的度數，定義如下：

利用所有點之間的權重值，我們可以得到圖的鄰接矩陣W，它也是一個n×n的矩陣，第i行的第j個值對應我們的權重wij。

除此之外，對于點集V的的一個子集A?V，我們定義：

3. 譜聚類基礎之二：相似矩陣

在上一節我們講到了鄰接矩陣W，它是由任意兩點之間的權重值wij組成的矩陣。通常我們可以自己輸入權重，但是在譜聚類中，我們只有數據點的定義，并沒有直接給出這個鄰接矩陣，那么怎么得到這個鄰接矩陣呢？

基本思想是，距離較遠的兩個點之間的邊權重值較低，而距離較近的兩個點之間的邊權重值較高，不過這僅僅是定性，我們需要定量的權重值。一般來說，我們可以通過樣本點距離度量的相似矩陣S來獲得鄰接矩陣W。

在實際的應用中，使用第三種全連接法來建立鄰接矩陣是最普遍的，而在全連接法中使用高斯徑向核RBF是最普遍的。

4. 譜聚類基礎之三：拉普拉斯矩陣

單獨把拉普拉斯矩陣(Graph Laplacians)拿出來介紹是因為后面的算法和這個矩陣的性質息息相關。它的定義很簡單，拉普拉斯矩陣L=D?W。D即為我們第二節講的度矩陣，它是一個對角矩陣。而W即為我們第二節講的鄰接矩陣，它可以由我們第三節的方法構建出。

拉普拉斯矩陣有一些很好的性質如下：

1）拉普拉斯矩陣是對稱矩陣，這可以由D和W都是對稱矩陣而得。

2）由于拉普拉斯矩陣是對稱矩陣，則它的所有的特征值都是實數。

3）對于任意的向量f,我們有

4) 拉普拉斯矩陣是半正定的，且對應的n個實數特征值都大于等于0，即0=λ1≤λ2≤...≤λn， 且最小的特征值為0，這個由性質3很容易得出。

5. 譜聚類基礎之四：無向圖切圖

對于無向圖G的切圖，我們的目標是將圖G(V,E)切成相互沒有連接的k個子圖，每個子圖點的集合為：A1,A2,..Ak，它們滿足Ai∩Aj=?,且A1∪A2∪...∪Ak=V.

那么如何切圖可以讓子圖內的點權重和高，子圖間的點權重和低呢？一個自然的想法就是最小化cut(A1,A2,...Ak), 但是可以發現，這種極小化的切圖存在問題，如下圖：

我們選擇一個權重最小的邊緣的點，比如C和H之間進行cut，這樣可以最小化cut(A1,A2,...Ak), 但是卻不是最優的切圖，如何避免這種切圖，并且找到類似圖中"Best Cut"這樣的最優切圖呢？我們下一節就來看看譜聚類使用的切圖方法。

6. 譜聚類之切圖聚類

為了避免最小切圖導致的切圖效果不佳，我們需要對每個子圖的規模做出限定，一般來說，有兩種切圖方式，第一種是RatioCut，第二種是Ncut。下面我們分別加以介紹。

6.1 RatioCut切圖

RatioCut切圖為了避免第五節的最小切圖，對每個切圖，不光考慮最小化cut(A1,A2,...Ak)，它還同時考慮最大化每個子圖點的個數，即：

由于我們在使用維度規約的時候損失了少量信息，導致得到的優化后的指示向量h對應的H現在不能完全指示各樣本的歸屬，因此一般在得到nxk維度的矩陣H后還需要對每一行進行一次傳統的聚類，比如使用K-Means聚類.

6.2 Ncut切圖

7. 譜聚類算法流程

一般來說，譜聚類主要的注意點為相似矩陣的生成方式、切圖的方式以及最后的聚類方法。最常用的相似矩陣的生成方式是基于高斯核距離的全連接方式。最常用的切圖方式是Ncut。而到最后常用的聚類方法為K-Means。下面為Ncut總結的譜聚類算法流程。

輸入：樣本集D=(x1,x2,...,xn)，相似矩陣的生成方式, 降維后的維度k1, 聚類方法，聚類后的維度k2

輸出： 簇劃分C(c1,c2,...ck2).

（1）根據輸入的相似矩陣的生成方式構建樣本的相似矩陣

（2）根據相似矩陣S構建鄰接矩陣W，構建度矩陣D

（3）計算出拉普拉斯矩陣L

（4）構建標準化后的拉普拉斯矩陣D?1/2LD?1/2

（5）計算D?1/2LD?1/2 最小的k1個特征值所對應的特征向量f

（6）將各自對應的特征向量f組成的矩陣按行標準化，最終組成n×k1維的特征矩陣F

（7）對F中的每一行作為一個k1維的樣本，共n個樣本，用輸入的聚類方法進行聚類，聚類維數為k2.

（8）得到簇劃分C(c1,c2,...ck2).

8. 譜聚類算法總結

主要優點：

（1）譜聚類算法只需要數據之間的相似度矩陣，因此對于處理稀疏數據的聚類很有效。這點傳統聚類算法比如K-Means很難做到

（2）由于使用了降維，因此在處理高維數據聚類時的復雜度比傳統聚類算法好

主要缺點：

（1）如果最終聚類的維度非常高，則由于降維的幅度不夠，譜聚類的運行速度和最后的聚類效果均不好

（2）聚類效果依賴于相似矩陣，不同的相似矩陣得到的最終聚類效果可能不同。

本文轉自：

譜聚類（spectral clustering）原理總結?www.cnblogs.com

總結

以上是生活随笔為你收集整理的聚类算法 距离矩阵_谱聚类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。