DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a density-based clustering algorithm. It can find clusters of arbitrary shape and detect outliers as noise.

Basic Concept

DBSCAN uses two main parameters:

Parameter	Explanation
ε (epsilon)	Radius of the neighborhood around a point
min_points	Minimum number of neighbors within radius ε

Point Types

Type	Definition
Core Point	≥ min_points neighbors within radius ε
Border Point	< min_points neighbors, but within radius ε of a core point
Noise Point	Neither a core point nor a border point

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
import numpy as np

X, _ = make_moons(n_samples=200, noise=0.1, random_state=42)

dbscan = DBSCAN(eps=0.2, min_samples=5)
labels = dbscan.fit_predict(X)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print(f"Clusters found: {n_clusters}")
print(f"Number of noise points: {n_noise}")

Density-Reachable

Two connectivity concepts in DBSCAN:

Directly Density-Reachable: Point q is in the ε-neighborhood of point p
Density-Reachable: A chain of directly density-reachable points
Density-Connected: Two points are density-reachable from the same point

Visualizing the Results

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons, make_circles
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt
import numpy as np

fig, axes = plt.subplots(1, 2, figsize=(12, 5))

datasets = [
    make_moons(n_samples=200, noise=0.1, random_state=42),
    make_circles(n_samples=200, noise=0.05, factor=0.5, random_state=42)
]

for ax, (X, _) in zip(axes, datasets):
    X = StandardScaler().fit_transform(X)
    db = DBSCAN(eps=0.3, min_samples=5)
    labels = db.fit_predict(X)

    unique_labels = set(labels)
    for label in unique_labels:
        mask = labels == label
        if label == -1:
            ax.scatter(X[mask, 0], X[mask, 1], c='gray', alpha=0.5, label='Noise')
        else:
            ax.scatter(X[mask, 0], X[mask, 1], label=f'Cluster {label}')
    ax.legend()

plt.tight_layout()
plt.show()

Parameter Selection

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

X, _ = make_moons(n_samples=200, noise=0.1, random_state=42)

# K-distance graph to determine epsilon
neighbors = NearestNeighbors(n_neighbors=5)
neighbors.fit(X)
distances, _ = neighbors.kneighbors(X)
distances = np.sort(distances[:, -1])

plt.figure(figsize=(8, 4))
plt.plot(distances)
plt.xlabel('Point Index')
plt.ylabel('5th Nearest Neighbor Distance')
plt.title('K-Distance Graph')
plt.grid(True, alpha=0.3)
plt.show()

Example: Outlier Detection

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

np.random.seed(42)
X, _ = make_blobs(n_samples=300, centers=3, random_state=42)
# Add outliers
outliers = np.random.uniform(low=-10, high=10, size=(10, 2))
X_with_outliers = np.vstack([X, outliers])

dbscan = DBSCAN(eps=0.8, min_samples=5)
labels = dbscan.fit_predict(X_with_outliers)

outlier_mask = labels == -1
print(f"Number of outliers detected: {outlier_mask.sum()}")
print(f"Outlier indices: {np.where(outlier_mask)[0]}")

Pros and Cons

Pros	Cons
No need to specify k	Sensitive to ε and min_samples
Detects noise/outliers	Varying densities are hard to handle
Flexible cluster shapes	Not good for high-dimensional data
No scaling required	Hard to choose parameters

Parameter Selection Tips

Use the k-distance graph to determine ε
Rule of thumb: min_samples ≥ data dimensionality + 1
For large data: consider HDBSCAN (hierarchical DBSCAN)
Always scale your data before DBSCAN

Next chapter: PCA, a dimensionality reduction technique for simplifying high-dimensional data.

Next: PCA →