On the Performance of Clustering in Hilbert Spaces

Based on randomly drawn vectors in a separable Hilbert space, one may construct a k-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 X from the set of cluster centers. Ou...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2008-02, Vol.54 (2), p.781-790
Main Authors: Biau, G., Devroye, L., Lugosi, G.
Format: Article
Language:English
Subjects:
Applied sciences
Biology
Cluster analysis
Clustering
Coding, codes
Computation
Computational complexity
Computer science
Data analysis
Data compression
empirical risk minimization
Exact sciences and technology
Hilbert space
Information theory
Information, signal and communications theory
k -means
Kernel
Mathematical analysis
Mathematics
Performance evaluation
Probability
Projection
random projections
Reduction
Risk
Risk management
Sampling, quantization
Signal and communications theory
Signal representation. Spectral analysis
Signal, noise
Telecommunications and information theory
Unsupervised learning
Vector quantization
Vector space
Vectors (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Based on randomly drawn vectors in a separable Hilbert space, one may construct a k-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 X from the set of cluster centers. Our main result states that, for an almost surely bounded , the expected excess clustering risk is O(¿1/n) . 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 k-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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2007.913516