# Are Easy Data Easy (for K-Means)

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 2 Aug 2023.

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

- [Incremental Clustering: The Case for Extra Clusters](https://mlsanity.com/paper/1406.6398/) (2014)
- [A Clustering Preserving Transformation for k-Means Algorithm Output](https://mlsanity.com/paper/2202.10455/) (2022)
- [K-means Clustering Based Feature Consistency Alignment for Label-free Model Evaluation](https://mlsanity.com/paper/2304.09758/) (2023)
- [An Aposteriorical Clusterability Criterion for k-Means++ and Simplicity of Clustering](https://mlsanity.com/paper/1704.07139/) (2017)
- [On the Consistency of k-means++ algorithm](https://mlsanity.com/paper/1702.06120/) (2017)
- [Experimental Estimation of Number of Clusters Based on Cluster Quality](https://mlsanity.com/paper/1503.03168/) (2015)
- [On the Discrepancy Between Kleinberg's Clustering Axioms and k-Means Clustering Algorithm Behavior](https://mlsanity.com/paper/1702.04577/) (2017)
- [Generalization of k-means Related Algorithms](https://mlsanity.com/paper/1903.10025/) (2019)

## Abstract (arXiv)

This paper investigates the capability of correctly recovering well-separated clusters by various brands of the k-means algorithm. The concept of well-separatedness used here is derived directly from the common definition of clusters, which imposes an interplay between the requirements of within-cluster-homogenicity and between-clusters-diversity. Conditions are derived for a special case of well-separated clusters such that the global minimum of k-means cost function coincides with the well-separatedness. An experimental investigation is performed to find out whether or no various brands of k-means are actually capable of discovering well separated clusters. It turns out that they are not. A new algorithm is proposed that is a variation of k-means++ via repeated subsampling when choosing a seed. The new algorithm outperforms four other algorithms from k-means family on the task.