Mean-shift is an iterative procedure often used as a nonparametric clustering algorithm that defines clusters based on the modal regions of a density function. The algorithm is conceptually appealing and makes assumptions neither about the shape of the clusters nor about their number. However, with a complexity of O(n^2) per iteration, it does not scale well to large data sets. In this talk, we present a novel algorithm which performs density-based clustering much quicker than mean-shift, yet delivering virtually identical results. This algorithm combines subsampling and a stochastic approximation procedure to achieve a potential complexity of O(n) at each step. Its convergence is established. We evaluate its performances using simulations and applications to image segmentation and to the preprocessing of single-cell data, where the algorithm was tens or hundreds of times faster than the traditional mean-shift, yet causing negligible amounts of clustering errors. The algorithm can be combined with alternative acceleration strategies to further speed up clustering.
Ollivier Hyrien received his MS and PhD degrees in Statistics from the University of Rennes 1, France, in 2001. His is an Associate Professor in the Department of Biostatistics and Computational Biology at the University of Rochester Medical Center. His current methodological research centers on the development of flexible statistical methods for the analysis of large scale biomedical data sets, stochastic processes and their applications to study the dynamics of complex biological systems, and scalable implementation of these approaches using efficient algorithms, asymptotic approximations and numerical techniques.