2
$\begingroup$

For a collection of points in $\mathbb{R}^n$, is there a statistic that I can compute which will estimate the number of clusters with some level of confidence?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
4
$\begingroup$

This is an age-old question, which actually does not have (I think even cannot have) a definite answer, because first you need to define what you mean by a cluster and so on. A famous saying in this regard is that "cluster is in the eye of a beholder". It is easy to construct examples where somebody could see one cluster, but somebody else more than one.

This being said, the MDL (minimum description length) principle would lead you to devise (IMHO) a clustering cost function in a most principled way, which by optimizing you could the find the cluster assignments and number of clusters simultaneously. For multinomial data you can see following: P.Kontkanen, P.Myllymäki, W.Buntine, J.Rissanen, H.Tirri, An MDL Framework for Data Clustering. In Advances in Minimum Description Length: Theory and Applications, edited by P. Grünwald, I.J. Myung and M. Pitt. The MIT Press, 2005.

The intuitively-appealing idea behind MDL clustering is that by clustering you create a model of the data. So the assumption is that a very good model is one that lets you compress the data well.

Anyway MDL might not be easy to apply, if you are looking for a practical way to detect the number of clusters. BIC (Bayesian information criteria) and the F-ratio have proven to work OK in practice.

Improve this answer
$\endgroup$
11
$\begingroup$

I don't know if this is the most effective answer, but it has to be one of the coolest:

Barcodes: the persistent topology of data

It lets you estimate not only the number of connected components but also the higher Betti numbers. (For instance, if you take a random sample of enough points from an annulus, you will be able to measure both H0 = Z and H1 = Z.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't think persistent homology actually would help with this. The question doesn't seem to be about data analysis, but clustering of data. $\endgroup$
    – Josh
    Commented Oct 21, 2009 at 11:37
  • $\begingroup$ Isn't persistent 0th homology pretty relevant to the OP's problem? $\endgroup$
    – Darsh Ranjan
    Commented Oct 21, 2009 at 16:06
  • $\begingroup$ Yes, that's true. $\endgroup$
    – Josh
    Commented Oct 21, 2009 at 17:48
  • $\begingroup$ Actually, this "Barcodes" paper points to projection of high-dimensional datasets into lower dimensions and then recognizing shapes. The projection vector used to decrease the dimensionality of the data points has a strong effect on the possible separability of the clusters. I actually don't know if there's a good way to pre-estimate the number of expected clusters without considering a priori factors about what the data set it. But the paper does not necessarily address what the best projective vector might be. $\endgroup$
    – ABh
    Commented Aug 28, 2010 at 21:43
7
$\begingroup$

Carlsson has developed methods from applied topology to do clustering work. Robert Ghrist called a talk about this "Clusterfunctor" since it involves a functor from metric spaces to "persistent sets". It's talked about in Topology and Data, a survey article about using topology to do data analysis.

Improve this answer
$\endgroup$
4
$\begingroup$

I think that for computing a level of confidence you need a model of clusters, for example a gaussian mixture model.

If the level of confidence is not an issue and you need simply the "right" number of clusters I would repeat what Ville said plus the following article:

Estimating the number of clusters in a dataset via the Gap statistic (2000) Tibshirani, Walther, Hastie http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.6664

Improve this answer
$\endgroup$
4
$\begingroup$

There is a whole research field on this, and the answers so far have only highlighted a few of the specific algorithms developed. Check out this Wikipedia article on cluster analysis for an overview and some references.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .