Overview

Spectral Clustering Algorithoms（譜聚類算法）的三個基本階段：

1. Pre-processing（預處理）
   構(gòu)建圖的矩陣表示
2. Decomposition（分解）
   • 計算矩陣的特征值和特征向量
   • 基于一或多個特征向量將每個點映射到較低維的表示形式
3. Grouping（分組）
   • 基于新的表示將所有點劃分為2個或多個集群

Graph Patitioning

問題定義

給定無向圖，將圖中的節(jié)點劃分到兩個不相交的集群中。接下來要考慮的問題在于：

• 如何定義當前劃分方式的好壞？
• 如何高效地識別這樣的分區(qū)？

Graph Cut Criterion

首先需要明確的是，一個好的分區(qū)，其特點在于：

• 最大化分區(qū)內(nèi)部的連接數(shù)量；
• 最小化分區(qū)與分區(qū)之間的連接數(shù)量。

接下來，將以一個與分區(qū)的“edge cut”相關的方程來表達分區(qū)目標，其中Cut為那些兩個端點位于不同分區(qū)的邊的集合，即 w_{ij}，若圖中沒有權重表示，則。
由此，Graph Cut Criterion可定義為最小化cut的值，即，但考慮如下圖所示的情況，紅線標注的cut滿足最小化的情況，但這并不是我們期望的切分方式，因此還需要添加對集群內(nèi)的連接盡可能多的考慮。

cut criterion degenerate case

為了產(chǎn)生更加平衡的分區(qū)，[Shi-Malik, ’97]提出了新的分區(qū)評判標準Conductance，它定義了相對于分區(qū)密度的連通情況，即：

其中代表volume，表示分區(qū)A中所有節(jié)點的加權度數(shù)（degree）之和，即?？梢钥吹疆敺帜钢袃蓚€分區(qū)的volume盡可能相等時，該式的值趨向于最大。但此時伴隨而來的問題是想要計算得到一個最佳的conductance cut是一個NP-hard問題。而接下來要學習的Spectral Graph Partitioning可以實現(xiàn)優(yōu)化上述標準的近似保證。

Spectral Graph Partitioning

Basic Knowledge

• 設為無向圖的鄰接矩陣，為中每一個節(jié)點的標簽/值，則計算的是圖中每個節(jié)點各自鄰居的標簽之和，即。對于等式，其中稱為特征向量（eigenvector），對應的稱為特征值（eigenvalue）。
• Spectrum：對于圖的任一特征向量，設其對應的特征值為，則將譜（spectrum）定義，其中。
• 例1：設為一個所有節(jié)點的度數(shù)均為的連通圖（稱為d-regular graph），當特征向量時，求得，此時為的鄰接矩陣的最大特征值，即。
• 例2：若不是連通圖，設有兩個互不相連的連通子圖和組成，每一個子圖均是d-regular。若令特征向量中的節(jié)點的值為1，中所有節(jié)點值均為0，對應特征值，反之亦然，則此時有。
• 例3：在例二的基礎上，若和之間存在部分連接，已知特征向量，由于實對稱陣屬于不同特征值的的特征向量是正交的，所以有。
• Laplacian matrix ：定義，其中為對角矩陣，主對角線元素為各節(jié)點的度數(shù)。Laplacian矩陣具有以下屬性：
  1. 對于特征向量，特征值；
  2. 所有特征值均為非負實數(shù)；
  3. 所有特征向量為實數(shù)且彼此正交。
• 對于對稱矩陣，有，已知為對應的特征向量。其中最小化的意義在于：
  
  由此對于Laplacian矩陣，上述公式可寫為，此時為單位向量且與正交。由于為單位向量，最小化該式意味著最小化分子，又因為，所以求解的特征向量中有正有負，理想結(jié)果將如下圖所示（使盡可能少的邊經(jīng)過坐標軸上0的位置）：
  
  Finding x that minimize lambda

Find Optimal Cut

[Fiedler '73]提出了一種尋找最佳切分點的方案，將分區(qū)表示為一個向量，若某節(jié)點，則對應，反之，。分區(qū)期望實現(xiàn)，即，當前向量同樣與正交。接下來將通過下式尋找最小化分區(qū)cut的分區(qū)方案：

若將的取值擴大到實數(shù)范圍，則有：

此時Laplacian矩陣的第二小特征值由得到；對應的特征向量由得到，這里的又稱為Fiedler vector。此時就可以利用的正負來決定節(jié)點屬于哪一個分區(qū)。上述過程稱為spectual clustering。

該過程對應開始的Spectral Clustering Algorithoms（譜聚類算法）的三個基本階段：

1. Pre-processing：構(gòu)建圖的Laplacian矩陣；
2. Decomposition：尋找矩陣的特征值和特征向量；對節(jié)點與特征向量進行映射；
3. Grouping：對各元素進行排序，尋找合適的位置進行切分并對相應節(jié)點進行分區(qū)。