基于正交基的多视图迁移谱聚类

王丽娟，张霖，尹明，郝志峰，蔡瑞初，温雯

（1.广东工业大学 计算机学院，广州 510006；2.广东工业大学 自动化学院，广州 510006；3.汕头大学，广东 汕头 515063）

0 概述

聚类是一种无监督的大规模数据分析算法，在过去的几十年中，许多经典聚类算法被提出。经典的聚类算法包含但不限于标准谱聚类［1］（Spectral Clustering，SC）、稀疏子空间聚类［2］（Sparse Subspace Clustering，SSC）和低秩表示［3］（Low-Rank Representation，LRR）等。尽管这些算法取得了较好的成果，但其仅考虑单视图数据，忽略了来自不同的特征集或异构源的信息。

在现实生活中，目标对象通常由来自不同视图的信息表示，即数据可以由多个不同的特征集或多个异构源来描述。例如，一幅图像可用像素强度、梯度方向直方图（Histogram of Oriented Gradient，HOG）和局部二值模式（Local Binary Pattern，LBP）等不同的图像特征来描述。在生物医学研究中，不同细胞的化学结构和反应都可以用来代表某种药物，而序列和基因表达值可以在不同方面代表某种蛋白质［4］。多视图数据提供来自不同视图的丰富底层信息，只有所有视图结合在一起才能准确、真实地表示对象。为了充分利用多视图信息，近年来研究人员提出了许多多视图聚类算法［5-7］。

考虑到多个视图特征共同描述同一数据，因此不同视图之间应该存在许多共享信息。如何将多个视图集成在一起，从不同的视图中提取一致的底层信息，是多视图聚类需要重点解决的问题。基于此，研究人员提出一些有效的多视图聚类算法，主要分为图学习（或图融合）和谱学习，图学习通过学习一致性图对多视图数据进行聚类。文献［8］通过学习多个单一图，继而将学习到的多个图集成到具有k个分量的全局图中。文献［9］利用拉普拉斯矩阵上的秩约束学习一致性图，无需后处理步骤直接从图本身获得聚类分配结果。谱学习通过直接学习或构建公共子空间学习一致性表示，从而获取多视图数据之间的一致性信息。例如，自适应加权Procrustes［5］（Adaptively Weighted Procrustes，AWP）利 用 PA（Procrustes Analysis）技术从谱嵌入中恢复了一致性聚类指标矩阵。文献［6］提出一种结合非负嵌入和谱嵌入的多视角谱聚类（NESE）算法，该算法在统一框架中同时学习非负嵌入和谱嵌入，其中非负嵌入直接揭示了一致的聚类结果，从而提升聚类性能。文献［10］表明，挖掘多视图数据之间的底层一致性，对于提高多视图聚类性能非常重要。

综上所述，挖掘多视图数据之间的底层一致信息是一项至关重要和具有挑战性的工作。本文提出一种基于正交基的多视图迁移谱聚类（Orthogonal basis-based Multiview Transfer Spectral Clustering，OMTSC）算法。OMTSC 算法同时学习每个视图的聚类分配矩阵和特征嵌入，并将聚类分配矩阵分解为共享正交基矩阵和聚类编码矩阵。其中正交基矩阵包含一组潜在的聚类中心，即每个多视图样本可以有效地分配给多个不同权重的类。同时，引入基于二部图的协同聚类来控制和实现多视图之间的知识迁移，发现多视图之间的一致性信息，维护各个视图的特征流形信息。在此基础上，通过从正交基矩阵和特征嵌入迁移知识来获取每个视图聚类任务的聚类编码矩阵，将正交基矩阵和加权聚类编码矩阵相结合学习多视图聚类分配矩阵，从而得到最终聚类指标。

1 相关工作

本节将介绍文中用到的符号以及迁移学习和单（多）视图谱聚类的相关工作。

1.1 矩阵表示

在本文中，X={X(1)，X(2)，…，X(V)}表示V个视图的数据矩阵，表示第v个视图的数据矩阵，其中，dv表示第v个视图的特征数目，n表示样本总数目，对应于第v个视图的第(i，j)个元素，I和1 表示对角线元素为1 的单位矩阵。

1.2 迁移学习

迁移学习［11-13］的目的是通过迁移源领域的知识来提高目标学习者在目标领域中的表现，其在文档分类［11］、情感分类［14］、协同训练［15］等许多数据挖掘领域中都取得较好的效果。协同训练考虑在只有一小组标记样本的情况下，通过迁移相关知识给无标记样本，从而提高学习算法的性能。

文献［16］基于协同训练提出一种双视图谱聚类算法，即二部图协同聚类。该算法通过在两个视图之间迁移相关知识，达到提升多视图聚类性能的目的。二部图的相似矩阵定义为：

其中：A∈ℝd×n为数据矩阵，d和n分别表示特征个数和样本个数。

对应的图拉普拉斯矩阵定义为：

其中：D1=diag(A1)；D2=diag(AT1)。

二部图协同聚类的目标函数表示如下：

其中：向量x为特征嵌入；向量y为样本嵌入。可将式（3）转化为：

1.3 正交基聚类

文献［17］提出一种无监督特征选择算法，即同时正交基聚类特征选择（Simultaneous Orthogonal basis Clustering Feature Selection，SOCFS）算法。该算法旨在利用目标矩阵通过正交基聚类获取投影数据点的潜在聚类中心，继而引导投影矩阵选择判别特征。给出特征权重矩阵G∈ℝd×m，目标矩阵K∈ℝm×n，SOCFS正交基聚类部分表示如下：

其中：目标矩阵K可直接对投影的数据点GTA进行聚类。因此，允许K拥有额外的自由度，将其分解为正交基矩阵BK∈ℝm×c和聚类指标矩阵EK∈ℝn×c，即K=BET。施加在BK上的正交约束保证了BK的每一列是独立的，即BK由投影的数据点GTA的正交基构成。此外，BK的列可以看作是相应聚类中心的方向。施加在EK上的正交和非负约束使得EK的每一行只有一个非零元素。因此，可以利用K=BET来寻找潜在的聚类中心，从而更好地分离聚类。

1.4 单视图谱聚类

本节主要介绍通用的单视图谱聚类算法［15］。假设存在n个数据点，需将其分成c个类。谱聚类第1 步是构造一个无向相似图G={X，W}，其中，X∈ℝd×n为顶点集，W∈ℝn×n为对应的相似矩阵，W中的元素wi，j定义为每对顶点(xi，xj)的相似性，可通过式（7）计算：

其中：N(x*)为搜索x*的k近邻函数。

通过求解一个特征值分解问题得到原始数据的谱嵌入，即：

其中：P∈ℝn×c为聚类分配矩阵；L∈ℝn×n为图拉普拉斯矩阵，可由L=I-W定义。求解得出的最优P是L最小的k个特征值对应的特征向量。最后，对聚类分配矩阵P进行k-means 聚类，返回k-means 的聚类结果作为最终指标。

1.5 多视图谱聚类

其中：α(v)是一个非负归一化系数，可以反映不同视图的权重；r是一个标量，用于控制权重在不同视图上的分布；L(v)为第v个视图的图拉普拉斯矩阵；F为求解得出的一致性嵌入，即多视图聚类分配矩阵。

在实际应用中，数据往往由多个不同的特征集或多个异构源来描述，即多视图数据。单视图谱聚类［15，20-22］并不能独立地处理多视图数据，并且聚类性能一般。为解决这一问题，近年来研究人员在单视图聚类的基础上提出多视图聚类算法。多视图谱聚类通过最大化多视图一致性来提高聚类性能。因此，如何最大化多视图一致性成为一个关键问题。

现有的多视图聚类算法［5-7］通过学习一致性嵌入或者一致性图来挖掘多视图一致性，但其存在不足之处：一是多视图一致性信息挖掘不充分；二是无法有效地平衡不同视图的质量差异。本文OMTSC算法与现有算法的不同之处在于：OMTSC 分解一致性表示，即聚类分配矩阵，分别学习正交基矩阵和聚类编码矩阵。一方面，正交基矩阵可以捕获并储存多视图一致性；另一方面，聚类编码矩阵通过加权融合，可更好地平衡不同视图的质量差异。并且OMTSC 算法利用二部图充分挖掘多视图数据的一致性和多样性，通过多样性提升一致性的学习性能。

本文工作的主要贡献如下：

1）提出一种基于正交基的多视图迁移谱聚类（OMTSC）算法。该算法在一个统一框架中学习聚类分配矩阵和特征嵌入。

2）聚类分配矩阵可分解为正交基矩阵和聚类编码矩阵。正交基矩阵保留潜在的聚类中心，并捕获多视图数据之间的一致性信息。

3）OMTSC 算法学习特征嵌入，借助其多样性并最大限度地优化多视图一致性。

2 OMTSC 算法

为有效地挖掘多视图数据之间的一致性，本节提出基于正交基的多视图迁移谱聚类（OMTSC）算法。

2.1 多视图迁移谱聚类

OMTSC 算法沿用文献［17］采用正交基聚类发现潜在的聚类中心的思想，可将每个视图的聚类分配矩阵P分解为两个子矩阵，即共享正交基矩阵B∈ℝc×c和一个聚类编码矩阵E(v)∈ℝn×c。聚类分配矩阵可表示为P(v)=E(v)B，则传统多视图谱聚类可以演化为以下形式：

其中：为第v个视图的归一化图拉普拉斯矩阵；W(v)为第v个视图的相似矩阵；D(v)=diag(W(v)1)。对聚类编码矩阵施加的正交约束促使E(v)的每一行只有一个元素。E(v)的每一行元素选择了B中的一行，这是一个将多个样本分配给不同聚类的过程。对正交基矩阵B施加的正交约束促使B的每一行相互独立。因此，本文利用B来细化潜在的聚类中心，从而捕获多视图数据之间的一致性信息，以获得更好的聚类性能。

OMTSC 算法为更好地学习多视图一致性，通过优化学习到的正交基矩阵B，并致力于进一步细化潜在的聚类中心。本文为每个视图构建对应的特征嵌入，其中k为降维数目。受文献［16］采用基于二部图协同聚类来控制和实现两个任务之间的知识迁移的启发，OMTSC 引入二部图协同聚类，并将多个视图连接在一起。不同于二部图协同聚类算法，OMTSC 适用于多视图聚类任务。考虑到B是多视图数据的共同聚类中心，它可以在多个视图之间进行迁移。B可将在上一视图捕获到的一致性知识迁移到下一视图，从而促进下一视图的学习和优化。同时，OMTSC 通过从正交基矩阵B和特征嵌入A(v)迁移知识来获取并优化每个视图聚类任务的聚类编码矩阵E(v)。其相关模型如下：

在多视图之间迁移的正交基矩阵B，基于多视图数据一致性原则，可以促进一致性信息的学习，多视图谱聚类任务可以从共同聚类中心学习的角度相互迁移一致性知识。以二部图为桥梁，B可将一致性知识迁移给A(v)，从而促使当前视图更好地学习A(v)。得益于协同聚类，A(v)可从多视图数据中提取重要特征。具有群稀疏约束的A(v)可提升处理每个视图的带噪和高维特征的能力，同时提高被提取特征的多样性和完整性。在A(v)提取的多样性信息的基础上，B可通过二部图有选择性地提取多视图一致性知识，从而进一步细化潜在的聚类中心。此外，从A(v)和B迁移知识给E(v)，有利于优化E(v)。同时，E(v)借助其特异性，有效提升多视图一致性。

其中：λ为每个视图的谱聚类与协同聚类目标之间的权衡；μ为稀疏因子。当λ和μ设置为0 时，该模型将退化为具有共同聚类中心的多视图谱聚类。现有的多视图聚类算法［5-7］通过学习一致性嵌入或者一致性图来挖掘多视图一致性。其不足之处在于：一是多视图一致性信息挖掘不充分，MVGL 算法［8］和MCGC 算法［9］由于没有去除冗余信息或考虑噪声矩阵，将对学习到的一致性图造成影响；二是无法有效地平衡不同视图的质量差异。谱聚类的性能在很大程度上取决于相似矩阵的质量。Co-Reg 算法［23］完全忽略了不同视图相似矩阵之间的质量差异，AASC 算法［24］为每个视图分配了一个特定的权重，但这并不能很好地解决不同相似矩阵之间的质量差异。由于谱嵌入具有严格的一致性约束，AASC 算法很有可能学习到较差的谱嵌入。本文提出的OMTSC 算法旨在解决上述问题。

在多视图聚类任务中，正交基矩阵B迭代迁移一致性知识，聚类编码矩阵E(v)对单个视图聚类任务进行编码。一方面，B可捕获并储存多视图一致性信息，形成潜在聚类中心；另一方面，加权聚类编码矩阵可更好地平衡不同视图的质量差异。特征嵌入A(v)和B在二部图上相互迁移知识，从而相互促进彼此的学习和优化。

2.2 模型优化

本节将主要探讨对OMTSC 算法模型的优化。显而易见，直接解决问题式（14）是一项具有挑战性的工作，由于它是非凸的，因此本文采用一种交替方向策略来优化多变量问题。首先固定B、A(v)和α(v)更新E(v)，然后固定E(v)、A(v)和α(v)更新B，继而固定E(v)、B和α(v)更新A(v)，最后固定E(v)、B和A(v)更新α(v)。重复以上步骤直至目标模型收敛。

下面简单介绍更新的过程：

首先明确更新E(v)和B的重点，由于对E(v)和B施加正交约束，因此E(v)和B实际上是位于Stiefel流形上，这个问题可以通过对流形的反复更新来解决，如果E(v)和B不在流形上，则通过更新其在流形上的投影来求解。在迭代过程中，Stiefel 流形由以下命题定义：

命题1假设一个秩为p的矩阵Z，Z在Stiefel 流形上的投影可以定义为：

引入一个变量S来分离上述问题，即：

针对上述问题，本文采用ADMM 算法，其增广拉格朗日形式如下：

其中：Y是拉格朗日乘数。

然后对于下面问题：

有封闭（closed-form）解，即：

算法1基于正交基的多视图迁移谱聚类

3 实验

本节选用3 个数据集进行实验，并同时与9 种聚类算法进行比较，以此评估OMTSC 算法的聚类性能。最后分析OMTSC 算法的时间复杂度、收敛性和参数灵敏性。

3.1 数据集

本文选用3 个真实数据集来评估多视图数据聚类的性能。实验数据集包括人脸、图像和文本数据。数据集详细信息如表1 所示。

表1 数据集信息Table 1 Introduction to datasets

ORL［27］是人脸识别领域流行的人脸数据库，共有400 个样本，分为40 个类，可由3 个视图描述，分别是强度特征、LBP 特征和Gabor 特征。

WikipediaArticles 可分为30 个类，由于其中一些类很少，因此选取其中10 个最受欢迎的类，选取的数据集共有693 个样本。

COIL20［28］是一个图像数据集，共有1440幅图像，可分为20类，对于每幅图像提取3 个不同的特征向量，包括强度特征、LBP 特征和Gabor 特征。

3.2 对比算法

本文选用1 种单视图聚类算法和8 种多视图聚类算法，与OMTSC 算法进行比较。下文简要介绍对比算法：

1）SC-Best［15］。SC-Best 算法对每个视图中的特征进行标准的谱聚类，并由实验者手动选择最佳的聚类性能作为最终的聚类结果。

2）CoReg SPC［23］。该算法通过对聚类假设进行共正则化，使不同的视图保持一致。

3）AASC［24］。该算法将相似矩阵聚集在一起进行谱聚类。

4）RMSC［29］。该算法为多视图聚类恢复了一个共享的低秩转移概率矩阵。

5）MVGL［8］。该算法从不同的单视图中学习全局图。由于秩约束，因此聚类指标直接由全局图获得。

6）MVGC［9］。该算法利用拉普拉斯矩阵上的秩约束学习一致性图，并利用拉普拉斯矩阵直接获取聚类标签。

7）AWP［5］。该算法利用PA技术从谱嵌入中恢复一致性聚类指标矩阵。

8）WMSC［7］。该算法利用不同视图的归一化拉普拉斯矩阵的特征向量张成子空间之间的最大标准角，它可衡量不同视图聚类结果之间的差异性。因此，最小化标准角可以为所有视图带来更好的聚类一致性。

9）NESE［6］。该算法在统一框架中同时学习非负嵌入和谱嵌入，其中非负嵌入直接揭示了一致的聚类结果，从而提升聚类性能。

本文对每种算法分别进行了10 次实验，通过比较各评估指标的均值和标准差对比聚类性能。所有算法的聚类结果由3 个评估指标测量：即聚类精度（Accuracy，ACC）、归一化互信息（Normalized Mutual Information，NMI）、调整兰特指数（Adjusted Rand Index，ARI）。对于每个评估指标，指标值越大，结果越好。

3.3 实验结果与分析

3 个数据集的聚类结果如表2～表4 所示，其中，粗体字体是最优结果，下划线字体是次优结果，表中数值为均值±标准差。SC-Best 是SC 在单一视图下得到的最佳结果。

表2 不同算法在WikipediaArticles 数据集上的聚类结果Table 2 Clustering results of different algorithms in WikipediaArticles dataset

表3 不同算法在COIL20 数据集上的聚类结果Table 3 Clustering results of different algorithms in COIL20 dataset

表4 不同算法在ORL 数据集上的聚类结果Table 4 Clustering results of different algorithms in ORL dataset

由表2～表4 可以得出以下结论：

1）在以上3 个数据集中，OMTSC 算法的聚类性能均优于其他算法。特别是在与WikipediaArticles、ORL 数据集上的次优结果相比，OMTSC 算法在ARI指标上的提升超过了近5%。

2）值得注意的是大多数对比算法在不同的数据集上的性能并不稳定。比如NESE 算法在COIL20数据集上取得次优结果，然而在另外两个数据集上的性能并不理想，而OMTSC 算法在不同数据集上保持着最优结果。这是因为NESE 算法是直接学习一致性嵌入，而OMTSC 算法将一致性嵌入分解为公共正交基矩阵和聚类编码矩阵，考虑多视图的一致性和不同视图的特异性，并在模型优化过程中促进两者的相互学习。同时，利用每个视图特征嵌入的多样性来捕获多视图潜在的一致性。

3）与SC-Best 算法和CoReg 算法相比，OMTSC算法可以充分挖掘多视图一致性，捕获潜在聚类中心，并有效消除视图中的噪声和不重要信息，从而提升其聚类性能。其中，SC-Best 算法需要对每个视图分别进行聚类，然后手动选择最佳性能视图，故不适用于实际应用。而CoReg 算法完全忽略了视图相似矩阵之间的质量差异，对学习到的一致的特征向量集有很大影响。OMTSC 算法考虑了不同视图的显著差异，它通过学习加权聚类编码矩阵，可以很好地平衡不同视图相似矩阵之间的质量差异。

4）ORL和COIL20数据集都有3个视图，其中视图的特征数目大多超过3 000 个。由于ORL 和COIL20 数据集的高维性，其中存在一些噪声和冗余信息。OMTSC 算法基于群稀疏约束的特征嵌入，可有效消除视图中的噪声，降低视图中高维和噪声特征对聚类性能的影响。可以看出，与ORL数据集上的MVGL 算法相比，OMTSC 算法在ACC上的提升超过了近10%；与COIL20 数据集上的MCGC 算法相比，OMTSC 算法在AR 上的提升超过了近10%。这可能是因为MVGL 算法和MCGC算法没有去除冗余信息或噪声矩阵。

综上所述，本文提出的OMTSC 算法在聚类性能及稳定性上，均优于其他先进的多（单）视图聚类算法。

3.4 时间复杂度分析

不同算法的时间复杂度如表5 所示。由算法1可知，OMTSC 算法可分为2 个子问题。对于第1 个问题，涉及计算一个正交基矩阵B和多个聚类编码矩阵E(v)的投影，其计算包括矩阵乘积和加法，时间复杂度为O(n2k)。为了寻求投影，需要对E(v)和B进行奇异值分解。已知对于m×n矩阵，奇异值分解的时间复杂度为O(min{mn2，m2n})。因此，计算正交基矩阵B和聚类编码矩阵E(v)及投影的时间复杂度为O((t1+t2)(n2k))。其中t1和t2分别是E(v)和B单次优化过程的更新迭代次数。对于第2 个问题，OMTSC 算法计算新的特征嵌入A(v)的时间复杂度为O(n2k)，新的变量S的时间复杂度为O(max(n2D，n3)k)，Y的时间复杂度可忽略不计。因此，OMTSC 算法优化迭代部分的总时间复杂度为O(t3((t1+t2)n2k+max(n2D，n3)k))，其中t3是优化过程的总迭代次数。

表5 不同算法的时间复杂度Table 5 Time complexity of different algorithms

3.5 参数灵敏性

在OMTSC 算法中存在有3 个参数：λ为每个视图的谱聚类与协同聚类目标之间的权衡；μ为稀疏因子；r是一个标量，用于控制权重在不同视图上的分布。根据ORL 和WikipediaArticles 数据集的实验结果，分析以上参数对聚类评估指标ACC 的敏感性，其结果如图1 所示。

1）当固定r=2 时，将参数λ和μ设置为［0.000 1，10 000］，结果如图1（a）、图1（b）所示。可以看出，在ORL 和WikipediaArticles 数据集中，当λ=［0.000 1，1］和μ=［0.000 1，10 000］时，算法能取得最优性能。由此可知，参数λ对OMTSC 算法的性能较敏感，参数μ对OMTSC 算法的性能不敏感。

2）在ORL 数据集上，固定参数λ=0.1和μ=0.001；在WikipediaArticles 数据集上，固定参数λ=1和μ=1。同时，将参数r设置为［2，10］。结果如图1（c）、图1（d）所示。由此可知，在这两个数据集上，当r=2 时算法能取得最优性能。

图1 不同参数下OMTSC 算法在ORL 和WikipediaArticles 数据集上的聚类性能Fig.1 Clustering performance of OMTSC algorithm on ORL and WikipediaArticles datasets with different parameters

3.6 收敛性分析

本节采用ORL 和WikipediaArticles 数据集来评估OMTSC 算法的收敛性。当更新E(v)和B时，对应的更新问题分别是E(v)和B的连续函数，故只要步长t1和t2足够小，其值便可单调递减。一般来说，步长t1和t2越小，所需的迭代次数就越大。本文设定t1=t2=1。根据式（14），ADMM 算法［30-31］给出详细的解释，并说明了如何保证该算法的收敛性。

4 结束语

本文提出了一种基于正交基的多视图迁移谱聚类（OMTSC）算法。将每个视图的聚类分配矩阵分解为正交基矩阵和一个聚类编码矩阵，正交基矩阵通过捕获并储存多视图一致性，获取多视图数据的潜在聚类中心。同时，基于加权聚类编码矩阵，OMTSC 可以更好地平衡不同视图之间的质量差异。通过引入协同聚类控制和实现知识迁移，在二部图上同时学习优化特征嵌入和聚类分配矩阵。在此基础上，利用特征嵌入的多样性最大化多视图一致性，学习最优的潜在聚类中心，进而提升多视图聚类性能。此外，本文设计一种交替迭代优化算法对目标函数进行优化，在3 种真实基准数据集上的实验结果验证了该算法的有效性。下一步将考虑构造自适应图，以更好地发现数据的内在关系，提升聚类性能。