1
$\begingroup$

I'm running into a problem while working on clustering. I work on data with white Gaussian noise. All of the methods I have come across use some sort of random initialization to set up the mean and covariance matrix of the clusters.

My question is: Since the initialization is random, there is a chance that I get a really bad starting point which gives me bad results. How do I deal with this?

One specific initialization I'm considering is the K-Means++ which is better than strictly random because it at least attempts to use the data to make informed initialization, but it too is random in the end.

Do people usually do multiple runs and take the best initialization?

What about that for streaming data?

$\endgroup$
4
$\begingroup$

You have two options:

1) Let the K-means algorithm run for a large number of iterations (if on sklearn, change the max_iter parameter value for sklearn.cluster.KMeans). It will eventually converge to a good result (but it will take more time)

2) Make and "educated guess" for the initial starting point. One way to do that is to transform your data in a space where you know your points can only lie within a specific region: from there, you can evaluate the best seeds where to start the K-means. For a clearer explanation, see this article (for a quick overview, look at the related slides, in particular at step 3, slide number 10)

$\endgroup$
  • $\begingroup$ For (1), what if I don’t want to choose the K ahead of time? I want to discover clusters to be built into the solution. I’m reading about DPMM but even those require random initialization but at least they don’t require K ahead of time. Is this a fundamental trade off? $\endgroup$ – Engineer Dec 11 '19 at 0:09
  • $\begingroup$ I am honestly not aware of any algorithm that can do everything by itself. And if does, might work only for a really small subset of problems. You have always a trade-off between the quality of a method and your knowledge on the data. I personally always try to first explore the data and the problem itself to establish assumptions, and then - based on the assumptions themselves - use the methodology that best fits my needs. $\endgroup$ – Logozoe Dec 11 '19 at 7:54
0
$\begingroup$

Various techniques are used for initialization.

In literature I've seen the suggestion to use k-means to find initial centers. Probably in the Bishop book.

For example mclust in R seems to use hierarchical clustering (which is very expensive) to find initial clusters, then GMM to refine them. Maybe because back then computing all the exp and log functions were more expensive.

ELKI does allow to use k-means++ initialization as you proposed. It also seems to use some good heuristic to choose initial covariance matrixes. This worked very well for me - it converged very nicely in my experiments. I didn't check their code for details (there often are literature references in their code, which is really nice), though.

$\endgroup$

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.