谱聚类（Spectral Clustering）

谱聚类 (Spectral Clustering) 是一种基于图论 (Graph Theory) 的聚类算法。与传统的 K-Means 不同，它不假设数据服从某种凸形（如球形）分布，而是通过分析数据的连通性来进行聚类。简单来说，谱聚类的核心思想是：将聚类问题转化为图的切割问题，并通过线性代数中的特征分解 (Eigen-decomposition) 来求解，从而实现聚类。

本文会从直观理解、数学原理、算法步骤和优缺点分析四个部分来简单介绍谱聚类。

---

1. 直观理解：从“距离”到“连通性”

• 传统聚类 (如 K-Means): 基于欧氏距离。它倾向于发现“球状”的簇。如果你有两个同心圆（一个大圆包着一个小圆），K-Means 通常会像切饼一样把它们切开，无法正确区分内外圆。
• 谱聚类: 基于连通性。它把数据看作图中的节点。如果两个点离得很近，它们之间就有一条强权重的边。
  • 对于同心圆数据，谱聚类会发现：内圆上的点彼此连接紧密，外圆上的点彼此连接紧密，但内圆和外圆之间的连接很弱。
  • 因此，它能轻易地将复杂的非凸形状（如螺旋、圆环）分开。

---

2. 数学基石：图与矩阵

谱聚类的理论基础主要涉及三个矩阵：邻接矩阵 (Adjacency Matrix)、度矩阵 (Degree Matrix) 和 拉普拉斯矩阵 (Laplacian Matrix)。

假设我们有 $n$ 个数据点 $x_1, ..., x_n$。

A. 构建相似图 (Similarity Graph) & 邻接矩阵 $W$

我们需要构建一个无向加权图 $G=(V, E)$。

• $V$ (顶点): 每个数据点是一个顶点。
• $E$ (边): 顶点之间的连线，权重 $w_{ij}$ 表示点 $i$ 和点 $j$ 的相似度。
• $W$ (邻接矩阵): 一个 $n \times n$ 的对称矩阵，其中元素 $W_{ij} = w_{ij}$。

常用的相似度计算方法是 高斯核函数 (RBF Kernel)：

$$w_{ij} = \exp\left(-\frac{||x_i - x_j||^2}{2\sigma^2}\right)$$

(注：如果距离越近，权重越接近 1；距离越远，权重越接近 0。)

B. 度矩阵 $D$ (Degree Matrix)

这是一个对角矩阵。对角线上的元素 $d_{ii}$ 是该节点所有连接边的权重之和：

$$d_{ii} = \sum_{j=1}^{n} w_{ij}$$

它代表了该点与其他点的连接紧密程度。

C. 拉普拉斯矩阵 $L$ (Laplacian Matrix)

这是谱聚类的核心。最简单的未归一化拉普拉斯矩阵定义为：

$$L = D - W$$

拉普拉斯矩阵的重要性质：

1. 半正定性: 对任意向量 $f$，有 $f^T L f \ge 0$。
2. 特征值: 最小的特征值为 0，对应的特征向量是全 1 向量。
3. 连通分量: 如果图由 $k$ 个互不相连的子图（即理想的簇）组成，那么 $L$ 将有 $k$ 个为 0 的特征值。

---

3. 核心理论：为什么要找特征向量？(图割理论)

谱聚类的目标是将图 $V$ 切割成 $k$ 个子集 $A_1, ..., A_k$，使得：

1. 子集内部的边权重之和尽可能大（内部紧密）。
2. 子集之间的边权重之和尽可能小（外部疏离）。

这被称为 最小割 (Mincut) 问题。但是，直接做 Mincut 往往会切出孤立点（因为切断孤立点的代价最小）。为了解决这个问题，我们引入了 归一化切图 (Normalized Cut, Ncut)，要求切出来的子集规模不能太小。

Ncut 的目标函数：

$$\text{Ncut}(A_1, ..., A_k) = \sum_{i=1}^{k} \frac{\text{cut}(A_i, \bar{A}_i)}{\text{vol}(A_i)}$$

• $\text{cut}(A_i, \bar{A}_i)$: 子集 $A_i$ 与其余部分之间的连接权重。
• $\text{vol}(A_i)$: 子集 $A_i$ 中所有点的度之和（代表子集的大小）。

从 Ncut 到 特征值：

求解 Ncut 的最小化是一个 NP-hard 问题（很难直接算）。但是，数学家发现，如果我们把这个离散的分类问题“松弛”成连续的实数问题，它就等价于求解拉普拉斯矩阵的特征值问题。

具体来说：$L$ 的前 $k$ 个最小特征值对应的特征向量，包含了图的最优切割信息。

---

4. 算法步骤 (Standard Algorithm)

1. 构图: 计算数据点之间的相似度矩阵 $W$。
2. 计算矩阵: 计算度矩阵 $D$ 和拉普拉斯矩阵 $L$（通常使用归一化的 $L_{sym} = D^{-1/2}LD^{-1/2}$ 或 $L_{rw} = D^{-1}L$）。
3. 特征分解: 计算 $L$ 的特征值和特征向量。
4. 降维: 取出前 $k$ 个最小特征值对应的特征向量 $u_1, ..., u_k$。将这 $k$ 个向量作为列，组成一个 $n \times k$ 的矩阵 $U$。
   • 关键点：现在，每一行代表一个原始数据点，但它被映射到了一个 $k$ 维的新空间中。
5. 聚类: 对矩阵 $U$ 的 $n$ 行数据（作为新的特征）应用 K-Means 算法，得到最终的分类结果。

---

5. 优缺点总结

优点	缺点
形状适应性强: 能处理各种形状的数据（环形、螺旋形），只在乎连通性。	计算复杂度高: 特征分解的时间复杂度约为 $O(n^3)$，数据量大时（如 >5000）非常慢。
收敛于全局最优: 在松弛条件下是全局最优解（不像 K-Means 易陷入局部最优）。	参数敏感: 对相似度图的构建参数（如 RBF 核的 $\sigma$ 或 KNN 的 $k$）非常敏感。
降维效果: 自动实现了流形学习中的降维。	扩展性差: 新的数据点加入时，需要重新计算整个图和特征值。

---

总结

谱聚类本质上是**“在变换后的空间里做 K-Means”**。

它先通过拉普拉斯矩阵**提取数据的拓扑结构（连通性），将复杂的空间结构映射到低维的特征向量空间。在这个新空间里，原本纠缠在一起的非凸数据，会变成容易分离的团块，这时候再用 K-Means 就轻而易举了。