用于谱聚类的带平滑图核回归方法

《Image and Vision Computing》：Kernel regression with smooth graph for spectral clustering

　　苗晓宇|蒋爱民|徐宁|史新桐 中国南通江苏航运职业技术学院交通工程研究所

摘要
谱聚类在诸多领域中发挥着重要作用。近年来，基于图的谱聚类方法的发展揭示了图结构对聚类结果的影响。本文提出了一种新的基于图的谱聚类框架，该框架将样本的图结构与核矩阵相结合，以实现连续标签的生成。与现有的先进方法如带核的结构化图学习不同，我们所提出的方法将样本和连续标签视为同一底层图上的节点，并通过核回归估计的潜变量将二者连接起来。此外，该框架还将样本的核矩阵纳入谱聚类部分，以此在最大化组间差异的同时最小化组内差异，这一做法与费希尔判别分析的原则一致。同时，为了减少k均值算法带来的干扰并提升方法的稳健性，该方法还保持了连续标签的非负性特征。我们还提出了高效且实用的数值方法来解决相关的优化问题。在多种数据集上的实验结果表明，所提出的算法性能优于现有先进方法。

引言
在现代数据分析和处理过程中，通常会涉及大量结构化数据，而这些数据与其拓扑结构之间的内在联系蕴含着重要的信息。图学习方法的出现为探索数据之间的关系和结构特性提供了有效途径。因此，图结构已被广泛应用于机器学习的各个领域，如计算机视觉[1][2]、知识图谱[3]、图像处理[4][5]以及信号处理[6][7]。近年来，研究人员提出了多种图学习模型，以学习具有不同特性的图结构，从而解决各种任务。例如，Egilmez等人[8]将图拉普拉斯矩阵视为协方差矩阵的逆矩阵，并通过高斯马尔可夫随机场模型[9]将二者联系起来。Dong[10]基于相邻节点具有相似信号的假设，提出了平滑图模型，这一模型目前颇为流行。Zhang和Lu[11][12]则利用数据的自表示特性，即来自同一子空间的所有样本之间存在线性相关性，提出了自表示图学习模型。

本文主要研究基于图的谱聚类算法。聚类的任务在于找出相似样本的子集并将它们归为一组，使得同一簇内的样本彼此之间具有高度相似性，而不同簇的样本则相似性较低[13][14]。图结构能够很好地体现样本之间的相似性，这与聚类的目标十分契合。基于图的谱聚类算法分为两个步骤：首先，通过图学习模型学到的拉普拉斯矩阵生成连续标签；随后，再利用k均值方法将这些连续标签转换为离散标签。已有不少研究致力于解决第一阶段的问题，即通过学习邻接矩阵来编码样本之间的关系。例如，Nie[15]和Wu[16]通过一种自适应机制学习邻接矩阵，该机制可以控制每个节点的邻居数量，进而分别发展出了具有自适应邻居的聚类方法和结构化图学习方法。此外，基于结构化双随机图的聚类方法[17]引入了双随机条件，并采用优化算法同时满足所有条件，从而提高了对噪声的抵抗能力。第二阶段的任务则是建立连续标签与离散标签之间的联系。离散非负谱聚类方法[18]通过线性回归以及对连续标签进行投影变换来估计离散标签。Yang[19]为多视图聚类任务开发了一种快速的坐标下降算法，该算法利用增量矩阵记录每次迭代中样本标签更新所带来的变化，从而高效地得到离散标签。另有研究[20]利用二分图分解技术，直接应用非负矩阵分解方法来高效获得离散簇。此外，还有研究[21]提出了一种一步式多视图聚类方法，该方法通过自适应的低秩锚图学习模型直接学习软指示矩阵。

近期，有一种名为带核的结构化图学习的新图学习框架被提出，用于解决聚类和半监督分类任务[22]。SGK框架旨在学习一个全面的图结构，以便生成能够有效捕捉样本局部和全局结构的“优质”连续标签。具体而言，该框架通过样本本身的平滑性来探索样本的局部结构，而样本的高维空间映射的自表达性则有助于揭示样本的全局结构。此外，该框架还将核表示方法纳入其中，从而无需直接指定映射函数。为进一步提升SGK框架在实际任务中的性能，研究者们又根据核函数的不同构建方式，分别提出了单核结构化图学习方法和多核结构化图学习方法。

传统的基于图的聚类算法，如SGSK和SGMK，是通过对拉普拉斯矩阵进行特征值分解来生成连续标签的。这些方法主要侧重于放大不同簇之间样本的差异，却往往忽视了减少同一簇内样本的差异性。此外，SGSK和SGMK还利用核矩阵来表示高维空间中样本映射对应的潜变量之间的关系。但从数值上看，核矩阵主要反映的是样本之间的关联，尤其是当使用一些简单的核函数（如线性核、高斯核[23]以及多项式核）时。另外，这两种方法在得到连续标签后仍需借助k均值算法来生成离散标签，而这往往会导致大量信息的丢失。

本文提出了一种新的图聚类框架，该框架结合了费希尔判别分析原理[24]与核回归方法[25][26]，以此解决上述问题。在该框架中，我们引入潜变量来连接样本与连续标签，并构建相应的映射函数，以捕捉样本与连续标签之间的非线性关系。与SGK框架不同的是，所提出的框架认为样本、潜变量以及连续标签是由同一图上不同节点通过不同的映射生成的，因此连续标签的获取可以基于样本和潜变量的图结构。由于聚类任务属于无监督学习任务，本文还通过具有更强局部结构信息捕捉能力的平滑图学习模型，确保图中这三个组成部分的一致性。本文的主要贡献可总结如下：
• 本文提出了一种新的基于图的谱聚类模型，该模型通过同时利用图拉普拉斯矩阵和核矩阵，解决了传统方法仅关注簇内相似性而忽视簇间差异的问题。
• 通过引入通过核回归估计的潜变量来连接样本与连续标签矩阵，本文基于样本、潜变量以及连续标签在拓扑结构上具有一致性这一假设，提出了一种新的基于图的谱聚类框架。
• 为消除将连续标签转换为离散标签过程中可能出现的不稳定性，本文在框架中对连续标签施加了非负性约束，并提出了一种新的基于图的谱聚类算法。
• 非负性约束的引入使得该算法转变为一个具有挑战性的非凸联合学习问题，为此我们采用了交替方向乘子法[27]来解决这一问题，该方法通过交替更新各个变量和拉格朗日乘子来实现优化。

本文的结构如下：第2节首先回顾了谱聚类领域的一篇经典相关工作，即比率切割算法[28]，随后将重点介绍SGSK和SGMK方法。第3节首先介绍一种新的谱聚类算法，接着介绍所提出的框架及其改进算法。同时，本文还设计了交替优化算法和交替方向乘子法来解决由此产生的问题。第4节通过多组真实世界数据进行的实验结果，验证了所提算法的性能。最后，第5节对全文进行总结（见表1）。

片段摘录
谱聚类
给定一个数据矩阵X=x1,x2,…,xN?∈RN×D，聚类的目标是根据特定标准将样本xi划分为c个组Cmm=1c。在实际应用中，常用的标准是要求不同组内的样本存在显著差异，而同一簇内的样本则应具有极高的相似性。因此，原始的谱聚类问题可表述为：minYTrY?LYs.t.yi∈{0,1}c,?i，其中Y=y1,y2,…,yN?∈RN×c为标签矩阵（即yi∈{0,1}c）。

费希尔比率切割算法
在一些传统的谱聚类算法中，例如比率切割算法，其重点在于最大化簇间的差异，而忽视了减少同一簇内样本的差异性。然而，根据费希尔判别分析的原则，理想的谱聚类算法还应能够将相似的样本归入同一簇。基于这一思路，我们提出了费希尔比率切割聚类算法。该算法对应的问题可表述为：minH,SFH,Ss.t.H?H=Ic,S??1=1,S∈A,L=D?S+S?2,D=

实验设置
为验证所提出的聚类算法的有效性，本节介绍了使用文献[22]中提及的大部分数据集进行的实验。为便于比较，本文采用了标准聚类精度和归一化互信息这两种广为认可的评估指标来衡量所提算法的性能。为便于理解，这两项指标的定义如下：ACC=1N∑i=1Nδmapl?i,li，NMI=∑i=1c∑i=1cni

结论
本文首先基于费希尔判别分析原则提出了FRcut模型，该模型旨在最大化聚类样本的组间差异，同时最小化组内差异。随后，我们将FRcut与SGSK以及核回归方法相结合，提出了一种名为KRSGF的新型基于图的谱聚类框架。在该框架中，我们利用核回归建立了样本与潜变量之间具有高度可解释性的映射关系。另一方面，利用图结构的特性……

CRediT作者贡献说明
苗晓宇：撰写——初稿、方法论、形式分析、概念设计。蒋爱民：撰写——审稿与编辑、方法论。徐宁：监督、验证。史新桐：数据整理、形式分析。

利益冲突声明
作者声明不存在任何可能影响本文研究工作的已知财务利益或个人关系。

致谢
本研究部分得到了南通市自然科学基金的支持，项目编号为JCZ202311。