# More features than data points in linear regression

In a dataset with more features (e.g. 120) than data points (e.g. 60) what are the techniques commonly used to select the best features to apply linear regression? Obviously there is an efficiency problem here - you cannot enumerate all the subsets of features and try them one by one. Suggestion of some library/function in R would also be very useful to me.

First, you should know we can use all features in the model (even they have strong correlation). The trick is adding regularization terms. Please check Lasso and Ridge Regression in An Introduction to Statistical Learning. (On page 215 of the book:) In ridge regression, your loss function is changing from

$$\sum_{i=1}^n (y_i -f(\mathbf x_i))^2$$

to

$$\sum_i (y_i -f(\mathbf x_i))^2+\lambda \cdot|| \pmb \beta ||_2^2$$

Using this approach (all features with regularization) will give generally you better "performance" but lower "interpretation", comparing to "select some features".

If you really want to select features instead of using all of them, there are many approaches, from comprehensive approaches such as "best subset" (which you mentioned about not scalable on large number of features) to greedy approaches such as "forward stage-wise". (The word "greedy" will tell you it works on large number of features, but cannot guarantee the selected subset is the "best"/ global optima.)

Here are some sample code (most important line) from chapter 6 lab section of the book.

regfit.fwd=regsubsets(Salary~.,data=Hitters,nvmax=19,method="forward")


The output looks like this

It shows the algorithm first select the CRBI feature, then Hits feature. Note that, once a feature is selected, we will not change it in the future. This greedy solution make it work on a large scale problem

I would strongly recommend you to read the chapter 6 of the book, which is freely available online.