# Consistent procedures for cluster tree estimation and pruning

arXiv: https://arxiv.org/abs/1406.1546 · HTML: https://mlsanity.com/paper/1406.1546/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2014.

## Built on by (most cited first, 9 of 9)

- [Recovery Guarantees for Kernel-based Clustering under Non-parametric Mixture Models](https://mlsanity.com/paper/2110.09476/) (2021)
- [Moving Up the Cluster Tree with the Gradient Flow](https://mlsanity.com/paper/2109.08362/) (2021)
- [An Axiomatic Definition of Hierarchical Clustering](https://mlsanity.com/paper/2407.03574/) (2024)
- [Skeleton Clustering: Dimension-Free Density-based Clustering](https://mlsanity.com/paper/2104.10770/) (2021)
- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)
- [An Asymptotic Equivalence between the Mean-Shift Algorithm and the Cluster Tree](https://mlsanity.com/paper/2111.10298/) (2021)
- [Model-free Estimation of Latent Structure via Multiscale Nonparametric Maximum Likelihood](https://mlsanity.com/paper/2410.22248/) (2024)
- [Towards Robust and Scalable Density-based Clustering via Graph Propagation](https://mlsanity.com/paper/2605.00390/) (2026)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)

## Abstract (arXiv)

For a density f on mathbb Rd, a it high-density cluster is any connected component of x: f(x) ≥ λ, for some λ > 0. The set of all high-density clusters forms a hierarchy called the it cluster tree of f. We present two procedures for estimating the cluster tree given samples from f. The first is a robust variant of the single linkage algorithm for hierarchical clustering. The second is based on the k-nearest neighbor graph of the samples. We give finite-sample convergence rates for these algorithms which also imply consistency, and we derive lower bounds on the sample complexity of cluster tree estimation. Finally, we study a tree pruning procedure that guarantees, under milder conditions than usual, to remove clusters that are spurious while recovering those that are salient.