Feature selection

From Wikipedia, the free encyclopedia

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 that which are the important features and how they are related with each other.

1 Introduction
2 Subset Selection
3 Optimality criteria
4 minimum-Redundancy-Maximum-Relevance
5 Embedded methods incorporating Feature Selection
6 Software for Feature Selection
7 References
8 See also
9 External links

[edit] 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.

[edit] 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. These metrics 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

[edit] 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^{[citation needed]}, 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}}}$ .

[edit] 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.

[edit] Embedded methods incorporating Feature Selection

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

[edit] 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.