aiwiki.page
中文
计算机 / 人工智能 / spectral-clustering

谱聚类

谱聚类利用相似度图的特征向量划分数据,能够发现原始特征空间中难以用简单几何边界分隔的群组。

20 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
无监督学习K均值聚类图论矩阵(数学)K近邻算法图拉普拉斯算子特征值与特征向量NP困难性谱聚类

谱聚类是一类无监督学习方法,通过分析表示观测对象之间相似度的矩阵的特征向量,将观测对象分组。它不直接在原始特征空间中划分簇,而是先构建加权图,将顶点映射到谱表示空间,再对这一表示进行划分,通常采用K均值聚类。当图能够反映群组内在的连通关系时,这种方法可以识别弯曲形状或相互交错形状等非凸群组。其结果在很大程度上取决于相似度和图连接的定义方式。

数学基础

将数据表示为图

给定观测对象 x1,…,xnx_1,\ldots,x_n,谱聚类构建一个无向加权图,其中顶点表示观测对象,边的权重表示相似度。这些权重构成对称的亲和矩阵 WW,其元素满足 wij≥0w_{ij}\geq 0。不存在的边对应权重为零。自连接权重 wiiw_{ii} 通常设为零。

一种常见的亲和度是高斯相似度:

wij=exp⁡(−∥xi−xj∥22σ2),i≠j,w_{ij} = \exp\left(-\frac{\lVert x_i-x_j\rVert^2}{2\sigma^2}\right), \qquad i\ne j,

其中,σ>0\sigma>0 决定距离尺度。较小的取值强调局部关系;较大的取值则使相距较远的观测对象也具有较高的相似度。

常见的图构建方式包括:

  • **全连接图:**为每对不同的观测对象赋予一个相似度权重。
  • **近邻图:**每个观测对象与指定数量的邻近观测对象相连。由于近邻关系可能不对称,通常通过保留近邻关系的并集或交集,将图对称化。
  • **邻域半径图:**仅当两个观测对象之间的距离小于某个阈值时,才在它们之间建立边。

构图所用的近邻数量与期望的簇数是两个不同的参数。使用近邻图也不意味着谱聚类属于K近邻算法中的分类方法:近邻图规定的是无标签观测对象之间的关系,而不是根据带标签的近邻来预测标签。

亲和度也可以来自网络连接、文档相似度或特定领域的度量。常规谱聚类假定亲和矩阵对称且非负;对于有向图和带符号的相似度,则需要修改其数学形式。

图拉普拉斯算子

顶点 ii 的度为

di=∑j=1nwij.d_i=\sum_{j=1}^{n}w_{ij}.

令 D=diag⁡(d1,…,dn)D=\operatorname{diag}(d_1,\ldots,d_n)。未归一化的图拉普拉斯算子为

L=D−W.L=D-W.

两种广泛使用的归一化形式为

Lsym=I−D−1/2WD−1/2L_{\mathrm{sym}} = I-D^{-1/2}WD^{-1/2}

和

Lrw=I−D−1W.L_{\mathrm{rw}} = I-D^{-1}W.

这些定义假定所有顶点的度均为正;对于孤立顶点,需要单独处理或明确规定其处理约定。

对于实向量 ff,有

fTLf=12∑i,jwij(fi−fj)2.f^\mathsf{T}Lf = \frac{1}{2}\sum_{i,j}w_{ij}(f_i-f_j)^2.

因此,这个二次型的值越小,对应函数在强连接顶点之间的变化就越小。这正是谱聚类的核心机制:与较小拉普拉斯特征值对应的特征向量,提供了在强连接群组内部变化缓慢的坐标。

特征值与特征向量还编码了图的精确连通结构。零特征值的重数等于连通分量的数量。对于未归一化的拉普拉斯算子,各连通分量的示性向量张成零特征空间。对于 LsymL_{\mathrm{sym}},对应的向量则是经过度加权的示性向量。当各分量之间存在弱连接,而非完全断开时,较小的非零特征值可能反映出近似的簇结构。

与图划分的联系

谱聚类可以由离散图划分问题的松弛推导而来。

对于不相交的顶点集 AA 和 BB,定义

cut⁡(A,B)=∑i∈A,  j∈Bwij,\operatorname{cut}(A,B) = \sum_{i\in A,\;j\in B}w_{ij},

并将集合的体积定义为

vol⁡(A)=∑i∈Adi.\operatorname{vol}(A)=\sum_{i\in A}d_i.

仅最小化割的权重,可能倾向于将某个连接较弱的顶点单独分离出来。平衡划分目标通过考虑簇的大小或体积来抑制这一倾向。

将图划分为 kk 个非空集合 A1,…,AkA_1,\ldots,A_k 时,两个重要的目标为

RatioCut⁡=∑r=1kcut⁡(Ar,Ar‾)∣Ar∣\operatorname{RatioCut} = \sum_{r=1}^{k} \frac{\operatorname{cut}(A_r,\overline{A_r})}{|A_r|}

和

Ncut⁡=∑r=1kcut⁡(Ar,Ar‾)vol⁡(Ar).\operatorname{Ncut} = \sum_{r=1}^{k} \frac{\operatorname{cut}(A_r,\overline{A_r})} {\operatorname{vol}(A_r)}.

这里,Ar‾\overline{A_r} 表示 ArA_r 的补集。比率割按顶点数量进行平衡;归一化割则按与顶点关联的边权总和进行平衡。

重要的平衡割问题具有NP难性。谱方法用实值向量替代离散的簇示性变量,从而得到可有效求解的松弛问题。具体而言,比率割的松弛形式为

min⁡HTH=Itr⁡(HTLH),\min_{H^\mathsf{T}H=I} \operatorname{tr}(H^\mathsf{T}LH),

其解由 LL 的 kk 个最小特征值所对应的特征向量构成。

归一化割的松弛形式可表示为

min⁡HTDH=Itr⁡(HTLH),\min_{H^\mathsf{T}DH=I} \operatorname{tr}(H^\mathsf{T}LH),

由此得到广义特征值问题

Lu=λDu.Lu=\lambda Du.

它也可以等价地转化为涉及 LsymL_{\mathrm{sym}} 的普通对称特征值问题。

这些松弛解释了该方法的计算结构,但通常无法恢复原始离散目标的精确最优解。将连续的特征向量转化为簇标签,还会引入进一步的近似。

主要算法变体

典型的谱聚类过程包含四个阶段:

  1. 构建亲和图。
  2. 计算拉普拉斯矩阵或相关的归一化矩阵。
  3. 提取少量特征向量,形成嵌入表示。
  4. 将嵌入坐标转化为簇标签。

矩阵、特征向量、归一化方式和最终划分规则的选择,构成了不同算法变体之间的区别。

未归一化谱聚类

计算 LL 的 kk 个最小特征值对应的特征向量,将它们按列组成矩阵 U∈Rn×kU\in\mathbb{R}^{n\times k},再对 UU 的行进行聚类。

这一变体源于比率割的松弛。当图中各顶点的度差异很大时,它可能表现不佳,因为其平衡簇大小的目标并未考虑这些度的差异。

随机游走归一化聚类

求解 Lu=λDuLu=\lambda Du,或者等价地,使用 LrwL_{\mathrm{rw}} 最小特征值对应的右特征向量。随后对所得特征向量矩阵的行进行聚类。

这种形式与归一化割密切相关。对于二分问题,可以通过对一个非平凡特征向量设定阈值来完成划分,而无须另行进行多维聚类。

对称归一化聚类

一种广泛使用的流程是计算 LsymL_{\mathrm{sym}} 的前 kk 个特征向量,将其作为 UU 的列,并将每个非零行归一化:

yi=Ui,:∥Ui,:∥.y_i=\frac{U_{i,:}}{\lVert U_{i,:}\rVert}.

然后用K均值方法对行向量 yiy_i 进行划分。这一步行归一化是 Ng–Jordan–Weiss 方法的一个标志性环节。

一种等价的形式是使用 D−1/2WD−1/2D^{-1/2}WD^{-1/2} 的最大特征值所对应的特征向量,因为这个矩阵等于 I−LsymI-L_{\mathrm{sym}}。

对于标准的多路归一化聚类,这 kk 个特征向量通常包含平凡特征向量。其他谱嵌入任务可能会舍弃它;这两种约定不应混为一谈。

解释与相关方法

随机游走

矩阵

P=D−1WP=D^{-1}W

是图上随机游走的转移矩阵。对于连通无向图,其平稳分布与顶点的度成正比。

一个有意义的簇,可以理解为随机游走在进入其他区域之前倾向于停留其中的区域。归一化割衡量的是相对于簇体积而言,随机游走离开各簇的倾向。这种解释将谱聚类与基于扩散的方法以及混合缓慢过程的研究联系起来。

几何与表征

谱聚类也是一种表征学习:它用从图中导出的坐标替代原始坐标。即使两个观测对象在原始坐标中相距很远,只要它们属于同一个连通结构,在这种表示中也可能变得接近。

例如,在原始平面中,两个相互交错的月牙形群组可能难以通过K均值方法分开。局部相似度图可以在每个月牙形内部建立较强的连接,同时仅在两个群组之间建立少量连接。这样,谱表示便可能使两个群组更容易分离。

这种关系使谱聚类与流形学习密切相关,尤其是拉普拉斯特征映射。不过,两者的目标不同:流形学习通常侧重于获得有用的低维表示,而谱聚类则利用这种表示来生成划分。

与核方法的关系

谱聚类与核方法有关,因为两者都可以通过成对相似度矩阵进行运算。某些图割目标与适当构造的加权核K均值目标等价。不过,非负的图亲和矩阵不一定是半正定核矩阵,谱聚类也不只是将普通K均值方法应用于任意核。

参数选择与数值表现

相似度尺度与预处理

与在标准谱聚类变体之间进行选择相比,图的构建方式往往影响更大。基于距离的亲和度会受到计量单位、无关变量和所选度量的影响。特征缩放或特定领域的相似度度量,都可能显著改变最终构建的图。

过于局部化的图可能碎裂为互不连通的部分。过密的图或过大的高斯带宽,则可能模糊有意义的分隔。局部尺度亲和度使用随邻域变化的带宽,以适应采样密度的差异,但也引入了自身的假设。

簇的数量

簇数通常预先给定。一种常见的启发式方法是考察按顺序排列的拉普拉斯特征值

0=λ1≤λ2≤⋯0=\lambda_1\leq\lambda_2\leq\cdots

并寻找 λk\lambda_k 与 λk+1\lambda_{k+1} 之间的显著间隙。这种特征值间隙可以支持将数据解释为 kk 个簇,但并不是通用的选择规则。噪声、群组重叠、密度不均以及构图参数,都可能改变特征谱。

稳定性与标签分配

特征向量的正负号可以任意选择,重特征值对应的特征空间也可以采用不同的标准正交基。在统一的正交变换下,这些不确定性本身不会改变嵌入后各行之间的欧氏距离。不过,如果所选特征值与未选特征值之间的间隙较小,选定的子空间就可能对扰动较为敏感。

最后的K均值阶段可能因初始化不同而产生不同结果。阈值划分、离散化方法以及其他舍入方案,也提供了分配标签的途径。

计算成本与可扩展性

谱聚类的计算成本可能很高,因为它处理的是观测对象之间的关系,而不只是各个对象自身的特征向量。

稠密亲和矩阵需要 O(n2)O(n^2) 的存储空间;直接计算成对距离所需的工作量随观测对象数量呈二次增长,同时还取决于特征维度。对稠密矩阵进行完整特征分解的时间复杂度约为 O(n3)O(n^3)。

实际实现通常只计算少量特征向量。稀疏邻域图和迭代特征值求解器可以显著减少存储需求和计算量。其成本取决于图的稀疏程度、特征值间隙、数值容差以及所需特征向量的数量;不存在一个能够描述所有实现的统一运行时间界限。

面向大规模数据的方法包括:

  • 稀疏图构建和近似近邻搜索;
  • 地标法和 Nyström 近似;
  • 图粗化和多层次划分;
  • 分布式特征值求解器;
  • 通过学习近似谱嵌入。

这些方法可能改变实际使用的图或嵌入表示。因此,它们的准确性取决于能否保留与划分相关的结构。

应用与局限

谱聚类已应用于图像分割、文档分组、网络社区发现、运动分割和关系数据分析。在计算机视觉中,亲和度可以综合外观和空间邻近性。在文档分析中,亲和度可以表示稀疏文本向量或学习得到的嵌入之间的相似度。

其主要局限包括:

  • **依赖相似度设计:**划分反映的是所选图的结构,而不是独立于表示方式的客观分组。
  • **对噪声和度不均衡敏感:**离群点、弱连接和不均匀采样可能扭曲特征向量,或产生非预期的划分。
  • **可扩展性有限:**亲和度构建和特征向量计算可能占据主要的内存和运行时间开销。
  • **直推式结构:**标准形式只对用于构图的观测对象进行聚类。为新观测对象分配簇标签需要扩展方法,例如样本外嵌入或单独训练的预测规则。
  • **硬划分:**标准变体将每个观测对象分配到一个群组,因而可能无法表示重叠结构或层次结构。
  • **不保证适用于任意形状:**能够分离某些非凸群组,并不意味着能够可靠地恢复任意形状或密度下的群组。

历史发展

谱聚类起源于谱图论和数值图划分。米罗斯拉夫·菲德勒在20世纪70年代的工作,确立了图连通性与拉普拉斯特征值之间的重要联系。第二小拉普拉斯特征值对应的特征向量,后来成为谱二分法的核心。

在计算机视觉领域,史建波与吉滕德拉·马利克于2000年发表的归一化割研究,将图划分与基于感知的图像分割联系起来。随后,吴恩达、迈克尔·乔丹和亚伊尔·韦斯在21世纪初提出了一种影响广泛的归一化谱聚类方法。这些进展推动谱聚类成为机器学习中的标准方法之一,将图割目标、谱嵌入和传统聚类流程联系在一起。