南京大学提出用于聚类的最优间隔分布机

在这篇题为《Optimal Margin Distribution Clustering》的论文中,南京大学周志华教授、张腾博士提出了一种新方法——用于聚类的最优间隔分布机(Optimal margin Distribution Machine for Clustering/ODMC),该方法可以用于聚类并同时获得最优间隔分布。在 UCI 数据集上的大量实验表明 ODMC 显著地优于对比的方法,从而证明了最优间隔分布学习的优越性。

聚类是机器学习、数据挖掘和模式识别中的一个重要研究领域,其目标是分类相似的数据点。它催生出了包括信息检索、计算机视觉、生物信息学等在内的大量新研究,并且不同的聚类算法已被提出超过十年(Jain and Dubes 1988; Xu and Wunsch 2005; Jain 2010)。

最近有一种称为最大间隔聚类(MMC/maximum margin clustering)的方法,它基于支持向量机的大间隔启发(Cortes and Vapnik 1995; Vapnik 1995)。对于好的聚类方法而言,当标签分配到不同簇时,SVM 在该数据上可以得到最大化的最小间隔。由于形式化成的极大极小问题涉及用集合 {+1, −1} 标记每一个实例,它也就不再是一个凸优化问题,而是一个更难处理的混合整数规划(mixed-integer programming)。从那时起,为解决这一问题做了大量努力,这些努力可被分为两类。第一类通过不同的凸松弛技术(Xu et al. 2005)首次将其松弛为凸半定规划(semi-definite programming/SDP),其中一种带有线性约束的正半定矩阵被用于逼近标签外积矩阵。很快,Valizadegan 和 Jin (2006) 引入一个新的形式化,其变量数明显减少,尽管它依然是一个 SDP 问题。最后,Li et al.(2009; 2013)提出一个比 SDP 更紧致的极大极小松弛,并可通过迭代地生成最违反的标签,然后借助多核学习整合它们而被解决。

第二类通过非凸优化的变量直接优化原始的问题。这些案例包括了交替优化(Zhang, Tsang, and Kwok 2007; 2009),其中通过连续地寻找标签和优化一个支持向量回归(SVR)进行聚类;以及 CCCP(Zhao, Wang, and Zhang 2008; Wang, Zhao, and Zhang 2010),其中非凸目标函数或约束被表达为两个凸函数之间的差值;后者进一步替换成其线性近似,因此完全是凸的。此外,很多研究尝试将 MMC 扩展到更加普遍的学习环境。例如,Zhou 等人 2013 年假设数据具有隐变量并开发了 LMMC 框架。Niu 等人 2013 年的研究提出了 MMC 的另一种实现,称为最大容量聚类(maximum volume clustering,MVC),其在理论的意义上更重要。在 2016 年,MMC 的增量版本也被提出(Vijaya Saradhi and Charly Abraham 2016)。

上述的 MMC 方法全部基于大间隔理论,即尝试最大化训练实例的最小间隔。然而,间隔理论的近年研究(Gao and Zhou 2013)表明最小间隔的最大化并不必然导致更好的性能,而优化间隔分布才是关键。受此启发,Zhang 和 Zhou (2014; 2016; 2017) 提出了最优间隔分布机(optimal margin distribution machine,ODM),相比基于大间隔的方法可以获得更好的泛化性能。之后,Zhou 和 Zhou(2016)将该思想扩展为可利用无标签数据和控制不均衡误分类代价的方法。最优间隔分布学习的成功预示着在 MMC 方法上还存在很大的提升空间。

在本文中,作者提出了一种新的方法——ODMC(Optimal margin Distribution Machine for Clustering,用于聚类的最优间隔分布机),该方法可以用于聚类并同时获得最优间隔分布。特别地,他们利用一阶和二阶统计量(即间隔均值和方差)描述间隔分布,然后应用 Li 等人 2009 年提出的极小极大凸松弛法(已证明比 SDP 松弛法更严格)以获得凸形式化(convex reformulation)。作者扩展了随机镜像下降法(stochastic mirror descent method)以求解因而产生的极小极大问题,在实际应用中可以快速地收敛。此外,我们理论上证明了 ODMC 与当前最佳的割平面算法有相同的收敛速率,但每次迭代的计算消耗大大降低,因此我们的方法相比已有的方法有更好的可扩展性。在 UCI 数据集上的大量实验表明 ODMC 显著地优于对比的方法,从而证明了最优间隔分布学习的优越性。


图 1:随机镜像下降方法的一次迭代的图示。


算法 1:用于 ODMC 的随机镜像下降。


表 1:实验数据集的统计。


图 2:IterSVR、CPMMC、LG-MMC、ODMC 的单次迭代的平均时间消耗。


表 2:在 24 个 UCI 数据集上的聚类准确率(Acc)和 Rand Index(RI)的对比。粗体表示在该数据集上的最佳性能结果。黑点表示 ODMC 方法显著地优于对比的方法(配对 t-检验在 95% 的显著性水平)。最后两行总结了 ODMC 相对其它方法的优/平/劣的数量。GMMC 在某些数据集上无法在两天内返回结果。


下一步工作

在未来,作者将应用重要性采样以进一步加速 ODMC 方法,并将其扩展到其它的学习环境,即半监督学习。

论文:Optimal Margin Distribution Clustering


论文链接:https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/aaai18odmc.pdf

最大间隔聚类(Maximum margin clustering,MMC)基于支持向量机(SVM)的大间隔启发,相比传统的聚类方法有更高的准确率。可以直觉地理解为,对于一个足够好的聚类方法,当给不同的聚类分配标签时,SVM 可以在该数据上得到很大的最小间隔。然而,最近的研究揭示出最小间隔的最大化并不必然导致更好的性能,而优化间隔分布才是关键。在本文中,我们提出了一种新的方法——用于聚类的最优间隔分布机(Optimal margin Distribution Machine for Clustering,ODMC),该方法可以用于聚类并同时获得最优间隔分布。特别地,我们利用一阶和二阶统计量(即间隔平均和方差)描述间隔分布,并扩展了一种随机镜像下降法(stochastic mirror descent method)以求解因而产生的极小极大问题。此外,我们理论地证明了 ODMC 结合当前最佳的割平面(cutting plane)算法能得到相同的收敛速率,但每次迭代的计算消耗大大降低,因此我们的方法相比已有的方法有更好的可扩展性。在 UCI 数据集上的大量实验表明 ODMC 显著地优于对比的方法,从而证明了最优间隔分布学习的优越性

理论理论论文周志华AAAI 2018AAAI聚类
返回顶部