Start learning

DBSCAN

Lesson 45. About 7 minutes.

DBSCAN (density-based spatial clustering of applications with noise) groups points that sit in dense areas and marks points in sparse areas as noise. It finds clusters of any shape and doesn't need the number of clusters in advance.

Your Path Through This Lesson

0 of 5 done

By the End of This Lesson You Can
  • Explain core, border and noise points.
  • Know what eps and min_samples control.
  • See DBSCAN succeed where K-means fails.

Clusters as Dense Regions

K-means assumes clusters are round blobs around a centre. Real groups can be long, curved or irregular. DBSCAN uses a different idea: a cluster is a region where points are packed closely together, separated from other clusters by empty space.

Two Settings

  • eps (): the radius of a point's neighbourhood.
  • min_samples: how many points (including itself) must be inside that radius for the area to count as dense.

Three Kinds of Points

Type Rule Role
Core Has at least min_samples points within eps The heart of a cluster
Border Not core, but within eps of a core point The edge of a cluster
Noise Neither An outlier, labelled −1

The Algorithm

  1. Pick an unvisited core point and start a new cluster.
  2. Add every point within eps of it.
  3. For each core point added, add its neighbours too, and keep expanding.
  4. When the cluster can't grow any more, pick the next unvisited core point.
  5. Points never reached are noise.

Clusters grow by chaining from core point to core point, which is why they can follow any shape.

By Hand

Study hours: 1, 2, 3, 10, 11, 12, 25. Settings: eps = 1.5, min_samples = 2.

Point Neighbours within 1.5 (incl. itself) Type
1 1, 2 Core
2 1, 2, 3 Core
3 2, 3 Core
10 10, 11 Core
11 10, 11, 12 Core
12 11, 12 Core
25 25 Noise

Result: cluster 0 = {1, 2, 3}, cluster 1 = {10, 11, 12}, and 25 is noise. K-means would have been forced to put 25 in some cluster.

python
import numpy as np
from sklearn.cluster import DBSCAN

hours = np.array([[1], [2], [3], [10], [11], [12], [25]])
db = DBSCAN(eps=1.5, min_samples=2).fit(hours)
print("labels    :", db.labels_)
print("core point indices:", db.core_sample_indices_)
Output
labels    : [ 0  0  0  1  1  1 -1]
core point indices: [0 1 2 3 4 5]

Where K-Means Fails

make_moons creates two interlocking half-circles:

python
from sklearn.cluster import KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score
from sklearn.preprocessing import StandardScaler

X, true_labels = make_moons(n_samples=300, noise=0.06, random_state=0)
X = StandardScaler().fit_transform(X)

km_labels = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(X)
db_labels = DBSCAN(eps=0.3, min_samples=5).fit_predict(X)

print(f"K-means agreement with truth: {adjusted_rand_score(true_labels, km_labels):.3f}")
print(f"DBSCAN  agreement with truth: {adjusted_rand_score(true_labels, db_labels):.3f}")
print("DBSCAN clusters found:", len(set(db_labels) - {-1}), "  noise points:", int(np.sum(db_labels == -1)))
Output
K-means agreement with truth: 0.470
DBSCAN  agreement with truth: 0.993
DBSCAN clusters found: 2   noise points: 1

The adjusted Rand score compares a clustering with the true groups: 1 means a perfect match, 0 means no better than random. K-means cuts each moon in half with a straight boundary; DBSCAN follows the curves.

Choosing Eps

eps matters most. Too small, and most points become noise; too large, and separate clusters merge into one.

python
for eps in [0.1, 0.2, 0.3, 0.5, 1.0]:
    labels = DBSCAN(eps=eps, min_samples=5).fit_predict(X)
    print(f"eps={eps:<4}: clusters {len(set(labels) - {-1})}   noise {int(np.sum(labels == -1)):>3}")
Output
eps=0.1 : clusters 20   noise 161
eps=0.2 : clusters 3   noise   5
eps=0.3 : clusters 2   noise   1
eps=0.5 : clusters 1   noise   0
eps=1.0 : clusters 1   noise   0

A common way to pick eps: for each point, find the distance to its min_samples-th nearest neighbour, sort those distances and plot them. Choose eps where the curve bends sharply upward (a "k-distance" plot). Start min_samples at about twice the number of features.

Strengths and Weaknesses

✅ Finds clusters of any shape
✅ Detects outliers as noise
✅ No need to choose the number of clusters
❌ One eps for the whole dataset Struggles when clusters have very different densities
❌ Sensitive to eps and to scale Scale features first
❌ Weak in many dimensions Distances become less meaningful (see the curse of dimensionality)
Tip

HDBSCAN (sklearn.cluster.HDBSCAN) extends DBSCAN to clusters of varying density and needs only min_cluster_size. It's often a better default when densities differ.

Try It Yourself
  1. In the hand example, change eps to 0.9. Which points become noise now?
  2. On the moons, try min_samples=20 with eps = 0.3. What changes?
The Key Idea

DBSCAN grows clusters from dense core points, so it follows any shape and labels isolated points as noise (−1). eps and min_samples define "dense".

Summary

  • DBSCAN: clusters are dense regions; isolated points are noise.
  • Core, border and noise points, defined by eps and min_samples.
  • Finds any shape and flags outliers; no K needed.
  • Pick eps with a k-distance plot; scale features first.
  • Next: why many features make distance-based methods struggle, the curse of dimensionality.