Density Level Set Estimation on Manifolds with DBSCAN

Abstract

DBSCAN is one of the most popular clustering algorithms amongst practitioners, but it has received comparatively less theoretical treatment. We show that given \(\lambda > 0\) and its parameters set under appropriate ranges, DBSCAN estimates the connected components of the \(\lambda\)-density level set (i.e. \(\{ x : f(x) \ge \lambda \}\) where \(f\) is the density). We characterize the regularity of the level set boundaries using parameter \(\beta > 0\) and analyze the estimation error under the Hausdorff metric. When the data lies in \(\mathbb{R}^D\) we obtain an estimation rate of \(O(n^{-1/(2\beta + D)})\), which matches known lower bounds up to logarithmic factors. When the data lies on an embedded unknown \(d\)-dimensional manifold in \(\mathbb{R}^D\), then we obtain an estimation rate of \(O(n^{-1/(2\beta + d\cdot \max\{1, \beta \})})\). Finally, we provide adaptive parameter tuning in order to attain these rates with no a priori knowledge of the intrinsic dimension, density, or \(\beta\).