Deterministic Feature Selection for K-Means Clustering
Deterministic Feature Selection for K-Means Clustering
复制标题
DOI：
10.1109/tit.2013.2255021
复制
发表时间：
2011-09
影响因子：
2.5
通讯作者：
Christos Boutsidis;M. Magdon-Ismail
中科院分区：
文献类型：
--
作者：
Christos Boutsidis;M. Magdon-Ismail
我们研究了k-means聚类的特征选择。虽然文献中包含许多具有良好经验性能的方法，但具有可证明理论行为的算法只是最近才开发出来。不幸的是，这些算法是随机的，失败的概率是恒定的。我们提出了第一个确定性的特征选择算法的k-means聚类相对误差保证。在我们的算法的核心在于一个确定性的方法分解的身份和结构的结果，量化的一些权衡降维。
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 present the first deterministic feature selection algorithm for k-means clustering with relative error guarantees. At the heart of our algorithm lies a deterministic method for decompositions of the identity and a structural result which quantifies some of the tradeoffs in dimensionality reduction.