Feature selection

Feature selection, also known as variable selection, feature reduction, attribute selection or variable subset selection, is the technique, commonly used in machine learning, of selecting a subset of relevant features for building robust learning models. When applied in biology domain, the technique is also called discriminative gene selection, which detects influential genes based on DNA microarray experiments. By removing most irrelevant and redundant features from the data, feature selection helps improve the performance of learning models by:

• Alleviating the effect of the curse of dimensionality.
• Enhancing generalization capability.
• Speeding up learning process.
• Improving model interpretability.

Feature selection also helps people to acquire better understanding about their data by telling them which are the important features and how they are related with each other.

Introduction

Simple feature selection algorithms are ad hoc, but there are also more methodical approaches. From a theoretical perspective, it can be shown that optimal feature selection for supervised learning problems requires an exhaustive search of all possible subsets of features of the chosen cardinality. If large numbers of features are available, this is impractical. For practical supervised learning algorithms, the search is for a satisfactory set of features instead of an optimal set.

Feature selection algorithms typically fall into two categories; Feature Ranking and Subset Selection. Feature Ranking ranks the features by a metric and eliminates all features that do not achieve an adequate score. Subset Selection searches the set of possible features for the optimal subset.

In statistics, the most popular form of feature selection is stepwise regression. It is a greedy algorithm that adds the best feature (or deletes the worst feature) at each round. The main control issue is deciding when to stop the algorithm. In machine learning, this is typically done by cross validation. In statistics, some criteria are optimized. This leads to the inherent problem of nesting. More robust methods have been explored, such as Branch and Bound and Piecewise Linear Networks.

Subset Selection

Subset selection evaluates a subset of features as a group for suitability. Subset selection algorithms can be broken into Wrappers, Filters and Embedded. Wrappers use a search algorithm to search through the space of possible features and evaluate each subset by running a model on the subset. Wrappers can be computationally expensive and have a risk of over fitting to the model. Filters are similar to Wrappers in the search approach, but instead of evaluating against a model, a simpler filter is evaluated. Embedded techniques are embedded in and specific to a model.

Many popular search approaches use greedy hill climbing, which iteratively evaluates a candidate subset of features, then modifies the subset and evaluates if the new subset is an improvement over the old. Evaluation of the subsets requires a scoring metric that grades a subset of features. Exhaustive search is generally impractical, so at some implementor (or operator) defined stopping point, the subset of features with the highest score discovered up to that point is selected as the satisfactory feature subset. The stopping criterion varies by algorithm; possible criteria include: a subset score exceeds a threshold, a program's maximum allowed run time has been surpassed, etc.

Search approaches include:

• Exhaustive
• Best first
• Simulated annealing
• Genetic algorithm
• Greedy forward selection
• Greedy backward elimination

Two popular filter metrics for classification problems are correlation and mutual information, although neither are true metrics or 'distance measures' in the mathematical sense, since they fail to obey the triangle inequality and thus do not compute any actual 'distance' -- they should rather be regarded as 'scores'. These scores are computed between a candidate feature (or set of features) and the desired output category.

Other available filter metrics include:

• Class separability
  • Error probability
  • Inter-class distance
  • Probabilistic distance
  • Entropy
• Consistency-based feature selection
• Correlation-based feature selection

Optimality criteria

There are a variety of optimality criteria that can be used for controlling feature selection. The oldest are Mallows' Cp statistic and Akaike information criterion (AIC). These add variables if the t statistic is bigger than ${\sqrt {2}}$.

Other criteria are Bayesian information criterion (BIC) which uses ${\sqrt {\log {n}}}$, minimum description length (MDL) which asymptotically uses ${\sqrt {\log {n}}}$ but some argue this asymptote is not computed correctly, Bonnferroni / RIC which use ${\sqrt {2\log {p}}}$, and a variety of new criteria that are motivated by false discovery rate (FDR) which use something close to ${\sqrt {2\log {\frac {p}{q}}}}$.

minimum-Redundancy-Maximum-Relevance

Selecting features that correlate strongest to the classification variable has been called the "maximum-relevance selection". Many heuristic algorithms can be used, such as the sequential forward, backward, or floating selections.

On the other hand, features can be selected to be different from each other, while they still have high correlation to the classification variable. This scheme, called "minimum-Redundancy-Maximum-Relevance" selection (mRMR), has been found to be more powerful than the maximum relevance selection.

As a special case, statistical dependence between variables can be used instead of correlation. Mutual information can be used to quantify the dependency. In this case, it is shown that mRMR is an approximation to maximizing the dependency between the joint distribution of the selected features and the classification variable.

Embedded methods incorporating Feature Selection

• Random forests (RF)
• Random multinomial logit (RMNL)
• Ridge regression
• Decision tree
• Memetic algorithm
• Auto-encoding networks with a bottleneck-layer
• Many other machine learning methods applying a pruning step.

Software for Feature Selection

• RapidMiner, a freely available open-source software for intelligent data analysis, knowledge discovery, data mining, machine learning, visualization, etc. featuring numerous feature generation and feature selection operators.
• Weka, a Java software package including a collection of machine learning algorithms for data mining tasks.

See also

• Cluster analysis
• Dimensionality reduction
• Feature extraction
• Data mining

References

• JMLR Special Issue on Variable and Feature Selection
• Peng, H.C., Long, F., and Ding, C., Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 8, pp.1226-1238, 2005. Program
• Sun, Y., Todorovic, S., and Goodison, S., A feature selection algorithm capable of handling extremely large data dimensionality, in Proc. 8th SIAM International Conference on Data Mining (SDM’08), pp. 530-540, April 2008.
• Feature Selection for Knowledge Discovery and Data Mining (Book)
• An Introduction to Variable and Feature Selection (Survey)
• Toward integrating feature selection algorithms for classification and clustering (Survey)
• Searching for Interacting Features
• Feature Subset Selection Bias for Classification Learning
• M. Hall 1999, Correlation-based Feature Selection for Machine Learning

External links

• NIPS challenge 2003 (see also NIPS)
• Naive Bayes implementation with feature selection in Visual Basic (includes executable and source code)
• minimum-Redundancy-Maximum-Relevance (mRMR) feature selection program