Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

HDBSCAN (Hierarchical DBSCAN) › Example

Michael BrenndoerferAugust 17, 20255 min read

Machine Learning from ScratchAll chapters

Part 7 of 9Unsupervised Learning

Chapter 56HDBSCAN (Hierarchical DBSCAN) › Example

Reading section 4 of 8 · Example · 5 minSection 4 of 8 · 5 min

Section 4 of 8 · 5 min read

HDBSCAN (Hierarchical DBSCAN) › ExampleOne section · Sections in this chapter4 / 8 ↓

Sections in this chapter8

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Let's work through a concrete example to understand how HDBSCAN processes data step by step. We'll use a simple 2D dataset and trace through the key calculations.

In[5]:

Code

import matplotlib.pyplot as plt
import numpy as np

# Set up matplotlib
plt.style.use("default")
plt.rcParams["font.size"] = 14
plt.rcParams["axes.labelsize"] = 16
plt.rcParams["axes.titlesize"] = 20
plt.rcParams["xtick.labelsize"] = 14
plt.rcParams["ytick.labelsize"] = 14

# Create a simple example dataset
np.random.seed(42)
X = np.array(
    [
        [1, 1],
        [1.2, 1.1],
        [1.1, 1.3],  # Cluster 1
        [3, 3],
        [3.1, 2.9],
        [2.9, 3.1],  # Cluster 2
        [5, 1],
        [5.2, 1.1],  # Cluster 3
        [2, 5],
        [8, 8],  # Noise points
    ]
)

print("Example Dataset:")
print("Points:", X)
print("Number of points:", len(X))

Now let's calculate the core distances and mutual reachability distances step by step:

In[6]:

Code

# Calculate core distances (k=3 for min_samples)
k = 3
nbrs = NearestNeighbors(n_neighbors=k + 1).fit(X)
distances, indices = nbrs.kneighbors(X)

# Core distances (distance to k-th nearest neighbor)
core_distances = distances[:, k]  # k-th neighbor (0-indexed)

print("\nCore Distances (distance to 3rd nearest neighbor):")
for i, (point, core_dist) in enumerate(zip(X, core_distances)):
    print(f"Point {i}: {point} -> Core distance: {core_dist:.3f}")

In[7]:

Code

# Calculate mutual reachability distances
n_points = len(X)
mutual_reach_distances = np.zeros((n_points, n_points))

for i in range(n_points):
    for j in range(n_points):
        if i != j:
            euclidean_dist = np.linalg.norm(X[i] - X[j])
            mutual_reach_distances[i, j] = max(
                core_distances[i], core_distances[j], euclidean_dist
            )
        else:
            mutual_reach_distances[i, j] = 0

print("\nMutual Reachability Distance Matrix:")
print("Rows/Cols represent points 0-9")
print(mutual_reach_distances.round(3))

In[8]:

Code

# Build minimum spanning tree
mst = minimum_spanning_tree(mutual_reach_distances)
mst_dense = mst.toarray()

print("\nMinimum Spanning Tree (edge weights):")
print("This shows the mutual reachability distances for MST edges")
print(mst_dense.round(3))

Out[9]:

Visualization

Scatter plot showing points colored by core distances. — Original data points colored by their core distances. Each point's color intensity represents its distance to the 3rd nearest neighbor. Points in dense regions (clusters) have smaller core distances (darker colors), while isolated points have larger core distances (lighter colors). This visualization shows how HDBSCAN uses local density information to understand the data structure before clustering.

Minimum spanning tree showing hierarchical cluster structure. — Minimum spanning tree (MST) showing the hierarchical cluster structure. The red edges connect points with the minimum total weight, creating a tree that preserves useful connectivity while reducing complexity. This MST forms the backbone of HDBSCAN's hierarchical approach, where clusters are identified by removing edges in order of decreasing weight.

This example demonstrates the key steps of HDBSCAN:

Core Distance Calculation: Each point's core distance represents the distance to its k-th nearest neighbor.
Mutual Reachability Distance: This distance metric ensures that points in dense regions are closer to each other, while points in sparse regions are farther apart, making clusters easier to separate.
Minimum Spanning Tree: The MST connects all points with minimum total weight, creating a hierarchical structure that preserves the essential connectivity information.

The algorithm then uses this hierarchy to identify stable clusters by analyzing how clusters persist across different density thresholds.