Local Cluster Cardinality Estimation for Adaptive Mean Shift

This article presents an adaptive mean shift algorithm in which every parameter used at a point is derived from that point's own distance distribution. The distance distribution from a point to all others is used to estimate the cardinality of the local cluster by identifying a local minimum in the density of that distribution; the statistics of the identified subset then set the bandwidth and the kernel radius threshold applied at that point. The estimator built this way is scale invariant, since the γ function it rests on is unchanged when the data is multiplied by a positive constant, so no length constant has to be chosen for the scale of the data. It is also local: γ evaluated at rank k depends only on the k nearest distances, and the mean shift kernel is truncated at the estimated cluster radius, so data lying beyond that radius neither enters the estimate of the local cluster nor contributes to the weighted mean. This contrasts with kernel density estimation, which in its basic form measures density in a neighborhood of fixed size and needs a bandwidth chosen for the dataset as a whole. Our algorithm is competitive within the adaptive mean shift family: it obtains a higher Rand index than the weighted adaptive mean shift method of Ren et al. (2014) on seven of the nine datasets of that study, four of them by more than 0.03 and three by less than 0.012, and it performs competitively on a broader clustering benchmark, in both cases without being given the number of clusters.