面向大规模数据的非负矩阵分解多视图聚类算法及其性能优化

12344OO面向大规模数据的一次多视图聚类刘继元，王欣，刘*，杨宇翔，刘力，王思齐，梁伟轩，石江永国防科技大学中国湖南长沙410072.{liujiyuan13，xinwangliu，yyx} @ nudt.edu.cn摘要现有的基于非负矩阵分解的多视图聚类算法针对不同的数据视图计算多个系数最后的分区总是从经典聚类技术（如k-均值）的共识中获得。然而，非负性约束阻止获得更有区别的嵌入。同时，这两步的过程未能统一多视图矩阵分解和分区生成紧密，导致性能不佳。因此，我们提出了一个单通道多视图聚类算法，通过消除非负性约束和联合优化上述两个步骤。通过这种方式，生成的划分可以指导多视图矩阵分解，以产生更有目的的系数矩阵，作为反馈，提高划分的质量。为了解决这一优化问题，我们设计了一个交替的策略，该策略在理论上是收敛的。此外，该算法不含参数，具有线性复杂度，具有一定的实用性。最后，在基准测试上将该算法与文献中的最新进展进行了比较，验证了该算法的有效性、优越性和效率。1. 介绍随着多视图数据的广泛传播，提出了多视图聚类（MvC）算法以最大限度地整合视图之间的互补信息并揭示用于聚类的底层数据结构[10，18]。它们大多是在经典聚类方法的基础上发展起来的，如非负矩阵分解、k-均值、谱聚类等。[26，21，9，17]。因此，MvC方法可以根据这个标准进行粗略的分类。在本文中，我们集中在非负矩阵分解的基础上。*通讯作者非负矩阵分解（NMF）[14]是机器学习和数据工程任务中最基本的聚类技术之一。它将输入数据分解为两部分，即系数和基矩阵[12]。正交性[5]和低秩约束[29]在矩阵分解中得到了广泛的研究，实现了有希望的性能。在MvC环境中，Gao et al.通过对每个数据视图执行NMF来获得系数矩阵，然后将它们推向公共共识[6]。相反，一些研究假设所有视图共享底层共识流形，因此使用单个系数矩阵来捕获内在数据结构[7]。在上述两个框架上，大量研究人员[27，30，24，7，25]借用了[2]中的流形正则化来进一步提高聚类性能。具体而言，每个视图可以被视为流形，并且流形正则化能够保留数据的局部几何结构[30]。然而，它需要构建一个或多个相似图，引入更高的计算和存储复杂性，有时（n2）甚至（n3）[27]。Nev- ertheless，Gaoet al.在基矩阵上施加正交性明确[7]，而Zhang et al.隐式地这样做[27]，其中两者都在实验中被证实是有效的。然而，上述方法通过强加非负性来限制区分性嵌入学习，为了解决这个问题，我们提出了一个单通道多视图聚类（OPMC）算法。首先，我们移除系数矩阵和基矩阵的非负性约束。而不是明确地将矩阵分解和k-均值的目标结合在一个统一的公式中，我们用一个consense硬分区矩阵和一个视图特定的质心矩阵来近似系数矩阵OPMC的概述如图所示。1.可以观察到，所生成的硬划分引导多视图矩阵因式分解以产生更有目的的系数矩阵，其作为反馈，提高了划分的质量。为了验证方案的有效性，我们12345..≈..≈010001点积100001010点积近似损失·2v=1OF∈∈--F划分生成多视图矩阵分解硬分区质心矩阵系数矩阵基矩阵数据视图图1.提出的OPMC算法概述（以两个视图的数据为例）。两个语义部分，包括多视图矩阵分解和分区生成。从左到右，硬分割矩阵通过分别乘以质心矩阵来经过两个视图特定变换然后，获得对应于每个视图的系数矩阵注意，我们使用虚线来表示系数矩阵，因为它没有在我们的算法中明确给出。通过将系数矩阵与基矩阵相乘，可以重构数据视图。从右到左，虚线箭头指示聚类信息从原始数据视图逐步流向共识硬分区。通过比较单视图OPMC与ONMF设计消融研究[5]。此外，进行了大量的实验和OPMC建立国家的最先进的性能相比，最近的进展，在六个基准。最后，这些贡献概述如下：1) 我们发现去除非负性约束和uni-其中f（）是损失函数。在大多数情况下，采用l2和Kullback-Leibler散度损失[14]。此外，Ding et al.探索正交约束对矩阵分解方法的好处[5]。通过采用l2范数并将基矩阵正则化为正交，等式(1)可以配制成利用分块生成的fying矩阵分解可以提高聚类性能，并验证了它们的有效性minH≥0，W≥0X−HWS.T. WW= Ik.（二）消融研究的有效性2) 我们提出了一种非参数OPMC算法来解决多视图数据聚类问题。它在六个基准测试上实现了最先进的性能。3) 我们设计了一个替代策略来解决由此产生的优化问题。从理论和实验上分析了算法的收敛性和计算复杂度（n）2. 相关工作2.1. 单视图矩阵分解通过对系数矩阵H执行经典的聚类算法（主要是k-均值）来获得最终划分。2.2. 多视图矩阵分解给定来自V个视图XV的数据，其中Xv由Rn×dv得出，且dv是v的特征维度。多视图矩阵分解就是寻找一个最优H，以揭示不同视图的一致性数据结构。Liu等人制定了一个联合矩阵分解过程，该过程具有将每个视图的系数矩阵Hv推向公共共识H[6]的约束，如图所示V V给定n个数据观测值X∈Rn×d，从k个数据中抽取-minH≥0，Hv≥0，W≥0ΣXv−HvWv2+λΣg（H，Hv）分配，矩阵分解算法旨在decom-v=1v=1将 它们 分 成两 部 分， 即 系数 矩 阵 HRn×k和 基矩 阵WRk×d。最典型的矩阵因子化方法是NMF [1]，它将两者都正则化S.T. g（H，Hv）= γ vH −HvQv2，（三）矩阵为非负，如图所示其中Qv是用于标量匹配的对角矩阵。同时，Gao et al.建议捕获基础数据minH≥0，W≥0f（X，HW）（1）所有数据中具有一致性系数矩阵H的结构123462ΣV2v=1p=1，pv=1vY，{Cv}V，{Wv}VVvvvvK12KvvΣ联系我们WYvF观点[7]。制剂呈现为V统一Eq. (5)和（7），3-因子矩阵分解可以被导出为2minΣX−HW+λh（H）minXv−YvCvWvFvv（八）H≥0，W≥0v vFv=1Σ（四）Yv，Cv，WvS.T. WvW= Ik，y（i）∈ {e1，e2，···，ek}.S.T. h（H）= TrH*（λvLv）H，v=1考虑到V数据视图，OPMC的目标是-模拟成其中Lv是第v个数据视图的拉普拉斯矩阵与所获得的一致性系数矩阵H，标准k-minv=11ΣXv=1v=1-YCW采用计算数据划分的方法。S.T. W W= I，y（i）∈ {e，e，···，e}.3. 该方法可以观察到，单视图和多视图矩阵分解方法都遵循数据聚类的两步过程。因此，系数矩阵的生成没有足够的聚类结果的指导，导致没有前途的性能。为了解决这个问题，建议的OPMC结合在一个统一的目标的两个步骤。3.1. 目的从第v个视图获取数据Xv，可以通过下式获得相应的系数矩阵：注意，硬分区在特定的聚类任务中是唯一的，因此，我们在所有视图中采用共识Y同时，我们将所有视图的权重设置为1/V。这被称为元素明智的目标，每个特征元素的损失是平等的测量。另一种被广泛采用的设置称为视图方式，其中权重在每个视图丢失时浮动在实验中，我们发现元素明智的OPMC优于视图明智的一致。然而，可以观察到，在等式（1）中不需要超参数。(9)，这是一个很大的改进，在文献中的最新进展，因为没有验证集的参数调整在聚类任务。3.2. 优化minHv，W vXv−HvWvS.T. WvWv=Ik（5）为了优化Eq.（9）中，我们设计了一种替代策略，其中每个未知变量通过在每个步骤中固定其他变量来求解。其中正交正则化被施加于Wv.与Eq相比。(2)，我们去除了对Hv和Wv的非负性约束。这鼓励模型在更大的搜索重新搜索中学习更具区分性的嵌入3.2.1Wv子问题显然，{Wv}V独立于每个gion。作为一个副产品，它有利于优化过程中，封闭形式的解决方案，可以获得他们在每次迭代。此外，k-均值算法的目标是将数据划分为k个不相交的聚类，每个聚类的特征为其他. 因此，我们固定WpVv，CvV将关于Wv的优化公式化为最大Tr（WvB）S.T.WvWv=Ik，v和Y，（十）其质心，其可以被公式化为其中B = XYC。当量(11)可以被有效地优化VVminHv−YvCv2S.T. y（i）∈ {e1，e2，···，ek}，其中y（i）表示Y的第i行。与此同时，Y（六）∈奇异值分解（SVD）技术，而封闭形式的解决方案可以通过定理1获得。定理1. 定义矩阵B的经济秩k奇异值分解为UΣV，得到了方程（1）的闭合解。(10)应Rn×k是硬分块矩阵，每行是k维空间的一个标准正交基。此外，Cv∈Wv*=U V。（十一）Rk×k是一个质心矩阵，它的第j行表示H的第j质心v.而不是组合Eq. (5)（6）在一个统一的公式中，OPMC首先通过下式将Hv逼近为Yv和CvHv≈ YvCv。（七）2VvF（九）v12347--j=1j=1{}≤Σ证据 假设F =VWvU，当量（十） 可以 重 写 为 maxFTr （ FΣ ） ， 其 中FF=VWvUUWvV=I。 如果F是正交的，则它的所有元素都是从1到1。同时，Σ是一个对角矩阵，由非负奇异值组成σjk. 因此，Tr（FΣ）kσj 。 当 F 是 单位矩阵时等式成立，从而得到等式：（十一）、12348vv=1OCvv=1联系我们v=1Vv=1J（Y ，{C}，{W}）（t）V（t）V（t）v=1v=1vv我Jv=1vvVJFv=1v=1p=1，pvVv=1表1. NMF和建议的OPMC之间的复杂性比较。NMFc是多视图数据上NMF的初始设置（更多详细信息见第4.1节）。 注意，等式（1）中的SVD分解（11）takesO（a1d2k+a2k3），其中a1和a2是常数[8]的一项建议。同时，d = ΣVdv。算法子问题加法乘法除法整体NMFcU（3k−1）dn−kd3kdn+kd kd（kdn）V（3kd-k-d）n k（3d+ 1）n nkWvdv n+k（2k−3）dv+O（a1d2k+a2k3）2k2dv+O（a1d2k+a2k3）-OPMCCvdv n+（k−1）kdv−k2k2dv+k2kYk（2d−1）n+（k−1）kd k2d+kdn-O（kdn）3.2.2Cv子问题类似 对于Wv子问题，我们固定{Cp}VV3.3. 复杂性和收敛性下面提供所提出的OPMC的计算复杂度分析。根据定义，{Wv}v=1和Y.因此，Eq. (9)降低到我们可以找到Xv∈Rn×dv，Cv∈Rk×k和Wv∈Rk×dv.minTr（YYCvCv）−2 Tr（WvXvYCv）.（十二）通过将其导数设置为零，可以在以下情况下Cv=（YY）−1YXvWv。（十三）观察到Y保持聚类分配，计算可以通过执行索引和求和操作而不是涉及Y时的矩阵乘法来加速。例如，A=YCv需要k2n个元素乘法。或者，如果Y（i，j）= 1，则A（i，j）= Cv（j，j），这显然比前一种方法快得多。在具体地，在表1中分析了OPMC的复杂性它3.2.3子问题可以观察到，所提出的算法是线性的数据其中d=ΣVd v. 更多-可以观察到，硬分区Y的第i行满足1/K编码方案。因此，我们对k个候选者进行穷举搜索，即e1，e2，，ek，来找到解的形式可以表示为y={e|其中下标i，j表示对应的第i，j行此外，与经典的NMF相比，它在每次迭代中需要更少的运算，包括加、这两个观察结果证明了OPMC然而，建议的OPMC理论上是guaranteed收敛到局部最小值。[19]我也一样。下面给出了所提出的OPMC的收敛性证明为了便于表达，我们重新表述在Eq. (9)成矩阵此外，还概述minY，{Cv}V，{Wv}VJ（Y，{Cv}v=1，{Wv}V）（十五）在算法1中。算法1一遍多视图聚类算法由于优化策略是循环过程， 我们使用上标t来表示优化轮次t. 在W_v子问题中，给定Y（t）和{C_v}V（t），输入：数据{X}V和簇kV（t+1）v=1输出vv=1得到{Wv}v=1，：硬分区Y1：初始化Y，{C}V（V）随机地（t）V（t）V（t+1）V Vv=1v=1v=1v=1（十六）第二章： 而真正的

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