Fully adaptive density-based clustering

Abstract

The clusters of a distribution are often defined by the connected components of a density level set. However, this definition depends on the user-specified level. We address this issue by proposing a simple, generic algorithm, which uses an almost arbitrary level set estimator to estimate the smallest level at which there are more than one connected components. In the case where this algorithm is fed with histogram-based level set estimates, we provide a finite sample analysis, which is then used to show that the algorithm consistently estimates both the smallest level and the corresponding connected components. We further establish rates of convergence for the two estimation problems, and last but not least, we present a simple, yet adaptive strategy for determining the width-parameter of the involved density estimator in a data-depending way.

Published at http://dx.doi.org/10.1214/15-AOS1331 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• A Population Background for Nonparametric Density-Based Clustering
• Fully adaptive density-based clustering
• Pruning nearest neighbor cluster trees
• Adaptive Hausdorff estimation of density level sets

Cited by in corpus (11)

• Fully adaptive density-based clustering
• Some remarks on polar actions
• Density Level Set Estimation on Manifolds with DBSCAN
• DBSCAN: Optimal Rates For Density Based Clustering
• Adaptive Clustering Using Kernel Density Estimators
• Minimax Hausdorff estimation of density level sets
• Improved Classification Rates for Localized SVMs
• A fully data-driven method for estimating density level sets
• Nonparametric Estimation of Surface Integrals on Level Sets
• An Asymptotic Equivalence between the Mean-Shift Algorithm and the Cluster Tree
• Density-based Clustering with Best-scored Random Forest