# Clustering algorithm for a data set with at most N clusters

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.

Thanks!

• 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? – Pedro Sep 18 '13 at 22:09
• look at kmeans++. It guarantees logn nearness to optimal configuration. – Ashish Negi Sep 19 '13 at 10:47
• @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. – anjruu Sep 19 '13 at 12:44
• @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++? – anjruu Sep 19 '13 at 12:48
• I'd look for some hierarchical (divisive) clustering, the restriction would fit naturally as part of the stopping criterion. – 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.
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}$.