What is DBSCAN?
DBSCAN is a density-based clustering algorithm that expands connected neighborhoods around core samples and marks samples not density-reachable from any core as noise.
Quick Facts
| Full Name | Density-Based Spatial Clustering of Applications with Noise |
|---|---|
| Created | 1996 by Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu |
| Specification | Official Specification |
How It Works
Distinguish core, border, and noise samples
The original DBSCAN paper defines direct density reachability, transitive density reachability, and symmetric density connectivity. A core sample satisfies the neighborhood count; a border sample is reachable from a core but does not satisfy the count itself. Noise is relative to the chosen eps, minPts, metric, and dataset.
Tune density in the deployed representation
eps is a radius in the selected metric space, while minPts sets the neighborhood support needed for a core. Scaling, dimensionality, duplicate weights, cosine normalization, and distance concentration all change the effective density. Parameter selection must be repeated when the embedding model or preprocessing changes, and should be checked across relevant slices.
Preserve implementation and assignment semantics
Current scikit-learn documentation notes a worst-case O(n^2) memory path for its implementation, unlike the original algorithm's linear-memory design. Shared border samples can also be assigned according to traversal order. DBSCAN is commonly transductive; assigning future records requires a separately defined policy or refit.
Key Characteristics
- Builds clusters from density-reachable and density-connected samples
- Uses an eps neighborhood radius and a minimum core support
- Can discover non-convex clusters without specifying their count
- Separates core samples, border samples, and noise
- Struggles when valid clusters have strongly different densities
- Depends heavily on feature scaling, metric choice, and neighbor-search behavior
Common Use Cases
- Discovering irregular spatial or embedding groups
- Separating sparse outliers from dense event patterns
- Exploring datasets where the cluster count is unknown
- Finding local communities under a meaningful distance threshold
- Building a density-based baseline beside centroid clustering
Example
Loading code...Frequently Asked Questions
How does DBSCAN form a cluster?
It starts from a core sample whose `eps` neighborhood contains at least `minPts` samples, then expands through neighboring core samples. Border samples reached by a core join the cluster but do not expand it; unreachable samples remain noise.
Is eps the maximum diameter of a DBSCAN cluster?
No. `eps` limits one neighborhood step. A chain of overlapping core neighborhoods can connect endpoints much farther apart than `eps`, so density connectivity rather than global diameter defines a cluster.
How should eps and minPts be selected?
Choose them in the exact scaled feature space and distance metric used in production. Inspect neighbor-distance distributions, test a prespecified range, evaluate stability and domain usefulness, and repeat the process whenever representation or sampling changes.
Why does DBSCAN struggle in high dimensions or with varying density?
Distances become less discriminative in high dimensions, and one global `eps` and `minPts` pair cannot represent both sparse and dense valid groups. Feature selection, a better metric, OPTICS, HDBSCAN, or another model may be more appropriate.
Can fitted DBSCAN assign a new record directly?
Classical DBSCAN describes the fitted dataset and does not define a universal prediction rule. A system must specify whether new records attach to frozen core neighborhoods, enter a separate classifier, remain unassigned, or trigger a versioned refit.