DBSCAN: Optimal Rates For Density Based Clustering

Understand

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.