Proof of convergence of k-means

Question

For an assignment I've been asked to provide a proof that k-means converges in a finite number of steps.

This is what I've written:

In the following, $C$ is a collection of all the cluster centres. Define an “energy” function $$E(C)=\sum_{\mathbf{x}}\min_{i=1}^{k}\left\Vert \mathbf{x}-\mathbf{c}_{i}\right\Vert ^{2}$$ The energy function is nonnegative. We see that steps (2) and (3) of the algorithm both reduce the energy. Since the energy is bounded from below and is constantly being reduced it must converge to a local minimum. Iteration can be stopped when $E(C)$ changes at a rate below a certain threshold.

Step 2 refers to the step which labels each data point by its closest cluster centre, and step 3 is the step where the centres are updated by taking a mean.

This is not sufficient to prove convergence in a finite number of steps. The energy can keep getting smaller but it doesn't rule out the possibility that the centre points can jump about without changing the energy much. In other words there might be multiple energy minima and the algorithm can jump about between them, no?

Answer 1

First, there are at most $k^N$ ways to partition $N$ data points into $k$ clusters; each such partition can be called a "clustering". This is a large but finite number. For each iteration of the algorithm, we produce a new clustering based only on the old clustering. Notice that

1. if the old clustering is the same as the new, then the next clustering will again be the same.
2. If the new clustering is different from the old then the newer one has a lower cost

Since the algorithm iterates a function whose domain is a finite set, the iteration must eventually enter a cycle. The cycle can not have length greater than $1$ because otherwise by (2) you would have some clustering which has a lower cost than itself which is impossible. Hence the cycle must have length exactly $1$. Hence k-means converges in a finite number of iterations.

Answer 2

To add something: Whether the algorithm converges or not also depends on your stop criterion. If you stop the algorithm once the cluster assignments do not change any more, then you can actually prove that the algorithm does not necessarily converge (provided that the cluster assignment does not have a deterministic tie breaker in case multiple centroids have the same distance).

Here you have 8 data-points (dots) and two centroids (red crosses). Now the green-data points have same distance to both the left and the right centroid. The same holds for the blue data-points. Let us assume that the assignment function is not deterministic in this case. Further we assume that at iteration 1 the green dots get assigned to the left cluster and the blue dots get assigned to the right cluster. Then we update the centroids. It turns out that they in fact stay in the same spot. (this is an easy calculation. For the left centroid you average the coordinates of the two left black dots and the two green dots -> (0, 0.5). Same for the right centroid).

Then at iteration 2 the situation looks again the same, but now we assume that our (in case of ties) non-deterministic assignment function assigns the green dots to the right cluster and the blue dots to the left cluster. Again the centroids won't change.

Iteration 3 is again the same as iteration 1. Thus we have a case where the cluster assignments continuously change and the algorithm (with this stop criterion) does not converge.

Essentially we only have a guarantee that each step in k-means reduces the cost or keeps it the same (i.e. $\leq$ instead of $\lt$). This allowed me to construct a case where the cost stays the same through iterates, even though the assignment still changes.