最优间隔分布学习的优越性

聚类是机器学习、数据挖掘和模式识别中的一个重要研究领域，其目标是分类类似的数据点。它催生出了包括信息检索、计算机视觉、生物信息学等在内的大量新研究，而且不一样的聚类算法已被提出超过十年（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 更紧致的极大极小松弛，并可经过迭代地生成最违反的标签，而后借助多核学习整合它们而被解决。api

第二类经过非凸优化的变量直接优化原始的问题。这些案例包括了交替优化（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 的单次迭代的平均时间消耗。ui

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

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------