Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
Recently, I am working on DBSCAN algorithm, the original paper is
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!
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.
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.
