譜聚類 Spectral Clustering

作者：由 Elfsong 發表于攝影時間：2021-10-07

最近記憶力感覺很差，很多以前常用的演算法都記不清楚了。正好現在坡縣一天病例新增3千多例，我在家也沒什麼事情做，所以打算用文章的方式鞏固一下自己的記憶。另外，讓我來吐槽一下知乎的公式編輯器真難用～

譜聚類是一種非常高效簡單的演算法。雖然名字聽上去比較炫酷，但只要靜下心來認真看看，其實原理非常容易理解。

1 譜聚類是什麼？

我們就不一上來搞一大堆高大上的定義了。其實譜聚類的思想非常樸實，就是把需要分類的點看作一個圖

$G\in(V, E)$

。其中距離較近的結點有較高的邊權，距離較遠的結點有較低的邊權（對於距離的定義會在下文中進行解釋）。類似於最小割問題，我們希望對圖進行分割（分類）操作之後，不同子圖間的邊權儘可能小，相同子圖內的邊權儘可能高。

在切圖的過程中，我們會發現最小割方案存在無法找到最優切圖方案的問題。於是在譜聚類中我們透過修改最佳化目標解決了這個問題。

最後，譜聚類透過大幅度降維使得NP-hard可以被近似求解。我覺得這一點是譜聚類的核心之所在。對於K-means這類空域上的演算法，我們需要考慮樣本間的每一個維度，這樣會給我們帶來不小（甚至不可在多項式時間內求解）的開銷。但如果我們可以換一個視角去思考這個問題，為所有樣本向量找到一組正交基（單位向量），或者不嚴謹地說，找到一組座標系。基於這個座標系，我們可以找到對於樣本向量貢獻最大的

個座標軸。這樣我們就可以使用這組座標軸來表示這些樣本了。如果你熟悉PCA或者傅立葉變換，相信你可以很自然的理解譜聚類的思路。

所以我們在下文中會先介紹一下有關的前置概念，最後引出介紹譜聚類演算法。

2 圖的定義

對於一個圖

$G\in(V,E)$

，

代表圖中的節點（Vertex），

表示圖中的邊（Edge）。

此外，我們定義

$W_{ij}$

為節點

$V_{i}$

到節點

$V_{j}$

之間的距離。如果兩個節點之間有連線，則

$W_{ij} > 0$

，否則

$W_{ij} = 0$

。

對於圖中的任意一個點

，它的度

定義為和它相連的所有邊的權重之和：

$d_{i} = \sum_{j \in Neighbors}{w_{ij}} \\$

將每一個點的

整合起來，我們可以得到

$n \times n$

的度矩陣

。它是一個對角矩陣，只有主對角線有值：

$D = \left ( \begin{matrix} d_1 & \cdots & \cdots \\ \cdots & d_2 & \cdots \\ \vdots & \ddots & \vdots \\ \cdots & \cdots & d_3 \\ \end{matrix} \right ) \\$

3 相似矩陣

在圖的定義中我們使用

$W_{ij}$

作為兩個節點距離的表示。但對於絕大多數分類問題而言，我們只有資料點的定義，沒有點之間距離的定義。所以我們需要自己來定義點之間的距離。距離的定義有很多種，實踐中最常使用的是全連結法，我們可以使用不同的核函式來定義權重（內積的對映）：

$_{ } = (\frac{−|| _{ }− _{ }||^2}{2 ^2}) \\$

拉普拉斯矩陣

簡單來說，圖

$G\in(V,E)$

的拉普拉斯矩陣可以定義為

。

其中，D為第二節圖的定義中的度矩陣，A為鄰接矩陣（在全連結法中，

）。

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

1）拉普拉斯矩陣是對稱矩陣（因為

和

都是對稱矩陣）。

2）由於拉普拉斯矩陣是對稱矩陣，則它的所有的特徵值都是實數。

3）對於任意的向量

，我們有：

$f^T L f = \frac{1}{2} \sum_{i,j=1}^{n}{w_{ij} (f_i - f_j)^2} \\$

4）拉普拉斯矩陣是半正定矩陣，且對應的n個實數特徵值都大於等於0，即：

$0 = \lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n \\$

Laplacians是譜聚類的核心知識點，如果有不清楚的朋友可以看看這篇文章：

5 無向圖切圖

對於無向圖的切圖，我們的目標是將圖

$G \in (V, E)$

切成相互沒有連線的

個子圖。嚴謹地說，每個子圖點的集合為：

它們滿足

$A_i \cap A_j = \varnothing$

且

$A_1 \cup A_2 \cup ... \cup A_k = V$

。

對於含有

兩個子圖點

的集合

$V \in (A, B)$

，我們可以定義A和B之間的切圖權重為：

$W(A, B) = \sum_{i \in A, j \in B}{w_{ij}} \\$

那麼對於我們

個子圖點的集合

，我們定義切圖為：

$cut(A_1, A_2, ... , A_k) = \frac{1}{2} \sum_{k}^{i=1}{W(A_i, \bar{A_i})} \\$

其中

$\bar{A_i}$

為

的補集，意為除

之外其他V的子集的並集。

那麼如何切圖可以讓子圖內的點權重和高，子圖間的點權重和低呢？一個自然的想法就是最小化

，但是可以發現，這種極小化的切圖存在問題，如下圖：

Smallest cut切斷了

與

的連線，達到了最小化

的目的，但並沒有找到Best cut的位置。

6 切圖聚類

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

6。1 RatioCut 切圖

為了避免出現Smallest切圖類別分佈不均勻的問題，Ratio Cut不僅考慮最小化

，它同時還會考慮最大化每個子圖的節點個數：

$cut(A_1, A_2, ... , A_k) = \frac{1}{2} \sum_{k}^{i=1}{\frac {W(A_i, \bar{A_i})} {|A_i|}} \\$

將圖的節點

分成

個分割槽，我們定義指示向量：

$h_j = \{ h_{1,j}, h_{2,j}, ... , h_{n,j} \}$

，其中：

$h_{i, j} = \begin{equation} \left\{ \begin{array}{**lr**} \frac{1}{\sqrt{|A_j|}}, & v_i \in A_j \\ 0, & otherwise \\ \end{array} \right. \end{equation} \\$

對於

我們有：

$h_i^T L h_i = \frac{1}{2} \sum_{m=1}^{N} \sum_{n=1}^{N} w_{mn}(h_{im} - h_{in})^2 \\ = \frac{1}{2} \sum_{m \in A_i; n \notin A_i} w_{mn}(\frac{1}{\sqrt{|A_i|}} - 0)^2 + \frac{1}{2} \sum_{m \notin A_i; n \in A_i} w_{mn}(0 - \frac{1}{\sqrt{|A_i|}})^2 \\ = \frac{1}{2} (\sum_{m \in A_i; n \notin A_i} w_{mn} \frac{1}{|A_i|} + \sum_{m \notin A_i; n \in A_i} w_{mn} \frac{1}{|A_i|}) \\ = \frac{1}{2} (cut(A_i, \bar{A_i}) \frac{1}{|A_i|} + cut( \bar{A_i}, A_i) \frac{1}{|A_i|}) \\ = \frac{cut(A_i, \bar{A_i})}{|A_i|} \\$

對於某一個分類子圖

，它的RatioCut對應於

，那麼完整的

個子圖呢？對應的RatioCut函式表示式為：

$RatioCut(A_1, A_2, ... , A_k) = \sum_{i=1}^{K}{h_i^T L h_i} = \sum_{i=1}^{K}{(H^T L H)_{ii}} = tr(H^T L H) \\$

其中

為矩陣的跡。我們可以發現切圖問題已經轉化為了求解最小化

的問題。同時，考慮到

的含義（特徵向量），我們需要保證

：

$argmin(tr(H^T L H)) \\ s.t. H^T H = I$

H中每一個指示向量（特徵向量）都是n維的，向量中每一個變數的取值為

$(0, \frac{1}{\sqrt{|A_i|}})$

。全部K個指示向量共有

$K \times 2^N$

種可能的取值，因此這是一個NP-hard問題。

對於

，我們的目標是找到最小的

的特徵值；而對於

，我們的目標是找的

個最小的特徵值。一般來說，

$K \ll N$

，當這個問題的維度從

被規約到

之後，我們就可以近似的解決這個NP-hard的問題了。

透過找到

最小的

個特徵值，我們可以得到對應的

個特徵向量，這些向量組成了

矩陣。通常我們會對矩陣

進行標準化：

$h_{ij}^* = \frac{h_{ij}}{\sqrt{\sum_{K}^{t=1}{h_{it}^2}}} \\$

由於我們在使用維度規約的時候損失了少量資訊，導致得到的最佳化後的指示向量不能完全指示各樣本的歸屬，因此一般在得到

$N \times K$

維度的矩陣

後還需要對每一行進行一次傳統的聚類，比如使用K-Means聚類。

6。2 NormalizedCut 切圖

NormalizedCut對RatioCut進行了改進。考慮到子圖樣本的個數多並不一定權重就大，在切圖時我們也應該考慮子圖間的權重大小。和RatioCut類似，NormalizedCut採用了：

$NormalizeCut(A_1, A_2, ... , A_k) = \frac{1}{2} \sum_{k}^{i=1}{\frac {W(A_i, \bar{A_i})} {vol(A_i)}} \\$

其中，

$vol(A_i) = \sum_{i \in A} {d_i}$

。

除此之外，NormalizedCut和RatioCut幾乎完全一樣。由於在NormalizedCut中，

$H^T H \ne I$

，我們需要對矩陣

做一個變換，使之標為標準正交基：

$H = D^{-\frac{1}{2}}$

。推導如下：

$H^T D H = \sum_{i=1}^{K}{ h_{ij}^2 d_j} = h_{ij}^2 \sum_{i=1}^{K}{ d_j } = \frac{1}{vol(A_i)} \sum_{i=1}^{K}{ d_j } = \frac{1}{vol(A_i)} vol(A_i) = 1 \\$