Dimensionality Reduction for $k$-means Clustering

We present a study on how to effectively reduce the dimensions of the $k$-means clustering problem, so that provably accurate approximations are obtained. Four algorithms are presented, two \textit{feature selection} and two \textit{feature extraction} based algorithms, all of which are randomized.

cs.LG stat.ML Face and Expression Recognition Stochastic Gradient Optimization Techniques Advanced Clustering Algorithms Research Computer Science Mathematics

View graph Source

Paper

Similar papers

Randomized Dimensionality Reduction for k-means ClusteringChristos Boutsidis, Anastasios Zouzias, Michael W. Mahoney et al.2011 · IEEE Transactions on Information Theory · 236 citations In Library

Random Projections for $k$-means ClusteringChristos Boutsidis, Anastasios Zouzias, P. Drineas2010 · Neural Information Processing Systems · 178 citations In Library

Dimensionality Reduction for k-Means Clustering and Low Rank ApproximationMichael B. Cohen, Sam Elder, Cameron Musco et al.2014 · Symposium on the Theory of Computing · 380 citations In Library

Deterministic Feature Selection for $k$-means ClusteringChristos Boutsidis, M. Magdon-Ismail2011 · IEEE Transactions on Information Theory · 67 citations In Library

Assessing the impact of dimensionality reduction on clustering performance -- a systematic studyOusmane Assani-Amate, Mohammadreza Bakhtyari, ·. Roy et al.2026 · arXiv.org · 0 citations In Library

Modified K-Means Clustering Algorithms for Feature SelectionAyeasha Akhter, Ken Ferens2023 In Library

Dimension Reduction for Clustering: The Curious Case of Discrete CentersShaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir et al.2025 · ArXiv.org In Library

Learning-Augmented K-Means Clustering Using Dimensional ReductionIssam K.O Jabari, Shofiyah Shofiyah, Pradiptya Kahvi Sugiharto et al.2023 · International Conference on Sustainable Information Engineering and Technology · 6 citations In Library

Moderate Dimension Reduction for $k$-Center ClusteringShaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir2023 · arXiv (Cornell University) In Library

Dimension Reduction for Projective ClusteringRafael Zuolo Coppini Lima2022 In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal