3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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.
    Commented Nov 30, 2012 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
    Commented Nov 30, 2012 at 18:43

1 Answer 1

Reset to default
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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