Hartigan’s Method: k-means Clustering without Voronoi
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:820-827, 2010.
Hartigan’s method for $k$-means clustering is the following greedy heuristic: select a point, and optimally reassign it. This paper develops two other formulations of the heuristic, one leading to a number of consistency properties, the other showing that the data partition is always quite separated from the induced Voronoi partition. A characterization of the volume of this separation is provided. Empirical tests verify not only good optimization performance relative to Lloyd’s method, but also good running time.