1、譜聚類算法總結(jié)聚類三種方法：k-means聚類、密度聚類、層次聚類和譜聚類SpectrumClustering簡(jiǎn)述譜聚類是一種基于圖論的聚類方法將帶權(quán)無(wú)向圖劃分為兩個(gè)或兩個(gè)以上的最優(yōu)子圖，使子圖內(nèi)部盡量相似，而子圖間距離盡量距離較遠(yuǎn)，以達(dá)到常見(jiàn)的聚類的目的。其中的最優(yōu)是指最優(yōu)目標(biāo)函數(shù)不同，可以是割邊最小分割，也可以是分割規(guī)模差不多且割邊最小的分割。譜聚類算法首先根據(jù)給定的樣本數(shù)據(jù)集定義一個(gè)描述成對(duì)數(shù)據(jù)點(diǎn)相似度的親合矩陣，并且計(jì)算矩陣的特征值和特征向量，然后選擇合適的特征向量聚類不同的數(shù)據(jù)點(diǎn)。譜聚類算法最初用于計(jì)算機(jī)視覺(jué)、VLSI設(shè)計(jì)等領(lǐng)域，最近才開(kāi)始用于機(jī)器學(xué)習(xí)中，并迅速成為國(guó)際上機(jī)器學(xué)習(xí)領(lǐng)域

2、的研究熱點(diǎn)。譜聚類算法建立在譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題，是一種點(diǎn)對(duì)聚類算法，與傳統(tǒng)的聚類算法相比，它具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解的優(yōu)點(diǎn)。根據(jù)不同的圖拉普拉斯構(gòu)造方法，可以得到不同的譜聚類算法形式。但是，這些算法的核心步驟都是相同的：利用點(diǎn)對(duì)之間的相似性，構(gòu)建親和度矩陣；構(gòu)建拉普拉斯矩陣；求解拉普拉斯矩陣最小的特征值對(duì)應(yīng)的特征向量（通常舍棄零特征所對(duì)應(yīng)的分量全相等的特征向量）；由這些特征向量構(gòu)成樣本點(diǎn)的新特征，采用K-means等聚類方法完成最后的聚類。譜聚類概述譜聚類是從圖論中演化過(guò)來(lái)的。主要思想是把所有的數(shù)據(jù)看做是空間中的點(diǎn)，這些點(diǎn)之間可以

3、用邊鏈接起來(lái)。距離比較遠(yuǎn)的兩個(gè)點(diǎn)之間的邊權(quán)重比較低，距離較近的兩點(diǎn)之間權(quán)重較高，通過(guò)對(duì)所有的數(shù)據(jù)點(diǎn)組成的圖進(jìn)行切割，讓切圖后不同的子圖間權(quán)重和盡可能低，而子圖內(nèi)的邊權(quán)重和盡可能高，從而達(dá)到聚類的目的。無(wú)向權(quán)重圖對(duì)于有邊連接的兩個(gè)點(diǎn)Vi和Vj,Wj0，若沒(méi)有邊連接，Wj=O,度di定義為和它相連的所有邊的權(quán)重之和，即n血=工叱?=1度矩陣Dnn是一個(gè)對(duì)角矩陣，只有對(duì)角線有值，對(duì)應(yīng)第i個(gè)點(diǎn)的度數(shù)：.d，2.D=TOC o 1-5 h zadjl/鄰近矩陣Wn,第行的第j個(gè)值對(duì)應(yīng)我們的權(quán)重Wj相似矩陣譜聚類中，通過(guò)樣本點(diǎn)距離度量的相似矩陣S來(lái)獲得鄰接矩陣W。構(gòu)造鄰接矩陣W的方法有鄰近法，K鄰近法和全

4、連接法。-鄰近法:設(shè)置距離閾值然后用歐氏距離Sj度量任意兩點(diǎn)Xj和Xj的距離，即Sij=|xi-Xj|22鄰接矩陣W定義為：由于不夠準(zhǔn)確，所以很少使用。K鄰近法利用KNN算法遍歷所有的樣本點(diǎn)，取每個(gè)樣本最近的k個(gè)點(diǎn)作為近鄰，只有和樣本距離最近的k個(gè)點(diǎn)之間的0.為了保證對(duì)稱性:1.只要一個(gè)點(diǎn)在另一點(diǎn)的k近鄰中則保留Sr航電KNN（：j）and衍電航EKWV（巧）*叼eK皿陽(yáng)2.必須兩個(gè)點(diǎn)互為k近鄰,才保留SiiXiKNNxjcr叼KAWi/i）嗆Ejand叼EKNN（d：j）全連接法相比前兩種方法，第三種方法所有的點(diǎn)之間的權(quán)重值都大于0,因此稱之為全連接法。可以選擇不同的核函數(shù)來(lái)定義邊權(quán)重，常用

5、的有多項(xiàng)式核函數(shù)，高斯核函數(shù)和Sigmoid核函數(shù)。最常用的是高斯核函數(shù)RBF,此時(shí)相似矩陣和鄰接矩陣相同：H逆=Si.j=exp（-一）在實(shí)際的應(yīng)用中，使用第三種全連接法來(lái)建立鄰接矩陣是最普遍的，而在全連接法中使用高斯徑向核RBF是最普遍的。拉普拉斯矩陣L=D-W,D為度矩陣，是一個(gè)對(duì)角矩陣。W為鄰接矩陣。其性質(zhì)如下：拉普拉斯矩陣是對(duì)稱矩陣，這可以由D和W都是對(duì)稱矩陣而得。由于拉普拉斯矩陣是對(duì)稱矩陣，則它的所有的特征值都是實(shí)數(shù)。對(duì)于任意的向量f,我們有/TW=-嚴(yán)町=E卅-叫仍TOC o 1-5 h zi-L-1172帀7；i71-=仏護(hù)-2工叫/右+52新）=可力叫場(chǎng)右）3_*JJtJ*-

6、*FFa112jJ171-拉普拉斯矩陣是半正定的，且對(duì)應(yīng)的n個(gè)實(shí)數(shù)特征值都大于等于0,即0=幾W2W.Wn，且最小的特征值為0。無(wú)向圖切圖對(duì)于無(wú)向圖G的切圖，我們的目標(biāo)是將圖G(V,E)切成相互沒(méi)有連接的k個(gè)子圖，每個(gè)子圖點(diǎn)的集合為：A，A2,.Ak，它們滿足AinAj=0,且AUA2U.UAk=V對(duì)于任意兩個(gè)子圖點(diǎn)的集合A,BuV,AnB=0,我們定義A和B之間的切圖權(quán)重為:對(duì)于k個(gè)子圖點(diǎn)的集合：A,A2，.Ak,我們定義切圖cut為:中A為Ai的補(bǔ)集。那么如何切圖可以讓子圖內(nèi)的點(diǎn)權(quán)重和高，子圖間的點(diǎn)權(quán)重和低呢？一個(gè)自然的想法就是最小化cut(A,A2,.Ak),但是可以發(fā)現(xiàn)，這種極小化的切

7、圖存在問(wèn)題，如下圖：我們選擇一個(gè)權(quán)重最小的邊緣的點(diǎn)，比如C和H之間進(jìn)行cut，這樣可以最小化cut(A,A2,.Ak),但是卻不是最優(yōu)的切圖，如何避免這種切圖，并且找到類似圖中BestCut這樣的最優(yōu)切圖呢？譜聚類之切圖聚類RatioCut切圖RatioCut切圖為了避免最小切圖，對(duì)每個(gè)切圖，不光考慮最小化cut(A,A2,.Ak)，它同時(shí)還考慮最大化每個(gè)子圖點(diǎn)的個(gè)數(shù)，即：接下來(lái)是最小化這個(gè)RatioCut函數(shù):引入指示向量hj=h,h2,.hk,j=,2,.k0*A.-=“；三j!h1,h2,.hk,j=,2,.k，對(duì)于任意一個(gè)向量hj,它是一個(gè)n維向量hj,它是一個(gè)n維向量，定義叩為:對(duì)于

8、hiTLhi:呀匸撫=+imh說(shuō))In1=豆(52(=7-O)2-I-Y世喚e)對(duì)應(yīng)的RatioCut函數(shù)表達(dá)式為:ct血血CW,山)=ykfLhj=工=trHTLH)f-1注意到HTH=I,則我們的切圖優(yōu)化目標(biāo)為:arcmins.t.HTH=Iv對(duì)于hiTLhi,我們的目標(biāo)是找到最小的L的特征值,e而i-1則我們的目標(biāo)就是找到k個(gè)最小的特征值，一般來(lái)說(shuō)，k遠(yuǎn)遠(yuǎn)小于n,也就是說(shuō)，此時(shí)我們進(jìn)行了維度規(guī)約，將維度從n降到了k,從而近似可以解決這個(gè)NP難的問(wèn)題。通過(guò)找到L的最小的k個(gè)特征值，可以得到對(duì)應(yīng)的k個(gè)特征向量，這k個(gè)特征向量組成一個(gè)nxk維度的矩陣，即為我們的H。一般需要對(duì)H矩陣按行做標(biāo)準(zhǔn)化

9、，即由于我們?cè)谑褂镁S度規(guī)約的時(shí)候損失了少量信息，導(dǎo)致得到的優(yōu)化后的指示向量h對(duì)應(yīng)的H現(xiàn)在不能完全指示各樣本的歸屬，因此一般在得到nxk維度的矩陣H后還需要對(duì)每一行進(jìn)行一次傳統(tǒng)的聚類，比如使用K-Means聚類.Ncut切圖Ncut切圖和RatioCut切圖很類似，但是把Ratiocut的分母|Ai|換成vol(Ai).由于子圖樣本的個(gè)數(shù)多并不一定權(quán)重就大，我們切圖時(shí)基于權(quán)重也更合我們的目標(biāo)，因此一般來(lái)說(shuō)Ncut切圖優(yōu)于RatioCut切圖。1呂W(Ai.Ai)對(duì)應(yīng)的，Ncut切圖對(duì)指示向量hh做了改進(jìn)。注意到RatioCut切圖的指示向量使用的是1標(biāo)示樣本歸屬，而Ncut切圖使用了子圖權(quán)重優(yōu)化

10、目標(biāo)函數(shù)為：tNGiitA-,A-2.Ak)=工眄L松=工迅工LH衣=tr(HTLHi-1i-1來(lái)標(biāo)示指示向量h,定義如下:對(duì)于暉Lht=3:他-T7i-1西一：y(工比嘶(_JJvolAj)1t1$.L:+皿(生V*)誠(chéng))mEAiJE.1.-(曲地，脫_0)3工理耐刃(0,)啊疋.4.訶e.4,;”應(yīng)川(Ay)V二7(11)HTDH=I.推導(dǎo)如下:72J-11加（比）最終為：時(shí)百mint.r(HTLH)s.HTDH=I令H=D-1/2F,將指示向量矩陣H做一個(gè)小小的轉(zhuǎn)化，使其為標(biāo)準(zhǔn)正交基，則HTLH=FTD-1/2LD-1/2F,HTDH=FTF=I那么目標(biāo)函數(shù)變?yōu)椋和觤inriTrir1/

11、3LP-1/3F）s.t.FTF=丁這樣我們就可以繼續(xù)按照RatioCut的思想，求出D-1/2LD-1/2的最小的前k個(gè)特征值，然后求出對(duì)應(yīng)的特征向量，并標(biāo)準(zhǔn)化，得到最后的特征矩陣F,最后對(duì)F進(jìn)行一次傳統(tǒng)的聚類（比如K-Means）即可。D-1/2LD-1/2相當(dāng)于對(duì)拉普拉斯矩陣L做了一次標(biāo)準(zhǔn)化，譜聚類算法流程譜聚類主要的注意點(diǎn)為相似矩陣的生成方式，切圖的方式以及最后的聚類方法。最常用的相似矩陣的生成方式是基于高斯核距離的全連接方式，最常用的切圖方式是Ncut。而到最后常用的聚類方法為K-Means。下面以Ncut總結(jié)譜聚類算法流程。輸入：樣本集D=（x1,x2,.,xn），相似矩陣的生成方式，降維后的維度k1,聚類方法，聚類后的維度k2輸出：簇劃分C（c1,c2,.ck2）根據(jù)輸入的相似矩陣的生成方式構(gòu)建樣本的相似矩陣S2）根據(jù)相似矩陣S構(gòu)建鄰接矩陣W,構(gòu)建度矩陣D3）計(jì)算出拉普拉斯矩陣L4）構(gòu)建標(biāo)準(zhǔn)化后的拉普拉斯矩陣D-1/2LD-1/25）計(jì)算D-1/2LD-1/2最小的k1個(gè)特征值所各自對(duì)應(yīng)的特征向量f2將各自對(duì)應(yīng)的特征向量f組成的矩陣按行標(biāo)準(zhǔn)化，最終組成nxk1維的特征矩陣F7對(duì)F中的每一行作為一個(gè)k1維的樣本，共n個(gè)樣本，用輸入的聚類方法進(jìn)行聚類，聚類維數(shù)為k2。8）得到簇劃分C（c1,c2,.ck2）總結(jié)譜聚類算法的主要