DBSCAN
Core/border/noise points, eps and minPts, non-spherical clusters
You have geographic data — customer addresses mapped to (lat, lon). You want to find city clusters of any shape. K-means would fit circles; cities are not circles. DBSCAN finds density-connected regions of arbitrary shape and labels sparse areas as noise. A city center is a dense region; a rural highway stop is noise. No K to specify — the number of clusters emerges from the data's density structure.
DBSCAN parameters: ε (epsilon) — the radius defining "neighborhood." minPts — the minimum number of points in the ε-neighborhood to be a core point. Core point: has ≥ minPts points within distance ε. Border point: within ε of a core point but not itself a core point. Noise point: not within ε of any core point — explicitly labeled -1.
Density reachability: point A is directly density-reachable from core point B if A is in B's ε-neighborhood. A cluster is the connected component of core points plus their border points. The chain-following is what lets clusters take any shape — crescents, rings, L-shapes.
Parameter selection: minPts = 2 × dimensions (rule of thumb). For ε: sort all pairwise distances to the k-th nearest neighbor (k = minPts), plot the k-distance graph, pick ε at the knee where distances jump.
NOT-this: "DBSCAN does not require K, so it is always better than K-means." DBSCAN has two equally tricky hyperparameters: ε and minPts. If ε is too small, most points are noise. If too large, all points merge into one cluster. And DBSCAN does not handle clusters of varying density well — dense and sparse clusters need different ε values. HDBSCAN (hierarchical DBSCAN) handles variable density and is almost always better than vanilla DBSCAN in practice.
Key points
- Use DBSCAN when your clusters are non-spherical or vary in size, when noise or outlier detection is important, and when you do not know K. Geospatial and graph neighborhood data are ideal. The explicit noise label (-1) is operationally valuable — route ambiguous points to human review rather than forcing overconfident cluster assignments.
- Trap: DBSCAN is O(n²) without a spatial index. On 1M+ points, build a KD-tree or ball tree first — sklearn's DBSCAN does this automatically with algorithm=`'auto'` for low dimensions. Above 20 dimensions, spatial indices degrade back to O(n²) anyway. For high-dimensional data, use HDBSCAN with UMAP preprocessing to first reduce to a meaningful low-dimensional space.
- Diagnostic: if DBSCAN produces one giant cluster containing 90% of points, ε is too large. If it produces hundreds of tiny clusters, ε is too small. Plot the k-distance graph for k=minPts and pick the elbow — this is the systematic way to set ε. No clear elbow means density-based clustering may not match the structure of your data.
DBSCAN finds clusters of any shape and labels outliers explicitly — but a single ε threshold breaks when clusters have different internal densities, which is exactly the problem HDBSCAN was built to fix.
Recap
- Density-connected regions of any shape; sparse points labeled noise (-1). No K.
- Core point: ≥ minPts within ε. Border: near a core. Noise: near nothing.
- Clusters follow chains of core points → crescents, rings, L-shapes.
- Params: minPts ≈ 2×dims; set ε at the knee of the k-distance plot.
- ε too small → all noise; ε too large → one giant cluster.
- Explicit -1 noise label is operationally valuable — route to human review.
- Fails on varying density — single ε breaks; HDBSCAN fixes it.
Check your understanding
Q1. K-means gives 5 circular clusters on GPS location data, but you suspect the true structure has non-circular geographic regions. Which two of the following are the correct setup and validation steps for DBSCAN here?
- A) Use the k-distance plot with k=4 (matching minPts) to find eps at the knee of the sorted distance curve
- B) Validate by inspecting clusters on a map for geographic boundary alignment and checking that noise is genuinely sparse
- C) Set eps by taking the mean pairwise distance and dividing by 10, which is the standard, widely accepted GPS calibration rule
- D) DBSCAN is not suitable for GPS data at all, because lat/lon coordinates require spherical distance, which it does not support
Q2. DBSCAN with eps=0.5 and minPts=5 produces 1 cluster containing 95% of data and 200 noise points. What does this indicate and what do you try?
- A) eps is too small — the radius is not wide enough to connect the dense regions into their own natural clusters correctly here
- B) minPts is too high — reducing it all the way down to 2 will split the single large cluster into meaningful subgroups too
- C) One giant cluster means eps is too large — reduce via the k-distance knee; if no gap exists, try another algorithm entirely
- D) The 200 noise points indicate the dataset has significant outliers preventing proper cluster formation — remove them first
Q3. You apply DBSCAN to customer embeddings in 128 dimensions and get mostly noise (90% of points labelled -1). What is happening and how do you fix it?
- A) The minPts value is set far too high for 128-dimensional data — reduce it all the way to 2 and simply re-run DBSCAN now
- B) DBSCAN labels as noise any point that is not a core point, so 90% noise just means the dataset has few dense regions
- C) The training data itself is contaminated — 90% of the points are genuine anomalies and only 10% are truly normal
- D) In 128 dims, Euclidean distances converge so eps cannot discriminate neighbours — apply PCA/UMAP to 10-20 dims first
Q4. What is the difference between noise in DBSCAN and outliers detected by Isolation Forest? When would you use each for anomaly detection?
- A) They are equivalent — both define anomalies as points with fewer than k neighbours within some fixed, pre-chosen radius
- B) DBSCAN noise requires labelled normal data to calibrate eps and minPts; Isolation Forest is instead fully unsupervised
- C) DBSCAN noise is density-local (sparse vs eps/minPts); Isolation Forest gives a global score — pick by dimensionality
- D) Isolation Forest is always superior overall — DBSCAN noise labelling should only ever be a preprocessing step before it
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →