谱聚类是基于无向带权图的聚类方法，通过最小化归一化割（Ncut）将图分割为多个子图。适用于非凸数据集。

聚类思路对比

方法	思路	代表算法
Compactness	类内紧凑	K-means、GMM
Connectivity	图连通性	谱聚类

图定义

无向带权图 $G = (V, E)$ ，权重矩阵 $W$ ，相似度（径向核）：

$w_{ij} = exp (- \frac{∥ x _{i} - x _{j} ∥ ^{2}}{2 σ ^{2}})$

定义 $w (A, B) = \sum_{i \in A, j \in B} w_{ij}$ ，归一化割：

$N c u t = \sum_{k = 1}^{K} \frac{w ( A _{k} , A _{k} )}{\sum _{i \in A_{k}} d _{i}}$

其中 $d_{i} = \sum_{j = 1}^{N} w_{ij}$ 为节点度。

引入指示向量 $Y$ ，目标函数：

$N c u t = T r a ce [(Y^{T} L Y) (Y^{T} D Y)^{- 1}]$

其中：

最小化 Ncut 等价于求拉普拉斯矩阵的最小特征值对应的特征向量，然后用 K-means 聚类。