I have a data set that I'm trying to cluster, and I know that there will be at most N clusters (based on some physical properties of the thing the data set represents). However, there could be as few as 1 cluster. The clusters themselves are pretty tight, and the cluster separation is pretty large (the inter-cluster distance is an order of magnitude larger than the intra-cluster distance, at least). This is down-stream of other processing steps, so I'm (reasonably) confident that extreme outliers have been removed. N is generally 1, 2, or 4. Is there a well-known algorithm for this case?

I thought about using K-Means, run it with $K \in \{1,...,N\}$, and somehow choose the best result (maybe the result which maximizes the intercluster to intracluster distance ratio, or something), but the criteria I've come up with for distinguishing the best run have all seemed ad hoc to me.


  • 1
    $\begingroup$ Do you have a more specific description for your problem? I.e. what exactly are you trying to cluster? Points in space? Nodes in a graph? What is you measure of goodness? What distinguishes a good clustering from a bad one? $\endgroup$
    – Pedro
    Sep 18 '13 at 22:09
  • $\begingroup$ look at kmeans++. It guarantees logn nearness to optimal configuration. $\endgroup$ Sep 19 '13 at 10:47
  • $\begingroup$ @Pedro I'm clustering points in a 6-dimensional space using the Euclidean distance. A good clustering is one that has a valid number of clusters (between 1 and N), groups points that are close to each other into the same cluster, but does not join two points that are far away into the same cluster. I know that's a bit wishy-washy, but given the fact that I know the intercluster distance will be so much larger than the intracluster distance, I think it's not too bad of a definition. $\endgroup$
    – anjruu
    Sep 19 '13 at 12:44
  • $\begingroup$ @ASHISHNEGI My understanding is that k-means++ will help choose the initial seeds for k-means, but still requires a single parameter K that represents the number of clusters it will find. If I use k-means, I'll use the k-means++ initialization scheme, but I don't think that particular algorithm addresses having an indeterminate numbers of clusters within a known bound. Unless I'm totally wrong and don't understand the point of k-means++? $\endgroup$
    – anjruu
    Sep 19 '13 at 12:48
  • $\begingroup$ I'd look for some hierarchical (divisive) clustering, the restriction would fit naturally as part of the stopping criterion. $\endgroup$
    – leonbloy
    Sep 19 '13 at 14:16

You might take a look at Bayesian Clustering. This seems like a good fit because you can start with exaclty N clusters, and the ones that are not needed will drop out as your solution converges. If your data is already well separated, I expect that this method would converge rather quickly. For an example of this, see [1] chapter 10.

[1] Christopher M. Bishop, Pattern Recognition and Machine Learning


You could try a recursive approach in which given a set of points $S$, you first compute the covariance matrix $C_S$ of the points' coordinates.

You can then use the largest eigenvector $v_\mathsf{max}$ of $C_S$ as your search direction, i.e. for each point $x_i$, compute $\xi_i = v_\mathsf{max}\cdot x_i$, which reduces your problem to a one-dimentional clustering of the $\xi_i$ values, which can be solved by sorting the $\xi_i$ and splitting them at the largest gap between two entries, giving you two subsets $S_\mathsf{left}$ and $S_\mathsf{right}$.

You can then proceed recursively as long as the clusters produced are sufficiently well separated.

Note that this approach will fail for pathological cases, e.g. if the particles are on circle, but then so will most approaches. The main advantage is that it is independent of the number of dimensions used.


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.