Skip to content
AI.info

Unsupervised learning

OPTICS and HDBSCAN Across Density Scales

Use reachability ordering and hierarchical density stability to analyze variable-density data without treating either method as parameter-free.

By the end you can

729 million stars and no single radius that works across the sky

729 million Gaia DR3 sources, down to G~20, in one table, to be clustered in one pass. Crowded fields packed against nearly empty sky. Any single neighbourhood radius that resolves the crowded regions dissolves the sparse ones. Hunt and Reffert ran that blind all-sky search with HDBSCAN in 2023, and the hierarchy returned a catalogue instead of a partition: “We recovered 7167 clusters, 2387 of which are candidate new objects and 4782 of which crossmatch to objects in the literature, including 134 globular clusters.”

The same run also passed judgement on earlier work. 1152 Milky Way Star Cluster catalogue entries that should have been detectable did not appear, which the authors suggest may mean they are not real. The delivered data confirm the counts independently. The VizieR catalogue at Strasbourg ships clusters.dat with exactly 7167 records and members.dat with 1291929 member stars, while its ReadMe still reproduces the earlier submitted abstract's rounded counts of 7200 and 2420. The table row count is the figure to quote. You only learn that by opening the table.

OPTICS and HDBSCAN answer variable density by examining structure across scales rather than at one. They reduce dependence on a single radius. They do not remove the modeling choices — representation, metric, minimum support, and a selection rule — that decide what comes out the other end.

Multiscale density methods trade one threshold for a hierarchy and a selection rule.

Comparison

DBSCAN, OPTICS, and HDBSCAN, with measured numbers against each

The strongest method is the one whose output contract matches the investigation, and on this question there are measured numbers rather than adjectives.

Before that all-sky catalogue came a bake-off. In 2021 Hunt and Reffert ran DBSCAN, HDBSCAN and Gaussian mixture models over the same Gaia DR2 fields, scored against 1385 known open clusters. “DBSCAN was sensitive to 50% to 62% of the true positive open clusters in our sample, with generally very good specificity and precision. HDBSCAN traded precision for a higher sensitivity of up to 82%, especially across different distances and scales of open clusters.” The Gaussian mixture models were sensitive to only 33%. The sensitivity HDBSCAN bought with precision was not cosmetic. It turned up 41 new open cluster candidates, three of them closer than 500 pc, and the delivered VizieR catalogue carries clustern.dat with exactly 41 records — “List of new open clusters reported by this work” — beside 5175 per-algorithm detections in clusterl.dat.

DBSCAN cuts the density landscape at one explicit epsilon: a simple final partition, clear core and border semantics, worth using when epsilon carries domain meaning, and hostage to a single global scale.

How much of a hostage was fought out in print. Gan and Tao proved an Omega(n^4/3) lower bound for d>=3 in 2015 and proposed rho-approximate DBSCAN, which their abstract says “should replace DBSCAN on big data due to the latter's computational intractability”. Five authors answered in 2017 in ACM Transactions on Database Systems, noting that the 2015 article “won the conference's best paper award”, and offered diagnostics rather than a replacement. Two of those diagnostics are numbers. One is the noise rate: “The desirable amount of noise will usually be between 1% and 30%”. The other is the biggest cluster: “If the largest component contains more than 20% to 50% of the clustered points, either a hierarchical approach such as OPTICS [3], or HDBSCAN* [13] should be used, or DBSCAN should be run again with a smaller ε radius.” Those two ranges are the exit condition. They tell you when epsilon has stopped being one scale for the data and become one scale imposed on it.

OPTICS orders the data so several density scales stay visible: a reachability plot for exploration, DBSCAN-like cuts extractable on demand, interpretation that can be subjective. Reach for it when the question is where the density transitions sit. HDBSCAN condenses the hierarchy by persistence: varying density handled more flexibly, controlled by minimum cluster size and its relatives, membership strengths attachable per point. Persistence is not domain value. That 2017 reply puts the two on the same footing, as the pair that “remove the need to choose ε”.

FigureComparison · 3 columns

DBSCAN

One explicit epsilon cut through the density landscape.

  • Simple final partition
  • Clear core and border semantics
  • Sensitive to one global scale
  • Useful when epsilon has domain meaning

OPTICS

Ordering that exposes several density scales.

  • Reachability plot supports exploration
  • Can extract DBSCAN-like cuts
  • Interpretation can be subjective
  • Useful for studying density transitions

HDBSCAN

Hierarchy condensed by cluster persistence.

  • Handles varying density more flexibly
  • Uses minimum cluster size and related controls
  • Can assign membership strengths
  • Persistence is not domain value

Example

Reading multiscale density output carefully

The diagnostic object often matters as much as the final labels. And the rule that turns a diagnostic into labels has a documented defect of its own.

  • Reachability valley: A deep broad valley in OPTICS suggests a dense region relative to its surroundings, not a guaranteed semantic class. The step from valley to cluster is not settled engineering. Schubert and Gertz wrote in 2018 that “Multiple methods for automatic detecting such valleys have been proposed, but all of them tend to produce a particular artifact, where some point is included in the cluster that may be far away from the remainder.” Their conclusions explain why nobody caught it: the correction moves “usually just 0-2 samples per cluster”, so the artifact “easily goes unnoticed” in ARI or NMI.
  • Extraction rule: The predecessor-consistency fix Schubert and Gertz proposed now sits in two independent packages, differently. scikit-learn cites their 2018 paper for its xi extraction and states that “This implementation deviates from the original OPTICS by first performing k-nearest-neighborhood searches on all points”. The CRAN R package dbscan says of optics() that “The used algorithm was originally contributed by the ELKI framework and is explained in Schubert et al (2018), but contains a set of fixes.” One paper, three implementations, three sets of deviations. Record which one you ran.
  • Nested group: A broad HDBSCAN cluster may contain smaller persistent subclusters, so coarse and fine readings of the same data can both be defensible. The hierarchy is what lets you show them side by side instead of choosing silently.
  • Membership strength: A low value can identify an uncertain boundary point, but it is not a calibrated probability of a human category. It expresses association with density structure and nothing else.
  • Noise fraction: Large noise can reflect real rarity, an inappropriate metric, weak support, or the minimum-cluster-size choice. Rescaling the features changes the neighborhoods that produced it, even though HDBSCAN itself is invariant to uniform scaling of all coordinates.

Key idea

Cluster persistence can optimally discard the group you care about

A small operationally critical group may occupy a narrow density range and receive lower persistence than a broad common population. Selection by stability can then drop exactly the group the task was about. This is not a rough heuristic misfiring, which is why it binds so hard. In 2015 Campello and three co-authors set the rule out: “In the unsupervised scenario, the algorithm corresponding to this postprocessing module provides a global, optimal solution to the formal problem of maximizing the overall stability of the extracted clusters.” An optimal answer is still an answer about density.

The mechanism is one comparison, stated plainly in the reference implementation's documentation, “How HDBSCAN Works”: “If, on the other hand, the cluster's stability is greater than the sum of its children then we declare the cluster to be a selected cluster and unselect all its descendants.” A rare branch loses to its parent whenever the parent wins that sum, and nothing in the test knows what the branch contains. Inspect the condensed tree and the rare branches before you accept the flat selection. Business importance and density persistence answer different questions. The optimum here is an optimum in stability.

Stable density is not the same thing as high consequence.

Steps

Compare density methods across a controlled parameter grid

Preserve hierarchy diagnostics and example-level uncertainty, and record which build produced them. 1. Validate geometry: check scaling, metric, duplicate mass, and high-dimensional neighborhood quality. 2. Fit a DBSCAN baseline with one interpretable radius, then test it against the published triggers — noise outside 1% to 30%, or a largest component holding more than 20% to 50% of the clustered points. 3. Inspect OPTICS: read the reachability valleys and compare extraction rules across plausible parameters. 4. Inspect HDBSCAN: condensed trees, persistence, membership strength, cluster size, and noise. 5. Test rare groups: verify whether small consequential regimes survive the hierarchy and the selection rule. 6. Report alternatives: document coarse, fine, and unassigned structure rather than one flat label set.

Step 4 has a version number attached to it, and it matters. The hdbscan Python package was published in the Journal of Open Source Software in March 2017. The accelerated algorithm behind it followed in May, from McInnes and Healy. scikit-learn adopted that implementation as cluster.HDBSCAN in version 1.3.0, released June 2023: “By performing a modified version of cluster.DBSCAN over multiple epsilon values simultaneously, cluster.HDBSCAN finds clusters of varying densities making it more robust to parameter selection than cluster.DBSCAN.”

The changelog is more precise about what you are actually running: “This implementation is an adaptation from the original implementation of HDBSCAN in scikit-learn-contrib/hdbscan, by Leland McInnes et al.”, contributed in pull request #26385 by Meekail Zain, and missing a few features from the original implementation. Two packages, one algorithm, not identical behaviour. Name the one you ran in the report, next to the parameters.

FigureProcess · 6 steps

  1. 1. Validate geometry

    Check scaling, metric, duplicate mass, and high-dimensional neighborhood quality.

  2. 2. Fit a DBSCAN baseline

    Use one interpretable radius to reveal the limitations of a single scale.

  3. 3. Inspect OPTICS

    Read reachability valleys and compare extraction rules across plausible parameters.

  4. 4. Inspect HDBSCAN

    Review condensed trees, persistence, membership strength, cluster size, and noise.

  5. 5. Test rare groups

    Verify whether small consequential regimes survive the hierarchy and selection rule.

  6. 6. Report alternatives

    Document coarse, fine, and unassigned structures rather than only one flat label set.

Visual

Two ways to represent density across scales

OPTICS preserves an ordering and a reachability profile; HDBSCAN builds a cluster hierarchy and condenses it. The scikit-learn user guide states the first relationship exactly: “The OPTICS algorithm shares many similarities with the DBSCAN algorithm, and can be considered a generalization of DBSCAN that relaxes the eps requirement from a single value to a value range.”

The OPTICS reachability view orders points so that valleys suggest dense regions across neighborhood scales. It stores reachability distances, supports several extraction choices, requires either plot interpretation or an extraction rule, and can reveal nested density structure. The HDBSCAN hierarchy is built from mutual-reachability structure and selects persistent groups. It uses minimum cluster size as its main control, can represent varying densities, provides noise and soft-membership information, and still depends on the metric and on the sample it was given. Both keep the alternatives that one DBSCAN cut throws away — which is what the OPTICS run-time premium in the closing section buys.

FigureComparison · 2 columns

OPTICS reachability view

Orders points so valleys suggest dense regions across neighborhood scales.

  • Stores reachability distances
  • Supports several extraction choices
  • Requires plot interpretation or extraction rules
  • Can reveal nested density structure

HDBSCAN hierarchy

Builds a hierarchy from mutual-reachability structure and selects persistent groups.

  • Uses minimum cluster size
  • Can represent varying densities
  • Provides noise and soft membership information
  • Still depends on metric and sampling

A hierarchy preserves alternatives that a single DBSCAN cut discards.

Analogy

Reading terrain with contour lines instead of one flood level

Contour lines say more about a landscape than any single flood level does. One flood level gives a single set of islands. The full contour map shows which peaks persist as the water rises and falls.

The analogy breaks in one place, and it is the place that matters. Physical elevation is observed directly; statistical density is estimated from sampled points and a chosen metric. Sparse coverage can manufacture ridges or erase them. A persistent branch is evidence about the sample and the metric before it is evidence about the world.

Persistence across scales is useful evidence, not a certificate of meaning.

Multiscale methods reveal more structure and more judgment

OPTICS and HDBSCAN are powerful when density varies, but they do not remove the analyst from the loop. The representation, metric, minimum support, and selection rule still define the result. Use the hierarchy to expose alternatives and uncertainty; a single flat partition should be a downstream decision, not the only artifact retained.

That refusal was the design. Four authors published OPTICS in ACM SIGMOD Record in June 1999, and the abstract opens with it: “We introduce a new algorithm for the purpose of cluster analysis which does not produce a clustering of a data set explicitly; but instead creates an augmented ordering of the database representing its density-based clustering structure.” That single ordering carries information equivalent to the density-based clusterings for a broad range of parameter settings.

The price is measured, not rhetorical. Later in the same paper the authors report: “It simply turned out that the run-time of OPTICS was almost constantly 1.6 times the run-time of DBSCAN.” One run at 1.6 times the cost, against one radius fixed in advance and one partition you cannot interrogate afterwards. Where the world has no natural single scale, that is a cheap exchange.

Keep the density hierarchy when the world does not have one natural scale.

Key takeaways