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

2018 年 1 月 9 日 机器之心

选自南京大学

作者：张腾、周志华

机器之心编译

参与：刘晓坤、黄小天

在这篇题为《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 显著地优于对比的方法，从而证明了最优间隔分布学习的优越性。