Title: DBSCAN: Optimal Rates For Density Based Clustering,
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.