An Observation on Lloyd's k-Means Algorithm in High Dimensions
This addresses a theoretical limitation in clustering algorithms for statisticians and machine learning practitioners, but it is incremental as it builds on known issues in high-dimensional data analysis.
The paper explains why k-means fails in high-dimensional, noisy settings with limited samples using a Gaussian Mixture Model, showing that almost every data partition becomes a fixed point of the algorithm with high probability.
Clustering and estimating cluster means are core problems in statistics and machine learning, with k-means and Expectation Maximization (EM) being two widely used algorithms. In this work, we provide a theoretical explanation for the failure of k-means in high-dimensional settings with high noise and limited sample sizes, using a simple Gaussian Mixture Model (GMM). We identify regimes where, with high probability, almost every partition of the data becomes a fixed point of the k-means algorithm. This study is motivated by challenges in the analysis of more complex cases, such as masked GMMs, and those arising from applications in Cryo-Electron Microscopy.