Deterministic Feature Selection for K-Means Clustering

DOI10.1109/TIT.2013.2255021MaRDI QIDQ5346350zbMATH OpenFDO

Authors Christos Boutsidis, Malik Magdon-Ismail

Publication date 8 June 2017

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

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

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Information theory (general) (94A15)

Abstract: We study feature selection for $k$-means clustering. Although the literature contains many methods with good empirical performance, algorithms with provable theoretical behavior have only recently been developed. Unfortunately, these algorithms are randomized and fail with, say, a constant probability. We address this issue by presenting a deterministic feature selection algorithm for k-means with theoretical guarantees. At the heart of our algorithm lies a deterministic method for decompositions of the identity.

Cited in

(11)

• Optimal column subset selection for image classification by genetic algorithms
• Subset selection for matrices with fixed blocks
• Feature selection for linear SVM with provable guarantees
• Feature selection for \(k\)-means clustering stability: theoretical analysis and an algorithm
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• A Local Search Framework for Experimental Design
• Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
• Feature Selection for Ridge Regression with Provable Guarantees
• Unsupervised clustering and feature weighting based on generalized Dirichlet mixture modeling
• Subset selection for matrices in spectral norm

This page was built for publication: Deterministic Feature Selection for K-Means Clustering

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