基于多阶近邻约束的深度不完整多视图聚类方法

王 梅 ,王伟东 ,刘 勇 ,于源泽

（1.东北石油大学计算机与信息技术学院，大庆，163318；2.中国人民大学高瓴人工智能学院，北京，100049）

近年来有许多多视图聚类方法被提出［1-9］，其中大部分工作都显示或隐式地采用数据完整性假设，即所有实例的所有视图都是可见的.然而，在实际应用中，由于数据收集和传输的复杂性，数据完整性假设很难成立，从而导致不完整多视图聚类问题.与完整的多视图数据相比，缺失视图不仅削弱了原始多视图丰富的语义信息，而且由于缺失导致的分布不确定性，使得提取数据信息更加困难.Li et al［10］首次利用非负矩阵分解技术挖掘公共潜在子空间，提出了部分对齐的多视图聚类算法（Partial Multi-View Clustering，PVC）.Hu and Chen［11］提出一种基于半非负矩阵分解的双重对齐不完整多视图聚类算法（Doubly Aligned Incomplete Multi -View Clustering Algorithm，DAIMC）.Zhao et al［12］通过一个新的图拉普拉斯项来处理不完全多模态视觉数据分组问题，并提出不完整的多模态视觉数据聚类算法（Incomplete Multi-modal Visual Data Grouping，IMG）.Wang et al［13］将数据缺失问题转化为矩阵相似性问题，提出一种面向扰动的不完整多视图聚类方法（Perturbation-Oriented Incomplete Multi-View Clustering，PIC）.Liu et al［14］将不完整多视图聚类重新定义为联合优化问题，提出一种具有不完整多核K-means 方法（Multiple Kernel K-means with Incomplete Kernels，MKKM-IK）.次 年，Liu et al［15］发现过于复杂的优化限制了MKKM-IK 聚类性能的提升.为此，他们提出一种高效且有效的不完整多视图聚类算法（Efficient and Effective Incomplete Multi-View Clustering，EE-R-IMVC）.Wen et al［16］设计了由不完全图构造的拉普拉斯矩阵来约束缺失视图，提出了一种基于一致张量框架下的缺失视图推断的不完整多视图聚类算法（Unifified Embedding Alignment Framework，UEAF）.刘晓琳等［17］通过交叉扩散的方式将不同阶的深层结构信息进行融合，提出一种基于多阶近邻扩散融合的不完整多视图聚类算法（Incomplete Multi-View Clustering Algorithm Based on Multi-Order Neighborhood Dffusion and Fusion，MNDF）.

尽管上述方法在不完整多视图聚类任务上具有良好的表现，但大多数方法是利用浅层模型完成不完整多视图聚类任务，在处理高维和大规模数据时性能有限.对此现有部分不完整多视图聚类方法［18-27］利用深度网络卓越的非线性拟合能力挖掘数据深层次信息.Zhang et al［18］同时考虑了多视图的互补性和类分布，设计并构建了一个部分交叉多视图网络（Cross Partial Multi-View Networks，CPM-Nets）处理不完整多视图问题.Wang et al［19］构建了一个带有生成器的多视图聚类模型，通过显式生成缺失视图数据解决不完全多视图问题.Zhang et al［20］引入了一种单阶段后期融合方法，该方法结合了缺失视图的插补和聚类.Tang and Liu［21］为了减少缺失视图导致的聚类性能退化，提出了深度安全不完整多视图聚类方法（Deep Safe Incomplete Multi-View Clustering，DSIMVC）.Zhang et al［22］引入了可学习的潜在表示，以从多个视图中挖掘公共语义.受到信息论的启发，Lin et al［23］将一致性学习与缺失数据恢复统一到一个框架中，提出了基于对比预测的不完整多视图聚类方法（Incomplete Multi-View Clustering via Contrastive Prediction，COMPLETER）.次 年，Lin et al［24］在COMPLETER 的基础上加以改进，提出了双重对比预测模型（Dual Contrastive Prediction for Incomplete Multi-View Representation Learning，DCP），解决了两个以上视图的缺失问题.Yang et al［25］建立了一个统一的框架，同时解决视图对齐和样本缺失问题.

然而现有的基于深度学习的不完整多视图聚类方法只考虑了视图的属性信息，而忽视了结构信息对聚类的影响，导致提取的特征不能充分表示原始数据的潜在结构.近年来，已经有研究人员发现数据的内在结构对于无监督学习至关重要.经典的最近邻图约束被广泛应用于各种机器学习方法［28-29］中，使得提取的语义表示能够保持数据的原始拓扑结构.也有一些多视图学习方法［30-33］通过构造先验邻接矩阵来帮助保持数据的原始内在结构.这是基于一个基本的假设：如果两个样本在原始特征空间中彼此接近，那么它们在嵌入空间中也很接近.但是在数据不完整的情况下，很难从数据中直接获得完整的图.为此，也有一些方法利用视图间的互补性构建近似完整的近邻图，指导编码器提取高级语义特征.然而，这些方法都是直接计算数据集中两个样本间的相似性，学习到的图鲁棒性差，且易受噪声影响导致所获得的图难以准确刻画数据的结构信息，从而降低聚类性能.

考虑到上述问题，本文提出了一种基于多阶近邻约束的深度不完整多视图聚类方法（Deep Incomplete Multi-View Clustering Based on Multi-Order Neighborhood Constraint，DMNC）.首 先，结合自注意力机制和多视图学习的特点，设计了一个基于Transformer 的编码器.与简单的线性编码器相比，它能够进行交叉视图间的信息交互，有利于挖掘多个视图间的互补性.其次，引入了加权融合策略来组合多视图互补信息，同时避免了缺失视图带来的影响.最后，考虑到数据的不同阶结构信息，利用不完整多视图的互补性，提出一种多阶近邻约束，其目的是构建一个融合多阶近邻关系的近似完整的近邻图指导编码器提取更紧致、更有判别性的高级语义特征.另一方面，更明显的区别性语义特征也可以促进缺失视图的恢复.大量的实验和直观的可视化结果也验证了本文所提方法的有效性.

1 相关理论

1.1 高阶近邻关系一阶近邻关系指的是直接计算两个样本间的相似性或在向量空间的距离，比如计算两个特征向量之间的欧式距离表示这两个向量之间的相似性，欧式距离越小，样本之间越相似.大多数基于图嵌入的方法都是为了保持这种一阶近邻关系而设计的，然而这些方法并没有观察到数据的深层结构信息.换句话说，观察到的一阶近邻关系难以准确刻画数据的潜在结构.高阶近邻关系刻画的是一种更深层次的近邻关系［17，34］.比如，样本之间的二阶近邻关系并不是通过计算样本间距离来确定，而是通过样本的共享邻域结构来确定.二阶近邻关系的一般概念可以解释为共享邻居越多的样本点越有可能相似.在复杂的样本关系中，多阶相似性对数据潜在结构的挖掘更为重要.

举例说明，图1 为包含10 个样本的近邻关系图，连边表示样本间的一阶近邻关系，连边越粗表明一阶近邻关系越紧密.可以看出，样本6 和样本7 具有较高的一阶近邻关系，仅按一阶近邻关系进行数据划分时将会把样本6 和样本7 视为同一类.另外，尽管样本5 和样本6 之间不存在一阶近邻关系，但是它们共享许多共同的邻居，即它们具有很高的二阶近邻关系，因此以二阶近邻关系进行数据划分时，样本5 与样本6 应该同属于一类，这也更加符合数据的真实结构.

图1 近邻关系图Fig.1 Neighborhood relationship

图2 多头自注意力机制Fig.2 Multi-Head Attention

定义M(o)∈Rn×n为样本对之间的第o阶近邻矩阵，其中每个元素的计算如式（1）所示：

1.2 多头自注意力机制注意力机制是一种能够选择性地关注重要信息而忽略其他可见信息的方法.自注意力机制［35］是注意力机制的一种变体，与传统的注意力机制相比，减少了对外部信息的依赖，更加聚焦于捕捉数据或特征内部的相关性.本文采用自注意力机制来计算同一样本不同视图之间的相关性，从而更好地理解数据内部的结构和关联性.缩放点积注意力（Scaled Dotproduct Attention）是一种常用的自注意力计算公式.首先，需要使用线性变阵矩阵{WQ，WK，WV}计算每个特征或视图的Q(query)，K(key)和V(value)，自注意力的计算如下：

其中，dk是K的向量维度，除以是为了稳定梯度，防止反向传播时梯度消失.

为了增强自注意力机制的表示能力，促使模型在相同的注意力机制下学习多样化的行为，并捕获特征或视图内各种范围的依赖关系，提出了多头注意力机制.如下所示：

2 基于多阶近邻约束的深度不完整多视图聚类方法

本文提出一种基于多阶近邻约束的深度不完整多视图聚类方法（Deep Incomplete Multi-View Clustering Based on Multi-Order Neighborhood Constraint，DMNC），用于学习具有不完整多视图样本的表示.DMNC 模型框架如图3 所示，考虑到本文的下游任务是无监督聚类，由于缺乏直接区分数据的监督信息，本文只能利用可用的原始数据来施加重构约束，以学习视图所共享的公共语义表示.因此，设计了一个基于Transformer 的自编码器同时完成多视图公共表示学习与缺失视图恢复.此外，为了使提取的公共语义表示能够包含数据的潜在结构信息，设计了一个多阶近邻约束项，以获取带有多阶结构信息的公共表示.为了保证恢复的缺失视图对下游任务有利，采用两阶段的学习策略.第一阶段：利用多视图的一致性恢复缺失视图，避免缺失位置的噪声数据产生负面影响；第二阶段：将第一阶段恢复的数据和原始不完整数据相结合生成新的数据（近似完整数据），完成多视图聚类.因此，在第二阶段，整个模型可以被视为一个通用的多视图聚类网络，而不需要任何额外的计算.

图3 DMNC 模型框架Fig.3 The framework of DMNC

2.1 符号定义为了便于表达，首先对不完整多视图聚类方法的基本符号作出定义.

给定具有m个视图和n个样本的多视图数据集，将它们划分为c个类，dv表示第v个视图的维度.为了表示缺失数据，引入缺失指示矩阵W∈{0，1}n×m，其中，Wi，j=1 表示第i个样本的第j个视图可见，否则表示第i个样本的第j个视图缺失，表示第v个视图可见样本数.表示模型重构的数据，是填充有重构数据的插补数据.Z∈Rn×m×de是完成交叉视图信息交互后的深层特征，de表示深层特征的维度，其融合表示是本文的目标矩阵.

2.2 交叉视图信息交互模块与单视图数据相比，多视图学习成功的关键是视图之间的互补性，即每个视图存在其他视图没有的特有信息.为了聚合视图间的互补信息，本文设计了一个具有交叉视图信息交互的编码器（Cross-View Information Interaction Transformer Encoder，CFormer）.首先，原始数据各个视图的特征维度不同，为了便于后续模块能够并行处理所有视图，为所有视图添加一组低级的特征提取器，将原始多视图数据映射到具有相同维度的嵌入空间.简单起见，选择m个多层感知机作为低级特征提取器.其中，θ(v)为多层感知机Φ(v)的参数.本文提出的编码器与经典的Transformer 中的编码器类似，主要区别在于本文在计算多头自注意力得分时引入了缺失视图指标矩阵，以防止缺失视图参与注意力的计算.具体实现如下：给定多头自注意力机制的头数h，对于每个样本的嵌入特征∈Rm×de，利用h组线性变换参数矩阵获取相应的query，key和value的映射，其中，dh=de/h.为了根据带有缺失的嵌入特征计算注意力，定义了一个填充函数zerofil（l），表示用-e9填充零值，并构造了样本i的掩码矩阵，其中，wi是缺失视图指示矩阵W的第i行向量.采用式（6）计算带有缺失视图的自注意力：

在第二阶段，对于完整视图数据采用式（7）计算注意力：

对于样本i，拼接所有输出：

总之，在编码器模块中，同一样本的所有视图都将在并行编码过程中交换信息.因此，每个视图的私有信息在某种程度上被其他视图共享.最后，具有交叉视图信息交互的编码器CFormer 可以公式化为

2.3 一致性视图恢复模块大量多视图工作［36-39］都假设所有视图共享同一样本的共同语义，如公共表示或聚类标签.受此启发，本文设计了一个简单的加权融合模块获得所有视图共享的公共表示：

仅通过加权融合获得的公共表示Zˉ还无法保证其包含了各个视图共享的共同语义.为此，本文设计了一个对称的具有缺失视图恢复的解码器（Missing Views Reconstruct Transformer Decoder，RFormer），利用公共表示Zˉ重构包括缺失视图在内的所有数据.同样地，为了使模型的输入输出格式统一，在输入解码器之前，添加一个多层感知机具有缺失视图恢复的解码器 RFormer 可以公式化为D∶

由于缺乏直接区分恢复数据的监督信息，本文只能利用可用的原始数据来施加部分重构约束.因此，引入一个加权重构损失Lre.

2.4 多阶近邻约束模块在数据不完整的情况下，一些现有的方法简单地跳过缺失视图来构造邻接图，这是明显有偏的，特别是在缺失率较大的数据上.因此，本文期望获得一个近似完整的邻接图来指导编码器提取高级语义特征.同时，考虑到多阶相似性信息可以为数据提供不同层次的结构描述信息，融合这些不同阶的相似性关系能够为聚类算法提供更加明确的聚类指导.另一方面，更明显的区别性语义特征也可以促进缺失视图的恢复.结合这两点，本文提出多阶近邻图约束.首先，构建不完整视图的近邻矩阵，以第v个视图为例，定义M(o)(v)∈Rnv×nv为样本对之间的第o阶近邻矩阵，其中每个元素计算如式（11）所示：

由于视图存在样本缺失的情况，所以仅能计算可见样本之间的相似性.基于视图之间的互补性，假设每个视图的数据样本信息是缺失的，但是多个视图的结构信息是互补且完备的［40-41］.为此，对同阶的m个不完整视图进行互补性对齐融合，旨在获得同阶的互补近邻图A(o)∈Rn×n：

为了使不同阶的互补近邻图具有相同的度量尺度，首先，需要对互补近邻图进行归一化，即，其中，D(o)为度矩阵，对角线元素为同时，本文采用加权融合的方式获得包含不同阶结构信息的近邻图G∈Rn×n：

最后，多阶近邻约束损失函数Lrg如式（16）所示：

2.5 损失函数与聚类综上所述，模型在第一阶段的整体损失函数如式（17）所示：

其中，β是平衡这两个损失的超参数.

第二阶段的损失函数如式（18）所示：

本文在第二阶段进行了完整的多视图聚类，将第二阶段获得的融合嵌入特征Zˉ∈Rn×de作为最终的聚类指标矩阵.简单起见，本文在Zˉ上执行K-means，以获得最终的聚类结果.

3 实验分析

3.1 实验数据在四个广泛使用的多视图数据集上全面地评估了提出的方法.数据集的详细信息如表1 所示.MNIST-USPS 是一个流行的手写数字数据集，包含5000 个样本和两种不同风格的数字图像.Columbia Consumer Video（CCV）是一个包含20 个类6773 个样本的视频数据集，每个样本包含三个视图STIP，SIFT 和MFCC.Multi-Fashion 是一个图像数据集，本文将三种不同的风格视为一个样本的三种视图.Caltech7 是Caltech101 数据集的一个子集，是具有多个视图的RGB 图像数据集，本文从中选择了1474 张涵盖七个类别的图像，每幅图像都提取六种特征，即WM，CENTRIST，LBP，GIST，HOG 和Gabor.

表1 实验使用的数据集的详细信息Table 1 Information of datasets used in experiments

3.2 对比方法将本文提出的方法与以下四类方法进行聚类性能的比较实验.

（1）基线方法：BSV 是一种简单的基线方法，用平均向量填充缺失的视图，并对每个视图执行K-means 以获得最佳结果；Concat 是另一种流行的基线方法，它将所有视图与BSV 相同的计算策略对齐，并简单地将它们连接起来进行单视图聚类.

（2）利用对齐信息的方法：PVC［10］是不完整多视图聚类的一项先驱工作，旨在寻找对齐样本和非对齐样本共享的潜在空间.

（3）利用结构信息的方法：UEAF［16］考虑了多视图数据的局部结构，将获取一致性特征向量与缺失视图推理统一到一个框架.

（4）基于数据补全的方法：MKKM-IK［14］是一个基于核矩阵补全的算法，采用集成的思想将多个核矩阵进行融合；EE-R-IMVC［15］将每个不完整基础矩阵与学习的共识聚类矩阵进行归因，以提高聚类性能；DCP［24］是一种基于互信息理论的深度不完整多视图聚类方法.

3.3 实验设置及评价指标所有模型都基于PyTorch［42］实现，在Ubuntu 20.04 系统和NVIDIA 1080Ti GPU 的服务器上完成所有实验.对于所有数据集，模型的CFormer 和RFormer 分别由三个相同的多头自注意力层组成，并且为每个视图设计了一个视图特有的多层感知机，每个多层感知机由三个全连接层构成.近邻数K和权衡系数β分别设置为100 和0.1.

为了评估模型处理不完整的多视图数据的性能，随机删除每个视图p%(p∈{10，30，50})的实例，但对于每个样本至少保留一个视图可用.采用广泛使用的三个指标评价模型最终的聚类性能，包括聚类精度（Accuracy，ACC），归一化互信息（Normalized Mutual Information，NMI）和纯度（Purity），这些指标的值越高表明聚类性能越好.为了减少随机性产生的影响，所有方法在每个数据集上独立重复10 次，取平均值.详细的实验结果见表2～5，表中黑体字表示每种实验设置下的最佳结果.

表2 不同缺失率下各聚类方法在MNIST-USPS 数据集上的聚类结果Table 2 Results on MNIST-USPS with different incomplete rates

表3 不同缺失率下各聚类方法在CCV 数据集上的聚类结果Table 3 Results on CCV with different incomplete rates

表4 不同缺失率下各聚类方法在Multi-Fashion 数据集上的聚类结果Table 4 Results on Multi-Fashion with different incomplete rates

表5 不同缺失率下各聚类方法在Caltech7 数据集上的聚类结果Table 5 Results on Caltech7 with different incomplete rates

3.4 实验结果与分析从这些实验结果中能够得出以下结论.

（1）本文所提方法在大多数指标上都优于其他七种方法，尤其在有二个视图的Multi-Fashion数据集上，该方法的准确率比第二优的方法大约高7%.表明本文提出的方法在多视图聚类任务中取得了显著的改进效果.横向比较所有结果发现，缺失视图对多视图学习的影响非常大.较高的缺失率通常会导致较差的学习结果，这是因为缺失视图削弱了原始多视图中丰富的语义信息.然而，和其他方法相比，本文方法在缺失视图的情况下性能下降较缓，这表明该方法对缺失视图相对不敏感.其主要原因是多阶近邻图通过多次迭代计算多阶近邻关系，可以在多个视图之间进行信息的交互，更好地捕捉到样本之间的潜在依赖和重要关系，更准确地刻画数据的结构，从而更好地消除缺失视图带来的负面影响.

（2）在大多数情况下，基于传统机器学习的不完整多视图聚类方法的效果比基于深度学习的方法聚类的效果差，因为深度学习模型通过多个隐层的连接和非线性变换，能够逐渐构建多层次的抽象表示，可以从原始输入数据中学习到更具有代表性的特征表示.与其他深度多视图聚类方法不同，本文采用Transformer 作为基础模型，能够在特征表示过程中自动学习到不同视图之间的依赖关系和重要性，进而可以更好地捕捉到多视图数据中不同视图之间的相关性和互补性.

（3）和只考虑一阶近邻关系的UEAF 方法相比，本文方法的效果更好，因为本文扩展了引入多阶近邻关系的思想.通过考虑多阶近邻关系，DMNC 能够更全面地捕捉数据中样本之间的联系和结构.同时，多阶近邻关系允许本文在建模过程中考虑更长的依赖关系，从而更准确地刻画数据的结构.最重要的是，多阶近邻关系的引入有助于改善聚类结果的连通性，通过考虑多阶近邻关系，能够更好地将相似的样本彼此连接起来，并且减少不相似样本之间的连接.这可以有效地提高聚类的连贯性和一致性，使得聚类结果更加合理和可解释.

（4）与其他数据集相比，本文的方法在Caltech7 数据集上的提升较少.这是因为Caltech7 数据集中各类样本的数量较少，深度学习方法在这种情况下的效果并不明显.另外，其他方法在该数据集上的提升效果也不显著，这说明该数据集本身较难被聚类.因此，本文方法对于该数据集的优化能力有限.

3.5 参数敏感性分析及消融研究以50%缺失率的不完整多视图数据集MNIST-USPS 为例，评估超参数对聚类性能的影响.DMNC 的超参数包括近邻数K和权衡系数β，为了评估算法对K和β的敏感性，K设置为{20，40，60，80，100}，β设置为{0.01，0.1，1，10，100}.如图4 所示，可以发现DMNC 对K的选择具有鲁棒性.此外，选择一个好的β将显著提高DMNC 的性能.

图4 在MNIST-USPS 数据集上的参数敏感性分析实验Fig.4 Parameter analysis on MNIST-USPS

其次，为了评估不同阶近邻关系对模型性能的影响，设置了不同阶数的对比实验，将近邻约束的阶数设置在零阶至四阶内，如表6 所示.其中，零阶表示不带有近邻约束项，一阶表示传统K 近邻约束.从表可见，三阶互补近邻图获得了最好的聚类性能.

表6 在MNIST-USPS 数据集上采用不同阶近邻关系时DMNC 算法的性能比较Table 6 Performance of DMNC with different orders of neighborhood relationships on MNIST-USPS

3.6 收敛性分析及可视化为了证明DMNC 的收敛性，在MNIST-USPS 数据集上进行实验，缺失率p固定为50%.图5 展示了随着迭代次数的增加，损失值和聚类性能的变化.由图可见，损失值不断下降直到收敛.同时，ACC，NMI和Purity的值也随着迭代次数的增加逐渐增加，最后趋于稳定，这些结果证明了DMNC 的收敛性.

图5 DMNC 在MNIST-USPS 数据集上的收敛曲线Fig.5 Convergence curves of DMNC on MNIST-USPS

此外，随着迭代次数增加，本文使用t-SNE［43］对学习到的特征进行可视化.如图6 所示，随着迭代次数增加，集群结构变得更加紧凑和分离.这些结果验证了近似完整的多阶近邻图可以指导编码器提取更紧致、更有判别性的高级语义特征.

图6 对MNIST-USPS 数据集的聚类可视化Fig.6 Multi-view clustering visualization on MNISTUSPS

4 结论

本文同时考虑到多视图的互补性、一致性及视图内的结构信息提出一种针对不完整多视图问题的深度聚类方法，在利用基于Transformer 的深度自编码器进行交叉视图间信息交互的同时引入加权融合层获取多视图公共表示.同时，利用视图内不同阶的潜在结构信息，构建近似完整的多阶近邻图，指导编码器提取更紧致、更有判别性的高级语义特征.在多个数据集上的实验结果证明了本文方法的有效性.

本文提出的模型只是在一些基准数据集上取得了良好的结果，并没有将其应用到更实际的数据集上.同时，在构建多阶近邻图时只利用了可见的视图，下一步工作是研究新的策略将重构数据融入构建多阶近邻图中并解决两阶段优化问题.