1
$\begingroup$

I use Lloyd's algorithm for clustering. Since it relies on a random initialization and Lloyd's algorithm can get stuck in local optima of the k-means objective function, I have to run it several times.

How many different random initializations should I perform with Lloyd's algorithm to obtain the optimal clustering with X% of confidence? Or at least is there any rule of thumb advising for a decent number of random initializations?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

What good is finding the global optimum? You optimize some number, not the actual result.

k-means is based on assumptions that won't hold on real data anyway.

So it's not much more than a heuristic anyway.

Why find the gloabl optimum of a heuristic?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well I would like to minimize the within-cluster sum of squares. Although it's indeed not a perfect metric, I prefer to be closer far from its global minimum. $\endgroup$
    – Franck Dernoncourt
    Dec 10, 2013 at 18:53
  • $\begingroup$ If your data is so that k-means works reasonably well, a local minimum will be about as good as the global minimum. When you get very different results by running k-means multiple times, then your data does not fit the algorithm. (For example, you might be trying to use k-means on binary data. Don't.) $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 10, 2013 at 18:56

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.