Are Easy Data Easy (for K-Means)
Not on the map. Why?
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.
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
8 of 28 references.
References · 8
- 2014Incremental Clustering: The Case for Extra Clusterscited by 5
- 2022A Clustering Preserving Transformation for k-Means Algorithm Outputcited by 4
- 2023K-means Clustering Based Feature Consistency Alignment for Label-free Model Evaluationcited by 4
- 2017An Aposteriorical Clusterability Criterion for k-Means++ and Simplicity of Clusteringcited by 3
- 2017On the Consistency of k-means++ algorithmcited by 2
- 2015Experimental Estimation of Number of Clusters Based on Cluster Qualitycited by 1
- 2017On the Discrepancy Between Kleinberg's Clustering Axioms and k-Means Clustering Algorithm Behaviorcited by 1
- 2019Generalization of k-means Related Algorithmscited by 1
Built on by
Not cited yet.