图的谱聚类 图的谱聚类是一种基于图论和线性代数的数据聚类方法。它将数据点视为图的顶点，根据数据点之间的相似性构建图，然后利用图的拉普拉斯矩阵的特征向量对数据进行聚类。 1. 相似性图构建 谱聚类的第一步是将数据转化为图结构。给定一组数据点，我们需要构建一个加权无向图 G=(V,E,W)，其中： 顶点集 V 对应每个数据点。 边集 E 表示点之间的连接关系。 权重矩阵 W 是一个对称矩阵，Wᵢⱼ 表示顶点 i 和 j 之间边的权重，通常由相似性函数计算得出。常用的构图方法有： ε-邻域图 ：仅当两点间的距离小于阈值 ε 时才连接，权重为1或距离函数值。 k-最近邻图 ：每个点只与其k个最近邻点连接，可以是相互k近邻或单向k近邻。 全连接图 ：所有点两两相连，权重由高斯核函数等相似性函数计算，如 Wᵢⱼ = exp(-||xᵢ - xⱼ||² / 2σ²)。 2. 图的拉普拉斯矩阵 拉普拉斯矩阵是谱聚类的核心工具，主要有三种形式： 非规范拉普拉斯矩阵 ：L = D - W，其中 D 是度矩阵（对角矩阵，Dᵢᵢ = Σⱼ Wᵢⱼ）。 规范拉普拉斯矩阵（对称型） ：Lₛyₘ = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}。 规范拉普拉斯矩阵（随机游走型） ：Lᵣw = D^{-1} L = I - D^{-1} W。 这些矩阵都是半正定的，其特征值提供了图的结构信息，如连通分量数目。 3. 特征值与特征向量计算 对选定的拉普拉斯矩阵进行特征分解，计算其前k个最小特征值对应的特征向量（忽略零特征值）。例如，若要将数据分为k类，则取前k个最小特征值对应的特征向量，组成矩阵 U ∈ R^{n×k}，其中每一行对应一个数据点在新的特征空间中的坐标。 4. 特征向量空间聚类 将原数据点投影到由特征向量张成的低维空间后，传统的聚类算法（如k-means）被应用于新坐标点。由于特征向量突出了数据的聚类结构，即使原数据在原始空间中非线性可分，在新空间中也可能变得线性可分。 5. 谱聚类优势与应用 谱聚类能处理非凸形状的簇，对噪声相对鲁棒，适用于图像分割、社交网络社区发现等。其效果依赖于相似性图的质量和参数（如高斯核的σ），且计算特征分解对于大规模图可能较昂贵。