The Catastrophic Failure of *the* k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It

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.

Clustering — automatically sorting data into groups of similar items, or clusters — is a foundational tool in data analysis, used for everything from grouping customer reviews by topic to sorting medical images by disease. One of the most widely used clustering methods is a classic algorithm known as Lloyd's algorithm, so dominant it is often called "the k-means algorithm." Yet researchers have long observed that it performs poorly when the data has many features and is noisy — increasingly common in genomics, text analysis, and imaging. We mathematically prove why this happens. In a simplified but well-studied statistical model, Lloyd's algorithm is very likely to get stuck immediately: it returns whatever initial guess it was given and never improves on it. Remarkably, this can happen even when the correct clusters are easy to find by other methods. We also prove that a lesser-known variant, Hartigan's algorithm, escapes this trap and reliably recovers the correct clusters. Our experiments indicate the same behavior arises in real datasets beyond the reach of our analysis. In short, we explain a long-standing weakness of a popular clustering method and point to a simple alternative that avoids it.