谱聚类（Spectral Clustering）的图构造、拉普拉斯矩阵选择与图切割视角分析
字数 2356 2025-12-19 10:03:23

谱聚类（Spectral Clustering）的图构造、拉普拉斯矩阵选择与图切割视角分析

谱聚类是一种基于图论的聚类方法，它利用数据的相似度图，通过对图的拉普拉斯矩阵进行特征分解，在低维特征空间中进行聚类。下面我将从图构造、拉普拉斯矩阵选择和图切割视角三个方面，详细讲解其原理和过程。

1. 图构造

谱聚类的第一步是根据数据集构建一个无向加权图 \(G(V, E)\)，其中顶点 \(V\) 对应数据点，边 \(E\) 的权重表示点之间的相似度。常用方法如下：

  • 全连接图：为每对点 \((x_i, x_j)\) 分配权重，通常用高斯核函数计算相似度：

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

其中 \(\sigma\) 控制邻域宽度。这会产生一个稠密矩阵，适合小数据集。

  • k近邻图：每个点只连接其k个最近邻。这又分为两种：

    • k近邻图：如果 \(x_i\) 是 \(x_j\) 的k近邻，或 \(x_j\) 是 \(x_i\) 的k近邻，则连接边。
    • 相互k近邻图：仅当两点互为k近邻时才连接，图更稀疏，适合噪声数据。

  • \(\epsilon\)-邻域图：如果两点距离小于阈值 \(\epsilon\)，则连接边，权重常设为1（无权图）或高斯核加权。阈值选择对结果敏感。

解释：图构造的本质是捕获数据的局部结构。相似度高的点之间边权重大，表示它们更可能属于同一类；相似度低的点边权重小或不连接，表示它们可能属于不同类。构造的图用相似度矩阵 \(W\) 表示，其中 \(W_{ij} = w_{ij}\)。

2. 拉普拉斯矩阵选择

拉普拉斯矩阵是图的关键代数表示，谱聚类中常用以下三种形式，每种对应不同的图切割目标：

  • 非归一化拉普拉斯矩阵：

\[ L = D - W \]

其中 \(D\) 是度矩阵，\(D_{ii} = \sum_j w_{ij}\)，\(D_{ij}=0 (i \neq j)\)。L 是半正定矩阵，最小特征值为0，对应特征向量为全1向量。

  • 对称归一化拉普拉斯矩阵：

\[ L_{\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2} \]

这种归一化可消除顶点度的影响，使特征值在 [0, 2] 范围内，常用于实际应用。

  • 随机游走归一化拉普拉斯矩阵：

\[ L_{\text{rw}} = D^{-1} L = I - D^{-1} W \]

它与随机游走转移矩阵相关，其特征向量与 \(L_{\text{sym}}\) 的特征向量通过 \(D^{-1/2}\) 关联。

解释：拉普拉斯矩阵的特征向量反映了图的连通结构。例如，L 的第二小特征向量（称为 Fiedler 向量）给出了图的最佳二分划分。归一化拉普拉斯矩阵能处理图中顶点度差异大的情况，避免将孤立点单独划为一类。

3. 图切割视角

谱聚类可视为对图进行切割的最优化问题，目标是将图划分为k个子图，使得子图内部连接紧密，子图之间连接稀疏。常见的切割准则有：

  • RatioCut：最小化切割边占子图大小的比例。对于划分为k个子集 \(A_1, ..., A_k\)，目标为：

\[ \text{RatioCut}(A_1,...,A_k) = \frac{1}{2} \sum_{i=1}^k \frac{\text{cut}(A_i, \bar{A}_i)}{|A_i|} \]

其中 \(\text{cut}(A_i, \bar{A}_i) = \sum_{u \in A_i, v \in \bar{A}_i} w_{uv}\)，\(|A_i|\) 是子集大小。最小化 RatioCut 等价于对 L 的前k个特征向量进行聚类。

  • Ncut：用子图体积代替大小，更能适应度分布不均的图：

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

其中 \(\text{vol}(A_i) = \sum_{u \in A_i} d_u\) 是子图内所有点的度之和。最小化 Ncut 等价于对 \(L_{\text{sym}}\) 的前k个特征向量进行聚类。

过程解释：通过求解拉普拉斯矩阵的前k个特征向量，将原始数据映射到低维特征空间，此时数据点在这些特征向量张成的空间中更易于分离。然后对特征向量矩阵的行（即每个数据点的低维表示）运行k-means等传统聚类算法，得到最终聚类结果。

总结步骤

  1. 构建相似度图：选择邻接方式（如k近邻），计算相似度矩阵 \(W\)。
  2. 计算拉普拉斯矩阵：根据数据特性选择 \(L\), \(L_{\text{sym}}\) 或 \(L_{\text{rw}}\)。
  3. 特征分解：计算前k个最小特征值对应的特征向量，形成矩阵 \(U \in \mathbb{R}^{n \times k}\)。
  4. 归一化：对 \(U\) 的行进行归一化（尤其使用 \(L_{\text{sym}}\) 时），得到矩阵 \(T\)。
  5. 聚类：对 \(T\) 的每一行作为点，应用k-means聚类为k类。
  6. 映射回原数据：将聚类结果对应到原始数据点。

谱聚类的优势是能发现非凸形状的簇，对噪声相对稳健，但计算复杂度高（需特征分解），且参数（如k、\(\sigma\)）选择敏感。

谱聚类（Spectral Clustering）的图构造、拉普拉斯矩阵选择与图切割视角分析 谱聚类是一种基于图论的聚类方法，它利用数据的相似度图，通过对图的拉普拉斯矩阵进行特征分解，在低维特征空间中进行聚类。下面我将从图构造、拉普拉斯矩阵选择和图切割视角三个方面，详细讲解其原理和过程。 1. 图构造 谱聚类的第一步是根据数据集构建一个无向加权图 \( G(V, E) \)，其中顶点 \( V \) 对应数据点，边 \( E \) 的权重表示点之间的相似度。常用方法如下： 全连接图 ：为每对点 \((x_ i, x_ j)\) 分配权重，通常用高斯核函数计算相似度： \[ w_ {ij} = \exp\left(-\frac{\|x_ i - x_ j\|^2}{2\sigma^2}\right) \] 其中 \(\sigma\) 控制邻域宽度。这会产生一个稠密矩阵，适合小数据集。 k近邻图 ：每个点只连接其k个最近邻。这又分为两种： k近邻图 ：如果 \(x_ i\) 是 \(x_ j\) 的k近邻，或 \(x_ j\) 是 \(x_ i\) 的k近邻，则连接边。 相互k近邻图 ：仅当两点互为k近邻时才连接，图更稀疏，适合噪声数据。 \(\epsilon\)-邻域图 ：如果两点距离小于阈值 \(\epsilon\)，则连接边，权重常设为1（无权图）或高斯核加权。阈值选择对结果敏感。 解释 ：图构造的本质是捕获数据的局部结构。相似度高的点之间边权重大，表示它们更可能属于同一类；相似度低的点边权重小或不连接，表示它们可能属于不同类。构造的图用相似度矩阵 \(W\) 表示，其中 \(W_ {ij} = w_ {ij}\)。 2. 拉普拉斯矩阵选择 拉普拉斯矩阵是图的关键代数表示，谱聚类中常用以下三种形式，每种对应不同的图切割目标： 非归一化拉普拉斯矩阵 ： \[ L = D - W \] 其中 \(D\) 是度矩阵，\(D_ {ii} = \sum_ j w_ {ij}\)，\(D_ {ij}=0 (i \neq j)\)。L 是半正定矩阵，最小特征值为0，对应特征向量为全1向量。 对称归一化拉普拉斯矩阵 ： \[ L_ {\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2} \] 这种归一化可消除顶点度的影响，使特征值在 [ 0, 2 ] 范围内，常用于实际应用。 随机游走归一化拉普拉斯矩阵 ： \[ L_ {\text{rw}} = D^{-1} L = I - D^{-1} W \] 它与随机游走转移矩阵相关，其特征向量与 \(L_ {\text{sym}}\) 的特征向量通过 \(D^{-1/2}\) 关联。 解释 ：拉普拉斯矩阵的特征向量反映了图的连通结构。例如，L 的第二小特征向量（称为 Fiedler 向量）给出了图的最佳二分划分。归一化拉普拉斯矩阵能处理图中顶点度差异大的情况，避免将孤立点单独划为一类。 3. 图切割视角 谱聚类可视为对图进行切割的最优化问题，目标是将图划分为k个子图，使得子图内部连接紧密，子图之间连接稀疏。常见的切割准则有： RatioCut ：最小化切割边占子图大小的比例。对于划分为k个子集 \(A_ 1, ..., A_ k\)，目标为： \[ \text{RatioCut}(A_ 1,...,A_ k) = \frac{1}{2} \sum_ {i=1}^k \frac{\text{cut}(A_ i, \bar{A}_ i)}{|A_ i|} \] 其中 \(\text{cut}(A_ i, \bar{A} i) = \sum {u \in A_ i, v \in \bar{A} i} w {uv}\)，\(|A_ i|\) 是子集大小。最小化 RatioCut 等价于对 L 的前k个特征向量进行聚类。 Ncut ：用子图体积代替大小，更能适应度分布不均的图： \[ \text{Ncut}(A_ 1,...,A_ k) = \frac{1}{2} \sum_ {i=1}^k \frac{\text{cut}(A_ i, \bar{A} i)}{\text{vol}(A_ i)} \] 其中 \(\text{vol}(A_ i) = \sum {u \in A_ i} d_ u\) 是子图内所有点的度之和。最小化 Ncut 等价于对 \(L_ {\text{sym}}\) 的前k个特征向量进行聚类。 过程解释 ：通过求解拉普拉斯矩阵的前k个特征向量，将原始数据映射到低维特征空间，此时数据点在这些特征向量张成的空间中更易于分离。然后对特征向量矩阵的行（即每个数据点的低维表示）运行k-means等传统聚类算法，得到最终聚类结果。 总结步骤 构建相似度图 ：选择邻接方式（如k近邻），计算相似度矩阵 \(W\)。 计算拉普拉斯矩阵 ：根据数据特性选择 \(L\), \(L_ {\text{sym}}\) 或 \(L_ {\text{rw}}\)。 特征分解 ：计算前k个最小特征值对应的特征向量，形成矩阵 \(U \in \mathbb{R}^{n \times k}\)。 归一化 ：对 \(U\) 的行进行归一化（尤其使用 \(L_ {\text{sym}}\) 时），得到矩阵 \(T\)。 聚类 ：对 \(T\) 的每一行作为点，应用k-means聚类为k类。 映射回原数据 ：将聚类结果对应到原始数据点。 谱聚类的优势是能发现非凸形状的簇，对噪声相对稳健，但计算复杂度高（需特征分解），且参数（如k、\(\sigma\)）选择敏感。