Question

Let a configuration of the k-means algorithm correspond to the k way partition generated by the clustering at the end of each iteration. Is it possible for the k-means algorithm to revisit a configuration? Justify how your answer proves that the k-means algorithm converges in a finite number of steps.

Answer 1

Since the k means algorithm converges if the k way partition does not change in successive iterations, thus the k way partition has to change after every iteration. As the mean squared error monotonically decreases it is thus impossible to revisit a configuration. Thus eventually the k means algorithm will run out of configurations, and converge.

NB: The maximum no of iterations corresponds to the no of k way partitions possible on a set of n objects : S(n,k) where S are Stirling numbers of the 2^nd kind.