# Variable selection procedure for binary classification

What are the variable/feature selection that you prefer for binary classification when there are many more variables/feature than observations in the learning set? The aim here is to discuss what is the feature selection procedure that reduces the best the classification error.

We can fix notations for consistency: for $i \in \{0, 1\}$, let $\{x_1^i,\dots, x_{n_i}^i\}$ be the learning set of observations from group $i$. So $n_0 + n_1 = n$ is the size of the learning set. We set $p$ to be the number of features (i.e. the dimension of the feature space). Let $x[i]$ denote the $i$-th coordinate of $x \in \mathbb{R}^p$.

Please give full references if you cannot give the details.

EDIT (updated continuously): Procedures proposed in the answers below

As this is community wiki there can be more discussion and update

I have one remark: in a certain sense, you all give a procedure that permit ordering of variables but not variable selection (you are quite evasive on how to select the number of features, I guess you all use cross validation?) Can you improve the answers in this direction? (as this is community wiki you don't need to be the answer writter to add an information about how to select the number of variables? I have openned a question in this direction here Cross validation in very high dimension (to select the number of used variables in very high dimensional classification))

• Is it a question or a pool? If the latter, it should be community wiki. If the first, give more details about what you want to achieve? For instance, is it all-relevant or rather minimal-optimal selection? How much is many? How hard is the classification problem?
– user88
Commented Jul 22, 2010 at 11:38
• pool... many means 1000 features or more and less than 100 observations. Commented Jul 22, 2010 at 11:58

A very popular approach is penalized logistic regression, in which one maximizes the sum of the log-likelihood and a penalization term consisting of the L1-norm ("lasso"), L2-norm ("ridge"), a combination of the two ("elastic"), or a penalty associated to groups of variables ("group lasso"). This approach has several advantages:

1. It has strong theoretical properties, e.g., see this paper by Candes & Plan and close connections to compressed sensing;
2. It has accessible expositions, e.g., in Elements of Statistical Learning by Friedman-Hastie-Tibshirani (available online);
3. It has readily available software to fit models. R has the glmnet package which is very fast and works well with pretty large datasets. Python has scikit-learn, which includes L1- and L2-penalized logistic regression;
4. It works very well in practice, as shown in many application papers in image recognition, signal processing, biometrics, and finance.

I have a slight preference for Random Forests by Leo Breiman & Adele Cutleer for several reasons:

• it allows to cope with categorical and continuous predictors, as well as unbalanced class sample size;
• as an ensemble/embedded method, cross-validation is embedded and allows to estimate a generalization error;
• it is relatively insensible to its tuning parameters (% of variables selected for growing a tree, # of trees built);
• it provides an original measure of variable importance and is able to uncover complex interactions between variables (although this may lead to hard to read results).

Some authors argued that it performed as well as penalized SVM or Gradient Boosting Machines (see, e.g. Cutler et al., 2009, for the latter point).

A complete coverage of its applications or advantages may be off the topic, so I suggest the Elements of Statistical Learning from Hastie et al. (chap. 15) and Sayes et al. (2007) for further readings.

Last but not least, it has a nice implementation in R, with the randomForest package. Other R packages also extend or use it, e.g. party and caret.

References:

Cutler, A., Cutler, D.R., and Stevens, J.R. (2009). Tree-Based Methods, in High-Dimensional Data Analysis in Cancer Research, Li, X. and Xu, R. (eds.), pp. 83-101, Springer.

Saeys, Y., Inza, I., and Larrañaga, P. (2007). A review of feature selection techniques in bioinformatics. Bioinformatics, 23(19): 2507-2517.

Metropolis scanning / MCMC

• Select few features randomly for a start, train classifier only on them and obtain the error.
• Make some random change to this working set -- either remove one feature, add another at random or replace some feature with one not being currently used.
• Train new classifier and get its error; store in dE the difference the error on the new set minus the error on the previous set.
• With probability min(1;exp(-beta*dE)) accept this change, otherwise reject it and try another random change.
• Repeat it for a long time and finally return the working set that has globally achieved the smallest error.

You may extend it with some wiser control of beta parameter. Simpler way is to use simulated annealing when you increase beta (lower the temperature in physical analogy) over the time to reduce fluctuations and drive the algorithm towards minimum. Harder is to use replica exchange.

If you are only interested in generalization performance, you are probably better off not performing any feature selection and using regularization instead (e.g. ridge regression). There have been several open challenges in the machine learning community on feature selection, and methods that rely on regularization rather than feature selection generally perform at least as well, if not better.

Greedy forward selection.

The steps for this method are:

• Make sure you have a train and validation set
• Repeat the following
• Train a classifier with each single feature separately that is not selected yet and with all the previously selected features
• If the result improves, add the best performing feature, else stop procedure
• How do you "train" your classifier? Presumably this is done on the training set. If it is a Support vector Machine (SVM) there are several parameters to try during training. Is each tested against the validation (test) set? Or are you using k-fold cross validation? How many times are you using the validation (test) set to check your performance - presumably this is accuracy. Sorry to be pedantic, but this is a poorly defined answer and risks over-fitting. Commented Aug 9, 2010 at 9:08
• @Thylacoleo This is a very crude basic and greedy method. Often you keep your validation set the same over runs, but whatever you like is ok. Commented Aug 9, 2010 at 18:20

Backward elimination.

Start with the full set, then iteratively train the classifier on the remaining features and remove the feature with the smallest importance, stop when the classifier error rapidly increases/becomes unacceptable high.

Importance can be even obtained by removing iteratively each feature and check the error increase or adapted from the classifier if it produces it (like in case of Random Forest).

• But the question says there are more variables than observations. So it is not possible to begin with the full set. Commented Jul 23, 2010 at 9:50
• What's the problem?
– user88
Commented Jul 23, 2010 at 13:41
• You can't fit a model that has more variables than observations. There are not enough degrees of freedom for parameter estimation. Commented Jul 25, 2010 at 4:42
• In Fisher's F calculation, you compute the F as (n - k - p) / (k - 1) * ... with n the number of observations, k the number of classes (2 here) and p the number of variables. n - 2 - p < 0 when n < p + 2 (which is the case here) which leads to F < 0. Wouldn't that be a problem? Commented Sep 2, 2014 at 9:17
• Regularized or fully Bayesian regression would allow a unique solution to be got with the full set of predictors to start with - doubtless the same goes for some other ML techniques. Commented Apr 5, 2016 at 14:39