3
$\begingroup$

yes, DBSCAN parameters, and in particular the parameter eps (size of the epsilon neighborhood). In the documentation we have a "Look for the knee in the plot".

Fine, but it requires a visual analysis. And it doesn't really work if we want to make things automatic. So, I was wondering if it was possible to find a good eps in a few lines of code.

Let's imagine something like :

  1. evaluate kNN distance
  2. sort these values
  3. scale them (so that the values are always between 0 and 1)
  4. evaluate the derivative
  5. find the first point where derivative is higher than a certain value, let's try with 1

In R, it would look like (using iris dataset as in the DBSCAN documentation) :

# evaluate kNN distance
dist <- dbscan::kNNdist(iris, 4)

# order result
dist <- dist[order(dist)]

# scale
dist <- dist / max(dist)

# derivative
ddist <- diff(dist) / ( 1 / length(dist))

# get first point where derivative is higher than 1
knee <- dist[length(ddist)- length(ddist[ddist > 1])]

and the result is 0.536 which looks quite good. enter image description here

Is this approach relevant or totally nonsense ?

$\endgroup$
4
$\begingroup$

OPTICS gets rid of $\varepsilon$, you might want to have a look at it. Especially the reachability plot is a way to visualize what good choices of $\varepsilon$ in DBSCAN might be.

Wikipedia (article) illustrates it pretty well. The image on the top left shows the data points, the image on the bottom left is the reachability plot:

enter image description here

The $y$-axis are different values for $\varepsilon$, the valleys are the clusters. Each "bar" is for a single point, where the height of the bar is the minimal distance to the already printed points.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm a bit confused (but that's normal since I'm just starting to work with this kind of tools...) because according to the doc a eps parameter still need to be set for OPTICS algorithm. So we don't really get rid of it, do we ? $\endgroup$ – irimias May 18 '16 at 12:00
  • 1
    $\begingroup$ The eps parameter of OPTICS is different. It is an upper bound, not a fixed value. It mainly has influence on how fast the algorithm runs. $\endgroup$ – Martin Thoma May 18 '16 at 12:33
  • $\begingroup$ Indeed but, at the end, if we want to extract clusters we have to make a visual analysis of the reachability plot and set xi parameter manually Is there a way to set it in a cleaner way ? (I'm going off topic...) $\endgroup$ – irimias May 18 '16 at 13:28
2
$\begingroup$

If you go for an automatic solution, you may as well just decide that 80% of your points should be core points, and choose the 80% quantile of the 4-NN distances.

Looking at the derivative etc. to formally define a "knee" is fragile, this will not work in my opinion. Because you cannot compare distances to ranks.

But:

  • Several heuristics for DBSCAN parameterization have been proposed over the last 20 years.
  • Several enhancements of DBSCAN such as OPTICS and HDBSCAN* have been published, that get rid of the epsilon parameter (in favor of a graphical approach, e.g. OPTICS plots).

In the end, having parameters is a feature, not a limitation. Cluster analysis is not something to fully automate. It is an explorative method. You try it, change parameters, try it again, change parameters again, ... until you have learned something about your data. Any method that does not allow you to reiterate is badly designed.

| improve this answer | |
$\endgroup$

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.