引用本文

罗辉, 韩纪庆. 基于灵活平衡约束的图聚类方法. 自动化学报, 2023, 49(4): 778−789 doi: 10.16383/j.aas.c200144

Luo Hui, Han Ji-Qing. Graph clustering based on flexibly balanced constraint. Acta Automatica Sinica, 2023, 49(4): 778−789 doi: 10.16383/j.aas.c200144

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200144

关键词

图聚类，图分割，平衡约束，紧松弛 

摘要

现有的图聚类方法主要存在两方面的问题, 一是对各个类规模一致的假设, 在许多实际应用中并不成立; 二是在处理多类聚类问题时, 其所常借助的递归技术或启发式算法会影响聚类的性能. 为此, 本文提出一种基于灵活平衡约束的多类图聚类方法. 其能够覆盖从绝对平衡约束到无平衡约束的范围, 可同时处理类别规模一致和不一致的问题. 为有效求解新方法中的参数, 进一步提出一个紧松弛方法来使所提出的图聚类方法不仅易于求解, 且在处理多类聚类问题时不必依赖递归技术, 而能直接得到聚类结果. 另外, 本文还给出一种实现松弛图聚类的有效求解算法. 在合成数据和真实数据上的实验结果表明, 所提出的方法具有良好的性能.

文章导读

聚类是数据挖掘领域中应用最广泛的技术之一. 多年来, 研究人员提出了许多不同的聚类算法, 例如K均值聚类[1]、谱聚类[2-3]、非负矩阵分解[4]和子空间聚类[5-6]. 其中, 谱聚类是一种颇为流行的聚类方法. 它求解简单、聚类性能好, 更重要的是, 可以看作是对图聚类(图划分、图切割)的一种松弛[2], 因而具有很强的理论支撑.

在图聚类方法中, 通常将一个两类(多类)聚类问题转换为一个两路(多路)图分割问题. 图分割问题主要研究如何根据一定的条件, 将图中的顶点划分成两个或多个点集群. 其处理的数据类型是图数据, 图中的每一个顶点表示一个需要进行聚类的样本点, 每一条边则表示顶点与顶点间的依赖关系. 而对于非图数据, 可先根据点与点间的相似性来构造一个邻域图, 然后再运用图聚类方法进行处理. 构造邻域图的方法有很多, 比如γ-邻域图和K近邻图[2].

现有的图分割方法大都遵循最小切割(Minimun cut, mincut)准则[7], 即要求不同集群之间的边权值之和最小. 此外, 为了避免产生非常不平衡的集群分布, 例如将单独一个顶点划分成一个集群, 这些方法还都使用平衡函数对mincut准则进行正则化. 目前, 比例割(Ratio cut, RCut)模型[8]和归一化割(Normalized cut, NCut)模型[9]是两种既简单又直接的图分割方法. 它们的不同之处在于使用了不同的平衡函数, RCut的平衡函数约束各集群的规模, 而NCut的平衡函数约束各集群内部的紧密程度.

在图聚类方法中, 平衡函数的选择是任务依赖的. 在一些实际应用中, 任务要求各集群的规模必须是平衡或近似平衡的. 如在科学计算中, 每个顶点代表一部分需要被计算的信息, 每条边表示这些信息间的依赖关系. 对信息进行平衡的划分, 可使计算网络中的每台机器都进行同等规模的计算, 从而确保并行计算的高效性. 然而, RCut和NCut方法并不能很好地处理这类需要进行平衡聚类的任务. 为此, 文献[10]提出了Cheeger比例割(Ratio Cheeger cut, RCC)方法和Cheeger归一化割(Normalized Cheeger cut, NCC)方法, 来对不平衡的图分割施加更强的惩罚, 从而得到更平衡的集群[11-12]. 此外, 还可以使用一些平衡函数, 如截断函数和硬平衡函数, 来达到施加不同级别平衡约束的目的[13]. 而在其他一些应用中, 例如图像分割, 其存在着分布不均衡的集群, 采用RCut和NCut方法反而会导致施加的平衡约束太强. 为此, 文献[14]提出了一组平衡函数, 它们由一个参数p(p>1)取不同的值来得到. 通过选择p>2的一些平衡函数, 可以对不同集群实施强度弱于RCut/NCut (p=2)的平衡约束. 文献[15]提出了一组平衡约束更弱的函数, 它们由参数τ(0<τ<2)取不同的值来得到, 可以覆盖从无平衡约束的mincut准则到RCut/NCut准则的平衡约束.

平衡函数约束的图切割方法通常会导致非确定性多项式(Nondeterministic polynomially, NP)难题. 在实际应用中, 需要先对这样的优化问题进行松弛, 即在连续空间中对原始离散优化问题进行重新表述, 以得到一个方便求解且与原问题相近的新问题. 它们的近似程度也反映了所使用的松弛方法的松紧程度. 文献[2]证明了对RCut模型的松弛可以得到基于未归一化图拉普拉斯算子的谱聚类方法, 对NCut模型的松弛会得到基于归一化图拉普拉斯算子的谱聚类方法. 尽管如此, 文献[14]指出, 通过谱聚类方法求得的解并不能保证也是原始图切割问题的最优解. 一般来说, 使用太松的松弛方法得到的近似解和原始问题的解会存在很大的差异. 如何减小近似解与最优解间的差距, 一直是松弛方法研究中的主要问题. 文献[14]研究了Cheeger cut模型与图p-Laplacian之间的关系. 通过选择参数p=1, 可以实现对Cheeger cut模型的紧松弛[16]. 之后, 文献[13]将这一结果推广到不同平衡约束的图切割问题中, 得到了各自的紧松弛模型. 此外, 文献[17]提出了利用ℓ1范数作为距离度量的方法, 分别实现了对RCut和NCut模型的紧松弛. 然而, 这些工作的初衷都只是解决两路图分割问题, 要处理多路图分割问题, 只能依赖于贪婪递归技术. 需要注意的是, 通过递归技术的多路扩展往往不能得到理想的多类聚类, 且会带来较大的计算复杂度. 为此, 文献[11]和文献[12]都将两路问题中的Cheeger cut模型扩展到了多路问题中, 两者的区别在于文献[11]使用的平衡函数是非对称的, 而文献[12]中是对称的, 这使得它们对各集群的大小所施加的约束不同. 文献[18]提出了一个一般化的求解多路图分割问题的方法, 可以用来求解包括RCut、RCC和非对称RCC (Asymmetric RCC, ARCC)问题, 以及它们各自对应的规范化图分割问题. 文献[19]提出将ℓ2,1-范数用于距离测量和归一化项, 把文献[17]中的一维谱嵌入扩展到多维谱嵌入, 从而实现了多类聚类.

受文献[14-15]的启发, 本文提出了一种新的灵活平衡多路图分割(Flexible multi-way graph cut, FMC)模型. 首先, 针对两路图分割问题, 设计了一系列的平衡函数, 并且证明了传统的图分割方法是 FMC的特例. 接着进一步将两路图切割模型推广到了多分类的场景. 在文献[11]的基础上, 提出一种非对称的平衡约束模型. 与文献[15]相同, 其可通过选择合适的模型参数, 来使得所施加的平衡约束弱于 RCut和NCut方法. 与文献[15]不同的是, 所提出的模型还可以选择特定的模型参数, 来使得所施加的平衡约束强于RCC和NCC. 因此, 本文的模型具有更广泛的应用范围. 最后, 针对模型实现时的NP难题, 提出了一个紧的松弛方法, 并开发相应的算法来解决由此产生的最小化问题. 通过求解该松弛模型, 可以直接得到多分类结果, 而不需要利用递归技术对两路模型进行扩展. 尽管本文的算法基于文献[18]中的工作, 但与[18]不同, 后者只能解决平衡函数为凹函数的松弛问题, 而本文的算法既可以解决凹函数的松弛问题, 也可以解决非凹函数的松弛问题. 为了验证FMC的有效性, 在合成数据集和真实数据集上进行了大量的实验. 结果表明, 所提出的优化算法在求解多路图切割问题方面优于其他对比方法. 而且在聚类性能方面, 与几种基于图分割的聚类方法和其他类型的聚类方法相比, 本文的方法也具有竞争力.

图 1  函数Φp(v)在不同参数p时的示意图

图 2  函数Ψr(v)在不同参数r时的示意图

图 4  合成数据及其邻接图

本文针对多类聚类问题, 提出了一种基于灵活平衡约束的图聚类方法FMC, 能够实现从无平衡约束到严格平衡约束的图聚类. 在聚类方法的实现方面, 提出了一种紧的连续松弛方法, 将原问题中的离散集合函数替换成与之等价的Lovasz扩展. 通过选择一组合适的约束条件, 避免了病态的连续解, 从而保证能从连续解中恢复离散问题的解. 此外, 还提出了一种新的优化算法来解决非凸、非光滑的连续优化问题. 在合成数据集上对FMC在不同平衡约束下的性能进行了验证, 结果表明, FMC通过选择不同的参数r能实现不同的平衡约束, 从而影响聚类结果. 在20个真实数据集上对FMC的聚类性能和算法求解的准确性进行了验证, 结果表明FMC在大部分数据上的聚类性能比传统方法的更好, 且得到的解也最优. 虽然FMC的聚类性能优于其他模型, 但这些结果都是在不同参数r上的最优性能, 如何进行模型选择还需要进一步探讨和研究.

作者简介

罗辉

哈尔滨工业大学计算机科学与技术学院博士研究生. 2014年获贵州大学通信与信息系统专业硕士学位. 主要研究方向为智能语音处理技术和模式识别. 本文通信作者.E-mail: luohui0216@163.com

韩纪庆

哈尔滨工业大学计算机科学与技术学院教授. 1998年获哈尔滨工业大学计算机科学博士学位. 主要研究方向为智能语音处理技术和音频信息的智能处理. E-mail: jqhan@hit.edu.cn