聚類三種方法：k-means聚類毒租、密度聚類左刽、層次聚類和譜聚類Spectrum Clustering

簡述

譜聚類是一種基于圖論的聚類方法——將帶權(quán)無向圖劃分為兩個或兩個以上的最優(yōu)子圖丹泉，使子圖內(nèi)部盡量相似，而子圖間距離盡量距離較遠，以達到常見的聚類的目的。其中的最優(yōu)是指最優(yōu)目標函數(shù)不同议忽，可以是割邊最小分割,也可以是分割規(guī)模差不多且割邊最小的分割。

譜聚類算法首先根據(jù)給定的樣本數(shù)據(jù)集定義一個描述成對數(shù)據(jù)點相似度的親合矩陣,并且計算矩陣的特征值和特征向量十减，然后選擇合適的特征向量聚類不同的數(shù)據(jù)點栈幸。譜聚類算法最初用于計算機視覺、VLS I 設(shè)計等領(lǐng)域帮辟，最近才開始用于機器學(xué)習(xí)中速址，并迅速成為國際上機器學(xué)習(xí)領(lǐng)域的研究熱點。譜聚類算法建立在譜圖理論基礎(chǔ)上由驹，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題芍锚，是一種點對聚類算法，與傳統(tǒng)的聚類算法相比，它具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解的優(yōu)點并炮。

根據(jù)不同的圖拉普拉斯構(gòu)造方法默刚，可以得到不同的譜聚類算法形式。但是逃魄，這些算法的核心步驟都是相同的：

利用點對之間的相似性荤西，構(gòu)建親和度矩陣；
構(gòu)建拉普拉斯矩陣嗅钻；
求解拉普拉斯矩陣最小的特征值對應(yīng)的特征向量（通常舍棄零特征所對應(yīng)的分量全相等的特征向量）皂冰；
由這些特征向量構(gòu)成樣本點的新特征，采用K-means等聚類方法完成最后的聚類养篓。

譜聚類概述

譜聚類是從圖論中演化過來的秃流。主要思想是把所有的數(shù)據(jù)看做是空間中的點，這些點之間可以用邊鏈接起來柳弄。距離比較遠的兩個點之間的邊權(quán)重比較低舶胀，距離較近的兩點之間權(quán)重較高，通過對所有的數(shù)據(jù)點組成的圖進行切割碧注，讓切圖后不同的子圖間權(quán)重和盡可能低嚣伐，而子圖內(nèi)的邊權(quán)重和盡可能高，從而達到聚類的目的萍丐。

無向權(quán)重圖

對于有邊連接的兩個點v_i和v_j,w_ij>0轩端，若沒有邊連接，w_ij=0逝变，度d_i定義為和它相連的所有邊的權(quán)重之和基茵，即

度矩陣D_nn是一個對角矩陣，只有對角線有值壳影，對應(yīng)第i個點的度數(shù)：

鄰近矩陣W_nn,第i行的第j個值對應(yīng)我們的權(quán)重w_ij

相似矩陣

譜聚類中拱层，通過樣本點距離度量的相似矩陣S來獲得鄰接矩陣W。
構(gòu)造鄰接矩陣W的方法有? -鄰近法宴咧，K鄰近法和全連接法根灯。
? -鄰近法:設(shè)置距離閾值?，然后用歐氏距離s_ij度量任意兩點x_i和x_j的距離掺栅，即s_ij=||x_i-x_j||₂²
鄰接矩陣W定義為：

由于不夠準確烙肺，所以很少使用。
K鄰近法
利用KNN算法遍歷所有的樣本點氧卧，取每個樣本最近的k個點作為近鄰桃笙，只有和樣本距離最近的k個點之間的w_ij>0.為了保證對稱性：

只要一個點在另一點的k近鄰中，則保留S_ij
必須兩個點互為k近鄰假抄，才保留S_ij

全連接法
相比前兩種方法怎栽，第三種方法所有的點之間的權(quán)重值都大于0，因此稱之為全連接法宿饱⊙椋可以選擇不同的核函數(shù)來定義邊權(quán)重，常用的有多項式核函數(shù)谬以，高斯核函數(shù)和Sigmoid核函數(shù)强饮。最常用的是高斯核函數(shù)RBF，此時相似矩陣和鄰接矩陣相同：

在實際的應(yīng)用中为黎，使用第三種全連接法來建立鄰接矩陣是最普遍的邮丰，而在全連接法中使用高斯徑向核RBF是最普遍的。

拉普拉斯矩陣

L=D-W,D為度矩陣铭乾，是一個對角矩陣剪廉。W為鄰接矩陣。
其性質(zhì)如下：

拉普拉斯矩陣是對稱矩陣炕檩，這可以由D和W都是對稱矩陣而得斗蒋。
由于拉普拉斯矩陣是對稱矩陣，則它的所有的特征值都是實數(shù)笛质。
對于任意的向量f泉沾，我們有
拉普拉斯矩陣是半正定的，且對應(yīng)的n個實數(shù)特征值都大于等于0妇押，即0=λ₁≤λ₂≤...≤λ_n跷究，且最小的特征值為0。

無向圖切圖

對于無向圖G的切圖敲霍，我們的目標是將圖G(V,E)切成相互沒有連接的k個子圖俊马，每個子圖點的集合為：A₁,A₂,..A_k，它們滿足A_i∩A_j=?,且A₁∪A₂∪...∪A_k=V

對于任意兩個子圖點的集合A,B?V, A∩B=?, 我們定義A和B之間的切圖權(quán)重為：

對于k個子圖點的集合：A₁,A₂,..A_k,我們定義切圖cut為：

中Aˉ_i為Ai的補集色冀。
那么如何切圖可以讓子圖內(nèi)的點權(quán)重和高潭袱，子圖間的點權(quán)重和低呢？一個自然的想法就是最小化cut(A₁,A₂,..A_k), 但是可以發(fā)現(xiàn)锋恬，這種極小化的切圖存在問題屯换，如下圖：

我們選擇一個權(quán)重最小的邊緣的點，比如C和H之間進行cut与学，這樣可以最小化cut(A₁,A₂,..A_k), 但是卻不是最優(yōu)的切圖彤悔，如何避免這種切圖，并且找到類似圖中"Best Cut"這樣的最優(yōu)切圖呢索守？

譜聚類之切圖聚類

RatioCut切圖

RatioCut切圖為了避免最小切圖晕窑，對每個切圖，不光考慮最小化cut(A₁,A₂,..A_k)卵佛，它同時還考慮最大化每個子圖點的個數(shù)杨赤，即：

接下來是最小化這個 RatioCut函數(shù)：
引入指示向量h_j={h₁,h₂,..h_k},j=1,2,..k,對于任意一個向量h_j,它是一個n維向量h_j,它是一個n維向量敞斋，定義h_ji為：

對于h_i^TLh_i:

對應(yīng)的RatioCut函數(shù)表達式為：

注意到H^TH=I,則我們的切圖優(yōu)化目標為:

對于h_i^TLh_i，我們的目標是找到最小的L的特征值,e而

則我們的目標就是找到k個最小的特征值疾牲，一般來說植捎，k遠遠小于n，也就是說阳柔，此時我們進行了維度規(guī)約焰枢，將維度從n降到了k，從而近似可以解決這個NP難的問題舌剂。
通過找到L的最小的k個特征值济锄，可以得到對應(yīng)的k個特征向量，這k個特征向量組成一個nxk維度的矩陣霍转，即為我們的H荐绝。一般需要對H矩陣按行做標準化，即

由于我們在使用維度規(guī)約的時候損失了少量信息避消，導(dǎo)致得到的優(yōu)化后的指示向量h對應(yīng)的H現(xiàn)在不能完全指示各樣本的歸屬很泊，因此一般在得到nxk維度的矩陣H后還需要對每一行進行一次傳統(tǒng)的聚類，比如使用K-Means聚類.

Ncut切圖

Ncut切圖和RatioCut切圖很類似沾谓，但是把Ratiocut的分母|Ai|換成vol(Ai). 由于子圖樣本的個數(shù)多并不一定權(quán)重就大委造，我們切圖時基于權(quán)重也更合我們的目標，因此一般來說Ncut切圖優(yōu)于RatioCut切圖均驶。

對應(yīng)的昏兆，Ncut切圖對指示向量hh做了改進。注意到RatioCut切圖的指示向量使用的是

標示樣本歸屬妇穴，而Ncut切圖使用了子圖權(quán)重

來標示指示向量h爬虱，定義如下:

對于h_i^TLh_i

優(yōu)化目標函數(shù)為：

H^TDH=I.推導(dǎo)如下：

最終為：

令H=D^-1/2F,將指示向量矩陣H做一個小小的轉(zhuǎn)化，使其為標準正交基腾它，則H^TLH=F^TD^-1/2LD^-1/2F, H^TDH=F^TF=I
那么目標函數(shù)變?yōu)椋?br>

這樣我們就可以繼續(xù)按照RatioCut的思想跑筝，求出D^-1/2LD^-1/2的最小的前k個特征值，然后求出對應(yīng)的特征向量瞒滴，并標準化曲梗，得到最后的特征矩陣F,最后對F進行一次傳統(tǒng)的聚類（比如K-Means）即可。
D^-1/2LD^-1/2相當于對拉普拉斯矩陣L做了一次標準化妓忍，

譜聚類算法流程

譜聚類主要的注意點為相似矩陣的生成方式虏两，切圖的方式以及最后的聚類方法。
最常用的相似矩陣的生成方式是基于高斯核距離的全連接方式世剖，最常用的切圖方式是Ncut定罢。而到最后常用的聚類方法為K-Means。下面以Ncut總結(jié)譜聚類算法流程旁瘫。

輸入：樣本集D=(x1,x2,...,xn)祖凫，相似矩陣的生成方式, 降維后的維度k1, 聚類方法琼蚯，聚類后的維度k2
輸出：簇劃分C(c1,c2,...ck2)

根據(jù)輸入的相似矩陣的生成方式構(gòu)建樣本的相似矩陣S
2）根據(jù)相似矩陣S構(gòu)建鄰接矩陣W，構(gòu)建度矩陣D
3）計算出拉普拉斯矩陣L
4）構(gòu)建標準化后的拉普拉斯矩陣D^-1/2LD^-1/2
5）計算D^-1/2LD^-1/2最小的k1個特征值所各自對應(yīng)的特征向量f
將各自對應(yīng)的特征向量f組成的矩陣按行標準化惠况，最終組成n×k1維的特征矩陣F
7）對F中的每一行作為一個k1維的樣本凌停，共n個樣本，用輸入的聚類方法進行聚類售滤，聚類維數(shù)為k2。
8）得到簇劃分C(c1,c2,...ck2)

總結(jié)

譜聚類算法的主要優(yōu)點有：
1）譜聚類只需要數(shù)據(jù)之間的相似度矩陣台诗，因此對于處理稀疏數(shù)據(jù)的聚類很有效完箩。這點傳統(tǒng)聚類算法比如K-Means很難做到
2）由于使用了降維，因此在處理高維數(shù)據(jù)聚類時的復(fù)雜度比傳統(tǒng)聚類算法好拉队。
譜聚類算法的主要缺點有：
1）如果最終聚類的維度非常高弊知，則由于降維的幅度不夠，譜聚類的運行速度和最后的聚類效果均不好粱快。

聚類效果依賴于相似矩陣秩彤，不同的相似矩陣得到的最終聚類效果可能很不同。

轉(zhuǎn)自：https://www.cnblogs.com/pinard/p/6221564.html

譜聚類算法總結(jié)