Randomized Dimensionality Reduction for k-means Clustering

2011-10-13 · Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney, Petros Drineas

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.

📄 PDF Abstract BibTeX arXiv:1110.2897

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringDimensionality Reductionfeature selection

Dimensionality Reduction for $k$-means Clustering

2020-07-26 · Neophytos Charalambides

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…

Clustering Dimensionality Reduction feature selection

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

2021-07-05 · Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir

Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hie…

Clustering Dimensionality Reduction

Self-Supervised Graph Embedding Clustering

2024-09-24 · Fangfang Li, Quanxue Gao, Cheng Deng, Wei Xia

The K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. However, it combines the K-means clustering and dimensionality reducti…

Clustering Dimensionality Reduction Graph Embedding

Assessing the impact of dimensionality reduction on clustering performance -- a systematic study

2026-04-23 · Ousmane Assani-Amate, Mohammadreza Bakhtyari, Émilie Roy, Vladimir Makarenkov arxiv

Dimensionality reduction is a critical preprocessing step for clustering high-dimensional data, yet comprehensive evaluation of its impact across diverse methods and data types remains limited. In this study, we systemat…

Dimensionality Reduction

Sparse Embedded k-Means Clustering

2017-12-01 · NeurIPS 2017 12 · Weiwei Liu, Xiaobo Shen, Ivor Tsang

The $k$-means clustering algorithm is a ubiquitous tool in data mining and machine learning that shows promising performance. However, its high computational cost has hindered its applications in broad domains. Researche…