基于稀疏一致图分解的鲁棒多视图聚类算法

doi:10.3785/j.issn.1008-9497.2023.05.008

浙江大学学报（理学版）

2023, Vol. 50

Issue (5): 569-579 DOI: 10.3785/j.issn.1008-9497.2023.05.008

数学与计算机科学

基于稀疏一致图分解的鲁棒多视图聚类算法

耿莉(

),王长鹏(

)

长安大学理学院，陕西西安 710064

Robust multi-view clustering algorithm based on sparse consensus graph decomposition

Li GENG(

),Changpeng WANG(

)

School of Science，Chang'an University，Xi'an 710064，China

全文: PDF(1924 KB)

HTML( 2 )

摘要：

由于数据形式日益复杂，陆续涌现了大量多视图聚类算法。但现有方法存在计算复杂度较高、需要额外的后续处理步骤、构造的相似图非最优等缺点。基于此，首先提出一种基于稀疏一致图分解的单视图聚类算法，然后将其扩展为多视图聚类算法，考虑不同视图对最终结果的贡献不同，对每个视图分配适当的权重，同时利用 $L 2.1$ 范数，得到性能更优的一致图，在一致图基础上学习非负表示矩阵，经交替迭代得到聚类结果。最后在多个数据集上进行比较实验，验证了该算法的有效性。

关键词： 多视图聚类;

L 2,1

范数')" href="#">

L 2,1

范数; 一致图分解

Abstract:

Due to the increasing complexity of data form, multi-view clustering algorithms emerge one after another. The main disadvantages of existing methods include: the computational complexity of these methods is high; the final clustering involves additional processing steps; the similarity graph constructed may not be the optimal graph. In order to solve the above problems, a clustering algorithm based on sparse consensus graph decomposition is proposed. The algorithm is first tested on single-view data, and then extends from single-view data to multi-view data. The algorithm takes into account different contributions of different views to the final result by giving each view appropriate weight, at the same time, makes use of the $L 2,1$ norm to obtain the consensus graph with better performance, learns the non-negative representation matrix on the basis of the consensus graph, and reveals the cluster result directly after alternation iteration. Finally, an update iterative algorithm is proposed and tested on a large number of data sets to verify the effectiveness of the algorithm.

Key words: multi-view clustering

L 2,1

norm')" href="#">

L 2,1

norm consensus graph decomposition

收稿日期: 2022-04-18 出版日期: 2023-09-16

CLC:

TP 181

基金资助: 国家自然科学基金青年项目(12001057);长安大学中央高校基本科研业务费专项资金资助项目(300102122101);陕西省重点产业创新链项目(2020ZDLGY09-09);陕西省自然科学基础研究计划项目(2020JQ-346)

通讯作者: 王长鹏 E-mail: 1069159798@qq.com;cpwang@chd.edu.cn

作者简介: 耿莉（1998—），ORCID：https：//orcid.org/0000-0002-8051-5236，女，硕士研究生，主要从事机器学习研究，E-mail：1069159798@qq.com.

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	耿莉
	王长鹏

引用本文:

耿莉,王长鹏. 基于稀疏一致图分解的鲁棒多视图聚类算法[J]. 浙江大学学报（理学版）, 2023, 50(5): 569-579.

Li GENG,Changpeng WANG. Robust multi-view clustering algorithm based on sparse consensus graph decomposition. Journal of Zhejiang University (Science Edition), 2023, 50(5): 569-579.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2023.05.008 或 https://www.zjujournals.com/sci/CN/Y2023/V50/I5/569

符号	说明	符号	说明
$G v$	第 $v$ 个视图的图矩阵	$I$	单位矩阵
$S$	一致图相似矩阵	$n$	数据样本数
$D$	度矩阵	$n v$	视图总数
$L$	拉普拉斯矩阵	$d v$	第 $v$ 个视图的特征维数
$P$	非负矩阵	$c$	聚类数
$Q$	正交矩阵	$w v$	第 $v$ 个视图的权重
E	辅助变量

表1 符号说明

图1 SCGFm流程

表2 单视图数据集描述

表3 单视图聚类性能比较

图2 SCGFs模型对参数λ的敏感性分析

数据集	样本数	视图数	聚类数	第v个视图的特征维数d_v
数据集	样本数	视图数	聚类数	$d 1$	$d 2$	$d 3$	$d 4$	$d 5$	$d 6$
BBCSport	544	2	5	3 183	3 203
100leaves	1 600	3	100	64	64	64
ORL	400	3	40	4 096	3 304	6 750
Yale	165	3	15	4 096	3 304	6 750
MSRCV1	210	6	7	1 302	48	512	100	256	210

表4 多视图数据集描述

表5 在BBCSport数据集上的聚类性能比较

表6 不同算法在100leaves数据集上的聚类性能比较

表7 不同算法在ORL数据集上的聚类性能比较

表8 不同算法在Yale数据集上的聚类性能比较

表9 不同算法在MSRCV1数据集上的聚类性能比较

图3 SCGFm模型对参数λ和μ的敏感性分析

图4 SCGFm模型在多视图数据集上的收敛曲线

1	林宙辰，李欢，方聪. 机器学习中的加速一阶优化算法［M］. 北京：机械工业出版社， 2021. doi:10.1007/978-981-15-2910-8 LIN Z C， LI H， FANG C. Accelerated Optimization for Machine Learning First-Order Algorithms［M］. Beijing： China Machine Press， 2021. doi:10.1007/978-981-15-2910-8 doi: 10.1007/978-981-15-2910-8
2	周志华. 机器学习［M］. 北京：清华大学出版社， 2016. ZHOU Z H. Machine Learning［M］. Beijing： Tsinghua University Press， 2016.
3	NIE F P， LI J， LI X L. Self-weighted multiview clustering with multiple graphs［C］// Twenty-Sixth International Joint Conference on Artificial Intelligence. Melbourne： AAAI Press， 2017： 2564-2570. doi:10.24963/ijcai.2017/357 doi: 10.24963/ijcai.2017/357
4	WANG H， YANG Y， LIU B， et al. A study of graph-based system for multi-view clustering［J］. Knowledge-Based Systems， 2019， 163： 1009-1019. DOI：10.1016/j.knosys.2018.10.022 doi: 10.1016/j.knosys.2018.10.022
5	ZHAN K， NIU C X， CHEN C L， et al. Graph structure fusion for multiview clustering［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 31（10）： 1984-1993. DOI：10.1109/TKDE. 2018.2872061 doi: 10.1109/TKDE. 2018.2872061
6	ZHAN K， NIE F P， WANG J， et al. Multiview consensus graph clustering［J］. IEEE Transactions on Image Processing， 2018， 28（3）： 1261-1270. DOI：10.1109/TIP.2018.2877335 doi: 10.1109/TIP.2018.2877335
7	HUANG S D， TSANG I W， XU Z L， et al. Measuring diversity in graph learning： A unified framework for structured multi-view clustering［J］. IEEE Transactions on Knowledge and Data Engineering， 2022， 34（12）： 5869-5883. DOI：10. 1109/tkde.2021.3068461 doi: 10. 1109/tkde.2021.3068461
8	WU D Y， NIE F P， DONG X， et al. Parameter-free consensus embedding learning for multiview graph-based clustering［J］. IEEE Transactions on Neural Networks and Learning Systems， 2022， 33（12）： 7944-7950. DOI：10.1109/TNNLS.2021.3087162 doi: 10.1109/TNNLS.2021.3087162
9	MA X L， YAN X M， LIU J F， et al. Simultaneous multi-graph learning and clustering for multiview data［J］. Information Sciences， 2022， 593： 472-487. DOI：10.1016/j.ins.2022.02.018 doi: 10.1016/j.ins.2022.02.018
10	WANG Q， LIU R， CHEN M L， et al. Robust rank-constrained sparse learning： A graph-based framework for single view and multiview clustering［J］. IEEE Transactions on Cybernetics， 2022， 52（10）： 10228-10239. DOI：10.1109/TCYB.2021.3067137 doi: 10.1109/TCYB.2021.3067137
11	HUANG S D， XU Z L， KANG Z， et al. Regularized nonnegative matrix factorization with adaptive local structure learning［J］. Neurocomputing， 2020， 382： 196-209. DOI：10.1016/j.neucom.2019.11.070 doi: 10.1016/j.neucom.2019.11.070
12	WANG J， TIAN F， YU H C， et al. Diverse non-negative matrix factorization for multiview data representation［J］. IEEE Transactions on Cybernetics， 2017， 48（9）： 2620-2632. DOI：10.1109/tcyb.2017. 2747400 doi: 10.1109/tcyb.2017. 2747400
13	LIANG N Y， YANG Z Y， LI Z N， et al. Multi-view clustering by non-negative matrix factorization with co-orthogonal constraints［J］. Knowledge-Based Systems， 2020， 194： 105582. DOI：10.1016/j.knosys.2020.105582 doi: 10.1016/j.knosys.2020.105582
14	YANG Z Y， LIANG N Y， YAN W， et al. Uniform distribution non-negative matrix factorization for multiview clustering［J］. IEEE Transactions on Cybernetics， 2020， 51（6）： 3249-3262. DOI：10. 1109/tcyb.2020.2984552 doi: 10. 1109/tcyb.2020.2984552
15	ZHAO L， YANG T， ZHANG J， et al. Co-learning non-negative correlated and uncorrelated features for multi-view data［J］. IEEE Transactions on Neural Networks and Learning Systems， 2020， 32（4）： 1486-1496. DOI：10.1109/tnnls.2020.2984810 doi: 10.1109/tnnls.2020.2984810
16	SHI S J， NIE F P， WANG R， et al. Multi-view clustering via nonnegative and orthogonal graph reconstruction［J］. IEEE Transactions on Neural Networks and Learning Systems， 2023， 34（1）： 201-214. DOI：10.1109/TNNLS.2021.3093297 doi: 10.1109/TNNLS.2021.3093297
17	POWELL M J D. A method for nonlinear constraints in minimization problems［J］. Optimization， 1969： 283-298.
18	HU Z X， NIE F P， WANG R， et al. Multi-view spectral clustering via integrating nonnegative embedding and spectral embedding［J］. Information Fusion， 2020， 55： 251-259. DOI：10.1016/j.inffus. 2019.09.005 doi: 10.1016/j.inffus. 2019.09.005
19	NIE F P， WANG X Q， JORDAN M， et al. The constrained Laplacian rank algorithm for graph-based clustering［C］// Proceedings of the 30th AAAI Conference on Artificial Intelligence. Phoenix， Arizona： AAAI Press， 2016： 1969-1976. doi:10.1609/aaai.v30i1.10302 doi: 10.1609/aaai.v30i1.10302
20	NIE F P， HUANG H， CAI X， et al. Efficient and robust feature selection via joint ℓ2， 1-norms minimization［C］// Proceedings of the 23th International Conference on Neural Information Processing Systems， New York： Curran Associates Inc， 2010：1813-1821. DOI：10.5555/2997046. 2997098 doi: 10.5555/2997046. 2997098
21	YUAN M， LIN Y. Model selection and estimation in regression with grouped variables［J］. Journal of the Royal Statistical Society： Series B （Statistical Methodology）， 2006， 68（1）： 49-67. DOI：10.1111/j.1467-9868.2005.00532.x doi: 10.1111/j.1467-9868.2005.00532.x
22	LI Y Q， NIE F P， HUANG H， et al. Large-scale multi-view spectral clustering via bipartite graph［C］// Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Austin： AAAI Press， 2015： 2750-2756. doi:10.1609/aaai.v29i1.9598 doi: 10.1609/aaai.v29i1.9598
23	WANG Q， CHEN M L， NIE F P， et al. Detecting coherent groups in crowd scenes by multiview clustering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2018， 42（1）： 46-58. DOI：10.1109/tpami.2018.2875002 doi: 10.1109/tpami.2018.2875002
24	HUANG J， NIE F P， HUANG H. A new simplex sparse learning model to measure data similarity for clustering［C］// Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Buenos Aires： AAAI Press， 2015： 3569-3575.
25	ZHU H B， ZHOU M C. Efficient role transfer based on Kuhn-Munkres algorithm［J］. IEEE Transactions on Systems， Man， and Cybernetics-Part A： Systems and Humans， 2011， 42（2）： 491-496. DOI：10.1109/TSMCA.2011.2159587 doi: 10.1109/TSMCA.2011.2159587
26	SEUNG D， LEE L. Algorithms for non-negative matrix factorization［J］. Advances in Neural Information Processing Systems， 2001， 13： 556-562.
27	ABDI H， WILLIAMS L J. Principal component analysis［J］. Wiley Interdisciplinary Reviews： Computational Statistics， 2010， 2（4）： 433-459. doi:10.1002/wics.101 doi: 10.1002/wics.101
28	GU Q Q， ZHOU J. Local learning regularized nonnegative matrix factorization［C］// Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers Inc， 2009： 1046-1051.
29	CAI D， HE X F， HAN J W， et al. Graph regularized nonnegative matrix factorization for data representation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（8）： 1548-1560. DOI：10.1109/TPAMI.2010.231 doi: 10.1109/TPAMI.2010.231
30	HUANG J， NIE F P， HUANG H， et al. Robust manifold nonnegative matrix factorization［J］. ACM Transactions on Knowledge Discovery from Data， 2014， 8（3）： 1-21. DOI：10.1145/2601434 doi: 10.1145/2601434
31	PEI X B， CHEN C B， GONG W H. Concept factorization with adaptive neighbors for document clustering［J］. IEEE Transactions on Neural Networks and Learning Systems， 2016， 29（2）： 343-352. DOI：10.1109/TNNLS.2016.2626311 doi: 10.1109/TNNLS.2016.2626311
32	KANG Z， SHI G X， HUANG S D， et al. Multi-graph fusion for multi-view spectral clustering［J］. Knowledge-Based Systems， 2020， 189： 105102. DOI：10.1016/j.knosys.2019.105102 doi: 10.1016/j.knosys.2019.105102

[1]	胡东滨, 冯婧瑜, 杨艺, 易国栋. 考虑处置效果的苯系物泄露应急方案生成方法[J]. 浙江大学学报（理学版）, 2022, 49(4): 457-466.
[2]	刘华玲, 恽文婧, 林蓓, 丁宇杰. 网络广告点击率预估的特征学习及技术研究进展[J]. 浙江大学学报（理学版）, 2019, 46(5): 565-573.

Viewed

Full text

Abstract

Cited

Shared

Discussed