基于上界单纯形投影图张量学习的多核聚类算法

doi:10.11772/j.issn.1001-9081.2021061393

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (12): 3468-3474.DOI: 10.11772/j.issn.1001-9081.2021061393

• 第十八届中国机器学习会议(CCML 2021) • 上一篇下一篇

基于上界单纯形投影图张量学习的多核聚类算法

雷皓云¹^,², 任珍文¹^,³(), 汪彦龙⁴, 薛爽¹, 李浩然¹

^1.西南科技大学国防科技学院，四川绵阳 621010
^2.电子科技大学信息与通信工程学院，成都 611731
^3.计算机软件新技术国家重点实验室（南京大学），南京 210023
^4.浙江传媒学院媒体工程学院，浙江杭州 310018

收稿日期:2021-05-12 修回日期:2021-08-30 接受日期:2021-08-31 发布日期:2021-12-28 出版日期:2021-12-10
通讯作者: 任珍文
作者简介:雷皓云（1999—），男，四川成都人，硕士研究生，CCF会员，主要研究方向：多核聚类、雷达成像技术
汪彦龙（1971—），男，黑龙江黑河人，硕士，主要研究方向：医学图像处理
薛爽（2000—），女，山西运城人，主要研究方向：多核聚类、多视图聚类
李浩然（1997—），男，河北石家庄人，硕士研究生，主要研究方向：多核聚类、多视图聚类。
基金资助:
四川省科技厅应用基础研究项目(2021YJ0083);国家自然科学基金资助项目(62106209);南京大学计算机软件新技术国家重点实验室资助项目(KFKT2021B23);浙江省基础公益研究计划项目(LGF21F020003);重庆自然科学基金资助项目(cstc2020jcyj-msxmX0473);浙江省影视媒体技术研究重点实验室开放基金课题(2020E10015)

Multiple kernel clustering algorithm based on capped simplex projection graph tensor learning

Haoyun LEI¹^,², Zhenwen REN¹^,³(), Yanlong WANG⁴, Shuang XUE¹, Haoran LI¹

^1.School of National Defense Science and Technology，Southwest University of Science and Technology，Mianyang Sichuan 621010，China
^2.School of Information and Communication Engineering，University of Electronic Science and Technology of China，Chengdu Sichuan 611731，China
^3.State Key Laboratory for Novel Software Technology （Nanjing University），Nanjing Jiangsu 210023，China
^4.School of Media Engineering，Communication University of Zhejiang，Hangzhou Zhejiang 310018，China

Received:2021-05-12 Revised:2021-08-30 Accepted:2021-08-31 Online:2021-12-28 Published:2021-12-10
Contact: Zhenwen REN
About author:LEI Haoyun， born in 1999， M. S. candidate. His research interests include multiple kernel clustering， radar imaging technology.
WANG Yanlong， born in 1971. M. S. His research interests include medical image processing.
XUE Shuang， born in 2000. Her research interests include multiple kernel clustering， multi-view clustering.
LI Haoran， born in 1997， M. S. candidate. His research interests include multiple kernel clustering， multi-view clustering.
Supported by:
the Application Foundation Research Project of Science and Technology Department of Sichuan Province(2021YJ0083);the National Natural Science Foundation of China(62106209);the State Key Lab for Novel Software Technology Project at Nanjing University(KFKT2021B23);the Basic Public Welfare Research Program of Zhejiang Province(LGF21F020003);the Natural Science Foundation of Chongqing(cstc2020jcyj-msxmX0473);the Open Fund Project of Key Lab of Film and TV Media Technology of Zhejiang Province(2020E10015)

摘要/Abstract

摘要：

近年来，多核图聚类（MKGC）受到了广泛的关注，这得益于多核学习能有效地避免核函数与核参数的选择，而图聚类能充分挖掘样本间的复杂结构信息。然而现有的MKGC方法存在着如下问题：图学习技术使得模型复杂化，图拉普拉斯矩阵的高秩特性使其难以保证学到的关系图包含精确的c个连通分量（块对角性质），以及大部分方法忽略了候选关系图间的高阶结构信息，使得多核信息难以被充分利用。针对以上问题，提出了一种新的MKGC方法。首先，提出一种新的上界单纯形投影图学习方法，直接将核矩阵投影到图单纯形上，降低了计算复杂度；同时，引入一种新的块对角约束，使学到的关系图能保持精确的块对角属性；此外，在上界单纯形投影空间中引入低秩张量学习来充分挖掘多个候选关系图的高阶结构信息。在多个数据集上与现有的MKGC方法相比，所提出方法计算量小、稳定性高，在聚类精度（ACC）和标准互信息（NMI）指标上具有较大的优势。

关键词: 多核图聚类, 上界单纯形, 张量学习, 块对角性质, 高阶结构信息

Abstract:

Because multiple kernel learning can avoid selection of kernel functions and parameters effectively， and graph clustering can fully mine complex structural information between samples， Multiple Kernel Graph Clustering （MKGC） has received widespread attention in recent years. However， the existing MKGC methods suffer from the following problems： graph learning technique complicates the model， the high rank of graph Laplacian matrix cannot ensure the learned affinity graph to contain accurate c connected components （block diagonal property）， and most of the methods ignore the high-order structural information among the candidate affinity graphs， making it difficult to fully utilize the multiple kernel information. To tackle these problems， a novel MKGC method was proposed. First， a new graph learning method based on capped simplex projection was proposed to directly project the kernel matrices onto graph simplex， which reduced the computational complexity. Meanwhile， a new block diagonal constraint was introduced to keep the accurate block diagonal property of the learned affinity graphs. Moreover， the low-rank tensor learning was introduced in capped simplex projection space to fully mine the high-order structural information of multiple candidate affinity graphs. Compared with the existing MKGC methods on multiple datasets， the proposed method has less computational cost and high stability， and has great advantages in Accuracy （ACC） and Normalized Mutual Information （NMI）.

Key words: Multiple Kernel Graph Clustering (MKGC), capped simplex, tensor learning, block diagonal property, high-order structural information

中图分类号:

TP391

雷皓云, 任珍文, 汪彦龙, 薛爽, 李浩然. 基于上界单纯形投影图张量学习的多核聚类算法[J]. 计算机应用, 2021, 41(12): 3468-3474.

Haoyun LEI, Zenwen REN, Yanlong WANG, Shuang XUE, Haoran LI. Multiple kernel clustering algorithm based on capped simplex projection graph tensor learning[J]. Journal of Computer Applications, 2021, 41(12): 3468-3474.

图/表 8

参考文献 23

1	ELHAMIFAR E， VIDAL R. Sparse subspace clustering： algorithm， theory， and applications［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（11）： 2765-2781. 10.1109/tpami.2013.57
2	LI C G， YOU C， VIDAL R. Structured sparse subspace clustering： a joint affinity learning and subspace clustering framework［J］. IEEE Transactions on Image Processing， 2017， 26（6）： 2988-3001. 10.1109/tip.2017.2691557
3	LI X F， REN Z W， LEI H Y， et al. Multiple kernel clustering with pure graph learning scheme［J］. Neurocomputing， 2020， 424： 215-225. 10.1016/j.neucom.2020.10.052
4	LU C Y， FENG J S， LIN Z C， et al. Subspace clustering by block diagonal representation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2019， 41（2）： 487-501. 10.1109/tpami.2018.2794348
5	ZHANG C Q， FU H Z， LIU S， et al. Low-rank tensor constrained multiview subspace clustering［C］// Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway： IEEE， 2015： 1582-1590. 10.1109/iccv.2015.185
6	REN Z W， LEI H Y， SUN Q S， et al. Simultaneous learning coefficient matrix and affinity graph for multiple kernel clustering［J］. Information Sciences， 2021， 547： 289-306. 10.1016/j.ins.2020.08.056
7	REN Z W， SUN Q S. Simultaneous global and local graph structure preserving for multiple kernel clustering［J］. IEEE Transactions on Neural Networks and Learning Systems， 2021， 32（5）： 1839-1851. 10.1109/tnnls.2020.2991366
8	ZHOU S H， LIU X W， LI M M， et al. Multiple kernel clustering with neighbor-kernel subspace segmentation［J］. IEEE Transactions on Neural Networks and Learning Systems， 2020， 31（4）： 1351-1362. 10.1109/tnnls.2019.2919900
9	REN Z W， YANG S X， SUN Q S， et al. Consensus affinity graph learning for multiple kernel clustering［J］. IEEE Transactions on Cybernetics， 2021， 51（6）： 3273-3284. 10.1109/tcyb.2020.3000947
10	REN Z W， MUKHERJEE M， LLORET J， et al. Multiple kernel driven clustering with locally consistent and selfish graph in Industrial IoT［J］. IEEE Transactions on Industrial Informatics， 2021， 17（4）： 2956-2963. 10.1109/tii.2020.3010357
11	WU J L， XIE X X， NIE L Q， et al. Unified graph and low-rank tensor learning for multi-view clustering［C］// Proceedings of the 34th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2020： 6388-6395. 10.1609/aaai.v34i04.6109
12	NIE F P， WANG X Q， JORDAN M I， et al. The constrained Laplacian rank algorithm for graph-based clustering［C］// Proceedings of the 30th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2016： 1969-1976.
13	ZHOU P， LU C Y， FENG J S， et al. Tensor low-rank representation for data recovery and clustering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2021， 43（5）： 1718-1732. 10.1109/tpami.2019.2954874
14	NIE F P， WANG X Q， HUANG H. Clustering and projected clustering with adaptive neighbors［C］// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 977-986. 10.1145/2623330.2623726
15	DU L， ZHOU P， SHI L， et al. Robust multiple kernel k-means using l_2，1-norm［C］// Proceedings of the 24th International Joint Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2015： 3476-3482.
16	HUANG H C， CHUANG Y Y， CHEN C S. Multiple kernel fuzzy clustering［J］. IEEE Transactions on Fuzzy Systems， 2012， 20（1）： 120-134. 10.1109/tfuzz.2011.2170175
17	KANG Z， WEN L J， CHEN W Y， et al. Low-rank kernel learning for graph-based clustering［J］. Knowledge-Based Systems， 2019， 163：510-517. 10.1016/j.knosys.2018.09.009
18	KANG Z， PENG C， CHENG Q， et al. Unified spectral clustering with optimal graph［C］// Proceedings of the 32nd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2018： 3366-3373.
19	KANG Z， LU X， YI J Fet al. Self-weighted multiple kernel learning for graph-based clustering and semi-supervised classification［J］. Proceedings of the 27th International Joint Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2018： 2312-2318. 10.24963/ijcai.2018/320
20	KANG Z， XU Z， LU X ， et al. Self-weighted multiple kernel learning for graph-based clustering and semi-supervised classification［C］// Proceedings of the 27th International Joint Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2018： 2312-2318. 10.24963/ijcai.2018/320
21	REN Z W， SUN Q S， WEI D. Multiple kernel clustering with kernel k-means coupled graph tensor learning［C］// Proceedings of the 35th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2021： 9411-9418.
22	章永来，周耀鉴. 聚类算法综述［J］. 计算机应用， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
	ZHANG Y L， ZHOU Y J. Review of clustering algorithms［J］. Journal of Computer Application， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
23	李杏峰，黄玉清，任珍文. 联合低秩稀疏的多核子空间聚类算法［J］. 计算机应用， 2020， 40（6）： 1648-1653.
	LI X F， HUANG Y Q， REN Z W. Joint low-rank and sparse multiple kernel subspace clustering algorithm［J］. Journal of Computer Applications， 2020， 40（6）： 1648-1653.

数据集	类型	类数	样本数	特征数
Yale	人脸图像	15	165	1 024
Jaffe	人脸图像	10	213	676
AR	人脸图像	120	840	768
ORL	人脸图像	40	400	1 024
COIL20	物体图像	20	1 440	1 024
BA	手写数字图像	36	1 404	320

数据集	类型	类数	样本数	特征数
Yale	人脸图像	15	165	1 024
Jaffe	人脸图像	10	213	676
AR	人脸图像	120	840	768
ORL	人脸图像	40	400	1 024
COIL20	物体图像	20	1 440	1 024
BA	手写数字图像	36	1 404	320

数据集	度量指标	MKKM		RMKKM		LKGr		SCMK		SMKL		SPMKC-E		CSGTMKC
数据集	度量指标	数值	标准差	数值	标准差	数值	标准差	数值	标准差	数值	标准差	数值	标准差	数值	标准差
Yale	ACC	0.457	0.041	0.521	0.034	0.540	0.030	0.582	0.025	0.582	0.017	0.658	0.000	0.830	0.012
Yale	NMI	0.501	0.036	0.556	0.025	0.566	0.025	0.576	0.012	0.614	0.015	0.650	0.000	0.838	0.011
Jaffe	ACC	0.746	0.069	0.871	0.053	0.861	0.052	0.869	0.022	0.967	0.000	1.000	0.000	1.000	0.000
Jaffe	NMI	0.798	0.058	0.893	0.041	0.869	0.031	0.868	0.021	0.951	0.000	1.000	0.000	1.000	0.000
ORL	ACC	0.475	0.023	0.556	0.024	0.616	0.016	0.656	0.015	0.573	0.032	0.745	0.000	0.970	0.015
ORL	NMI	0.689	0.016	0.748	0.018	0.794	0.008	0.808	0.008	0.733	0.027	0.855	0.000	0.985	0.009
AR	ACC	0.286	0.014	0.344	0.012	0.314	0.015	0.544	0.024	0.263	0.009	0.750	0.000	0.902	0.008
AR	NMI	0.592	0.014	0.655	0.015	0.648	0.007	0.775	0.009	0.568	0.014	0.889	0.000	0.971	0.009
COIL20	ACC	0.548	0.058	0.667	0.028	0.618	0.051	0.591	0.028	0.487	0.031	0.842	0.000	0.989	0.007
COIL20	NMI	0.707	0.033	0.773	0.017	0.766	0.023	0.726	0.011	0.628	0.018	0.909	0.000	0.988	0.006
BA	ACC	0.405	0.019	0.434	0.018	0.444	0.018	0.384	0.014	0.246	0.012	0.508	0.000	0.949	0.024
BA	NMI	0.569	0.008	0.585	0.011	0.604	0.009	0.544	0.012	0.486	0.011	0.632	0.000	0.966	0.019

数据集	度量指标	MKKM		RMKKM		LKGr		SCMK		SMKL		SPMKC-E		CSGTMKC
数据集	度量指标	数值	标准差	数值	标准差	数值	标准差	数值	标准差	数值	标准差	数值	标准差	数值	标准差
Yale	ACC	0.457	0.041	0.521	0.034	0.540	0.030	0.582	0.025	0.582	0.017	0.658	0.000	0.830	0.012
Yale	NMI	0.501	0.036	0.556	0.025	0.566	0.025	0.576	0.012	0.614	0.015	0.650	0.000	0.838	0.011
Jaffe	ACC	0.746	0.069	0.871	0.053	0.861	0.052	0.869	0.022	0.967	0.000	1.000	0.000	1.000	0.000
Jaffe	NMI	0.798	0.058	0.893	0.041	0.869	0.031	0.868	0.021	0.951	0.000	1.000	0.000	1.000	0.000
ORL	ACC	0.475	0.023	0.556	0.024	0.616	0.016	0.656	0.015	0.573	0.032	0.745	0.000	0.970	0.015
ORL	NMI	0.689	0.016	0.748	0.018	0.794	0.008	0.808	0.008	0.733	0.027	0.855	0.000	0.985	0.009
AR	ACC	0.286	0.014	0.344	0.012	0.314	0.015	0.544	0.024	0.263	0.009	0.750	0.000	0.902	0.008
AR	NMI	0.592	0.014	0.655	0.015	0.648	0.007	0.775	0.009	0.568	0.014	0.889	0.000	0.971	0.009
COIL20	ACC	0.548	0.058	0.667	0.028	0.618	0.051	0.591	0.028	0.487	0.031	0.842	0.000	0.989	0.007
COIL20	NMI	0.707	0.033	0.773	0.017	0.766	0.023	0.726	0.011	0.628	0.018	0.909	0.000	0.988	0.006
BA	ACC	0.405	0.019	0.434	0.018	0.444	0.018	0.384	0.014	0.246	0.012	0.508	0.000	0.949	0.024
BA	NMI	0.569	0.008	0.585	0.011	0.604	0.009	0.544	0.012	0.486	0.011	0.632	0.000	0.966	0.019

多核图聚类方法	Yale	ORL
MKKM	0.105	0.327
RMKKM	0.870	3.634
LKGr	1.020	7.432
SCMK	4.591	42.048
SMKL	1.439	12.852
SPMKC-E	0.604	2.917
CSGTMKC	0.515	1.785

基于上界单纯形投影图张量学习的多核聚类算法

Multiple kernel clustering algorithm based on capped simplex projection graph tensor learning

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 15

编辑推荐

Metrics

[1]	李昆鹏张鹏程上官宏王燕玲杨婕桂志国. 基于卷积神经网络的时频域CT重建算法 [J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	杜汉, 龙显忠, 李云. 基于图学习正则判别非负矩阵分解的人脸识别[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3455-3461.
[3]	王梅, 许传海, 刘勇. 基于神经正切核的多核学习方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3462-3467.
[4]	李子龙, 周勇, 鲍蓉, 王洪栋. 优化三元组损失的深度距离度量学习方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3480-3484.
[5]	李华, 卢桂馥, 余沁茹. 基于干净数据的流形正则化非负矩阵分解[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3492-3498.
[6]	骆锦潍, 刘杜钢, 潘微科, 明仲. 基于改进的倾向得分估计的无偏推荐模型[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3508-3514.
[7]	汪翠, 张亚飞, 郭军军, 高盛祥, 余正涛. 融合句法信息的无触发词事件检测方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3534-3539.
[8]	薛海涛, 王莉, 杨延杰, 廉飚. 基于用户传播网络与消息内容融合的谣言检测模型[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3540-3545.
[9]	毕蓓, 潘慧瑶, 陈峰, 隋京言, 高扬, 王耀君. 基于异构图注意力网络的微博谣言监测模型[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3546-3550.
[10]	俸亚特, 文益民. 基于改进Mask R-CNN的越南场景文字检测[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3551-3557.
[11]	温静, 李强. 基于时空上下文信息增强的目标跟踪算法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3565-3570.
[12]	李小雨, 房体育, 夏英杰, 李金屏. 基于图割精细化和可微分聚类的无监督显著性目标检测[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3571-3577.
[13]	龚云鹏, 曾智勇, 叶锋. 基于灰度域特征增强的行人重识别方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3590-3595.
[14]	刘乾, 王洪元, 曹亮, 孙博言, 肖宇, 张继. 基于联合损失胶囊网络的换衣行人重识别[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3596-3601.
[15]	徐婉晴, 王保栋, 黄艺美, 李金屏. 基于人体骨骼关键点的吸烟行为检测算法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3602-3607.