Overview
DBSCAN grows clusters from core points that have enough nearby neighbors within a chosen radius.
CoreSource checked
DBSCAN
Clusters points by dense neighborhoods and labels sparse points as noise.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Machine Learning
- Difficulty
- Intermediate
- Family
- Density-Based Clustering
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
learned parameterscluster structuredensity neighborhoodunlabeled patternsdensity-based clusteringmodel fittraining examplesprediction rule
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use DBSCAN when you need to find dense regions of points.
- Use it when the input assumptions match the method's model.
- Use it when you have data that matches the model's assumptions and a measurable target or structure.
- Use it when the method's tradeoffs fit the workload.
When Not to Use
- Avoid it when there is not enough representative data to train or evaluate the model.
- Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
- Avoid it when the required output is not cluster labels.
What It Does
- Finds dense regions of points
- Marks low-density points as noise
Use Cases
- Spatial clustering
- Outlier detection
- Clusters with irregular shapes
Inputs
- Data points
- Neighborhood radius
- Minimum points
Outputs
- Cluster labels
- Noise labels
Key Formulas (1)
Core point rule
core(point) if count(neighbors within ε) ≥ minpoints
core(point) if count(neighbors within eps) >= min_pointsMarks a point as dense enough to expand a cluster.
Pseudocode
- 1.Visit an unprocessed point
- 2.Find neighbors within the radius
- 3.Start a cluster if enough neighbors exist
- 4.Expand through neighboring core points
- 5.Mark sparse points as noise
Canonical Example
- Input
- points = [(0,0), (0,1), (9,9)], radius = 2, minPoints = 2
- Output
- one cluster near (0,0) and noise point (9,9)
- Explanation
- DBSCAN: Grows clusters from dense neighborhoods and labels isolated points as noise.
Implementation Notes
- Keep the input contract explicit: Data points; Neighborhood radius; Minimum points.
- Split data for evaluation and track preprocessing steps so predictions use the same feature format.
- Treat examples as educational sketches; production models need validation, monitoring, and domain checks.
Common Pitfalls
- DBSCAN avoids choosing a cluster count but depends on radius and density parameters.
- Evaluating only on training data and mistaking memorization for useful performance.
- Handle empty, invalid, and boundary inputs before trusting cluster labels.
- Data leakage, unscaled features, and validation on training data can make results look better than they are.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow dense point groups forming clusters while isolated points stay noise.
Step 1 of 5: Visit an unprocessed point
density-clustersNotes
DBSCAN operates in O(n log n) time and O(n) space within the Density-Based Clustering family. Key governing relation: core(point) if count(neighbors within eps) >= min_points. Often compared with K-Means and K-Nearest Neighbors.
Sources (1)
What each reference supports for this entry.
The Elements of Statistical Learning
BookStatistical learning reference for the model family and tradeoffs of DBSCAN.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toK-Means
DBSCAN clusters by density instead of fixed centroids.
Related Algorithms
Tags
Machine LearningClusteringDensity BasedUnsupervised Learning