譜聚類(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í)下圖的概念。對于一個圖$G$，我們一般用點(diǎn)的集合$V$和邊的集合$E$來描述。即為$G(V,E)$。其中$V$即為我們數(shù)據(jù)集里面所有的點(diǎn)$(v_1, v_2,...v_n)$。對于$V$中的任意兩個點(diǎn)，可以有邊連接，也可以沒有邊連接。我們定義權(quán)重$w_{ij}$為點(diǎn)$v_i$和點(diǎn)$v_j$之間的權(quán)重。由于我們是無向圖，所以$w_{ij} = w_{ji}$。

對于有邊連接的兩個點(diǎn)$v_i$和$v_j$，$w_{ij} > 0$,對于沒有邊連接的兩個點(diǎn)$v_i$和$v_j$，$w_{ij}?= 0$。對于圖中的任意一個點(diǎn)$v_i$，它的度$d_i$定義為和它相連的所有邊的權(quán)重之和，即$$d_i = \sum\limits_{j=1}^{n}w_{ij}$$

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

$$\mathbf{D} =

\left( \begin{array}{ccc}

d_1?& \ldots & \ldots \\

\ldots?&?d_2 & \ldots \\

\vdots & \vdots & \ddots \\

\ldots & \ldots & d_n \end{array} \right)$$

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

除此之外，對于點(diǎn)集$V$的的一個子集$A \subset V$，我們定義：$$|A|: = 子集A中點(diǎn)的個數(shù)$$ $$vol(A): = \sum\limits_{i \in A}d_i$$

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

在上一節(jié)我們講到了鄰接矩陣$W$，它是由任意兩點(diǎn)之間的權(quán)重值$w_{ij}$組成的矩陣。通常我們可以自己輸入權(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$的方法有三類。$\epsilon$-鄰近法，K鄰近法和全連接法。

對于$\epsilon$-鄰近法，它設(shè)置了一個距離閾值$\epsilon$，然后用歐式距離$s_{ij}$度量任意兩點(diǎn)$x_i$和$x_j$的距離。即相似矩陣的$s_{ij} = ||x_i-x_j||_2^2$,??然后根據(jù)$s_{ij}$和$\epsilon$的大小關(guān)系，來定義鄰接矩陣$W$如下：

$$w_{ij}=

\begin{cases}

0& {s_{ij} > \epsilon}\\

\epsilon& {{s_{ij}?\leq \epsilon}}

\end{cases}$$

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

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

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

$$w_{ij}=w_{ji}=

\begin{cases}

0& {x_i \notin KNN(x_j) \;and \;x_j \notin KNN(x_i)}\\

exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2})& {x_i \in KNN(x_j)\; or\; x_j \in KNN(x_i})

\end{cases}$$

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

$$w_{ij}=w_{ji}=

\begin{cases}

0& {x_i \notin KNN(x_j) \;or\;x_j \notin KNN(x_i)}\\

exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2})& {x_i \in KNN(x_j)\; and \; x_j \in KNN(x_i})

\end{cases}$$

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

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

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

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

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

1)拉普拉斯矩陣是對稱矩陣，這可以由$D$和$W$都是對稱矩陣而得。

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

3)對于任意的向量$f$,我們有$$f^TLf = \frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_i-f_j)^2$$

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

$$f^TLf = f^TDf - f^TWf = \sum\limits_{i=1}^{n}d_if_i^2 - \sum\limits_{i,j=1}^{n}w_{ij}f_if_j$$ $$=\frac{1}{2}(?\sum\limits_{i=1}^{n}d_if_i^2 - 2?\sum\limits_{i,j=1}^{n}w_{ij}f_if_j + \sum\limits_{j=1}^{n}d_jf_j^2) = \frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_i-f_j)^2?$$

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

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

對于無向圖$G$的切圖，我們的目標(biāo)是將圖$G(V,E)$切成相互沒有連接的k個子圖，每個子圖點(diǎn)的集合為：$A_1,A_2,..A_k$，它們滿足$A_i \cap A_j = \emptyset$,且$A_1 \cup A_2 \cup ... \cup A_k = V$.

對于任意兩個子圖點(diǎn)的集合$A, B \subset V$, $A \cap B = ?\emptyset$, 我們定義A和B之間的切圖權(quán)重為：$$W(A, B) = \sum\limits_{i \in A, j \in B}w_{ij}$$

那么對于我們k個子圖點(diǎn)的集合：$A_1,A_2,..A_k$，我們定義切圖cut為：$$cut(A_1,A_2,...A_k) = \frac{1}{2}\sum\limits_{i=1}^{k}W(A_i, \overline{A}_i?)$$

其中$\overline{A}_i?$為$A_i$的補(bǔ)集，意為除$A_i$子集外其他V的子集的并集。

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

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

6. 譜聚類之切圖聚類

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

6.1 RatioCut切圖

RatioCut切圖為了避免第五節(jié)的最小切圖，對每個切圖，不光考慮最小化$cut(A_1,A_2,...A_k)$，它還同時考慮最大化每個子圖點(diǎn)的個數(shù)，即：$$RatioCut(A_1,A_2,...A_k) = \frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_i, \overline{A}_i?)}{|A_i|}$$

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

我們引入指示向量$h_j \in \{h_1, h_2,..h_k\}\; j =1,2,...k$,對于任意一個向量$h_j$, 它是一個n維向量(n為樣本數(shù))，我們定義$h_{ij}$為：

$$h_{ij}=

\begin{cases}

0& {?v_i \notin A_j}\\

\frac{1}{\sqrt{|A_j|}}& {?v_i \in A_j}

\end{cases}$$

那么我們對于$h_i^TLh_i$,有：

$$ \begin{align} h_i^TLh_i & =?\frac{1}{2}\sum\limits_{m=1}\sum\limits_{n=1}w_{mn}(h_{im}-h_{in})^2 \\& =\frac{1}{2}(\sum\limits_{m \in A_i, n \notin A_i}w_{mn}(\frac{1}{\sqrt{|A_i|}} - 0)^2 + ?\sum\limits_{m \notin A_i, n \in A_i}w_{mn}(0 - \frac{1}{\sqrt{|A_i|}} )^2\\& = \frac{1}{2}(\sum\limits_{m \in A_i, n \notin A_i}w_{mn}\frac{1}{|A_i|} + ?\sum\limits_{m \notin A_i, n \in A_i}w_{mn}\frac{1}{|A_i|}\\& = \frac{1}{2}(cut(A_i, \overline{A}_i) \frac{1}{|A_i|} + cut(\overline{A}_i, A_i) \frac{1}{|A_i|}) \\& = ?\frac{cut(A_i, \overline{A}_i)}{|A_i|} \end{align}$$

上述第(1)式用了上面第四節(jié)的拉普拉斯矩陣的性質(zhì)3. 第二式用到了指示向量的定義。可以看出，對于某一個子圖i，它的RatioCut對應(yīng)于$h_i^TLh_i$,那么我們的k個子圖呢？對應(yīng)的RatioCut函數(shù)表達(dá)式為：$$RatioCut(A_1,A_2,...A_k) = \sum\limits_{i=1}^{k}h_i^TLh_i = \sum\limits_{i=1}^{k}(H^TLH)_{ii} = tr(H^TLH)$$

其中$tr(H^TLH)$為矩陣的跡。也就是說，我們的RatioCut切圖，實(shí)際上就是最小化我們的$tr(H^TLH)$。注意到$H^TH=I$,則我們的切圖優(yōu)化目標(biāo)為:$$\underbrace{arg\;min}_H\; tr(H^TLH) \;\; s.t.\;H^TH=I $$

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

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

對于$h_i^TLh_i$，我們的目標(biāo)是找到最小的L的特征值，而對于$tr(H^TLH) = \sum\limits_{i=1}^{k}h_i^TLh_i$，則我們的目標(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)化，即$$h_{ij}^{*}= \frac{h_{ij}}{(\sum\limits_{t=1}^kh_{it}^{2})^{1/2}}$$

由于我們在使用維度規(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(A_i)$. 由于子圖樣本的個數(shù)多并不一定權(quán)重就大，我們切圖時基于權(quán)重也更合我們的目標(biāo)，因此一般來說Ncut切圖優(yōu)于RatioCut切圖。$$NCut(A_1,A_2,...A_k) = \frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_i, \overline{A}_i?)}{vol(A_i)}$$

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

$$h_{ij}=

\begin{cases}

0& {?v_i \notin A_j}\\

\frac{1}{\sqrt{vol(A_j)}}& {?v_i \in A_j}

\end{cases}$$

那么我們對于$h_i^TLh_i$,有：

$$ \begin{align} h_i^TLh_i & =?\frac{1}{2}\sum\limits_{m=1}\sum\limits_{n=1}w_{mn}(h_{im}-h_{in})^2 \\& =\frac{1}{2}(\sum\limits_{m \in A_i, n \notin A_i}w_{mn}(\frac{1}{\sqrt{vol(A_i)}} - 0)^2 + ?\sum\limits_{m \notin A_i, n \in A_i}w_{mn}(0 - \frac{1}{\sqrt{vol(A_i)}} )^2\\& = \frac{1}{2}(\sum\limits_{m \in A_i, n \notin A_i}w_{mn}\frac{1}{vol(A_i)} + ?\sum\limits_{m \notin A_i, n \in A_i}w_{mn}\frac{1}{vol(A_i)}\\& = \frac{1}{2}(cut(A_i, \overline{A}_i) \frac{1}{vol(A_i)} + cut(\overline{A}_i, A_i) \frac{1}{vol(A_i)}) \\& = ?\frac{cut(A_i, \overline{A}_i)}{vol(A_i)} \end{align}$$

推導(dǎo)方式和RatioCut完全一致。也就是說，我們的優(yōu)化目標(biāo)仍然是$$NCut(A_1,A_2,...A_k) = \sum\limits_{i=1}^{k}h_i^TLh_i = \sum\limits_{i=1}^{k}(H^TLH)_{ii} = tr(H^TLH)$$

但是此時我們的$H^TH \neq I$,而是$H^TDH = I$。推導(dǎo)如下：$$?h_i^TDh_i = \sum\limits_{j=1}^{n}h_{ij}^2d_j =\frac{1}{vol(A_i)}\sum\limits_{j \in A_i}d_j= \frac{1}{vol(A_i)}vol(A_i) =1$$

也就是說，此時我們的優(yōu)化目標(biāo)最終為：$$\underbrace{arg\;min}_H\; tr(H^TLH) \;\; s.t.\;H^TDH=I $$

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

我們令$H = D^{-1/2}F$, 則：$H^TLH = F^TD^{-1/2}LD^{-1/2}F$，$H^TDH=F^TF = I$,也就是說優(yōu)化目標(biāo)變成了: $$\underbrace{arg\;min}_F\; tr(F^TD^{-1/2}LD^{-1/2}F) \;\; s.t.\;F^TF=I $$

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

一般來說， $D^{-1/2}LD^{-1/2}$相當(dāng)于對拉普拉斯矩陣$L$做了一次標(biāo)準(zhǔn)化，即$\frac{L_{ij}}{\sqrt{d_i*d_j}}$

7. 譜聚類算法流程

鋪墊了這么久，終于可以總結(jié)下譜聚類的基本流程了。一般來說，譜聚類主要的注意點(diǎn)為相似矩陣的生成方式(參見第二節(jié))，切圖的方式(參見第六節(jié))以及最后的聚類方法(參見第六節(jié))。

最常用的相似矩陣的生成方式是基于高斯核距離的全連接方式，最常用的切圖方式是Ncut。而到最后常用的聚類方法為K-Means。下面以Ncut總結(jié)譜聚類算法流程。

輸入：樣本集D=$(x_1,x_2,...,x_n)$，相似矩陣的生成方式, 降維后的維度$k_1$, 聚類方法，聚類后的維度$k_2$

輸出： 簇劃分$C(c_1,c_2,...c_{k_2})$.

1) 根據(jù)輸入的相似矩陣的生成方式構(gòu)建樣本的相似矩陣S

2)根據(jù)相似矩陣S構(gòu)建鄰接矩陣W，構(gòu)建度矩陣D

3)計(jì)算出拉普拉斯矩陣L

4)構(gòu)建標(biāo)準(zhǔn)化后的拉普拉斯矩陣$D^{-1/2}LD^{-1/2}$

5)計(jì)算$D^{-1/2}LD^{-1/2}$最小的$k_1$個特征值所各自對應(yīng)的特征向量$f$

6) 將各自對應(yīng)的特征向量$f$組成的矩陣按行標(biāo)準(zhǔn)化，最終組成$n?\times k_1$維的特征矩陣F

7)對F中的每一行作為一個$k_1$維的樣本，共n個樣本，用輸入的聚類方法進(jìn)行聚類，聚類維數(shù)為$k_2$。

8)得到簇劃分$C(c_1,c_2,...c_{k_2})$.

8. 譜聚類算法總結(jié)

譜聚類算法是一個使用起來簡單，但是講清楚卻不是那么容易的算法，它需要你有一定的數(shù)學(xué)基礎(chǔ)。如果你掌握了譜聚類，相信你會對矩陣分析，圖論有更深入的理解。同時對降維里的主成分分析也會加深理解。

下面總結(jié)下譜聚類算法的優(yōu)缺點(diǎn)。

譜聚類算法的主要優(yōu)點(diǎn)有：

1)譜聚類只需要數(shù)據(jù)之間的相似度矩陣，因此對于處理稀疏數(shù)據(jù)的聚類很有效。這點(diǎn)傳統(tǒng)聚類算法比如K-Means很難做到

2)由于使用了降維，因此在處理高維數(shù)據(jù)聚類時的復(fù)雜度比傳統(tǒng)聚類算法好。

譜聚類算法的主要缺點(diǎn)有：

1)如果最終聚類的維度非常高，則由于降維的幅度不夠，譜聚類的運(yùn)行速度和最后的聚類效果均不好。

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

(歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處。歡迎溝通交流： liujianping-ok@163.com)

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的python谱聚类算法_谱聚类（spectral clustering）原理总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。