# Multi-Prototypes Convex Merging Based K-Means Clustering Algorithm

arXiv: https://arxiv.org/abs/2302.07045 · HTML: https://mlsanity.com/paper/2302.07045/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 55 references that are in the map.
- First posted on arXiv 14 Feb 2023.

## Builds on (most cited first, 3 of 3)

- [Splitting Methods for Convex Clustering](https://mlsanity.com/paper/1304.0499/) (2013)
- [Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm](https://mlsanity.com/paper/1810.02677/) (2018)
- [Structures of Spurious Local Minima in k-means](https://mlsanity.com/paper/2002.06694/) (2020)

## Built on by (most cited first, 4 of 4)

- [Learning Self-Growth Maps for Fast and Accurate Imbalanced Streaming Data Clustering](https://mlsanity.com/paper/2404.09243/) (2024)
- [UniForCE: The Unimodality Forest Method for Clustering and Estimation of the Number of Clusters](https://mlsanity.com/paper/2312.11323/) (2023)
- [Hierarchical clustering with maximum density paths and mixture models](https://mlsanity.com/paper/2503.15582/) (2025)
- [Scene-Aware Memory Discrimination: Deciding Which Personal Knowledge Stays](https://mlsanity.com/paper/2602.11607/) (2026)

## Abstract (arXiv)

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.