I know that K-means algorithm stops when the cluster assignment does not change or just changes a little. Apart from that, and defining the maximum number of iterations, is there any other stopping condition?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Another most commonly used stopping criterion is the maximum number of iterations. Also relevant in this context: stackoverflow.com/questions/30195806/… $\endgroup$– Nikolas RiebleCommented Feb 9, 2017 at 13:29
-
$\begingroup$ Oh I forgot to mention that. Apart from the maximum number of iterations as well. That criteria does not seem to be very convincing to me. $\endgroup$– fooCommented Feb 9, 2017 at 13:55
-
2$\begingroup$ Knowing that K-Means is not a convex problem, the result will most likely be suboptimal. Therefore restricting by maximum number of iterations allows efficient (fast) repetitive computation of K-means results and simply using the best in the end. $\endgroup$– Nikolas RiebleCommented Feb 9, 2017 at 14:03
-
2$\begingroup$ The answer to your new question therefore simply is: No. $\endgroup$– Nikolas RiebleCommented Feb 9, 2017 at 14:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
First of all, there are some much more clever algorithms than the "standard" algorithm. These can literate very fast at the end, so it's well affordable to iterate until convergence.
The common stopping conditions I have seen:
Convergence. (No further changes)
Maximum number of iterations.
Variance did not improve by at least x
Variance did not improve by at least x * initial variance
If you use MiniBatch k-means, it will not converge, so you need one of the other criteria. The usual one is the number of iterations.
answered Feb 9, 2017 at 22:28
-
$\begingroup$ Thanks very much. Btw, beside k-means-like algorithms, what are some other iterative algorithms that do converge? $\endgroup$– fooCommented Feb 12, 2017 at 11:13
-
1$\begingroup$ PAM, for example. Check out the convergence proofs to understand why. $\endgroup$ Commented Feb 13, 2017 at 19:22