An Observation on Lloyd's k-Means Algorithm in High Dimensions

2025/06/17 by David Silva-Sánchez, Silva-Sánchez, David, Roy R. Lederman +1
Computer Science · #Data Mining Algorithms and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2506.14952

openalex publication_date 2025/06/17 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Methods for Cryo-EM Single Particle Reconstruction of Macromolecules having Continuous Heterogeneity
• RELION: Implementation of a Bayesian approach to cryo-EM structure determination
• K‐means clustering: A half‐century synthesis
• Least squares quantization in PCM

Related

• An Experimental Comparison of Several Clustering and Initialization Methods
• Learning Mixtures of Gaussians using the k-means Algorithm
• Asymptotic properties of k-means and its bias correction for high-dimension, low-sample-size data
• The algorithm of noisy k-means
• Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise