谱聚类

基本算法

1. 计算拉普拉斯矩阵 ${\displaystyle L}$  （或归一化的拉普拉斯矩阵）
2. 计算前 ${\displaystyle k}$  个特征向量（这些特征向量对应 ${\displaystyle L}$  的 ${\displaystyle k}$  个最小的特征值）
3. 考虑由这 ${\displaystyle k}$  个特征向量组成的矩阵，矩阵的第 ${\displaystyle l}$  行定义了图节点 ${\displaystyle l}$  的特征
4. 根据这些特征对图节点进行聚类（例如使用k-均值聚类）

大型图的（归一化）拉普拉斯矩阵通常是病态的（ill-conditioned，即高条件数），这会减缓迭代求解的收敛速度。预处理（英语：Preconditioner#Preconditioning_for_eigenvalue_problems）（Preconditioning）可以加速收敛。通过首先确定结构，然后对群落进行聚类，谱聚类可以成功应用于大型图。^[1]

谱聚类与非线性降维密切相关，局部线性嵌入（Locally-linear embedding）等降维技术可用于减少噪声或异常值的误差。^[2]

有不少大型开源项目实现谱聚类，包括Scikit-learn^[3]（使用带有多网格预处理（multigrid method）或ARPACK的LOBPCG算法），MLlib（使用幂迭代法，Power iteration method）进行伪特征向量聚类^[4]，以及R^[5]。

谱聚类算法它可以在核聚类方法的背景下进行描述，这显示了它与其他方法的相似之处。^[6]

和k-means聚类算法的关系

加权核K-means问题与谱聚类问题的目标函数相同，可以通过多级方法直接优化。