谱聚类 (Spectral Clustering)

定义

谱聚类(Spectral Clustering)是把聚类问题转化为图划分问题的算法:将样本看作图的顶点,以相似度作为边权,寻找一个使"簇间连接弱、簇内连接强"的切分。

原理

直接求最优图切分(如归一化割 Normalized Cut)是 NP 难问题,谱聚类将其松弛为特征值问题:构造相似度矩阵与度矩阵,得到图拉普拉斯矩阵(Laplacian),取其最小的 k 个特征值对应的特征向量组成低维嵌入,再在嵌入空间中用 K-means 完成最终聚类。代表性工作包括 Shi-Malik 的归一化割(2000)与 Ng-Jordan-Weiss 算法(2001)。

优点

不假设簇为凸形,能正确分离环形、月牙形等复杂结构;理论根基清晰,与图论、流形学习联系紧密。

局限

需要构建并分解 n×n 相似度矩阵,大规模数据代价高;结果对相似度图的构建方式(近邻数、带宽参数)较敏感。

应用

常见于图像分割、社交网络社区发现。