Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula>-Means Clustering

DOI10.1109/TIT.2014.2375327MaRDI QIDQ2978788zbMATH OpenOpenAlexFDO

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

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.2897

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Information theory (general) (94A15)

Abstract: 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.

Recommendations

• Dimensionality reduction for k-means clustering and low rank approximation
• A general framework for dimensionality reduction of K-means clustering
• High-dimensional clustering via random projections
• Reduced \(k\)-means clustering with MCA in a low-dimensional space
• A fast approximation scheme for low-dimensional k-means
• On variants of k-means clustering
• Efficient clustering on Riemannian manifolds: a kernelised random projection approach
• Cluster-based estimation for sufficient dimension reduction

Cited in

(36)

• Optimal column subset selection for image classification by genetic algorithms
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Fuzzy \(c\)-means and cluster ensemble with random projection for big data clustering
• Regularized k-means clustering of high-dimensional data and its asymptotic consistency
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Dimension reduction for objects composed of vector sets
• Quick-means: accelerating inference for K-means by learning fast transforms
• Subset selection for matrices with fixed blocks
• Parameterized \(k\)-clustering: tractability island
• Reduced \(k\)-means clustering with MCA in a low-dimensional space
• Global and local structure preserving sparse subspace learning: an iterative approach to unsupervised feature selection
• Structural conditions for projection-cost preservation via randomized matrix multiplication
• Core-sets: updated survey
• Approximating spectral clustering via sampling: a review
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• A novel feature selection approach based on clustering algorithm
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• A numerical study of efficient sampling strategies for randomized singular value decomposition
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Real-Time Radiation Treatment Planning with Optimality Guarantees via Cluster and Bound Methods
• scientific article; zbMATH DE number 7164768 (Why is no real title available?)
• Minimum cost‐compression risk in principal component analysis
• k-means-g*: accelerating \(k\)-means clustering algorithm utilizing primitive geometric concepts
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers
• Algorithm for orthogonal matrix nearness and its application to feature representation
• Turning big data into tiny data: coresets for unsupervised learning problems
• An empirical evaluation of k-means coresets
• Efficient algorithms for Tucker decomposition via approximate matrix multiplication
• Parameterized complexity of feature selection for categorical data clustering
• Bayesian D-optimal experimental designs via column subset selection
• Subset selection for matrices in spectral norm
• Sublinear data structures for nearest neighbor in ultra high dimensions
• Guessing efficiently for constrained subspace approximation
• Deterministic complexity analysis of Hermitian eigenproblems

This page was built for publication: Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978788)