Termination of K-means algorithm

Theoretically, k-means should terminate when no more pixels are changing classes. There are proofs of termination for k-means. These rely on the fact that both steps of k-means (assign pixels to nearest centers, move centers to cluster centroids) reduce variance. So eventually, there is no move to make that will continue to reduce the variance.

Running to completion (no pixels changing classes) may require a large number of iterations. In software, we typically terminate when one of the following criteria is met:

1. Terminate after fewer than n pixels change classes (we use n=1000 for 256x256 pixel images)
2. Terminate after J iterations. We use 50.

This page is maintained by Prof. Miriam Leeser
Last updated September 16, 1999.
Email: mel@ece.neu.edu