聚类是数据挖掘中的一项重要任务，将相似的点划分到同一簇中，相异点划分到不同簇中.聚类在信息检索[1]、医疗诊断[2]、社交网络分析[3]、图像分割[4]等领域都发挥着重要作用.传统的单视图聚类算法已遇到瓶颈，在过去的几年中，多视图聚类成为前沿研究.

多视图聚类利用多视图数据中的信息来进行聚类.多视图数据从多个角度来描述同一事物，随着技术的进步，近年来这类数据日益增多.例如，可以同时使用多个设备对同一事物进行拍摄，得到的多个图像属于多视图数据.再者，同一张图像可以使用不同的特征来表示，多种特征形成的数据即为多视图数据.通过使用多视图数据，多视图聚类能够利用不同视图之间的互补信息，从而可能提高聚类的效果.

迄今为止，研究人员已提出大量的多视图聚类算法，大致包括基于多核学习的算法[5-7]、基于矩阵分解的算法[8]、基于图学习的算法[9-10]、基于谱聚类的算法等.其中，基于谱聚类的多视图聚类算法也可称为多视图谱聚类算法，该类算法将谱聚类的思想应用到了多视图数据的聚类中，通常可以分为4类:第1类是为所有视图的数据生成一个一致的相似度矩阵，然后利用谱聚类算法得到聚类结果.有些算法[11-13]直接从原始数据中为所有视图学习统一的相似度矩阵，还有一些算法利用核函数[14]或k近邻图[15-16]等方式先为每个视图构造相应的初始相似度矩阵，然后从中学习一致性相似度矩阵.第2类是为各个视图的数据生成相应的相似度矩阵，再利用各视图的相似度矩阵生成一致的拉普拉斯矩阵[17]，从拉普拉斯矩阵中生成划分矩阵，使用k均值聚类算法得到聚类结果.第3类是为每个视图构造好相似度矩阵后，直接利用谱聚类的思想，为所有视图学习统一的划分矩阵[18]，然后使用k均值算法进行聚类.第4类是基于协同训练的思想[19]，利用视图间的互补信息进行聚类.尽管该领域已有大量研究成果，但仍然存在不少挑战.首先，原始数据通常包含冗余信息和噪声，很多算法忽略了这一问题.其次，在聚类过程中，每个视图扮演的角色是不同的，不少算法将各个视图同等对待.为了解决这些问题，本文提出了一种基于Markov链的多视图谱聚类算法——一致性引导的自适应加权多视图聚类(consensus guided auto-weighted multi-view clustering, CAMC)，主要思想如图1所示.由图1可知，该算法首先为原始数据的各个视图构建转移概率矩阵，然后为所有视图学习一致性转移概率矩阵，最后执行谱聚类算法.目标是为各视图学习不同权重，并得到所有视图的一致性邻接矩阵.

本文的主要贡献有3个方面:

1) 为每个视图构造一个转移概率矩阵，以减小原始数据中的冗余信息和噪声对聚类性能的影响.

2) 以自适应加权的方式获得一致性转移概率矩阵，并对一致性转移概率矩阵的拉普拉斯矩阵进行秩约束，以确保拉普拉斯图中连通分量的数目与聚类的数目完全相等.

3) 在人造数据集上证明了CAMC是有效的；在7个真实数据集上的大量实验表明，CAMC算法在聚类性能方面优于其他单视图和多视图聚类基准算法.

1 相关工作

为了更加方便地介绍后面的内容，本文在表1中对文中的符号进行了说明.由于本文提出的算法属于基于Markov链的谱聚类算法，故在本节对该类算法的相关工作进行介绍.

目前，已有研究[20-21]在聚类和Markov链之间建立了联系.给定n个数据点的单视图数据矩阵X∈d×n，X的相似度矩阵用S表示.计算S的一种常见方式是其中，i,j∈(1,n)，xi,xj分别表示第i、第j个向量，σ是标准差.之后构建图G=(V,EG,S)，其中V是顶点集，EG是边集，S用来表示边的权值.转移概率矩阵定义为P=D-1S，其中D为对角矩阵，从Markov链的角度来看，pij是从节点Nodei一步到达节点Nodej的随机行走概率，图G存在平稳分布π，其中谱聚类就是对图G进行划分，使Markov随机行走尽量在同一簇内进行.关于基于Markov链聚类的详细信息，请参考文献[20-21].

在基于Markov链的多视图聚类研究方面，Xia等人[22]提出了鲁棒多视图谱聚类法(robust multi-view spectral clustering, RMSC).RMSC通过低秩和稀疏分解从所有视图的数据中恢复了潜在的转移概率矩阵，并将其作为相似度矩阵，使用谱聚类得到最终的结果.RMSC的目标函数为:

(1)

其中，P(v)表示第v个视图构造的转移概率矩阵，P*是学到的转移概率矩阵，E(v)是第v个视图中学到的转移概率矩阵和构造矩阵之间的误差.

Wu等人[23]提出了多视图谱聚类的本质张量学习法(essential tensor learning for multi-view spectral clustering, ETLMSC).ETLMSC将各个视图得到的转移概率矩阵叠成张量，对张量施加核范数的约束，确保张量的低秩性质，并对张量进行旋转来探索不同视图之间的关系.ETLMSC的目标函数为:

(2)

其中，表示低秩张量，表示旋转后的转移概率张量，表示二者之间的误差.

尽管这些方法取得了不错的结果，但仍有很多方面需要改进.从式(1)中可以得知，RMSC将各视图平等对待，忽视了视图所起作用的多样性.ETLMSC使用张量来探索各视图之间的关系，但是当计算最终的相似度矩阵时，直接将张量切片进行平均，忽略了各视图之间的差异.由于我们提出的算法CAMC更为接近RMSC，故在实验部分使用RMSC与CAMC进行对比.

2 一致性引导的自适应加权多视图聚类

2.1 算法思想

设有一个含m个视图的数据矩阵，它的第v个视图用d(v)×n表示，其中n是样本的数量，d(v)表示第v个视图中样本的维度.

基于Markov链的谱聚类算法很关键的一个环节是获得最终转移概率矩阵.本文使用文献[24]中的算法为每个视图学习相应的转移概率矩阵，在RMSC的启发下，利用核范数确保学到的一致性转移概率矩阵P*是低秩的.该方案的表达式为:

(3)

其中,i,j∈(1,n).但是，这种方式忽略了各视图之间的差异性，故为每个视图分配了权重，即

(4)

其中，w(v)是第v个视图的权值.

受到自动分配权值策略[9,25]的启发，本文提出了一种自适应加权的策略来学习一致性的转移概率矩阵.令w(v)为

(5)

则式(4)等价于

(6)

式(6)所学到的转移概率矩阵中相连部分的数量是不确定的.假设簇的数量是c，为了使P*恰好有c个相连部分，对P*的拉普拉斯矩阵的秩进行约束.目标函数表达式设计为:

(7)

其中，LP*表示P*的拉普拉斯矩阵.

根据Fan[26]的定理求解秩约束问题，可以使用来进行，tr(·)表示矩阵的迹.因此，最终的目标函数为

(8)

如图1所示，CAMC先为原始数据的各个视图构建转移概率矩阵；然后，利用式(8)为全部视图学习一致性转移概率矩阵；最后，将其作为输入执行谱聚类算法，得到聚类结果.所学的一致性转移概率矩阵如图2所示，同一簇内的点之间存在转移概率，不同簇之间转移概率值为0，一致性转移概率矩阵的秩等于簇的数目.

2.2 优 化

CAMC的目标函数为式(8)，其等价于

(9)

其中，w(v)的值见式(5).

为了求解式(9)，本文采用交替方向乘子法(alternating direction method of multiplier, ADMM)[27]设计优化策略.将矩阵变量Q作为辅助变量来替代核范数中的P*.式(9)可转化为:

(10)

式(10)的求解可以转换为求解5个子问题.

1) 求解w(v)，将其他变量固定，w(v)的值见式(5).

2) 求解P*，固定其他变量，关于P*的目标函数变为

(11)

其中，Y是拉格朗日乘子，μ是惩罚项参数.对于不同的i，该问题是独立的，故而有

(12)

设式(12)等价于

(13)

式(13)可以通过投影算法[28]求解.

3) 求解F，固定w(v)，Q,P*时,F的值可以通过求解问题得出:

(14)

找出LP*的c个最小特征值，对应特征向量为F的解.

4) 求解Q，当w(v),P*,F固定不变时，式(9)变为

(15)

式(15)等价于

(16)

式(16)可通过奇异值阈值法[29]进行求解.

5) 更新乘子Y和惩罚项参数μ:

(17)

上述5个子问题是求解目标函数式(9)的核心内容.CAMC的算法流程如算法1所示:

算法1. CAMC.

输入:多视图数据集X，超参λ1和λ2;

输出:聚类结果.

① 初始化

② 为每个视图构建转移概率矩阵；

③ while iter<maxiter 且未收敛do

④ iter=iter+1;

⑤ for v from 1 to m do

⑥ 根据式(5)更新w(v);

⑦ end for

⑧ 根据式(13)更新P*;

⑨ 根据式(14)更新F;

⑩ 根据式(16)更新Q;

根据式(17)更新Y和μ;

end while

将P*作为相似度矩阵，执行谱聚类算法.

2.3 算法复杂度和收敛性

算法CAMC的求解涉及5个子问题.求解w的复杂度为O(mn)；求解P*时使用了矩阵的加法，复杂度为O(n2)；求解F时涉及了特征向量分解，复杂度为O(n3)；求解Q时使用了奇异值分解，复杂度为O(n3)；更新乘子Y的复杂度为O(n2)，所以整个算法的复杂度为O(n3+n2).

根据文献[10]，式(14)是凸函数，由于F范数和核范数均是凸函数，根据文献[30]，式(9)是凸的.

本文提出的优化算法在每次迭代时，需要求解式(10)(13)(14)(16)(17).根据已有文献[10,25]，这几个问题都是凸的，这确保了算法1能够收敛到问题的最优解.

3 实 验

为了对算法进行评估，在人造数据集和真实数据集两大类数据集上进行了实验，采用了7个常用的聚类指标：标准化互信息(normalized mutual information, NMI)、准确率(accuracy, ACC)、F分数(F)、调整后的兰德指数(adjusted rand index, ARI)、精度(precision, P)、召回率(recall, R)、纯度(Purity).这些指标的定义参见文献[31]，它们的值越高，聚类效果越好.

3.1 人造数据集实验分析

在文献[32]提供的人造数据集双月(Two-Moon)上进行了实验.如图3(a),3(b)所示，该数据集包含了2个视图，每个视图里的点都是2个月亮的形状，对应着2个簇，每个簇中有100个点，每个视图中都加上了0.12%的高斯噪声.CAMC在此数据集上聚类得到的标签和数据集中的标签是完全一致的.为了直观地对结果进行说明，进行了可视化展示.选取了距离较近但属于2个不同簇的40个点，在一致性转移概率矩阵中提取出来了相应的部分，对这40个点在2个视图中使用学到的一致性转移概率矩阵进行可视化，结果如图3(c),3(d)所示.尽管这些点距离较近，在聚类时容易出错，但CAMC能将它们分开，这表明了基于Markov链的方法是有效的.另外，该复杂图形中存在噪声，CAMC能有效将点分开证实了间接学习相似度矩阵和使用低秩正则化能够减弱噪声对聚类的影响.此外，图4展示了为各视图构造的转移概率矩阵和学习到的一致性转移概率矩阵，明显可以看出，学习到的一致性转移概率矩阵具有更好的块结构，更适合聚类.基于自动加权机制进行聚类，能够更有效地利用不同视图之间的互补信息，因而能提升聚类性能.

3.2 真实数据集简介

本文选取了7个真实数据集进行实验.数据集包括：英国广播公司体育新闻数据集(BBCSport)[33]、三新闻源文本数据集(3Sources)[34]、微软逐像素标记的图像数据集v1(MSRC)[35]、Citeseer科学出版物引用网络文本数据集(Citeseer)[36]、Mfeat手写体识别数据集(Mfeat)[37]、新闻组数据集(NGs)[38]、100种植物叶子数据集(100leaves)[39].这些数据集的详细信息如表2所示.

3.3 参数敏感性分析和算法收敛性验证

CAMC中有2个超参λ1和λ2，用来平衡目标函数中3项之间的关系.这2个超参的值域为{0.000 1,0.01,0.1,1,10,100,1 000}.在3Sources和Mfeat数据集上，使用了网格化调参法对CAMC进行参数敏感性实验，记录聚类结果的准确率值和标准化互信息值，结果如图5所示.

从图5中可以看出，当λ1>100时对结果较为敏感，当λ1<100时性能较为稳定；参数λ2的变化对性能影响不大，但当λ2<1时聚类效果要更好一些.总的来说，CAMC的性能是比较稳定的.

本文的2.3节对算法的收敛性从理论上进行了证明，这里以实验的方式对其进行验证.在3Sources,BBCSport,NGs,Citeseer这4个数据集上进行了收敛性实验，变化值定义为其中k代表迭代次数.从图6中可以看出，变化值尽管刚开始有一点小波动，但随着迭代次数的增加，该值递减并趋于0，根据柯西收敛定理，算法是收敛的.

3.4 性能可视化

为了进一步说明CAMC性能上的优势，在NGs数据集上，对每个视图的原始数据和最终学习到的一致性转移概率矩阵都通过t分布随机邻居嵌入(t-SNE)[40]进行可视化表示，如图7所示.使用各种颜色区分不同的簇.相同颜色的点越近、不同颜色的点越远表示簇的可分离性越好.从图7中可以看出，学习到的一致性转移概率矩阵的聚类效果明显优于原始数据.主要原因在于CAMC能够利用不同视图之间的互补信息，为不同视图学习最优的权重.

3.5 对比算法

为了验证CAMC的有效性，本文将CAMC与8种基准算法进行了比较.其中谱聚类(SC)[41]、低秩表示子空间聚类(LRR)[42]是单视图聚类算法，基于共同正则化的聚类(CoReg)[43]、鲁棒多视图谱聚类(RMSC)[22]是经典多视图聚类算法，基于图学习的多视图聚类(MVGL,2017Transactions)[10]、基于图的自加权多视图聚类(SWMC,2017IJCAI)[44]、自适应加权法(AWP,2018KDD)[45]、稀疏多视图谱聚类(SMVSC,2020Nerocomputing)[15]是最新多视图聚类算法.对于每一种算法，都根据该算法所在的文献在所有的数据集上调参.

3.6 真实数据集的实验分析

本文选取了7个真实数据集来验证CAMC的性能.在每个数据集上，先找出结果最好的参数，然后使用该参数的值重复进行30次实验，记录平均值和均值.结果如表3～9所示，每个数据集上每个评价指标中最好的2个结果加粗显示.

由表3～9可知，在这9种算法中CAMC结果最好，它在BBCSport,3Sources,Citeseer,NGs,100leaves数据集上的评价指标结果基本上都是最优的.特别是在BBCSport数据集上，在NMI,ACC,F,ARI,P等评价指标上，CAMC分别以10.9%,7.7%,11.5%,15.2%,13.4%的优势拉开了与第2名之间的距离.

从结果中，本文有4方面的思考:

1) 总的来说，多视图算法的聚类性能要优于单视图算法.和单视图算法相比，多视图算法能够利用来自不同视图的多种互补信息，从而提高聚类的能力.

2) CAMC在多种类型的图像和文本数据集上均表现优异，这说明CAMC对各类型的数据集具有鲁棒性.

3) CAMC的聚类性能远优于RMSC.这2种方法都是基于Markov链的多视图谱聚类算法，RMSC将各个视图同等对待，而CAMC则考虑了不同视图之间的差异，为各个视图学习最优的权值，这表明为每个视图学习相应的权值能提高聚类的准确性.

4) 在对比算法中，SWMC和AWP均考虑了不同视图的差异性，但它们和CAMC仍然存在差距，这表明了基于Markov链聚类算法的有效性.

4 结 论

本文提出了一种基于Markov链的多视图谱聚类算法，利用了多个视图之间的互补信息，并考虑了各视图在聚类中发挥的不同作用，为各视图学到最优权值.此外，该算法对一致性转移概率矩阵的拉普拉斯矩阵进行了秩约束，以确保拉普拉斯图中连通分量的数目与聚类的数目完全相等.基于ADMM，提出了一种优化策略来对目标函数进行求解.在人造数据集和真实数据集上进行了大量实验，结果表明了CAMC是有效的.将来，我们会基于锚点等策略将CAMC扩展到大规模数据集上.

作者贡献声明：于晓负责研究方案设计和实验实现, 以及论文设计、撰写和修改; 刘慧设计研究方案，指导并参与论文修订; 林毓秀负责数据的整理和校对; 张彩明参与论文修订.

参考文献

[1]Liu Lu, Peng Tao, Zuo Wanli, et al. Clustering-based PU active text classification method[J]. Journal of Software, 2013, 24(11): 2571-2583 (in Chinese)(刘露, 彭涛, 左万利, 等. 一种基于聚类的PU主动文本分类方法[J]. 软件学报, 2013, 24(11): 2571-2583)

[2]Sun Shenshen, Guo Yang, Ren Huizhi, et al. Juxta-vascular nodule segmentation based on the flowing entropy and geodesic distance feature[J]. SCINTIA SINICA Informationis, 2013, 43(9): 1136-1146 (in Chinese)(孙申申, 郭阳, 任会之, 等. 基于流向特征熵和测地线距离的粘连血管型肺结节聚类分割[J]. 中国科学: 信息科学, 2013, 43(9): 1136-1146)

[3]Guo Hongyi, Liu Gongshen, Su Bo, et al. Collaborative filtering recommendation algorithm combining community structure and interest clusters[J]. Journal of Computer Research and Development, 2016, 53(8): 1664-1672 (in Chinese)(郭弘毅, 刘功申, 苏波, 等. 融合社区结构和兴趣聚类的协同过滤推荐算法[J]. 计算机研究与发展, 2016, 53(8): 1664-1672)

[4]Zhang Zhilong, Li Aihua, Li Chuwei. Superpixel segmentation based on clustering by finding density peaks[J]. Chinese Journal of Computers, 2020, 43(1): 1-15 (in Chinese)(张志龙, 李爱华, 李楚为. 基于密度峰值搜索聚类的超像素分割算法[J]. 计算机学报, 2020, 43(1): 1-15)

[5]Hong Min, Jia Caiyan, Li Yafang, et al. Sample-weighted multi-view clustering[J]. Journal of Computer Research and Development, 2019, 56(8): 1677-1685 (in Chinese)(洪敏, 贾彩燕, 李亚芳, 等. 样本加权的多视图聚类算法[J]. 计算机研究与发展, 2019, 56(8): 1677-1685)

[6]Liu Xinwang, Dou Yong, Yin Jianping, et al. Multiple kernel k-means clustering with matrix-induced regularization[C] //Proc of the 30th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI Press, 2016: 1888-1894

[7]Xia Dongxue, Yang Yan, Wang Hao, et al. Late fusion multi-view clustering based on local multikernel learning[J]. Journal of Computer Research and Development, 2020, 57(8): 1627-1638 (in Chinese)(夏冬雪, 杨燕, 王浩, 等. 基于邻域多核学习的后融合多视图聚类算法[J]. 计算机研究与发展, 2020, 57(8): 1627-1638)

[8]Zhang Xiaotong, Zhang Xianchao, Liu Han, et al. Multi-task multi-view clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(12): 3324-3338

[9]Huang Shudong, Kang Zhao, Tsang I W, et al. Auto-weighted multi-view clustering via kernelized graph learning[J]. Pattern Recognition, 2019, 88: 174-184

[10]Zhan Kun, Zhang Changqing, Guan Junpeng, et al. Graph learning for multiview clustering[J]. IEEE Transactions on Cybernetics, 2017, 48(10): 2887-2895

[11]Wang Changdong, Chen Mansheng, Huang Ling, et al. Smoothness regularized multiview subspace clustering with kernel learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020: 1-14

[12]Zheng Qinghai, Zhu Jihua, Li Zhongyu, et al. Feature concatenation multi-view subspace clustering[J]. Neurocomputing, 2020, 379: 89-102

[13]Zhou Tao, Zhang Changqing, Peng Xi, et al. Dual shared specific multiview subspace clustering[J]. IEEE Transactions on Cybernetics, 2019, 50(8): 3517-3530

[14]Yu Xiao, Liu Hui, Wu Yan, et al. Kernel-based low-rank tensorized multiview spectral clustering[J]. International Journal of Intelligent Systems, 2021, 36(2): 757-777

[15]Hu Zhanxuan, Nie Feiping, Chang Wei, et al. Multi-view spectral clustering via sparse graph learning[J]. Neurocomputing, 2020, 384: 1-10

[16]Wang Hao, Yang Yan, Liu Bing, et al. A study of graph-based system for multi-view clustering[J]. Knowledge-Based Systems, 2019, 163: 1009-1019

[17]Zong Linlin, Zhang Xianchao, Liu Xinyue, et al. Weighted multi-view spectral clustering based on spectral perturbation[C] //Proc of the 32nd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI Press, 2018: 4621-4628

[18]Huang H C, Chuang Y Y, Chen C S. Affinity aggregation for spectral clustering[C] //Proc of the 30th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2012: 773-780

[19]Kumar A, Daumé H. A co-training approach for multi-view spectral clustering[C] //Proc of the 28th Int Conf on Machine Learning(ICML11). New York: ACM, 2011: 393-400

[20]Zhou Dengyong, Huang Jiayuan, Schölkopf B. Learning from labeled and unlabeled data on a directed graph[C] //Proc of the 22nd Int Conf on Machine Learning. New York: ACM, 2005: 1036-1043

[21]Zhou Dengyong, Burges C J C. Spectral clustering and transductive learning with multiple views[C] //Proc of the 24th Int Conf on Machine learning. New York: ACM, 2007: 1159-1166

[22]Xia Rongkai, Pan Yan, Du Lei, et al. Robust multi-view spectral clustering via low-rank and sparse decomposition[C] //Proc of the 28th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI Press, 2014: 2149-2155

[23]Wu Jianlong, Lin Zhouchen, Zha Hongbin. Essential tensor learning for multi-view spectral clustering[J]. IEEE Transactions on Image Processing, 2019, 28(12): 5910-5922

[24]Liang Youwei, Huang Dong, Wang Changdong. Consistency meets inconsistency: A unified graph learning framework for multi-view clustering[C] /Proc of the 19th IEEE Int Conf on Data Mining(ICDM). Piscataway, NJ: IEEE, 2019: 1204-1209

[25]Nie Feiping, Li Jing, Li Xuelong. Parameter-free auto-weighted multiple graph learning: A framework for multiview clustering and semi-supervised classification[C] //Proc of the 25th Int Joint Conf on Artificial Intelligence(IJCAI). San Francisco: Margan Kaufmann, 2016: 1881-1887

[26]Fan K. On a theorem of Weyl concerning eigenvalues of linear transformations[J]. Proceedings of the National Academy of Sciences of the United States of America, 1949, 35(11): 652-656

[27]Boyd S, Parikh N, Chu E. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends® in Machine Learning, 2011, 3(1): 1-122

[28]Duchi J, Shalev-Shwartz S, Singer Y, et al. Efficient projections onto the L1-ball for learning in high dimensions[C] //Proc of the 25th Int Conf on Machine Learning. New York: ACM, 2008: 272-279

[29]Lin Zhouchen, Liu Risheng, Su Zhixun. Linearized alternating direction method with adaptive penalty for low-rank representation[C] //Advances in Neural Information Processing Systems 24: Proc of the 25th Annual Conf on Neural Information Processing Systems 2011. New York: Curran Associates, 2011: 612-620

[30]Boyd S, Boyd S P, Vandenberghe L. Convex Optimization[M]. Cambridge, UK: Cambridge University Press, 2004

[31]Zhan Kun, Nie Feiping, Wang Jing, et al. Multiview consensus graph clustering[J]. IEEE Transactions on Image Processing, 2018, 28(3): 1261-1270

[32]Wang Hao, Yang Yan, Liu Bing. GMC: Graph-based multi-view clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 32(6): 1116-1129

[33]Greene D. Dataset: BBCSport[DB/OL]. Ireland: University College Dublin. [2021-06-15]. http://mlg.ucd.ie/datasets/bbc.html

[34]Greene D. 3Sources Dataset[DB/OL]. Ireland: University College Dublin. [2021-06-15]. http://mlg.ucd.ie/datasets/3sources.html

[35]Winn J, Jojic N. Locus: Learning object classes with unsupervised segmentation[C] //Proc of the 10th IEEE Int Conf on Computer Vision(ICCV’05). Piscataway, NJ: IEEE, 2005: 756-763

[36]Rossi R, Ahmed N. The network data repository with interactive graph analytics and visualization[C] //Proc of the 29th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI Press, 2015: 4292-4293

[37]Van Breukelen M, Duin R P W, Tax D M J, et al. Handwritten digit recognition by combined classifiers[J]. Kybernetika, 1998, 34(4): 381-386

[38]Bisson G, Grimal C. An architecture to efficiently learn co-similarities from multi-view datasets[C] //Proc of the 19th Int Conf on Neural Information Processing. Berlin: Springer, 2012: 184-193

[39]Mallah C, Cope J, Orwell J. Plant leaf classification using probabilistic integration of shape, texture and margin features[J]. Signal Processing, Pattern Recognition and Applications, 2013, 5(1): 45-54

[40]Van derMaaten L, Hinton G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(11): 2579-2605

[41]Ng A Y, Jordan M I, Weiss Y. On spectral clustering: Analysis and an algorithm[C] //Advances in Neural Information Processing Systems 14: Proc of the 15th Annual Conf on Neural Information Processing Systems 2002. New York: Curran Associates, 2002: 849-856

[42]Liu Guangcan, Lin Zhouchen, Yan Shuicheng, et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 35(1): 171-184

[43]Kumar A, Rai P,Daume H. Co-regularized multi-view spectral clustering[C] //Advances in Neural Information Processing Systems 24: Proc of the 25th Annual Conf on Neural Information Processing Systems 2011. New York: Curran Associates, 2011: 1413-1421

[44]Nie Feiping, Li Jing, Li Xuelong. Self-weighted multiview clustering with multiple graphs[C] //Proc of the 26th Int Joint Conf on Artificial Intelligence(IJCAI). San Francisco, CA: Margan Kaufmann, 2017: 2564-2570

[45]Nie Feiping, Tian Lai, Li Xuelong. Multiview clustering via adaptively weighted procrustes[C] //Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2018: 2022-2030

Consensus Guided Auto-Weighted Multi-View Clustering

Yu Xiao1,2, Liu Hui1,2, Lin Yuxiu1,2, and Zhang Caiming2,3

1(School of Computer Science and Technology, Shandong University of Finance and Economics, Jinan 250014) 2(Shandong Key Laboratory of Digital Media Technology (Shandong University of Finance and Economics), Jinan 250014) 3(School of Software, Shandong University, Jinan 250014)

Abstract As it becomes increasingly easier to obtain multi-modal or multi-view data, multi-view clustering has gained much more attention recently. However, many methods learn the affinity matrix from the original data and may lead to unsatisfying results because of the noise in the raw dataset. Besides, some methods neglect the diversity of roles played by different views and take them equally. In this paper, we propose a novel Markov chain algorithm named consensus guided auto-weighted multi-view clustering (CAMC) to tackle these problems. A transition probability matrix is constructed for each view to learn the affinity matrix indirectly to reduce the effects of redundancies and noise in the original data. The consensus transition probability matrix is obtained in an auto-weighted way, in which the optimal weight for each view is gained automatically. Besides, a constrained Laplacian rank is utilized on the consensus transition probability to ensure that the number of the connected components in the Laplacian graph is exactly equal to that of the clusters. Moreover, an optimization strategy based on alternating direction method of multiplier (ADMM) is proposed to solve the problem. The effectiveness of the proposed algorithm is verified on a toy dataset. Extensive experiments on seven real-world datasets with different types show that CAMC outperforms the other eight benchmark algorithms in terms of clustering.

Key words multi-view; clustering; auto-weighted; spectral clustering; Markov chain

收稿日期：2021-02-22；修回日期：2021-08-18

基金项目：国家自然科学基金项目(62072274);山东省科技成果转移转化项目(2021LYXZ021)

This work was supported by the National Natural Science Foundation of China (62072274) and Shandong Provincial Transfer and Transformation Project of Scientific and Technological Achievements (2021LYXZ021).

通信作者：刘慧(liuh_lh@sdufe.edu.cn)

(20065894@sdufe.edu.cn)

中图法分类号 TP181

Yu Xiao, born in 1981. PhD, lecturer. Member of CCF. Her main research interests include machine learning and data mining.

于 晓，1981年生.博士，讲师，CCF会员.主要研究方向为机器学习和数据挖掘.

Liu Hui, born in 1978. PhD, professor and PhD supervisor. Member of CCF. Her main research interests include medical image processing, data mining, and machine learning.

刘 慧，1978年生.博士，教授，博士生导师，CCF会员.主要研究方向为医学图像处理、数据挖掘与机器学习.

Lin Yuxiu, born in 1996. PhD candidate. Her main research interests include image processing and machine learning.

林毓秀，1996年生.博士研究士.主要研究方向为图像处理和机器学习.

Zhang Caiming, born in 1955. PhD, professor and PhD supervisor. Senior member of CCF. His main research interests include data mining, computer graphics, information visualization and medical image processing.

张彩明，1955年生.博士，教授，博士生导师，CCF高级会员.主要研究方向为数据挖掘、计算机图形学、信息可视化及医学图像处理.