谱聚类详解：求L次小特征值与图划分

"求L次小特征值所对应的特征向量-谱聚类详细、入门级介绍" 谱聚类是一种在机器学习和数据挖掘领域广泛应用的聚类方法，它基于图论理论，通过分析数据集构建的图的特征值和特征向量来进行聚类。这种方法的核心是利用拉普拉斯矩阵的谱分解，找到数据内在结构的关键信息。 1. **谱聚类算法** 谱聚类算法首先将数据集表示为图的形式，其中节点代表数据样本，边的权重表示样本之间的相似度。通常，这个图可以是有向或无向的，无向图更常见，因为它们能更好地反映对称的相似性关系。 2. **图的表示** 在图论中，图G由顶点集V和边集E组成，边集E描述了顶点之间的关系。如果两个顶点之间存在边，则它们之间有某种关系，如相似度。边的权重wij表示顶点vi和vj之间的关系强度。对于无向图，wij = wji，表示相互的关系。 3. **拉普拉斯矩阵** 拉普拉斯矩阵是图的一个重要矩阵表示，它反映了图的结构信息。对于无向图，有两类拉普拉斯矩阵：非归一化拉普拉斯矩阵L = D - W和归一化拉普拉斯矩阵L' = D^(-1/2)WD^(-1/2)，其中D是对角矩阵，其对角元素是各节点的度（即与其相连的边的权重之和）。 4. **特征值和特征向量** 拉普拉斯矩阵的特征值和特征向量是谱聚类的关键。特征值λi和对应的特征向量qi揭示了图的结构特性。在聚类问题中，我们通常关注前L个最小的非零特征值及其特征向量，这些向量可以作为数据降维后的表示，进而用于聚类。 5. **瑞利商和最小割（Minimum Cut）** 瑞利商是衡量图中子图分割质量的一个指标，其最小值出现在最小特征值对应的特征向量中。在谱聚类中，最小割方法寻找的是最优的图划分，使得分割后的子图内部连接紧密，而子图间连接稀疏。这可以通过最小化损失函数Cut来实现，Cut值等于被割断的边的权重之和。 6. **图的划分** 图划分的目标是将图分割成多个子图，每个子图内的点相似度高，而子图间的点相似度低。一个好的划分应使子图间的连接权重和尽可能小，即损失函数Cut取值较小。 7. **优化过程** 谱聚类的优化过程通常涉及到特征值的计算和特征向量的选择。通过对拉普拉斯矩阵进行特征分解，我们可以得到特征值和特征向量，然后选取最小的L个特征向量进行聚类，例如使用K-means或其他聚类算法。 8. **实际应用** 谱聚类广泛应用于社区检测、图像分割、社交网络分析等领域，它能够处理非凸形状的聚类，并且对噪声和异常值有一定的鲁棒性。 总结来说，谱聚类通过分析图的拉普拉斯矩阵的特征结构，能够有效地捕捉数据的内在聚类信息，为复杂数据集的聚类提供了一种强大而灵活的方法。在实际应用中，根据数据特性和需求，选择合适的拉普拉斯矩阵类型和特征向量数量，可以优化聚类效果。