譜聚類(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
這樣，譜聚類能夠識(shí)別任意形狀的樣本空間且收斂于全局最優(yōu)解褒侧，其基本思想是利用樣本數(shù)據(jù)的相似矩陣(拉普拉斯矩陣)進(jìn)行特征分解后得到的特征向量進(jìn)行聚類良风。
1?理論基礎(chǔ)
??? 對(duì)于如下空間向量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 類的假設(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)眯牧，這樣便得到我們常見的圖的概念蹋岩。
??? 對(duì)于圖的表示(如圖2)，常用的有：
鄰接矩陣：E学少，eij表示vi和vi的邊的權(quán)值剪个，E為對(duì)稱矩陣，對(duì)角線上元素為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)系，用于類標(biāo)識(shí)沸移。
??? 那么：
??? 其中D為對(duì)角矩陣痪伦，行或列元素的和，L為拉普拉斯矩陣雹锣。
??? 由：
??? 有:
1网沾、 L為對(duì)稱半正定矩陣，保證所有特征值都大于等于0蕊爵；
2辉哥、 L矩陣有唯一的0特征值，其對(duì)應(yīng)的特征向量為1。
離散求解q很困難醋旦，如果將問題松弛化為連續(xù)實(shí)數(shù)值恒水，由瑞利熵的性質(zhì)知其二將你型的最小值就是L的特征值們(最小值，第二小值饲齐，......钉凌，最大值分別對(duì)應(yīng)矩陣L的最小特征值，第二小特征值捂人，......御雕，最大特征值，且極值q相應(yīng)的特征向量處取得先慷，請(qǐng)參見瑞利熵(Rayleigh quotient))饮笛。
??? 寫到此咨察，不得不對(duì)數(shù)學(xué)家們致敬论熙，將cut(S,T)，巧妙地轉(zhuǎn)換成拉普拉斯矩陣特征值(向量)的問題摄狱，將離散的聚類問題脓诡，松弛為連續(xù)的特征向量，最小的系列特征向量對(duì)應(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)非引入概念時(shí)的討論的kmeans了紫谷，此處的kmeans齐饮，更多的是與ensemble learning相關(guān)，在此不述笤昨；
??? 2祖驱、k與聚類個(gè)數(shù)并非要求相同，可從第4節(jié)的相關(guān)物理意義中意會(huì)瞒窒；
??? 3捺僻、在前k個(gè)特征向量中，第一列值完全相同(迭代算法計(jì)算特征向量時(shí)根竿，值極其相近)陵像，kmeans時(shí)可以刪除就珠，同時(shí)也可以通過這一列來簡(jiǎn)易判斷求解特征值(向量)方法是否正確，常常問題在于鄰接矩陣不對(duì)稱醒颖。
圖3 圖的L矩陣的特征值與特征向量
2?最優(yōu)化方法
??? 在kmeans等其它聚類方法中妻怎，很難刻劃類的大小關(guān)系，局部最優(yōu)解也是無法回避的漏病泞歉。當(dāng)然這與kmeans的廣泛使用相斥——原理簡(jiǎn)單逼侦。
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?方法
Ratio 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)的最大特征值對(duì)應(yīng)援制。
而計(jì)算的L’相比計(jì)算L要稍具優(yōu)勢(shì)戏挡，在具體實(shí)用中，常以L’替代L晨仑，但是min cut和ratio cut不可以褐墅。
??? PS：這也是常常在人們的博客中，A說譜聚類為求最大K特征值(向量)洪己，B說譜聚類為求最小K個(gè)特征值(向量的原因)妥凳。
3?譜聚類步驟
第一步：數(shù)據(jù)準(zhǔn)備，生成圖的鄰接矩陣码泛；
第二步：歸一化普拉斯矩陣猾封；
第三步：生成最小的k個(gè)特征值和對(duì)應(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的特征值與向量)殿衰。
上述對(duì)將E當(dāng)成向量空間矩陣，直觀地看符合我們的認(rèn)知盛泡，但缺乏理論基礎(chǔ)闷祥；而L(L’等)的引入，如第2節(jié)所述傲诵，使得計(jì)算具有理論基礎(chǔ)凯砍，其前k個(gè)特征向量，也等價(jià)于對(duì)L(L’等)的降維拴竹。
??? 因而聚類就是為圖的劃分找了理論基礎(chǔ)悟衩，能達(dá)到降維的目的。
