谱聚类

在多元变量统计中，谱聚类（）技术利用数据相似矩阵的谱（特征值），在对数据进行降维后，以较少的维度进行聚类。相似矩阵作为输入，提供了对数据集中每一对点相对相似性的定量评估。

在图像分割中，谱聚类被称为基于分割的物体分类。

 算法 

 基本算法

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

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

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

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

 和其它聚类算法的关系 
谱聚类算法它可以在核聚类方法的背景下进行描述，这顯示了它与其他方法的相似之处。

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

 参考资料 

Category:代数图论
Category:聚类分析