为什么谱聚类比K均值更能处理非凸簇：图划分视角

当数据中的集群形状不规则，比如是环形、月牙形或者缠绕在一起时，传统的聚类方法往往失效。本指南将从一个核心视角出发，揭示谱聚类为何能成功处理这些“非凸簇”，并给出实现其优势的关键思想。

1. 理解核心问题：几何假设的局限

所有聚类方法都基于某种数据结构的假设。

1. 剖析 K均值的几何直觉

   • 默认数据点围绕着一些“中心点”（质心）分布。
   • 通过计算每个点到各质心的欧几里得距离，将其分配给最近的质心，然后更新质心位置，如此迭代。
   • 关键限制：这个过程等价于用线性超平面（或圆、球）划分空间。因此，它能完美处理球形、凸形的簇。对于非凸形状（例如，一个数据点集形成一个圆环），同一个环会被强制分割成多个“凸”部分，导致结果完全错误。

2. 洞察非凸簇的本质

   • 想象数据点被画在图上，同一个非凸簇内的点，虽然它们到某个中心点的距离可能很远，但彼此之间通过一条“路径”紧密相连，这条路径上的所有点都属于同一个簇。
   • 因此，对于非凸簇，描述其内部结构的关键不是“距离中心的几何距离”，而是数据点之间的连通性和内在的相似性图结构。

2. 谱聚类的破局之道：从数据点到图

谱聚类的第一步，就是彻底抛弃原始空间中的几何中心概念，转而构建一张描述数据点亲近关系的图。

1. 构建相似性图

   • 将每个数据点视为图中的一个节点。
   • 定义节点间的相似性。最常见的是使用高斯核（径向基函数）：s(i, j) = exp(-||x_i - x_j||^2 / (2σ^2))。这个公式计算了两点距离的衰减值：距离越近，相似度 s(i, j) 越接近 1；距离越远，越接近 0。σ 是一个控制“亲近”范围的参数。
   • 连接节点：如果 s(i, j) 大于某个阈值，就在节点 i 和 j 之间连一条边，边的权重就是相似度 s(i, j)。这样，就得到了一个带权无向图 G=(V, E, W)。

2. 图划分：聚类的新目标

   • 在这个新视角下，聚类问题转化为：找到一种划分，将图 G 的顶点集 V 分成 k 个子集 A1, A2, ..., Ak。
   • 理想目标：让组内连接（即 Ai 内部的边）的权重之和尽量大，而组间连接（即 Ai 和 Aj 之间的边，i ≠ j）的权重之和尽量小。

3. 图割目标与图拉普拉斯矩阵

为了实现上述目标并使其可计算，我们需要引入核心的数学工具：图拉普拉斯矩阵。

1. 最小割的朴素想法与缺陷

   • 定义一个简单的切割目标：最小化组间连接的总权重，即 Cut(A1, A2, ..., Ak) = Σ_{i<j} W(Ai, Aj)。
   • 问题：这个目标倾向于产生非常不平衡的划分，例如，将一个孤点与其余所有点分开，这样切割的边很少，但结果毫无意义。

2. 归一化割与比例割

   • 优化目标，加入平衡约束。常用的有：
     • 归一化割 (Normalized Cut)：NCut(A1, ..., Ak) = Σ_{i=1}^k [Cut(Ai, V\Ai) / Vol(Ai)]。其中 Vol(Ai) 是子集 Ai 中所有节点连接的边权重之和（度数之和）。这鼓励每个划分具有相似的规模（按连接强度衡量）。
     • 比例割 (Ratio Cut)：RCut(A1, ..., Ak) = Σ_{i=1}^k [Cut(Ai, V\Ai) / |Ai|]。这鼓励每个划分包含相似数量的节点。

3. 图拉普拉斯矩阵：连接划分与代数

   • 构造度数矩阵 D：一个对角矩阵，D_ii 等于节点 i 的所有边权重之和（度）。
   • 构造权重矩阵 W：W_ij 是节点 i 和 j 之间的边权重。
   • 定义未归一化的拉普拉斯矩阵 L = D - W。
   • 定义归一化的拉普拉斯矩阵 L_{norm} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}。
   • 核心定理：最小化归一化割或比例割问题，在数学上等价于求解拉普拉斯矩阵 L 或 L_{norm} 的特征向量问题。特别是，对于 k 个簇，我们寻找其前 k 个最小的特征值（除了第一个恒为0的特征值）对应的特征向量。

4. 谱聚类的标准算法步骤

基于上述理论，一个标准的谱聚类流程如下：

1. 输入：数据点集 X，簇数量 k。
2. 构建相似性矩阵：计算所有点对之间的相似度 s(i, j)，形成 n x n 的相似性矩阵 S（即权重矩阵 W）。
3. 计算图拉普拉斯矩阵：计算度数矩阵 D（D_ii = Σ_j S_ij），然后计算归一化拉普拉斯矩阵 L_{norm} = I - D^{-1/2} S D^{-1/2}。
4. 计算特征向量：计算 L_{norm} 的前 k 个最小的特征值对应的特征向量 u_1, u_2, ..., u_k。（这一步是计算的核心，也是“谱”这个名字的由来）。
5. 构建特征矩阵：将这 k 个特征向量按列排列，形成一个 n x k 的矩阵 U。U 的每一行是原数据点在新的 k 维空间中的表示。
6. 进行K均值聚类：将 U 的每一行看作 k 维空间中的一个点，对这些新点运行标准的 K均值算法，得到 k 个簇的划分。
7. 输出：返回原始数据点的聚类标签。

5. 视角对比与本质结论

通过这个图划分的视角，谱聚类与 K均值的根本区别变得清晰。

1. K均值：原始空间的几何划分者

   • 操作空间：原始的 d 维特征空间。
   • 核心假设：簇是凸的、球状的，质心能代表簇。
   • 划分依据：点到质心的欧几里得距离。
   • 失败场景：当簇的形状非凸，或不同簇在原始空间中纠缠在一起时，线性划分无法将其分离。

2. 谱聚类：相似性图上的结构探索者

   • 操作空间：由数据点相似性关系构成的图。
   • 核心假设：簇是图中的连接紧密的子图（社区）。
   • 划分依据：图割（如归一化割），即最大化组内连接紧密度与组间连接稀疏度之比。
   • 成功关键：
     • 维度提升：通过特征向量，将数据点从原始空间映射到一个新的“谱空间”。在这个新空间中，原本在原始空间中分离不开的非凸簇，变得线性可分。
     • 捕获全局结构：图的构建（尤其是使用高斯核）考虑了所有点对之间的关系，而非仅仅是局部质心。拉普拉斯矩阵的特征向量编码了数据图的整体连通性信息，使得算法能够“看到”并分离出长程连接的、非凸的簇结构。

因此，谱聚类之所以能处理非凸簇，是因为它彻底改变了问题的分析框架：从计算几何距离，转向分析图的拓扑结构，并通过巧妙的代数方法（求解拉普拉斯矩阵的特征向量）找到图的最佳划分，从而揭示出隐藏在复杂连接关系中的数据内在聚类结构。