Source-linked AI summary
Random Projections for $k$-means Clustering
Christos Boutsidis, Anastasios Zouzias, Petros Drineas
TL;DR
The paper addresses dimensionality reduction for k-means clustering, where finding the optimal clustering is computationally difficult. It uses random projections and establishes approximation and runtime guarantees, supported by experiments on face images.
Problem
Finding Xopt is NP-hard even for k = 2, motivating approximation algorithms for k-means clustering.
Method
The method projects the data using a random sign matrix and computes the product AR with the mailman algorithm in O(nd⌈ε^-2k/log(d)⌉) time.
Results
With probability at least 0.97 − δγ, the algorithm provides the stated clustering-quality guarantee; with exact projected k-means, the distortion is at most 2 + ε.
Takeaways & Limitations
When k = O(log(d)), the embedding computation is almost linear, while face-image experiments examine projected dimension, accuracy, and clustering time.
Takeaways & Limitations
The guarantee assumes access to a γ-approximation k-means algorithm, specified with γ = 1 + ε′ and running time O(2^(k/ε′)O(1)dn).
Abstract
from arXiv · showhide
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 \in \RR^{n \times d}$) can be projected into $t = Ω(k / \eps^2)$ dimensions, for any $\eps \in (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 \times t$ random matrix $R$ having entries $+1/\sqrt{t}$ or $-1/\sqrt{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.
1 Introduction
The paper applies random projections to k-means dimensionality reduction, seeking fast embeddings that preserve clustering structure with limited distortion. It positions the approach against existing dimensionality-reduction methods and reports improvements in runtime, embedding dimension, or approximation accuracy.
- Motivation: The goal is to project n points from d dimensions into ˜d ≪ d dimensions before applying k-means, without significantly distorting the clustering structure.The paper frames random projection as a feature-extraction approach that constructs new features from the original dimensions.
- Background: Dimensionality reduction includes feature selection and feature extraction, with the latter constructing artificial features such as linear combinations of original features.
- Related methods: Table 1 organizes dimension-reduction methods for k-means and identifies random-projection methods as using random sign matrices with the mailman algorithm.
2 Preliminaries
The preliminaries define k-means through indicator matrices and approximation factors, explain why approximation is needed, and review dimensionality reduction through singular vectors and Johnson–Lindenstrauss embeddings.
- k-means formulation: The k-means problem seeks an n × k indicator matrix Xopt minimizing the k-means objective for n points represented by an n × d matrix A.Each row of an indicator matrix has one nonzero entry representing cluster membership.
- Approximation: Finding Xopt is NP-hard even for k = 2, motivating approximation algorithms for k-means clustering.
- Approximation: A γ-approximation algorithm returns a clustering whose objective is within factor γ of optimal with probability at least 1 − δγ.
- Approximation: The fixed approximation algorithm guarantees γ = 1 + ε′ for ε′ ∈ (0, 1] with running time O(2^(k/ε′)O(1)dn).
- Random projections: Johnson–Lindenstrauss embeddings use random projections into Ω(log(n)/ε^2) dimensions to approximately preserve pairwise distances, while random sign matrices provide the same type of guarantees.The paper adopts the rescaled random-sign approach for k-means.
3 A random-projection-type k-means algorithm
Algorithm 1 reduces the data dimension with a random sign projection, clusters the projected data using any γ-approximation method, and exploits the projection structure for faster multiplication.
- Algorithm: Algorithm 1 takes A, k, ε ∈ (0, 1/3), and a γ-approximation algorithm, then returns an indicator matrix defining a k-partition.
- Algorithm: The algorithm sets the projected dimension to t = Ω(k/ε^2), computes ˜A = AR, and runs the approximation algorithm on ˜A.
- Running time: Using a random sign matrix and the mailman algorithm computes AR in O(nd⌈ε^-2k/log(d)⌉) time.
- Running time: When k = O(log(d)), the projection computation has almost linear time complexity O(nd/ε^2).
- Clustering step: The theoretical approximation guarantee is independent of the particular γ-approximation algorithm, although the experiments use Lloyd’s heuristic.Lloyd’s algorithm is popular and empirically effective but does not admit a worst-case theoretical analysis here.
4 Main Theorem
The main theorem bounds the clustering distortion after random projection, with the proof controlling singular-value and residual terms through concentration and matrix inequalities. The analysis culminates in a constant-probability guarantee for Algorithm 1.
- Main guarantee: With probability at least 0.97 − δγ, Algorithm 1 produces a clustering whose quality is bounded by the theorem’s γ-dependent approximation guarantee.The theorem applies for ε ∈ (0, 1/3), k < min{n, d}, and any γ-approximation k-means algorithm.
- Main guarantee: When γ = 1, the algorithm guarantees distortion at most 2 + ε for the optimal projected k-means solution.
- Proof ingredients: The proof establishes singular-value preservation for the projected top-k subspace with probability at least 0.99.
- Proof ingredients: A residual-error bound controls the projection of the component outside the top-k singular subspace, yielding an error term bounded by 4ε∥A − Ak∥F with probability at least 0.97.
- Proof strategy: The argument combines projector properties, triangle inequalities, submultiplicativity, union bounds, and rescaling of ε to complete the theorem.
5 Experiments
Experiments on the ORL face-image collection evaluate Algorithm 1 across projection dimensions and against other dimensionality-reduction methods. Increasing the projection dimension improves the normalized objective and mis-classification behavior with diminishing returns, while increasing runtime nearly linearly.
- 5.1 An application of Algorithm 1 on a face images collection: 400 ORL face images from 40 people form a 400 × 4096 image-by-pixel matrix, clustered with k = 40 using deterministic initialization.Each person contributes 10 images, and cluster centers are initialized from the first image of each group.
- 5.1 An application of Algorithm 1 on a face images collection: t = 5, 10, ..., 300 projections were tested with k = 40 to study how projected dimension affects clustering.The experiments varied t while holding the other settings fixed.
- 5.1 An application of Algorithm 1 on a face images collection: The normalized objective function ˜F decreases piece-wise with t, with large gains initially and negligible changes after around 90 dimensions.The mis-classification rate P is piece-wise non-decreasing and likewise becomes largely unchanged after around t = 90.
- 5.1 An application of Algorithm 1 on a face images collection: The mis-classification rate P and objective function F can behave differently, so clustering accuracy is not directly determined by the objective value.The paper specifically notes differing behavior between t = 20 and t = 25 dimensions.
- 5.1 An application of Algorithm 1 on a face images collection: Runtime increases almost linearly with t, indicating that small projected dimensions can yield substantial computational savings when n is large.The observed nonlinearities arise from differing numbers of Lloyd iterations required for convergence.
- 5.1 An application of Algorithm 1 on a face images collection: Algorithm 1 was compared with SVD, LLE, Laplacian-score feature selection, and Lloyd’s heuristic on the original high-dimensional data.The evaluation also reports comparisons at four representative projection dimensions.
- 5.2 A note on the mailman algorithm for matrix-matrix and matrix-vector multiplication: The mailman implementation was faster than naive matrix multiplication for vector inputs, while the best matrix-matrix implementation was inferior to the alternatives tested.The comparison included Matlab multiplication, on-the-fly computation, and the mailman algorithm.