6
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Scratch Dec 13 '13 at 17:36
  • $\begingroup$ 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. $\endgroup$ – Anony-Mousse Dec 13 '13 at 18:20
  • $\begingroup$ 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? $\endgroup$ – KLDavenport Apr 23 '14 at 3:52
  • $\begingroup$ There's also an HDBSCAN implementation that works with the sklearn pipeline api. github.com/lmcinnes/hdbscan $\endgroup$ – Luke Feb 19 '16 at 23:09

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.