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

聚类思路对比

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

图定义

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

$$w_{ij}=\exp\left(-\frac{|x_i-x_j|^2}{2\sigma^2}\right)$$

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

$$Ncut=\sum_{k=1}^K\frac{w(A_k,\overline{A_k})}{\sum_{i\in A_k}d_i}$$

其中 $d_i=\sum_{j=1}^Nw_{ij}$ 为节点度。

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

$$Ncut=Trace[(Y^TLY)(Y^TDY)^{-1}]$$

其中：

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