2
$\begingroup$

Recently, I am working on DBSCAN algorithm, the original paper is

M. Ester, H. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise.

However, there are debates on whether the clustering result is deterministic or not. I read through the paper and relevant materials, but no solid proof can be found.

It's quite easy to say that given epsilon and min samples, the core points set should be unique so the clustering should be deterministic either.

However, can any one give a shot on proving this in a more rigorous mathematical style?

Thanks!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you provide an example of these debates? Actually, there can be no such debate, not in a principled manner. If an algorithm bases at least one of its steps on a random value drawn from a probability distribution, it is non-deterministic. Otherwise, it is deterministic. There is no room for debate, and no need for a rigorous proof. $\endgroup$ – cangrejo Oct 8 '17 at 8:57
  • $\begingroup$ Thanks @broncoAbierto. The first entry in the disadvantage part on wiki en.wikipedia.org/wiki/DBSCAN, it says DBSCAN is not entirely deterministic. $\endgroup$ – shin Oct 8 '17 at 9:00
  • $\begingroup$ I now see where your doubts come from. I just don't think that the use of the word "deterministic" is the right choice there. The algorithm is deterministic, but the result depends on the order of the input. One often encounters similar issues in the literature, and authors usually suggest to "break ties arbitrarily", because the properties they want to demonstrate or prove hold for either choice. These algorithms can be considered non-deterministic as they depend on the "random value" of the choice made by the implementer. I think that's stretching the definition, though. $\endgroup$ – cangrejo Oct 8 '17 at 9:10
  • $\begingroup$ Check the references on Wikipedia. They give an example, and a more precise formulation (deterministic on core and noise, but not always on border points). But this is discussed in the DBSCAN paper, if you read it completely (it's easy to miss if you only scan it briefly). $\endgroup$ – Has QUIT--Anony-Mousse Oct 8 '17 at 14:37
  • 1
    $\begingroup$ I found the 20 years later paper by the original authors insightful: Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (July 2017). "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN". ACM Trans. Database Syst. 42 (3): 19:1–19:21.ISSN 0362-5915. doi:10.1145/3068335. It discusses some of the later insights into the algorithm. $\endgroup$ – Has QUIT--Anony-Mousse Oct 8 '17 at 14:41
2
$\begingroup$

It is not entirely deterministic.

See page 230 of the DBSCAN paper, the end of section 4.1, which gives the exception (border points of two clusters), and concludes:

Except for these rare situations, the result of DBSCAN is independent of the order in which the points of the database are visited due to Lemma 2.

If clusters are assigned integer labels, the label values of course still change, but they are considered to be the same clusters.

Because the order in which points from a database are returned may depend on various factors (e.g., they might be in a hash table, or in a distributed system they might be merged depending on their transmission time) it can cause non-deterministic variation in the result. Only when such hidden data structures are deterministic, then DBSCAN is guaranteed to always yield the exact same result.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks @Anony-Mousse . I read the through the paper you found for me, but still I didn't find any explicit proof. Besides the rare situation mentioned above, can you rigorously prove that the clustering result is deterministic? Or Do you also think it's very straightforward and no proof needed? $\endgroup$ – shin Oct 9 '17 at 1:34
  • $\begingroup$ I have not seen a rigorous proof. Because it will be hard to do with that "but". It should be easier to prove that at least on core points the result is deterministic. $\endgroup$ – Has QUIT--Anony-Mousse Oct 9 '17 at 5:53
1
$\begingroup$

There is no clear answer to the question whether DBSCAN is deterministic or not.

Fact is, that if you shuffle the data set, it can return slightly different results on some data sets and parameters ("rare situations").

This will also happen if SetOfPoints is actually implemented as a set, with no well-defined iteration order (usually, this will only depend on the data order; but in some implementations this may yield a different order every time!)

However, the actual pseudocode of DBSCAN does not contain non-determinism itself. So it is perfectly reasonable to call DBSCAN deterministic, given the data, minPts, eps, distance function, and iteration order.

From a mathematical point of view, DBSCAN is deterministic (but some points are border points to more than one cluster; and the DBSCAN algorithm proposed only approximates the definition).

From an experimental point of view, DBSCAN is deterministic: unless I change my data, the result usually does not change; and I do not need to experiment with shuffled data, because the results will often not change at all, or only so little that it does not make a difference. In contrast to k-means, where I must consider different random seeds, I do not need to do shuffling for DBSCAN.

From an implementors point of view, DBSCAN is not deterministic: Different implementations can both be correct, yet yield slightly different results. So if I compare my results to the results of someone else, I cannot blindly require the labels to be identical, because different data structures and processing order can yield different results. This also applies, e.g., to parallel and distributed versions of DBSCAN. These can be correct, yet yield a different result on multiple-border-objects.

|cite|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.