Roy Lederman

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 re…