# Global k-means++: an effective relaxation of the global k-means clustering algorithm

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 46 references that are in the map.
- First posted on arXiv 22 Nov 2022.

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

- [k-means++: few more steps yield constant approximation](https://mlsanity.com/paper/2002.07784/) (2020)
- [On Approximability of Clustering Problems Without Candidate Centers](https://mlsanity.com/paper/2010.00087/) (2020)
- [An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2111.15571/) (2021)

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

- [Deep Clustering Using the Soft Silhouette Score: Towards Compact and Well-Separated Clusters](https://mlsanity.com/paper/2402.00608/) (2024)
- [Counterfactual Explanations for k-means and Gaussian Clustering](https://mlsanity.com/paper/2501.10234/) (2025)
- [UniForCE: The Unimodality Forest Method for Clustering and Estimation of the Number of Clusters](https://mlsanity.com/paper/2312.11323/) (2023)
- [Silhouette-Driven Instance-Weighted k-means](https://mlsanity.com/paper/2506.12878/) (2025)

## Abstract (arXiv)

The k-means algorithm is a prevalent clustering method due to its simplicity, effectiveness, and speed. However, its main disadvantage is its high sensitivity to the initial positions of the cluster centers. The global k-means is a deterministic algorithm proposed to tackle the random initialization problem of k-means but its well-known that requires high computational cost. It partitions the data to K clusters by solving all k-means sub-problems incrementally for all k=1,ldots, K. For each k cluster problem, the method executes the k-means algorithm N times, where N is the number of datapoints. In this paper, we propose the emphglobal k-meanstexttt++ clustering algorithm, which is an effective way of acquiring quality clustering solutions akin to those of global k-means with a reduced computational load. This is achieved by exploiting the center selection probability that is effectively used in the k-meanstexttt++ algorithm. The proposed method has been tested and compared in various benchmark datasets yielding very satisfactory results in terms of clustering quality and execution speed.