Adaptive Hausdorff estimation of density level sets

Abstract

Consider the problem of estimating the $\gamma$-level set $G_{\gamma }^{\ast }=\{x:f(x)\ge \gamma \}$ of an unknown $d$-dimensional density function $f$ based on $n$ independent observations $X_1,...,X_n$ from the density. This problem has been addressed under global error criteria related to the symmetric set difference. However, in certain applications a spatially uniform mode of convergence is desirable to ensure that the estimated set is close to the target set everywhere. The Hausdorff error criterion provides this degree of uniformity and, hence, is more appropriate in such situations. It is known that the minimax optimal rate of error convergence for the Hausdorff metric is $(n/\log n{)}^{-1/(d+2\alpha )}$ for level sets with boundaries that have a Lipschitz functional form, where the parameter $\alpha$ characterizes the regularity of the density around the level of interest. However, the estimators proposed in previous work are nonadaptive to the density regularity and require knowledge of the parameter $\alpha$. Furthermore, previously developed estimators achieve the minimax optimal rate for rather restricted classes of sets (e.g., the boundary fragment and star-shaped sets) that effectively reduce the set estimation problem to a function estimation problem. This characterization precludes level sets with multiple connected components, which are fundamental to many applications. This paper presents a fully data-driven procedure that is adaptive to unknown regularity conditions and achieves near minimax optimal Hausdorff error control for a class of density level sets with very general shapes and multiple connected components.

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

References in corpus (2)

• Generalization error bounds in semi-supervised classification under the cluster assumption
• Optimal rates for plug-in estimators of density level sets

Cited by in corpus (21)

• To Trust Or Not To Trust A Classifier
• Generalized density clustering
• Fully adaptive density-based clustering
• Quickshift++: Provably Good Initializations for Sample-Based Mean Shift
• Optimal rates of convergence for persistence diagrams in Topological Data Analysis
• Level sets estimation and Vorob'ev expectation of random compact sets
• Density Level Set Estimation on Manifolds with DBSCAN
• Learning Low-Density Separators
• Faster DBSCAN via subsampled similarity queries
• Modal-set estimation with an application to clustering
• Asymptotics of Lower Dimensional Zero-Density Regions
• DBSCAN: Optimal Rates For Density Based Clustering
• A fully data-driven method for estimating density level sets
• Non-Asymptotic Uniform Rates of Consistency for k-NN Regression
• Level set estimation from projection measurements: Performance guarantees and fast computation
• Locally Adaptive Label Smoothing for Predictive Churn
• Nonparametric Estimation of Surface Integrals on Level Sets
• The sample complexity of level set approximation
• Baseline zone estimation in two dimensions
• Nonparametric Trace Regression in High Dimensions via Sign Series Representation
• An Asymptotic Equivalence between the Mean-Shift Algorithm and the Cluster Tree