K-means clustering uniqueness of solution

Question

Does the k-means clustering algorithm always yield the same solution? The initialization is supposed to be random, so does the clustering converge to the same result regardless of the initialization?

Answer 1

The initialization is supposed to be random, so does the clustering converge to the same result regardless of the initialization?

Quite the contrary. If the k-means problem were a nice, convex optimization problem, we wouldn't be randomly initializing it, since simply starting at (0,0,...,0) would give the right answer.

The reason for random initialization is exactly that you can get different solutions by trying different random seeds, then pick the best one when all your k-means runs are done. Ten runs is a good rule of thumb for many applications.

Finding the global minimum of the k-means problem is NP-hard in general. The common algorithm is really a heuristic.

Answer 2

Actually the initialization of the k-means algorithm has a clear influence on the obtained result. To prevent a 'bad' initialization you could resort to the k-means++ algorithm which overcomes this problem. You can check this out in wikipedia (http://en.wikipedia.org/wiki/K-means%2B%2B).