基于一致二部图的不完全大规模多视图聚类方法

9776基于一致二部图王四维1、刘欣王1*、刘立2、涂文轩1、朱新忠4、刘继元1、周思航3、朱恩11国防科技大学计算机学院2国防科技大学系统工程学院3国防科技大学情报科学与技术学院4浙江师范大学。{wangsiwei13，xinwangliu，twx，liujiyuan13，enzhu} @ nudt.edu.cn，Li. oulu.fi摘要多视图聚类由于其在融合互补信息而无需人工注释的有效性而受到越来越多的关注。以前的大多数方法都假设每个实例出现在所有视图中。然而，它并不罕见地看到，一些视图可能包含一些丢失的实例，这引起了在文献中的不完全多视图聚类（IMVC）。尽管最近提出了许多IMVC方法，但它们在应用于大规模任务时总是遇到高复杂度和昂贵的时间开销。针对这些问题，本文提出了一种基于偶图框架的灵活高效的不完全大规模多视图聚类方法具体来说，我们将多视图锚点学习和不完全二分图形式化为一个统一的框架，相互协调以提高集群性能。通过引入灵活的二分图框架来处理IMVC的第一次实践，我们提出的方法具有线性复杂度方面的实例数量，这是更适用于大规模的IMVC任务。在各种基准数据集上的综合实验结果表明，我们提出的算法对其他IMVC竞争对手的有效性和效率代码在1可用。1. 介绍多视图聚类（MVC）全面整合不同的源信息，将具有相似结构或模式的数据样本划分到同一个聚类中，而无需强调标签注释[4，10，12，14，17，19，20，24、30、44、46、48]。 近年来，众多的多视图*通讯作者1https://github.com/wangsiwei2010/CVPR22-IMVC-CBG在计算机视觉和机器学习领域已经提出了聚类算法，其基本上可以分为以下四类：协同训练方式、多核聚类（MKC）、非负矩阵分解（NMF）和图聚类。MVC的协同训练策略提出交替组合多个聚类结果，这些结果为其他视图的未标记数据提供预测[8]。通过这种方法，除了从相应的视图中提取特定的信息外，聚类标签还可以在不同的视图上达成一致。 通过遵循多核学习框架，MKC方法从希尔伯特空间中的一组预定义核矩阵中单位化核矩阵[4，17，19，21，33，42，43]。此外，NMF将矩阵分解应用于具有统一潜在空间的多视图聚类，并且图聚类方法从多视图数据表示优化统一的图结构[2，3，25，27，28，50]。此外，深度多视图聚类（DMVC）也被深入研究[13，31，38，40]。尽管已经提出了现有的MVC算法来提高各种应用程序任务的性能，但它们中的大多数都持有一个共同的假设：所有视图都是完整的。不幸的是，从某些视图中无法访问某些实例的情况并不少见。例如，对于网页分析，一些具有文本，音频和图片特征，而另一些可能仅包含一种或两种[45]。此外，患者可能由于经济上的不便而无法进行各种医学测试，从而导致相应视图中的样本不完整。不完备性导致现有MVC算法性能严重下降甚至执行失败，这使得不完备多视图聚类（IMVC）成为一个挑战性问题。为了解决IMVC问题，文献中已经提出了现有的不完整的多9777视图聚类可分为三类：基于矩阵分解（MF）的[6，9，26]，图或核-基于[18，21，36，37，39]和深度学习[13，31，38，40]。基于MF的IMVC方法尝试建立跨各种视图的具有不完整数据的统一表示。例如，PVC是第一次尝试采用NMF来导出不完整数据的共识潜在表示[9]。 在PVC之后，MIC [26]然后介绍了表1.在整个文件中使用的主要符号。符号意义加权NMF和NMF二、一正则化器以提高性能。此外，Huet al.提出基于半NMF表示对齐和基本空间对齐来对齐多视图信息[6]。基于图或核的IMC方法试图恢复在不同视角中跨多个视图一致的相似性图或核矩阵。Liu等建议将不完全填充和聚类统一到一个框架中，以提高聚类性能[21]。随着深度学习的广泛Li等设计一个深度IMVC模型，可以通过对比学习来模拟学习表示和恢复数据[13]。然而，现有算法的计算复杂度高、优化过程复杂、时间开销大，使其难以应用于大规模任务。此外，应开发更灵活的IMVC框架，以处理除两个视图之外的任意不完整视图。为了解决上述问题，本文提出了一种灵活高效的基于共识二分图框架的不完全大规模多视图聚类方法IMVC-CBG。首先，我们在不完全二部图框架下对IMVC问题进行了形式化描述，这是该社区的第一次实践。与以往研究中融合多个视图的大型成对相似度矩阵不同，本文将锚学习和不完全二分图融合在一起，使实例共享一致二分图，并确保视图间的结构一致性.我们还提供了解释我们的方法与概率模型。然后，提出了一个四步交替优化算法，证明了收敛性，有效地解决由此产生的优化问题。凭借所提出的新框架，我们所提出的方法享有线性复杂度方面的实例数，这是更适用于大规模的聚类任务。在各种基准数据集上的综合实验结果值得注意的是，我们是第一个算法，可以有效地和effec- tively运行在数据集超过100000个样本与64 G RAM在IMVC社区。本文的主要贡献可归纳如下，• 我们提出了一种灵活的IMVC方法（IMVC-CBG）用不完全二分图融合来处理先前研究中的可伸缩性问题。 通过引入IMVC-CBG是一个灵活的框架，可以处理任意视图的不完整性。IMVC-CBG的第一个实践是将IMVC和二分图集成到一个联合框架中。• 与现有的IMVC方法相比，我们同时利用统一二分图来捕获互补信息，并学习在不完整视图上发现聚类结构。• 我们设计了一个四步交替优化算法，有效地解决IMVC-CBG与证明收敛。我们提出的方法enjoys线性复杂度方面的实例数，这是更适用于大规模的IMVC任务。全面的实验结果清楚地证明了我们所提出的方法的有效性和效率。2. 相关工作在本节中，我们简要介绍了以下小节中的一些相关工作，即IMVC和MVC与二部图。表1列出了论文中使用的主要符号.2.1. 不完全多视图聚类不完全多视图聚类（IMVC）问题近年来得到了越来越多的关注。 我们将不完全多视图聚类算法分为三类：基于矩阵分解（MF）的算法[6，9，15，26，49]，基于图形或核的算法[21，32，47，49]和深度算法[13，31，40，41]。基于MF的IMVC方法试图建立一种表示，n数量的样本v视图数K聚类数M选定锚点α∈Rv×1视图系数向量Di第i个视图ΣvDi=1diX（i）∈Rdi×n第i个视图A（i）∈Rn×ni第i个视图W（i）∈Rk×di第i个视图S∈Rn×n相似度矩阵C∈Rk×mconsensus anchor matrixZ∈Rm×n一致锚图9778澵濢濗濜濣濦C¨∈∈¨∈(i)di×n（一）（二）（v）中国招标人中国招标人茯苓茯苓图1.我们提出的IMVC-CBG的框架我们将多视图不完全数据投影到一个共享的潜在空间中，并为每个视图构造相应的不完全二分图 通过正则化一致锚，所有视图都有助于填充关于拉伸矩阵A（i）的一致二分图。最后，直接用完全一致二部图Z进行聚类算法.IMVC-CBG被证明具有O（n）的复杂度，可以有效地处理大规模IMVC问题。潜在子空间在这一类别中，部分多视图聚类（PVC）[9] 是 一 个 先 驱 性 的 工 作 ， 它 使 用 非 负 矩 阵 分 解（NMF）来导出不完整数据的一致潜在表示。在PVC之后，Shao等人[26]然后引入加权NMF和NMF2，1正则化器来提高性能。此外，Huet al.建议DAIMC方法[6]以实现一致性-tral clustering [7，10，11，28，29，35].二分图的主要优点多视图二分图的传统框架可以写为：min<$X（i）− C（i）Z（i）<$2+ S（Z（i），Z），s.t. Z（i）≥0，Z（i）≥1 = 1，基于半NMF表示对齐和基本空间对齐。 的Z（i），ZF哪里（一）基于图或基于核的IMC方法试图以各种方式重新覆盖在多个视图上一致的相似性图或核矩阵。考虑到图拉普拉斯项，IMG [49]通过在多个视图上探索紧凑的全局结构来扩展PVC。Liu等[21]将填充和聚类结合到一个框架中，以提高聚类性能。上述两类算法都是浅层算法.随着深度学习的广泛应用，许多研究者通过深度神经网络提取高层信息来解决IMC问题。Cai等人提出了一种对抗性不完全多视图聚类方法[41]，将其扩展到多个视图。之后，Wenet al.提出了一个DIMC- net[40]，它自适应地融合了视图特定的高级信息，以寻求共识表示。在DIMC-net的基础上，CDIMC-net [38]还引入了一种自定进度的策略，以减少离群值的负面影响2.2. 二分图聚类二分图是一种有效的多视图处理大规模数据集的策略，C（i）Rdi×m表示选定或采样的m个第i个视图中的实例从而使相应图的大小由Rn×n降为ZRm×n。在此之后Line，Li et al.提出一种替代的锚点采样策略来构建单个锚点图，然后将它们组合到共识图中[10]。如前锚子空间方法所示，锚图可以帮助减少存储和计算时间，同时提供可比的聚类性能。然而，现有的二分图框架不能处理IMVC情况。在下一节中，我们将介绍IMVC-CBG，用于使用二分图进行大规模IMVC的第一次实践。3. 基于一致二分图的不完全大规模多视图聚类（IMVC-CBG）3.1. 问题公式化为了处理二部图的IMVC问题，我们首先定义了X（i）的不完全性。给定指示向量h（i）Rni包含排序中第i个视图的ni个现有样本的索引，我们可以定义索引矩阵3iYYiTMJGZG濷一只羊在看你濷一只小老虎在看濷<1YGS VRK<[2019 - 04- 25]<[iK]vYGSVRK3iYYiTMJGZG濁濁濁9779A=QI.∀···∈¨¨¨¨Σ|Σ|--vΣ∈∈OOi=1vOOOα，W（i）vi=1.Σ⊗我¨F¨ ¨FKKnj=1.ΣA（i）∈Rn×ni对于第i个视图如下，（一）PQ1、如果条目h（i）=p， q= 1，2n，0，否则。（二）很容易证明X（i）A（i）Rdi×ni是在第i个视图中排序的完全数据矩阵。因此，我们可以采用Eq。（1）以单视图二分图构造为例，F[YiUTminXZ（i）（一）A（i）（一）Z（i）2A（i）+ A（Z）F（一）），s.t.Z（一）≥0，Z（i） 1=1，（三）8KIUTYZX[IZI UT然而，如果不完整比率相对较大（非常小的ni），则基于k均值或均匀采样的锚点选择策略将在可用实例信息不足的情况下严重影响锚点质量与现有的完全二部图策略不同我们决定基于视图中的所有可用实例来迭代地学习锚IMVC-CBG旨在构建图2.用概率模型解释我们的框架。建立转移概率矩阵为M=Z的一步平稳马尔可夫随机游动，其中M1= 1。然后，第i个样本和第j个锚点的一步中的转移概率如下，带有锚点的一致二部图结构首先（一）Z记（一）Z记（五）投影多维完备数据X（i）A（i）∈RdiM（xi cj）=mj=1、MZ记（cj xi）=ni=1.Z记一个共同的潜在空间。利用共识潜在锚C，我们将IMVC-CBG的优化目标定义为对于图2中跨视图的多个二分图，不完整的示例可以重新分级为与接着，min<$α2<$W（i）X（i）A（i）−CZA（i）<$2+λ<$Z<$2，i=1chors（虚线），并且相应的转移概率为0。通过将它们融合成完全二部图Z在适当拉伸的情况下，双阶跃转变可能-S.T. α<$1 = 1，W（i）W（i）<$1= I，CC<$1= I，Z ≥ 0，Z<$1 = 1。基矩阵可以被重构为S=Z<$Λ−1Z，其中其中X（i）Rdi×n是原始数据的第i维，CRk×m是具有m个选定锚点的统一锚点矩阵。 λ是一致二部图构造和正则化项的平衡超参数。虽然二分图学习工作已被广泛采用，以减少复杂性的多视图聚类，ING，现有的工作都没有成功地采用IMVC任务。从Eq.（4）简单介绍-引入不完全指示矩阵A（i）∈Rn×ni，随机矩阵，因此我们可以简单地对Z执行SVD以获得聚类标签。推导的细节可以在补充材料中找到。3.3. 优化方程（1）中的优化问题（4）当同时考虑所有变量时，它不是联合因此，我们提出了一种交替优化算法，在其他变量固定的情况下，对每个变量进行带来（n2）空间复杂度和（n3）时间复杂度，这成为大规模数据的严重问题。我们将我们的贡献总结为：（i）通过揭示X（i）A（i）A（i）=3.3.1更新投影矩阵W（i）v- 是的当C、Z和α i固定时，目标函数w.r.t.W（i）可以表示为：X（i）<$P（i）其中P（i）=1d我1nJa（i）∈Rdi×n且a（i）=j，lΣ2¨W（i）i=1（一）（一）（一）（i）（2）（一）（i）[a（i），.，a（i）]n，其中a（i）=ni A（i）。与仔细最小α i？W X A−CZA？F，标准偏差 W W= Ik.设计目标Eq.（4）、减少了空间组合，复杂度从（vn2）到（dn），时间复杂度为（dn）。（ii）IMVC-CBG是一项开创性的工作，它集成了IMVC和二分图，首次成功实践了大规模IMVC任务。(iii)根据我们的建议，（六）由于每个W（i）彼此分离，我们可以将等式（1）变换为等式（2）。（6）通过迹扩展Frobenius范数并去除与W（i）无关的项，框架，新的二分图方法IMVC可以很容易地提出，并有利于社区。.澷濣濢濢濙濗濨濙濘濂濣濨 澷濣濢濢濙濗濨濙濘澹濬濝濧濨濝濢濛 濧濕濡濤濠濙濁濝濧濧濝濢濛 濘濕濨濕澵濢濗濜濣濦、C、Z（四）ΛII=ZIJ. 很容易证明，S是一个双l=1- -C键9780MaxW（i）Tr（W（i）B（i）），s.t. W（i）W（i）=Ik， （7）3.2.概率模型在本节中，我们为图2中的IMVC-CBG提供了深入的理论解释。[16]我曾其中B（i）=X（i）P（i）Z<$C<$。 假设B（i）的奇异值分解（SVD ）结果为U<$V<$，通过计算U k V k<$，可以很容易地得到最优W（i） 根据[34]。的总时间复杂度9781i=1i=1v我i=1我22Jα2-W（i）X（i）A（i）−CZA（i）<$τ1τ2τv*jF*jfF*jJ加上Z1= 1，我们可以很容易地得到，--Σ--¨−¨i=1i=1F（八）在本节中，我们将分析我们提出的算法-算计W（i）需要O（d（nm+km+k2）），算法1IMVC-CBG迭代3.3.2更新共识锚点矩阵C。在W（i）、Z和αi被固定的情况下，可以如下更新共识锚定器MAKICv2输入：输入v查看不完整的数据集 X（i）v得双曲余切值.缺失索引P（i）v和聚类数k。初始化：用1初始化C、Z和α i。1：不收敛时2：通过求解方程中的问题来更新W（i）（七）、通过解决方程中的问题来更新C。（九）、第三章：¨ ¨与W（i）的优化类似，C（i）的优化也是如此由方程式（8）等于下列形式最大Tr（C/G），s. t. CC=Ik，（9）C第六章： end while第七章： 通过对Z执行SVD来获得U。8：输出：对U执行k-均值，以获得最终聚类结果。其中G=ωvα2W（i）。X（i）<$P（i）<$Z<$。类似地，（i）（i）（一）（i）（2）更新变量A的最优解可由C的左奇异矩阵与右奇异矩阵的乘积求得。计算C的总时间复杂度需要其中τ i=W X ACZAF。 根据柯西-布尼亚科夫斯基-施瓦茨不等式，αi可以通过αi=e直接获得，其中e=每次迭代的时间复杂度为O（ndk+ndk+m2k）1.一、时间复杂度为1+1+···+1τi时间复杂度为O（nk（d+m））。3.3.3更新共识锚点图Z。固定其他变量W（i）、C和αi，用于更新变量Z的优化问题可以重写为，随着迭代的进行，上述优化中的四个变量由于每个子问题都可以达到其全局最优，因此目标值将单调下降，直到最小值α2<$W（i）X（i）A（i）−CZA（i）<$+λ<$Z <$，达到了收敛条件，Zi=1我S.T. Z≥0，Z≥1=1。¨F¨ ¨F（十）可以很容易地证明目标函数为零。列出了上述优化的整个过程DenotingZ:,jasavectorwiththei-thelementtobezij,weoptimize Z by column:2minZZ：，j−fj，s.t. Z1=1，Z≥0， （11）在下面的算法1中。3.4. 讨论哪里Σvα2 X（i）<$W（i）<$C.我们写的是-=i=11J我Rithm在空间/时间复杂度和收敛性方面。jλ+λvα2P（i）在此基础上，对SOTA与Eq.的Grangian函数（11）作为，L（Z：，j，β，η）=<$Z：，j−fj<$2−βj。Z<$1−1<$−η<$Z：，j，表2中的IMVC方法。空间复杂性：在本文中，主要内存我们的方法的代价是矩阵W（i）∈Rk×di，P（i）∈其中β和ηj是各自的拉格朗日乘子。Rdi×n，C∈Rk×m，Z∈Rm×n. 因此，空间com-然后KKT条件写为，IMVC-CBG的复杂度为（d+m）（n+k）。在我们的算法中-.Z：，jηj— FJ— βj1−ηj=0，（十三）Rithm，mn和kn。因此，IMVC-CBG的空间复杂度为O（n）。我们总结了*j1 +f1IMVC-CBG由四个优化步骤组成，Z：，j=max（f）+βj1，0），βj=j。（十四）M之前提到过。 更新时。W（i），it成本由于Z的最佳值可以解析地获得，O（d（nm+km+k2）），得到最优值。似-min一，s.t. CC= Ik.4：通过求解方程中的问题更新Z。（十一）、5：通过求解方程更新αi（15）、i=1我*j（十二）Z：，j=0，在下面的表2中比较算法。时间复杂度： 的计算复杂度时间复杂度为O（nk（d+m））。9782i=1OOO我Oi=1.当分析获得Z时，最大为upd a ting。W（i）时间复杂度为O（ndk+nm2+ k）3.3.4更新视图系数αi。固定无关变量，我们就得到了更新αi的最优化问题.（ nk （ d + m ） ） 。 计算α的 时 间 成 本 是 （ nk（d+m））。因此，优化过程的总时间成本为（n（dk+dk+dm）+mdk）。然而，我们提出的计算复杂性最小αivi=1α2τi，S.T.α1=1，（十五）优化算法是线性复杂度（n）。在优化之后，我们对Z执行SVD以获得Σ9783On样品在Ri=1-th视图，= 1，其他─样本，随机矩阵H=H，h，. . .，h谱嵌入并通过k均值输出离散聚类标签[35]。后处理需要（nm2），也是关于样本的线性复杂度.总之，我们的算法实现了IMVC与线性时间复杂度，这表明IMVC-CBG的效率。表2.SOTA IMVC方法的复杂性分析方法内存开销时间复杂度BSV [23]vn2O（n3）MIC [26]vn2+nd+nvk+vdkO（n3+n2dk）[17]vn2+vnkO（vn3）DAIMC [6]vn2+nd+nk+dkO（nd3+ndk）APMC [5]nd+vnm+nkO（n3+nmd+m3） UEAF [37]vn2+dn+nvk+dkO（n3+dk2）MKKM-IK-MKC [22]vn2+vnkO（vn3）EEIMVC [18]vn2+vnk+vk2O（nk2+vk3）FLSD [39]vn2+dnk+nkO（nd2）我们的mn+（d+m）kO（ndk+nmd+mdk）4. 实验4.1. 数据集我们在九个广泛使用的多视图基准数据集上进行实验 ： NG 、 Caltech101-7 、 Caltech101-20 、 BDGP 、Caltech101-all、NUSWIDE、MNIST和Youtube- Face。表3详细列出了这些数据。具体地，Caltech 101 -7和Caltech 101 -20都是图像数据集Caltech 1012的子集。BDGP3包含5类2500个果蝇胚胎样品。NUSWIDE4是一个对象识别数据集。MNIST5由0到9的手写数字组成YoutubeFace6是一个由YouTube生成的视频数据集，包含101499个实例。这些数据可以在7下载。4.2. 比较方法和实验设置表3.实验中的不完整多视图数据集数据集大小类查看维度NGS50053500/500/500加州理工学院101 -714747648/40/254/198/512/928加州理工学院101 -20238620648/40/254/198/512/928BDGP公司2500531000/500/250加州理工学院101-全部9144102548/40/254/512/928NUSWIDE3000031565/226/145/74/129MNIST60000103342/1024/64YoutubeFace10149931564/512/64/647/838框架. 双对齐不完全多视图聚类（DAIMC）[6]基于半NMF学习具有对齐样本的公共表示，并使用2，1正则化回归对齐基矩阵。锚带来轻松：部分多视图聚类（APMC）[ 5 ]的一种非常简单的方法融合了构造的一个chor相似性矩阵，并且仅限于在具有两个视图或三 个 视 图 的 数 据 集 上 使 用 。 不 完 整 多 视 图 聚 类（UEAF）[37]的统一嵌入对齐与缺失视图推断通过使用局部保留联合估算缺失 带不完全核的多核k均值算法（MKKM-IK-MKC）[22]将内核估算和内核k均值聚类统一到一个联合框架中。高效和有效的规则化不完全多视图聚类（EEIMVC）[18]联合估算低维基本特征矩阵，并寻求用于聚类的共识特征矩阵具有灵活局部结构扩散（FLSD）的通用不完全多视图聚类[39]联合学习视图特定的潜在表示和共享表示。在我们的实验中，我们随机选择np对sam-在所有视图中观察到的问题对于其余的n−n12（n−np）∈生成{0，1}（n-np）×v，0

下载后可阅读完整内容，剩余1页未读，立即下载