I am trying to cluster the data shown below. The clusters are clearly separable. I've tried k-means and EM clustering (Gaussian mixture), however, both techniques divide the large main cluster into one or more sub-clusters. The main issue is that the clusters have very different numbers of points and overall size. I expect spectral clustering to work - however, I do not have the computational power to do this. Is there some fast clustering method that would work well for this type of data?
(There are about 16,000 pts)

enter image description here

  • $\begingroup$ how are you doing model selection, i.e. choosing number of clusters? $\endgroup$ – DataD'oh Oct 17 '17 at 13:17
  • $\begingroup$ The overall goal is separate the central main cluster from the surrounding artifact. I've manually tried n=3 through n=6 to see if any value creates good separation. It is fine for me to have manual n selection. $\endgroup$ – Joey Costello Oct 17 '17 at 13:34

A good implementation of Gaussian mixture modeling should be able to separate this fatal. It probably depends on the initialization.

The better choice probably is DBSCAN. Choose an epsilon smaller than the gap between the clusters and Minpts 5 to 10. Your plot looks very much like the "density connected" clusters expected by DBSCAN.


In small dimension, density clustering often works very well. Possibilities:

DBSCAN is more popular. It is faster with an accelerating data structure, and I guess it's provided by most implementations.

Mean-shift could do well, complexity is essentially $O(N^2)$ for a basic implementation. For 16000 pts, I think this will be ok anyway.

Density clustering is based on a sort of connectedness heuristic: if $a$ and $b$ can be connected by a path surrounded by a sufficient density of points, then they are in the same cluster. I guess this would work with your data.

  • $\begingroup$ DBSCAN sensitive to outliers? Where did you read that? It's one of the least sensitive methods. The N is for Noise - it's designed to work on noisy data. $\endgroup$ – Anony-Mousse Oct 17 '17 at 21:18
  • $\begingroup$ I guess I confused with another thing. Revised. $\endgroup$ – Benoit Sanchez Oct 18 '17 at 8:16

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.