基于拓展约束投影的加权半监督聚类集成算法

doi:10.13232/j.cnki.jnju.2022.04.002

南京大学学报(自然科学版) ›› 2022, Vol. 58 ›› Issue (4): 570–583.doi: 10.13232/j.cnki.jnju.2022.04.002

基于拓展约束投影的加权半监督聚类集成算法

张鼎, 杨有龙(), 孙丽芹

西安电子科技大学数学与统计学院，西安，710126

收稿日期:2022-04-19 出版日期:2022-07-30 发布日期:2022-08-01
通讯作者: 杨有龙 E-mail:ylyang@mail.xidian.edu.cn
基金资助:
陕西省自然科学基金(2021JM-133)

Weighted semi⁃supervised clustering ensemble algorithm based on extended constraint projection

Ding Zhang, Youlong Yang(), Liqin Sun

School of Mathematics and Statistics，Xidian University，Xi'an，710126, China

Received:2022-04-19 Online:2022-07-30 Published:2022-08-01
Contact: Youlong Yang E-mail:ylyang@mail.xidian.edu.cn

摘要/Abstract

摘要：

半监督聚类集成旨在利用成对约束提升聚类集成的精度，但在高维空间的聚类效果却显著降低，另外，当只有少量的成对约束可以利用时，聚类性能很难提升.针对这些问题，提出一种新颖的半监督聚类集成算法WSCEC （Weighted Semi?supervised Clustering Ensemble Algorithm Based on Extended Constraint Projection）.首先，利用多种聚类算法对数据的特征空间进行聚类，再使用随机子空间进行降维，以减少冗余特征的影响；其次，根据每对约束的k个最近或最远的样本以及约束间的传递关系来扩展原有的约束集，通过约束投影技术将原始数据空间投影到低维空间以满足尽可能多的约束；最后，设计了一个聚类解的加权策略，为每一个聚类解分配一个适当的权重以降低低质量聚类解的影响.在多个数据集上的实验结果证明了提出算法的有效性.

关键词: 半监督聚类, 聚类集成, 随机子空间, 约束投影

Abstract:

Semi?supervised clustering ensemble aims at improving the accuracy of clustering ensemble by using pairwise constraints，but it achieves poor performance on high?dimensional datasets. In addition，clustering performance has little improvement when only a few pairwise constraints are available. To solve these problems，this paper proposes a novel semi?supervised clustering ensemble algorithm WSCEC (Weighted Semi?supervised Clustering ensemble algorithm based on Extended Constraint projection algorithm). Firstly，a variety of clustering algorithms are exploited to cluster the feature space of data，and then the random subspace is utilized for the dimension reduction to reduce the impact of redundant features. Secondly，the original constraint set is expanded according to the k nearest or farthest samples of constraints and the transitive relationship between constraints，and the original data space is projected into a low?dimensional space by constraint projection technique to satisfy as many constraints as possible. Finally，a weighting strategy of clustering solutions is designed，which assigns an appropriate weight to each clustering solution to reduce the impact of low?quality clustering solutions. Experimental results on several datasets prove the effectiveness of the proposed algorithm.

Key words: semi?supervised clustering, clustering ensemble, random subspace, constraint projection

中图分类号:

TP311.13

张鼎, 杨有龙, 孙丽芹. 基于拓展约束投影的加权半监督聚类集成算法[J]. 南京大学学报(自然科学版), 2022, 58(4): 570–583.

Ding Zhang, Youlong Yang, Liqin Sun. Weighted semi⁃supervised clustering ensemble algorithm based on extended constraint projection[J]. Journal of Nanjing University(Natural Sciences), 2022, 58(4): 570–583.

图/表 11

图1

图2

表1

表2

表3

表4

图3

图4

表5

图5

图6

参考文献 30

1	Jain A K. Data clustering：50 years beyond K?means. Pattern Recognition Letters，2010，31(8)：651-666.
2	Wu J J， Liu H F， Xiong H，et al. K?means?based consensus clustering：A unified view. IEEE Transactions on Knowledge and Data Engineering，2015，27(1)：155-169.
3	Yu Z W， Luo P N， Liu J M，et al. Semi?supervised ensemble clustering based on selected constraint projection. IEEE Transactions on Knowledge and Data Engineering，2018，30(12)：2394-2407.
4	Fern X Z， Brodley C E. Random projection for high dimensional data clustering：A cluster ensemble approach∥Proceedings of the 20th International Conference on Machine Learning. Washington，DC，USA：ACM，2003：186-193.
5	Fred A L N， Jain A K. Combining multiple clusterings using evidence accumulation. IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(6)：835-850.
6	Iam?On N， Boongoen T， Garrett S，et al. A link?based approach to the cluster ensemble problem. IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(12)：2396-2409.
7	Huang D， Wang C D， Lai J H，et al. Locally weighted ensemble clustering. IEEE Transactions on Cybernetics，2018，48(5)：1460-1473.
8	Strehl A， Ghosh J. Cluster ensembles：A knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research，2002，3(3)：583-617.
9	Mimaroglu S， Erdil E. Combining multiple clusterings using similarity graph. Pattern Recognition，2011，44(3)：694-703.
10	Li T， Ding C， Jordan M I. Solving consensus and semi?supervised clustering problems using nonnegative matrix factorization∥Proceeding of the 21th International Conference on Machine Learning. Omaha，NE，USA：IEEE，2007：577-582.
11	Huang D， Lai J H， Wang C D. Ensemble clustering using factor graph. Pattern Recognition，2016(50)：131-142.
12	Tian J L， Ren Y Z， Cheng X. Stratified feature sampling for semi?supervised ensemble clustering. IEEE Access，2019(7)：128669-128675. DOI：10.1109/ACCESS.2019.2939581 .
13	Yu Z W， Luo P N， You J E，et al. Incremental semi?supervised clustering ensemble for high dimensional data clustering. IEEE Transactions on Knowledge and Data Engineering，2016，28(3)：701-714.
14	Lai Y X， He S Y， Lin Z J，et al. An adaptive robust semi?supervised clustering framework using weighted consensus of random K?means ensemble. IEEE Transactions on Knowledge and Data Engineering，2021，33(5)：1877-1890. DOI：10.1109/TKDE. 2019.2952596 .
15	Iqbal A M， Moh'd A， Khan Z. Semi?supervised clustering ensemble by voting. 2009，arXiv:1208. 4138.
16	Wei S T， Li Z X， Zhang C L. Combined constraint?based with metric?based in semi?supervised clustering ensemble. International Journal of Machine Learning and Cybernetics，2018，9(7)：1085-1100.
17	Yang Y， Jiang J M. Bi?weighted ensemble via HMM?based approaches for temporal data clustering. Pattern Recognition，2018(76)：391-403.
18	Yu Z W， Chen H S， You J，et al. Double selection based semi?supervised clustering ensemble for tumor clustering from gene expression profiles. IEEE/ACM Transactions on Computational Biology and Bioinformatics，2014，11(4)：727-740.
19	Yu Z W， Kuang Z Q， Liu J M，et al. Adaptive ensembling of semi?supervised clustering solutions. IEEE Transactions on Knowledge and Data Engineering，2017，29(8)：1577-1590.
20	Wang H J， Qi J H， Zheng W F，et al. Semi?supervised cluster ensemble based on binary similarity matrix∥2010 2nd IEEE International Conference on Information Management and Engineering. Chengdu，China：IEEE，2010：251-254.
21	Yang F， Li T， Zhou Q F，et al. Cluster ensemble selection with constraints. Neurocomputing，2017(235)：59-70.
22	Xiao W C， Yang Y， Wang H J，et al. Semi?supervised hierarchical clustering ensemble and its application. Neurocomputing，2016(173)：1362-1376.
23	Ho T K. The random subspace method for constructing decision forests. IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20(8)：832-844.
24	Zhang D Q， Chen S C， Zhou Z H，et al. Constraint projections for ensemble learning∥Proceeding of the 23rd National Conference on Artificial Intelligence. Chicago，IL，USA：AAAI Press，2008：758-763.
25	Lu Z W， Peng Y X. Exhaustive and efficient constraint propagation：A graph?based learning approach and its applications. International Journal of Computer Vision，2013，103(3)：306-325.
26	Wagstaff K， Cardie C， Rogers S，et al. Constrained k?means clustering with background knowledge∥Proceedings of the 18th International Conference on Machine Learning. San Francisco，CA，USA：Morgan Kaufmann Publishers Inc.，2001：557-584.
27	Wang H J， Li T， Li T R，et al. Constraint neighborhood projections for semi?supervised clustering. IEEE Transactions on Cybernetics，2014，44(5)：636-643.
28	Liu H F， Wu J J， Liu T L，et al. Spectral ensemble clustering via weighted K?means：Theoretical and practical evidence. IEEE Transactions on Knowledge and Data Engineering，2017，29(5)：1129-1143.
29	Huang D， Wang C D， Wu J S，et al. Ultra?scalable spectral clustering and ensemble clustering. IEEE Transactions on Knowledge and Data Engineering，2020，32(6)：1212-1226.
30	Xiong S C， Azimi J， Fern X Z. Active learning of constraints for semi?supervised clustering. IEEE Transactions on Knowledge and Data Engineering，2014，26(1)：43-54.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

数据集	样本量	特征数	类别
Segmentation	2319	19	7
Semeion	1593	256	10
Optdigit	5620	64	10
ISOLET	1559	617	26
Cardiotocography	2126	23	10
Sat	6435	36	6
COIL20	1440	1024	20
Yale	165	1024	15
MNIST4000	4000	784	10
ORL	400	1024	40
11_Tumors	174	12533	11
Leukemia2	72	11225	3

数据集	COPE⁃kmeans	CNPE⁃kmeans	E²CPE	WECR	MCLA	SEC	USENC	WSCEC
Segmentation	0.513	0.547	0.634	0.623	0.539	0.562	0.638	0.662
Semeion	0.525	0.554	0.599	0.590	0.578	0.551	0.649	0.633
Optdigit	0.815	0.763	0.916	0.793	0.839	0.683	0.834	0.914
ISOLET	0.663	0.707	0.679	0.711	0.675	0.687	0.709	0.755
Cardiotocography	0.471	0.479	0.464	0.527	0.511	0.450	0.544	0.609
Sat	0.529	0.533	0.520	0.544	0.511	0.541	0.578	0.625
COIL20	0.760	0.776	0.793	0.801	0.744	0.723	0.799	0.841
Yale	0.417	0.477	0.438	0.413	0.351	0.414	0.417	0.464
MNIST4000	0.504	0.543	0.595	0.584	0.551	0.363	0.588	0.632
ORL	0.608	0.614	0.581	0.645	0.445	0.666	0.690	0.736
11_Tumors	0.544	0.569	0.554	0.543	0.515	0.577	0.524	0.670
Leukemia2	0.527	0.535	0.363	0.593	0.490	0.388	0.456	0.627

数据集	COPE⁃kmeans	CNPE⁃kmeans	E²CPE	WECR	MCLA	SEC	USENC	WSCEC
Segmentation	0.377	0.456	0.527	0.526	0.425	0.343	0.516	0.567
Semeion	0.391	0.454	0.487	0.499	0.464	0.457	0.535	0.522
Optdigit	0.776	0.723	0.921	0.761	0.806	0.671	0.780	0.914
ISOLET	0.415	0.482	0.440	0.488	0.386	0.391	0.454	0.507
Cardiotocography	0.254	0.262	0.236	0.303	0.278	0.235	0.304	0.385
Sat	0.439	0.449	0.434	0.465	0.421	0.353	0.486	0.531
COIL20	0.613	0.638	0.645	0.647	0.596	0.571	0.598	0.681
Yale	0.342	0.400	0.368	0.359	0.296	0.343	0.347	0.392
MNIST4000	0.386	0.452	0.490	0.475	0.429	0.286	0.469	0.535
ORL	0.217	0.186	0.235	0.311	0.063	0.277	0.327	0.390
11_Tumors	0.332	0.372	0.332	0.331	0.304	0.365	0.343	0.536
Leukemia2	0.535	0.538	0.341	0.596	0.461	0.32	0.397	0.633

数据集	COPE⁃kmeans	CNPE⁃kmeans	E²CPE	WECR	MCLA	SEC	USENC	WSCEC
Segmentation	0.543	0.563	0.65	0.662	0.574	0.573	0.645	0.668
Semeion	0.624	0.669	0.595	0.671	0.661	0.617	0.724	0.68
Optdigit	0.811	0.86	0.944	0.871	0.851	0.79	0.91	0.939
ISOLET	0.532	0.567	0.541	0.552	0.432	0.447	0.545	0.565
Cardiotocography	0.434	0.431	0.407	0.403	0.438	0.384	0.47	0.533
Sat	0.603	0.642	0.616	0.653	0.64	0.404	0.7	0.73
COIL20	0.693	0.705	0.732	0.717	0.634	0.553	0.617	0.751
Yale	0.372	0.419	0.38	0.348	0.312	0.359	0.355	0.397
MNIST4000	0.55	0.621	0.666	0.583	0.601	0.334	0.6	0.687
ORL	0.412	0.38	0.391	0.528	0.24	0.439	0.452	0.553
11_Tumors	0.513	0.522	0.509	0.539	0.508	0.489	0.512	0.677
Leukemia2	0.729	0.791	0.704	0.836	0.665	0.648	0.512	0.677

Datasets	WSCEC	WSCEC_not
Segmentation	0.650	0.615
Semeion	0.621	0.644
Optdigit	0.928	0.900
ISOLET	0.752	0.728
Cardiotocography	0.615	0.508
Sat	0.625	0.560
COIL20	0.832	0.806
Yale	0.459	0.401
MNIST4000	0.638	0.603
ORL	0.732	0.631
11_Tumors	0.683	0.573
Leukemia2	0.623	0.585

基于拓展约束投影的加权半监督聚类集成算法

Weighted semi⁃supervised clustering ensemble algorithm based on extended constraint projection

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 30

相关文章 9

Metrics

本文评价

推荐阅读 0

[1]	邵长龙, 孙统风, 丁世飞. 基于信息熵加权的聚类集成算法[J]. 南京大学学报(自然科学版), 2021, 57(2): 189-196.
[2]	杨红鑫,杨绪兵,张福全,业巧林. 半监督平面聚类算法设计[J]. 南京大学学报(自然科学版), 2020, 56(1): 9-18.
[3]	柴变芳,魏春丽,曹欣雨,王建岭. 面向网络结构发现的批量主动学习算法[J]. 南京大学学报(自然科学版), 2019, 55(6): 1020-1029.
[4]	杨鑫, 施虹, 王平心, 徐刚. 基于稳定性的三支聚类[J]. 南京大学学报(自然科学版), 2019, 55(4): 546-552.
[5]	王彤, 魏巍, 王锋. 基于样本对加权共协关系矩阵的聚类集成算法[J]. 南京大学学报(自然科学版), 2019, 55(4): 592-600.
[6]	严丽宇1，魏　巍1，2*，郭鑫垚1，崔军彪1. 一种基于带核随机子空间的聚类集成算法[J]. 南京大学学报(自然科学版), 2017, 53(6): 1033-.
[7]	孟　娜1，梁吉业1，2*，庞天杰1. 一种基于抽样的谱聚类集成算法 [J]. 南京大学学报(自然科学版), 2016, 52(6): 1090-.
[8]	常瑜^1.2*，梁吉业^{1, 2}，高嘉伟^1,2，杨静^1·2. 一种基于Seeds集和成对约束的半监督聚类算法[J]. 南京大学学报(自然科学版), 2012, 48(4): 405-411.
[9]	申彦*，宋顺林，朱玉全 . 一种基于半监督的大规模数据集聚类算法 [J]. 南京大学学报(自然科学版), 2011, 47(4): 372-382.