56  DBSCAN and HDBSCAN

Unlike K-Means or hierarchical methods which assume convex or compact clusters, density-based algorithms partition data by discovering contiguous regions of high point density separated by low-density noise (Ester et al. 1996).

1 Fundamental Definitions

DBSCAN requires two parameters: neighborhood radius \(\varepsilon\) and minimum points threshold \(\text{minPts}\).

Definition. \(\varepsilon\)-Neighborhood: \[ N_\varepsilon(\mathbf{x}) = \{\mathbf{y}\in\mathcal{D} \mid d(\mathbf{x},\mathbf{y})\leq\varepsilon\}. \tag{1}\]

Point Categorization: - Core Point: \(|N_\varepsilon(\mathbf{x})|\geq\text{minPts}\). - Border Point: \(|N_\varepsilon(\mathbf{x})|<\text{minPts}\) but \(\mathbf{x} \in N_\varepsilon(\mathbf{y})\) where \(\mathbf{y}\) is a core point. - Noise Point: Neither core nor border point.

DBSCAN — ε-Neighborhood Explorer
Adjust ε and minPts parameters to visualize core, border, and noise designations

ε = 0.9

minPts = 3

2 HDBSCAN

Hierarchical DBSCAN (HDBSCAN) builds a hierarchical tree of density-based clusters, extracting persistent clusters across varying densities (Campello et al. 2013).

Definition. Mutual Reachability Distance: \[ d_{\text{mreach},k}(\mathbf{x},\mathbf{y}) = \max\{d_k(\mathbf{x}),\; d_k(\mathbf{y}),\; d(\mathbf{x},\mathbf{y})\}, \tag{2}\] where \(d_k(\mathbf{x})\) is the distance to the \(k\)-nearest neighbor of \(\mathbf{x}\).

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

X, y_true = make_moons(n_samples=300, noise=0.05, random_state=42)

db = DBSCAN(eps=0.15, min_samples=5)
labels = db.fit_predict(X)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = np.sum(labels == -1)

print(f"Clusters discovered: {n_clusters}")
print(f"Noise instances: {n_noise} ({100*n_noise/len(X):.1f}%)")

Clusters discovered: 2
Noise instances: 0 (0.0%)

3 Summary

DBSCAN and HDBSCAN identify non-spherical clusters of arbitrary geometric shapes without requiring a prior specified cluster count \(k\), automatically isolating noise instances (Ester et al. 1996; Campello et al. 2013).

4 References

Campello, Ricardo J. G. B., Davoud Moulavi, and Jörg Sander. 2013. “Density-Based Clustering Based on Hierarchical Density Estimates.” Advances in Knowledge Discovery and Data Mining, Lecture notes in computer science, vol. 7819: 160–72.

Ester, Martin, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.” Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 226–31.