譜聚類算法總結

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

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

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

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

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

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

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

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

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

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

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