0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What's DBSCAN please? If it's a method, it is best not to assume abbreviations or acronyms as universally understood. If it's software, there needs to be a statistical question at the heart of this for it to be on-topic here. $\endgroup$
    – Nick Cox
    Dec 4, 2013 at 17:00
  • 2
    $\begingroup$ DBSCAN is a popular clustering algorithm, but the question is about whether the claim that a distance matrix follows a poisson distribution is correct (see quoted section), not about the algorithm itself. I have edited the title to make it clearer (I hope) $\endgroup$
    – vrios
    Dec 4, 2013 at 17:26
  • $\begingroup$ Thanks for the clarification. I won't try to evaluate that paper, but I do note specifically that what is called the "geometrical mean" is just the standard (arithmetic) mean. To many statistical readers, geometric mean might seem implied, but the formula on p.1969 is unequivocal. $\endgroup$
    – Nick Cox
    Dec 4, 2013 at 18:10
  • 1
    $\begingroup$ @NickCox that follow-up article is crap. Their experiments are laughable (tiny synthetic data sets), and they can't even distinguish the arithmetic and the harmonic mean? JOICS is also all but a sound journal, but the usual chinese pay-to-publish scam/spam. $\endgroup$ Dec 4, 2013 at 22:33
  • $\begingroup$ @Anony-Mousse I don't endorse your choice of wording here, but merely emphasise that I didn't read the paper beyond the quotation. $\endgroup$
    – Nick Cox
    Dec 5, 2013 at 1:34

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ AFAIK, HDBSCAN is not from the original DBSCAN authors. But instead by some other chinese guys... Or maybe you were talking about another paper ? $\endgroup$
    – kebs
    Jun 3, 2014 at 8:33
  • $\begingroup$ I'm talking about HDBSCAN by R. J. G. B. Campello, D. Moulavi, J. Sander. and the followup work on hierarchy extraction by R. J. G. B. Campello, D. Moulavi, A. Zimek, J. Sander. $\endgroup$ Jun 3, 2014 at 9:35
  • $\begingroup$ Ok, I can't check the paper as my institution doesn't provide me an access on these, but if the name is indeed the same, this is not going to clarify things ;-) (although I have absolutely no doubt on the relative value of these 3 papers.) $\endgroup$
    – kebs
    Jun 3, 2014 at 9:42
  • $\begingroup$ There is an HDBSCAN implementation. $\endgroup$
    – user61638
    Nov 28, 2014 at 3:17

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.