DBSCAN

K-Means assumes your clusters are round. Your data does not care about that assumption. Real-world clusters are shaped like rivers, rings, and crescents. Fraud patterns form tight dense pockets surrounded by sparse noise. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) was built for exactly this — it finds clusters of arbitrary shape and labels everything that does not fit as an outlier. For anomaly detection, this is not a side effect, it is the feature.

---

Learning Objectives

• Explain the density-based intuition behind DBSCAN (core, border, noise points)
• Describe what eps and min_samples control and how to tune them
• Use the k-distance plot to choose eps empirically
• Interpret DBSCAN output including the -1 noise label
• Know when DBSCAN outperforms K-Means and when it struggles
• Use DBSCAN as an anomaly detector on real data

---

The Core Intuition

K-Means asks: "What is the nearest centroid?" DBSCAN asks: "How many points are near this point?"

DBSCAN grows clusters outward from dense regions. It classifies every point into one of three roles:

Core point: Has at least min_samples points within radius eps (including itself). This point is in the dense interior of a cluster.

Border point: Within eps of a core point, but does not itself have enough neighbours to be a core point. On the edge of a cluster.

Noise point: Not a core point and not within eps of any core point. Labelled -1. This is your outlier.

Imagine a scatter plot of GPS coordinates for a city:

  Dense downtown area:
  ● ● ● ● ●     <- core points (many nearby neighbours)
  ● ● ● ● ●
  ● ● ●

  Sparse suburbs:
  ·   ·   ·     <- border or noise points

  Isolated house 50 km away:
  ·             <- noise (labelled -1)

Info

DBSCAN was proposed by Ester, Kriegel, Sander, and Xu in 1996. The "noise" label was not an afterthought — detecting outliers was a design goal from the start. In fraud detection, network intrusion, and sensor fault detection, the -1 label is often the most valuable output the algorithm produces.

---

Parameters: eps and min_samples

These two parameters fully determine DBSCAN's behaviour.

Parameter	What it controls	Too small	Too large
eps	Radius of the neighbourhood	Every point is noise	Everything merges into one cluster
min_samples	Points needed for a core point	Everything is a core point, no noise	Fewer core points, more noise

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
import pandas as pd
import numpy as np

# Simulated GPS-like coordinates
data = pd.DataFrame({
    "lat": [40.71, 40.72, 40.70, 40.73, 40.71,   # downtown cluster
             34.05, 34.06, 34.04,                  # LA cluster
             51.50],                                # isolated point — noise
    "lon": [-74.00, -74.01, -73.99, -74.00, -74.02,
             -118.24, -118.25, -118.23,
             -0.12]
})

X_scaled = StandardScaler().fit_transform(data)

model = DBSCAN(eps=0.5, min_samples=3)
labels = model.fit_predict(X_scaled)

data["cluster"] = labels
print(data)
# Output:
#      lat     lon  cluster
# 0  40.71  -74.00        0   <- NYC cluster
# 1  40.72  -74.01        0
# 2  40.70  -73.99        0
# 3  40.73  -74.00        0
# 4  40.71  -74.02        0
# 5  34.05 -118.24        1   <- LA cluster
# 6  34.06 -118.25        1
# 7  34.04 -118.23        1
# 8  51.50   -0.12       -1   <- NOISE (London, isolated)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print(f"Clusters found: {n_clusters}")  # Output: Clusters found: 2
print(f"Noise points: {n_noise}")       # Output: Noise points: 1

Warning

DBSCAN output is highly sensitive to eps. Changing eps from 0.5 to 0.6 can merge two separate clusters into one. Changing from 0.5 to 0.4 can split a single real cluster into many fragments. Always tune eps systematically using the k-distance plot — do not guess.

---

Choosing eps: The K-Distance Plot

The k-distance plot is an empirical method for choosing eps. For each point, compute its distance to its k-th nearest neighbour (using k = min_samples). Sort these distances in ascending order. The plot will usually show a "knee" — the point where distances start increasing sharply. Set eps at that knee.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import NearestNeighbors
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler

X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)
X_scaled = StandardScaler().fit_transform(X)

min_samples = 5  # the k in k-distance

# Fit nearest neighbours
nbrs = NearestNeighbors(n_neighbors=min_samples).fit(X_scaled)
distances, _ = nbrs.kneighbors(X_scaled)

# Distance to the k-th neighbour for each point
kth_distances = distances[:, -1]  # last column = k-th distance
kth_distances_sorted = np.sort(kth_distances)

plt.figure(figsize=(8, 4))
plt.plot(kth_distances_sorted)
plt.xlabel("Points sorted by distance")
plt.ylabel(f"Distance to {min_samples}-th nearest neighbour")
plt.title("K-Distance Plot — set eps at the knee")
plt.axhline(y=0.3, color="red", linestyle="--", label="eps = 0.3 (knee here)")
plt.legend()
plt.tight_layout()
plt.savefig("kdistance_plot.png", dpi=150)
plt.show()

# The knee in this plot is approximately at y=0.3
# Use that as your eps value

from sklearn.cluster import DBSCAN

# Apply the eps chosen from the k-distance plot
model = DBSCAN(eps=0.3, min_samples=5)
labels = model.fit_predict(X_scaled)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print(f"Clusters: {n_clusters}")   # Output: Clusters: 2
print(f"Noise: {n_noise}")         # Output: Noise: 8 (approx)

Tip

Set min_samples to 2 * n_features as a starting point. For 2D data, try min_samples=4. For higher-dimensional data (10+ features), increase min_samples accordingly — sparse neighbourhoods in high dimensions require more points to define a dense region.

---

Why DBSCAN Handles Arbitrary Shapes

K-Means partitions space into Voronoi cells — regions of space closest to each centroid. This is inherently linear. DBSCAN instead grows clusters by connectivity: if point A is close to point B and point B is close to point C, then A and C are in the same cluster even if they are far apart from each other. This lets DBSCAN trace curves, crescents, and rings.

from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score
import matplotlib.pyplot as plt

X, true_labels = make_moons(n_samples=300, noise=0.07, random_state=42)
X_scaled = StandardScaler().fit_transform(X)

# K-Means on crescent data
kmeans_labels = KMeans(n_clusters=2, random_state=42, n_init="auto").fit_predict(X_scaled)

# DBSCAN on the same data
dbscan_labels = DBSCAN(eps=0.3, min_samples=5).fit_predict(X_scaled)

kmeans_ari = adjusted_rand_score(true_labels, kmeans_labels)
dbscan_ari = adjusted_rand_score(true_labels, dbscan_labels)

print(f"K-Means ARI:  {kmeans_ari:.3f}")   # Output: K-Means ARI:  0.402
print(f"DBSCAN ARI:   {dbscan_ari:.3f}")   # Output: DBSCAN ARI:   0.981

# DBSCAN correctly identifies the two moons; K-Means cuts straight through them

---

DBSCAN for Anomaly Detection

Fraud detection, network intrusion, and sensor fault detection all share one property: the "normal" behaviour is dense and clustered, while the "anomalous" behaviour is sparse and isolated. DBSCAN was designed for exactly this.

import pandas as pd
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

# Simulate transaction data: most are normal, a few are suspicious
np.random.seed(42)
n_normal = 200
n_anomalies = 8

normal_transactions = pd.DataFrame({
    "amount": np.random.normal(loc=75, scale=20, size=n_normal),
    "hour_of_day": np.random.normal(loc=14, scale=3, size=n_normal).clip(0, 23)
})

anomalous_transactions = pd.DataFrame({
    "amount": [8500, 9200, 7800, 11000, 9500, 8900, 10200, 7600],  # abnormally high
    "hour_of_day": [3, 2, 4, 3, 2, 1, 4, 3]  # middle of the night
})

transactions = pd.concat([normal_transactions, anomalous_transactions], ignore_index=True)
X_scaled = StandardScaler().fit_transform(transactions)

model = DBSCAN(eps=0.4, min_samples=10)
transactions["cluster"] = model.fit_predict(X_scaled)
transactions["is_anomaly"] = transactions["cluster"] == -1

print(f"Total transactions: {len(transactions)}")
print(f"Flagged as anomalies: {transactions['is_anomaly'].sum()}")
print(f"\nAnomaly details:")
print(transactions[transactions["is_anomaly"]][["amount", "hour_of_day"]].round(1))
# Output:
# Total transactions: 208
# Flagged as anomalies: 8 (approx, depends on eps tuning)
# Anomaly details:
#       amount  hour_of_day
# 200   8500.0          3.0
# 201   9200.0          2.0
# ...

Tip

When using DBSCAN for anomaly detection, tune eps to match what "normal density" looks like in your data, not what produces the prettiest cluster count. The noise label is your anomaly flag — make sure your eps is tight enough to exclude genuine outliers but loose enough to keep genuine cluster members together.

---

Where DBSCAN Struggles

Varying density clusters: If one cluster is very dense and another is sparse, no single eps value works for both. A large eps merges everything; a small eps breaks the sparse cluster into noise.

from sklearn.datasets import make_blobs
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
import numpy as np

# Two clusters: one tight, one spread out
X_tight, _ = make_blobs(n_samples=100, centers=[[0, 0]], cluster_std=0.3, random_state=42)
X_spread, _ = make_blobs(n_samples=100, centers=[[8, 8]], cluster_std=2.0, random_state=42)
X = np.vstack([X_tight, X_spread])

X_scaled = StandardScaler().fit_transform(X)

# eps=0.3 finds the tight cluster but misses the spread one
labels_small = DBSCAN(eps=0.3, min_samples=5).fit_predict(X_scaled)
# eps=0.8 merges everything into one
labels_large = DBSCAN(eps=0.8, min_samples=5).fit_predict(X_scaled)

n_clusters_small = len(set(labels_small)) - (1 if -1 in labels_small else 0)
n_clusters_large = len(set(labels_large)) - (1 if -1 in labels_large else 0)

print(f"eps=0.3 -> {n_clusters_small} clusters, {list(labels_small).count(-1)} noise")
# Output: eps=0.3 -> 1 clusters, 77 noise  <- spread cluster lost
print(f"eps=0.8 -> {n_clusters_large} clusters, {list(labels_large).count(-1)} noise")
# Output: eps=0.8 -> 1 clusters, 0 noise   <- merged into one

Warning

DBSCAN with a single eps cannot handle clusters of drastically different densities. If your data has this structure, consider HDBSCAN (a hierarchical extension of DBSCAN available in hdbscan or sklearn.cluster.HDBSCAN in sklearn 1.3+), which adapts the density threshold locally.

---

DBSCAN vs K-Means: When to Use Which

Situation	Use
Round, blob-like clusters, k is guessable	K-Means
Non-spherical shapes (curves, rings, filaments)	DBSCAN
Need to detect outliers natively	DBSCAN
Large dataset (>50k rows), need speed	K-Means
Unknown number of clusters	DBSCAN
All clusters are similar density	Either
Clusters vary wildly in density	Neither — use HDBSCAN
Need interpretable centroid summaries	K-Means

Success

DBSCAN is underused because K-Means is what people learn first. In any problem where cluster shape matters (geospatial data, sensor readings, biological data) or where finding outliers is the goal, DBSCAN is the more honest algorithm. Learn the k-distance plot for tuning eps and DBSCAN becomes immediately practical.

---

---

What's Next

You've covered DBSCAN's core/border/noise point classification, the epsilon-neighbourhood and min_samples parameters, the k-distance plot for tuning epsilon, anomaly detection with the noise label, the varying-density failure mode, and the decision table comparing DBSCAN against K-Means. Next up: 05-evaluation-and-scaling — where you'll bring all three clustering algorithms together and learn how to evaluate and compare them using silhouette score, Davies-Bouldin index, and cluster profiling — plus the scaling decisions that determine which algorithm is appropriate for your dataset size.

Optional Deep Dive

Read the original DBSCAN paper "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise" by Ester, Kriegel, Sander, and Xu (1996, KDD Proceedings) — it is only 6 pages and provides the exact formal definitions of core, border, and noise points, the reachability relation, and the algorithm's computational complexity proof that explains why DBSCAN scales linearly with an index but quadratically without one.

← Hierarchical Clustering | Next: Evaluation and Scaling →