论文引用格式：Geng W F， Wang X， Jing L P and Yu J. 2023. Consensus graph learning-based self-supervised ensemble clustering. Journal of Image and Graphics， 28（04）：1069-1078（引用格式:耿伟峰， 王翔， 景丽萍， 于剑. 2023. 共识图学习驱动的自监督集成聚类. 中国图象图形学报， 28（04）：1069-1078）［0　引 言聚类是根据数据相似性将其划分到若干集合中的一个经典机器学习问题，在兴趣推荐、图像分割和异常检测等领域均有广泛的应用前景（Jain，2010）。除此之外，聚类还常用于划分数据子块、生成伪标签和剔除异常点等数据预处理任务，以简化后续复杂任务或提升后续任务的性能。在大数据时代，随着数据采集技术的发展、数据标注成本的不断增加，自监督学习成为海量数据分析的一个重要策略。然而，如何从海量数据中抽取有用的监督信息，以及如何在该监督信息下开展有效的学习仍然是制约该方向发展的研究难点。由于深度神经网络具有强大表示能力，可以将数据转换为更有利于聚类的表示，大量基于深度学习的聚类方法相继提出。例如，深度嵌入聚类（Xie等，2016）方法通过优化样本特征表示和聚类分配隶属度，大幅提升了在复杂数据上的聚类性能。在此基础上，Yang等人（2017）、Guo等人（2017，2018）和Tao等人（2019）等方法的提出使深度聚类成为一个热门的研究领域。现有的大多深度神经网络模型和方法主要依赖监督信息或先验假设来挖掘数据的复杂潜在结构。受该思想的启发，Deep-cluster（Caron等，2018）提出自监督聚类的思想，对学习到的特征进行聚类，将聚类生成的伪标签作为监督信息指导网络更新。伪标签策略在许多无监督、半监督任务中都表现出不错的性能（Caron等，2018；Berthelot等，2019；Chang等，2017）。但是，由于初始阶段的伪标签置信度较低，模型在训练过程中会逐渐产生错误积累，影响最终聚类结果。集成学习作为一种通过训练多个基学习器并组合它们的预测结果来提高整体预测性能的学习方法，被认为是体现群体智慧能力的代表性机器学习方法（Sagi和Rokach，2018）。在基于伪标签的聚类任务中，集成学习能够整合不同的基学习器，从而获得高置信度的伪标签（Gupta等，2020）。但目前基于伪标签的集成聚类方法在捕获标签时仅考虑了样本的类别信息，忽略了样本本身特征表示和样本间聚类结构等重要信息，难以确保监督信息获取的有效性。图神经网络能够同时兼顾节点内容信息和节点间的结构信息，图表示学习已成为数据挖掘领域的一个重要分支（Kipf和Welling，2016，2017；Pan等，2018）。受该方法启发，本文设计了基于共识图表示学习的自监督集成聚类方法。核心思路是在集成学习中充分利用样本特征和样本间关系，同时挖掘全局和局部信息，以获得更高置信度的伪标签作为监督信息，提升自监督聚类的性能。本文的主要贡献为3个方面：1）提出一个通用的共识图学习集成聚类框架，充分利用样本特征和类别结构等多层次信息进行集成聚类；2）提出一种自监督训练方法，使用图神经网络挖掘共识图的全局与局部信息，获得高置信度伪标签作为监督信息；3）在图像和文本数据集上进行实验，证明了共识图学习集成聚类方法与最先进的集成聚类方法相比具有显著优势。1　相关工作近年提出了大量关于自监督聚类方法。本文聚焦于使用集成学习提升自监督聚类中监督信息的准确性与稳定性。1.1　自监督聚类深度嵌入聚类（Xie等，2016）以数据本身作为监督信息，使用重建损失预训练自动编码器，计算嵌入特征的软聚类分配，最小化软聚类分配与辅助目标分布之间的KL（Kullback-Leibler）散度，实现了同时优化数据表示和聚类分配。在此基础上，DCN（deep clustering network）（Yang等，2017）使用硬聚类替代软分配、IDEC（improved deep embedding clustering）（Guo等，2017）应用了局部约束，进一步提升了模型性能。与以数据本身作为监督信息不同，伪标签策略是用神经网络的预测结果作为标签来模拟监督信息的一种自监督学习方式，避免了深度嵌入聚类等方法收敛时无法达到最佳性能的问题。Deep-cluster（Caron等，2018）使用K均值聚类生成伪标签以指导卷积网络训练，但网络训练初期，生成的伪标签置信度较低，而且容易出现平凡解，这都会影响最终的聚类性能。DEC-DA（deep embedding clustering with data augmentation）（Guo等，2018）和MixMatch（Berthelot等，2019）使用数据增强样本的预测结果作为原始数据的监督信息，在一定程度上提升了监督信息的准确性，但是这种手段难以推广到文本等领域。深度自适应聚类（deep adaptive clutering，DAC）（Chang等，2017）在预测结果中选出了高置信度伪标签子集迭代训练网络，但忽略了低置信度样本中蕴含的数据分布信息。伪半监督聚类（Gupta等，2020）投票选取高置信度伪标签子集，再使用全部样本半监督地训练神经网络。虽然集成策略能够提升伪标签的置信度，但仅使用类别表示的投票策略忽略了样本本身的特征表示，这在某些情况下会严重降低聚类性能（Tao等，2017）。1.2　集成聚类集成聚类通过组合基学习器的预测来提高整体聚类性能，从本质上看，预测无标签样本的伪标签也是对数据进行划分的一种聚类任务。因此，集成学习也能够用来提升伪标签置信度。集成聚类方法可以分为3类，即基于效用函数的方法、基于共识矩阵的方法和基于图的方法。基于效用函数的方法将集成聚类转化成最大化效用函数（utility function）问题。效用函数度量了基本划分与共识划分间的相似度，如基于二次互信息的效用函数（Topchy等，2003）、基于K均值的效用函数（Wu等，2015）。随后又提出了多种共识函数（Li等，2007；Lu等，2008）。基于共识矩阵的方法通过样本对在同一个聚类中出现的次数来构造一个共识矩阵（Fred和Jain，2005），再利用传统聚类生成最终结果。谱集成聚类（Liu等，2015）对共识矩阵使用谱聚类，转化为一个加权K均值聚类问题。伪半监督聚类（Gupta等，2020）在共识矩阵中寻找高置信度的子集来迭代训练基学习器。基于图的方法以图或超图的形式集成基聚类器信息，再用图分割获得最终的聚类结果。传统的图集成采用启发式算法（Strehl和Ghosh，2003）和随机游走算法（Abdala等，2010）。但由于传统方法仅使用类别特征构建共识图，忽略了对样本原始特征的重用。最近，对抗图自编码器聚类（Tao等，2019）使用图自编码器学习低维的节点嵌入表示，重用了样本原始特征，在低维空间上获得了不错的聚类性能，但其共识图是预先定义的、不可学习的，共识图上的噪声可能会使最终的聚类性能较差。本文融合图集成方法与自监督方法的优势，通过图神经网络获得可学习的数据集成表示，提高了伪标签的置信度，并自监督迭代训练整个模型。2　基于共识图学习的自监督集成聚类在集成学习中，共识图包含多层次的复杂信息。为了充分利用这些信息，本文提出了一个通用的集成聚类框架，如图1所示。10.11834/jig.210947.F001图1共识图学习自监督集成聚类Fig.1Consensus graph learning-based self-supervised ensemble clustering基于共识图学习的自监督集成聚类框架可以分为3个部分：第1部分利用基学习器结果构建共识图；第2部分利用图神经网络分析共识图，捕获节点优化表示和节点的聚类结构；第3部分从聚类中挑选高置信度的节点子集及对应的类标签生成监督信息；在此标签监督下联合其他无标注样本更新集成成员基学习器。模型反复迭代使聚类性能得到了持续的提高。在本框架中，基学习器可以替换成任意无监督聚类模型或半监督模型。2.1　共识图构建对于给定的无标注数据集X={x1,…,xn}，本文以阶梯网络（Rasmus等，2015）作为基学习器模型M={M1,…,Mm}进行训练，阶梯网络采用多通道的自动编码器抽取样本特征，并在编码器顶层后添加了分类头。然而，阶梯网络是一种半监督模型，同时使用监督损失和无监督损失，但在没有监督损失的情况下会仅输出常数，需要在损失中增加信息最大化损失（Gomes等，2010），具体为LIM=IX;Y=HY-HYX (1)式中，X和Y为模型输入和输出，H(∙)和H(∙∙)分别是熵和条件熵。最大化H(Y)鼓励神经网络在输出类别上均匀分布；最小化HYX鼓励神经网络对给定的输入进行明确的类分配。对于基学习器输出的m个聚类结果，采用类似于证据积累法（Fred和Jain，2005）的方式初始化共识图A={X,E}，图中每个节点代表一个样本，如果M中的超过阈值t (0 t ≤ m)个数的基学习器将样本对划分为同一簇（可以有较高的置信度认为样本对为同一类），则在样本对之间添加边E；即x, x'∈E⇔nagreex,x' ≥ tnagreex,x'=m:m∈M,mx=mx' （2）2.2　共识图学习为了挖掘图结构信息、提高伪标签的置信度，本文使用图神经网络学习从嵌入空间到聚类分配空间的映射，充分利用了节点特征作为聚类依据。具体来说，共识图学习先由图神经网络消息传递层计算新的集成表示Z¯，再通过多层感知器计算节点的聚类分配S（Bianchi等，2020），即Z¯=MPZ,A˜=ReLUA˜ZWm+ZWs+b （3）S=MLPφZ¯ （4）式中， Wm,Ws,b,φ是图神经网络的参数，节点表示Z是在基学习器阶梯网络的无噪声通道顶层获得的数据的低维表示，邻接矩阵A˜是共识图A经过对称归一化后得到的。具体为A˜=D-12AD-12∈RN×N （5）D=diagA1N （6）网络的损失为L=-trSTA˜StrSTD˜S︸Lc+STSSTSF-IKKF︸Lo （7）式中，A1N为全1矩阵，图割损失Lc计算由聚类分配矩阵S给出的图割损失，最小化Lc鼓励强连通节点被划分为一簇。正交损失Lo鼓励聚类分配是正交的，并且鼓励模型将样本平均分配给每个簇，避免了平凡解的产生，K为聚类簇数。IK可以理解为一个重构的聚类矩阵IK=S^TS^，其中S^为每个簇分配n/K个点。值得注意的是，图神经网络直接学习从节点特征空间到聚类分配空间的映射，不需要计算图的谱，所以可以应用于流式数据，直接计算新样本的聚类分配，而不需要计算谱分解。相比于伪半监督聚类（Gupta等，2020）仅集成基学习器的聚类结果，本文使用共识图学习更有利于聚类的节点集成表示。使用共识图学习有以下优势：1）使用共识图学习优化节点表示不仅考虑了数据的类别表示，还重新引入了数据的嵌入表示。而伪半监督聚类仅考虑了基学习器的结果，忽略了样本本身特征表示，存在严重的信息损失；2）使用共识图学习可以基于全局和局部信息挖掘节点聚类结构，寻找密集强连通子图，进一步提高监督信息（伪标签）的置信度。而以前的方法采用贪心的策略选取伪标签，仅利用了图的局部的信息。2.3　自监督基学习器构建尽管基学习器已经提供了较好的基础准确率，但仍然存在部分样本被错误划分的情况。为了尽可能避免使用错误的伪标签训练基学习器，在新的共识图的每一簇中，仅选取高置信度的样本子集标注伪标签。为了最大化每个样本子集的规模，获得更多数量的伪标签，使模型更快地收敛，选取度最大的节点及与其连通的节点标注对齐的伪标签。即Xk=xx→xmaxk,xmaxk∈Sk,0≤kK (8)式中，K是聚类簇数，Sk表示第k个簇，xmaxk是第k簇内度最大的节点。与仅使用高置信度伪标签样本训练学习器不同，本方法使用伪标签子集与无标签样本一起训练半监督基学习器集合M={M1,…,Mm}，半监督基学习器采用与初始化步骤中相同的阶梯网络。训练后的基学习器将再产生m个聚类结果用于构建共识图、优化共识图表示、选取高置信度的伪标签子集并反复迭代更新，即自监督地训练基学习器。需要强调的是，本文模型在迭代过程中，通过不断精炼伪标签，以提高伪标签置信度。前一轮模型迭代产生的高置信度伪标签子集经过对齐后，成为下一轮迭代的基学习器的监督信息。由于剔除了低置信度的伪标签，所以并非所有样本都具有监督信息，因此，基学习器采取半监督分类器充分挖掘未标注样本和伪标签样本的语义信息。CGL-SEC算法完整的伪代码如下：输入：数据X，聚类簇数K；输出：聚类分配 S。1） For j ∈ {1,2,⋯, m} Do；2） 初始化第j基学习器阶梯网络Mj参数；3） 使用无监督损失训练基学习器Mj；4） End For；5） For it ∈ {1,2,⋯, n_iter} Do；6） 初始化共识图A；7） 初始化图神经网络；8） 使用式（7）中损失训练图神经网络；9） 图神经网络前向传播，输出聚类分配矩阵S；10） For k ∈ {1,2, . . . ,K} Do；11） 筛选伪标签；12） End For；13） For j ∈ {1,2,⋯,m} Do；14） 对齐Mj的输出伪标签；15） 最小化监督损失和无监督损失之和训练基学习器Mj；16） End For；17） End For；18） 图神经网络前向传播，输出聚类分配矩阵S；19） Return S。3　实验为验证本文方法的性能，在5个标准数据集上进行实验。本文的代码开源发布在：https://github. com/ggg929627701/GNN-kingdra。3.1　实验数据集MNIST-Test（modified national institute of standards and technology database），是MNIST数据集的测试集，共10类10 000个样本。STL10（self-taught learning 10 ）包含10类13 000幅图像。每个样本为96 × 96像素的彩色RGB图像。USPS（United States Postal Service）包含10类手写体数字，共9 298个样本，每个样本为16 × 16像素的灰度图像。Reuters包含4类英语新闻文本数据，是一个类别不均衡数据集，最大的类占数据集的43%。20News包含20类英文新闻文档，每个类有902个样本。本文采用与Hu等人（2017）相同的数据预处理方式。3.2　基准方法实验将提出的基于共识图学习的自监督集成聚类与多种聚类算法进行比较。包括：1）3类传统的聚类方法。即K均值聚类（K-means）（MacQueen，1967）、谱聚类（normalized-cut spectral clustering， SC）（Shi和Malik，2000）和基于ζ函数的凝聚聚类（zeta function based agglomerative clustering，AC）（Zhao和Tang，2008）。2）3类最先进的深度聚类方法。即使用信息最大化损失的自增强聚类（information maximizing self-augmented training，IMSAT）（Hu等，2017）、深度嵌入聚类（deep embedded clustering，DEC）（Xie等，2016）和深度聚类网络（deep clustering networks，DCN）（Yang等，2017）。3）4类集成聚类方法。即谱集成聚类（spectral ensemble clustering，SEC）（Liu等，2015）、K均值共识聚类（K-means-based consensus clustering， KCC）（Wu等，2015）、对抗图自编码器聚类（adversarial graph auto-encoder，AGAE）（Tao等，2019）和伪半监督聚类（Kingdra）（Gupta等，2020）。由于在Tao等人（2019）的研究中，变分图自编码器（variational graph auto-encoder，VGAE）（Kipf和Welling，2016）和（adversarially regularized variational graph autoencoder，ARVGE）（Pan等，2018）等图嵌入聚类方法已与AGAE对比了性能，本文只对比性能最好的AGAE方法。同样，在Liu等人（2015）的研究中，CSPA、HGPA和MCLA等集成聚类方法已与KCC和SEC对比了性能，本文不再对其进行比较。3.3　实验结果实验在3个图像基准数据集和两个文本数据集上进行，实验结果如表1和表2所示，展示了聚类准确率（accuracy，ACC）和归一化互信息（normalized mutual information，NMI）指标。10.11834/jig.210947.T001表1在图像标准数据集上的聚类准确率和归一化互信息Table 1Clustering ACC and NMI on image datasetsMNIST-TestSTL10USPSACCNMIACCNMIACCNMIK-means0.531 60.499 40.848 40.786 00.668 00.627 0SC0.660 00.704 00.563 50.568 50.562 00.540 0AC0.810 00.693 00.821 70.754 40.657 00.798 0IMSATN/AN/A0.941 0N/AN/AN/ADEC0.856 00.830 00.841 30.851 80.688 00.683 0DCN0.802 00.786 00.893 0*0.816 3*0.762 0*0.767 0*SEC0.568 70.515 70.797 6*0.783 0*0.681 5*0.652 9*KCC0.602 60.465 10.727 8*0.787 3*0.560 7*0.638 5*AGAEN/AN/A0.932 5*0.874 1*0.735 7*0.741 5*Kingdra0.939 30.909 60.951 00.888 00.773 20.798 0CGL-SEC0.977 80.942 00.963 10.892 70.797 30.821 5注：加粗字体表示各列最优结果，带*的结果摘自Tao等人（2019）的研究，下划线的结果摘自Gupta等人（2020）的研究，N/A表示对应方法不适用于相关数据集。10.11834/jig.210947.T002表2在文本标准数据集上的聚类准确率和归一化互信息Table 2Clustering ACC and NMI on text datasets方法20NewsReutersACCNMIACCNMIK-means0.153 90.185 50.540 40.412 8SC0.248 60.214 70.663 30.339 1AC0.239 70.202 40.436 60.011 1IMSAT0.311 0N/A0.710 0N/ADEC0.308 00.299 60.736 80.497 6Kingdra0.439 00.414 70.705 00.393 0CGL-SEC0.442 70.461 70.723 20.416 4注：加粗字体表示各列最优结果，下划线的结果摘自Gupta等人（2020）的研究，N/A表示对应方法不适用于相关数据集。如表1和表2所示，诸如K均值聚类、谱聚类等传统聚类方法往往比深度聚类方法性能差。与DEC等先进的深度聚类方法相比，本文方法在多个数据集上实现了更高的聚类准确率。实际上，除了Reuters之外，本文算法都优于其他方法。在Reuters数据集上略低于DEC，是因为基学习器信息最大化损失鼓励聚类平均分配，但Reuters是一个类不均衡数据集，最大的一类占总样本数的43%，这使得模型性能受到了影响。然而，可以使用任意聚类算法替换本框架中基学习器来适应不同数据集。与投票集成方法Kingdra相比，本方法在所有数据集上都获得了更好的聚类性能。这表明本文提出的图集成方法比投票集成方法更具性能优势。在MNIST-Test数据集上，图集成方法的准确率相比于投票集成方法提升了3.85%。与AGAE预先定义共识图相比，本文方法在迭代训练中持续更新共识图表示，在STL和USPS数据集上的准确率（ACC）与归一化互信息（NMI）高出了3%以上。这体现了可学习的共识图的优越性。在时间性能方面，以MNIST数据集为例，模型在单个TITAN Xp GPU加速的条件下，每次迭代（模型每获得一次伪标签）约花费40±3 min，完整训练过程需要50次迭代。图神经网络训练时间复杂度与节点数和边数成正比，MNIST是10类手写数字分类数据集，在训练过程中90%的同类的样本对之间均会产生边，这形成了一个稠密图。常见的图数据集比如Cora、Citeseer等的拓扑关系往往是稀疏的，这使得图神经网络在这些稀疏图上的训练时间较少。本文期望通过拓扑关系是否稠密来衡量节点集合是否紧致，进一步从语义角度定义节点伪标签的置信度，这也导致了一定的时间性能代价。3.4　消融实验为了说明每个模块对于最终性能的贡献，设计了消融实验，分别对比本文使用的单独的基学习器（base learner，BL）、投票集成多个基学习器的聚类结果（base-learner-vote，BL-Vote）和不进行共识图学习，仅投票选取伪标签的自监督迭代聚类（voted self-supervised clustering，V-SEC）的性能，结果如表3所示。可以看出，基学习器提供了一个较好的基础准确率，但投票集成仅提供了1%～2%的性能增益，最大的性能增益来自自监督训练方式。共识图学习进一步为自监督训练提供了更大的增益，使性能相比于基学习器提高了4%～10%。10.11834/jig.210947.T003表3在5个标准数据集上的消融实验Table 3Ablation experiment on 5 standard datasets模块MNIST-TestSTL10USPS20NewsReutersACCNMIACCNMIACCNMIACCNMIACCNMIBL0.893 70.837 80.871 80.768 40.718 90.680 80.384 00.330 50.682 00.315 0BL-Vote0.916 00.886 40.915 00.817 20.731 20.729 80.405 00.401 20.690 00.347 2V-SEC0.939 30.909 60.951 00.888 00.773 20.798 00.439 00.414 70.705 00.393 0CGL-SEC0.977 50.942 00.963 10.892 70.797 30.821 50.442 70.461 70.723 20.416 4注：加粗字体表示各列最优结果。与V-SEC相比，CGL-SEC在MNIST-Test和Reuters上的准确率（ACC）与归一化互信息（NMI）都增加了2%以上，表明本文提出的基于图神经网络的集成学习方法足够通用，在图像和文本数据集上都获得了较大的性能提升。图2描述了在MNIST-Test数据集上本方法和Kingdra方法的伪标签数量和准确率与迭代次数的关系。图2表明，本方法的图神经网络选出了数量更少但准确率更高的伪标签，基于图神经网络的集成策略比投票策略更好地抑制了伪标签置信度的下降。然而，伪标签的减少并没有让模型的收敛速度减慢，本方法只减少了少量的低置信度伪标签，但使得模型性能获得了较大地提升。10.11834/jig.210947.F002图2伪标签数量、准确率与迭代次数的关系Fig.2The number and accuracy of pseudo-labels vary with the number of iterations3.5　收敛性和泛化性在许多聚类算法中，分阶段特征学习和聚类、深度嵌入聚类以及数据增强的深度嵌入聚类，会出现模型性能在训练阶段早期达到最大值，但随后降低并收敛到稳定值的现象。这是由于网络在微调阶段发生了过拟合，随着训练迭代轮次的增加，重建损失使网络逐渐关注数据中与类别无关的信息。这使得基于自动编码器的聚类模型不得不增加停止迭代的条件（Guo等，2018）。基于伪标签的聚类方法可以有效避免收敛时达不到最佳聚类性能的问题。图3描述了聚类性能指标与迭代次数的关系，可以观察到，随着迭代次数的增加，准确率与归一化互信息逐步收敛到最大值。因为随着训练的进行，高置信度伪标签的数量会逐渐增加，更多的样本参与计算伪监督损失，指导网络学习数据中与类别相关的信息，有效避免了过拟合。10.11834/jig.210947.F003图3STL数据集在训练过程中准确率和归一化互信息Fig.3Accuracy and normalized mutual information during training on the STL dataset为证明模型的泛化性能，在MNIST-Test上训练本文模型，并在MNIST和MNIST-Test上分别测试，结果如表4所示。其中，在新样本测试集（MNIST）上的准确率仅比训练集上的测试结果低0.007，尤其是模型的训练集仅有10 000个样本，而测试集含有60 000个新样本，这表明模型具有很好的泛化能力。10.11834/jig.210947.T004表4训练集为MNIST-Test，测试集分别为MNIST和MNIST-Test的模型性能Table 4The performance of the model when training set is MNIST-Test and test set is MNIST or MNIST-Test respectively测试集ACCNMIMNIST-Test0.977 80.942 3MNIST0.970 80.924 84　结论本文希望解决自监督聚类中如何从海量数据中抽取有用的监督信息，以及如何在该监督信息下开展有效的学习这两方面问题，提出了一种基于共识图学习的自监督集成聚类框架。总结如下：1）在集成聚类任务中，以往的共识图的构建方法往往忽略了样本特征信息和共识图自身的可学习性，本文使用图神经网络融合了样本特征与类别表示等多层次信息，更好地从数据中抽取了高质量的自监督信息。2）提出了基于共识图学习的自监督集成聚类框架，利用从共识图中提取的伪标签监督模型学习知识，并在多个图像、文本标准数据集上取得了令人满意的结果。3）实验与结果表明，共识图表示学习可以提升伪标签的置信度，进而提升深度集成聚类的性能。通过实验探究，发现了所提方法存在的问题。在大规模数据集上，本方法在图神经网络训练阶段耗时较长。时间性能较低几乎是所有基于图的聚类方法的限制。因此，如何提高图集成聚类的效率将是本领域未来的研究方向。此外，对于集成聚类领域，如何构建多样性的基学习器也是一个具有挑战性的问题。