Title:
randomized-dimensionality-reduction-for-k-means.r
Download
Description: Randomized Dimensionality Reduction for k-means
Clustering
This paper makes further progress towards a better understanding of dimensionality reduction for kmeans
clustering. Namely, we present the first provably accurate feature selection method for k-means
clustering and, in addition, we present two feature extractionmethods. The first feature extractionmethod
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.
To Search:
File list (Check if you may need any files):
randomized dimensionality reduction for k-means.pdf
