基于样本对加权共协关系矩阵的聚类集成算法

doi:10.13232/j.cnki.jnju.2019.04.009

南京大学学报(自然科学版) ›› 2019, Vol. 55 ›› Issue (4): 592–600.doi: 10.13232/j.cnki.jnju.2019.04.009

所属专题：测试专题

基于样本对加权共协关系矩阵的聚类集成算法

王彤¹,魏巍^1,²(),王锋^1,²

1. 山西大学计算机与信息技术学院，太原，030006
2. 山西大学计算智能与中文信息处理教育部重点实验室，太原，030006

收稿日期:2019-05-14 出版日期:2019-07-30 发布日期:2019-07-23
通讯作者: 魏巍 E-mail:weiwei@sxu.edu.cn
基金资助:
山西省高等教育机构科技创新项目(2016111)

Sample pairwise weighting co⁃association matrix based ensemble clustering algorithm

Tong Wang¹,Wei Wei^1,²(),Feng Wang^1,²

1. School of Computer and Information Technology, Shanxi University, Taiyuan, 030006, China
2. Key Laboratory of Computation Intelligence and Chinese Information Processing, Ministry of Education, Shanxi University, Taiyuan, 030006, China

Received:2019-05-14 Online:2019-07-30 Published:2019-07-23
Contact: Wei Wei E-mail:weiwei@sxu.edu.cn

摘要/Abstract

摘要：

聚类集成的目标是通过集成多个聚类结果来提高聚类算法的稳定性、鲁棒性以及精度.近些年，聚类集成受到了越来越多的关注.现有的集成聚类通常平等地对待所有基聚类，而不考虑它们的重要度.虽然学者们已经在这一方面做出了一些努力，例如使用加权策略来改进共协关系矩阵，但无论是给基聚类加权还是对类重要度评价时都忽略了样本对于其所在类贡献的差异.为此，提出了基于样本对加权共协关系矩阵的聚类集成算法，该算法利用k?means算法产生多个基聚类结果，然后对于其中的每个类再利用k?means算法产生多个小类，并计算去掉样本对所在的小类后类的不确定性变化的程度来评价该样本对的重要度，最后通过层次聚类算法得到聚类结果.在六个UCI数据集上的实验结果表明，基于样本对加权共协关系矩阵的聚类集成算法的性能优于三种经典的基于共协关系矩阵的聚类集成算法.

关键词: 聚类, 聚类集成, 共协矩阵, 加权策略

Abstract:

The goal of clustering ensemble is to improve the stability,robustness and accuracy of the final clustering results by integrating multiple clustering results. In recent years,clustering ensemble has attracted more and more attention. One limitation of most existing clustering ensemble methods is that they generally treat all base clustering equally,regardless of their importance. Although scholars have made some efforts in this aspect,for example,the weighted strategy is used to improve the co?association matrix. However,they ignore the difference in the contribution of samples to the classes they belong to when either weighting the base clustering or evaluating the class importance. Therefore,sample pairwise weighting co?association matrix based ensemble clustering algorithm is proposed. The algorithm firstly uses the k?means algorithm to generate multiple base partition results and multiple small classes for each class. The importance of the sample to the class is evaluated by calculating the change degree of uncertainty of the class after removing the subclass of the sample pairwise. Finally,the final clustering result can be obtained through the hierarchical clustering algorithm. Experimental results on six UCI data sets show that the performance of sample pairwise weighting co?association matrix based clustering ensemble algorithm is superior to the three classical clustering ensemble algorithms based on co?association matrix.

Key words: clustering, clustering ensemble, co?association matrix, weighted strategy

中图分类号:

TP391

王彤, 魏巍, 王锋. 基于样本对加权共协关系矩阵的聚类集成算法[J]. 南京大学学报(自然科学版), 2019, 55(4): 592–600.

Tong Wang, Wei Wei, Feng Wang. Sample pairwise weighting co⁃association matrix based ensemble clustering algorithm[J]. Journal of Nanjing University(Natural Sciences), 2019, 55(4): 592–600.

图/表 8

图1

图2

表1

表2

表3

表4

图3

图4

参考文献 20

1	Van HamF. Using Multilevel call matrices in large software projects∥IEEE Symposium on Information Visualization 2003. Seattle,WA,USA：IEEE,2003：227-232.
2	FurnasG F. Generalized fisheye views∥Proceedings of the SIGCHI Conference on
	Human Factors in Computing Systems. New York,NY,USA：ACM,1986：16-23.
3	SchafferD,ZaoZ P,GreenbergS,et al. Navigating hierarchically clustered networks through fisheye and full?zoom methods. ACM Transaction on Computer?Human Interaction,1996,3(2)：162-188.
4	贾云得,吕宏静,刘万春. 鱼眼变形立体图像恢复稠密深度图的方法. 计算机学报,2000,23(12)：1332-1336.
	Jia Y D,Lu H J,Liu W C.Fish?eye lens camera stereo vision for dense depth map recovery. Chinese Journal of Computers,2000,23(12)：1332-1336.
5	Van HeeK,SidorovaN,VoorhoeveM. Soundness and separability of workflow nets in the stepwise refinement approach∥Proceedings of the 24^th International Conference on Application and Theory of Petri Nets. Springer Berlin Heidelberg,2003,2679：337-356.
6	StrehlA,GhoshJ. Cluster ensembles?a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research,2003,3：583-617.
7	Iam?OnN,BoongoenT,GarrettS,et al. A link?based approach to the cluster ensemble problem. IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(12)：2396-2409.
8	FredA L N,JainA K. Combining multiple clusterings using evidence accumulation. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(6)：835-850.
9	NgA Y,JordanM I,WeissY. On spectral clustering：analysis and an algorithm∥Proceedings of the 14^th International Conference on Neural Information Processing Systems. Vancouver,Canada：MIT Press,2002：849-856.
10	FernX Z,BrodleyC E. Solving cluster ensemble problems by bipartite graph partitioning∥Proceedings of the 21^st International Conference on Machine Learning. New York,NY,USA：ACM,2004：36-43.
11	KaufmanL,RousseeuwP J. Finding groups in data：an introduction to cluster analysis. Hoboken：John Wiley and Sons Inc,1990.
12	YangY,ChenK. Temporal data clustering via weighted clustering ensemble with different representations. IEEE Transactions on Know?ledge and Data Engineering,2010,23(2)：307-320.
13	NandaA,PujariA K. Weighted co?clustering based clustering ensemble∥3^rd National Conference on Computer Vision,Pattern Recognition,Image Processing and Graphics. Hubli,India：IEEE Press,2011：46-49.
14	ZhongC M,YueX D,ZhangZ H,et al. A clustering ensemble：Two?level?refined co?association matrix with path?based transformation. Pattern Recognition,2015,48(8)：2699-2709.
15	HuangD,WangC D,LaiJ H. Locally weighted ensemble clustering. IEEE Transactions on Cybernetics,2018,48(5)：1460-1473.
16	黄栋,王昌栋,赖剑煌等. 基于决策加权的聚类集成算法. 智能系统学报,2016,11(3)：418-425.
	Huang D,Wang C D,Lai J H,et al.Clustering ensemble by decision weightingCAAI Transactions on Intelligent Systems,2016,11(3)：418-425.
17	BerikovV,PestunovI. Ensemble clustering based on weighted co?association matrices：error bound and convergence properties. Pattern Recognition,2017,63：427-436.
18	NazariA,DehghanA,NejatianS,et al. A comprehensive study of clustering ensemble weighting based on cluster quality and diversity. Pattern Analysis and Applications,2019,22(1)：133-145.
19	RandW M. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association,1971,66(336)：846-850.
20	NguyenN,CaruanaR. Consensus clusterings∥Proceedings of the 7^th IEEE International Conference on Data Mining. Omaha,NE,USA：IEEE,2007：607-612.

相关文章 15

[1]	王丽娟,丁世飞,丁玲. 基于迁移学习的软子空间聚类算法[J]. 南京大学学报(自然科学版), 2020, 56(4): 515-523.
[2]	陈俊芬,赵佳成,韩洁,翟俊海. 基于深度特征表示的Softmax聚类算法[J]. 南京大学学报(自然科学版), 2020, 56(4): 533-540.
[3]	王露,王士同. 改进模糊聚类在医疗卫生数据的Takagi⁃Sugeno模糊模型[J]. 南京大学学报(自然科学版), 2020, 56(2): 186-196.
[4]	杨红鑫,杨绪兵,张福全,业巧林. 半监督平面聚类算法设计[J]. 南京大学学报(自然科学版), 2020, 56(1): 9-18.
[5]	柴变芳,魏春丽,曹欣雨,王建岭. 面向网络结构发现的批量主动学习算法[J]. 南京大学学报(自然科学版), 2019, 55(6): 1020-1029.
[6]	杨鑫, 施虹, 王平心, 徐刚. 基于稳定性的三支聚类[J]. 南京大学学报(自然科学版), 2019, 55(4): 546-552.
[7]	徐秀芳, 徐　森, 花小朋, 徐　静, 皋　军, 安　晶. 一种基于t－分布随机近邻嵌入的文本聚类方法[J]. 南京大学学报(自然科学版), 2019, 55(2): 264-271.
[8]	贾海宁, 王士同. 面向重尾噪声的模糊规则模型[J]. 南京大学学报(自然科学版), 2019, 55(1): 61-72.
[9]	陆慎涛, 葛洪伟, 周　竞. 自动确定聚类中心的移动时间势能聚类算法[J]. 南京大学学报(自然科学版), 2019, 55(1): 143-153.
[10]	朱庆峰1，2，葛洪伟1，2*. 快速特征映射优化的流形密度峰聚类[J]. 南京大学学报(自然科学版), 2018, 54(4): 838-.
[11]	底晓强1，2*，于力伟，刘　旭，Syed Umer. 一种基于演化博弈的低轨卫星切换算法研究[J]. 南京大学学报(自然科学版), 2018, 54(4): 855-.
[12]	帅　惠, 袁晓彤, 刘青山. 基于L0约束的稀疏子空间聚类[J]. 南京大学学报(自然科学版), 2018, 54(1): 23-.
[13]	刘　宏，申德荣*，寇　月，聂铁铮，于　戈. 基于实体演化的记录链接算法[J]. 南京大学学报(自然科学版), 2017, 53(6): 991-.
[14]	严丽宇1，魏　巍1，2*，郭鑫垚1，崔军彪1. 一种基于带核随机子空间的聚类集成算法[J]. 南京大学学报(自然科学版), 2017, 53(6): 1033-.
[15]	孙梦梦1，唐旭清1，2*. 基于粒度空间的最小生成树分类算法[J]. 南京大学学报(自然科学版), 2017, 53(5): 963-.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Datasets	Objects	Dimensions	Classes
Iris	150	4	3
Wine	178	13	3
Column_3C	310	6	3
Glass	214	9	6
Musk	476	167	2
Seeds	210	7	3

Datasets	θ
Datasets	0.1	0.2		0.3	0.4		0.5		0.6		0.7		0.8		0.9		1.0		2.0		4.0
Iris	0.6249	0.6141	0.6183			0.6167		0.6107		0.5985		0.6003		0.6170		0.6124		0.6023		0.5937	0.5976
Wine	0.3238	0.3680	0.3721			0.3796		0.3794		0.3703		0.3498		0.3511		0.3595		0.3372		0.3201	0.3394
Column_3C	0.3616	0.4057	0.4403			0.4234		0.4320		0.4196		0.4066		0.3800		0.4495		0.4206		0.4186	0.4226
Glass	0.2732	0.3005	0.3357			0.3115		0.3094		0.3503		0.3145		0.3388		0.3038		0.3388		0.3038	0.7303
Musk	0.1687	0.2914	0.2592			0.2639		0.2511		0.2644		0.2949		0.2876		0.2949		0.2355		0.2086	0.2444
Seeds	0.3631	0.4283	0.4573			0.4575		0.4615		0.4861		0.4789		0.4352		0.5461		0.5153		0.4891	0.4681

Datasets	θ
Datasets	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0	2.0	4.0
Iris	0.8567	0.8490	0.8603	0.8543	0.8480	0.8410	0.8443	0.8467	0.8560	0.8477	0.8463	0.8430
Wine	0.6646	0.6820	0.6713	0.6904	0.6483	0.6789	0.6646	0.6612	0.6840	0.6621	0.6590	0.6671
Column_3C	0.7152	0.7471	0.7690	0.7563	0.7571	0.7426	0.7450	0.7410	0.7687	0.7519	0.7518	0.7556
Glass	0.6993	0.7008	0.7098	0.7178	0.7136	0.7203	0.7231	0.7376	0.7210	0.7376	0.7210	0.3318
Musk	0.6818	0.7569	0.7420	0.7291	0.7232	0.7255	0.7450	0.7561	0.7561	0.7243	0.7143	0.7255
Seeds	0.7140	0.7593	0.7731	0.7743	0.7702	0.7864	0.7807	0.7624	0.8188	0.7993	0.7881	0.7793

Datasets	ARI						CA
Datasets	OWEC	EAC		LWEA	LWGP		OWEC	EAC	LWEA	LWGP
Iris	0.6324		0.4394	0.4634		0.4400	0.8527	0.6533	0.7527	0.7413
Wine	0.3632		0.3045	0.3331		0.3295	0.6607	0.6348	0.6354	0.6399
Column_3C	0.4320		0.3054	0.3963		0.3675	0.7571	0.6935	0.7326	0.6944
Glass	0.3581		0.2092	0.2701		0.2520	0.7290	0.6782	0.6449	0.6729
Musk	0.2876		0.0291	0.1785		0.1687	0.7561	0.5924	0.6893	0.6890
Seeds	0.5016		0.1317	0.2522		0.2385	0.7943	0.5286	0.5952	0.5886

基于样本对加权共协关系矩阵的聚类集成算法

Sample pairwise weighting co⁃association matrix based ensemble clustering algorithm

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 20

相关文章 15

Metrics

本文评价

推荐阅读 2