I have a clustering algorithm which works iteratively like K-means, but there are some constraints on cluster sizes with lower and upper thresholds.

Do you know any convergence proofs of K-means in general? Would they be applicable in the case of this alternative algorithm?

  • 1
    $\begingroup$ It would probably help to know a bit more about how your implementation differs from k-means! Does it just have to do with the constraints on cluster sizes? $\endgroup$ – Kyle. Nov 30 '12 at 18:20
  • $\begingroup$ Yes, there are only some constraints for cluster sizes (lower and upper bound thresholds). Of course I could not assign my records in the same manner of k-means to the most nearest cluster, but I have to solve a linear program to find the best candidates for given clusters $\endgroup$ – remo Nov 30 '12 at 18:43

IIRC the proof works by showing that the variance decreases in each step. And as there only is a finite number of possible assignments (and they are an ordered set, ordered by variance), it thus must stop at some point. Nothing very spectacular, actually. I don't know if there is a convergence proof for fuzzy c-means or EM that have an infinite number of possible states.

Which BTW is why k-Means doesn't work with arbitrary distance functions: recomputing the means is reducing the distances for Euclidean, but may not work for other distance functions. However if it doesn't hold that the mean reduces variance, then the convergence proof fails.

You might be interested in this recent G+ post: https://plus.google.com/u/0/101988970685633977359/posts/PNGY1mZZn9E which is also about a k-means variation with size constraints.

  • $\begingroup$ Thank you very much. I'm following the link. Excuse me, I could not vote you up, because I'm newbie. $\endgroup$ – remo Dec 1 '12 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.