图论基础与谱聚类算法

A1008612121

1094人浏览 · 2025-12-29 19:08:37

A1008612121 · 2025-12-29 19:08:37 发布

参考：https://blog.csdn.net/jteng/article/details/49590069

2.2 均衡分割策略：RatioCut 与 Normalized Cut

2.3 数学求解：拉普拉斯矩阵与松弛化

2.3.1 RatioCut 的推导与求解

2.3.2 多聚类扩展

2.3.3 Normalized Cut 的求解差异

谱聚类将数据的划分转化为对图的分割，是一种基于图论的聚类方法，其直观理解为根据图内点的相似度将图分为多个子图，使子图内部的点相似度最高，子图之间点的相似度最低。

1.图论的基础

1.1 图的表示

三个关键组成部分：图本身、邻接矩阵 W 和度矩阵 D

例子：假设我们有4个人：Alice, Bob, Carol, David。我们用一张图来表示他们之间的好友关系，关系紧密程度（权重）用数字表示。

1）图的定义 $G=(V,E)$ 。

G: 这就是我们所要描述的整个图，它包含了所有顶点（人）和边（好友关系）。

V(顶点集合vertex): $V={v_1,v_2,....,v_n}$ 图中所有顶点的集合。

E(边集合edge): 图中所有连接的集合。

无向图:顾名思义，就是没有方向的图。关系是双向的、对等的，没有“谁指向谁”的区别。

2）邻接矩阵 W。

描述图中顶点之间的连接关系（可以理解为权重）。是一个 n×n的方阵（n是顶点数）， $w_{ij}$ 表示顶点 $v_i$ 和顶点 $v_j$ 之间的边的权值。

规则：

$w_{ij}\geq 0$ : 权值是非负的。

$w_{ij}=0$ : 如果两点之间没有边直接相连，则权值为0。

w $w_{ij}=w_{ij}$ : 因为是无向图，矩阵是对称的

在例子中:

假设好友关系权重如下：

Alice和Bob很熟，权重 w12=3
Alice和Carol是普通朋友，权重 w13=1
Bob和David是朋友，权重 w24=2
Carol和David是朋友，权重 w34=2
Alice和David不是朋友，Bob和Carol也不是朋友。

那么，邻接矩阵 W如下所示：

$W=\begin{bmatrix} 0 & 3 &1 &0\\ 3& 0& 0&2 \\ 1 &0 & 0&2 \\ 0& 2& 2& 0 \end{bmatrix}$

3）度 $d_i$ 与度矩阵 D。

“度”衡量的是一个顶点与外部世界的“总连接强度”。度 $d_i$ 表示顶点 $v_i$ 的度，是其所有连接边的权值之和。

在例子中:

$d_1$ (Alice的度) = w12+w13+w14=3+1+0=4

度矩阵是一个对角矩阵，只有对角线上的元素有非零值，这些值就是各个顶点的度 $d_i$ 。

在例子中，度矩阵 D为：

$D=\begin{bmatrix} 4 & 0& 0& 0\\ 0 & 5& 0 &0 \\ 0& 0& 3& 0\\ 0& 0& 0& 4 \end{bmatrix}$

4）总结

图 (G): 就是上面这个关系图，包含了4个顶点和4条边

1.2 相似度图的构造方法

目的：给定一堆数据点 $V={v_1,v_2,....,v_n}$ ，我们要构建一个图 $G=(V,E)$ 。这个图用来描述数据点之间的局部近邻关系。边的权重（相似度）越高，表示两个点越相似。

三种构造相似度图的方法：

方法一：ε-近邻图

核心思想：设定一个距离阈值ε。如果两个点之间的距离小于ε，则连接两点。重点在于参数 ε 的选择。且对参数ε非常敏感。

方法二：k-近邻图

核心思想：不为所有点设定一个固定的距离阈值，而是为每个点单独寻找其最接近的k个点作为邻居。这样，每个点都保证有k个邻居。
“非相互性”问题与解决策略：
问题：近邻关系不一定是相互的。 $v_j$ 是 $v_i$ 的k近邻，并不意味着也是 $v_j$ 的k近邻。
策略：采用 “或” 或 “与” 的方法。区别在于连接条件不同，一个是 $v_j$ 是 $v_i$ 的k近邻或是 $v_j$ 的k近邻即可，一个是同时满足。
优点是可以自适应不同密度的数据集，缺点是要选择参数 k

方法三：全连接图

核心思想：最简单粗暴的方法——连接所有点对。每个点都和其余所有n-1个点相连。
关键：既然全都连接了，那么边的权重（相似度）就变得至关重要。权重函数需要能够很好地度量相似度，并且对于不相似的点对，权重应该非常小（接近零）。
常用的相似性函数：高斯核函数（也称为径向基函数，RBF）
$s(x_i, x_j) = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)$
参数 $\sigma$ 控制权重随距离衰减的速度，参数越小衰减越快。

在实际应用中，k-近邻图（通常采用“或”的策略） 是最常用的方法，因为它在实用性和效果之间取得了很好的平衡。

1.3 图的Laplacian矩阵

在谱聚类中，拉普拉斯矩阵 L=D−W ，这个矩阵蕴含了图的分割信息，是谱聚类算法能够工作的核心。其中D和W就是上文定义的图的度矩阵和邻接矩阵。

2.谱聚类算法

谱聚类算法（Spectral Clustering）的本质是将聚类任务转化为图论中的最优分割问题。首先将所有的样本点连接成图，然后将图分割成不同的子图，使得不同子图之间的连接权值最小。

2.1 最小割准则（Min-cut）

首先，将所有样本点映射为图中的顶点，样本间的相似度作为边的权重。聚类的目标是将图划分为 k 个互不相交的子图 $A_1,....A_k$ ，并使得各子图之间的连接权值总和达到最小。定义子图 A 与其补集 Aˉ 之间的连接权值为：

$W(A,\bar{A})=\sum_{i\in A,j\in\bar{A}} w_{ij}$

最优分割即最小化以下目标函数：

$\text{cut}(A_{1},\ldots, A_{k})=\frac{1}{2}\sum_{i=1}^{k} W\left(A_{i},\bar{A}_{i}\right)$

问题：传统的最小割准则往往会产生“孤立点”现象，即算法倾向于切下极少数的点以换取最小的权值和，导致分割结果极度不均衡。

2.2 均衡分割策略：RatioCut 与 Normalized Cut

解决该问题的有效办法是让每个子图都有合理的大小，子图大小的度量方式不同就会得出不同的最小分割问题，常用的两种方法是RaioCut和Normalized Cut

1. RatioCut：以子图内节点的数量 $\left |A_i \right |$ 作为规模度量，旨在平衡各簇的样本规模。

$\text{RatioCut}(A_{1},\ldots,A_{k}) = \sum_{i=1}^{k} \frac{\text{cut}(A_{i},\bar{A}_{i})}{\left|A_{i}\right|}$

2. Normalized Cut (Ncut)：以子图内节点的度之和（Volume） $vol(A_i)$ 作为度量，更看重簇内连接的紧密程度。

$N\text{cut}(A_{1},\ldots,A_{k}) = \sum_{i=1}^{k} \frac{\text{cut}(A_{i},\bar{A}_{i})}{\text{vol}(A_{i})}$

其中， $\text{vol}(A_{i}) = \sum_{j \in A_{i}} d_{j}$ 。通过将子图大小作为分母，强制约束各子图不能过小。

2.3 数学求解：拉普拉斯矩阵与松弛化

2.3.1 RatioCut 的推导与求解

以二聚类为例，引入示性向量 $f\in\mathbb{R}^{n}$ ，其元素定义如下：

$f_{i} = \begin{cases} \sqrt{|\bar{A}|/|A|} & \text{if } v_{i}\in A \\ -\sqrt{|A|/|\bar{A}|} & \text{if } v_{i}\in\bar{A} \end{cases}$

结合图的拉普拉斯矩阵（Laplacian Matrix） L=D−W，利用二次型性质可以推导出：

$f^{T}Lf = |V|\cdot\text{RatioCut}(A,\bar{A})$

由于 $\left |V \right |$ 为常数，最小化 RatioCut 等价于最小化 $f^{T}Lf$ 。

松弛化处理： 寻找最优示性向量是一个 NP-hard 的离散优化问题。通过松弛化，允许 f 取任意实数，并加上约束 $f\perp 1$ 和 $\|f\| = \sqrt{n}$ 。据 Rayleigh-Ritz 定理，该问题的最优解即为矩阵 L 的第二小特征值对应的特征向量。

2.3.2 多聚类扩展

对于 k 聚类，我们定义 k 个正交的示性向量构成矩阵 $H\in\mathbb{R}^{n\times k}$ ，目标函数转化为：

$\min_{H\in\mathbb{R}^{n\times k}} \text{Tr}(H^{T}LH), \quad s.t. \quad H^{T}H = I$

其解为 $L$ 的前 $k$ 个最小特征值对应的特征向量所组成的矩阵。

2.3.3 Normalized Cut 的求解差异

Ncut 的推导逻辑相似，但其松弛化后的优化问题转变为广义特征值问题：

$L f = \lambda D f$

此时，需要求解的是 $L$ 相对于度矩阵 $D$ 的前 $k$ 个广义特征向量。

3. 谱聚类算法标准化流程

基于图分割理论，标准谱聚类算法可以总结为以下四个步骤：

Step 1：构建相似度图。将每个样本看做图的顶点，构造无向加权图及其邻接矩阵 W。
Step 2：计算矩阵算子。推导度矩阵 D 以及拉普拉斯矩阵 L。
Step 3：谱分解（特征提取）。根据 RatioCut 或 Ncut 准则，计算 L 的前 k 个最小特征值对应的特征向量。
Step 4：空间重构与聚类。将提取出的 k 个特征向量按列组成矩阵 Y。将 Y 的每一行视作原始样本在低维空间中的新坐标，然后利用 K-means 算法完成最终聚类。