CODEWITHSUNDEEP
machine-learningcluster-analysisdbscan
user650585
user650585

Reputation: 323

DBSCAN and border points

It is being said that DBSCAN is not consistent on the border points and depends on which cluster it assigns the point to first. Is there a variation of DBSCAN which takes into account the number of points a border point is close to (eps) in each cluster, when it wants to assign a border point to one of the clusters?

Upvotes: 0

Views: 1273

Answers (2)

Elvira Siegel
Elvira Siegel

Reputation: 19

A little bit late, but still: first of all, a border point must be a core point itself because there must be at least one further object in its epsilon neighborhood from which it is directly density reachable. Otherwise it would not be connected to a cluster.

By definition the DBSCAN result is deterministic w.r.t. the core and noise points but not w.r.t the border points, so: if a border point is density reachable from two clusters it really depends on the processing or your implementation, to which cluster it will be assigned.

Upvotes: 0

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

In those cases where this matters, the number of points will usually be 1 for two clusters each.

The better tie breaker will be the distance, but even that can have ties.

It is a trivial modification, easily implemented in post-processing: for every border point, find the nearest core point, and use that label.

However, does it matter?

Clustering is never perfect. And we are talking here about a rare case where the "best" (for a rather ad-hoc definition of "best", based on two hard thresholds) assignment usually makes 0.000 difference to the end result.

If I am not mistaken, the DBSCAN author suggested that you can also assign these points to both clusters. That is supposedly the solution most true to the definitions (the border point is reachable from both clusters). But it makes everything much more complicated. Because many users want each point to have one label in a nice numeric column, and not have to deal with this special case.

Upvotes: 1

Related Questions