Hartigan's Method: k-means Clustering without Voronoi

Matus Telgarsky, Andrea Vattani ; JMLR W&CP 9:820-827, 2010.

Abstract

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.