Hierarchical Clustering via Density Level Sets

36 concepts33 papers1 proposal

Traditional clustering algorithms often force data into rigid, flat partitions. Methods like $k$-means require you to specify the number of clusters in advance and struggle when clusters have non-convex shapes or varying densities.

Density-based hierarchical clustering offers a more natural alternative. Instead of forcing geometric boundaries, it defines clusters through the topology of the data's underlying probability density function. By treating clusters as connected regions of high density separated by valleys of low density, this paradigm allows us to discover nested, multi-scale structures without making restrictive geometric assumptions.

The Topographic Intuition of the Cluster Tree

To understand why this approach works, imagine the probability density function of a dataset as a multi-peaked mountain landscape. If you flood this landscape and gradually lower the water level, the highest peaks emerge first as isolated islands. As the water level continues to drop, these islands grow, and some eventually merge at the valleys connecting them.

If we track this sequence of emerging, splitting, and merging components across all possible density thresholds, we get a rooted, nested tree structure. This is known as the cluster tree or superlevel set tree (Justin Eldridge et al., Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering).

Density Threshold (λ)
   ▲
   │       Peak A      Peak B
   │         ▲           ▲
   │        / \         / \
   │       /   \       /   \
───┼───────┬───┬───────┬───┬─────── High Threshold: Two separate islands (A and B)
   │       │ A │       │ B │
   │       └───┘       └───┘
───┼───────────┬───────┬─────────── Low Threshold: Islands merge into one component
   │           │ A + B │
   │           └───────┘
   └─────────────────────────────► Space

This formulation provides a powerful theoretical advantage. As Sivaraman Balakrishnan et al. demonstrate in Cluster Trees on Manifolds, by defining clusters via these upper level sets, we can recover the intrinsic geometry of data lying on low-dimensional manifolds, effectively bypassing the curse of dimensionality that plagues distance-based methods in high-dimensional spaces.

Global Extraction: Estimating Level Sets

To implement this concept on finite, real-world samples, we must estimate these continuous level sets from discrete data points.

One direct method is to construct a sequence of empirical graphs where vertices and edges are filtered by a density threshold. Kamalika Chaudhuri et al. (Rates of convergence for the cluster tree) proved that by tracking how the connected components of these graphs evolve as the threshold changes, we can achieve provably consistent convergence to the true population cluster tree.

However, explicitly estimating density values at every point can be statistically challenging in practice. To circumvent this, the authors of Approximating Hierarchical MV-sets for Hierarchical Clustering show that one can directly estimate minimum volume (MV) sets using convex optimization. By building a graph where edge weights represent the maximum density level encountered along the path connecting two points, iteratively removing high-weight edges naturally reveals the underlying modal structure.

This level-set perspective is also deeply connected to anomaly detection. For instance, Nicolas Goix et al. (On Anomaly Ranking and Excess-Mass Curves) utilize nested empirical regions that maximize excess mass to guarantee a monotonic, consistent ranking of data points from high density (normal) to low density (anomalous).

Local Execution: Mode-Seeking and Density Paths

Sweeping a global threshold across an entire dataset can be computationally intensive. Fortunately, we can discover the exact same hierarchical structure from the bottom up using a localized graph-based mechanism known as mode-seeking or hill-climbing.

Instead of looking at global thresholds, every data point acts locally. Each point searches its immediate neighborhood and draws a directed edge to its nearest neighbor that possesses a higher local density.

  Point A (Low Density) ──► Point B (Medium Density) ──► Root Mode (Peak Density)

This simple rule organizes the dataset into a directed forest, often called a density-ascending dependency graph. Because every edge points upward along the density gradient, every path is guaranteed to terminate at a local density peak (a mode). The collection of points whose paths converge at the same mode forms an attraction basin (Haowen Ma et al., TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization).

Heinrich Jiang provided a critical unification of these two perspectives in On the Consistency of Quick Shift. He proved that this localized mode-seeking process—connecting points to their nearest higher-density neighbors—is mathematically guaranteed to recover the complete, true hierarchical cluster tree of the underlying distribution.

This graph-based architecture makes cluster verification highly efficient: to determine if two points belong to the same cluster, you simply traverse their paths upward to see if they share the same root node (Duarte Magano et al., Quantum density peak clustering). Furthermore, these density-driven paths capture long-range structural context without global overhead. As Senhui Guo et al. (Density-Aware Feature Embedding for Face Clustering) demonstrate, these chains effectively use high-density samples as anchors to pull distant outliers into the correct cluster skeleton.

Taming Finite-Sample Noise

While the mathematical theory is elegant, applying it to real-world data introduces a major obstacle: finite-sample noise. Random fluctuations in a finite sample create tiny, artificial local maxima. A naive mode-seeking algorithm will mistake every minor ripple for a true peak, resulting in severe over-segmentation.

To make density hierarchies robust, researchers rely on three primary strategies to separate true structural modes from random noise:

  1. Tree Pruning: Samory Kpotufe et al. (Pruning nearest neighbor cluster trees) show that empirical cluster trees can be cleaned by systematically cutting away branches that fail to contain a statistically significant amount of data mass, leaving behind only the true, high-confidence clusters.
  2. Robust Cores: Instead of routing points toward individual, highly unstable point-modes, the authors of Quickshift++: Provably Good Initializations for Sample-Based Mean Shift propose routing points toward robust "cluster-cores"—locally high-density regions of arbitrary shape. This keeps points within the same broad attraction basin even if the local density surface is rough.
  3. Topological Persistence: Rather than preventing over-segmentation during graph construction, you can allow minor peaks to form and then filter them topologically. Marius Huber et al. (AuToMATo: An Out-Of-The-Box Persistence-Based Clustering Algorithm) combine mode-seeking with statistical bootstrapping to measure the "persistence" (the height difference between a peak and the valley separating it from a higher peak) of each mode. Spurious peaks with low persistence are automatically merged into their taller neighbors.

Domain Adaptations

Because density hierarchies depend entirely on the intrinsic distribution of the data rather than fixed geometric shapes, they are highly versatile and adapt easily to complex domain-specific structures.

In 3D computer vision, standard distance clustering often fails when distinct objects are physically touching. To resolve this, Weiguang Zhao et al. (Divide and Conquer: 3D Point Cloud Instance Segmentation With Point-Wise Binarization) implement a multi-stage density grouping strategy: they first isolate and cluster reliable, high-density "core" points to establish instance seeds, and subsequently use a neighbor voting scheme to assign the low-density edge points to their correct boundaries.

On an astronomical scale, Dimitrios Kelesis et al. (Detecting and analysing the topology of the cosmic web with spatial clustering algorithms I: Methods) demonstrate that hierarchical density partitioning can map the cosmic web. By applying overdensity thresholds to spatial networks, they can automatically categorize vast cosmic structures into distinct topological classes—ranging from empty voids to dense filaments—purely based on their local density signatures.

Key Foundational Work

An Efficient Approach to Clustering in Large Multimedia Databases with Noise (1998) — contributed 1 concept elements to this direction.
A strategy for analysis of (molecular) equilibrium simulations: Configuration space density estimation, clustering, and visualization (2001) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_density_based_hierarchical_clustering_af61a608,
  title = {density-based hierarchical clustering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/density-based-hierarchical-clustering/rdr_af61a608f6324c5b8651311511f25c8d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_density_based_hierarchical_clustering_af61a608_v1,
  title = {density-based hierarchical clustering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/density-based-hierarchical-clustering/rdr_af61a608f6324c5b8651311511f25c8d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake