Nearest neighbour estimators of density derivatives, with application to mean shift clustering

• NN estimators introduced for arbitrary derivative order of density function.
• Efficient normal scale/rule of thumb choice of optimal number of NN.
• Application of NN estimator of density and density gradient to mean shift clustering.
• NN mean shift can give higher clustering quality than k-means and kernel mean shift.

Nearest neighbour estimators of the order derivatives of the probability density function are introduced. We establish their squared error consistency, and most importantly for data analysis, an automatic, single pass normal scale or ‘rule of thumb’ selector of the number of nearest neighbours. Density derivatives are crucial components for statistical unsupervised learning based on density gradient ascent known as mean shift clustering. The proposed automatic choice of the nearest neighbours for density gradients is applied to the mean shift clustering and is demonstrated to discover accurately the number, location and shape of non-ellipsoidal clusters in multivariate data analysis and image segmentation.