Skip to content
返回搜索结果

谱聚类

提出者
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
年份
2002
类型
Graph-based clustering (spectral method)

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

谱聚类(Spectral Clustering)是一种基于图的无监督学习算法,由 Ng、Jordan 和 Weiss 于 2002 年正式提出。该算法首先将数据点映射到一个低维的特征空间,该空间由相似性图的拉普拉斯矩阵导出,然后再应用 k-means 算法。这种谱嵌入使得恢复任意形状的簇(如环状、新月形、交织螺旋形)成为可能,而基于欧氏距离的方法在分离这些簇时常常会失败。

方法背后的直觉

标准的 k-means 通过直线距离对空间进行划分,因此只能找到凸的、大致呈球形的簇。谱聚类通过首先将数据视为一个网络来绕过这一限制:每个点是一个节点,节点之间的边带有反映两点相似度的权重。簇对应于网络中内部连接密集但与其他部分连接稀疏的区域。图的拉普拉斯矩阵编码了这种连通性结构,其最小的特征向量充当了一个平滑的坐标系,能够拉伸数据,使得即使在原始空间中相互缠绕的簇在新的坐标系中也彼此远离。然后,在该新坐标系中执行一个简单的 k-means 步骤即可清晰地分离它们。

历史学

谱聚类的理论基础可以追溯到 Fiedler 1973 年关于图连通性和代数连通性特征值的工作。Shi 和 Malik (2000) 通过他们提出的用于图像分割的归一化割(normalized-cuts)标准将该方法引入计算机视觉领域。Ng、Jordan 和 Weiss (2002) 在 NIPS 会议上提出了一个清晰、通用的算法——即现在最常被引用的算法——并附带了扰动理论分析,解释了该方法何时以及为何有效。Von Luxburg 于 2007 年在 Statistics and Computing 期刊上发表的教程统一了各种相互竞争的表述,阐明了拉普拉斯矩阵归一化的作用,并成为从业者的标准参考。谱聚类现已在机器学习课程中占据核心地位,并且仍然是一个活跃的研究课题,在可扩展的近似方法、鲁棒核以及图和流形上的扩展方面都有持续的研究工作。

何时使用

谱聚类特别适用于数据中的簇呈非凸、非线性可分或通过细桥连接(欧氏划分方法无法检测)的情况——常见的例子包括环状簇、交织螺旋和图像分割。当可以有意义地计算点之间的成对相似性(无论是通过原始特征上的核函数还是通过预先提供的亲和力矩阵)并且簇的数量 k 已知或可以通过特征值间隙启发式方法估计时,该方法是适用的。该方法对簇形状没有分布假设。实际限制包括内存需求与点数成二次方关系(对于完整的亲和力矩阵)以及特征值分解的立方时间复杂度,这使得标准方法对于超过约 10,000 个点的数据来说成本高昂。近似方法(如 Nystrom 方法、稀疏图、随机 SVD)可以将其应用范围扩展到更大的数据集。

局限与注意事项

  • 构建完整的 n×n 亲和力矩阵需要 O(n^2) 的内存和 O(n^3) 的特征值分解时间,这使得朴素算法对于大型数据集不可行。
  • 结果对核带宽 sigma 的选择以及图的构建策略敏感;选择不当可能导致簇合并或分裂。
  • k-means 在谱嵌入中的初始化引入了随机性;不同的运行可能产生不同的划分。
  • 如果不进行仔细的核选择,无法很好地扩展到非常高维的特征空间。
  • 仅提供簇标签;它不提供生成模型,也没有对新点的自然样本外扩展方法。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 检测任意形状的簇,包括 k-means 和高斯混合模型无法处理的非凸和非线性可分配置。
  • 可以操作于任何成对相似性矩阵,而不仅仅是欧氏距离,使其适用于图、字符串和其他结构化数据。
  • 特征值间隙启发式方法为选择簇的数量 k 提供了一个原则性的、数据驱动的指导。
  • 基于丰富的谱图理论,能够对收敛性和簇质量进行形式化分析。
  • 概念简单,易于使用标准的线性代数库实现。

应用

  • 图像分割:根据像素级特征相似性将像素或超像素划分为感知上连贯的区域。
  • 社交和生物网络中的社群检测,其中成对连通性而非特征向量定义了结构。
  • 生物信息学:按表达谱相似性对基因或蛋白质进行分组,其中表达簇在基因空间中很少是凸的。
  • 自然语言处理:使用语义相似性核对文档或句子进行聚类。
  • 计算机视觉:运动分割和点云划分,其中簇边界不规则。
  • 探索性数据分析:在应用验证性方法之前揭示不明显的簇结构。

使用方式

使用方式

1

根据数据构建一个成对相似性(亲和力)矩阵 W。最常见的选择是高斯(RBF)核,它为邻近的点对分配高权重,为距离较远的点对分配接近于零的权重。带宽参数 sigma 控制相似度随距离衰减的速度;正确选择它至关重要。或者,也可以使用 k-近邻图来表示大型数据集的稀疏表示。

公式
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

度矩阵 D 是一个对角矩阵,其第 i 个对角线元素是 W 的第 i 行(或第 i 列)之和。从 W 和 D 可以形成归一化的(对称)图拉普拉斯矩阵 L_sym。该矩阵捕捉了相似性图的完整连通性结构;其特征值谱揭示了数据包含多少自然簇以及它们的分离程度。

公式
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

计算 L_sym 对应于 k 个最小特征值的 k 个特征向量。这些特征向量构成了嵌入矩阵 U 的列,U 的行数等于数据点的数量。在这个 k 维的谱空间中,即使原始特征空间中的点相互交织,属于同一簇的点也会被拉近。

公式
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

将 U 的每一行除以其欧氏范数,将嵌入点投影到单位超球面上。这种由 Ng、Jordan 和 Weiss 引入的归一化消除了特征向量之间不相关的尺度差异,并确保后续的 k-means 步骤关注嵌入的角向结构而非幅度。

公式
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

将标准的 k-means 聚类应用于归一化嵌入矩阵 T 的行。由于谱嵌入已经解开了簇的几何结构,即使对于非凸簇形状,k-means 也能找到有意义的划分。然后将簇标签映射回原始数据点。

常见陷阱

  • 在没有原则性的交叉验证或自适应调整的情况下选择 sigma;过小的带宽会使图断开连接,而过大的带宽会合并不同的簇。
  • 忽略了在 k-means 之前对亲和力矩阵行进行归一化(Ng 等人提出的行归一化步骤对于稳定性至关重要)。
  • 忽略特征值间隙:使用固定的 k 而不检查特征值谱,常常导致欠分割或过分割。
  • 在没有切换到近似或稀疏变体的情况下,将完整算法应用于包含数万个点的数据集。
  • 混淆未归一化(L = D - W)和归一化(L_sym, L_rw)的拉普拉斯矩阵,这可能导致簇分配发生实质性变化。

常见问题

如何选择簇的数量 k?

特征值间隙启发式方法是标准的指导:按升序计算归一化拉普拉斯矩阵的特征值,并寻找连续特征值之间的最大间隙。该间隙出现的索引指示了自然簇的数量。当特征值间隙不明确时,基于稳定性的方法——运行算法处理多个 k 值并比较不同扰动下的簇分配——可以提供帮助。

如何设置高斯核带宽 sigma?

一种常见的启发式方法是数据集中成对距离的中位数,或一种近邻自适应方案(Zelnik-Manor & Perona, 2004),该方案为每个点分配局部带宽。实践中,应通过检查所得亲和力图的连通性来验证 sigma:每个点应至少有几个高权重邻居,并且图不应分裂成孤立的组件。

为什么行归一化步骤是必需的?

拉普拉斯矩阵的特征向量在尺度上可能存在显著差异。如果不将嵌入矩阵的每一行归一化为单位长度,k-means 步骤可能会被具有大模的特征向量主导,而忽略信息量大但模较小的分量。Ng、Jordan 和 Weiss 提出的行归一化将所有点映射到单位球面上,使得 k-means 响应嵌入的角向几何结构。

谱聚类能处理非常大的数据集吗?

在其朴素形式下不能,因为它需要 O(n^2) 的内存和 O(n^3) 的特征值分解时间。对于大的 n,标准的解决方案包括:构建稀疏的 k-近邻图而不是完整的亲和力矩阵;使用 Nystrom 近似从子样本估计特征向量;或应用随机 SVD。这些近似方法以较低的成本恢复了大部分精度。

相关方法

参考文献

  1. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.

    打开出版物文献
    已复制。
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    打开 DOI 文献
    已复制。
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    打开 DOI 文献
    已复制。