How to decide on the correct number of clusters?

Question

We find the cluster centers and assign points into different bins in k-means clustering which is a very simple algorithm and is found almost in every machine learning material on the net. But the lacking and more important part in my opinion is the choice of correct k. What is the best value for it? And, what is meant by saying best?

I use MATLAB for scientific computing and looking at silhouette plots is given as a way to decide on the correct number of clusters as discussed here. But, I would be more interested in Bayesian approaches. Any suggestions are appreciated.

Answer 1

This has been asked a couple of times on stackoverflow: here, here and here. You can take a look at what the crowd over there thinks about this question (or a small variant thereof).

Let me also copy my own answer to this question, on stackoverflow.com:

Unfortunately there is no way to automatically set the "right" K nor is there a definition of what "right" is. There isn't a principled statistical method, simple or complex that can set the "right K". There are heuristics, rules of thumb that sometimes work, sometimes don't.

The situation is more general as many clustering methods have these type of parameters, and I think this is a big open problem in the clustering/unsupervised learning research community.

Answer 2

Firstly a caveat. In clustering there is often no one "correct answer" - one clustering may be better than another by one metric, and the reverse may be true using another metric. And in some situations two different clusterings could be equally probable under the same metric.

Having said that, you might want to have a look at Dirichlet Processes. Also see this tutorial.

If you begin with a Gaussian Mixture model, you have the same problem as with k-means - that you have to choose the number of clusters. You could use model evidence, but it won't be robust in this case. So the trick is to use a Dirichlet Process prior over the mixture components, which then allows you to have a potentially infinite number of mixture components, but the model will (usually) automatically find the "correct" number of components (under the assumptions of the model).

Note that you still have to specify the concentration parameter $\alpha$ of the Dirichlet Process prior. For small values of $\alpha$, samples from a DP are likely to be composed of a small number of atomic measures with large weights. For large values, most samples are likely to be distinct (concentrated). You can use a hyper-prior on the concentration parameter and then infer its value from the data, and this hyper-prior can be suitably vague as to allow many different possible values. Given enough data, however, the concentration parameter will cease to be so important, and this hyper-prior could be dropped.

Answer 3

Cluster sizes depend highly on both your data and what you're gonna use the results for. If your using your data for splitting things into categories, try to imagine how many categories you want first. If it's for data visualization, make it configurable, so people can see both the large clusters and the smaller ones.

If you need to automate it, you might wanna add a penalty to increasing k, and calculate the optimal cluster that way. And then you just weight k depending on whether you want a ton of clusters or you want very few.

Answer 4

You can also check Unsupervised Optimal Fuzzy Clustering which deal with the problem you have mentioned (finding the number of clusters) which a modified version of it is implemented here

Answer 5

I have managed to use the "L Method" to determine the number of clusters in a geographic application (ie. essentally a 2d problem although technically non-Euclidean).

The L Method is described here: Determining the Number of Clusters/Segments in Hierarchical Clustering/Segmentation Algorithms Stan Salvador and Philip Chan

Essentially this evaluates the fit for various values of k. An "L" shaped graph is seen with the optimum k value represented by the knee in the graph. A simple dual-line least-squares fitting calculation is used to find the knee point.

I found the method very slow because the iterative k-means has to be calculated for each value of k. Also I found k-means worked best with multiple runs and choosing the best at the end. Although each data point had only two dimensions, a simple Pythagorean distance could not be used. So that's a lot of calculating.

One thought is to skip every other value of k (say) to half the calculations and/or to reduce the number of k-means iterations, and then to slightly smooth the resulting curve to produce a more accurate fit. I asked about this over at StackOverflow - IMHO, the smoothing question remains an open research question.

Answer 6

I use the Elbow method:

• Start with K=2, and keep increasing it in each step by 1, calculating your clusters and the cost that comes with the training. At some value for K the cost drops dramatically, and after that it reaches a plateau when you increase it further. This is the K value you want.

The rationale is that after this, you increase the number of clusters but the new cluster is very near some of the existing.

Answer 7

You need to reconsider what k-means does. It tries to find the optimal Voronoi partitioning of the data set into $k$ cells. Voronoi cells are oddly shaped cells, the orthogonal structure of a Delaunay triangulation.

But what if your data set doesn't actually fit into the Voronoi scheme?

Most likely, the actual clusters will not be very meaningful. However, they may still work for whatever you are doing. Even breaking a "true" cluster into two parts because your $k$ is too high, the result can work very well for example for classification. So I'd say: the best $k$ is, which works best for your particular task.

In fact, when you have $k$ clusters that are not equally sized and spaced (and thus don't fit into the Voronoi partitioning scheme), you may need to increase k for k-means to get better results.

Answer 8

As no one has pointed it yet, I thought I would share this. There is a method called X-means, (see this link) which estimates proper number of clusters using Bayesian information criterion (BIC). Essentially, this would be like trying K means with different Ks, calculating BIC for each K and choosing the best K. This algorithm does that efficiently.

There is also a weka implementation, details of which can be found here.