  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. A
theoretical proof is given to guarantee that the multi-prototypes selected by
MPS can achieve a constant factor approximation to the optimal cost of the
K-Means problem. 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.
Experimental results performed on synthetic and real-world data sets have
verified the effectiveness of the proposed algorithm.
