PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Dimensionality Reduction for k-means Clustering

Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney, Petros Drineas

arXiv:1110.2897v3cs.DScs.LG

TL;DR

The paper addresses the lack of provably accurate feature selection for k-means amid high-dimensional data and many heuristic dimensionality-reduction methods. It presents one feature selection method and two feature extraction methods, achieving randomized constant-factor approximation guarantees while improving feature counts or time complexity.

  • Problem

    High-dimensional data make k-means computationally inefficient, while irrelevant features can obscure underlying structure; provably accurate feature selection methods were not known.

  • Method

    The paper develops one randomized feature selection algorithm and two randomized feature extraction algorithms based on random projections and approximate SVD.

  • Results

    The methods provide constant-factor approximation guarantees, including (3 + ε) error with O(k log(k)/ε2) selected features and 2 + ε error with k extracted features.

  • Takeaways & Limitations

    Dimensionality reduction for k-means can be analyzed through low-rank approximations, supporting provably efficient feature selection and extraction methods.

  • Takeaways & Limitations

    The guarantees evaluate the k-means objective value rather than directly comparing the structure of the resulting clustering with the optimal clustering.

Abstract

from arXiv · show

We study the topic of dimensionality reduction for $k$-means clustering. Dimensionality reduction encompasses the union of two approaches: \emph{feature selection} and \emph{feature extraction}. A feature selection based algorithm for $k$-means clustering selects a small subset of the input features and then applies $k$-means clustering on the selected features. A feature extraction based algorithm for $k$-means clustering constructs a small set of new artificial features and then applies $k$-means clustering on the constructed features. Despite the significance of $k$-means clustering as well as the wealth of heuristic methods addressing it, provably accurate feature selection methods for $k$-means clustering are not known. On the other hand, two provably accurate feature extraction methods for $k$-means clustering are known in the literature; one is based on random projections and the other is based on the singular value decomposition (SVD). This paper makes further progress towards a better understanding of dimensionality reduction for $k$-means clustering. Namely, we present the first provably accurate feature selection method for $k$-means clustering and, in addition, we present two feature extraction methods. The first feature extraction method is based on random projections and it improves upon the existing results in terms of time complexity and number of features needed to be extracted. The second feature extraction method is based on fast approximate SVD factorizations and it also improves upon the existing results in terms of time complexity. The proposed algorithms are randomized and provide constant-factor approximation guarantees with respect to the optimal $k$-means objective value.

1 Introduction

High-dimensional data make k-means clustering costly and can obscure relevant structure, motivating feature selection and extraction. This paper develops three randomized, provably accurate dimensionality-reduction approaches with approximation guarantees.

  • Motivation: High-dimensional datasets challenge efficient k-means clustering through computational inefficiency and irrelevant features.These obstacles can prevent identification of relevant underlying structure.
  • Dimensionality reduction: Feature selection retains a small subset of original features, whereas feature extraction constructs a small set of artificial features.Both approaches seek a lower-dimensional representation that approximates the original clustering structure.
  • Prior work: Provably accurate feature selection methods were previously unknown, while prior feature extraction methods used random projections or SVD.Random projections require O(log(m)/ε^2) features for a (1 + ε)-approximate clustering, while the cited SVD method uses k features for a 2-approximation.
  • Contributions: The paper presents the first provably accurate feature-selection algorithm for k-means.It uses randomized feature sampling and achieves a (3 + ε)-error with r = O(k log(k)/ε^2) features in the stated running time.
  • Contributions: A random-projection feature-extraction algorithm achieves a (2 + ε)-error using r = O(k/ε^2) artificial features.This improves the cited prior random-projection result in the number of extracted features and has the stated running time.
  • Contributions: An approximate-SVD feature-extraction algorithm uses r = k artificial features and achieves a 2 + ε multiplicative clustering-error bound.Its running time is O(mnk/ε), improving the cited exact-SVD approach through fast approximate SVD.

2 Linear Algebraic Formulation and our Approach

The paper recasts k-means as a matrix approximation problem, representing clusterings with indicator matrices and comparing their Frobenius-norm objectives. It then uses low-rank approximations to construct reduced features whose clustering remains close to the original.

  • 2.1 Linear Algebraic Formulation of k-means: The data matrix A stores points as rows and features as columns, while a cluster indicator matrix X encodes each point’s cluster membership.Each column of X corresponds to a cluster, and its nonzero entries are normalized by cluster size.
  • 2.1 Linear Algebraic Formulation of k-means: The k-means objective minimizes the Frobenius norm ∥A−XX^TA∥_F over valid indicator matrices, with quality measured relative to an optimal clustering.The paper evaluates a clustering through F(A, X̂)/F(A, Xopt).
  • 2.2 Our Approach: Feature selection chooses columns of A, whereas feature extraction constructs C=AD, whose columns are linear combinations of the original features.This linear-algebraic view unifies actual-feature selection and artificial-feature construction.
  • 2.2 Our Approach: Using C=AV_k, the SVD-based construction yields F(A, X̂opt) ≤ 2F(A, Xopt) for the optimal clustering in reduced space.The bound follows because A_k=C·H is the best rank-k approximation to A.
  • 2.2 Our Approach: The approach seeks a low-dimensional C and matrix H such that C·H approximates A in Frobenius norm, paralleling the best rank-k SVD approximation.The Matrix Pythagorean theorem supports the analysis of these approximation errors.

3 Preliminaries

The preliminaries establish the matrix-norm, projection, SVD, sampling, and randomization tools used to analyze the proposed reductions. Fast approximate SVD and randomized sampling provide computationally efficient substitutes for exact low-rank structure and full feature sets.

  • Matrix norms: The paper defines Frobenius and spectral norms, along with spectral submultiplicativity and the triangle inequality for matrix products and sums.These inequalities are used repeatedly in the approximation analyses.
  • Projection and norm tools: The Matrix Pythagorean theorem decomposes squared Frobenius error when two matrix components have orthogonal row spaces.This theorem is the starting point for proofs of the three main results.
  • Singular Value Decomposition: The SVD decomposes A into singular vectors and values, with A_k providing the best rank-k approximation in Frobenius norm.The residual is denoted A_{ρ−k}=A−A_k.
  • Approximate Singular Value Decomposition: FastFrobeniusSVD computes an orthonormal Z whose rank-k approximation AZZ^T is nearly as good in expectation as A_k, in O(mnk/ε) time.Z therefore serves as an efficient approximation to the top right singular vectors.
  • Projection and probability tools: Projection matrices cannot increase the Frobenius norm, and standard identities for pseudoinverses and orthogonal projections support the error bounds.The paper also states Markov’s inequality and the union bound for probabilistic guarantees.
  • 3.1 Randomized Sampling: Randomized sampling selects and rescales columns through a sampling matrix Ω and diagonal matrix S, with probabilities derived from rows of an input matrix.The procedure samples with replacement and requires O(nk) time to compute probabilities and execute sampling.
  • 3.1 Randomized Sampling: Sampling sufficiently many rows of an orthonormal matrix preserves its singular values with high probability, while column subsampling preserves relevant low-rank approximation properties.These facts underpin randomized feature selection.

4 Feature Selection with Randomized Sampling

The paper introduces its first provably accurate feature-selection algorithm for k-means by approximating the top right singular vectors and sampling actual columns. It achieves a constant-factor clustering guarantee with roughly O(k log k) selected features.

  • Algorithm: Algorithm 1 constructs Z from approximate top-k right singular vectors of A and uses randomized column sampling to select features.The approximate SVD makes the procedure faster than using the exact SVD.
  • Theorem 11: O(mnk/ε + k log(k)/ε^2 log(k log(k)/ε)) time constructs r=O(k log(k)/ε^2) selected features.The guarantee holds for inputs A, k, and ε∈(0,1/3).
  • Interpretation: O(k log k) actual features suffice for the reduced-space clustering to remain close to the clustering obtained in the original high-dimensional data.The result applies to any set of points and specified number of clusters k.
  • Approximation guarantee: The approximation factor is (1+(2+ε)γ), where γ reflects the reduced-space k-means approximation and 2+ε reflects the dimensionality-reduction analysis.The paper explicitly separates these two sources of the factor.
  • Proof: The proof bounds the reduced clustering error by combining projection identities, low-rank approximation properties, and randomized sampling estimates.The final algebraic bound is rescaled to obtain Theorem 11.
  • Theorem 11: With probability at least 0.2−δγ, running a γ-approximation k-means algorithm on the selected features achieves the theorem’s clustering-error bound.The failure probability combines the randomized sampling, approximate-SVD, and k-means guarantees.

5 Feature Extraction with Random Projections

The second reduction constructs artificial features by multiplying A by a random projection matrix. It needs only O(k/ε^2) dimensions, runs quickly with the Mailman algorithm, and provides a constant-factor clustering guarantee.

  • Method: Random projection maps A into C=AR using an n×r random matrix, with r=O(k/ε^2) artificial features.The projection preserves the optimal clustering objective within a factor of 2+ε with constant probability.
  • Runtime: O(mn⌈ε^−2k/log(n)⌉) time constructs the projected features and runs the stated randomized projection procedure.Generating the random matrix costs O(mk/ε^2), while Mailman multiplication reduces the product cost.
  • Theorem 12: With probability at least 0.96−δγ, a γ-approximation k-means algorithm on C satisfies the theorem’s clustering-error guarantee.The 0.04 failure component comes from the projection analysis and is combined with δγ.
  • Interpretation: O(k) new features suffice for random-projection reduction, and the reduced clustering remains close to the clustering from the original high-dimensional data.This improves the number of dimensions required by the standard random-projection result.
  • Approximation guarantee: The approximation factor is (1+(1+ε)γ), with γ arising from approximate k-means and 1+ε from running k-means after projection.For γ=1, the distortion is at most 2+ε.
  • Discussion: The method improves on Johnson–Lindenstrauss dimensionality reduction by using fewer dimensions, but its bound is 2+ε rather than 1+ε.The authors conjecture that the weaker relative-error factor may be an artifact of the analysis.

6 Feature Extraction with Approximate SVD

The paper presents a randomized approximate-SVD feature-extraction method that constructs exactly k artificial features and supports approximate k-means clustering with a stated approximation guarantee.

  • Approximate-SVD feature extraction: The method uses a fast randomized approximate SVD instead of the expensive exact deterministic SVD.The proof techniques match the prior SVD-based approach while improving computational speed, with comparable approximation error.
  • Algorithm: k artificial features are constructed from an input dataset A ∈ R^m×n for k-means clustering.Algorithm 3 outputs C ∈ R^m×k.
  • Guarantee: The resulting low-dimensional clustering is close to the clustering obtained by applying k-means in the original high-dimensional space.This holds for any γ-approximation k-means algorithm run on the constructed features, under the theorem’s probability guarantee.
  • Guarantee: The approximation factor is (1 + (1 + ε)γ), combining the low-dimensional reduction error with the γ-approximation factor of the k-means algorithm.The theorem gives probability at least 0.99 − δγ, with the failure probability derived using a union bound.
  • Proof strategy: The proof decomposes A into AZZ^T plus an error term and bounds the resulting clustering objective using Frobenius-norm and spectral arguments.The analysis assumes γ ≥ 1 when combining the terms in the final bound.

7 Experiments

The experiments evaluate proposed feature selection and extraction methods against competing reductions and full-dimensional k-means. Small projected dimensions often preserve clustering quality, while dataset structure affects comparative accuracy.

  • Evaluation methodology: The evaluation compares proposed methods with Sampl/SVD, Sampl/ApproxSVD, random projections, exact and approximate SVD, Laplacian Scores, and full-dimensional k-means.The experiments vary the number r of selected or extracted features.
  • Datasets: The experiments use one synthetic Gaussian-mixture dataset and five real-world datasets: USPS, COIL20, ORL, PIE, and LIGHT.The synthetic dataset contains 1000 points in 2000 dimensions and five generated clusters.
  • Evaluation methodology: The study measures normalized k-means objective value, label-based mis-classification accuracy, and running time.Reported running time includes both dimensionality reduction and low-dimensional k-means, averaged over five executions.
  • Results: For the synthetic data, all dimensionality-reduction methods are more efficient than naive k-means and remain accurate with approximately r = 20 dimensions.The clusters are well separated, and the authors suggest dimensionality reduction is effective in this setting.
  • Results: For real-world datasets, normalized objective values decrease as projected dimensions increase and converge toward naive k-means; proposed methods outperform Laplacian Scores except on PIE and COIL20 accuracy.On PIE and COIL20, Laplacian Scores has superior accuracy, while poor naive-k-means accuracy suggests those data may be less well separated.
  • Results: Running time does not always increase with projected dimension because low-dimensional k-means may require different iteration counts to converge.The authors did not investigate this behavior further because it was outside the experimental focus.
  • Results: The authors describe the empirical evaluation as preliminary but report encouraging performance with small values such as r = 20 or r = 30.They also state that the large constants in the theoretical bounds may be artifacts of the analysis.

8 Conclusions

The paper presents three theoretically grounded dimensionality-reduction approaches for k-means and reports encouraging practical results. These methods connect dimensionality reduction with low-rank approximation and produce faster clustering that is nearly as accurate as clustering in the original space.

  • Three approaches are presented: one feature-selection method and two feature-extraction methods for k-means clustering.The feature-extraction methods use random projections and fast approximate SVD factorizations.
  • The theoretical analysis exploits connections between k-means dimensionality reduction and low-rank approximations of the data matrix.The paper uses modern fast algorithms for low-rank approximation to design fast dimensionality-reduction algorithms.
  • Experimental results indicate that the proposed dimensionality-reduction techniques yield faster algorithms that are almost as accurate as running k-means on high-dimensional data.
  • The work describes the first provably efficient feature-selection algorithm for k-means and two novel provably efficient feature-extraction algorithms.The paper identifies provably efficient (1+ε)-relative-error dimensionality reduction as an avenue for future research.

Appendix

This appendix develops a technical lemma for analyzing a matrix projection whose singular values remain close to one. The proof uses SVD-based manipulations to control the resulting pseudoinverse and spectral-norm error.

  • The lemma assumes an orthonormal matrix Q and a projection Θ whose first k singular values lie between 1−ε and 1+ε.The conditions require n > k, r > k, and 0 < ε < 1/3.
  • The proof takes SVDs of (Q^TΘ)† and (Q^TΘ)^T to compare the pseudoinverse with the transpose.The factor UX can be dropped without changing the spectral norm, simplifying the comparison.
  • A diagonal matrix formed from the singular values is used to express the deviation from identity coordinatewise.Its diagonal entries are determined by the squared singular values of the projected matrix.
  • The proof’s final bounds follow from positivity of the singular values, the assumed singular-value bounds, and ε < 1/3.

Proof of Lemma 8

The proof bounds the error of a randomized matrix-product approximation by combining sampling estimates, rank preservation, and pseudoinverse control. Conditioning on successful sampling events allows the approximation error to be reduced to a residual term.

  • Randomized sampling matrices Ω and S subsample and rescale columns of E and rows of Z in the matrix-product analysis.A cited matrix multiplication bound controls the sampled product for arbitrary sampling probabilities.
  • The construction EZ = 0 enables cancellation after the sampled matrix Z^TΩS has full row rank.Under this rank condition, (Z^TΩS)(Z^TΩS)† = I_k and the corresponding residual term vanishes.
  • The proof conditions on a high-probability sampling inequality before decomposing the approximation error into separately bounded terms.
  • The Frobenius error is bounded using spectral submultiplicativity, the triangle inequality, Markov’s inequality, and pseudoinverse approximation.The key decomposition compares the pseudoinverse with the transpose and bounds the sampled residual factors.

Proof of Lemma 9

The proof establishes randomized projection bounds through Johnson–Lindenstrauss and matrix-multiplication arguments. With an appropriate projection dimension, several good events hold simultaneously and yield a residual approximation error bounded by 3ε times the residual norm.

  • A matrix multiplication bound applies to random matrices with independent rows containing four-wise independent, zero-mean entries.The paper’s random matrix uses full independence, which satisfies the stated condition.
  • Choosing r ≥ 576(k ln(18) + ln(100))/ε^2 makes the relevant failure probability at most 0.01, and c0 = 3330 suffices for the lemma.
  • The three required events occur with probability at least 0.97 after a union bound, enabling the subsequent error analysis.The events control singular values, a residual projection term, and an orthogonality-related term.
  • 3ε · ∥Aρ−k∥F bounds the final residual error after combining the event-specific inequalities and taking a square root.The derivation assumes ε ∈ (0, 1/3), along with the stated conditions on c0 and k.

Proof of Eqn. (2)

The proof applies Markov’s inequality to the nonnegative random variable Y = ∥E∥2^F, using the rank structure of E = A−AZZᵀ.

  • Markov’s inequality is applied to the random variable Y = ∥E∥2^F.
  • The application of Markov’s inequality yields a bound on ∥E∥2^F.
  • Y is nonnegative because E = A−AZZᵀ and rank(AZZᵀ) = k.
Loading 1110.2897v3…