I would like to automatically determine the number of clusters for K-means. I have read that elbow method could be used for that.

The thing that confuses me is - I have to rerun algorithm while increasing number of clusters.

How can I know how much does the random initialization influence the decrease of function? Maybe the decrease is greater because of better initialization?

I have tried doing something like this, but I'm getting different number of clusters when I run this multiple times.

Am I missing something, what should I do?



k-means results can of course vary because of randomized initialization.

However, that generally indicates that the result is not good, when you observe this effect.

If your aim is fining a good value of $k$, it should be stable, and still better than the random results you see with a worse $k$.

For many applications, the quality of the result does not make much of a difference, IMHO. You might just pick a $k$ as desired for your application (or computational reasons), and live with the result.

Also have a look at X-means, which aims at choosing this parameter automatically.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your answer. The thing is, I have some kind of streaming data, that I cluster periodically, so the number of clusters may change. That is why I need to determine number of clusters dynamically. I have read about k-means++, that differs in initialization,if you are familiar with it,in your opinion,can I expect better results with it,while rerunning the algorithm multiple times to find optimal number of clusters? $\endgroup$ – Kobe-Wan Kenobi Oct 5 '14 at 19:43
  • $\begingroup$ You can expect better results by the standards of k-means. Which aren't high... It's more of a quantization than a structure discovery algorithm. Seriously, have a look at x-means. It discusses two quality measures for deciding when to split clusters and when not. $\endgroup$ – Has QUIT--Anony-Mousse Oct 5 '14 at 21:16
  • $\begingroup$ Thanks for your answer. The thing is, I'm using Mahout since I'm working with Big Data,so I'm currently trying to use what is given,not to implement from scratch.But I will definitely consider x-means.My current approach is to use Mahouts Streaming K Means implementation,and to give a shot to elbow method,since I see no better solution to determine the number of clusters with as much reuse as possible.If you have any idea,any suggestion would be great.Thanks,again. $\endgroup$ – Kobe-Wan Kenobi Oct 6 '14 at 8:54
  • $\begingroup$ Try using anything else but Mahout. In my experiments it was awfully slow. So slow, that it wouldn't scale for me - using a fast tool like ELKI on a single (large) machine would outperform the whole cluster for me: ELKI took 10 minutes on a single core, Mahout took 1 hour per iteration on 20 cores. Benchmark yourself! $\endgroup$ – Has QUIT--Anony-Mousse Oct 6 '14 at 9:34
  • $\begingroup$ Thank you very much for your advice,I appreciate it.Can you please tell me if you had any experience with Spark and its MLib library?Since the purpose is Big Data,I would really like to implement it on a distributed system...because of speed,of course. $\endgroup$ – Kobe-Wan Kenobi Oct 6 '14 at 9:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.