HDBSCAN (Hierarchical DBSCAN) › Formula

To understand how HDBSCAN works, we need to explore how it measures density, builds relationships between points, and selects meaningful clusters. The algorithm adapts to varying densities across the dataset, which is a capability that many traditional clustering methods lack. Let's build this understanding step by step, starting with the fundamental question: how do we measure local density in a way that works for clusters of different sizes and shapes?

Imagine you're standing in a crowded city square. If you look around and see many people nearby, you're in a dense area. If you see only a few people far away, you're in a sparse area. HDBSCAN uses a similar intuition, but formalizes it mathematically through the concept of neighborhoods.

For each point in the dataset, HDBSCAN asks: "How far do I need to look to find k other points?" This distance tells us about the local density around that point. Points in dense clusters will have nearby neighbors, while isolated points or noise will need to look much farther.

This idea is captured by the core distance, which measures the distance from a point to its k-th nearest neighbor:

$$\text{core}_k(x) = d(x, \text{kNN}(x))$$

where:

• $\text{core}_k(x)$: core distance of point $x$ (distance to its k-th nearest neighbor)
• $d(x, \text{kNN}(x))$: Euclidean distance from point $x$ to its k-th nearest neighbor
• $k$: the min_samples parameter, which controls how many neighbors we require (typically set to the minimum number of samples in a neighborhood for a point to be considered a core point)
• $x$: a data point in the dataset
• $\text{kNN}(x)$: the k-th nearest neighbor of point $x$

The core distance is small for points in dense regions and large for isolated points. This gives us a local measure of density that adapts to each point's immediate surroundings, rather than using a single global threshold like DBSCAN does.

Now comes the key insight: when measuring distances between points, we should account for the density of the regions they inhabit. Two points in a dense cluster should be considered "close" even if their Euclidean distance is moderate, because they're both in a region of high density. Conversely, two points in sparse regions should be considered "distant" even if they're relatively close in Euclidean space, because they're both in low-density areas.

This leads to the mutual reachability distance, which adjusts distances based on local density:

$$d_{\text{mreach}}(x,y) = \max\{\text{core}_k(x), \text{core}_k(y), d(x,y)\}$$

where:

• $d_{\text{mreach}}(x,y)$: mutual reachability distance between points $x$ and $y$ (a density-aware distance metric)
• $\text{core}_k(x)$: core distance of point $x$ (distance to its k-th nearest neighbor)
• $\text{core}_k(y)$: core distance of point $y$ (distance to its k-th nearest neighbor)
• $d(x,y)$: Euclidean distance between points $x$ and $y$
• $k$: the min_samples parameter (same as in the core distance calculation)
• $x, y$: two data points in the dataset

This formula ensures that the distance between two points is at least as large as the core distance of either point. Here's why this matters: if either point is in a sparse region (large core distance), the mutual reachability distance will reflect that sparsity, effectively "stretching" the distance between sparse regions. Points in dense regions (small core distances) remain close to each other, while points in sparse regions become farther apart.

This density-aware distance metric is the foundation that allows HDBSCAN to handle clusters of varying densities. By transforming the original distance space into a mutual reachability space, we create a representation where dense clusters are well-separated from sparse regions, making them easier to identify.

With our density-aware distances, we can now construct a hierarchical representation of the data. HDBSCAN builds a minimum spanning tree (MST) using the mutual reachability distances. The MST connects all points using the minimum total edge weight, creating a tree structure where each edge represents a connection between points.

The MST construction finds the spanning tree $T$ that minimizes:

$$\sum_{(x,y) \in T} d_{\text{mreach}}(x,y)$$

where:

• $T$: a spanning tree (a connected acyclic graph that connects all points in the dataset)
• $(x,y) \in T$: an edge in the spanning tree connecting points $x$ and $y$
• $d_{\text{mreach}}(x,y)$: mutual reachability distance between points $x$ and $y$ (used as the edge weight)
• $x, y$: data points connected by an edge in the tree

Why a tree? A tree structure captures the essential connectivity of the data while eliminating redundant connections. Each point is connected to the rest of the dataset through a unique path, and the edges in this tree represent the most "natural" connections based on our density-aware distances. This tree structure allows us to build a hierarchy by progressively removing edges.

The hierarchical nature emerges when we consider what happens as we remove edges from the MST in order of decreasing weight. Removing a long edge (representing a connection between sparse regions) separates the tree into components, which we can interpret as potential clusters. As we continue removing edges, we create a hierarchy of cluster structures at different density levels.

The challenge now is: which clusters should we select from this hierarchy? Not all clusters are equally meaningful. Some clusters appear only at very specific density thresholds and disappear quickly as we change the threshold. Others persist across a wide range of density levels, suggesting they represent stable, meaningful structures in the data.

HDBSCAN introduces the concept of stability to quantify how persistent a cluster is across different density thresholds. For each point in a cluster, we track when it first joins the cluster (its "birth" threshold) and when it leaves (its "death" threshold). A cluster that persists across many density levels, and contains many points that remain in the cluster for a long time, is considered more stable and therefore more meaningful.

The stability of a cluster $C$ is defined as:

$$\text{stability}(C) = \sum_{x \in C} (\lambda_{\text{death}}(x) - \lambda_{\text{birth}}(x))$$

where:

-$\text{stability}(C)$: stability score of cluster $C$ (a measure of how persistent the cluster is across different density thresholds)

• $\lambda_{\text{birth}}(x)$: density threshold (λ value) at which point $x$ first joins the cluster (the "birth" threshold)
• $\lambda_{\text{death}}(x)$: density threshold (λ value) at which point $x$ leaves the cluster (the "death" threshold), with $\lambda_{\text{death}}(x) > \lambda_{\text{birth}}(x)$
• $C$: a cluster (a set of data points that form a coherent group)
• $x \in C$: a data point belonging to cluster $C$
• $\sum_{x \in C}$: sum over all points in cluster $C$

This formula sums the "lifespan" of each point within the cluster across density thresholds. Since death occurs at a higher threshold than birth, the difference is positive, representing how long each point remains in the cluster. Clusters with high stability are those where many points remain together across a wide range of density levels, indicating a coherent structure that persists as density changes.

The final step is to select the set of clusters that maximizes total stability while ensuring no cluster is a subset of another. This optimization problem can be written as:

$$\text{optimal clusters} = \arg\max_{\mathcal{C}} \sum_{C \in \mathcal{C}} \text{stability}(C)$$

where:

-$\mathcal{C}$: a set of clusters selected from the hierarchy (a collection of non-overlapping clusters)

• $C \in \mathcal{C}$: a cluster in the selected set
• $\text{stability}(C)$: stability score of cluster $C$ (as defined in the stability formula above)
• $\sum_{C \in \mathcal{C}} \text{stability}(C)$: total stability across all selected clusters
• $\arg\max$: the argument (set of clusters) that maximizes the total stability

subject to the constraint that no cluster is a subset of another selected cluster. This ensures we select the most stable, meaningful clusters without redundancy.

The constraint prevents us from selecting both a parent cluster and its child cluster, which would double-count stability. Instead, we choose the cluster configuration that maximizes total stability across all selected clusters, giving us the representation that best preserves persistent structure in the data.

The mathematical foundation of HDBSCAN provides several important guarantees. The mutual reachability distance satisfies the triangle inequality, making it a proper metric. This property enables the use of efficient algorithms for MST construction, such as Kruskal's or Prim's algorithm.

The stability measure provides a principled, data-driven way to select clusters, addressing one of the main limitations of traditional DBSCAN: the need to manually choose a single density threshold. Instead of making this difficult choice, HDBSCAN explores all possible density thresholds and selects clusters based on how long they persist.

The hierarchical approach naturally captures nested cluster structures and provides a way to handle clusters of varying densities within the same dataset. The algorithm's theoretical foundation ensures convergence to a stable solution and provides guarantees about cluster quality under reasonable assumptions about the data distribution.

Let's create a visualization that demonstrates how the stability measure works in practice: