# Algorithm for deriving multiple clusters

Suppose I have a set of data (with 2-dimensional feature space), and I want to obtain clusters from them. But I do not know how many clusters will be formed.

Yet, I want separate clusters (The number of clusters is more than 2).

I figured that k means of k medoid cannot be used in this case. Nor can I use hierarchical clustering. Also since there is no training set hence cannot use KNN classifier to any others (supervised learning cannot be used as no training set). I cannot use OPTICS algorithm as I do not want to specify the radius (I don't know the radius)

Is there any machine learning technique that would give me multiple clusters (distance based clustering) that deals well with outlier points too?

This should be the output:

• With 2D features you can visualize your data, correct? Everything will be much clearer then. And why "nor can I use hierarchical clustering"? Commented May 29, 2015 at 8:08
• Yes I can visualize the data.... Hierarchical clustering is going to give me l clusters and subclusters ..... Oh so are you suggesting that even if I get subclusters , in order to obtain my clusters I should repeatedly subtract a subcluster from its parent cluster? Commented May 29, 2015 at 8:11
• I just tried to visualize it, but identification of the separate clusters is not possible.... Commented May 29, 2015 at 8:15
• With hierarchical clustering you make a dendogram. Then you cut it at specific level, which you estimate reasonable from the dendogram. The precedure is very clear and gives you clusters. No "subclusters", no substraction. If you post your visualization (plot of your actual data that you are trying to cluster), it will be easier to tell more. Commented May 29, 2015 at 8:18

I don't think that EM clustering algorithms like k-means and Gaussian mixture models are quite what you're looking for. There are definitely other algorithms that don't require one to pick a number of clusters. My personal favorite (most of the time) is called mean-shift-clustering. You could find a great little blog post about it here, and it has a good implementation in python's scikit-learn library.

• I just read mean shift clustering , and I seem to like it...I will read more and let you know.. thanks a lot! Commented Jun 1, 2015 at 11:45
• Be aware that in the case of Mean Shift Clustering you are replacing one parameter (number of clusters) by another one (kernel radius) that in fact will indirectly determine the final number of clusters. Therefore, model selection is still required. Commented Jul 28, 2015 at 13:05

The fact is that you could use any of the algorithms you mentioned, and in general any algorithm that requires to set the number of clusters as a parameter (or any other parameter that indirectly sets the final number of clusters, like the threshold in a hierarchical clustering algorithm.)

The solution to your problem is model selection. Model selection methods evaluate different clustering solutions, and select the one that optimizes a given criterion.

For instance, in the case of K-means, you could find a solution for a range of k values, and keep the one that maximizes any cluster validation measure (see the Wikipedia entry for cluster analysis to read about some examples of cluster validation measures).

There are automatic and more complex approaches (one specific example is "Automatic Cluster Number Selection Using a Split and Merge K-Means Approach" by Muhr, M. and Granitzer, M., but this is just an example). These methods use cluster validation measures to automatically split or merge clusters, but the idea is basically the same.

The radius in OPTICS is a maximum value, and it can be set to infinity! So you don't need to know it, and you should give OPTICS as well as DBSCAN a try. There are heuristics to choose their parameters, if you know your data.

Similarly, try hierarchical clustering. There are good heuristics on how to extract flat partitions out of it.

You want something that handles noise well - this calls for DBSCAN, OPTICS and HAC.

If the data are suitable, you can use Gaussian mixture modeling, fit via an EM algorithm to estimate various separate Gaussian clusters. When determining the number of clusters, you can use something like BIC (or other penalized likelihood criterion) to penalize based on the number of parameters that you are estimating. Then simply search over different numbers of clusters and choose the number with the lowest BIC. This is a form of model-based clustering.

You should be able to use the mclust package in R to do this: mclust: Gaussian Mixture Modelling for Model-Based Clustering, Classification, and Density Estimation.