A K-modes Clustering Method Based on Maximal Information Coefficient Data Preprocessing

doi:10.16182/j.issn1004731x.joss.21-0484

Abstract

Abstract:

The existing k-modes clustering method ignores the weak correlation of variable attributes, which often results in poor clustering performance in practical applications. A new k-modes clustering method that includes the weak correlation of attributes is proposed. Maximum information coefficient (MIC) is introduced to measure the correlation of variable attributes in the data set. The obtained MIC value is merged with the original distance to establish a new measurement method containing weak attribute correlation information to enhance the completeness of related information of variable attributes, and a more refined k-modes clustering method is established. Three different data sets are used to compare the performance of the new method with the existing k-modes clustering and other improved k-modes clustering methods, the simulation results shows the effectness of the new method.

Key words: clustering algorithm, k-modes, maximum information coefficient(MIC), distance metric, variable attribute

CLC Number:

TP311

Mingmei Li, Chenglin Wen, Shaolin Hu. A K-modes Clustering Method Based on Maximal Information Coefficient Data Preprocessing[J]. Journal of System Simulation, 2022, 34(10): 2204-2212.

Figures/Tables 11

Table 1

Fig. 1

Fig. 2

Fig. 3

Table 2

Table 3

Table 4

Table 5

Table 6

Table 7

Table 8

References 13

1	Huang Z, Ng M K.A Fuzzy K-modes Algorithm for Clustering Cate-Gorical Data[J].IEEE Transactions on Fuzzy Systems, 1999, 7(4): 446-452.
2	Ahmad A, Dey L.A Method to Compute Distance between Two Cate-Gorical Values of Same Attributein Unsupervised Learning for Categori-Cal Data Set[J].Pattern Recognition Letters(S0167-8655), 2007, 28(1): 110-118.
3	张小宇, 梁吉业, 曹付元, 等. 基于加权连接度的改进K-Modes聚类算法[J]. 广西师范大学学报(自然科学版), 2008, 26(3): 189-193.
	Zhang Xiaoyu, Liang Jiye, Cao Fuyuan, et al. An Improved K-modes Clustering Algorithm Based on Weighted Connectivity [J]. Journal of Guangxi Normal University (Natural Science Edition), 2008, 26(3): 189-193.
4	吴润秀. 基于互信息量的改进K-Modes聚类方法[J]. 统计与决策, 2012, 354(6): 89-91.
	Wu Runxiu. An Improved K-Modes Clustering Method Based on Mutual Information [J]. Statistics and Decision, 2012, 354(6): 89-91.
5	Choi Jin-Kyu, Shin Youngcheol, Hong Soonil, et al. A Study on Real-time Data Preprocessing Technique for Small Millimeter Wave Radar[J]. The Journal of The Institute of Internet, Broadcasting and Communication(S2289-0238), 2019, 19(6): 79-85.
6	Axelsson Owe, Neytcheva Maya, Ström Anders. An Efficient Preconditioning Method for State Box-Constrained Optimal Control Problems[J]. Journal of Numerical Mathematics(S1570-2820), 2018, 26(4): 185-207.
7	谢娟英, 吴肇中, 郑清泉. 基于信息增益与皮尔森相关系数的2D自适应特征选择算法[J]. 陕西师范大学学报(自然科学版), 2020, 48(6): 69-81.
	Xie Juanying, Wu Zhaozhong, Zheng Qingquan.A 2D Adaptive Feature Selection Algorithm Based on Information Gain and Pearson Correlation Coefficient [J].Journal of Shaanxi Normal University (Natural Science Edition), 2020, 48(6): 69-81.
8	彭竹清, 王艳, 纪志成. 基于改进熵值法的离散制造系统能效评价方法[J]. 系统仿真学报, 2017, 29(9): 2121-2127.
	Peng Zhuqing, Wang Yan, Ji Zhicheng. Energy Efficiency Evaluation Method of Discrete Manufacturing System Based on Improved Entropy Method[J]. Journal of System Simulation, 2017, 29(9): 2121-2127.
9	徐洪峰, 孙振强. 多标签学习中基于互信息的快速特征选择方法[J]. 计算机应用, 2019, 39(10): 2815-2821.
	Xu Hongfeng, Sun Zhenqiang. Fast Feature Selection Method Based on Mutual Information in Multi-label Learning [J]. Journal of Computer Applications, 2019, 39(10): 2815-2821.
10	叶继华, 兰清平, 刘长红, 等. 结合互信息量和Log-Gabor特征的嵌入式人脸识别[J]. 系统仿真学报, 2016, 28(9): 2214-2219.
	Ye Jihua, Lan Qingping, Liu Changhong, et al. Embedded Face Recognition Based on Mutual Information and Log-Gabor Feature [J]. Journal of System Simulation, 2016, 28(9): 2214-2219.
11	Reshef David N, Reshef Yakir A, Finucane Hilary K, et al. Detecting Novel Associations in Large Data Sets[J]. Science(S0036-8075), 2011, 334(6062): 1518-1524.
12	施振佺, 陈世平. 一种改进的k-modes聚类算法[J]. 运筹与管理, 2019, 28(12): 112-117.
	Shi Zhenquan, Chen Shiping.An Improved K-modes Clustering Algorithm [J]. Operations Research and Management, 2019, 28(12): 112-117.
13	Zhou Hongfang, Zhang Yihui, Liu Yibin. A Global-Relationship Dissimilarity Measure for the k-modes Clustering Algorithm[J]. Computational Intelligence and Neuroscience(S1687-5265), 2017: 3691316.

数据集	对象数n	属性数m
vote	435	16
cancer	699	10
mushroom	8 124	22

指标	k-modes	MI-k-modes	Z-k-modes	MIC-k-modes
AC	0.815 7	0.844 9	0.866 1	0.909 3
PE	0.828 9	0.842 3	0.862 7	0.899 5
RE	0.817 2	0.831 4	0.851 3	0.889 7

指标	k-modes	MI-k-modes	Z-k-modes	MIC-k-modes
AC	0.822 1	0.846 9	0.863 1	0.894 7
PE	0.818 3	0.840 0	0.861 1	0.882 3
RE	0.808 2	0.832 3	0.849 0	0.876 9

指标	k-modes	MI-k-modes	Z-k-modes	MIC-k-modes
AC	0.723 9	0.752 1	0.795 3	0.856 2
PE	0.751 2	0.768 9	0.802 1	0.843 7
RE	0.718 9	0.745 1	0.782 4	0.833 4

指标	对比k-modes	对比MI-k-modes	对比Z-k-modes
AC	11.475	7.622	4.987
PE	8.517	6.791	4.265
RE	8.872	7.012	4.510