谱聚类图割

本文目录导读：

1. 核心思想一句话总结
2. 从聚类到图割：问题建模
3. 避免畸形分割：引入归一化——RatioCut 与 Ncut
4. 数学魔法：将Ncut转化为特征分解
5. 谱聚类图割的标准算法流程
6. 直观理解：为什么“割”变成“特征向量”？
7. 优缺点与实用建议

我们来详细、系统地讲清楚谱聚类中的图割问题，这不仅是谱聚类的核心数学原理，也是连接“聚类”与“图论”的关键桥梁。

核心思想一句话总结

谱聚类的目标是通过对数据相似度图的拉普拉斯矩阵进行特征分解，将高维的图割问题转化为低维空间中的K-means聚类问题。

---

从聚类到图割：问题建模

我们手里有一堆数据点 (x_1, x_2, ..., x_n)，想把它分成k类。

1. 构建相似度图：

   • 把每个数据点 (x_i) 看作图中的一个节点 (v_i)。
   • 计算任意两点之间的相似度 (w_{ij} = s(x_i, xj))，作为边的权重，常用的有高斯核 (w{ij} = \exp\left(-\frac{|x_i - x_j|^2}{2\sigma^2}\right))。
   • 这样,我们就得到了一个带权无向图 (G = (V, E))，(W = (w_{ij})) 是邻接矩阵。

2. 定义“好聚类”的目标： 一个好的聚类，在图论的语言下就是：类内边权重尽可能大（紧密连接），类间边权重尽可能小（连接稀疏）。

   将图划分为 (k) 个子集 (A_1, A_2, ..., A_k)，我们要最小化割(Cut)： [ \text{Cut}(A_1, ..., Ak) = \frac{1}{2} \sum{i=1}^{k} W(A_i, \bar{Ai}) ] (W(A, B) = \sum{i \in A, j \in B} w_{ij})。

   问题：直接最小化 (\text{Cut}) 会导致“畸形分割”——比如把图中一个孤立点单独切出来，割的代价(cut)非常小，但这不是我们想要的全局划分。

避免畸形分割：引入归一化——RatioCut 与 Ncut

为了解决这个问题,我们需要在最小化Cut的同时，惩罚那些太小或太大的子集。

1 RatioCut（比例割）

对每个子集的大小（即节点数量 (|A_i|)）进行惩罚： [ \text{RatioCut}(A_1,...,Ak) = \frac{1}{2} \sum{i=1}^{k} \frac{W(A_i, \bar{A_i})}{|A_i|} ] 缺点：它只考虑了节点数量，没有考虑节点的重要程度（即节点的度）。

2 Normalized Cut (Ncut，归一化割)

对每个子集的总连接权重（即图的“体积” (\text{vol}(Ai) = \sum{j \in A_i} d_j)，(d_j) 是节点j的度）进行惩罚： [ \text{Ncut}(A_1,...,Ak) = \frac{1}{2} \sum{i=1}^{k} \frac{W(A_i, \bar{A_i})}{\text{vol}(A_i)} ] 为什么Ncut更好？ 如果一个子集内部连接非常紧密（体积大），分母 (\text{vol}(A_i)) 大，即使这个子集边界有点大，也能被容忍，这有效避免了切出孤立点。

谱聚类的核心：最小化Ncut是一个NP难问题，我们需要一个巧妙的数学变换，把它放到连续域里求解。

---

数学魔法：将Ncut转化为特征分解

这是谱聚类最精彩的部分。

1 引入指示向量与拉普拉斯矩阵

• 度矩阵 (D = \text{diag}(d_1, d_2, ..., d_n))，(d_i = \sumj w{ij})。
• 图拉普拉斯矩阵 (L = D - W)（未归一化）。
• 归一化拉普拉斯矩阵 (L{\text{sym}} = D^{-1/2} L D^{-1/2}) 或 (L{\text{rw}} = D^{-1}L)。

对于二分类（k=2）的情形，设指示向量 (f \in \mathbb{R}^n)， [ f_i = \begin{cases} \sqrt{\frac{\text{vol}(\bar{A})}{\text{vol}(A)}} & \text{if } v_i \in A \ -\sqrt{\frac{\text{vol}(A)}{\text{vol}(\bar{A})}} & \text{if } v_i \in \bar{A} \end{cases} ]

经过巧妙的代数推导（这里省略具体推导步骤，但这是关键），可以得到： [ \text{Ncut}(A, \bar{A}) = \frac{f^T L f}{f^T D f} ] (f) 满足约束：(f^T D \mathbf{1} = 0)（(\mathbf{1}) 是全1向量）。

2 松弛到连续域

直接解这个离散的组合优化（(f) 只能取两个特定值）很困难，标准做法是松弛：允许 (f) 取任意实数值。

问题变成了： [ \min_{f \in \mathbb{R}^n, f \perp D\mathbf{1}} \frac{f^T L f}{f^T D f} ] 这是一个瑞利商(Rayleigh Quotient) 的广义形式。

3 化为标准特征分解

令 (g = D^{1/2} f)，则： [ \frac{f^T L f}{f^T D f} = \frac{g^T D^{-1/2} L D^{-1/2} g}{g^T g} = \frac{g^T L_{\text{sym}} g}{g^T g} ] 约束 (f^T D \mathbf{1} = 0) 变成 (g^T D^{1/2} \mathbf{1} = 0)。

这个连续优化问题的最优解 (g)，(L_{\text{sym}}) 的第二小特征值对应的特征向量（因为最小特征值0对应的特征向量是 (D^{1/2}\mathbf{1})，这个解被约束排除掉了）。

---

谱聚类图割的标准算法流程

1. 构建邻接矩阵 (W)（基于相似度）。
2. 计算度矩阵 (D)。
3. 计算归一化拉普拉斯矩阵 (L_{\text{sym}} = D^{-1/2} (D - W) D^{-1/2})。
4. 特征分解：计算 (L_{\text{sym}}) 的前k个最小特征值对应的特征向量 (u_1, u_2, ..., u_k)。
5. 构造特征空间：将 (n) 个节点的 (k) 个特征向量按行堆叠，形成一个 (n \times k) 的矩阵 (U)，每一行就代表原始一个节点在低维特征空间（谱空间）中的坐标。
6. 归一化：对 (U) 的每一行进行L2归一化，使得所有行向量长度为1（这一步对于处理不同度的节点很重要，对应Ncut的几何意义）。
7. K-means聚类：在 (n) 个 (k) 维向量（(U) 的行）上运行K-means算法，将 (n) 个点聚成 (k) 类。

为什么这个算法有效？ 因为拉普拉斯矩阵的第二小特征向量（Fiedler向量）的符号，恰好可以近似指示最优的二分切割，扩展到k维，前k个特征向量构成的低维嵌入，完美地保留了图中各节点间“是否应被切到同一类”的流形结构，使得原本可能线性不可分的数据在谱空间中变得线性可分。

---

直观理解：为什么“割”变成“特征向量”？

• 图的可视化：想象一个图，数据点连成几个密集的“团块”，团块之间只有少量稀疏连接。
• 拉普拉斯矩阵的作用：(f^T L f = \frac{1}{2} \sum{i,j} w{ij} (f_i - fj)^2)，这个公式衡量的是：(f) 在强连接（(w{ij}) 大）的两个节点上取值差异大，则 (f^T L f) 大，最小化 (f^T L f) 等价于鼓励 (f) 在密集连接的区域取值平滑（接近），而在稀疏连接处允许跳变。
• 特征向量的角色：这就是为什么特征向量（特别是小特征值对应的）会在图的“自然分割”处发生符号变化或取值突变，Fiedler向量（第二小特征向量）的正负号，就对应着图的最粗粒度二分切割。
• Ncut的工作：归一化因子 (f^T D f) 保证了度大的节点在优化中占比更高，避免了切出孤立点。

优缺点与实用建议

项目
优点	对非凸形状数据效果好（优于K-means）。 基于谱的松弛是凸优化，能找到全局最优解（虽然是松弛后的）。 理论上与随机游走、马尔可夫链、归一化割均有深刻联系。
缺点	计算复杂度高：(O(n^3)) 的特征分解，对大数据集需要近似方法（如Nyström、随机奇异值分解）。 对相似度参数敏感（如高斯核的 (\sigma)）。 最终仍需K-means聚类，可能受到K-means初始化的影响。

什么时候用？

• 数据呈现复杂的流形结构（如螺旋形、环形）。
• 你关心数据点之间的相对关系大于它们在原始空间的绝对位置。
• 聚类数量k已知或可合理估计。

希望这个从图割出发的谱聚类推导对你有帮助,如果对某个具体公式（比如从Ncut到Rayleigh Quotient的推导细节）想深入，随时问。