Reachability explains how DBSCAN connects dense regions. A core point has at least minPoints points, including itself, within radius ϵ; nearby points can then join its cluster. section 12.3.1
Use these relationships to determine whether a point belongs to a density-connected cluster:
- A point is directly reachable from a core point when it lies within that core point’s radius ϵ. section 12.3.1
- A point is density-reachable when a chain of core points connects it to another point through successive direct-reachability relationships. section 12.3.1
- Points density-reachable from one another belong to the same cluster; points reachable from no other point become outliers or noise. section 12.3.1
DBSCAN grows a cluster by processing each core point and immediately examining its undiscovered neighbors. This avoids tracking cluster merges. A non-core edge point may be reachable from multiple clusters, so its assignment can vary while the overall clustering remains effectively unchanged. section 12.3.2 section 12.3.2
Figure 12.9 Core points, directly reachable points, and reachable points, given a radius ϵ and a threshold minPoints (the minimum number of points in a core region) equal to 3; hence, core points need to have at least two neighbors within distance ϵ.
Use the diagram to distinguish core points, directly reachable neighbors, and longer density-reachable paths under a radius ϵ and minPoints threshold. section 12.3.1
Figure 12.10 A few steps of the main loop of DBSCAN. When core points are processed (the first three steps in the figure) all their undiscovered neighbors are added to current cluster and to a set (not a queue) of points to be processed. Conversely, when the current point being processed is not a core point, like v in the last step, then no further action is taken.
Follow the cluster-growth sequence: core-point neighbors enter the current cluster and the set of points still to process, while non-core points do not expand it. section 12.3.2
