谱聚类算法的核心步骤与实现流程
字数 2917 2025-12-22 02:47:43

谱聚类算法的核心步骤与实现流程

题目描述

谱聚类（Spectral Clustering）是一种基于图论的聚类算法，它将数据点视为图中的节点，利用数据点之间的相似性构造图，然后通过对图的拉普拉斯矩阵进行谱分解（即特征分解）来降维，最后在低维空间中执行传统的聚类算法（如K-means）。它能够发现任意形状的簇，并且对噪声和离群点相对鲁棒。我们在此深入探讨其核心实现步骤。

解题过程

第一步：构建相似性图

谱聚类的首要任务是将给定的数据集 \(X = \{x_1, x_2, ..., x_n\}\) 转化为一个无向加权图 \(G = (V, E)\)。

  • 节点（V）：每一个数据点 \(x_i\) 对应图中的一个顶点。
  • 边（E）与权重（W）：边的权重 \(w_{ij}\) 由相似性矩阵（或称邻接矩阵） \(S\) 定义，表示两个点之间的相似度。常见构造方法有：
    1. \(\epsilon\)-邻近图：若两点间的欧氏距离 \(\|x_i - x_j\|^2\) 小于阈值 \(\epsilon\)，则连接一条边，权重为1（或为距离函数值），否则为0。这种方法对 \(\epsilon\) 敏感，不常用。
    2. k-最近邻图（k-NN Graph）：每个点只与其k个最相似的点连接。有互k近邻（仅在两者互为k近邻时连接）和非互k近邻两种变体，后者更常用。
    3. 全连接图：所有点两两相连，权重由相似度函数计算，常用高斯核（RBF核）函数：

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

    其中 $\sigma$ 是控制邻域宽度的尺度参数。

最终，我们得到一个 \(n \times n\) 的相似度矩阵 \(W\)，其中 \(W_{ij} = w_{ij}\)，且 \(W\) 是一个对称矩阵（\(W = W^T\)）。

第二步：计算图的拉普拉斯矩阵

图的拉普拉斯矩阵是谱聚类的核心。它有三种主要形式，选择不同形式会影响聚类效果。
定义度矩阵 \(D\)：这是一个对角矩阵，对角线元素 \(d_i = \sum_{j=1}^{n} w_{ij}\)，表示顶点 \(i\) 的度。

  1. 非规范（非标准化）拉普拉斯矩阵：

\[ L = D - W \]

  1. 规范（标准化）拉普拉斯矩阵：
    • 对称标准化拉普拉斯（更常用）：

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

- **随机游走标准化拉普拉斯**：

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

标准化形式（尤其是 \(L_{\text{sym}}\)）在实践中通常能产生更好的聚类结果，因为它对图中节点度的变化不敏感。

第三步：进行谱分解（特征分解）

对选定的拉普拉斯矩阵进行特征分解。假设我们要将数据聚成 \(k\) 个簇：

  • 计算拉普拉斯矩阵 \(L\)（或 \(L_{\text{sym}}\)、\(L_{\text{rw}}\)）的最小的 \(k\) 个特征值及其对应的特征向量。
  • 为什么是最小的k个特征值？ 对于一个无向加权图，拉普拉斯矩阵是半正定的，其特征值非负。最小的特征值（0）对应的特征向量是常数向量。第二个最小的特征值（称为代数连通度）对应的特征向量（称为Fiedler向量）给出了图的二划分。推广到k个簇，最小的k个特征向量包含了对图进行k划分的最优松弛解信息。
  • 用这些特征向量构造一个新的特征向量矩阵 \(U \in \mathbb{R}^{n \times k}\)。
    • 若使用 \(L\) 或 \(L_{\text{sym}}\)，则直接取对应最小k个特征值的k个特征向量 \(u_1, u_2, ..., u_k\) 作为 \(U\) 的列。
    • 若使用 \(L_{\text{rw}}\)，则取对应最小k个特征值的k个右特征向量。
  • 对于 \(L_{\text{sym}}\)，通常还需要对矩阵 \(U\) 的行进行标准化：设 \(U\) 的第 \(i\) 行为 \(y_i \in \mathbb{R}^k\)，我们计算：

\[ y_i' = \frac{y_i}{\|y_i\|} \]

这使得新的点 $ y_i' $ 位于一个 $ k $ 维的单位超球面上，可以改善后续K-means聚类的稳定性。

第四步：在低维空间进行聚类

现在，原始的每个数据点 \(x_i \in \mathbb{R}^d\) 都被映射到了 \(k\) 维空间中的一个点 \(y_i \in \mathbb{R}^k\)（即矩阵 \(U\) 的第 \(i\) 行）。在这个新的特征空间中，数据点之间的相似性结构被增强，不同簇之间的点更容易分离。

  • 将集合 \(\{y_1, y_2, ..., y_n\}\) 作为输入，使用K-means聚类算法将其划分为 \(k\) 个簇 \(C_1, C_2, ..., C_k\)。
  • K-means的初始中心点选择（如K-means++）对最终结果有较大影响，通常需要多次运行以获得稳定结果。

第五步：将聚类结果映射回原空间

K-means在低维空间 \(\mathbb{R}^k\) 中得到的簇标签，直接对应了原始数据空间 \(\mathbb{R}^d\) 中数据点 \(x_i\) 的簇标签。

  • 如果低维空间中的点 \(y_i\) 被分配到簇 \(C_j\)，那么原始数据点 \(x_i\) 就被分配到簇 \(j\)。

算法总结与关键点

  1. 输入：数据点 \(X\)，聚类数 \(k\)，相似度函数（如高斯核的 \(\sigma\)），图的构造方法（如全连接图或k-NN图），以及拉普拉斯矩阵类型。
  2. 过程：
    • 构造相似度矩阵 \(W\)。
    • 计算度矩阵 \(D\) 和拉普拉斯矩阵 \(L\)。
    • 计算 \(L\) 的前 \(k\) 个最小特征值对应的特征向量，形成矩阵 \(U\)。
    • （可选）对 \(U\) 的行进行标准化。
    • 对 \(U\) 的行向量运行K-means算法，得到k个簇。
  3. 输出：数据点 \(x_i\) 的簇标签。
  4. 关键优势：相比K-means，谱聚类不需要假设数据簇是凸形或球形，只要数据点在特征空间中是“连接”的即可。它本质上是一种基于图分割的聚类。
  5. 主要挑战：参数选择（如 \(\sigma\)、k-NN中的k、聚类数k）对结果影响大，特征分解对于大规模数据集计算成本高，需要使用如Lanczos方法等近似技术。
谱聚类算法的核心步骤与实现流程 题目描述 谱聚类（Spectral Clustering）是一种基于图论的聚类算法，它将数据点视为图中的节点，利用数据点之间的相似性构造图，然后通过对图的拉普拉斯矩阵进行谱分解（即特征分解）来降维，最后在低维空间中执行传统的聚类算法（如K-means）。它能够发现任意形状的簇，并且对噪声和离群点相对鲁棒。我们在此深入探讨其核心实现步骤。 解题过程 第一步：构建相似性图 谱聚类的首要任务是将给定的数据集 \( X = \{x_ 1, x_ 2, ..., x_ n\} \) 转化为一个无向加权图 \( G = (V, E) \)。 节点（V） ：每一个数据点 \( x_ i \) 对应图中的一个顶点。 边（E）与权重（W） ：边的权重 \( w_ {ij} \) 由 相似性矩阵（或称邻接矩阵） \( S \) 定义，表示两个点之间的相似度。常见构造方法有： \(\epsilon\)-邻近图 ：若两点间的欧氏距离 \( \|x_ i - x_ j\|^2 \) 小于阈值 \(\epsilon\)，则连接一条边，权重为1（或为距离函数值），否则为0。这种方法对 \(\epsilon\) 敏感，不常用。 k-最近邻图（k-NN Graph） ：每个点只与其k个最相似的点连接。有 互k近邻 （仅在两者互为k近邻时连接）和 非互k近邻 两种变体，后者更常用。 全连接图 ：所有点两两相连，权重由相似度函数计算，常用 高斯核（RBF核） 函数： \[ w_ {ij} = s_ {ij} = \exp\left( -\frac{\|x_ i - x_ j\|^2}{2\sigma^2} \right) \] 其中 \(\sigma\) 是控制邻域宽度的尺度参数。 最终，我们得到一个 \( n \times n \) 的相似度矩阵 \( W \)，其中 \( W_ {ij} = w_ {ij} \)，且 \( W \) 是一个对称矩阵（\( W = W^T \)）。 第二步：计算图的拉普拉斯矩阵 图的拉普拉斯矩阵是谱聚类的核心。它有三种主要形式，选择不同形式会影响聚类效果。 定义 度矩阵 \( D \) ：这是一个对角矩阵，对角线元素 \( d_ i = \sum_ {j=1}^{n} w_ {ij} \)，表示顶点 \( i \) 的度。 非规范（非标准化）拉普拉斯矩阵 ： \[ L = D - W \] 规范（标准化）拉普拉斯矩阵 ： 对称标准化拉普拉斯（更常用） ： \[ L_ {\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2} \] 随机游走标准化拉普拉斯 ： \[ L_ {\text{rw}} = D^{-1} L = I - D^{-1} W \] 标准化形式（尤其是 \( L_ {\text{sym}} \)）在实践中通常能产生更好的聚类结果，因为它对图中节点度的变化不敏感。 第三步：进行谱分解（特征分解） 对选定的拉普拉斯矩阵进行特征分解。假设我们要将数据聚成 \( k \) 个簇： 计算拉普拉斯矩阵 \( L \)（或 \( L_ {\text{sym}} \)、\( L_ {\text{rw}} \)）的 最小的 \( k \) 个特征值 及其对应的 特征向量 。 为什么是最小的k个特征值？ 对于一个无向加权图，拉普拉斯矩阵是半正定的，其特征值非负。最小的特征值（0）对应的特征向量是常数向量。第二个最小的特征值（称为代数连通度）对应的特征向量（称为Fiedler向量）给出了图的二划分。推广到k个簇，最小的k个特征向量包含了对图进行k划分的最优松弛解信息。 用这些特征向量构造一个新的特征向量矩阵 \( U \in \mathbb{R}^{n \times k} \)。 若使用 \( L \) 或 \( L_ {\text{sym}} \)，则直接取对应最小k个特征值的k个特征向量 \( u_ 1, u_ 2, ..., u_ k \) 作为 \( U \) 的列。 若使用 \( L_ {\text{rw}} \)，则取对应最小k个特征值的k个 右 特征向量。 对于 \( L_ {\text{sym}} \)，通常还需要对矩阵 \( U \) 的行进行标准化：设 \( U \) 的第 \( i \) 行为 \( y_ i \in \mathbb{R}^k \)，我们计算： \[ y_ i' = \frac{y_ i}{\|y_ i\|} \] 这使得新的点 \( y_ i' \) 位于一个 \( k \) 维的单位超球面上，可以改善后续K-means聚类的稳定性。 第四步：在低维空间进行聚类 现在，原始的每个数据点 \( x_ i \in \mathbb{R}^d \) 都被映射到了 \( k \) 维空间中的一个点 \( y_ i \in \mathbb{R}^k \)（即矩阵 \( U \) 的第 \( i \) 行）。在这个新的特征空间中，数据点之间的相似性结构被增强，不同簇之间的点更容易分离。 将集合 \( \{y_ 1, y_ 2, ..., y_ n\} \) 作为输入，使用 K-means聚类算法 将其划分为 \( k \) 个簇 \( C_ 1, C_ 2, ..., C_ k \)。 K-means的初始中心点选择（如K-means++）对最终结果有较大影响，通常需要多次运行以获得稳定结果。 第五步：将聚类结果映射回原空间 K-means在低维空间 \( \mathbb{R}^k \) 中得到的簇标签，直接对应了原始数据空间 \( \mathbb{R}^d \) 中数据点 \( x_ i \) 的簇标签。 如果低维空间中的点 \( y_ i \) 被分配到簇 \( C_ j \)，那么原始数据点 \( x_ i \) 就被分配到簇 \( j \)。 算法总结与关键点 输入 ：数据点 \( X \)，聚类数 \( k \)，相似度函数（如高斯核的 \( \sigma \)），图的构造方法（如全连接图或k-NN图），以及拉普拉斯矩阵类型。 过程 ： 构造相似度矩阵 \( W \)。 计算度矩阵 \( D \) 和拉普拉斯矩阵 \( L \)。 计算 \( L \) 的前 \( k \) 个最小特征值对应的特征向量，形成矩阵 \( U \)。 （可选）对 \( U \) 的行进行标准化。 对 \( U \) 的行向量运行K-means算法，得到k个簇。 输出 ：数据点 \( x_ i \) 的簇标签。 关键优势 ：相比K-means，谱聚类不需要假设数据簇是凸形或球形，只要数据点在特征空间中是“连接”的即可。它本质上是一种 基于图分割的聚类 。 主要挑战 ：参数选择（如 \( \sigma \)、k-NN中的k、聚类数k）对结果影响大，特征分解对于大规模数据集计算成本高，需要使用如Lanczos方法等近似技术。