The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It
This addresses a critical problem for practitioners using clustering in high-dimensional data, revealing a fundamental flaw in a widely used method.
The paper proves that Lloyd's k-means algorithm catastrophically fails in high-dimensional, high-noise settings by returning its initial partition as a fixed point, even when clusters are easily recoverable, while showing that Hartigan's algorithm avoids this issue.
Lloyd's k-means algorithm is one of the most widely used clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits catastrophic failure: with high probability, essentially every partition of the data is a fixed point. Consequently, Lloyd's algorithm simply returns its initial partition - even when the underlying clusters are trivially recoverable by other methods. In contrast, we prove that Hartigan's k-means algorithm does not exhibit this pathology. Our results show the stark difference between these algorithms and offer a theoretical explanation for the empirical difficulties often observed with k-means in high dimensions.