Statistics Glossary → ε-neighbourhood and minimum points (DBSCAN)
ε-neighbourhood and minimum points (DBSCAN)concept
In DBSCAN, the radius of the neighbourhood around a point (ε) and the minimum number of points (minPts) that this neighbourhood must contain for the point to count as the core of a dense region.
A point is a core point if its ε-neighbourhood contains at least minPts points, itself included. Points that lie in a core point's neighbourhood but are not core points themselves are border points, and points that cannot be reached from any core point are noise. Core points within each other's neighbourhoods are chained together to form clusters, so clusters of arbitrary shape can be found without specifying their number in advance.
The results are very sensitive to both parameters: a small ε labels many points as noise and breaks clusters apart, while a large ε merges separate clusters. A common way to choose ε is the k-distance plot: the distance of each point to its k-th nearest neighbour is sorted and plotted, and the point where the curve bends (the knee) is chosen (k = minPts). A rough rule for minPts is at least the number of dimensions + 1, often 2 × the number of dimensions. A single ε cannot capture clusters of very different density at once; HDBSCAN tries to overcome this by varying ε.
An everyday example
Cafés in a city are marked on a map, with the rule that 'a place with at least 5 cafés within 300 metres is the centre of a café district'. These centres are chained together to form café districts, while isolated cafés that are not near any district are treated as noise.
In MerQur
'ε (eps; 0.01 = automatic)' and 'Min. samples (minPts)' in DBSCAN / HDBSCAN; 'Radius (eps)' (great-circle distance in metres, with a suggested k-distance knee) and 'Min. points' in DBSCAN Spatial Clustering.
Analyses where this concept appears
DBSCAN / HDBSCANDBSCAN Spatial Clustering
Related concepts
Elbow method and k-distance plotDistance measure (Euclidean, Manhattan, Gower, great-circle)