DBSCAN: Find Dense Groups and Leave Room for Noise
Not every point belongs in a group
GPS delivery stops can trace a curved road or a winding market area. A method based on distance to one mean may split that shape awkwardly. A few faraway stops might not belong to any regular route at all.
DBSCAN groups points through dense neighbourhoods. Its name expands to Density-Based Spatial Clustering of Applications with Noise. You do not need to memorise the expansion. The idea is to connect dense regions and allow isolated points to remain unassigned.
Count neighbours within a radius
Take positions 0.0, 0.1, 0.2, 1.0, 1.1, 1.2, and 5.0. With a radius of 0.21, each point in the first trio sees all three members, including itself. So does the second trio. The point at 5.0 only sees itself.
1points = [0.0, 0.1, 0.2, 1.0, 1.1, 1.2, 5.0]
2eps = 0.21
3counts = [sum(abs(point - other) <= eps for other in points) for point in points]
4print("Neighbour counts:", counts)Neighbour counts: [3, 3, 3, 3, 3, 3, 1]
If we require at least three neighbours, the six points in the trios qualify as dense anchors. The isolated point does not.
Two settings describe local density
Key Points
- eps is the neighbourhood radius under the chosen distance.
- min_samples is the minimum count needed to make a point a core point.
- In scikit-learn, min_samples includes the point itself.
- Units matter: eps in kilometres is not eps in standardised feature units.
A core point has enough neighbours to support a dense region. A border point has too few neighbours of its own but lies within the radius of a core point. A noise point is not reached from a core region.
A dense neighbourhood can expand a cluster
Schematic with min_samples = 4, counting the point itself. The marked core has four neighbours including itself; the border has too few but touches a core.
Expand through core points
Start at a core point, collect its neighbours, then expand from neighbouring core points. A chain of core neighbourhoods forms one cluster, even if the cluster bends. Border points can join, but do not continue the expansion on their own.
A chain of dense points can connect distant areas, while a lone thin bridge may not. A border point touching two clusters can be assigned differently depending on processing order. Core connectivity is more stable than ambiguous border membership.
Fit the toy dataset
1from sklearn.cluster import DBSCAN
2
3X = [[0.0], [0.1], [0.2], [1.0], [1.1], [1.2], [5.0]]
4model = DBSCAN(eps=0.21, min_samples=3)
5labels = model.fit_predict(X)
6print("Labels:", labels.tolist())
7print("Core indices:", model.core_sample_indices_.tolist())
8print("Noise rows:", int((labels == -1).sum()))Labels: [0, 0, 0, 1, 1, 1, -1] Core indices: [0, 1, 2, 3, 4, 5] Noise rows: 1
The value −1 is the noise marker, not another discovered cluster. The other integers are arbitrary cluster IDs. No target labels were provided to fit these groups.
Changing the radius changes the question
If eps is too small, few neighbourhoods qualify and many rows become noise. If eps is too large, separate regions can join. min_samples controls how much local evidence is required; it is not the minimum final cluster size in every simple sense.
1from sklearn.cluster import DBSCAN
2
3X = [[0.0], [0.1], [0.2], [1.0], [1.1], [1.2], [5.0]]
4for radius in [0.05, 0.21, 1.0]:
5 labels = DBSCAN(eps=radius, min_samples=3).fit_predict(X)
6 cluster_count = len(set(labels) - {-1})
7 noise_count = int((labels == -1).sum())
8 print(f"eps={radius}: clusters={cluster_count}, noise={noise_count}")eps=0.05: clusters=0, noise=7 eps=0.21: clusters=2, noise=1 eps=1.0: clusters=1, noise=1
Distance and scale still matter
Scaling changes neighbourhood membership. Standardise columns when that suits their meaning, or choose a distance appropriate for the representation. Latitude and longitude in degrees need a geographic distance or a suitable projection rather than pretending every degree is the same metre distance.
In high dimensions, distances can become less informative. Adding every available column can make density harder to see instead of improving the groups.
Unequal densities are a real limitation
One global eps may fit a dense city-centre region and fail to include a sparse suburb. Increasing the radius to capture the suburb can join city-centre regions that should stay separate. Density-based does not mean every density is handled equally well.
Key Points
- Inspect cluster sizes, noise fraction, and example rows.
- A neighbour-distance plot can suggest a radius range, but still needs domain review.
- Check parameter sensitivity and whether dense bridges merge groups.
- Large neighbourhoods can create high memory use; indexed distance search does not guarantee cheap computation.
Noise is not automatically wrongdoing
A noise label means the row did not fit a dense region under these settings. It might be a data error, a new behaviour, a valid rare customer, or an event worth review. It is not proof of fraud.
The ordinary scikit-learn DBSCAN estimator also has no predict method. Assigning future rows to nearby fitted core points is a possible custom policy, but it differs from refitting and must be evaluated as its own decision rule.
Quick check
What makes a point a core point?
It has at least min_samples points in its eps neighbourhood under the chosen metric, including itself in scikit-learn.
How does a border point differ from a core point?
It is near a core point and can join the cluster, but lacks enough neighbours to expand the cluster itself.
What does the label −1 mean?
It marks noise: a point not included in a dense cluster under the chosen settings. It does not prove an error or fraud.
Why can one eps fail with unequal densities?
A radius suitable for a dense area may reject a sparse group; a larger radius suitable for the sparse group may merge dense areas.
What to carry forward
Key Points
- DBSCAN connects core neighbourhoods rather than fitting mean centres.
- It can find curved groups and label some rows as noise.
- Its radius, neighbour count, distance, and scale define the result.
- Next, PCA changes how many coordinates describe each row.
Theia
Can you explain this concept?
Practise DBSCAN: Find Dense Groups and Leave Room for Noise with realistic interview questions. Choose spoken or typed answers, get feedback on your reasoning, then return to the material that needs work.
Sign in to practise this conceptThe session stays focused on this lesson. Your selected interview level sets the bar.