How to compare dbscan clusters / choose epsilon parameter

I am currently trying to make a DBSCAN clustering using scikit learn in python. I would like to compare the different outputs when varying the epsilon parameter in order to choose the right epsilon parameter. I took as an example the iris dataset.

In order to compare clusters I thought about trying to cluster with epsilon within a range (ex : 0.1, 0.2, ..., 1). Now, when I run a kmeans or a hierarchical clustering I can choose my k value by checking the gap statistic for example, or by looking at inertia and choosing a k for which there is an 'elbow' on the inertia vs k plot.

My problem is that I assume this will not work anymore because the total number of points within all the clusters is not constant in DBSCAN. Indeed, depending on epsilon, the number of 'noisy sample' unclassified points will vary. As a result, I may have only a few points for a low epsilon, resulting on a very small Inertia which would be biased. I could consider gap statistic because I may be able to generate random samples with the right size each time. But I wonder if I will then leave the validity framework of the paper and I'm not sure the different clustering can still be compared.

Has anyone an idea on how to compare different total sizes clustering, and more precisely the results of dbscan for different epsilon? Would silhouette coefficient work or is it total size sensitive too?

Inertia is only a sensible measure for spherical clusters. I.e. not for DBSCAN. Similar reasonings apply for most internal measures: most are designed around centroid-based cluster models, not arbitrarily shaped clusters.

For DBSCAN, a sensible measure would be density-connectedness. But that needs the same parameters as DBSCAN already uses.

A recommended approach for DBSCAN is to first fix minPts according to domain knowledge, then plot a $k$-distance graph (with $k=minPts$) and look for an elbow in this graph. Alternatively, when having a domain knowledge to choose epsilon (e.g. 1 meter, when you have a geo-spatial data and know this is a reasonable radius), you can do a density plot for this radius and look for an elbow there.

Or you just use OPTICS, where epsilon only serves as an upper limit to boost performance.

• Ok thanks, but let's say, want to automate a small programm that takes several clustering models (kmeans, hierarchical, dbscan) as parameter and calculate a score for each one of them. What would be the best metric if I do not want to use optics ? I guess inertia cannot be applied to dbscan like you said. Dec 13, 2013 at 17:36
• I'm not aware of a good general internal evaluation measure. They all make very strong assumptions on what a cluster should look like, and none is general enough to make sense for arbitrary algorithms. You can do external evaluation though, if you have labels. Dec 13, 2013 at 18:20
• Someone got started on a OPTICS implementation for scikit-learn github.com/scikit-learn/scikit-learn/pull/1984 @Anony-Mousse can you elaborate on the k-distance graph? Apr 23, 2014 at 3:52
• There's also an HDBSCAN implementation that works with the sklearn pipeline api. github.com/lmcinnes/hdbscan
– Luke
Feb 19, 2016 at 23:09