Semi-supervised three-way clustering ensemble based on Seeds set and pairwise constraints

doi:10.11772/j.issn.1001-9081.2022071094

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (5): 1481-1488.DOI: 10.11772/j.issn.1001-9081.2022071094

• Data science and technology • Previous Articles

Semi-supervised three-way clustering ensemble based on Seeds set and pairwise constraints

Chunmao JIANG¹, Peng WU², Zhicong LI²()

^1.School of Computer Science and Mathematics，Fujian University of Technology，Fuzhou Fujian 350118，China
^2.College of Computer Science and Information Engineering，Harbin Normal University，Harbin Heilongjiang 150025，China

Received:2022-07-19 Revised:2022-10-03 Accepted:2022-11-04 Online:2023-05-08 Published:2023-05-10
Contact: Zhicong LI
About author:JIANG Chunmao， born in 1972， Ph. D.， professor. His research interests include three-way decision and three-way computing， cloud computing， big data mining.
WU Peng， born in 1997， M. S. candidate. His research interests include three-way decision.
LI Zhicong， born in 1972， M. S.， associate professor. His research interests include data mining.
Supported by:
Natural Science Foundation of Heilongjiang Province(LH2020F031);Fujian University of Technology Research Start Fund Project(GY-Z220212)

基于Seeds集和成对约束的半监督三支聚类集成

姜春茂¹, 吴鹏², 李志聪²()

^1.福建工程学院计算机科学与数学学院，福州 350118
^2.哈尔滨师范大学计算机科学与信息工程学院，哈尔滨 150025

通讯作者: 李志聪
作者简介:姜春茂（1972—），男，辽宁庄河人，教授，博士，CCF高级会员，主要研究方向：三支决策与三支计算、云计算、大数据挖掘
吴鹏（1997—），男，山东烟台人，硕士研究生，主要研究方向：三支决策
李志聪（1972—），男，黑龙江绥化人，副教授，硕士，CCF会员，主要研究方向：数据挖掘。lizhicong72@163.com
基金资助:
黑龙江省自然科学基金资助项目(LH2020F031);福建工程学院科研启动基金资助项目(GY?Z220212)

Abstract

Abstract:

Using appropriate strategies， clustering ensemble can effectively improve the stability， robustness and precision of clustering results by fusing multiple base cluster members with differences. Current research on the clustering ensemble rarely uses known priori information， and it is difficult to describe belonging relationships between objects and clusters when facing complex data. Therefore， a semi-supervised three-way clustering ensemble method was proposed on the basis of Seeds set and pairwise constraints. Firstly， based on the existing label information， a new three-way label propagation algorithm was proposed to construct the base cluster members. Secondly， a semi-supervised three-way clustering ensemble framework was designed to integrate the base cluster members to construct a consistent similarity matrix， and this matrix was optimized by using pairwise constraint information. Finally， the three-way spectral clustering was employed as a consistency function to cluster the similarity matrix to obtain the final clustering results. Experimental results on several real datasets in UCI show that compared with the semi-supervised clustering ensemble algorithms including Cluster-based Similarity Partitioning Algorithm （CSPA）， HyperGraph Partitioning Algorithm （HGPA）， Meta-CLustering Algorithm （MCLA）， Label Propagation Algorithm （LPA） and Cop-Kmeans， the proposed method achieves the best results on most of the datasets in terms of Normalized Mutual Information （NMI）， Adjusted Rand Index （ARI） and F-measure.

Key words: three-way decision, clustering ensemble, three-way clustering, pairwise constraint, semi-supervised, Seeds set

摘要：

聚类集成使用合适的策略融合多个具有差异性的基聚类成员，能够有效提高聚类结果的稳定性、鲁棒性和准确率。当前聚类集成的研究较少利用已知的先验信息，面对复杂数据时难以刻画对象与类簇之间明确的归属关系。因此，提出一种基于Seeds集和成对约束的半监督三支聚类集成方法。首先，基于已有的标签信息提出一种新的三支标签传播算法构造基聚类成员；其次，提出一种半监督三支聚类集成框架集成基聚类成员，构造出一致性相似矩阵，并利用成对约束信息对该矩阵进行优化调整；最后，将三支谱聚类作为一致性函数对相似矩阵进行聚类，得到最终集成结果。在多个UCI真实数据集上的实验结果表明，与基于类簇的相似分区算法（CSPA）、超图分区算法（HGPA）、元类簇算法（MCLA）、标签传播算法（LPA）、Cop-Kmeans等半监督聚类集成算法相比，所提方法的归一化互信息（NMI）、调整兰德系数（ARI）和F测度在绝大多数据集上取得了最优值，获得了相对更好的聚类集成结果。

关键词: 三支决策, 聚类集成, 三支聚类, 成对约束, 半监督, Seeds集

CLC Number:

TP391

Chunmao JIANG, Peng WU, Zhicong LI. Semi-supervised three-way clustering ensemble based on Seeds set and pairwise constraints[J]. Journal of Computer Applications, 2023, 43(5): 1481-1488.

姜春茂, 吴鹏, 李志聪. 基于Seeds集和成对约束的半监督三支聚类集成[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1481-1488.

Figures/Tables 8

References 25

1	STREHL A， GHOSH J. Cluster ensembles — a knowledge reuse framework for combining multiple partitions［J］. Journal of Machine Learning Research， 2003， 3： 583-617.
2	ZHOU Z H， TANG W. Cluster ensemble［J］. Knowledge-Based Systems， 2006， 19（1）： 77-83. 10.1016/j.knosys.2005.11.003
3	FRED A L N， JAIN A K. Combining multiple clusterings using evidence accumulation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（6）： 835-850. 10.1109/tpami.2005.113
4	WANG Z， WANG S， BAI L， et al. Semisupervised fuzzy clustering with fuzzy pairwise constraints［J］. IEEE Transactions on Fuzzy Systems， 2022， 30（9）： 3797-3811. 10.1109/tfuzz.2021.3129848
5	MA T H， ZHENG Z， GUO L， et al. Semi-supervised selective clustering ensemble based on constraint information［J］. Neurocomputing， 2021， 462： 412-425. 10.1016/j.neucom.2021.07.056
6	XIAO W， YANG Y， WANG H， et al. Semi-supervised hierarchical clustering ensemble and its application［J］. Neurocomputing， 2016， 173（Pt 3）： 1362-1376. 10.1016/j.neucom.2015.09.009
7	YU H， WANG Y. Three-way decisions method for overlapping clustering［C］// Proceedings of the 2012 International Conference on Rough Sets and Current Trends in Computing， LNCS 7413. Berlin： Springer， 2012： 277-286.
8	WANG P X， YAO Y Y. CE3： a three-way clustering method based on mathematical morphology［J］. Knowledge-Based Systems， 2018， 155： 54-65. 10.1016/j.knosys.2018.04.029
9	YU H， CHEN L Y， YAO J T. A three-way density peak clustering method based on evidence theory［J］. Knowledge-Based Systems， 2021， 211： No.106532. 10.1016/j.knosys.2020.106532
10	AFRIDI M K， AZAM N， YAO J T， et al. A three-way clustering approach for handling missing data using GTRS［J］. International Journal of Approximate Reasoning， 2018， 98： 11-24. 10.1016/j.ijar.2018.04.001
11	YU H， WANG X C， WANG G Y， et al. An active three-way clustering method via low-rank matrices for multi-view data［J］. Information Sciences， 2020， 507： 823-839. 10.1016/j.ins.2018.03.009
12	JIANG C M， LI Z C， YAO J T. A shadowed set-based three-way clustering ensemble approach［J］. International Journal of Machine Learning and Cybernetics， 2022， 13（9）： 2545-2558. 10.1007/s13042-022-01543-5
13	CUI S Z， WANG Y Z， YIN Y Q， et al. A cluster-based intelligence ensemble learning method for classification problems［J］. Information Sciences， 2021， 560： 386-409. 10.1016/j.ins.2021.01.061
14	TOPCHY A， JAIN A K， PUNCH W. A mixture model for clustering ensembles［C］// Proceedings of the 2004 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2004： 379-390. 10.1137/1.9781611972740.35
15	唐伟，周志华. 基于Bagging的选择性聚类集成［J］. 软件学报， 2005， 16（4）：496-502. 10.1360/jos160496
	TANG W， ZHOU Z H. Bagging-based selective clusterer ensemble［J］. Journal of Software， 2005， 16（4）： 496-502. 10.1360/jos160496
16	MA T H， YU T， WU X G， et al. Multiple clustering and selecting algorithms with combining strategy for selective clustering ensemble［J］. Soft Computing， 2020， 24（20）： 15129-15141. 10.1007/s00500-020-05264-1
17	RASHIDI F， NEJATIAN S， PARVIN H， et al. Diversity based cluster weighting in cluster ensemble： an information theory approach［J］. Artificial Intelligence Review， 2019， 52（2）： 1341-1368. 10.1007/s10462-019-09701-y
18	GHAEMI R， SULAIMAN M N， IBRAHIM H， et al. A survey： clustering ensembles techniques［J］. Proceedings of World Academy of Science， Engineering and Technology， 2009， 38： 644-653. 10.1109/itng.2010.88
19	WAGSTAFF K， CARDIE C， ROGERS S， et al. Constrained k-means clustering with background knowlege ［C］// Proceedings of the Eighteenth International Conference on Machine Learning.San Francisco， CA： Morgan Kaufmann Publishers Inc.， 2001： 577-584.
20	ZHENG L， LI T. Semi-supervised hierarchical clustering［C］// Proceedings of the IEEE 11th International Conference on Data Mining. Piscataway： IEEE， 2011： 982-991. 10.1109/icdm.2011.130
21	YANG Y， RUTAYISIRE T， LIN C， et al. An improved Cop-Kmeans clustering for solving constraint violation based on MapReduce framework［J］. Fundamenta Informaticae， 2013， 126（4）： 301-318. 10.3233/fi-2013-883
22	QIN Y， DING S F， WANG L J， et al. Research progress on semi-supervised clustering［J］. Cognitive Computation， 2019， 11（5）： 599-612. 10.1007/s12559-019-09664-w
23	ZHOU D Y， BOUSQUET O， LAL T N， et al. Learning with local and global consistency［C］// Proceedings of the 16th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2003： 321-328.
24	YU H， ZHANG C， WANG G Y. A tree-based incremental overlapping clustering method using the three-way decision theory［J］. Knowledge-Based Systems， 2016， 91： 189-203. 10.1016/j.knosys.2015.05.028
25	FANG X， XU Y， LI X， et al. Robust semi-supervised subspace clustering via non-negative low-rank representation［J］. IEEE Transactions on Cybernetics， 2016， 46（8）： 1828-1838. 10.1002/cpe.5359
	YANG J， SUN L， WU Q. Constraint projections for semi-supervised spectral clustering ensemble ［J］. Concurrency and Computation Practice and Experience， 2019， 31（20）： e5359. 10.1002/cpe.5359

数据集	样本数	属性数	分类数
Glass	214	9	6
Wine	178	13	3
Iris	150	4	3
Segment	2 310	19	7
Ionosphere	351	34	2
Bank	1 372	4	2
Sonar	208	60	2

数据集	样本数	属性数	分类数
Glass	214	9	6
Wine	178	13	3
Iris	150	4	3
Segment	2 310	19	7
Ionosphere	351	34	2
Bank	1 372	4	2
Sonar	208	60	2

数据集	CSPA	HGPA	MCLA	LPA	Cop-Kmeans	CPSSSCE	STWCE
Segment	0.803	0.823	0.816	0.791	0.691	0.504	0.825
Iris	0.833	0.770	0.810	0.714	0.801	0.830	0.885
Wine	0.762	0.781	0.863	0.712	0.864	0.853	0.863
Glass	0.318	0.278	0.434	0.267	0.248	0.277	0.477
Ionosphere	0.339	0.387	0.170	0.310	0.257	0.473	0.476
Bank	0.793	0.790	0.939	0.764	0.193	0.862	0.951
Sonar	0.183	0.136	0.122	0.114	0.129	0.209	0.227

数据集	CSPA	HGPA	MCLA	LPA	Cop-Kmeans	CPSSSCE	STWCE
Segment	0.803	0.823	0.816	0.791	0.691	0.504	0.825
Iris	0.833	0.770	0.810	0.714	0.801	0.830	0.885
Wine	0.762	0.781	0.863	0.712	0.864	0.853	0.863
Glass	0.318	0.278	0.434	0.267	0.248	0.277	0.477
Ionosphere	0.339	0.387	0.170	0.310	0.257	0.473	0.476
Bank	0.793	0.790	0.939	0.764	0.193	0.862	0.951
Sonar	0.183	0.136	0.122	0.114	0.129	0.209	0.227

数据集	CSPA	HGPA	MCLA	LPA	Cop-Kmeans	CPSSSCE	STWCE
Segment	0.834	0.843	0.843	0.824	0.691	0.594	0.852
Iris	0.816	0.777	0.870	0.745	0.795	0.805	0.870
Wine	0.746	0.694	0.824	0.722	0.847	0.841	0.824
Glass	0.438	0.396	0.470	0.435	0.356	0.427	0.500
Ionosphere	0.305	0.353	0.212	0.331	0.360	0.416	0.432
Bank	0.747	0.743	0.893	0.683	0.139	0.909	0.919
Sonar	0.141	0.105	0.109	0.130	0.096	0.158	0.182

Semi-supervised three-way clustering ensemble based on Seeds set and pairwise constraints

基于Seeds集和成对约束的半监督三支聚类集成

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 25

Related Articles 15

Recommended Articles

Metrics

数据集	CSPA	HGPA	MCLA	LPA	Cop-Kmeans	CPSSSCE	STWCE
Segment	0.898	0.912	0.907	0.889	0.741	0.653	0.914
Iris	0.939	0.833	0.891	0.876	0.906	0.904	0.959
Wine	0.908	0.899	0.918	0.907	0.954	0.949	0.956
Glass	0.475	0.475	0.660	0.452	0.360	0.428	0.685
Ionosphere	0.787	0.807	0.616	0.748	0.749	0.811	0.824
Bank	0.945	0.944	0.984	0.932	0.715	0.958	0.987
Sonar	0.716	0.687	0.653	0.674	0.680	0.727	0.740

[1]	Boyi FU, Yuncong PENG, Xin LAN, Xiaolin QIN. Survey of label noise learning algorithms based on deep learning [J]. Journal of Computer Applications, 2023, 43(3): 674-684.
[2]	Jinye LI, Ruizhang HUANG, Yongbin QIN, Yanping CHEN, Xiaoyu TIAN. Recognition of sentencing circumstances in adjudication documents based on abductive learning [J]. Journal of Computer Applications, 2022, 42(6): 1802-1807.
[3]	Yongru QIU, Guangle YAO, Jie FENG, Haoyu CUI. Single image de-raining algorithm based on semi-supervised learning [J]. Journal of Computer Applications, 2022, 42(5): 1577-1582.
[4]	Yuchang YIN, Hongyuan WANG, Li CHEN, Zundeng FENG, Yu XIAO. One-shot video-based person re-identification with multi-loss learning and joint metric [J]. Journal of Computer Applications, 2022, 42(3): 764-769.
[5]	Kaiqiang YUE, Bo LI, Panlong FAN. Air combat maneuver decision method based on three-way decision [J]. Journal of Computer Applications, 2022, 42(2): 616-621.
[6]	Yu LU, Lingyun ZHAO, Binwen BAI, Zhen JIANG. Imbalanced classification algorithm based on improved semi-supervised clustering [J]. Journal of Computer Applications, 2022, 42(12): 3750-3755.
[7]	Jie WU, Shitian ZHANG, Haibin XIE, Guang YANG. Semi-supervised knee abnormality classification based on multi-imaging center MRI data [J]. Journal of Computer Applications, 2022, 42(1): 316-324.
[8]	MAO Mingze, CAO Ruihao, YAN Chungang. Semi-supervised classification algorithm based on weight diversity [J]. Journal of Computer Applications, 2021, 41(9): 2473-2480.
[9]	ZHANG Shipeng, LI Yongzhong, DU Xiangtong. Intrusion detection model based on semi-supervised learning and three-way decision [J]. Journal of Computer Applications, 2021, 41(9): 2602-2608.
[10]	CAO Yuhong, XU Hai, LIU Sun'ao, WANG Zixiao, LI Hongliang. Review of deep learning-based medical image segmentation [J]. Journal of Computer Applications, 2021, 41(8): 2273-2287.
[11]	OU Lili, SHAO Fengjing, SUN Rencheng, SUI Yi. Cerebral infarction image recognition based on semi-supervised method [J]. Journal of Computer Applications, 2021, 41(4): 1221-1226.
[12]	YANG Ling, JIANG Chunmao. Strategy of energy-aware virtual machine migration based on three-way decision [J]. Journal of Computer Applications, 2021, 41(4): 990-998.
[13]	HUANG Xiaoxiang, HU Yongmei, WU Dan, REN Lijie. Early identification and prediction of abnormal carotid arteries based on variational autoencoder [J]. Journal of Computer Applications, 2021, 41(10): 3082-3088.
[14]	ZHU Yuna, ZHANG Yutao, YAN Shaoge, FAN Yudan, CHEN Hantuo. Protocol identification approach based on semi-supervised subspace clustering [J]. Journal of Computer Applications, 2021, 41(10): 2900-2904.
[15]	ZHANG Kailin, YAN Qing, XIA Yi, ZHANG Jun, DING Yun. Semi-supervised hyperspectral image classification based on focal loss [J]. Journal of Computer Applications, 2020, 40(4): 1030-1037.