# An Asymptotic Equivalence between the Mean-Shift Algorithm and the Cluster Tree

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 53 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 11 of 11)

- [A Population Background for Nonparametric Density-Based Clustering](https://mlsanity.com/paper/1408.1381/) (2014)
- [Quickshift++: Provably Good Initializations for Sample-Based Mean Shift](https://mlsanity.com/paper/1805.07909/) (2018)
- [Density Level Sets: Asymptotics, Inference, and Visualization](https://mlsanity.com/paper/1504.05438/) (2015)
- [Consistent procedures for cluster tree estimation and pruning](https://mlsanity.com/paper/1406.1546/) (2014)
- [The modal age of Statistics](https://mlsanity.com/paper/1807.02789/) (2018)
- [Mixture model modal clustering](https://mlsanity.com/paper/1609.04721/) (2016)
- [On the Consistency of Quick Shift](https://mlsanity.com/paper/1710.10646/) (2017)
- [Nonparametric Inference For Density Modes](https://mlsanity.com/paper/1312.7567/) (2013)
- [Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering](https://mlsanity.com/paper/1506.06422/) (2015)
- [Fully adaptive density-based clustering](https://mlsanity.com/paper/1409.8437/) (2014)
- [Statistical Inference using the Morse-Smale Complex](https://mlsanity.com/paper/1506.08826/) (2015)

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

- [Clustering by Hill-Climbing: Consistency Results](https://mlsanity.com/paper/2202.09023/) (2022)

## Abstract (arXiv)

Two important nonparametric approaches to clustering emerged in the 1970's: clustering by level sets or cluster tree as proposed by Hartigan, and clustering by gradient lines or gradient flow as proposed by Fukunaga and Hosteler. In a recent paper, we argue the thesis that these two approaches are fundamentally the same by showing that the gradient flow provides a way to move along the cluster tree. In making a stronger case, we are confronted with the fact the cluster tree does not define a partition of the entire support of the underlying density, while the gradient flow does. In the present paper, we resolve this conundrum by proposing two ways of obtaining a partition from the cluster tree -- each one of them very natural in its own right -- and showing that both of them reduce to the partition given by the gradient flow under standard assumptions on the sampling density.