Unsupervised Feature Selection for the k-means Clustering Problem

Abstract

We present a novel feature selection algorithm for the k-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter (0,1), selects and appropriately rescales in an unsupervised manner (k (k / ) / ^2) features from a dataset of arbitrary dimensions. We prove that, if we run any -approximate k-means algorithm ( 1) on the features selected using our method, we can find a (1+(1+))-approximate partition with high probability.

Tasks

Reproductions