Convergence Properties of the K-Means Algorithms

Part of Advances in Neural Information Processing Systems 7 (NIPS 1994)

Bibtex Metadata Paper


Léon Bottou, Yoshua Bengio


This paper studies the convergence properties of the well known K-Means clustering algorithm. The K-Means algorithm can be de(cid:173) scribed either as a gradient descent algorithm or by slightly extend(cid:173) ing the mathematics of the EM algorithm to this hard threshold case. We show that the K-Means algorithm actually minimizes the quantization error using the very fast Newton algorithm.