Theoretical Analysis of the $k$-Means Algorithm - A Survey
arXiv:1602.08254v1100 citations
Originality Synthesis-oriented
AI Analysis
It is an incremental survey for researchers interested in clustering algorithms, summarizing existing work without introducing novel methods.
This paper surveys recent theoretical results on the k-means algorithm, analyzing its running time and approximation quality to provide insights for improvement, without presenting new experimental findings.
The $k$-means algorithm is one of the most widely used clustering heuristics. Despite its simplicity, analyzing its running time and quality of approximation is surprisingly difficult and can lead to deep insights that can be used to improve the algorithm. In this paper we survey the recent results in this direction as well as several extension of the basic $k$-means method.