Andrew Ng's lecture notes here has the statement "it is possible for k-means to oscillate between a few different clusterings — i.e., a few different values for c and/or μ—that have exactly the same value of J, but this almost never happens in practice.)"

I thought that k-means is theoretically guaranteed to converge to a local optima. If so, how come it would oscillate between different clusterings? Maybe it is guaranteed to converge in terms of the optimized cost function (J), but not in terms of the cluster assignments? Is that the case mentioned above?


During the iterations, $J$, a nonnegative function decreases, hence by monotone convergence theorem, the objective value converges.

However, the convergence of the objective function does not rule out the possibilites of $(\hat{c}, \hat{\mu})$ and $(\tilde{c}, \tilde{\mu})$ having the same objective value.

| cite | improve this answer | |

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.