基于图的多视角聚类算法综述*

王春杰 何进荣 王文发

（延安大学数学与计算机科学学院 延安 716000）

1 引言

目前，多视角数据在很多领域得到了广泛的应用。例如，一个网页可以表示在给定页面上出现的单词和链接到该页面的超链接中出现的单词。对象可以通过各种成像模式可视化。不同的视角通常提供互补信息，因此从单个视角获取的信息并不能完全描述所有相关对象。来自不同领域［1～3］的各种集合通常表现出大量的异构属性。通过统一不同视角的共性和互补性，准确地聚类多视角对象仍然是一个挑战［4］。多视角聚类通过假设所有视角共享相同的集群结构，寻求多个表示的数据点划分。MvC算法通过结合不同视角的信息，试图获得比简单地将不同视角的特征连接在一起所得到的更精确的聚类。近年来，多视角聚类作为一种利用同一对象的冗余视角来提高聚类精度的新范式，由于能够有效地捕获隐藏在数据中的复杂结构，已经得到了广泛的研究［5～6］。传统的聚类方法是先构造一个加权无向图来度量数据样本的成对相似性，然后完成基于谱图分析的聚类。提高图聚类性能的关键在于构造一个高质量的相似度图，使其能够更准确地捕获样本之间的内在关系。

近年来，人们提出了各种基于图的聚类算法。这类方法试图在所有视角之间找到一个融合图或网络，然后在融合图上使用图形切割算法或者其他技术来生成聚类结果。融合图（或网络）被广泛用于表示对象之间的关系，其中每个节点对应一个数据对象，每个边描述一对对象之间的关系。在实际应用中，这种关系通常用相似性或亲和关系来表示，即由数据相似性矩阵生成输入图矩阵。在多视角数据中，数据对象由多个图形捕获。由于每个单独的图形都可以捕获数据的部分信息，而所有图形具有相同的数据底层聚类结构。因此，这些图可以通过学习数据对象之间的整体相关性而相互加强。在这一类中，文献综述分为三部分即基于图的MvC、基于网络的MvC和基于谱的MvC。

2 基于图的多视角聚类

一般来说，多视角图聚类数据融合过程（如图1 所示）。多视角聚类的目的是找到一个跨视角的融合图，然后使用图割算法或其他技术生成最终的聚类结果

图1 基于图的聚类的一般过程

基于多重相似图的MvC，文献［7］讨论了一般的聚类问题。提出的链接矩阵分解方法从多个图中提取共性因子，形成了多种基于图的聚类方法，可以自然地应用于多视角数据。文献［8］提出了一种多视角文档聚类算法，该算法首先将单视角聚类算法应用于每个视角的数据矩阵，以生成多个分块。最后，形成统一的相似矩阵进行聚类。文献［9］针对大多数方法都没有充分考虑不同视角的权重，需要额外的聚类步骤来生成最终的聚类。他们提出了一种通用的基于图的多视角聚类来解决这些问题。该模型将所有视角的数据图矩阵进行融合，生成一个统一的图矩阵。文献［10］为每个视角添加了一个自适应权重去避免异常视图，他们采用不同的权重来表示不同簇之间的相似性，虽然该方法学习了每个图的权重，但还有其他的参数。类似的文献［11］提出的基于位置加权的文本聚类模型。文献［12］则提出了一种不需要调整参数的聚类算法，基于结构相似性和顶点与其邻域之间的结构依赖关系对顶点进行聚类。文献［13］开发了一个无参数的多图框架来自动学习所有图的权重。同时，还研究了多视角数据的非监督特征选择问题。随后文献［14］提出了两种无参数加权投影聚类方法，它们同时采用两种无参数策略自动学习每个视角的最优权重。文献［15］也提出了一种适用于多视角聚类的可扩展、无参数的图融合框架，以自监督加权的方式寻找多视角间的可兼容的联合图。同时，利用连通性约束对联合图进行操作，使连通分量直接表示聚类使算法具有较好的稳定性和可扩展性。随即文献［16］提出了基于锚点和二分图的思想的一个可扩展的图形学习框架，它构造一个描述样本与锚点之间关系的二分图。同时，也是采用连通性约束来保证连通分量直接表示簇。文献［17］提出采用图形嵌入来保留原始的数据结构，他们致力于将多个视角的信息编码成一个紧凑的二进制代码，学习了来自多个视角的互补信息。考虑到不同视角对最终聚类结果的贡献不同，同时为每个视角自动分配权重的策略，以更好地指导聚类。文献［18］提出了一种在基系统框架下工作的多视角聚类方法，它能够有效地构造数据图矩阵，自动加权每个图矩阵，直接生成聚类结果。文献［19］同时进行鲁棒表示学习和最优图学习，不仅能有效地减少噪声的影响，还保持了数据的局部结构。在相似矩阵的Laplacian 矩阵上施加合理的秩约束，使学习得到的图具有理想的结构，可直接用于聚类。文献［20］在Laplacian 矩阵上加入秩约束，通过全局图直接得到聚类指标，而不执行任何图割技术。

此外，现有的聚类算法大多侧重于在全局上优化特定的质量度量，而没有仔细考虑局部结构的问题，这些局部结构的问题在际应用中可能具有重要意义。文献［21］提出了一种群体感知的多视角融合方法，用于图像聚类。该方法能够以更紧凑的视觉效果将图像分割成不同的组，并为组内和组间的图像赋予不同的融合权重。与全局融合方法相比，这种群感知融合模型提供了更灵活的融合策略和更有效的图像间相似性度量。文献［22］提出了一种基于递归计算的结构相似度测度的无向图聚类算法。该方法在保持原图局部结构信息的同时，增强了鲁棒性好、提高了的聚类结果。最近，文献［23］提出了一个公共子空间集成模型。该模型通过联合保留每个视角的局部几何来主动学习公共子空间，同时合并全局分区信息以增强学习过程中的可分性。

另一方面，本文还分析了最近邻技术和稀疏方法相结合的算法。例如，文献［24］提出了自适应邻居聚类，通过自适应局部结构学习相似度矩阵，在数据相似度矩阵的Laplacian 矩阵上施加秩约束，得到理想的聚类结构。文献［25］还对具有自适应邻域的多视角聚类和半监督分类同时进行聚类、半监督分类和局部流行学习，从原始多视角特征中获得的图形可以划分为特定的聚类。文献［26］提出了利用自适应邻域学习图像聚类（Learning with Adaptive Neighbors，LAN）来学习基于给定数据图的图，该方法在提高构造相似图的质量方面都取得了重要进展。LAN 尝试学习基于给定数据图的块对角数据相似度矩阵，从而使新图更适合于最终的聚类任务。与上述方法不同，文献［27］为了保持数据间的相似性，用一个修正的K-最近邻图对数据生成过程进行了正则化。此外文献［28］提出了通过学习鲁棒的结构化相似图并进行聚类。特别地，具有适当概率邻域分配的结构图是在抗噪声和异常值的鲁棒潜在表示上自适应学习的。且该模型不依赖标签离散化策略，通过对学习的相似图进行分割，可以直接得到离散的聚类标签。文献［29］也提出了一种鲁棒秩约束稀疏学习方法，引入稀疏表示的L2，1范数目标函数来学习具有鲁棒性的最优图。在初始图的邻域内搜索图保持数据，通过引入秩约束，可以直接将学习得到的图作为聚类指标，在不需要额外处理的情况下得到最终的结果。文献［24］在L2，1范数基础上，提出了拉普拉斯秩约束（Constrained Laplacian Rank，LRC）算法，LRC 学习了一个新的块对角数据相似度矩阵，可以直接将学习得到的图作为聚类指标，也不需要额外处理的情况下得到最终的结果。

最近，文献［30］设计了一种基于图的多视角聚类算法，称为拉普拉斯秩约束多视角聚类（Laplacian Rank Constrained Multiview Clustering，LRCMC）。首先，利用文献［24］的LRC算法在每个视角中同时找到亲和图和嵌入矩阵，以确保图的结构在相同的连通分量上。然后，基于文献［25］的方法，使用LRC方法获得一致图，其连接分量与每个视角的亲和图相同，最后得到了聚类结构。在图融合过程中，采用反距离加权方案为每个视角的关联图［25］设计不同的权重，更加有效地调整了一致图的结构。此外，将图学习、图融合和聚类的过程耦合成一个优化问题，以更新更准确的一致图，并改进聚类的结果。文献［30］提出的LRCMC算法的目标函数表为

图2 拉普拉斯秩约束多视角聚类的流程图

3 基于网络的多视角聚类

由于大多数基于图的MvC 方法通常假定对于不同的视角有相同的数据对象集，因此，不同视角中的数据对象之间的关系是一对一的。然而，在许多现实生活中的应用，如社会网络、文学复习网络和生物互动网络中，数据是从不同的领域收集的，一个领域中的一个对象可能对应于另一个领域中的多个对象，从而导致许多对应关系。用网络而不是图表来表示这种关系可能更合适，这是区分基于网络的MvC 和基于图的MvC 的主要原因。图形在现实生活中无处不在。生成了大量的图形数据，例如社会网络［31］、生物互动网络［32］和文献引用网络［33］。基于网络的MvC 的相关工作从［34］开始提出的基于网络的多视角图形聚类框架，该框架描述了几个关键特性，多对多映射关系、权值映射以及不同网络之间的部分映射。然而，不同的网络可能有不同的数据分布，所以文献［34］中的假设所有的网络都承认一个共同的集群结构不再适用。因此文献［35］提出了一个灵活的框架，允许跨不同网络的多个底层聚类结构，将领域相似性建模为一个主网络，可用于对不同网络中的聚类结构进行正则化。随后文献［36］又提出了一种新的方法ComClus 同时对多个网络进行分组和聚类，ComClus 在将节点聚类看作网络特征和学习适当的子空间以区分网络组等方面是一种新颖的方法。在学习过程中，网络分组和网络聚类相互耦合、相互增强。此外，ComClus 还可以利用网络组的先验知识，以半监督的方式进行网络分组，从而进一步提高聚类的准确性。还有许多其他方法不使用概率建模，例如文献［37］提出的相似网络融合（SNF）使用不同类型的基因组特征构建病人相似网络，并融合多个患者相似网络以实现一致性网络，开发了一个更简单、更通用的框架相似性网络融合，将多个网络组合成一个融合的协商一致网络。融合后的网络从多个视角中获取互补信息，并且比从每个视角中学习到的单个网络对噪声的鲁棒性更强。基于文献［37］的主要思想文献［38］提出了一种鲁棒相似网络融合（RSNF）方法，实验结果表明了该策略的有效性。在SNF的基础上，文献［39］开发了具有多种优点的亲和网络融合（ANF）。与SNF［37］相比，ANF 为具有多视角数据的复杂对象聚类提供了一个更为通用的框架，并能结合视角权重。ANF所需的计算量要少得多，文献［43］很好地说明了ANF 实际上只需要一次迭代就可以获得与SNF 一样好甚至更好的结果。

最近，文献［40］引入了直接连通点的概念来发现直接连通点的相似点，并引入了间接连通点的最短路径策略，提出了一种新的计算顶点相似性的协同相似度方法用于复杂网络中的社区检测。该算法借助于K-Medoid 框架，基于计算相似度的距离度量，构造了一组顶点。类似的有文献［41］提出了一种基于K-medoid 框架的新的聚类算法，该算法采用了一种考虑属性重要性的协同相似性测度来检测社区，针对间接连通节点以及均衡属性相似度和距离函数，提出了一种新的路径策略。与上述框架不同，文献［42］利用节点的属性以及拓扑信息结合的方式提出了脑网络聚类模型。文献［43］也做了一种新尝试将大脑网络作为一个完整的图形实例嵌入，将多个图叠加成多个部分对称张量，并利用张量技术同时利用多视角和多图脑网络之间的依赖和相关性。通过利用多视角、多图的交互作用，在聚类脑网络上具有优越的性能。

示例2：文献［44］也提出了一种基于聚类的多视角网络融合框架，用于估计多视角脑网络的脑网络图谱，其中每个视角都捕捉大脑结构的一个特定方面，首先将多视角网络非线性地融合成一个单一的融合网络，然后对融合网络进行聚类。同时以无监督的方式识别具有相似连接特性的个体，然后在每个聚类内进行平均，生成具有代表性的网络图谱，通过对所有簇的平均表示，构造了最终的多视角网络图集。这是前所未有用于估计健康人群和无序人群的多视角脑网络图谱。构建多视图脑网络图谱可以作为比较研究规范个体脑网络的参考，通过探索多个不同的学习方法来嵌入大脑视图，这将使原始和映射空间中的离群点最终产生更健壮的聚类结果。

图3 基于群体的多视角网络融合框架的图示。给定N个受试者的群体，每个人都有多个大脑连接视角。首先通过原始空间中的图扩散，对每个主题的多视角脑网络视角进行非线性融合。其次，将映射空间中的融合视角聚类为Nc簇，并通过线性融合生成一个特定簇的网络地图集。最后通过对特定于Nc聚类的模板进行平均，来估计最终的大脑网络图谱。

图3 基于群体的多视角网络融合框架

4 基于谱的多视角聚类

对于现有的多视角谱聚类方法，采用一致的相似矩阵进行聚类，对不同视角的信息进行集成。MvC谱聚类是一种典型的数据聚类方法，其基本思想是在任意一对对象之间建立一个成对的亲和矩阵，将亲和矩阵归一化，并计算出图拉普拉斯矩阵的特征向量。多视角谱聚类使图的归一化割最小化，即谱与图的关系。文献［45］在两个独立视角上开发了一种谱聚类算法，每个聚类算法都可以被输入到一个聚类模型中。这种基于谱的MvC 算法创建了一个具有最小不一致准则［46］的二分图以连接两个视角的特征，然后在这个二分图上采用适当的谱聚类算法。文献［47］研究了多视角谱聚类，将一个标准化的切割从单视角推广到多视角，考虑了如何学习一个接近于所有图的最优解的聚类，并进一步开发了一个基于多视角的谱聚类算法。文献［48］也试图找到一个平衡切口，能更好地区分所有相似的图形。此外，文献［49］提出了一种可以提供多个无冗余聚类解的方法学习多视角的非冗余子空间，并为每个视角同时生成聚类解决方案。为了解决数据的分类问题，文献［50］研究了马尔可夫链建立具有低阶稀疏分解的特点多视角谱聚类模型，它首先从每一个视角中绘制一个过渡概率矩阵，然后使用这些矩阵来形成一个共享的秩过渡转移矩阵。最后，将这个共享矩阵输入到标准的马尔可夫链模型中进行聚类，处理了大规模的数据并提高计算效率。Y.Q.Li 等［51］利用局部流形融合融合异构特征和二部图，从而逼近相似图。最近，文献［52］在二部图谱聚类中使用锚点的启发下，也提出了一种基于学习二分图的融合多视角聚类方法。该模型在迭代过程中不仅更新具有代表性的点，还能扩展到大规模数据集。此外文献［53］还提出了一种基于谱分割和局部细化的多视角归一化切割算法，这是一种无参数的多视角谱聚类算法。蔡宏民等［54］则考虑到各个视角数据的局部特征，对公共子空间的秩进行了约束，得到确切数量的聚类簇，提高聚类的准确性。文献［55］研究了凸稀疏谱聚类对单视角数据的稀疏化。然而，随着视角的增加，很难避免视角之间的依赖关系，而这些依赖关系往往误导预测。为了解决这些问题，文献［56］扩展了传统谱聚类处理视角之间的依赖关系，以迫使每个视角的信息在它们之间共享。文献［57］对于视角不平衡提出了一种基于成对约束的多特征融合AP聚类算法。克服了现有特征融合方法中效果差距很大的特征平起平坐的缺点。

一些MvC 方法也被结合谱聚类和其他技术进行了研究。例如文献［58］同时考虑数据空间和标签空间中的多样性和一致性，为了学习一个更优的聚类标签，使用低维谱嵌入代替原始数据。由于谱嵌入方法采用了多样性和一致性学习策略，能够挖掘多视角下的互补信息。文献［59］将谱嵌入过程和相似度矩阵过程联系起来，根据公共表示矩阵和相应的视角特定表示矩阵的乘积恢复每个相似矩阵的缺失项，然后根据完全相似矩阵学习这些表示矩阵。该算法对通用表示矩阵、视角特定表示矩阵、相似矩阵和视角权重进行交替更新。类似的文献［60］提出了基于有效凸层聚类的综合谱聚类方法，提供了多视角到融合特征向量的映射，并通过训练过程中的反馈，在一定程度上纠正了单视角中的误导性信息，从而获得了更精确的数据结构。同时该模型还可以对大型多视角数据集进行聚类。

此外，文献［61］依据谱聚类原理，在聚类任务中不仅实现图的嵌入保留了原始数据的流行结构，同时还解决了样本外数据的聚类问题且自动地为每个视角特征分配合适的权重。文献［62］通过对潜在的低维数据聚类表示进行分解，提出了结构化的低秩表示，一种迭代的多视角协议策略，在优化的每一次迭代过程中，将所有分解的潜在数据聚类表示的目标最小化，同时为了能够保持每个视角的灵活的局部流形结构，并对每个视角的数据聚类结构进行了描述。文献［63］利用图学习和谱聚类技术来学习不完全多视角聚类的通用表示，采用低秩表示自适应地构造每个视角的图，利用谱约束实现了基于光谱聚类的每个视角的低维表示。同时引入了一个共同正则化项来学习所有视角的共同表示。此外，文献［64］引入了一个低秩张量约束来探索多视角的互补信息，该方法以不同视角的子空间表示矩阵为张量，巧妙地捕捉多视角数据的高阶关联。在此基础上，引入了一个低秩约束，对不同视角间的交叉信息进行了精确的建模，有效地降低了学习子空间表示的冗余性，提高了聚类的准确性。文献［65］引入了一种基于鲁棒局部子空间学习的多视角谱聚类方法，该方法考虑到所有视角都是噪声的，并且是从一个鲁棒的统一子空间和噪声中得到的。文献［66］生成一个由所有视角共享的归一化图Laplacian，该图通过奇异值的部分和极小化实现低秩约束，提出了一种鲁棒的多视角谱聚类方法。首先计算每个视角的归一化图Laplacian，然后利用它们通过低秩稀疏矩阵分解恢复共享的低秩拉普拉斯图。文献［67］研究了基于张量低阶建模的多视角谱聚类（MvSC）问题，不像现有的方法都采用现成的张量低阶范数而不考虑MvSC中张量的特殊特性，他们设计了一种适合MvSC 的结构张量低阶范数，在张量的正面和水平切片上显式地施加了一个对称的低秩约束和一个结构稀疏的低秩约束，以分别描述视角内和视角间的关系。同时联合优化这两个约束，以实现相互细化。此外，该方法的参数可以很容易地调优，并且该模型对不同的数据集具有较强的鲁棒性，在实际应用中显示出其优势和潜力。

此外，基于谱的MvC 方法在信号检测［70］、数据安全［71］、故障诊断［72］等方面也有应用。

示例3：对于多视角谱聚类，现有的大多数聚类方法（文献［50］、文献［66］）假设多视角相似性矩阵之间存在一致的相似矩阵，表示所有视角的一致聚类信息，并对其进行单视角谱聚类，得到最终的聚类结果。然而，这种假设是不恰当的，因为数据在不同的视角中可能有很大的差异，使得同一对数据点在不同视角中的相似性在数值上并不一致，持续地追求一个恒定的相似矩阵可能会导致多视角数据中互补聚类信息的丢失。为了克服上述挑战，在文献［68］的基础上文献［69］又提出了一种新的多视角谱聚类方法本质多视角图聚类学习（Essential Multi-view Graph Learning，EMGL），它同时考虑了来自不同数据视角的一致性和互补性聚类信息。EMGL 的整体框架（如图4 所示）。EMGL 首先在构造的个体视角相似性矩阵的基础上，分别从每个相似矩阵中恢复一系列的低秩表示，通过引入正交矩阵因式分解，将低秩表示重构为共享矩阵和一系列视角特定矩阵的乘法。在正交约束作用下，共享矩阵包含一致聚类信息，而互补聚类信息在视角特定矩阵中保持良好。优化后EMGL 通过共享矩阵和视角矩阵形成一个新的相似性矩阵，然后将标准谱聚类方法强加于相应的相似性图上，得到最终的聚类。EMGL目标函数为式（5）：

图4 EMGL的框架

5 结语

虽然MvC 是在2003 年左右提出的，但是没有标准来决定哪个MvC算法是最好的，因为不同的方法有它们自己的优缺点。

1）基于图的不需要指定聚类数量参数与其他描述聚类个数的参数，这使得先验经验成为应用的非必需条件，适用范围增加，且具有明确的聚类中心点，允许数据呈非对称，数据适用范围非常大，但是对初始值不敏感，多次执行聚类算法，得到的结果是完全一样的，算法复杂度较高，聚类算法往往需要算很久，这会使得尤其在海量数据下运行时耗费的时间很多。

2）基于网络的运行速度很快，其运行速度与数据对象的个数无关，只依赖于数据空间中每个维上单元的个数，但是对参数敏感、无法处理不规则分布的数据、容易造成维数灾难。

3）基于谱的易于理解和实现对于大型数据集也是简单高效、时间复杂度、空间复杂度低，具有能在任意形状的样本空间上聚类且收敛于全局最优解，但是当数据集大时结果容易局部最优，对噪声和离群值非常敏感且谱聚类对相似度图的改变和聚类参数的选择非常的敏感。

本文主要从多视角数据的对应关系对其进行了分类，无论是基于图的，基于网络的，还是基于谱的方法，与现有的聚类方法相比，基于图的多视角聚类在众多算法中具有明显优势且在聚类性能上也具有明显的优势，同时大大减少了计算量。类似于大多数多视点聚类方法，我们发现基于图的多视角聚类算法的主要局限性可能是敏感的一些参数初始化，这是MvC 研究的一个新趋势和机遇，有待于我们今后的研究。