Scalable Feature Selection via Distributed Diversity Maximization
Scalable Feature Selection via Distributed Diversity Maximization
复制标题
DOI：
10.1609/aaai.v31i1.10926
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Sepehr Abbasi Zadeh;Mehrdad Ghadiri;V. Mirrokni;Morteza Zadimoghaddam
中科院分区：
文献类型：
--
作者：
Sepehr Abbasi Zadeh;Mehrdad Ghadiri;V. Mirrokni;Morteza Zadimoghaddam
特征选择是机器学习和数据挖掘中的一个基本问题。大多数特征选择算法被设计为在一台机器上运行(集中设置)，它们不太适用于非常大的数据集。虽然已经有一些分布式方法来解决这一问题，但它们大多是水平分布的数据，不适合于特征数较多、实例数较少的数据集。因此，在本文中，我们引入了一种新的垂直分布的特征选择方法，以加快这一过程，并能够以可伸缩的方式处理非常大的数据集。一般而言，特征选择方法的目标是选择相关和非冗余的特征(最小冗余和最大相关性)。在垂直分布的设置中考虑冗余比在集中式设置中要难得多，因为不存在对整个数据的全局访问。据我们所知，这是用垂直分布的滤波方法来解决特征选择问题的第一次尝试，该方法处理冗余性的结果与集中式方法一致。在本文中，我们通过在特征上引入基于互信息的度量距离，将特征选择问题形式化为一个多样性最大化问题。我们通过一个广泛的实证研究展示了我们方法的有效性。特别是，我们证明了我们的分布式方法在各种数据集上的性能优于最先进的集中式特征选择算法。从理论上证明了本文方法中使用的贪婪算法以较高的概率达到了分布式环境下多样性最大化问题的1/4的逼近因子。此外，我们使用分布中的多重性将其改进为8/25预期近似值。
Feature selection is a fundamental problem in machine learning and data mining. The majority of feature selection algorithms are designed for running on a single machine (centralized setting) and they are less applicable to very large datasets. Although there are some distributed methods to tackle this problem, most of them are distributing the data horizontally which are not suitable for datasets with a large number of features and few number of instances. Thus, in this paper, we introduce a novel vertically distributable feature selection method in order to speed up this process and be able to handle very large datasets in a scalable manner. In general, feature selection methods aim at selecting relevant and non-redundant features (Minimum Redundancy and Maximum Relevance). It is much harder to consider redundancy in a vertically distributed setting than a centralized setting since there is no global access to the whole data. To the best of our knowledge, this is the first attempt toward solving the feature selection problem with a vertically distributed filter method which handles the redundancy with consistently comparable results with centralized methods. In this paper, we formalize the feature selection problem as a diversity maximization problem by introducing a mutual-information-based metric distance on the features. We show the effectiveness of our method by performing an extensive empirical study. In particular, we show that our distributed method outperforms state-of-the-art centralized feature selection algorithms on a variety of datasets. From a theoretical point of view, we have proved that the used greedy algorithm in our method achieves an approximation factor of 1/4 for the diversity maximization problem in a distributed setting with high probability. Furthermore, we improve this to 8/25 expected approximation using multiplicity in our distribution.