Spectral Clustering

图拉普拉斯矩阵是图论中一个非常重要的概念，广泛应用于谱聚类、图的嵌入、网络分析等领域。图拉普拉斯矩阵描述了图的结构信息，包括节点的连接方式和连接强度。它能够有效地捕捉图中节点之间的相似性，并用于各种优化问题中。

一个图（Graph）由以下两个部分组成：

每条边的权重表示两个节点之间的相似程度，未连接的节点之间的相似性为 0。

假设一个图 $G$ 有 $n$ 个节点，那么它的图拉普拉斯矩阵 $L$ 是一个 $n \times n$ 的矩阵。它的构造依赖于图的度矩阵 $D$ 和邻接矩阵 $A$ 。

邻接矩阵 $A$ ：邻接矩阵 $A$ 是一个 $n \times n$ 的矩阵，用于表示节点之间的连接关系。如果节点 $i$ 和节点 $j$ 之间有一条边，则 $A_{ij} = 1$ （或等于边的权重）；否则 $A_{ij} = 0$ 。
$A_{ij} = {w_{ij}, 0, 如果节点 i 和节点 j 有边连接否则$

- **度矩阵 $D$**：度矩阵 $D$ 是一个对角矩阵，表示每个节点的度数（degree）。节点的度数是该节点连接的边的权重之和：

D_{ii} = \sum_{j} A_{ij}

- **无归一化的图拉普拉斯矩阵**： 图拉普拉斯矩阵 $L$ 定义为度矩阵与邻接矩阵的差值：

L = D - A

其中，$L_{ii}$ 表示与节点 $i$ 相连的边的总权重，$L_{ij}$ 则表示节点 $i$ 和节点 $j$ 是否相连。对于无向图，图拉普拉斯矩阵是对称的。 #### 3. **归一化的图拉普拉斯矩阵** 在某些场景下，我们使用归一化的图拉普拉斯矩阵： - **对称归一化图拉普拉斯矩阵**：

L_{sym} = D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}

- * * 随机游走归一化图拉普拉斯矩阵 * * ：

L_{rw} = D^{-1} L = I - D^{-1} A

归一化的图拉普拉斯矩阵更加适用于处理节点度数差异较大的图。 ### 最小割问题（Min-Cut Problem） **最小割问题**是图论中的一个经典问题，常用于图的划分（clustering）。目标是将图分割为两个或多个部分，使得割边的总权重最小。 #### 1. **问题描述** 给定一个图 $G = (V, E)$，其中 $V$ 是节点集合，$E$ 是边集合。每条边 $(i, j)$ 具有一个权重 $w_{ij}$，表示节点 $i$ 和节点 $j$ 之间的相似性。**最小割问题**的目标是找到一种方式将图划分为两个子集 $A$ 和 $B$，使得跨越 $A$ 和 $B$ 之间的边的总权重最小。 - **割**定义为跨越两个子集的边的集合，记作 $\text{cut}(A, B)$。割的值（cost of the cut）是子集之间的边的权重之和：

\text{cut}(A, B) = \sum_{i \in A, j \in B} w_{ij}

#### 2. **最小割的局限性** 最小割问题本身有一个局限：它倾向于产生**不平衡的划分**。比如，如果一个节点和图的其余部分之间的连接较少，最小割往往会将这个单独的节点分出来。 为了克服这个问题，引入了**归一化最小割（Normalized Cut，Ncut）**。 ### 归一化最小割问题（Normalized Cut） 归一化最小割问题是谱聚类中常用的优化目标，它对最小割问题进行了改进，考虑到了子集大小的不均衡问题。目标是找到一种图的划分，使得跨越子集的边的权重较小，同时子集的大小（节点的度数之和）相对均衡。 #### 1. **归一化割的定义** 归一化割的目标是最小化如下公式：

\text{Ncut}(A, B) = \frac{\text{cut}(A, B)}{\text{assoc}(A, V)} + \frac{\text{cut}(A, B)}{\text{assoc}(B, V)}

其中，$\text{assoc}(A, V)$ 表示节点集 $A$ 和整个图 $V$ 之间的关联强度，即 $A$ 中所有节点的度数之和：

\text{assoc}(A, V) = \sum_{i \in A, j \in V} w_{ij}

通过这种归一化，能够避免产生极端不平衡的划分，比如将单个节点与其他部分分开。 #### 2. **与谱聚类的联系** 谱聚类通过将最小割问题转化为线性代数问题来求解。具体来说，它通过图拉普拉斯矩阵的特征向量进行谱分解，找到图的低维嵌入，然后在这个低维空间中应用传统的聚类算法（如 k-means），从而得到聚类结果。 ### 总结 - **图拉普拉斯矩阵**通过度矩阵和邻接矩阵构造，能够有效捕捉图的结构信息。 - **最小割问题**和**归一化最小割问题**是图划分的核心问题，通过最小化跨子集的边的权重实现图的划分。 - **谱聚类**结合了图拉普拉斯矩阵和归一化最小割问题，通过谱分解找到图的最优划分方案。

ReMind