Agglomerative meanshift clustering via query set compression

Mean-Shift (MS) is a powerful non-parametric clustering method. Although good accuracy can be achieved, its com-putational cost is particularly expensive even on moder-ate data sets. In this paper, for the purpose of algorithm speedup, we develop an agglomerative MS clustering method called Agglo-MS, along with its mode-seeking ability and convergence property analysis. Our method is built upon an iterative query set compression mechanism which is mo-tivated by the quadratic bounding optimization nature of MS. The whole framework can be efficiently implemented in linear running time complexity. Furthermore, we show that the pairwise constraint information can be naturally integrated into our framework to derive a semi-supervised non-parametric clustering method. Extensive experiments on toy and real-world data sets validate the speedup advan-tage and numerical accuracy of our method, as well as the superiority of its semi-supervised version.