Random Projections for k-means Clustering

2010/11/21 by Boutsidis, Christos, Zouzias, Anastasios, Drineas, Petros · 2 citations
#Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1011.4632

Abstract

This paper discusses the topic of dimensionality reduction for k-means clustering. We prove that any set of n points in d dimensions (rows in a matrix A ∈ \RR^{n × d}) can be projected into t = Ω(k / \eps²) dimensions, for any \eps ∈ (0,1/3), in O(n d \lceil \eps^-2 k/ log(d) \rceil ) time, such that with constant probability the optimal k-partition of the point set is preserved within a factor of 2+\eps. The projection is done by post-multiplying A with a d × t random matrix R having entries +1/√(t) or -1/√(t) 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.

Cited by

• Dimension Reduction for Clustering: The Curious Case of Discrete Centers
• Simplicial clustering using the α--transformation

Related

• Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees
• Simple, Scalable and Effective Clustering via One-Dimensional Projections
• Dimensionality Reduction for k-means Clustering
• High-dimensional clustering via Random Projections
• The Bane of Low-Dimensionality Clustering