On the Performance of Clustering in Hilbert Spaces
Abstract—Based on � randomly drawn vectors in a separable Hilbert space, one may construct a �-means clustering scheme by minimizing an empirical squared error. We investigate the risk of such a clustering scheme, defined as the expected squared distance of a random vector ˆ from the set of cluster centers. Our main result states that, for an almost surely bounded ˆ, the expected excess clustering risk is y @ Ia�A. Since clustering in high (or even infinite)-dimensional spaces may lead to severe computational problems, we examine the properties of a dimension reduction strategy for clustering based on Johnson–Lindenstrauss-type random projections. Our results reflect a tradeoff between accuracy and computational complexity when one uses �-means clustering after random projection of the data to a low-dimensional space. We argue that random projections work better than other simplistic dimension reduction schemes. Index Terms—Clustering, empirical risk minimization, Hilbert space, �-means, random projections, vector quantization.