基于特征选择与鲁棒图学习的多视图聚类

黄奕轩，杜世强，，余瑶，肖庆江，宋金梅

（1.西北民族大学 数学与计算机科学学院，兰州 730030；2.西北民族大学 中国民族信息技术研究院，兰州 730030）

0 概述

随着数据收集和存储能力的提高，各领域已经积累了丰富的数据资源，快速对这些数据进行处理、分析和分类尤为重要。聚类［1-2］作为处理和分析数据的高效方法之一，已被广泛应用于机器学习、模式识别和数据挖掘等领域。

由于信息源的多样性，越来越多的多视图数据不断涌入人们的生活，为了对多视图数据进行分类，一系列多视图聚类方法相继被提出。多视图聚类通过融合多个视图的互补信息和兼容信息，从而获得更稳定的聚类性能。其中用于多视图的谱聚类算法［3-4］和K-means［5-7］算法应用最为广泛。与K-means聚类相比，谱聚类作为一种基于图的算法，在检测数据结构方面有着更强的能力［8］。根据图构建方式的不同，现有的多视图聚类方法主要分为两类：基于自表示的子空间多视图聚类和基于自适应近邻图学习的多视图聚类。

基于自表示的子空间多视图聚类算法用剩余其他数据点的线性组合来表示某一数据点，得到的系数矩阵即为图矩阵，其在滤除噪声影响的同时获取了数据样本的全局结构。文献［9］对表示矩阵施加低秩约束来捕获数据样本的全局结构。潜在嵌入空间的多视图聚类模型［10］先将各视图数据映射为共同的表示矩阵，然后再学习全局相似图进行谱聚类。文献［11］提出一种基于自适应图的子空间学习框架，通过同时学习数据的低秩表示和局部结构来获得子空间的最佳全局表示。多视图低秩稀疏子空间聚类［12］通过构造所有视图之间共享的亲和矩阵来学习子空间表示。文献［13］同时对每个视图的子空间表示进行聚类，为保证不同视图之间的一致性，模型强制将不同视图中的数据点分为同一类。文献［14］在子空间表示学习的基础上提出主动学习共识子空间的方法。文献［15］将原始数据映射到低维子空间中，在低维数据中挖掘信息的同时捕获数据的全局结构和局部结构，从而提高了聚类性能。但是，上述方法忽略了不同视图的重要性，即信息量较多的视图和信息量较少的视图被同等对待，因此会丢失一些重要的信息。

基于自适应近邻图学习的多视图聚类方法具有识别不同视图的聚类能力，其通过给每个数据点分配一个概率作为另一个数据点的邻域来构建一个图，并将学习到的概率作为两个数据点之间的相似性，可以有效探索数据样本的局部结构。文献［16］提出自适应近邻学习方法，将欧式距离作为度量标准，自适应地构造一个关系矩阵。文献［17］采用自适应近邻图学习方法构造数据样本的相似矩阵，然后融合相似矩阵进行谱聚类来获取最终聚类结果。之后，文献［18］对上述模型又进行了改进，将图矩阵、图融合和图聚类整合到一个框架中，以获得整体最优解。文献［19］提出了无参数自适应邻域构建无向图的方法降低算法的复杂度。为了解决不同视图的特征不同这一问题，文献［20］提出了一个无参数模型，可以自适应地为相似图分配权重。基于自适应加权的多视图聚类［21］首先分别学习不同视图的谱嵌入，然后通过谱旋转学习到一致的聚类结果。多图自加权多视图聚类［22］利用原始数据样本分别学习多个关系图，然后采用自加权技术融合多个关系图得到一个共识图，但是他们都是从原始数据中学习图，忽略了噪声和离群点的影响，无法保证样本之间的真实相似度。

针对上述问题，本文提出基于特征选择和鲁棒图学习的多视图聚类算法FRMC。通过特征选择学习每个视图的特征，利用自表示学习从多视图数据中得到样本的表示系数。在此基础上，引入自适应近邻图方法在表示系数的基础上构造鲁棒图矩阵，利用矩阵加权和得到最终的亲和图矩阵用于谱聚类。FRMC 算法将特征选择、噪声去除和鲁棒图学习集成在一个框架中，从而获得整体最优解，通过特征选择为不同的特征分配不同的权重，通过自适应学习不同视图的特征，降低高维数据并减少冗余特征，通过自表示学习滤除噪声和离群点同时获取数据样本的全局结构，在自适应近邻学习构建鲁棒图的同时保持数据样本的局部结构。

1 相关工作

在本节中，首先引入符号说明，然后分别介绍多视图子空间聚类算法和自适应近邻图学习方法。

1.1 符号说明

为方便起见，用X表示样本矩阵，X的每一列表示一个样本。本文算法中的符号说明如表1 所示。

表1 符号说明Table 1 Symbol description

1.2 多视图子空间聚类

多视图子空间聚类算法首先从自表示学习框架中学习各视图表示矩阵，然后利用学习到的表示矩阵构建拉普拉斯矩阵进行谱聚类。模型的一般表示形式如下［23］：

其中：Zv∈Rn×n(v=1，2，…，m)，是自表示矩阵，Z的每一列zi都被认为是样本xi在X为字典情况下的新表示；第一项R(Xv，Xv Zv)=，表示重构误差项；α>0 用于平衡正则化项ϕ(·)。

在相似图B上进行谱聚类可以得到最终的聚类结果，其中：

1.3 自适应近邻图学习

其中：Sv是第v个视图的相似矩阵，通过式（4）自适应学习到的Sv能够保留数据样本的局部结构。

2 FRMC 算法

本节提出了基于特征选择和鲁棒图学习的多视图聚类算法（FRMC），并给出其目标函数的优化过程。与其他相关算法相比，FRMC 主要有以下3 个特点：1）自适应选择不同视图的特征，在数据降维的同时减少了噪声和冗余特征的影响，并且在自表示矩阵的基础上能自适应地学习鲁棒图；2）同时捕获数据样本的全局结构和局部结构，采用l2，1范数测量样本噪声能更准确地揭示数据的真实分布；3）使用一种基于交替方向最小化的算法来优化目标函数。

2.1 目标函数

考虑到原始数据通常包含高度冗余特征，笔者希望充分地利用跨多个视图的有效特征，使得数据空间结构变得更加清晰。因此，为了更好地揭示多视图聚类结构，本文将特征选择技术应用于聚类算法中。文献［9-15］的研究证明了多视图子空间聚类算法能有效地减少噪声的影响，提高算法的鲁棒性。因此，本文将特征选择和鲁棒图学习集成到一个框架中。FRMC 算法的主要计算公式如下：

2.2 目标函数求解

式（5）可以通过交替方向最小化（ADM）策略［25］和增广拉格朗日乘子法（ALM）来解决。为方便求解Zv，本文引入辅助变量Qv和Jv。相应地，问题式（5）可以表示为：

构造式（6）的拉格朗日函数式为：

其中：μ>0 是惩罚参数；和(v=1，2，…，m)是拉格朗日乘数。为解决问题式（7），通过固定其他变量来最小化L1，迭代地更新每个变量，更新规则如下：

1）更新Pv。固定除Pv以外的其他变量，子问题Pv为：

根据式（4），问题式（8）可以表示为：

构造式（10）的拉格朗日函数式为：

2）更新Zv。固定除Zv以外的其他变量，子问题Zv为：

式（13）是关于Zv的凸函数，对Zv求导并将它置为0，则式（13）的封闭解为：

3）更新Ev。固定除Ev以外的其他变量，子问题Ev为：

引用文献［26］提出的方法解决上述问题，得到解：

4）更新Jv。固定除Jv以外的其他变量，子问题Jv为：

式（18）也是关于Jv的凸函数，对Jv求导并将其置为0，则式（18）的解为：

5）更新Qv。固定除Qv以外的其他变量，子问题Qv为：

为了简化符号，暂时忽略视图数v。式（20）中每个i是独立的，通过解决以下问题获得Q的第i行：

通过构造上式的拉格朗日函数式并利用KKT［27］条件得到qi的最优解为：

其中：(·)+=max(·，0)。

6）更新Av。Lv也是Av的函数，固定除Av以外的其他变量，子问题Av为：

式（24）对于每个i是独立的，因此，对于每个可以分别解决以下问题：

将ai限制为k个非零项，有aik≥0，ai，k+1≤01=1。由上述条件可得：

FRMC 算法详细迭代更新过程如算法1 所示。

算法1FRMC

输入多视图数据Xv=∈ℝdv×n，参数α、β、γ、μ

输出聚类结果C

9）对亲和图矩阵A进行谱聚类，得到聚类结果C。

3 实验与结果分析

将FRMC 算法与其他算法进行比较，验证其在聚类任务上的有效性，所有实验均在Matlab 上进行。

3.1 数据集

为了检验算法的性能，在6 个公开的标准数据集上进行聚类实验，每个数据集的具体信息如表2所示。

表2 数据集信息统计Table 2 Information statistics of datasets

1）BBCSport 数据集主要有2 个视图，包含了来自BBC 体育网站的544 份文件，分别对应于5 个热门领域发表的体育文章。

2）MSRC-v1数据集由210 张图像和7 个类别组成，对于1 张图像有5 个特征向量，包括色矩、GIST、CENT、HOT 和LBP。

3）HW2 数据集由2 000 张图像组成，10 个类别从0 到9 个数字不等，实验选择了76 个字符形状的傅里叶系数和216 个轮廓相关特征。

4）Scene 数据集有2 688 张图像，对于每张图像提取了4 个不同的特征向量，包括512DGIST、432D色矩、256DHOG 和48DLBP。

5）Uci-3view 数据集由10 个类的手写数字组成，每个类有200 个不同的数字，有2 000 个数据点。

6）ORL 数据集是人脸数据集，由40 个不同的类别组成，每个类别包含10 幅在不同时间、光照、面部表情和面部细节下拍摄的不同图像。

3.2 对比算法

为验证算法的有效性，本文简要介绍7 种对比算法来验证FRMC 的性能优势。

1）谱聚类（SC-best）［28］：该算法返回多个视图中最好的聚类结果。

2）从噪声数据中学习鲁棒图（RGC）［7］：该算法自适应地消除了原始数据中的噪声和误差，从干净的数据中学习鲁棒图，提高了聚类和半监督分类的性能。

3）基于自适应加权的多视图聚类（AWP）［18］：该算法将多个不同的谱嵌入集成到一个一致的索引矩阵中。

4）多图自加权多视图聚类（SwMC）［19］：该算法通过融合不同的权重图来构造相似图，然后利用相似图构造一个具有明确块对角结构的拉普拉斯图。

5）自加权多视图学习（AMGL）［17］：该算法没有额外的参数，能够自动学习每个视图的最优权值。

6）多视图低秩稀疏子空间聚类（MLRSSC）［11］：该算法通过构造所有视图之间共享的亲和矩阵来学习联合子空间表示。

7）一致和特定的多视图子空间聚类（CSMSC）［12］：该算法是一种新的多视图子空间聚类方法，将一致性和特异性共同用于子空间表示学习。

在所有的对比算法中，RGC、AWP、SwMC 和AMGL 使用相似矩阵作为算法的输入，并将图学习和聚类集成到一个框架中，而MLRSSC 和CSMSC则使用自表示系数矩阵作为算法的输入，两个算法都将子空间学习和聚类集成到一个框架中。

3.3 评价指标

本文使用精度（ACC）、归一化互信息（NMI）、纯度（Purity）和调整兰德指数（ARI）这4 个指标来评估算法的聚类性能，指标值越高，表示算法的聚类性能越好，表3～表8 列出了聚类结果，其中加粗表示最优结果。

表3 BBCSport 数据集上的实验结果Table 3 Experimental results on BBCSport dataset %

表4 MSRC-v1 数据集上的实验结果Table 4 Experimental results on MSRC-v1 dataset %

表5 HW2 数据集上的实验结果Table 5 Experimental results on HW2 dataset %

表6 Scene 数据集上的实验结果Table 6 Experimental results on Scene dataset %

表7 Uci-3view 数据集上的实验结果Table 7 Experimental results on Uci-3view dataset %

表8 ORL 数据集上的实验结果Table 8 Experimental results on ORL dataset %

3.4 实验结果分析

由表3～表8 可以看出，FRMC 算法在BBCSport、MSRC-v1、HW2 和ORL4 个公共数据集上都取得最佳聚类效果。FRMC 能自适应选择有用的特征，有效降低冗余特征的影响，通过鲁棒自表示学习获取表示系数，滤除噪声的同时获取数据样本的全局结构，并与自适应图学习结合，可以更好地增强多视图聚类结构。此外，鲁棒图矩阵建立在干净的表示系数矩阵上，可以更好地揭示样本之间的属性。FRMC 的优势具体体现在以下4 个方面：

1）与单视图聚类算法SC 和RGC 相比，FRMC 在4 种评价指标上聚类性能提高了10～40 个百分点。FRMC 可通过学习数据样本的全局结构和局部结构更好地利用多视图信息。

2）单视图聚类算法RGC 在Scene 数据集上的性能优于SwMC，这是由于RGC 构造鲁棒图矩阵用作算法的新输入，而SwMC 直接从原始数据中构造相似矩阵，这表明了构造鲁棒图的重要性。FRMC 构造了基于自表示系数矩阵的鲁棒图，更好地提高了聚类性能。

3）与在原始数据上构建图的AWP、SwMC和AMGL算法相比，FRMC 滤除了原始数据中的噪声和离群点，表现出更好的聚类性能。

4）与以自表示系数矩阵为输入的MLRSSC 和CSMSC 算法相比，FRMC 算法表现出更好的聚类性能：ACC 提升1～20 个百分点，NMI 提升1～10 个百分点，纯度提升5～20 个百分点，ARI 提升2～28 个百分点。FRMC 通过自适应选择重要特征增强了聚类结构，证明了数据进行特征选择的重要性。

综上所述，与其他相对比算法相比，FRMC 可以显著提高聚类性能。

3.5 算法复杂度分析

FRMC 的最高计算成本来自式（14）和式（19）。式（14）中的Zv和式（19）的Jv计算复杂度均为O(n3)。以数据集Scene 为例，由于其数据样本多，计算量大，因此本文利用Woodbury 公式［29］对式（14）和式（19）求逆，将复杂度降至O(dvn2)。因为Zv在迭代过程中没有更新，所以只需要一次求逆，故FRMC 的总时间复杂度为O(2m(dvn2))。FRMC 的存储成本主要也来自Zv，由于求解Zv利用了矩阵的求逆运算，因此存储复杂度为O(n2)。表9 列出了FRMC 算法和7 种对比算法在6 个数据集上运行10 次的平均时间。

表9 各算法在6 个数据集上的运行时间Table 9 Running time of each algorithm on six datasets 单位：s

由表9 可以看出：基于单视图的SC 算法运行时间少于多视图聚类算法，但聚类性能远低于多视图聚类算法；AMGL 算法在比较算法中运行时间最少，但在所有数据集上聚类性能低于FRMC 算法；与基于图学习的RGC、AWP、SwMC 和AMGL 算法相比，FRMC 算法运行时间最长，但是聚类性能最好；与基于自表示学习的方法MLRSSC 和CSMSC 相比，除了在Scene 和Uci-3view 数据集上，FRMC 算法均得到了最好聚类效果；此外，FRMC 算法在6 个数据集上的运行时间少于MLRSSC 算法。由表9 可知，虽然提出的基于特征选择和鲁棒图学习的多视图聚类算法运行速度不是最快的，但能够在可接受的时间范围内达到更好聚类效果。

3.6 收敛性分析

图1 显示了FRMC 在BBCSport 数据集上的收敛曲线，可见算法经过30 次迭代后趋于稳定，这说明FRMC 具有较好的收敛性。

图1 收敛性曲线Fig.1 Convergence curve

3.7 鲁棒性分析

利用合成数据集来验证算法的鲁棒性，实验具体设置参考文献［16］。实验使用的合成数据集是一个100×100 的矩阵，由4 个25×25 的块矩阵对角排列组成，每个块内的数据表示1 个类中2 个对应点的亲和度，亲和度数据在0～1 的范围内随机生成，而块外的数据表示噪声，噪声数据在0～f的范围内随机生成，f可以设置为0.5、0.6 或0.7。任意选取20 个噪声数据点，并将其值设置为1。

实验选取了2 种具有代表性的算法来验证FRMC 的鲁棒性，如图2 所示，图中展示了数据噪声为0.6 时的聚类图，可见FRMC 算法学习到的矩阵的块结构比其他算法更清晰。因此，FRMC 在捕获数据空间的不同结构方面表现得更好。

图2 对块对角合成数据进行聚类的结果Fig.2 Clustering results on the block diagonal synthetic data

3.8 参数分析和聚类可视化

FRMC 算法有α、β、γ和μ4 个参数。根据低秩表示算法得到α=，γ可以从式（28）中获得，因此，采用交叉验证方法来求解参数β和μ。一般来说，通常在［0.001，1 000］范围内调整参数，经过大量实验验证，当β和μ在［0.001，10］的范围内时，效果相对较好，所以，选择这个区间来评估算法的聚类性能。其他7 种比较算法则均按照文献中所推荐的参数范围进行网格搜索并选取最好的结果。

本文在HW2 数据集上展示FRMC 和3 种不同对算法的聚类可视化结果（彩色效果见《计算机工程》官网HTML 版），同种颜色的数据点代表同一类，如图3 所示。对比算法中都存在不同类别分离不充分的情况，FRMC 算法使得同类数据点之间的距离相对较小，不同类之间的距离相对较大，能够有效地将相似对象分组到同一个类别中。

图3 HW2 数据集上的聚类可视化结果Fig.3 Clustering visualization results on HW2 dataset

4 结束语

本文提出基于特征选择和鲁棒图学习的多视图聚类算法FRMC，将样本的特征选择、噪声去除和鲁棒图学习集成到一个框架中，以使模型获得整体最优值。此外，不仅通过自适应选择特征和自表示学习减少冗余特征和噪声的影响，同时还考虑多视图数据样本中的全局结构和局部结构。在6 种不同数据集上与7 种聚类算法的实验结果对比，验证了FRMC 在揭示样本类别属性方面的良好性能。后续将利用二部图技术降低FRMC 在处理大规模数据集时的计算复杂度，同时针对每个视图中聚类的多样性问题，为每个视图分配适当的权重，进一步提高算法的聚类性能。