Density Level Set Estimation on Manifolds with DBSCAN

We show that DBSCAN can estimate the connected components of the λ-density level set x : f(x) ≥ λ given n i.i.d. samples from an unknown density f. We characterize the regularity of the level set boundaries using parameter β > 0 and analyze the estimation error under the Hausdorff metric. When the data lies in ℝD we obtain a rate of widetildeO(n-1/(2β + D)), which matches known lower bounds up to logarithmic factors. When the data lies on an embedded unknown d-dimensional manifold in ℝD, then we obtain a rate of widetildeO(n^-1/(2β + d· max1, β )). Finally, we provide adaptive parameter tuning in order to attain these rates with no a priori knowledge of the intrinsic dimension, density, or β.