matching implementations & algorithm correctness

[elbamos]

@mhahsler I'm trying to add dbscan and optics to my largeVis package. I've been using your package to generate testing data to make sure that mine is producing the same results. I've come across a couple of thingies that I'm not understand and I hope you can help me clear it up.

In particular, on optics, my implementation and yours are producing similar but different results. The source of the discrepancy seems to be that they get different results in their calculation of core distance.

I've isolated an example. Take the dataset produced by:

data(iris)
dat <- as.matrix(iris[, 1:4])
dupes <- which(duplicated(dat))
dat <- dat[-dupes, ]

With eps = 1 and minPts = 10, my implementation calculates a core distance for point 1 of 0.3. dbscan::optics with those settings, and all other parameters at their defaults, seems to calculate 0.316.

With search = 'linear', dbscan::optics gives:

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

Checking manually, it seems to me that 0.3 is the right answer:

distances <- dist(dat)
neighbors[1:12, 1] # an adjacency matrix generated by largeVis; 0-indexed
[1] 17  4 39 28 27 40  7 49 37 21 48 26 
as.matrix(distances)[1, neighbors[1:12] + 1]

18	5	40	29	28	41	8	50	38	22	49	27
0.1000000	0.1414214	0.1414214	0.1414214	0.1414214	0.1732051	0.1732051	0.2236068	0.2449490	0.3000000	0.3000000	0.3162278

Any ideas? Could this be an issue in the approximate nearest neighbor search?

[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 notifications@github.com 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.