Hartigan’s Method: k-means Clustering without Voronoi

Matus Telgarsky, Andrea Vattani
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v9-telgarsky10a, 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}, pages = {820--827}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/telgarsky10a/telgarsky10a.pdf}, url = {https://proceedings.mlr.press/v9/telgarsky10a.html}, 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.} }
Endnote
%0 Conference Paper %T Hartigan’s Method: k-means Clustering without Voronoi %A Matus Telgarsky %A Andrea Vattani %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-telgarsky10a %I PMLR %P 820--827 %U https://proceedings.mlr.press/v9/telgarsky10a.html %V 9 %X 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.
RIS
TY - CPAPER TI - Hartigan’s Method: k-means Clustering without Voronoi AU - Matus Telgarsky AU - Andrea Vattani BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-telgarsky10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 820 EP - 827 L1 - http://proceedings.mlr.press/v9/telgarsky10a/telgarsky10a.pdf UR - https://proceedings.mlr.press/v9/telgarsky10a.html 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. ER -
APA
Telgarsky, M. & Vattani, A.. (2010). Hartigan’s Method: k-means Clustering without Voronoi. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:820-827 Available from https://proceedings.mlr.press/v9/telgarsky10a.html.

Related Material