I was asked to prove why having a finite amount of site to cluster assignments eventually leads to convergence.

In the Lloyd version of K-means, we minimize the distortion measure at every iteration until convergence. Graphically, I understand this as having the centroids and sites more compact until no new cluster memberships are reassigned. I understand that K-means achieves local minima via an EM approach on cluster centroids. I fail to see how the amount of site to cluster assignments ensure convergence.

$r_{nk} = 1$ when the $n^{th}$ site is in the $k^{th}$ cluster, 0 otherwise.

  • $\begingroup$ Let me check my understanding at a high level: (1) in each step of this algorithm, either the "distortion measure" (strictly) decreases or else convergence is declared. (2) There are finitely many "sites" to cluster. (3) Any solution--a "cluster assignment"--is a partition of the sites (into "clusters"). Are these characterizations correct? $\endgroup$
    – whuber
    May 5, 2016 at 17:54
  • $\begingroup$ (1) I would like to think that It strictly decreases. (2) right, by sites I meant a subset of data points assigned to some cluster. (3) that's right. $\endgroup$
    – Edqu3
    May 5, 2016 at 17:58
  • $\begingroup$ So, since the measure strictly decreases in each iteration, it will be impossible to revisit any configuration, right? Thus, if convergence did not occur, what would that tell you about the number of possible configurations? $\endgroup$
    – whuber
    May 5, 2016 at 18:01
  • $\begingroup$ The number of possible configurations will eventually stabilize between the k clusters. $\endgroup$
    – Edqu3
    May 5, 2016 at 18:08
  • $\begingroup$ But, according to (1), "stabilize" can only mean "converge"! $\endgroup$
    – whuber
    May 5, 2016 at 18:10


Browse other questions tagged or ask your own question.