TY - CONF
T1 - A local search approximation algorithm for k-means clustering
T2 - Proceedings of the eighteenth annual symposium on Computational geometry
Y1 - 2002
A1 - Kanungo,Tapas
A1 - Mount, Dave
A1 - Netanyahu,Nathan S.
A1 - Piatko,Christine D.
A1 - Silverman,Ruth
A1 - Wu,Angela Y.
KW - Approximation algorithms
KW - clustering
KW - computational geometry
KW - k-means
KW - local search
AB - In k-means clustering we are given a set of n data points in d-dimensional space Rd and an integer k, and the problem is to determine a set of k points in ÓC;d, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+&egr;)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-&egr;). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.
JA - Proceedings of the eighteenth annual symposium on Computational geometry
T3 - SCG '02
PB - ACM
CY - New York, NY, USA
SN - 1-58113-504-1
UR - http://doi.acm.org/10.1145/513400.513402
M3 - 10.1145/513400.513402
ER -