Poster
Random Projections for -means Clustering
Christos Boutsidis · Anastasios Zouzias · Petros Drineas
[
Abstract
]
2010 Poster
Abstract:
This paper discusses the topic of dimensionality reduction for
-means clustering. We prove that any set of points in
dimensions (rows in a matrix ) can be projected into dimensions, for any , in
time, such that with
constant probability the optimal -partition of the point
set is preserved within a factor of . The projection is
done by post-multiplying with a random
matrix having entries or with equal probability.
A numerical implementation of our technique and experiments on a large face images dataset verify the speed and the accuracy of our theoretical results.
Live content is unavailable. Log in and register to view live content