Hartigan’s Method: K-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.
Cite
Text
Telgarsky and Vattani. "Hartigan’s Method: K-Means Clustering Without Voronoi." Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.Markdown
[Telgarsky and Vattani. "Hartigan’s Method: K-Means Clustering Without Voronoi." Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.](https://mlanthology.org/aistats/2010/telgarsky2010aistats-hartigans/)BibTeX
@inproceedings{telgarsky2010aistats-hartigans,
title = {{Hartigan’s Method: K-Means Clustering Without Voronoi}},
author = {Telgarsky, Matus and Vattani, Andrea},
booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics},
year = {2010},
pages = {820-827},
volume = {9},
url = {https://mlanthology.org/aistats/2010/telgarsky2010aistats-hartigans/}
}