Use of a Poisson distribution from a distance matrix to determine dbscan parameters

Question

I´ve been researching about automatic determination of parameters for DBSCAN (a density-based clustering algorithm -- http://en.wikipedia.org/wiki/DBSCAN), especially eps, and have found the following paper, which proposes a method for determining the best eps from the data themselves: http://www.joics.com/publishedpapers/2012_9_7_1967_1973.pdf

However, the paper claims, in page 1969, section 3.1, about a distance matrix DIST$_{n \times n}$:

We calculate the value of each element in DIST$_{n\times n}$ successively, and then sort them in an ascending order line by line. We use DIST$_{n \times i}$ to express the $i$th column value in DIST$_{n \times n}$. As all data in DIST$_{n \times i}$ obeys the Poisson distribution[6], we use the maximum likelihood estimation in mathematics to estimate the value of parameter $\lambda$. That is to say, $\lambda$ can be obtained by means of the geometrical mean of the value of DIST$_{n \times i}$.

The paper goes to claim that this $\lambda$ can be used as eps. Is there a reason for this claim? I have read about the Poisson distribution, but nowhere I have found found support for the claim that distances should follow this distribution (I admit to not being very knowledgeable about probability distributions, however). If this claim is not spurious, it would enormously simplify working with DBSCAN, as it would diminish the guesswork necessary to determine parameters.

Answer 1

Ideally, you shouldn't be guessing the parameters.

For DBSCAN, the epsilon parameter is a distance. Whenever you are using DBSCAN, you should first understand distance in your data set.

Without having a working and reliable distance, DBSCAN results won't be convincing. And once you have understood your distances, it should no longer be hard to choose epsilon.

For example on geographic data, a lot of people work naively with Euclidean distance on latitude/longitude coordinates. This is flawed, and choosing epsilon is largely based on guessing. But using great-circle distance, you can actually give the distance in km, and choose it to fit your desired analysis. For example, when analyzing car accidents, you can assume that 20 meters is maybe a reasonable value (large enough to cover one crossroad, but not the next).

So figure out your distance function first.

But if you don't want to choose epsilon, use OPTICS. It's published by the original DBSCAN authors, it works great, and it does no longer require the epsilon parameter (unless you use that b0rked matlab/python version that has been floating around the interwebs for some time; which is an inefficient DBSCAN actually, not proper OPTICS). It has an epsilon parameter, but that is for limiting the runtime only. In DBSCAN terms, it is the maximum epsilon you allow (which is why you can set it to infinity, if you don't care about runtime).

There is a new HDBSCAN* by some of the original authors, which is described as "OPTICS done right". But I have not yet tested it or seen an implementation.