matching implementations & algorithm correctness about dbscan

[peekxc]

elbamos

This is a very good question, one of which I myself actually ran into (if I am right here) in trying to implement HDBSCAN.

If you refer to the original OPTICS paper, and I believe in the ELKI implementation (original software implementation of OPTICS) and also in the dbscan packages implementation, the core-distance is actually calculated as the minPts-closest neighbor distance to a point, inclusive of the point itself.

I refer you to check figure 4 in the original OPTICS paper: http://fogo.dbs.ifi.lmu.de/Publikationen/Papers/OPTICS.pdf

I don't know if it was spelled out as explicitly somewhere else in the OPTICS paper, I thought the definitions weren't as strict as what I've seen in the later papers, but it is spelled out in the newer journal paper of HDBSCAN (The 52-page "Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection" paper from 2015).

"Definition 3.1 (Core Distance). The core distance of an object xp ∈ X w.r.t. mpts, dcore(xp), is the distance from xp to its mpts-nearest neighbor (including xp)."

Thus, if you do:

dbscan::optics(dat, eps = 1, minPts = 11, search = "linear")$coredist[1]
[1] 0.3

The other standard dbscan algorithms follow the more standard interpretation or nearest neighbor:

dbscan::kNNdist(dat, k = 10)[1, 10]
0.3

I hope this helps, or perhaps I'm way off the mark, just something I've noticed.

[elbamos]

I think you are correct... this is the path I've been trying to track down since I posted the question.

On Sep 21, 2016, at 9:45 PM, Matt Piekenbrock [email protected] wrote:

elbamos

This is a very good question, one of which I myself actually ran into (if I am right here) in trying to implement HDBSCAN.

If you refer to the original OPTICS paper, and I believe in the ELKI implementation (original software implementation of OPTICS) and also in the dbscan packages implementation, the core-distance is actually calculated as the minPts-closest neighbor distance to a point, inclusive of the point itself.

I refer you to check figure 4 in the original OPTICS paper: http://fogo.dbs.ifi.lmu.de/Publikationen/Papers/OPTICS.pdf

I don't know if it was spelled out as explicitly somewhere else in the OPTICS paper, I thought the definitions weren't as strict as what I've seen in the later papers, but it is spelled out in the newer journal paper of HDBSCAN (The 52-page "Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection" paper from 2015).

"Definition 3.1 (Core Distance). The core distance of an object xp ∈ X w.r.t. mpts, dcore(xp), is the distance from xp to its mpts-nearest neighbor (including xp)."

Thus, if you do:

dbscan::optics(dat, eps = 1, minPts = 11, search = "linear")$coredist[1]
[1] 0.3

The other standard dbscan algorithms follow the more standard interpretation or nearest neighbor:

dbscan::kNNdist(dat, k = 10)[1, 10]
0.3

I hope this helps, or perhaps I'm way off the mark, just something I've noticed.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub, or mute the thread.

[peekxc]

Just as a follow up to this answer.

If you were wondering why they defined core distance like that, although I can't speak for the original authors, I believe it was probably to maintain the interpretation of the minPts parameter to mean the minimum number of points to constitute a cluster, as from the original DBSCAN idea.

Consider the following:

dat <- data.frame(x=runif(5), y=runif(5)) res <- dbscan::dbscan(dat, eps = 1, minPts = 5) # Can check against fpc::dbscan as well dbscan::hullplot(x = dat, res)

This code will produce 1 cluster of all 5 randomly generated points, however:
res <- dbscan::dbscan(dat, eps = 1, minPts = 6) # Can check against fpc::dbscan as well dbscan::hullplot(x = dat, res)

Marks all of the points as noise (which makes sense, since there are less points that minimum cluster size). If you use minPts = 5 with an exclusive core distance calculation, the semantics behind the interpretation of minPts is changed

[elbamos]

Yes, it makes perfect sense. I'm now getting matching core distances, the order is off considerably, but reachability distances are either the same to many significant digits or lower. I may ask again if it doesn't resolve.