Hartigan's K-Means Versus Lloyd's K-Means - Is It Time for a Change?
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 1677-1683.
Abstract
Hartigan's method for k-means clustering holds several potential advantages compared to the classical and prevalent optimization heuristic known as Lloyd's algorithm. E.g., it was recently shown that the set of local minima of Hartigan's algorithm is a subset of those of Lloyd's method. We develop a closed-form expression that allows to establish Hartigan's method for k-means clustering with any Bregman divergence, and further strengthen the case of preferring Hartigan's algorithm over Lloyd's algorithm. Specifically, we characterize a range of problems with various noise levels of the inputs, for which any random partition represents a local minimum for Lloyd's algorithm, while Hartigan's algorithm easily converges to the correct solution. Extensive experiments on synthetic and real-world data further support our theoretical analysis.
@inproceedings{ijcai2013p249,
title = {Hartigan's K-Means Versus Lloyd's K-Means - Is It Time for a Change?},
author = {Slonim, Noam and Aharoni, Ehud and Crammer, Koby},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {1677--1683},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/249},
}
TY - CPAPER TI - Hartigan's K-Means Versus Lloyd's K-Means - Is It Time for a Change? AU - Slonim, Noam AU - Aharoni, Ehud AU - Crammer, Koby T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 1677 EP - 1683 UR - https://ijcai.org/proceedings/2013/249 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
