Hartigan’s Method: k-means Clustering without Voronoi


Matus Telgarsky, Andrea Vattani ;
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.

Related Material