Multi-Prototypes Convex Merging Based K-Means Clustering Algorithm

Dong LI, Shuisheng ZHOU*, Tieyong ZENG, Raymond H. CHAN

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review


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.

Original languageEnglish
Pages (from-to)1-16
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Publication statusAccepted/In press - 2023
Externally publishedYes

Bibliographical note

Publisher Copyright: IEEE
This work was supported by the National Natural Science Foundation of China under Grants No. 61772020; HKRGC Grants Nos. CUHK14301718, CityU11301120, and C1013-21GF; and CityU Grant 9380101.


  • K-Means
  • multi-prototypes
  • multi-prototypes sampling
  • convex merging


Dive into the research topics of 'Multi-Prototypes Convex Merging Based K-Means Clustering Algorithm'. Together they form a unique fingerprint.

Cite this