Hartigan's method: κ-means clustering without Voronoi

Matus Telgarsky; Andrea Vattani

Hartigan's method: κ-means clustering without Voronoi

Matus Telgarsky, Andrea Vattani

Computer Science

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English (US)
Pages (from-to)	820-827
Number of pages	8
Journal	Journal of Machine Learning Research
Volume	9
State	Published - 2010
Event	13th International Conference on Artificial Intelligence and Statistics, AISTATS 2010 - Sardinia, Italy Duration: May 13 2010 → May 15 2010

ASJC Scopus subject areas

Control and Systems Engineering
Software
Statistics and Probability
Artificial Intelligence

Cite this

@article{8d469275aa9946e4bafd33ab8d6f3267,

title = "Hartigan's method: κ-means clustering without Voronoi",

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.",

author = "Matus Telgarsky and Andrea Vattani",

year = "2010",

language = "English (US)",

volume = "9",

pages = "820--827",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

note = "13th International Conference on Artificial Intelligence and Statistics, AISTATS 2010 ; Conference date: 13-05-2010 Through 15-05-2010",

}

TY - JOUR

T1 - Hartigan's method

T2 - 13th International Conference on Artificial Intelligence and Statistics, AISTATS 2010

AU - Telgarsky, Matus

AU - Vattani, Andrea

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84862296936&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862296936&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:84862296936

SN - 1532-4435

VL - 9

SP - 820

EP - 827

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

Y2 - 13 May 2010 through 15 May 2010

ER -

Hartigan's method: κ-means clustering without Voronoi

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this