# Bagged k-Distance for Mode-Based Clustering Using the Probability of Localized Level Sets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 71 references that are in the map.
- First posted on arXiv 18 Oct 2022.

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

- [Analysis of KNN Density Estimation](https://mlsanity.com/paper/2010.00438/) (2020)
- [DBSCAN++: Towards fast and scalable density clustering](https://mlsanity.com/paper/1810.13105/) (2018)
- [Local nearest neighbour classification with applications to semi-supervised learning](https://mlsanity.com/paper/1704.00642/) (2017)
- [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 Set Estimation on Manifolds with DBSCAN](https://mlsanity.com/paper/1703.03503/) (2017)
- [The modal age of Statistics](https://mlsanity.com/paper/1807.02789/) (2018)
- [MeanShift++: Extremely Fast Mode-Seeking With Applications to Segmentation and Object Tracking](https://mlsanity.com/paper/2104.00303/) (2021)
- [On the Consistency of Quick Shift](https://mlsanity.com/paper/1710.10646/) (2017)
- [Fully adaptive density-based clustering](https://mlsanity.com/paper/1409.8437/) (2014)
- [Modal Regression using Kernel Density Estimation: a Review](https://mlsanity.com/paper/1710.07004/) (2017)
- [Under-bagging Nearest Neighbors for Imbalanced Classification](https://mlsanity.com/paper/2109.00531/) (2021)
- [CDF Transform-and-Shift: An effective way to deal with datasets of inhomogeneous cluster densities](https://mlsanity.com/paper/1810.02897/) (2018)

## Abstract (arXiv)

In this paper, we propose an ensemble learning algorithm named textitbagged k-distance for mode-based clustering (textitBDMBC) by putting forward a new measurement called the textitprobability of localized level sets (textitPLLS), which enables us to find all clusters for varying densities with a global threshold. On the theoretical side, we show that with a properly chosen number of nearest neighbors kD in the bagged k-distance, the sub-sample size s, the bagging rounds B, and the number of nearest neighbors kL for the localized level sets, BDMBC can achieve optimal convergence rates for mode estimation. It turns out that with a relatively small B, the sub-sample size s can be much smaller than the number of training data n at each bagging round, and the number of nearest neighbors kD can be reduced simultaneously. Moreover, we establish optimal convergence results for the level set estimation of the PLLS in terms of Hausdorff distance, which reveals that BDMBC can find localized level sets for varying densities and thus enjoys local adaptivity. On the practical side, we conduct numerical experiments to empirically verify the effectiveness of BDMBC for mode estimation and level set estimation, which demonstrates the promising accuracy and efficiency of our proposed algorithm.