DBSCAN clustering: Complete Guide — Principles, Examples, and Python Implementation

Summary

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is one of the most powerful clustering algorithms in unsupervised machine learning. Unlike K-Means, which imposes spherical clusters and requires knowing their number in advance, DBSCAN automatically discovers arbitrarily shaped clusters based on the local density of the data. It also identifies noise points (outliers) without any additional parameter. This guide covers the mathematical principle in detail, practical implementation in Python with scikit-learn, hyperparameter tuning, and concrete use cases.

Mathematical principle of DBSCAN

The three types of points

DBSCAN classifies each point in the dataset into one of the following three categories:

Core point — A point is called a core point if its neighborhood of radius eps contains at least min_samples points (including itself). In other words, a core point lies in a region dense enough to justify creating or extending a cluster.

Border point — A point is a border point if it is not a core point, but it lies within the eps neighborhood of at least one core point. It therefore belongs to that core point’s cluster without being a central element of it.

Noise point — A point that is neither a core point nor a border point. It is isolated from any dense region and is assigned the label -1, meaning it does not belong to any cluster.

The eps parameter: neighborhood radius

The eps (epsilon) parameter defines the radius of the neighborhood around each point. For a point p, its eps neighborhood includes all points q such that the distance between p and q is less than or equal to eps:

N_eps(p) = { q ∈ D | distance(p, q) ≤ eps }

Where D is the set of all data. The larger eps is, the wider the neighborhood and the easier it is to extend a cluster. Conversely, an eps that is too small fragments natural clusters into many small groups.

The min_samples parameter: minimum density

The min_samples parameter determines the minimum number of points required in the eps neighborhood for a point to be considered a core point. A common default value is min_samples = 5, but it should be adjusted according to the dimensionality and density of the dataset.

Cluster expansion through reachability

The heart of the algorithm relies on the notion of density reachability:

1. A point q is directly reachable from a core point p if q ∈ N_eps(p).
2. A point q is density reachable from p if there exists a chain of points p_1, p_2, …, p_n where p_1 = p, p_n = q, and each p_{i+1} is directly reachable from p_i (all intermediate points being core points).
3. Two points are density connected if they are both density reachable from the same core point.

A cluster is then defined as the maximal set of points mutually density connected. The algorithm proceeds by traversing the data and, for each unvisited core point, launching a DFS or BFS expansion that retrieves all density reachable points.

Algorithmic complexity

The time complexity of DBSCAN depends on the method used for neighborhood search:

• Naive (linear search): O(n²) where n is the number of points.
• With spatial tree (BallTree, KDTree): O(n · log n) on average in low-dimensional spaces.
• For high dimensions, performance declines due to the curse of dimensionality.

Intuition: understanding DBSCAN simply

Imagine you are flying over a world population map seen from an airplane, at night. You see dense bright areas (cities), less dense peripheries (suburbs), and vast dark areas (countryside, deserts, oceans).

DBSCAN works exactly the same way in a data space:

• Dense areas form clusters — like islands of population in an ocean of data. Their shape doesn’t matter: a cluster can be circular, elongated, crescent-shaped, a ring… DBSCAN detects them all.
• Empty areas are noise — isolated points in low-density regions are simply labeled as outliers.
• No need to set the number of clusters — unlike K-Means where you must choose k, DBSCAN determines on its own how many dense structures exist in your data.

This intuition is valuable: if your data contains distinct density structures separated by low-density regions, DBSCAN is an excellent candidate. If the data is uniformly distributed, no clustering algorithm will produce a meaningful result.

Python implementation with scikit-learn

Basic example with make_moons

The make_moons dataset perfectly illustrates the advantage of DBSCAN over K-Means. The two clusters have the shape of nested crescents — a structure that K-Means cannot capture because it assumes clusters are convex and spherical.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import silhouette_score

# Generate crescent-shaped data
X, y_true = make_moons(n_samples=500, noise=0.05, random_state=42)

# DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=5)
dbscan_labels = dbscan.fit_predict(X)

# Count clusters and noise
n_clusters_dbscan = len(set(dbscan_labels)) - (1 if -1 in dbscan_labels else 0)
n_noise_dbscan = list(dbscan_labels).count(-1)

# KMeans for comparison
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans_labels = kmeans.fit_predict(X)

# Silhouette scores
# Exclude noise points from the calculation
mask = dbscan_labels != -1
if n_clusters_dbscan > 1 and mask.sum() > n_clusters_dbscan:
    sil_dbscan = silhouette_score(X[mask], dbscan_labels[mask])
    print(f"DBSCAN Silhouette : {sil_dbscan:.4f}")

sil_kmeans = silhouette_score(X, kmeans_labels)
print(f"KMeans Silhouette : {sil_kmeans:.4f}")

# Visualization
fig, axes = plt.subplots(1, 3, figsize=(15, 4))

axes[0].scatter(X[:, 0], X[:, 1], c=y_true, cmap='viridis', s=10)
axes[0].set_title('Ground truth')

axes[1].scatter(X[:, 0], X[:, 1], c=dbscan_labels, cmap='plasma', s=10)
axes[1].set_title(f'DBSCAN ({n_clusters_dbscan} clusters, {n_noise_dbscan} noise)')

axes[2].scatter(X[:, 0], X[:, 1], c=kmeans_labels, cmap='plasma', s=10)
axes[2].set_title('KMeans (k=2)')

plt.tight_layout()
plt.savefig('dbscan_vs_kmeans_moons.png', dpi=150)
plt.show()

On this dataset, DBSCAN perfectly recovers the two crescents with a silhouette score higher than K-Means. The latter cuts the crescents in two along a linear boundary, which is a poor partition.

Noise detection with synthetic data

from sklearn.datasets import make_blobs

# Create blobs with outliers
X_blobs, _ = make_blobs(n_samples=300, centers=3, cluster_std=0.8,
                        random_state=42)
outliers = np.random.uniform(-12, 12, size=(20, 2))
X_all = np.vstack([X_blobs, outliers])

dbscan = DBSCAN(eps=1.0, min_samples=5)
labels = dbscan.fit_predict(X_all)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)
print(f"Detected clusters : {n_clusters}")
print(f"Noise points : {n_noise}")
print(f"Unique labels : {set(labels)}")

DBSCAN automatically identifies the 20 outliers as noise (label -1) while preserving the three natural clusters. K-Means, on the other hand, would force each outlier into one of the three clusters, which would shift the centroids and degrade the quality of the partitioning.

DBSCAN hyperparameters

eps (epsilon)

Description: Maximum neighborhood radius for considering two points as neighbors.

Impact:
– eps too small: the majority of points are classified as noise. The algorithm over-segments the data.
– eps too large: distinct clusters merge into a single massive group.
– Recommended value: use the k-distance curve method for an informed choice.

from sklearn.neighbors import NearestNeighbors

# k-distance curve for choosing eps
k = 5
nn = NearestNeighbors(n_neighbors=k)
nn.fit(X_all)
distances, indices = nn.kneighbors(X_all)

# Sort distances to the k-th neighbor
distances_k = np.sort(distances[:, k-1])

plt.figure(figsize=(8, 4))
plt.plot(distances_k)
plt.axhline(y=1.0, color='r', linestyle='--', label='eps=1.0')
plt.xlabel('Sorted points')
plt.ylabel(f'Distance to the {k}-th neighbor')
plt.title('k-distance curve for choosing eps')
plt.legend()
plt.show()

The elbow of this curve indicates a good eps value.

min_samples

Description: Minimum number of points in the eps neighborhood for a point to be considered a core point.

Practical rule: a common value is min_samples ≥ D + 1 where D is the dimensionality of the data. For 2D data, min_samples = 5 is a good starting point. For noisy data, increase this value.

metric

Description: Distance used for neighborhood search.

Common options:
– 'euclidean' (default): standard Euclidean distance.
– 'manhattan': Manhattan distance (sum of absolute differences).
– 'cosine': cosine similarity, useful for text data.
– 'haversine': geodesic distance on a sphere, ideal for GPS coordinates.

algorithm

Description: Neighbor search method.

Options:
– 'auto' (default): scikit-learn automatically chooses the best algorithm.
– 'ball_tree': efficient for moderate dimensions.
– 'kd_tree': fast in low dimensions.
– 'brute': exhaustive search, necessary for some metrics like ‘haversine’.

Advantages and limitations of DBSCAN

Advantages

1. No need to specify the number of clusters — the algorithm determines it automatically from the data structure.
2. Detection of arbitrarily shaped clusters — unlike K-Means which only finds convex clusters, DBSCAN detects complex, elongated, ring-shaped forms, etc.
3. Intrinsic noise detection — outliers are identified naturally without an additional parameter or separate algorithm.
4. Deterministic results — unlike K-Means whose result depends on random initialization, DBSCAN always produces the same result for given data and parameters.
5. Few assumptions about distribution — assumes neither a Gaussian distribution nor a particular cluster shape.

Limitations

1. Difficulty with varying densities — if your clusters have very different densities (one very dense cluster and one very diffuse cluster), a single (eps, min_samples) pair cannot capture them both well. Algorithms like HDBSCAN solve this problem.
2. Sensitivity to hyperparameters — the choice of eps is critical and non-trivial. A bad value leads to either too much noise or excessive cluster merging.
3. Performance in high dimensions — like all distance-based algorithms, DBSCAN suffers from the curse of dimensionality. Beyond a few dozen dimensions, distances lose their discriminative power.
4. Ambiguous border points — a border point belonging to the neighborhoods of several core points from different clusters may be arbitrarily assigned to one cluster depending on the order in which the data is traversed.

4 concrete use cases for DBSCAN

1. Geolocation and spatial analysis

DBSCAN excels naturally on geographic data. The 'haversine' metric allows computing real distances on the Earth’s surface. It is used to detect areas of high concentration: tourist hotspots, crime zones, delivery clusters, or to detect anomalous trajectories in GPS data.

# Approximate example with GPS coordinates
from sklearn.preprocessing import StandardScaler

coordonnees_gps = np.array([
    [48.8566, 2.3522],  # Paris
    [48.8600, 2.3400],
    [45.7640, 4.8357],  # Lyon
    [45.7700, 4.8300],
    [43.2965, 5.3698],  # Marseille
])

# For real data, use metric='haversine'
scaler = StandardScaler()
X_scaled = scaler.fit_transform(coordonnees_gps)

dbscan_geo = DBSCAN(eps=0.5, min_samples=2, metric='euclidean')
labels_geo = dbscan_geo.fit_predict(X_scaled)

2. Anomaly detection in cybersecurity

By analyzing network logs, normal connections form dense clusters of typical behaviors. Suspicious activities — intrusion attempts, data exfiltration, lateral movement — appear as isolated points or micro-clusters. DBSCAN automatically identifies these anomalies without the need to define explicit rules.

3. Image analysis and segmentation

In computer vision, DBSCAN can be used to segment images based on pixel similarity (color, texture, spatial position). Unlike K-Means which imposes a fixed number of segments, DBSCAN discovers the number of natural homogeneous regions and isolates aberrant pixels. This is particularly useful for edge detection or object extraction.

4. Genomic data analysis

In bioinformatics, gene expression data clustering often relies on DBSCAN. Co-expressed genes form dense clusters in the measurement space, while genes with atypical behavior are identified as noise. This allows researchers to discover functionally related gene groups without presupposing the number of relevant biological groups.

Comparison table: DBSCAN vs K-Means

Conclusion

DBSCAN is a fundamental clustering algorithm that solves two major problems of K-Means: the need to know the number of clusters and the inability to detect non-convex shapes. Its density-based principle allows it to naturally distinguish significant structures from noise, making it a valuable tool for data exploration.

The key to success with DBSCAN lies in a judicious setting of eps and min_samples. The k-distance curve is your best ally for this choice. If your data has very heterogeneous densities, consider HDBSCAN, a modern extension that overcomes this limitation.

See also

• Calculating the Minimum Surface Area of a Convex Polygon in a Grid with Python
• Computing Unitary Divisor Square Sums in Python: Complete Guide and Optimized Code