Hartigan's method: κ-means clustering without Voronoi

Matus Telgarsky, Andrea Vattani

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)820-827
Number of pages8
JournalJournal of Machine Learning Research
StatePublished - 2010
Event13th International Conference on Artificial Intelligence and Statistics, AISTATS 2010 - Sardinia, Italy
Duration: May 13 2010May 15 2010

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Hartigan's method: κ-means clustering without Voronoi'. Together they form a unique fingerprint.

Cite this