譜聚類算法SpectralClustering原理分析

1、譜聚類算法(Spectral Clustering)    譜聚類(Spectral Clustering, SC)是一種基于圖論的聚類方法將帶權(quán)無向圖劃分為兩個(gè)或兩個(gè)以上的最優(yōu)子圖，使子圖內(nèi)部盡量相似，而子圖間距離盡量距離較遠(yuǎn)，以達(dá)到常見的聚類的目的。其中的最優(yōu)是指最優(yōu)目標(biāo)函數(shù)不同，可以是割邊最小分割如圖1的Smallest cut(如后文的Min cut)， 也可以是分割規(guī)模差不多且割邊最小的分割如圖1的Best cut(如后文的Normalized cut)。圖1 譜聚類無向圖劃分Smallest cut和Best cut   

2、 這樣，譜聚類能夠識別任意形狀的樣本空間且收斂于全局最優(yōu)解，其基本思想是利用樣本數(shù)據(jù)的相似矩陣(拉普拉斯矩陣)進(jìn)行特征分解后得到的特征向量進(jìn)行聚類。1 理論基礎(chǔ)    對于如下空間向量item-user matrix：    如果要將item做聚類，常常想到k-means聚類方法，復(fù)雜度為o(tknm)，t為迭代次數(shù)，k為類的個(gè)數(shù)、n為item個(gè)數(shù)、m為空間向量特征數(shù)：    1 如果M足夠大呢？    2 K的選??？    3 類的假

3、設(shè)是凸球形的？    4 如果item是不同的實(shí)體呢？    5 Kmeans無可避免的局部最優(yōu)收斂？           這些都使常見的聚類問題變得相當(dāng)復(fù)雜。1.1 圖的表示    如果我們計(jì)算出item與item之間的相似度，便可以得到一個(gè)只有item的相似矩陣，進(jìn)一步，將item看成了Graph(G)中Vertex(V)，歌曲之間的相似度看成G中的Edge(E)，這樣便得到我們常見的圖的概念。

4、0;   對于圖的表示(如圖2)，常用的有：鄰接矩陣：E，eij表示vi和vi的邊的權(quán)值，E為對稱矩陣，對角線上元素為0，如圖2-2。Laplacian矩陣：L = D E， 其中di (行或列元素的和)，如圖2-3。圖2 圖的表示1.2 特征值與L矩陣    先考慮一種最優(yōu)化圖像分割方法，以二分為例，將圖cut為S和T兩部分，等價(jià)于如下?lián)p失函數(shù)cut(S, T)，如公式1所示，即最小(砍掉的邊的加權(quán)和)。    假設(shè)二分成兩類，S和T，用q(如公式2所示)表示分類情況，且q滿足公式3的關(guān)系，用

5、于類標(biāo)識。    那么：    其中D為對角矩陣，行或列元素的和，L為拉普拉斯矩陣。    由：    有:1、 L為對稱半正定矩陣，保證所有特征值都大于等于0；2、 L矩陣有唯一的0特征值，其對應(yīng)的特征向量為1。    離散求解q很困難，如果將問題松弛化為連續(xù)實(shí)數(shù)值，由瑞利熵的性質(zhì)知其二將你型的最小值就是L的特征值們(最小值，第二小值，.，最大值分別對應(yīng)矩陣L的最小特征值，第二小特征值，.，最大特征值，且極值q相應(yīng)的特征向量處取得，請參見瑞利熵

6、(Rayleigh quotient)。    寫到此，不得不對數(shù)學(xué)家們致敬，將cut(S,T)，巧妙地轉(zhuǎn)換成拉普拉斯矩陣特征值(向量)的問題，將離散的聚類問題，松弛為連續(xù)的特征向量，最小的系列特征向量對應(yīng)著圖最優(yōu)的系列劃分方法。剩下的僅是將松弛化的問題再離散化，即將特征向量再劃分開，便可以得到相應(yīng)的類別，如將圖3中的最小特征向量，按正負(fù)劃分，便得類A,B,C和類D,E,F,G。在K分類時(shí)，常將前K個(gè)特征向量，采用kmeans分類。    PS：    1、此處雖再次提到kmeans，但意義已經(jīng)遠(yuǎn)非引入概

7、念時(shí)的討論的kmeans了，此處的kmeans，更多的是與ensemble learning相關(guān)，在此不述；    2、k與聚類個(gè)數(shù)并非要求相同，可從第4節(jié)的相關(guān)物理意義中意會(huì)；    3、在前k個(gè)特征向量中，第一列值完全相同(迭代算法計(jì)算特征向量時(shí)，值極其相近)，kmeans時(shí)可以刪除，同時(shí)也可以通過這一列來簡易判斷求解特征值(向量)方法是否正確，常常問題在于鄰接矩陣不對稱。圖3 圖的L矩陣的特征值與特征向量2 最優(yōu)化方法    在kmeans等其它聚類方法中，很難刻劃類的大小關(guān)系，局部最優(yōu)解

8、也是無法回避的漏病。當(dāng)然這與kmeans的廣泛使用相斥原理簡單。2.1 Min cut方法    如2.2節(jié)的計(jì)算方法，最優(yōu)目標(biāo)函數(shù)如下的圖cut方法：    計(jì)算方法，可直接由計(jì)算L的最小特征值(特征向量)，求解。2.2 Nomarlized cut方法    Normarlized cut，目標(biāo)是同時(shí)考慮最小化cut邊和劃分平衡，以免像圖1中的cut出一個(gè)單獨(dú)的H。衡量子圖大小的標(biāo)準(zhǔn)是：子圖各個(gè)端點(diǎn)的Degree之和。2.3 Ratio Cut 方法    Ra

9、tio cut的目標(biāo)是同時(shí)考慮最小化cut邊和劃分平衡，以免像圖1中的cut出一個(gè)單獨(dú)的H。    最優(yōu)目標(biāo)函數(shù)為：2.4 Normalized相似變換    歸一化的L矩陣有：    因而L的最小特征值與D-(1/2)E D-(1/2)的最大特征值對應(yīng)。    而計(jì)算的L相比計(jì)算L要稍具優(yōu)勢，在具體實(shí)用中，常以L替代L，但是min cut和ratio cut不可以。    PS：這也是常常在人們的博客中，A說譜聚類為求最大K特征值(向量)，B說

10、譜聚類為求最小K個(gè)特征值(向量的原因)。3 譜聚類步驟第一步：數(shù)據(jù)準(zhǔn)備，生成圖的鄰接矩陣；第二步：歸一化普拉斯矩陣；第三步：生成最小的k個(gè)特征值和對應(yīng)的特征向量；第四步：將特征向量kmeans聚類(少量的特征向量)；4 譜聚類的物理意義    譜聚類中的矩陣：    可見不管是L、L都與E聯(lián)系特別大。如果將E看成一個(gè)高維向量空間，也能在一定程度上反映item之間的關(guān)系。將E直接kmeans聚類，得到的結(jié)果也能反映V的聚類特性，而譜聚類的引入L和L是使得G的分割具有物理意義。    而且，如果E的item(即n)足夠大，將難計(jì)算出它的kmeans，我們完全可以用PCA降維(仍為top的特征值與向量)。    上述對將E當(dāng)成向量空間矩陣，直觀地看符合我們的認(rèn)知，但缺乏理論基礎(chǔ)；而L(L等)的引入，如第2節(jié)所述，使得計(jì)算具有理論基礎(chǔ)，其前k個(gè)特征向量，也等價(jià)于對L(L等)的降維。    因而聚類就是為圖的劃分找了理論基礎(chǔ)，能達(dá)到降維的目的。 其中不少圖出源于Mining of Massive Datasets，對于同仁們的布道授業(yè)，一并感謝。推薦相關(guān)相關(guān)文檔：Wen-Yen Chen, Y