DBSCAN: optimal rates for density-based cluster estimation
From MaRDI portal
minimax optimalitydensity-based clusteringDBSCANcluster treeclustering consistencyHölder smooth density
Computational methods for problems pertaining to statistics (62-08) Density estimation (62G07) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Applications of graph theory (05C90) Probabilistic graphical models (62H22) Minimax procedures in statistical decision theory (62C20)
Abstract: We study the problem of optimal estimation of the density cluster tree under various assumptions on the underlying density. Building up from the seminal work of Chaudhuri et al. [2014], we formulate a new notion of clustering consistency which is better suited to smooth densities, and derive minimax rates of consistency for cluster tree estimation for Holder smooth densities of arbitrary degree alpha. We present a computationally efficient, rate optimal cluster tree estimator based on a straightforward extension of the popular density-based clustering algorithm DBSCAN by Ester et al. [1996]. The procedure relies on a kernel density estimator with an appropriate choice of the kernel and bandwidth to produce a sequence of nested random geometric graphs whose connected components form a hierarchy of clusters. The resulting optimal rates for cluster tree estimation depend on the degree of smoothness of the underlying density and, interestingly, match minimax rates for density estimation under the supremum norm. Our results complement and extend the analysis of the DBSCAN algorithm in Sriperumbudur and Steinwart [2012]. Finally, we consider level set estimation and cluster consistency for densities with jump discontinuities, where the sizes of the jumps and the distance among clusters are allowed to vanish as the sample size increases. We demonstrate that our DBSCAN-based algorithm remains minimax rate optimal in this setting as well.
Recommendations
Cites work
- scientific article; zbMATH DE number 6670731 (Why is no real title available?)
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 1461253 (Why is no real title available?)
- A plug-in approach to support estimation
- A population background for nonparametric density-based clustering
- Adaptive Hausdorff estimation of density level sets
- Complexity penalized support estimation.
- Consistency of Single Linkage for High-Density Clusters
- Consistent Procedures for Cluster Tree Estimation and Pruning
- Convergence rates for persistence diagram estimation in topological data analysis
- Detection of Abnormal Behavior Via Nonparametric Estimation of the Support
- Differential Topology
- Estimating the cluster tree of a density by analyzing the minimal spanning tree of a sample
- Fully adaptive density-based clustering
- Generalized density clustering
- Introduction to nonparametric estimation
- Measuring mass concentrations and estimating density contour clusters -- An excess mass approach
- Minimax theory of image reconstruction
- On boundary estimation
- On nonparametric estimation of density level sets
- Optimal rates for plug-in estimators of density level sets
- Rates of strong uniform consistency for multivariate kernel density estimators. (Vitesse de convergence uniforme presque sûre pour des estimateurs à noyaux de densités multivariées)
- Set estimation and nonparametric detection.
- Single linkage clustering and continuum percolation
- Smoothing of Multivariate Data
- Stability of density-based clustering
- U-processes: Rates of convergence
Cited in
(7)- scientific article; zbMATH DE number 5896448 (Why is no real title available?)
- Limit theory of sparse random geometric graphs in high dimensions
- An axiomatic definition of hierarchical clustering
- Moving Up the Cluster Tree with the Gradient Flow
- Confidence regions for filamentary structures
- scientific article; zbMATH DE number 7626762 (Why is no real title available?)
- Generalized cluster trees and singular measures
This page was built for publication: DBSCAN: optimal rates for density-based cluster estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5214267)
