Hartigan's method: κ-means clustering without Voronoi

Matus Jan Telgarsky, Andrea Vattani

Research output: Contribution to journalArticlepeer-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
Externally publishedYes

ASJC Scopus subject areas

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

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

Cite this