CODEWITHSUNDEEP
algorithmstatisticsartificial-intelligencek-meansconvergence
Igor Ševo
Igor Ševo

Reputation: 5525

K-means clustering uniqueness of solution

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?

Upvotes: 5

Views: 3552

Answers (2)

ddem
ddem

Reputation: 180

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).

Upvotes: 3

Fred Foo
Fred Foo

Reputation: 363817

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.

Upvotes: 5

Related Questions