數(shù)學(xué)算法俱樂部

日期：2020年10月02日

正文共：4399字1圖

預(yù)計(jì)閱讀時間：11分鐘

來源：劉建平博客

譜聚類（spectral clustering）是廣泛使用的聚類算法，比起傳統(tǒng)的K-Means算法，譜聚類對數(shù)據(jù)分布的適應(yīng)性更強(qiáng)，聚類效果也很優(yōu)秀，同時聚類的計(jì)算量也小很多，更加難能可貴的是實(shí)現(xiàn)起來也不復(fù)雜。在處理實(shí)際的聚類問題時，個人認(rèn)為譜聚類是應(yīng)該首先考慮的幾種算法之一。下面我們就對譜聚類的算法原理做一個總結(jié)。

1. 譜聚類概述

譜聚類是從圖論中演化出來的算法，后來在聚類中得到了廣泛的應(yīng)用。它的主要思想是把所有的數(shù)據(jù)看做空間中的點(diǎn)，這些點(diǎn)之間可以用邊連接起來。距離較遠(yuǎn)的兩個點(diǎn)之間的邊權(quán)重值較低，而距離較近的兩個點(diǎn)之間的邊權(quán)重值較高，通過對所有數(shù)據(jù)點(diǎn)組成的圖進(jìn)行切圖，讓切圖后不同的子圖間邊權(quán)重和盡可能的低，而子圖內(nèi)的邊權(quán)重和盡可能的高，從而達(dá)到聚類的目的。

乍一看，這個算法原理的確簡單，但是要完全理解這個算法的話，需要對圖論中的無向圖，線性代數(shù)和矩陣分析都有一定的了解。下面我們就從這些需要的基礎(chǔ)知識開始，一步步學(xué)習(xí)譜聚類。

2. 譜聚類基礎(chǔ)之一：無向權(quán)重圖

由于譜聚類是基于圖論的，因此我們首先溫習(xí)下圖的概念。對于一個圖GG，我們一般用點(diǎn)的集合V和邊的集合E來描述。即為G(V,E)。其中V即為我們數(shù)據(jù)集里面所有的點(diǎn)(v1,v2,...vn)。對于V中的任意兩個點(diǎn)，可以有邊連接，也可以沒有邊連接。我們定義權(quán)重wij為點(diǎn)vi和點(diǎn)vj之間的權(quán)重。由于我們是無向圖，所以wij=wji。

對于有邊連接的兩個點(diǎn)vi和vj，wij>0,對于沒有邊連接的兩個點(diǎn)vivi和vj，wij=0。對于圖中的任意一個點(diǎn)vi，它的度定義為和它相連的所有邊的權(quán)重之和，即

利用每個點(diǎn)度的定義，我們可以得到一個nxn的度矩陣D,它是一個對角矩陣，只有主對角線有值，對應(yīng)第i行的第i個點(diǎn)的度數(shù)，定義如下：

利用所有點(diǎn)之間的權(quán)重值，我們可以得到圖的鄰接矩陣W，它也是一個nxn的矩陣，第i行的第j個值對應(yīng)我們的權(quán)重wij。

除此之外，對于點(diǎn)集V的的一個子集A?V，我們定義：

3. 譜聚類基礎(chǔ)之二：相似矩陣

在上一節(jié)我們講到了鄰接矩陣W，它是由任意兩點(diǎn)之間的權(quán)重值wij組成的矩陣。通常我們可以自己輸入權(quán)重，但是在譜聚類中，我們只有數(shù)據(jù)點(diǎn)的定義，并沒有直接給出這個鄰接矩陣，那么怎么得到這個鄰接矩陣呢？

基本思想是，距離較遠(yuǎn)的兩個點(diǎn)之間的邊權(quán)重值較低，而距離較近的兩個點(diǎn)之間的邊權(quán)重值較高，不過這僅僅是定性，我們需要定量的權(quán)重值。一般來說，我們可以通過樣本點(diǎn)距離度量的相似矩陣S來獲得鄰接矩陣W。

構(gòu)建鄰接矩陣W的方法有三類。?-鄰近法，K鄰近法和全連接法。

對于?-鄰近法，它設(shè)置了一個距離閾值??，然后用歐式距離sijsij度量任意兩點(diǎn)xi和xj的距離。即相似矩陣的, ?然后根據(jù)sij和?的大小關(guān)系，來定義鄰接矩陣W如下：

從上式可見，兩點(diǎn)間的權(quán)重要不就是?,要不就是0，沒有其他的信息了。距離遠(yuǎn)近度量很不精確，因此在實(shí)際應(yīng)用中，我們很少使用?-鄰近法。

第二種定義鄰接矩陣W的方法是K鄰近法，利用KNN算法遍歷所有的樣本點(diǎn)，取每個樣本最近的k個點(diǎn)作為近鄰，只有和樣本距離最近的k個點(diǎn)之間的wij>0。但是這種方法會造成重構(gòu)之后的鄰接矩陣W非對稱，我們后面的算法需要對稱鄰接矩陣。為了解決這種問題，一般采取下面兩種方法之一：

第一種K鄰近法是只要一個點(diǎn)在另一個點(diǎn)的K近鄰中，則保留sij

第二種K鄰近法是必須兩個點(diǎn)互為K近鄰中，才能保留sij

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

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

4. 譜聚類基礎(chǔ)之三：拉普拉斯矩陣

單獨(dú)把拉普拉斯矩陣(Graph Laplacians)拿出來介紹是因?yàn)楹竺娴乃惴ê瓦@個矩陣的性質(zhì)息息相關(guān)。它的定義很簡單，拉普拉斯矩陣L=D?WL=D?W。DD即為我們第二節(jié)講的度矩陣，它是一個對角矩陣。而WW即為我們第二節(jié)講的鄰接矩陣，它可以由我們第三節(jié)的方法構(gòu)建出。

拉普拉斯矩陣有一些很好的性質(zhì)如下：

? ? 1）拉普拉斯矩陣是對稱矩陣，這可以由DD和WW都是對稱矩陣而得。

? ? 2）由于拉普拉斯矩陣是對稱矩陣，則它的所有的特征值都是實(shí)數(shù)。

? ? 3）對于任意的向量ff,我們有

? ? 這個利用拉普拉斯矩陣的定義很容易得到如下：

? ? 4) 拉普拉斯矩陣是半正定的，且對應(yīng)的n個實(shí)數(shù)特征值都大于等于0，即0=λ1≤λ2≤...≤λn，且最小的特征值為0，這個由性質(zhì)3很容易得出。

5. 譜聚類基礎(chǔ)之四：無向圖切圖

對于無向圖GG的切圖，我們的目標(biāo)是將圖G(V,E)G(V,E)切成相互沒有連接的k個子圖，每個子圖點(diǎn)的集合為：A1,A2,..Ak ,它們滿足Ai∩Aj=?,且A1∪A2∪...∪Ak=V.

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

那么對于我們k個子圖點(diǎn)的集合：A1,A2,..Ak，我們定義切圖cut為：

其中為Ai的補(bǔ)集，意為除Ai子集外其他V的子集的并集。

那么如何切圖可以讓子圖內(nèi)的點(diǎn)權(quán)重和高，子圖間的點(diǎn)權(quán)重和低呢？一個自然的想法就是最小化cut(A1,A2,...Ak), 但是可以發(fā)現(xiàn)，這種極小化的切圖存在問題，如下圖：

我們選擇一個權(quán)重最小的邊緣的點(diǎn)，比如C和H之間進(jìn)行cut，這樣可以最小化cut(A1,A2,...Ak), 但是卻不是最優(yōu)的切圖，如何避免這種切圖，并且找到類似圖中"Best Cut"這樣的最優(yōu)切圖呢？我們下一節(jié)就來看看譜聚類使用的切圖方法。

6. 譜聚類之切圖聚類

為了避免最小切圖導(dǎo)致的切圖效果不佳，我們需要對每個子圖的規(guī)模做出限定，一般來說，有兩種切圖方式，第一種是RatioCut，第二種是Ncut。下面我們分別加以介紹。

6.1 RatioCut切圖

RatioCut切圖為了避免第五節(jié)的最小切圖，對每個切圖，不光考慮最小化cut(A1,A2,...Ak)，它還同時考慮最大化每個子圖點(diǎn)的個數(shù)，即：

那么怎么最小化這個RatioCut函數(shù)呢？牛人們發(fā)現(xiàn)，RatioCut函數(shù)可以通過如下方式表示。

我們引入指示向量hj∈{h1,h2,..hk}j=1,2,...k,對于任意一個向量hj, 它是一個n維向量（n為樣本數(shù)），我們定義hij為：

那么我們對于,有：

上述第（1）式用了上面第四節(jié)的拉普拉斯矩陣的性質(zhì)3. 第二式用到了指示向量的定義?？梢钥闯觯瑢τ谀骋粋€子圖i，它的RatioCut對應(yīng)于,那么我們的k個子圖呢？對應(yīng)的RatioCut函數(shù)表達(dá)式為：

其中tr(HTLH)為矩陣的跡。也就是說，我們的RatioCut切圖，實(shí)際上就是最小化我們的tr(HTLH)。注意到HTH=I,則我們的切圖優(yōu)化目標(biāo)為:

注意到我們H矩陣?yán)锩娴拿恳粋€指示向量都是n維的，向量中每個變量的取值為0或者，就有2^n種取值，有k個子圖的話就有k個指示向量，共有k2^n種H，因此找到滿足上面優(yōu)化目標(biāo)的H是一個NP難的問題。那么是不是就沒有辦法了呢？

注意觀察tr(HTLH)中每一個優(yōu)化子目標(biāo),其中h是單位正交基， L為對稱矩陣，此時的最大值為L的最大特征值，最小值是L的最小特征值。如果你對主成分分析PCA很熟悉的話，這里很好理解。在PCA中，我們的目標(biāo)是找到協(xié)方差矩陣（對應(yīng)此處的拉普拉斯矩陣L）的最大的特征值，而在我們的譜聚類中，我們的目標(biāo)是找到目標(biāo)的最小的特征值，得到對應(yīng)的特征向量，此時對應(yīng)二分切圖效果最佳。也就是說，我們這里要用到維度規(guī)約的思想來近似去解決這個NP難的問題。

對于，我們的目標(biāo)是找到最小的L的特征值，而對于，則我們的目標(biāo)就是找到k個最小的特征值，一般來說，k遠(yuǎn)遠(yuǎn)小于n，也就是說，此時我們進(jìn)行了維度規(guī)約，將維度從n降到了k，從而近似可以解決這個NP難的問題。

通過找到L的最小的k個特征值，可以得到對應(yīng)的k個特征向量，這k個特征向量組成一個nxk維度的矩陣，即為我們的H。一般需要對H矩陣按行做標(biāo)準(zhǔn)化，即

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

6.2 Ncut切圖

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

對應(yīng)的，Ncut切圖對指示向量hh做了改進(jìn)。注意到RatioCut切圖的指示向量使用的是標(biāo)示樣本歸屬，而Ncut切圖使用了子圖權(quán)重來標(biāo)示指示向量h，定義如下:

那么我們對于,有：

推導(dǎo)方式和RatioCut完全一致。也就是說，我們的優(yōu)化目標(biāo)仍然是

但是此時我們的HTH≠1,而是HTDH=I。推導(dǎo)如下：

也就是說，此時我們的優(yōu)化目標(biāo)最終為：

此時我們的H中的指示向量h并不是標(biāo)準(zhǔn)正交基，所以在RatioCut里面的降維思想不能直接用。怎么辦呢？其實(shí)只需要將指示向量矩陣H做一個小小的轉(zhuǎn)化即可。

我們令，則:?

也就是說優(yōu)化目標(biāo)變成了:

可以發(fā)現(xiàn)這個式子和RatioCut基本一致，只是中間的L變成了。這樣我們就可以繼續(xù)按照RatioCut的思想，求出的最小的前k個特征值，然后求出對應(yīng)的特征向量，并標(biāo)準(zhǔn)化，得到最后的特征矩陣F,最后對F進(jìn)行一次傳統(tǒng)的聚類（比如K-Means）即可。