图的谱聚类 基本概念 谱聚类是一种基于图论和线性代数的聚类方法，它将数据点视为图中的顶点，并根据顶点之间的相似性构建边。具体来说，给定一组数据点，首先构建一个相似图，其中每个顶点代表一个数据点，边权重表示点对之间的相似度（例如，使用高斯核函数计算）。谱聚类的核心思想是将聚类问题转化为图的划分问题，通过分析图的拉普拉斯矩阵的特征向量来实现数据分割。 图的拉普拉斯矩阵 图的拉普拉斯矩阵是谱聚类的关键工具。对于无向图 \( G \)，其拉普拉斯矩阵 \( L \) 定义为： \[ L = D - A \] 其中 \( A \) 是邻接矩阵（存储边权重），\( D \) 是对角度矩阵（\( D_ {ii} = \sum_ j A_ {ij} \)）。拉普拉斯矩阵具有以下性质： 特征值非负，最小特征值为0，对应特征向量为全1向量。 特征值的个数等于图中连通分量的数量，第二个特征值（谱间隙）反映图的连通性。 归一化拉普拉斯矩阵 为提高数值稳定性，常使用归一化拉普拉斯矩阵。两种常见形式为： 对称归一化：\( L_ {\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2} \) 随机游走归一化：\( L_ {\text{rw}} = D^{-1} L = I - D^{-1} A \) 归一化拉普拉斯矩阵的特征值范围在[ 0,2 ]之间，便于处理不同密度的图。 特征向量与低维嵌入 谱聚类的核心步骤是计算拉普拉斯矩阵的前 \( k \) 个最小特征值对应的特征向量（\( k \) 为聚类数）。这些特征向量构成一个新的低维空间，每个原始数据点映射为该空间中的一个点。这一过程保留了图的全局结构，使得原本在原始空间中复杂的数据分布变得线性可分。 聚类步骤 谱聚类的具体流程如下： 构建相似图：使用最近邻或全连接法确定边，并计算权重。 计算拉普拉斯矩阵（通常用归一化形式）。 求解前 \( k \) 个最小特征值对应的特征向量，形成特征向量矩阵 \( U \in \mathbb{R}^{n \times k} \)。 对 \( U \) 的每一行进行归一化，得到新样本点。 应用传统聚类算法（如K-means）对这些新点进行聚类。 优势与局限性 谱聚类的优势在于能处理非凸分布数据，且对初始聚类中心不敏感。但其计算成本较高（需特征分解），且相似图构建对参数敏感。后续改进包括稀疏化拉普拉斯矩阵和近似特征值计算。