HDBSCAN* · density-based clustering · parameter sensitivity

The shrinking cluster

HDBSCAN* can change its answer when you raise min_samples by one small step. This page explains why, how to spot the cluster at risk, and how to prove that a step is safe.

A biologist clusters 20,000 cells and finds five cell types. A data team groups customer reviews into topics with BERTopic. An astronomer searches a star catalogue for new star clusters. All three use HDBSCAN*, and all three set its density parameter, min_samples, once, or leave it at the default.

A small change to that parameter, say from 30 to 35, usually changes little. In the benchmarks of my preprint, with min_cluster_size moving together with min_samples as in the default, about one step in six (16.9% on 47 datasets) changed the result a lot: a cluster vanished, two clusters merged, or a fifth of the points changed label.

This is not a hidden flaw. Any rule with a size threshold behaves this way: when a parameter changes, a cluster close to min_cluster_size can drop out or merge with another. The documentation says as much. The hdbscan guide shows that min_samples “clearly has a dramatic effect on clustering” and makes the clustering more conservative as it grows. The scikit-learn user guide says that min_samples “tends to be a more robust hyperparameter” than the eps of DBSCAN, a comparison with eps and not a claim that the partition stays the same. The docstrings of scikit-learn and hdbscan, and BERTopic’s guide, state that min_samples takes the value of min_cluster_size when it is left unset. Campello et al. (2015) describe it as a classic smoothing factor in density estimates, to which methods with an analogous parameter are typically robust, and fix it at a single non-critical value in their experiments. They also report that runs with other values did not change their main conclusions. What was missing is a measurement of how often a small step changes the flat partition, and a way to see it coming without refitting.

Trying the nearby values by brute force shows whether a step changes the result, but it is slow: on 100,000 points, a sweep over 24 values takes 24 to 80 minutes. The preprint proposes a cheaper check that uses the run you already have. It explains why a step changes the result, flags the cluster at risk and proves when a step is safe, at about 1% of the cost of a new run. These results come from a single preprint that has not yet been peer reviewed. To try the check on your own data, with scikit-learn or the hdbscan library:

pip install git+https://github.com/provezano/minpts-check
from minpts_check import check_min_samples
check_min_samples(X, min_samples=30, min_cluster_size=30).summary()

The demo below runs HDBSCAN* in your browser, so you can watch a cluster vanish.

Try it: 180 points, one density knob Tap a point to see its core distance.
Colours: selected clusters. Grey: noise. Solid circle: core distance at the current value; dashed: at the next value.
m = 30
Both parameters move together here, as when min_samples is left unset and takes the value of min_cluster_size.
–clusters
–noise points
–ARI with the next value
STABILITY STRIP · each bar is one step m → next m (height = ARI; red = fragile step, ARI < 0.8)
5value of min_samples →70

Three Gaussian clouds (60, 60 and 40 points) and 20 scattered points, as in the paper’s example, drawn at random here. The numbers differ from the paper’s; the behaviour is the same.

Summary

What the paper found

Why?Shrinkage

A higher min_samples changes the cluster tree. A selected cluster can shrink below the minimum cluster size, drop out of the selection and change the output.

Which cluster?82% vs 10%

A count from the current run flags the cluster at risk. On new tables, 82% of flagged clusters were lost, against 10% of unflagged clusters of the same size.

When is it safe?0 errors

A theorem gives conditions, checked on one run, under which the next value keeps the same clusters. No certified step was fragile.

Part 1 · The basics

How HDBSCAN* finds clusters

Picture the data as a landscape in which altitude is point density. As the water level drops, the densest peaks appear first as islands, and neighbouring islands later join. HDBSCAN* records this history as a tree and then picks one set of islands as the clusters.

Two parameters steer the process. min_samples (mpts in the paper) sets how many neighbours a point needs to count as dense. min_cluster_size (mclSize) sets the smallest island that counts as a cluster. In scikit-learn, the hdbscan library and BERTopic, min_samples takes the value of min_cluster_size when it is left unset, so by default the two move together. Click the five stages to see each one on the example.

CONDENSED TREE (current value of min_samples). Width = points still in the cluster; downwards = denser (λ = 1/radius). Coloured blocks = clusters selected by EOM.

The last stage, excess of mass (EOM), gives each branch a stability score: roughly, how long its points stay together as the density level rises. It then picks the branches with the highest total score, never a branch together with one of its descendants. Only branches with at least min_cluster_size points can be picked, and this rule is behind everything that follows.

Part 2 · The problem

A small step, a big change

With the method in place, we can measure how often a small step changes its answer. Neto et al. (2018) describe HDBSCAN* as robust to min_samples, in that a small change “typically leads to only a small or no change in the clustering structure”, a statement about the hierarchy rather than the flat clusters. Users work with the final flat partition, so the measurement has to be made on the partition.

The paper calls a step fragile when the outputs at two neighbouring values agree poorly, with an adjusted Rand index (ARI) below 0.8 and noise counted as one label. The neighbouring values come from a grid of 24 values between 5 and 120, each 11% to 20% above the previous one.

16.9%of steps were fragile on 47 new benchmark datasets (95% CI: 11.2–23.1)
91.2%of fragile steps in real pipelines changed the number of clusters
16.5%of points change label in a typical fragile step (median, benchmarks)
22.6%of steps were fragile on 10 larger OpenML tables

The real pipelines were single-cell analysis with scanpy and UMAP, topic modelling with BERTopic, and the search for star clusters in data from the Gaia satellite. When a step was fragile, a cluster almost always appeared, disappeared, split or merged.

ARI can hide such a change. In the paper’s example, the step from 35 to 40 deletes a 41-point cluster and relabels 23.3% of the points, yet the ARI is 0.91. The paper therefore also reports the number of clusters and the share of relabelled points.
Part 3 · Why it happens

The tree is to blame, not the threshold

To predict such changes, we first need to know which stage of the method causes them. When min_cluster_size follows min_samples, one step changes two things: the tree, because core distances grow, and the size threshold. A 2 × 2 design separates them by changing only the tree, only the threshold, or both. Pick a step in the lab and compare the four panels.

2 × 2 lab ARI measured against the original output (top left).
30 → 35

The lab shows one dataset. On 47 new datasets, the fragile steps split as follows.

the new tree alone changes the output each change alone does the threshold alone (2%) only both together
Rounded shares of fragile steps. Source: Table 5 of the paper.

EOM picks only among branches with at least min_cluster_size points. A new threshold on the old tree can remove only clusters that were already below it, which is rare. A new tree can shrink any branch. When a selected cluster drops below the threshold, it is no longer a candidate, and EOM re-decides the branch above it: the cluster becomes noise, joins a neighbour, or the branch is reorganised.

To test this directly, the paper fixed the threshold and planted clusters of known size. Clusters just above the threshold (1.2 to 1.35 times) were often lost, and clusters two to three times larger never were. Every shape tested behaved this way.

Fragile rate when only the tree changes, for clusters planted near the threshold. For clusters 2–3 times the threshold, the rate was 0.0% for every shape. 300 replicates; Holm-corrected tests. Source: Table 7 of the paper.

On real data, steps near the threshold were more fragile than steps far from it, after adjusting for the number of clusters, the noise share and the threshold itself (odds ratio 6.6). Some steps far from the threshold are fragile too, so size explains most cases but not all.

Part 4 · Which cluster

A predictor that uses a single run

If a cluster is lost because it shrinks in the new tree, we can ask how many of its points remain at the level where it is born. This needs no new tree: compute the core distances at the next value with one nearest-neighbour query, and count.

ŝ(C) = number of points p of C with corenext m(p) ≤ birth radius of C

If ŝ falls below the next min_cluster_size, the cluster cannot reappear unchanged. In the paper’s example, the 41-point cluster has ŝ = 38 at the step to 40, and it is lost. At the step from 8 to 9, every cluster has ŝ ≥ 43, well above the threshold.

The predictor on the example Uses the step chosen in the lab above.

The predictor was then tested on 25 OpenML tables that the work had never used, with the analysis fixed before the data were downloaded.

ŝ below the next threshold
82%
ŝ at or above the threshold
10%
Loss rate among clusters of similar size (1 to 1.25 times the next threshold; 4,205 clusters). Difference 72.7 points, 95% CI 54.2–87.6. AUC 0.821 for the predictor against 0.763 for size alone. Source: Table 9 of the paper.

The predictor ranks well both the clusters absorbed by a larger one (AUC 0.80) and those that dissolve into noise (0.94). It does not predict splits, which are rare here (40 of 1,620 losses) and follow a different mechanism. Splits dominate when min_samples goes down, a case the paper does not cover.

Used as an alarm, the rule “flag the step if any cluster has ŝ below the next threshold” flagged 48% of the steps and caught 89% of the fragile ones. Only 4.4% of the unflagged steps were fragile. This analysis is exploratory and has not been replicated.

Resampling the data shows the same size effect. Clusters just above the threshold disappeared in 52% of resamples, against 17% to 26% for larger ones.

Part 5 · When it is safe

A certificate that nothing changes

Predicting risk is useful, but proving safety is stronger. The paper’s theorem uses the current run and the neighbour distances at the next value. If its three conditions hold, the next value selects the same clusters, and every point outside a small tolerance set U keeps its label. The new tree is never built.

(S) size

A core that holds

Every selected cluster keeps a certified core of at least the next min_cluster_size points over all density levels the step can affect.

(D1) selected clusters

Stability to spare

Each selected cluster’s certified stability beats the most its descendants could reach.

(M) margins

Comfortable decisions

Every EOM decision in the current run won by more than the step can change it.

Schematic (not data). Each selected cluster has a certified core (hatched) that must keep at least min_cluster_size points. Points inside the core provably keep their label; points in U may change.

The size condition is where the shrinking mechanism returns. If a selected cluster can fall below the threshold during the step, the certificate does not claim safety. Of the fragile steps, 82.7% fail this condition first.

Same coverage, fewer mistakes
Certificate (|U| ≤ 1%)
0
Persistence rule
12
Size rule
15
Fragile steps among those declared safe, when each rule declares the same number of steps safe (815 certified steps in three studies). Exact 95% upper bound for the certificate: 0.5%. On 25 new tables: 0 of 261, against 8 and 2. Source: Figure 4 of the paper (post hoc analysis).

The certificate covers a minority of steps. With U capped at 1% of the points, it certified 9.5% of the steps on the exploratory data and 26.2% on a new benchmark set. It was built as a diagnostic that shows where stability can be proved and why it fails elsewhere. A large U still allows an ARI below 0.8, so U should be capped.

Rolle and Scoccola (2024) propose a flattening with a stability theorem. On the horizontal slice that HDBSCAN* uses, it was fragile on 22.1% of steps, against 16.7% for EOM (secondary analysis, no test). This agrees with their Proposition 45: a one-unit change of the parameter can move the hierarchy arbitrarily far. A certificate for min_samples therefore has to use the observed growth of the core distances.
Part 6 · Cost

Why not simply rerun?

Both tools may seem unnecessary, since one could simply rerun HDBSCAN* at the next value. A rerun shows what changed but not why, and it costs a full fit per value. The predictor and the certificate need the current run plus one nearest-neighbour query for the whole grid.

100,000 points, 1 threadcovertypeHiggs
One HDBSCAN* fit63 s208 s
Sweep over the 24-value grid24 min80 min
Certificate check (after the neighbour query)1.5 s1.2 s
The check costs about 1% of a fit. Source: the paper, Section 1 and Supplementary Section S4.3.
Part 7 · In practice

What to do with this

The quickest route is minpts-check, which runs the whole check from one fit and one neighbour query: it flags the clusters at risk, proves the safe steps and handles the counting convention.

pip install git+https://github.com/provezano/minpts-check
from minpts_check import check_min_samples
check_min_samples(X, min_samples=30, min_cluster_size=30).summary()

To check by hand, whether you use HDBSCAN* directly, in scikit-learn or inside BERTopic:

  1. Run a few values of min_samples around your choice and check that the clusters hold.
  2. Treat a selected cluster close to min_cluster_size, or with ŝ below the next threshold, as a warning. Computing ŝ costs one neighbour query and no refit.
  3. When stability matters, report the agreement between neighbouring values, with and without noise, and the certified steps.
  4. Mind the counting convention: scikit-learn’s min_samples counts the point itself and the hdbscan library’s does not, so scikit-learn’s m + 1 equals hdbscan’s m.

If you compare methods that use HDBSCAN*, report min_samples, min_cluster_size, the extraction method and the tree algorithm. Prefer exact trees when stability matters: the default approximate tree was more fragile (29.3% of steps against 23.4% on the exploratory data).

Computing ŝ step by step
  1. Run HDBSCAN* at the current value m and keep the condensed tree and the selected clusters.
  2. For each selected cluster C, take the level λ at which it is born in the condensed tree; its birth radius is 1/λ.
  3. Compute, for every point, the distance to the neighbour that defines its core at the next value m′ (one k-NN query; mind the counting convention above).
  4. ŝ(C) is the number of points of C whose new core distance is at most the birth radius.
  5. If ŝ(C) < m′ (the next min_cluster_size), flag C as at risk.

The paper’s supplementary material includes a reference implementation of the stability report and of the certificate checker; minpts-check packages both for everyday use.

Part 8 · How it was tested

One exploratory study and six replications

The numbers on this page come from seven studies. The tools were developed on 61 datasets. Each later study used data that no earlier study had touched, tested a few hypotheses with Holm’s correction, and followed an analysis plan written before the runs. Every planned hypothesis is reported, confirmed or not.

DataQuestionConfirmed
61 benchmark and OpenML datasetsexploration: first form of every tool–
47 new datasets, 3 seedshow often; which stage causes it1 of 5
planted Gaussians; 51 datasetsmechanism, with the threshold fixed3 of 4
five planted shapes; 19 tablesrobustness to shape and confounders8 of 8
10 OpenML tables, up to 20,000 pointslarger tables: rate, mechanism, certificate3 of 5
17 datasets: single-cell, BERTopic, Gaiareal pipelines3 of 4
25 new OpenML tablespredictor ŝ; resampling3 of 4

Some hypotheses were not confirmed, and they are informative too:

  • In the real pipelines, the fragile rate (13.6%) was not significantly above 10%, and it varied by pipeline.
  • In BERTopic, two UMAP seeds at the same min_samples disagreed in 98.1% of cases, so the embedding seed moves the output far more than the parameter.
  • On the larger tables, the size ratio as a single pooled score ranked steps only moderately (AUC 0.71, below the planned bar), though it ranked them well within each table.
  • Decreases of min_samples, leaf extraction and approximate trees are outside the main claims.
Context

What was already known

HDBSCAN* was proposed by Campello, Moulavi and Sander (2013, 2015), and McInnes and colleagues (2017) wrote the popular implementation. The stability of the hierarchy is well studied, from the statistical theory of density cluster trees to ToMATo (Chazal and colleagues, 2013) and the work of Rolle and Scoccola (2024), who also show that the hierarchy can change arbitrarily after a one-unit change of the parameter.

Earlier work had also seen sensitivity in the final partition. PLSCAN (Bot and colleagues, 2025) notes on one example that HDBSCAN*’s clusterings vary considerably with the parameter and chooses the minimum cluster size by persistence. FOSC-X (Simpson and Campello, 2026) lists near-optimal EOM solutions on a fixed tree. Malzer and Baum (2020) documented over-splitting into micro-clusters at small values. Neto and colleagues (2018, 2021, 2022) compute the hierarchies for all values at once and describe them as robust to small changes. Hunt and Reffert (2021) found, on Gaia data, that the recovery rate of known star clusters ranges from 0.42 to 0.82 with the minimum cluster size.

That a cluster near the size threshold can drop out when a parameter changes is expected of any threshold rule. The paper adds a label-free measure of agreement between neighbouring values, the stage of the method that causes each change, a prediction of which cluster will be lost, and a proof of when a step is harmless. These results come from one preprint and still need independent replication.

Quick reference

Glossary

min_samples (mpts)
How many neighbours define a point’s core distance. Controls the smoothing of the density.
min_cluster_size (mclSize)
Minimum size of a branch for it to count as a cluster in the condensed tree.
core distance
Distance from a point to its m-th nearest neighbour. Small in dense regions.
mutual reachability
max(core(p), core(q), distance(p, q)). The distance used to build the tree.
λ (lambda)
Density level, equal to 1 / radius. The larger, the denser.
condensed tree
The hierarchy after discarding branches smaller than min_cluster_size.
EOM
Excess of mass: the rule that selects the final clusters by maximising total stability.
fragile step
Two neighbouring values of min_samples whose outputs have ARI < 0.8 (noise counted as one label).
ARI
Adjusted Rand index: 1 = identical partitions; near 0 = agreement by chance.
lost cluster
No cluster of the other output has a Jaccard index of at least 1/2 with it.
ŝ
Number of the cluster’s points whose new core distance fits within the radius at which the cluster is born (its birth radius).
tolerance set U
The only points the certificate does not cover; all others provably keep their label.