MD-SPKM: A set pair k-modes clustering algorithm for incomplete categorical matrix data

Abstract

In order to solve the clustering problem with incomplete and categorical matrix data sets, and considering the uncertain relationship between samples and clusters, a set pair k-modes clustering algorithm is proposed (MD-SPKM). Firstly, the correlation theory of set pair information granule is introduced into k-modes clustering. By improving the distance formula of traditional k-modes algorithm, a set pair distance measurement method between incomplete matrix samples is defined. Secondly, considering the uncertain relationship between the sample and the cluster, the definition of the intra-cluster average distance and the threshold calculation formula to determine whether the sample belongs to multiple clusters is given, and then the result of set pair clustering is formed, which includes positive region, boundary region and negative region. Finally, through the selected three data sets and four contrast algorithms for experimental evaluation, the experimental results show that the set pair k-modes clustering algorithm can effectively handle incomplete categorical matrix data sets, and has good clustering performance in Accuracy, Recall, ARI and NMI.

Keywords

Incomplete categorical matrix data set pair information granule k-modes set pair distance set pair k-modes

Get full access to this article

View all access options for this article.

References

Wang

T.X.

and Gao

J.Y.

, An improved k-means algorithm based on kurtosis test, Journal of Physics: Conference Series 1267 (2019), 012027.

Luchi

Santos

Rodrigues

et al., Genetic sampling k-means for clustering large data sets, Lecture Notes in Computer Science 9423 (2015), 691–698.

Huang

Z.X.

, Extensions to the k-means algorithm for clustering large data sets with categorical values, Data Mining and Knowledge Discovery 2 (1998), 283–304.

Shi

Z.Q.

and Chen

S.P.

, An improved k-modes clustering algorithm, Operations Research and Management Science 28 (2019), 112–117.

Jiang

Liu

G.Z.

and Du

J.W.

, Initialization of k-modes clustering using outlier detection techniques, Information Sciences 332 (2016), 167–183.

Peng

L.W.

and Liu

Y.G.

, Attribute weights-based clustering centres algorithm for initialising K-modes clustering, Cluster Computing 22 (2019), 6171–6179.

Wang

and Tang

, Improved cluster center initialization method for clustering categorical data, Journal of Computer Applications 38 (2018), 73–76.

Cao

F.Y.

L.Q.

and Huang Joshua

Z.X.

et al., k-mw-modes: An algorithm for clustering categorical matrix-object data, Applied Soft Computing 57 (2017), 605–614.

Yao

Y.Y.

, Three-way decisions and cognitive computing, Cognitive Computation 8 (2016), 1–2.

10.

Yao

Y.Y.

, Three-way decision and granular computing, International Journal of Approximate Reasoning 103 (2018), 107–123.

11.

, Three-way cluster analysis, Peak Data Science (2016), 31–35.

12.

Zhang

C.Y.

Wang

L.Y.

and Li

M.X.

et al., Model of three-way decision based on the space of set pair information granule and its application, Journal on Communications (2016), 15–24.

13.

Huang

Y.H.

Hao

Z.F.

Cai

R.C.

et al., K-modes algorithm based on interdependence redundancy measure, Journal of Chinese Computer Systems 37 (2016), 1790–1793.

14.

Zhou

H.F.

Zhang

Y.H.

and Liu

Y.B.

, A global-relationship dissimilarity measure for the k-modes clustering algorithm, Computational Intelligence and Neuroscience 2017 (2017), 1–7.

15.

Cao

F.Y.

Huang Joshua

Z.X.

Liang

J.Y.

et al., An algorithm for clustering categorical data with set-valued features, IEEE Transactions on Neural Networks and Learning Systems 29 (2018), 4593–4606.

16.

Cao

F.Y.

Huang Joshua

Z.X.

Liang

J.Y.

et al., A fuzzy SV-k-modes algorithm for clustering categorical data with set-valued attributes, Applied Mathematics and Computation 295 (2017), 1–15.

17.

S.Y.

Zhang

M.M.

and Cao

F.Y.

, A MD fuzzy k-modes algorithm for clustering categorical matrix-object data, Journal of Computer Research and Development 56 (2019), 1325–1337.

18.

Wang

P.X.

and Yao

Y.Y.

, CE3: A three-way clustering method based on mathematical morphology, Knowledge-Based Systems 155 (2018), 54–65.

19.

Zhang

, A three-way c-means algorithm, Applied Soft Computing Journal 82 (2019), 1568–4946.

20.

Zhao

K.Q.

, Set pair analysis and its preliminary application, Exploration of Nature 1 (1994), 67–72.

21.

Huang

D.C.

Zhao

K.Q.

and Lu

Y.Z.

, The fundamental operation of arithmetic on connection number a+b⁢i+c⁢j and its application, Mechanical & Electrical Engineering Magazine 17 (2000), 81–84.

22.

Saha

Sarkar

J.P.

and Maulik

, Rough set based fuzzy k-modes for categorical data, Swarm, Evolutionary, and Memetic Computing 7677 (2012), 323–330.