Search code examples
machine-learningdbscan

In DBSCAN, how to determine border points?


In DBSCAN, the core points is defined as having more than MinPts within Eps.

So if MinPts = 4, a points with total 5 points in Eps is definitely a core point. How about a point with 4 points (including itself) in Eps? Is it a core point, or a border point?


Solution

  • Border points are points that are (in DBSCAN) part of a cluster, but not dense themselves (i.e. every cluster member that is not a core point).

    In the followup algorithm HDBSCAN, the concept of border points was discarded.

    Campello, R. J. G. B.; Moulavi, D.; Sander, J. (2013).
    Density-Based Clustering Based on Hierarchical Density Estimates.
    Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery in Databases, PAKDD 2013. Lecture Notes in Computer Science 7819. p. 160. doi:10.1007/978-3-642-37456-2_14

    which states:

    Our new definitions are more consistent with a statistical interpretation of clusters as connected components of a level set of a density [...] border objects do not technically belong to the level set (their estimated density is below the threshold).