Variable and feature selection in large datasets.

摘要

Variable and feature selection are an important component in the manipulation and the analysis of massive data sets. The idea is to preprocess the data, which may contain a large number of features, and filter out irrelevant or redundant features. The reduced data can then be further analyzed with standard data mining or machine learning techniques. The work presented here is motivated by machine learning applications, where feature selection can be applied to unlabeled data, or alternatively to the labeled data that is available for training. In the machine learning literature the selection of features from the unlabeled data is called unsupervised feature selection, while the selection of features from the labeled data is called supervised feature selection. We describe new algorithms for both the supervised and the unsupervised case that can efficiently perform feature selection from large amounts of data. The first algorithm addresses the unsupervised case. It improves on the current state-of-the-art unsupervised feature selection algorithms in terms of run time and the number of passes over the data. The algorithm is a modification of the classical pivoted QR algorithm of Businger and Golub. It selects the exact same features as the classical pivoted QR algorithm, and has the same favorable numerical stability. The classical algorithm stood unchallenged (in terms of run time and the number of passes) for almost 40 years. We describe experiments on real-world datasets which sometimes show an improvement by several orders of magnitude over the commonly used classical algorithm.;Algorithms for unsupervised feature selection cannot be used for supervised feature selection. Our contribution to supervised feature selection is for a generalization of the standard supervised feature selection case, where one attempts to approximate an entire matrix in terms of another matrix. Specifically, we consider simultaneously approximating all the columns of a data matrix in terms of few selected columns of another matrix that is sometimes called "the dictionary''. We describe fast algorithms for this task. Our algorithms improve on the speed and the memory requirements of the current state-of-the-art, while producing the exact same output. It enables applying feature selection on large and sparse datasets that could not be handled by previously known techniques. For example, we describe results on a very large and sparse commonly available dataset, which takes our algorithm less than 4 minutes and 150 megabytes of memory. Using a naive approach for the same problem may take hundreds of thousands of years. Using the current state-of-the-art would take about 7 hours, and would require 240 gigabytes of memory.