Multi-Prototypes Convex Merging Based K-Means Clustering Algorithm
- 13 December 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 36 (11) , 6653-6666
Abstract
K-Means algorithm is a popular clustering method. However, it has two limitations: 1) it gets stuck easily in spurious local minima, and 2) the number of clusters $k$ has to be given a priori. To solve these two issues, a multi-prototypes convex merging based K-Means clustering algorithm (MCKM) is presented. First, based on the structure of the spurious local minima of the K-Means problem, a multi-prototypes sampling (MPS) is designed to select the appropriate number of multi-prototypes for data with arbitrary shapes. Then, a merging technique, called convex merging (CM), merges the multi-prototypes to get a better local minima without $k$ being given a priori. Specifically, CM can obtain the optimal merging and estimate the correct $k$ . By integrating these two techniques with K-Means algorithm, the proposed MCKM is an efficient and explainable clustering algorithm for escaping the undesirable local minima of K-Means problem without given $k$ first. Two theoretical proofs are given to guarantee that the cost of MCKM (MPS+CM) can achieve a constant factor approximation to the optimal cost of the K-Means problem. Experimental results performed on synthetic and real-world data sets have verified the effectiveness of the proposed algorithm.
Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61772020, HKRGC, CUHK14301718, CityU11301120, C1013-21GF)
- City University of Hong Kong (9380101)
This publication has 34 references indexed in Scilit:
- K-means properties on six clustering benchmark datasetsApplied Intelligence, 2018
- I-k-means−+: An iterative clustering algorithm based on an enhanced version of the k-meansPattern Recognition, 2018
- A review of clustering techniques and developmentsNeurocomputing, 2017
- Enhancement of the classification and reconstruction performance of fuzzy C-means with refinements of prototypesFuzzy Sets and Systems, 2017
- Robust K-means algorithm with automatically splitting and merging clusters and its applications for surveillance dataMultimedia Tools and Applications, 2016
- Splitting Methods for Convex ClusteringJournal of Computational and Graphical Statistics, 2015
- Data clustering: 50 years beyond K-meansPattern Recognition Letters, 2010
- Iterative shrinking method for clustering problemsPattern Recognition, 2006
- An empirical comparison of four initialization methods for the K-Means algorithmPattern Recognition Letters, 1999
- Comparing partitionsJournal of Classification, 1985