0

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.

Edqu3
  • 135
  • 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? – whuber May 05 '16 at 17:54
  • (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. – Edqu3 May 05 '16 at 17:58
  • 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? – whuber May 05 '16 at 18:01
  • The number of possible configurations will eventually stabilize between the k clusters. – Edqu3 May 05 '16 at 18:08
  • But, according to (1), "stabilize" can only mean "converge"! – whuber May 05 '16 at 18:10
  • Try to search the site. That question must be already answered. – ttnphns May 05 '16 at 19:36

0 Answers0