面向视角非对齐数据的多视角聚类方法

李骜，冯聪，牛宇童，徐士彪，张英涛，孙广路

（1.哈尔滨理工大学计算机科学与技术学院，黑龙江 哈尔滨 150080；2.北京邮电大学人工智能学院，北京 100876；3.哈尔滨工业大学计算机科学与技术学院，黑龙江 哈尔滨 150001）

0 引言

近年来，多视角学习在机器学习领域引起了广泛的研究兴趣[1-2]。一方面，在众多研究领域中，数据自然地呈现出多种表达方式[3-4]。另一方面，数据的各种表达方式之间存在着隐式的一致性和互补性[5-6]。因此，融合数据的多视角特征，能更全面地揭示数据的分布规律，提高多种下游任务的性能。

多视角聚类是多视角学习的典型应用，它旨在融合多个视角的线索，更好地挖掘数据中的本质类簇结构[7-8]。考虑基于多视角数据的相似性进行融合，Nie 等[9]提出参数无关的自加权多视角聚类方法，该方法重新表述标准的谱聚类算法，为每一视角分配最优权重。文献[10]寻求一个低秩相似性矩阵作为各视角图结构的质心，从质心中直接获取统一的类簇指示矩阵。Liang 等[11]在统一的框架中建模多视角数据的一致性和不一致性，进一步提高聚类性能。为了克服静态相似性矩阵的缺陷，Wang等[12]提出基于动态相似性融合的多视角聚类方法，实现视角专属相似性矩阵和公共相似性矩阵的相互促进。降维技术是应对多视角数据冗余性的有效方法。Liu 等[13]提出基于联合非负矩阵分解的多视角聚类方法，对各视角系数矩阵施加一致性约束，使其融合为一致的类簇指示矩阵。张祎等[14]在矩阵分解的基础上加入流形约束，有效保持了样本空间的流形结构。张量低秩约束是一种利用多视角数据高阶相关性的有效方法。Zhang 等[15]提出基于低秩张量约束的多视角子空间聚类方法，将各视角的自表达矩阵堆叠成张量，再以张量低秩约束降低其冗余性。Wu 等[16]提出基于关键张量学习的谱聚类方法，将各视角基于马尔可夫链的概率转移矩阵堆叠成张量并施加张量低秩约束，捕获了多视角数据的高阶相关性。

尽管上述多视角聚类方法取得了良好的性能，但在真实场景下的应用仍有一定局限性。由于信道时延、传输异步、网络拥塞等多种客观因素，获取的多视角数据会发生视角的非对齐现象，影响现有多视角聚类方法的性能。这类问题是多视角学习中的一类初探新兴问题，以三视角数据为例进行说明。如图1(a)所示，给定一个对齐的多视角数据集其所有视角的特征矩阵Xv的第i列表示同一样本i在不同视角v下的特征，即同一样本在各视角的特征矩阵中是沿列对齐的。然而，由于信道时延、传输异步等影响因素，如图1(b)所示，数据的原有视角对齐关系可能会发生错位，即各视角特征矩阵Xv的同一列可能不再来自相同样本。由于现有多视角聚类方法大多要求不同视角之间存在严格的对齐关系以实现特征融合[2]，视角非对齐现象将误导现有方法将不同类别样本的特征加以融合，降低了学习表示的鉴别力，从而限制了现有多视角聚类方法的应用。

图1 一般多视角数据与视角非对齐多视角数据对比

面向这一新兴问题的研究并不多见，根据本文的调研，目前仅包括文献[17-18]这2 个工作。文献[17]提出部分视角对齐聚类（PVC,partially view-aligned clustering）方法，设计了一个可微的对齐模块，并将其集成于深度神经网络以重建视角对齐关系。文献[18]提出一种鉴于噪声稳健损失的多视角对比学习（MvCLN,multi-view contrastive learning with noise-robust loss）模型，使对齐样本在表示空间中相互靠近，而非对齐样本则互相远离。然而，上述工作只适用于两视角数据。

文献[17-18]工作揭示了一种处理视角非对齐数据的可行思路：先基于特征的相似度信息学习视角对齐关系，再重建视角之间的对应关系以缓解视角非对齐现象对多视角学习的影响。在此基础上，本文提出了一种新的、适用于多视角的视角非对齐数据聚类方法。首先，本文方法基于多视角非负矩阵分解进行表示学习，将异构的多视角特征嵌入可度量的低维同构空间。其次，在低维同构空间中，基于二部图最优匹配学习视角对齐关系，并提出参考视角的概念将对齐模型推广至具有2 个以上视角的非对齐数据。最后，将上述表示学习和数据对齐模块放入统一的Bi-level 优化框架，通过交替求解上层问题（表示学习）和下层问题（数据对齐），使二者在迭代中相互促进，以提升模型的总体性能。本文的贡献如下。

1) 提出一种新颖的面向视角非对齐数据的多视角聚类方法，将表示学习和数据对齐置于同一目标函数中交替优化，学习到具有2 个以上视角的复杂非对齐数据的紧凑表示。

2) 提出了一种基于Bi-level 优化的目标函数，将表示学习和数据对齐抽象为上下层问题。设计了一种基于交替优化的数值求解算法，该算法具有较好的参数稳定性和高效的收敛性能。

3) 将本文方法应用于视角非对齐数据的多视角聚类任务，在3 个公开数据集、3 种视角不对齐率和3 种评价指标上，本文方法均优于8 种先进的多视角聚类方法。本文方法的总体结构如图2 所示。

图2 本文视角非对齐数据表示学习方法的总体结构

1 相关工作

1.1 多视角非负矩阵分解

多视角非负矩阵分解（MultiNMF,multiview non-negative matrix factorization）[13-14]是一种有效的多视角表示学习方法，能够在降低原始特征维度的同时融合各视角的特征，学习到紧凑的多视角公共表示。假设具有Nv个视角的多视角数据集对各视角的特征矩阵Xv进行非负矩阵分解，使Xv≈Uv(Vv)T，得到基矩阵Uv和系数矩阵Vv，则Vv可作为该视角的低维表示，再对Vv施加一致性约束，可得到公共表示矩阵V*。该方法的目标函数为

1.2 Kuhn-Munkres 算法

二部图是一种有着广泛应用的图论模型。对于二部图G和它的2 个大小相等的顶点集V1,V2，G上的最优匹配是指一个V1,V2的顶点之间的一一对应，使所有相互匹配的顶点对之间的边权总和最小。假设W是图G的边权矩阵，Wi,j表示顶点i与顶点j之间的边权；定义指示变量Pi,j，当顶点i与顶点j互相匹配时，Pi,j=1，否则Pi,j=0，二部图最优匹配问题的目标函数为

式(2)又称为线性指派问题，是一类特殊的整数线性规划问题，分别由Kuhn和Munkres 在20 世纪50 年代独立解决，一般把该算法称为Kuhn-Munkres算法。该算法能在多项式时间内精确求解二部图的最优匹配问题[19]。

2 本文方法描述及其数值算法

2.1 数据降维的必要性分析

多视角数据通常具有较高的特征维度，含有较多冗余信息，判别性较低。以人脸数据集ORL的视角1为例，该数据集的判别性信息随奇异值的分布规律如图3 所示。如图3(a)所示，尽管特征总数多达400 个，但其前50个特征值已包含了该数据集中超过60%的主要判别信息。如图3(b)和图3(c)所示，与原始特征矩阵相比，后30%小奇异值重建数据矩阵的取值较为均匀，说明其中的判别性信息较少。因此，对原始高维冗余数据进行降维，保留其主要判别分量，可以有效减少数据的冗余信息，提高特征的判别性。

图3 ORL 数据集视角1 判别性信息分析

2.2 面向视角非对齐数据的多视角聚类方法

面向视角非对齐数据聚类，现有方法的思路可以概括为：从多视角数据中学习潜在的视角对齐关系，以指导模型从视角非对齐数据中学习有效的表示。在此基础上，本文提出将学习到的表示转化为一种跨视角相似度信息并反馈到视角对齐模型中，通过二者的相互促进，以学习到的对齐关系指导表示学习模型尽可能地融合来自同类样本的视角信息，以消除视角不对齐因素的影响，改善表示特征的判别性，进而提高聚类性能。

本文的思路来自两方面的观察。一方面，对于数据对齐来说，保持跨视角一致性的表示学习是必要的。在缺少监督信号的情况下，表示特征之间的相似度信息是对齐关系学习的重要依据。但由于多视角特征的异构性，需要先将原始多视角特征嵌入一个低维同构的表示空间，才能有效地度量跨视角相似度。另一方面，对于视角非对齐数据的表示学习来说，对齐关系学习也是不可或缺的。由于视角非对齐现象的影响，模型无法直接对多视角数据进行特征融合，不能很好地利用多视角潜在一致性。因此，需要为每个特征找到与之对齐的其他视角特征，使它们对应相同的类簇，才能确保特征融合的有效性。受此启发，本文提出在2 个模块之间建立双向数据通道，以提高联合学习性能。

为了实现这一目的，本文将上述2 个模块嵌入基于文献[20]的Bi-level 优化框架中进行交替优化，使它们在迭代中相互促进，以提升模型的总体性能。本文面向视角非对齐数据的统一表示学习和数据对齐模型为

2.3 上层问题：表示学习

如上文所述，非负矩阵分解是一种有效的降维技术，能滤除数据中的冗余信息，提高特征的判别性。此外，该技术学到的特征具有较好的跨视角一致性，在跨模态检索领域有着广泛应用[21-22]。受此启发，本文基于该技术设计表示学习模块，以促进视角对齐关系学习并获得多视角公共表示。

在多视角非负矩阵分解中，基矩阵Uv捕获了原始特征空间中的潜在概念，而Vv则是这些潜在概念的叠加系数，从而把原始特征Xv嵌入一个以潜在概念为基底构成的坐标空间。由于不同视角所描述的样本是一致的，各视角的叠加系数Vv具有很高的相关性，对Vv施加一致性约束后，可视为原始特征的一种同构表示，具有跨视角一致性，即属于相同类簇的样本的不同视角的特征，在表示空间中也具有较高的相似性。

然而，传统的多视角非负矩阵分解只适用于视角对齐数据。对于视角非对齐数据，引入基于参考视角的对齐矩阵Pv,1 ≤v≤Nv,v≠u。将Pv右乘于原始特征矩阵Xv，可调整Xv的视角对齐关系，再对对齐后的特征矩阵Xv Pv,1 ≤v≤Nv进行多视角非负矩阵分解，得出表示学习的目标函数为

其中，λv是权衡参数，Pv是由数据对齐模块学习到的视角对齐矩阵。

2.4 下层问题：数据对齐

数据对齐模块的功能是从视角非对齐数据中学习潜在的视角对齐关系，为表示学习模块提供对齐矩阵Pv。本文提出一种基于参考视角的对齐方法，即选定一个参考视角，以之为基准逐个对齐其他视角，使所有视角都与参考视角保持对齐。该方法将一个Nv视角的对齐问题转化为Nv− 1个两视角对齐的子问题。因此，可以先针对两视角对齐问题设计模型，再由参考视角扩展到多视角的情况。

由于不同视角特征的跨视角相似度越大，它们属于相同类簇的可能性也就越大，应该令所有相互匹配的特征对之间的跨视角相似度总和最大。然而，由于原始特征的异构性之间的相似度无法度量，只能用相应的低维同构表示之间的距离来近似估计，由此得到两视角对齐模型的目标函数为

其中，C表示一种可能的特征匹配方案。注意到式(5)等价于一个二部图最优匹配模型。将Xv,Xu分别作为二部图的 2 个顶点集合V1,V2，将距离作为2 个顶点之间的边权Wi,j，将指示变量表示特征对是否匹配，可得到如式(2)所示的二部图最优匹配模型。

基于参考视角，可将式(5)推广至多视角情况。设u为参考视角，v为任意视角，距离矩阵Dv为视角v,u特征之间的成对距离则求解视角v关于参考视角u的对齐矩阵Pv的目标函数为

2.5 目标函数求解

目标函数式(3)是Bi-level 优化问题，上层问题是非凸的，下层问题是整数规划问题，难以同时求解。本文采用交替优化策略，通过交替求解上下层问题来获得近似解。

2.5.1 上层问题求解

上层问题的目标函数如式(4)所示，该问题可通过交替优化变量Vv,Uv,V*求解。为了消除对基向量的L1范数约束，引入辅助变量Qv

其中，Qv∈RK×K为对角矩阵，Mv为视角v的特征维数，K为低维表示的维数。借助辅助变量Qv，把式(4)等价变形为

从式(9)可将目标函数拆成如下的子问题。

U-子问题。将式(9)用矩阵的迹展开并引入拉格朗日乘子Φ，得到无约束拉格朗日函数

对L1求导并令其导数等于 0，结合 KKT（Karush-Kuhn-Tucker）条件得

从式(12)中解得U的更新规则为

V-子问题。由于式(9)中Q的作用是对U进行L1范数归一化，而U在V-子问题中是常量，因此可通过对U,V进行显式归一化来消除辅助变量Q

由于式(14)的归一化不改变式(9)中的目标函数值，因此在显式归一化U,V后，V-子问题可化简为

将式(15)用矩阵的迹展开并引入拉格朗日乘子Ψ，得到无约束拉格朗日函数

从式(17)解得V的更新规则为

V*-子问题。对于式(9)，只考虑与V*有关的部分，可得到目标函数为

式(19)是一个最小二乘问题，求导并令导数等于0，可解得V*的闭式解为

2.5.2 下层问题求解

式(6)是一类特殊的整数线性规划问题，可采用文献[19]中多项式时间的精确算法对其进行求解。本文的数值求解算法如算法1 所示。

算法1目标函数式(3)的数值求解算法

3 实验结果及分析

3.1 数据集描述

本节在3 个公开数据集上进行多视角聚类实验，数据集的具体情况阐述如下。

MSRC-v1 数据集。该数据集是一个物体图像数据集，选择其中7 个类别的样本，共210 张图像。提取5 种不同的特征作为5 个视角，分别为色矩（CM,color moment）特征、局部二进制模式（LBP,local binary pattern）特征、CENTRIST 特征、GIST特征以及SIFT 特征。

ORL 数据集。该数据集是一个人脸图像数据集，由400 张人脸图像组成。提取4 种不同的特征作为4 个视角，分别为强度特征（Intensity）、LBP特征、Gabor 特征以及灰度值特征（Gray）。

Digits 数据集。该数据集包含10 种手写数字的图像，样本总数为2 000。提取3 种不同的特征作为3 个视角，分别为剖面相关特征、傅里叶系数特征以及形态学特征。

3.2 对比实验设置及实验结果分析

由于文献[17]中的部分视角对齐聚类方法PVC和文献[18]中的多视角稳健对比学习方法MvCLN 仅能处理具有2 个视角的数据聚类问题，因此本文分别在两视角和2 个以上视角这2 种情况下进行对比实验。由于视角非对齐现象可以看作一类针对多视角数据的复杂噪声干扰，为了尽可能地公平，在包含2个以上视角的聚类实验中，本文选取了若干对一般性噪声稳健的先进传统多视角聚类方法进行比较，使对比实验能够在一定程度上客观地说明本文方法的优势。2 个以上视角情况下的对比方法包括：文献[12]中的基于图的多视角聚类（GMC,graph-based multi-view clustering）方法、文献[11]中的非一致图融合（DGF,distance graph fusion）方法、文献[10]中的自加权多视角聚类（SwMC,self-weighted multiview clustering）方法、文献[16]中的基于关键张量学习的多视角谱聚类（ETLMSC,essential tensor learning for multi-view spectral clustering）方法、文献[9]中的无参多图学习（AMGL,auto-weighted multiple graph learning）方法和文献[13]中的多视角非负矩阵分解（MultiNMF,multi-view NMF）方法。

对于上述6 种对比方法，首先在常用的三视角设定下进行实验，分别采用MSRC-v1和ORL的前3 个视角及Digits的全部视角，实验结果如图4(a)～图4(c)所示。其次，与PVC[17]和MvCLN[18]在上述数据集的两视角子集上进行对比实验，分别采用MSRC-v1的CM和CENTRIST 视角，ORL的LBP和Gabor 视角以及Digits的傅里叶系数和剖面特征视角，实验结果如图4(d)所示。最后，为了证明本文方法对一般多视角数据集的有效性，分别在MSRC-v1和ORL的全部视角上与上述6 种传统多视角聚类方法进行对比实验，实验结果如图4(d)所示。实验中设置了3 种视角不对齐率（0.3、0.5和0.7），采用准确率（ACC,accuracy）、归一化互信息（NMI,normalized mutual information）和纯度（PUR,purity）作为评价指标，所有实验均重复5 次，取其均值作为最终结果。对本文方法的参数设定如下：参考文献[13,14]中的做法，将表示学习中各视角的权衡参数λv设置为相同值λ；将参考视角u设置为视角1；取高斯核函数作为距离函数，即其中σ为高斯核的尺度参数，实验中取λ= 0.01，σ=1。

图4 本文方法在三视角和两视角设定下的对比实验结果

如图4(a)～图4(c)所示，在绝大多数情况下，本文方法的各项性能指标都超过了其他对比方法。以不同不对齐率下的指标均值来考量对比方法的平均性能，本文方法在MSRC-v1、ORL、Digits 这3 个数据集上，ACC 指标依次超过次优方法7%、7%和13%；NMI 指标依次超过次优方法8%、8%和14%；PUR 指标依次超过次优方法7%、8%和13%。当不对齐率逐渐增大时，其他对比方法的性能下降趋势明显，而本文方法的性能变化趋势相对平缓。在MSRC-v1 数据集上，当不对齐率逐渐增大时，本文方法的各项指标几乎保持不变。在Digits 数据集上，本文方法的性能下降趋势更平缓，例如当不对齐率从0.5 上升至0.7 时，对比方法的NMI 指标平均下降了16.4%，而本文方法的NMI 指标只下降了5.1%。

本文方法与PVC、MvCLN 方法的比较结果如图4(d)所示。可以看到，本文方法在MSRC-v1和ORL 数据集的评价指标上的性能均优于PVC和MvCLN。在Digits 数据集上，ACC 指标取得了几乎最优的性能，NMI和PUR 这2 个指标在部分实验条件下取得了次优的性能，说明本文方法有效改进了该领域的前人工作。本文方法在四、五视角设定下的实验结果如图5 所示。可以看到，各项性能指标在四视角ORL 数据集和五视角MSRC-v1 数据集上的变化趋势与在相应的三视角子集上基本一致，说明本文方法对一般的多视角数据集同样有效。

图5 本文方法在四、五视角设定下的对比实验结果

综上所述，本文方法在多个数据集、多种视角数量和多种不对齐率下的实验中都取得了最优性能。上述实验结果证明了本文方法对视角非对齐数据表示学习及其聚类应用的有效性和稳健性。

3.3 数据对齐模块的有效性验证

为了验证数据对齐模块的有效性，选取类簇对齐率作为视角对齐程度的评价指标，并绘制不同视角的类簇对齐率随迭代次数变化的曲线，这里展示在不对齐率为0.3 时MSRC-v1 数据集上的实验结果。如图6 所示，在初始状态下，视角2和视角3的类簇对齐率处于较低水平（仅略高于数据本身的样本对齐率0.7）。随着迭代数的增加，对齐率显著提高，最后稳定在高于初始状态4.5%～12%的水平。

注意到，图6的曲线变化趋势与图7(b)的收敛曲线的变化趋势基本一致：经过约3 轮迭代后，数值算法开始收敛，数据集对齐程度趋于饱和。这里提出一种提高该饱和程度的可能策略：在迭代过程中动态地调整一致性约束项的权衡系数λ。理由如下：在算法迭代初期，数据不对齐程度较高，不应强制Vv趋于一致，应设置较小的λ值；而在迭代后期，数据对齐程度有所提高，可加快Vv融合以提高其跨视角一致性，应适当增大λ值。

图6 视角2和视角3 在MSRC-v1 数据集上的类簇对齐率变化曲线

3.4 参数稳定性与收敛性分析

本文方法共包括2 个参数：表示学习中的权衡参数λ和数据对齐中的高斯核尺度参数σ。本文按照{0.001,0.01,0.1,1,10,100,1000}的变化范围进行网格搜索，分析聚类性能对不同参数组合的敏感程度。图7(a)是在不对齐率为0.7的MSRC-v1 数据集上，ACC 指标关于参数λ和σ的变化分布。可以看出，在较大的参数范围内，性能指标的变化幅度相对较小，说明本文方法具有较好的参数稳定性，从而具有较好的易用性。

为了证明本文数值算法的收敛性，以迭代次数和目标函数值分别为横、纵坐标绘制收敛曲线。在不对齐率为0.7的MSRC-v1数据集上的实验结果如图7(b)所示。从图7 中可以看出，本文数值算法具有较好的收敛性能。

图7 参数稳定性与收敛性分析

4 结束语

面向视角非对齐数据的多视角学习问题，本文提出了一种基于多视角非负矩阵分解的学习方法。在3 个公开数据集、多种不同的视角数量和3 种不对齐率上，本文方法的聚类性能均优于8 种先进的多视角聚类方法。在此基础上，后续研究可考虑引入核技巧扩展本文的表示学习模型，增强其非线性适应能力。此外，在视角非对齐设定下，表示学习的稳定性及相关参数的影响分析也是值得探索的后续研究方向。