【速览】TPAMI 2022 | SimpleMKKM: 简单多核K均值聚类

学会“成果速览”系列文章旨在将图像图形领域会议期刊重要成果进行传播，通过短篇文章让读者用母语快速了解相关学术动态，欢迎关注和投稿~

◆ ◆ ◆ ◆

TPAMI 2022：SimpleMKKM: 简单多核K均值聚类

刘新旺

国防科技大学计算机学院TPAMI 2022撰稿人：刘新旺

通讯作者：刘新旺

推荐理事：林宙辰原文标题：SimpleMKKM: Simple Multiple Kernel K-means原文链接：https://ieeexplore.ieee.org/abstract/document/9857664/原文代码链接：https://github.com/xinwangliu/SimpleMKKMcodes

◆ ◆ ◆ ◆

摘要

本文提出了一种简单而有效的多核聚类算法，称为SimpleMKKM。它将广泛使用的有监督核对齐准则扩展到多核聚类。本文的优化目标可以转化为一个核系数和聚类划分矩阵中的Min-Max问题。为了优化该目标，我们将Min-Max问题转化为一个等价的最优值函数的最小化问题。我们证明了该问题的可微性，并设计了一个简约梯度下降算法来优化它。此外，本文证明了SimpleMKKM得到的解是全局最优解，并从聚类泛化误差的角度分析SimpleMKKM的性能。在此基础上，我们进行了大量的实验研究，从聚类精度、目标式优化的优势、学习的共识聚类矩阵随迭代次数的变化、不同数量的样本和核下的聚类性能、学习核权重分析、运行时间和全局收敛性等方面对所提出的 SimpleMKKM 进行了研究。实验结果表明，SimpleMKKM算法的聚类性能显著地优于现有的多核聚类算法。此外，消融研究表明，聚类性能的提升是由新颖的目标式和优化方式共同促成的。本文的工作为集成多视图数据进行聚类提供了一种更有效的方法，这将带来在多核聚类领域的全新研究方向。

背景

多核聚类（MKC）旨在融合一组预先计算的核矩阵，以获得更好的聚类性能[1]。这些核矩阵可以编码不同来源或多个视图的数据[2,3,4]。多核均值（MKKM）[5]是一种流行的多核聚类方法，已被深入研究，并应用于多个场景下[7,8,9]。它将最优核系数和聚类划分矩阵的搜索统一为一个单一的目标函数，并通过对系数和聚类划分矩阵的两步交替优化来求解。

为了进一步提高聚类性能，研究人员已经提出了MKKM的多种变体。其中，文献[6]通过局部自适应的核融合方法，更好地捕获了数据的样本特定特征，极大地提高了MKKM的性能。文献[10]提出了一种优化局部核对齐准则的扩展。它将由个最近邻给出的样本的局部密度与一个理想的相似矩阵对齐。这有助于保持相邻的样本之间的对齐关系，从而避免了不可靠的相似性评估。文献[11]观察到现有的MKKM算法没有充分考虑这些核之间的相关性，因此采用矩阵正则化的方法来减少冗余度，增强所选核的多样性。与现有的MKKM算法假设最优核是一组核的线性组合不同，文献[12]提出了最优邻居核聚类（ONKC）算法，提高了最优核的表达能力，加强了聚类与核权重学习之间的互相促进。最近，MKKM算法被扩展到处理缺失的视图。通过假设最优核是核矩阵的线性组合，文献[13]提出了一个Min-Max准则，旨在对噪音的扰动具有鲁棒性。最近，许多工作都致力于扩展现有的MKKM，以处理缺失多核聚类任务。所有这些变体都从不同的方面改进了标准MKKM，并在多个应用中实现了良好的聚类性能。

上述方法的目标函数各不相同，但它们都有一个共同点：它们同时学习核系数和聚类划分矩阵。这样，学到的核系数可以更好地服务于聚类，从而达到更好的聚类性能。然而，同时求解核系数和聚类划分通常是困难的。一种常用的解决方法是通过块坐标下降算法将核系数的优化和聚类划分解耦，并对两者进行交替优化。这意味着，一个变量块被最小化，而另一个变量块则保持不变。然而，这种优化算法可能会陷入目标函数的局部最优之中。文献[10][11]提出了正则化策略，以避免陷入局部最小值。而引入这些正则化项是有代价的：这些方法有额外的超参数，考虑到聚类任务的无监督性质，这些超参数很难选择。

新颖的目标式

核对齐准则由于其简单性和有效性，已被广泛应用于有监督学习中的寻找最优核的过程。受启发于现有的有监督核学习，我们提出的新的目标式是基于无监督学习的多核对齐准则。我们可以通过最大化    和  来优化这个标准。虽然理论上很优雅，但我们通过实验观察到，这种的  形式并不能实现良好的聚类性能，这与有监督核学习不同。我们推测这是由于  和  过拟合优化引起的。另一方面，MKKM的目标式可以分解为两项，  和  。第一项可以看作是关于  的正则化项，它应该被最小化。另一项与核对齐准则相反，应该关于  最大化。通过同时考虑正则化和划分优化，我们的SimpleMKKM提出了一个新的目标式：

，（1）

其中，

。

这个目标式看上去很简单，但它有以下优点：（1）这是第一个严格按照  来调整核权重的MKKM目标。相比之下，MKKM及其所有变体都采用  作为标准，将经典的核均值的目标式扩展到多核聚类上。值得注意的是，核对齐准则更为通用，可以用于任何寻找最优核任务。因此，它可以被用于多核聚类。（2）根据文献[13]，通过关于  和  的Min-Max优化，可以避免对噪声视图或数据点的过拟合，从而产生更鲁棒的簇划分。（3）正如我们下文中提到的，虽然我们的公式看起来难以优化，但它实际上引出了一个比MKKM更有效的优化算法。此外，与文献[10][11]不同，SimpleMKKM除了簇数  之外没有引入其他参数。

为了让公式（1）在优化过程中单调下降，我们设计了一种高效且有效的简约梯度下降算法。首先，我们将公式（1）等价地重写为

  ，（2）

其中，

 。（3）

这样，我们就将原来的Min-Max优化过程转化为了一个最小化的优化过程，其中相应的目标是一个依赖于核  均值算法的最优值函数。下面，我们首先证明了  关于  的可微性，并应用简约梯度下降算法来优化公式（2）。

关于函数  导数的存在性和计算方法，在文献[14]中有所讨论。[14]中的定理4.1，已经被用于SVM的超参数调优和优化多核学习中的核权重优化。下面的定理1说明了  是可微的。

定理 1. 在公式（2）中的  是可微的。并且，

其中  。

我们提出采用简约梯度下降算法来优化公式（2）。为此，我们首先根据定理1计算  的梯度，然后用一个下降方向  更新  ，从而保证  上的等式约束和非负性约束。

（4）

其中，

（5）

。（6）

我们通过策略  来更新  ，其中  表示步长，可以通过线性搜索机制，如Armijo准则来选择。我们提出的SimpleMKKM的详细优化过程如算法3所示。

我们分析了算法3中SimpleMKKM的收敛性。注意，公式（3）是一种传统的核均值目标，它具有全局最优解。在这种情况下，定理1中的梯度计算是准确的，我们的SimpleMKKM在连续可微函数的  上进行简约梯度下降，该函数定义在单纯形  上。因此它确实收敛到  的极小值。此外，定理2说明了等式中的  是关于的一个  凸函数。

定理 2. 在公式（2）中的  关于  是凸的。

根据定理2，算法3中的SimpleMKKM得到的解为全局最优。这意味着我们的SimpleMKKM不依赖任何初始化，实验部分也验证了这一点。据我们所知，我们的SimpleMKKM是多核聚类文献中第一个理论上可以保证全局最优的算法。

泛化误差分析

通过推导泛化误差界，我们研究了由所提出的SimpleMKKM得到的聚类中心如何推广到测试数据上。首先，我们构造了一个函数类：

  （7）

其中，  表示多核希尔伯特空间。

定理 3. 对于任意  和所有  ，公式（8）以不小于  的概率成立。

 （8）

根据定理3，我们推断出，为了最小化误差上界，我们可能必须进行  。然而，在此准则下，很难找到  和  的较好的解，而且容易求出过拟合解[13]。因而，我们取它的一个下界，  作为SimpleMKKM的目标式。上述分析验证了SimpleMKKM具有良好的泛化能力。

实验结果

表1中展示了所提出的SimpleMKKM算法与其他先进的多核聚类算法的聚类性能对比，SimpleMKKM取得了相当或更好的聚类效果。与其他需要大量时间进行超参数选择的算法相比，我们的SimpleMKKM是一个无参数的算法。

表2中展示了SimpleMKKM消融实验结果。1）我们所提出的SimpleMKKM、SimpleMKKM-C与MKKM、MKKM-R相比具有显著的优势，证明了Min-Max范式优于Min-Min范式。2）SimpleMKKM的聚类效果比SimpleMKKM-C更好，证明我们提出的梯度下降优化算法优于广泛使用的坐标下降。消融实验的结果证明了我们所提出算法聚类性能的提升来自于新颖的范式与新颖的优化算法。

图1中展示了SimpleMKKM与对比算法在Caltech102数据集上聚类性能随样本数量的变化。SimpleMKKM显著提高了现有MKKM算法及其变体的聚类性能。

图2中展示了在不同初始化条件下SimpleMKKM的目标函数值随迭代次数的变化。从图中可以看到：1）所提出的算法目标函数值单调减少，在所有数据集上均在不到三十次迭代中收敛，验证了我们算法的收敛性；2）在不同初始化条件下，SimpleMKKM收敛时的目标函数值相同，验证了我们算法得到的解是全局最优的。

表 1 SimpleMKKM与其他先进算法的聚类性能对比

表 2 所有数据集上SimpleMKKM与MKKM、MKKM-R和SimpleMKKM-C的经验比较

图 1 在Caltech102数据集上聚类性能随样本数量变化曲线图

图 2 SimpleMKKM在不同初始化条件下目标函数值随迭代次数变化曲线图

结论

本文提出了一种简单且有效的MKKM的新颖范式（SimpleMKKM），并且提出了一种有效的算法来解决对应的优化目标。我们推导了所提出算法的泛化误差界，精心设计的实验验证了算法的有效性。我们的工作为融合多视图数据进行聚类提供了一种更有效的方法，带来了多核聚类上的新研究方向。

参考文献

[1] Zhao, Bin, James T. Kwok, and Changshui Zhang. "Multiple kernel clustering." Proceedings of the 2009 SIAM International Conference on Dat·a Mining. Society for Industrial and Applied Mathematics, 2009.

[2] Yu, Shi, et al. "Optimized data fusion for kernel k-means clustering." IEEE Transactions on Pattern Analysis and Machine Intelligence 34.5 (2011): 1031-1039.

[3] Zhang, Changqing, et al. "Deep partial multi-view learning." IEEE transactions on pattern analysis and machine intelligence (2020).

[4] Sun, Shiliang, Wenbo Dong, and Qiuyang Liu. "Multi-view representation learning with deep gaussian processes." IEEE Transactions on Pattern Analysis and Machine Intelligence 43.12 (2020): 4453-4468.

[5] Huang, Hsin-Chien, Yung-Yu Chuang, and Chu-Song Chen. "Multiple kernel fuzzy clustering." IEEE Transactions on Fuzzy Systems 20.1 (2011): 120-134.

[6] Gönen, Mehmet, and Adam A. Margolin. "Localized data fusion for kernel k-means clustering with application to cancer biology." Advances in neural information processing systems 27 (2014).

[7] Peng, Xi, et al. "COMIC: Multi-view clustering without parameter selection." International conference on machine learning. PMLR, 2019.

[8] Kumar, Abhishek, and Hal Daumé. "A co-training approach for multi-view spectral clustering." Proceedings of the 28th international conference on machine learning (ICML-11). 2011.

[9] Kumar, Abhishek, Piyush Rai, and Hal Daume. "Co-regularized multi-view spectral clustering." Advances in neural information processing systems 24 (2011).

[10] Li, Miaomiao, et al. "Multiple kernel clustering with local kernel alignment maximization." Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. 2016.

[11] Liu, Xinwang, et al. "Multiple kernel k-means clustering with matrix-induced regularization." Proceedings of the AAAI conference on artificial intelligence. Vol. 30. No. 1. 2016.

[12] Liu, Xinwang, et al. "Multiple kernel $k$ k-means with incomplete kernels." IEEE transactions on pattern analysis and machine intelligence 42.5 (2019): 1191-1204.

[13] Bang, Seojin, Yaoliang Yu, and Wei Wu. "Robust multiple kernel k-means clustering using min-max optimization." arXiv preprint arXiv:1803.02458 (2018).

[14] Bonnans, J. Frédéric, and Alexander Shapiro. "Optimization problems with perturbations: A guided tour." SIAM review 40.2 (1998): 228-264.

欢迎扫描二维码加入中国图象图形学学会

                 （http://membership.csig.org.cn）               

中国图象图形学学会科普活动、素材征集通知中国图象图形学学会高校志愿者招募
中国图象图形学学会关于组织开展科技成果鉴定的通知