densityconnected

Densityconnected is a concept in density-based clustering used to describe how points relate within dense regions of a dataset. It is central to algorithms like DBSCAN and OPTICS, where clusters are formed by linking closely situated points through density-based connections. The idea is that points in a high-density region can be reached from one another via a chain of nearby points, and that a cluster corresponds to a maximal set of such density-connected points.

Formally, consider a distance threshold epsilon and a minimum points threshold MinPts. Let N_eps(p) denote the epsilon-neighborhood of p. A point q is directly density-reachable from a point p if q lies in N_eps(p) and p is a core point (|N_eps(p)| ≥ MinPts). A point q is density-reachable from p if there exists a chain p = p0, p1, ..., pk = q where each pi+1 is directly density-reachable from pi. Two points a and b are density-connected if there exists a point o such that both a and b are density-reachable from o; equivalently, they can be connected via a chain of density-reachable steps from a common core point. This relation is symmetric and under appropriate conditions forms an equivalence relation among points in a dense region.

Clusters are defined as the maximal sets of density-connected points that contain at least one core point. Core points are surrounded by at least MinPts points within epsilon, while border points are non-core points that are density-reachable from a core point and thus join the cluster. Points not density-connected to any dense region are considered noise.

Densityconnected underpins the behavior of DBSCAN, guiding how clusters grow by expanding around core points and including density-reachable border points. See also DBSCAN, OPTICS, density-reachability, core point, and epsilon-neighborhood.