For the task of selecting the best subset of variables among many noisy and collinear ones, we decided to accompany our usual Boston house dataset with a tricky one, the Madelon dataset (https://archive.ics.uci.edu/ml/datasets/Madelon). It is an artificial dataset (that is generated using an algorithm) presented at the NIPS 2003 (the seventh Annual Conference on Neural Information Processing Systems) during a contest on feature selection.

The dataset is particularly challenging because it has been generated by placing 32 distinct clusters of points (16 from the positive group, 16 from the negative one) on the vertices of a five-dimension hypercube. The resulting 500 features and 2,000 cases have been extracted from various transformations of the five metric dimensions. To make things harder, some random numbers have been added to the features to act as noise and a few responses have been flipped (the flipped ones amount to 1%). All these intricate transformations make dealing with the modeling quite difficult, especially for linear models, since the relationship of most of the features with the response is definitely non-linear. This is really helpful for our exemplification because it clearly demonstrates how a direct inclusion of all the features is detrimental to the accuracy of out-of-sample predictions.

To download and make available on your computer such an interesting and challenging dataset, please carry out the following instructions and allow some time for your computer to download the data from the external website where it is stored:

In: try:
import urllib.request as urllib2
  except:
    import urllib2
  import numpy as np
  train_data = 'https://archive.ics.uci.edu/ml/machine-learning-databases/madelon/MADELON/madelon_train.data'
  validation_data = 'https://archive.ics.uci.edu/ml/machine-learning-databases/madelon/MADELON/madelon_valid.data'
train_response = 'https://archive.ics.uci.edu/ml/machine-learning-databases/madelon/MADELON/madelon_train.labels'
  validation_response = 'https://archive.ics.uci.edu/ml/machine-learning-databases/madelon/madelon_valid.labels'
try:
      Xt = np.loadtxt(urllib2.urlopen(train_data))
      yt = np.loadtxt(urllib2.urlopen(train_response))
      Xv = np.loadtxt(urllib2.urlopen(validation_data))
      yv = np.loadtxt(urllib2.urlopen(validation_response))
except:
    # In case downloading the data doesn't works, 
# just manually download the files into the working directory
      Xt = np.loadtxt('madelon_train.data')
      yt = np.loadtxt('madelon_train.labels')
      Xv = np.loadtxt('madelon_valid.data')
      yv = np.loadtxt('madelon_valid.labels')

After finishing loading both the training and validation sets, we can start exploring some of the information available:

In: print ('Training set: %i observations %i feature' % (Xt.shape))
  print ('Validation set: %i observations %i feature' % (Xv.shape))
Out:  Training set: 2000 observations 500 feature
    Validation set: 600 observations 500 feature 

Naturally, we won't touch the validation set (we won't even glance at it or it would be snooping), but we can try to figure out the situation with the training set:

In:from scipy.stats import describe
  print (describe(Xt))

The output is quite lengthy and it is put in matrix form (therefore it is not reported here), but it really tells us everything about the mean, min, max, variance, skewness, and kurtosis for each feature in the dataset. A fast glance through it doesn't reveal anything special; however, it explicits that all the variables have an approximately normal distribution and that they have a limited range of values. We can proceed with our exploration using a graphical representation of correlations among the variables:

import matplotlib.pyplot as plt
import matplotlib as mpl
%matplotlib inline

def visualize_correlation_matrix(data, hurdle = 0.0):
    R = np.corrcoef(data, rowvar=0)
    R[np.where(np.abs(R)<hurdle)] = 0.0
    heatmap = plt.pcolor(R, cmap=mpl.cm.coolwarm, alpha=0.8)
    heatmap.axes.set_frame_on(False)
    plt.xticks(rotation=90)
    plt.tick_params(axis='both', which='both', bottom='off',
                  top='off', left = 'off',right = 'off')
    plt.colorbar()
    plt.show()

visualize_correlation_matrix(Xt[:,100:150], hurdle=0.0)

Check the following screenshot:

After a glance at a portion of the features and their respective correlation, we can notice that just a couple of them have a significant correlation, whereas the others are mildly related. This gives the impression of noisy relationships between them, thus rendering an effective selection quite complicated.

As a last step, we check how a simple logistic regression model would score in terms of the error measured using the area under the curve metric.

Logistic regression classifies an observation as positive if the threshold is over 0.5 since such a split is always proved to be optimal, but we can freely change that threshold. To increase the precision at a top selection of results we just raise the threshold from 0.5 to 1.0 (raising the threshold increases the accuracy in the selected range). Instead, if we intend to increase the total number of guessed positive cases we just choose a threshold inferior to 0.5 down to almost 0.0 (lowering the threshold increases the coverage of positive cases in the selected range).

The AUC error measure helps us determine whether our predictions are ordered properly, no matter their effective precision in terms of value. Thus, AUC is the ideal error measure to evaluate an algorithm for selection. If you order results properly based on probability, no matter if the guessed probability is correct or not, you can simply pick the correct selection to be used by your project by changing the 0.5 threshold—that is, by taking a certain number of the top results.

In our case, the baseline AUC measure is 0.602, a quite disappointing value since a random selection should bring us a 0.5 value (1.0 is the maximum possible):

In: from sklearn.cross_validation import cross_val_score
  from sklearn.linear_model import LogisticRegression
  logit = LogisticRegression()
  logit.fit(Xt,yt)

  from sklearn.metrics import roc_auc_score
  print ('Training area under the curve: %0.3f' % 
oc_auc_score(yt,logit.predict_proba(Xt)[:,1]))
  print ('Validation area under the curve: %0.3f' % 
oc_auc_score(yv,logit.predict_proba(Xv)[:,1]))

Out:   Training area under the curve: 0.824
    Validation area under the curve: 0.602

Given this new tricky dataset, we really have to deal with a large number of either irrelevant or redundant features. Hopefully, after removing them all, our model should increase its performance, and this is indicated by the large difference in AUC score between the in-sample and out-sample values that we got from our last code snippet.

In addition, if interpreting your model is a valuable addition, you really should remove non-useful variables, striving for the simplest possible form of your linear model as dictated by Occam's razor, a commonplace practice in science, favoring simpler solutions against more complex ones when their difference in performance is not marked.

Feature selection can help in both increasing the model out-sample performance and its human readability by retaining only the most predictive set of variables in the model, in some cases just the best ones and in others the set that works the best in unison.

There are quite a few feature selection methods. The simplest approach is the univariate method, which evaluates how good a variable is by estimating its predictive value when taken alone in respect of the response.

This usually involves using statistical tests, and Scikit-learn offers three possible tests:

All such tests output a score and a statistical test expressed by a p-value. High scores, confirmed by small p-values (under 0.05, indicating a low probability that the score has been obtained by luck), will provide you with confirmation that a certain variable is useful for predicting your target.

In our example, we will use f_class (since we are working on a classification problem now) and we will have the SelectPercentile function help us by selecting a certain percentage of high-scoring features:

In: from sklearn.feature_selection import SelectPercentile, f_classif
selector = SelectPercentile(f_classif, percentile=50)
selector.fit(Xt,yt)
variable_filter = selector.get_support()

After selecting the upper half, hoping to have cut off the most irrelevant features and to have kept the important ones, we plot our results on an histogram to reveal the distribution of the scores:

In: plt.hist(selector.scores_, bins=50, histtype='bar')
plt.grid()
plt.show()

Look at the following screenshot:

Noticeably, most scores are near zero, with a few high-ranking ones. Now we are going to pick the features we assume to be important by directly selecting a threshold empirically chosen for its convenience:

  In: variable_filter = selector.scores_ > 10
  print ("Number of filtered variables: %i" %  np.sum(variable_filter))
  from sklearn.preprocessing import PolynomialFeatures
  interactions = PolynomialFeatures(degree=2, interaction_only=True)
  Xs = interactions.fit_transform(Xt[:,variable_filter])
  print ("Number of variables and interactions: %i" % Xs.shape[1])

Out:   Number of filtered variables: 13
Number of variables and interactions: 92

Now, we have reduced our dataset to just the core features. At this point, it does make sense to test a polynomial expansion and try to automatically catch any relevant non-linear relationship in our model:

In: logit.fit(Xs,yt)
Xvs = interactions.fit_transform(Xv[:,variable_filter])
 print ('Validation area Under the Curve ' + 
        'before recursive  selection:   %0.3f' % 
        roc_auc_score(yv,logit.predict_proba(Xvs)[:,1]))

Out:   Validation area Under the Curve before 
recursive selection: 0.808

The resulting validation score (out-sample) is about 0.81, a very promising value given our initial overfitted score of 0.82 on the training set. Of course, we can decide to stop here or try to go on filtering even the polynomial expansion; feature selection is really a never-ending job, though after a certain point you have to realize that only slightly incremental results are possible from further tuning.

The only problem with univariate selection is that it will decide the best features by considering each feature separately from the others, not verifying how they work together in unison. Consequently, redundant variables are not infrequently picked (due to collinearity).

A multivariate approach, such as recursive elimination, can avoid this problem; however, it is more computationally expensive.

Recursive elimination works by starting with the full model and by trying to exclude each variable in turn, evaluating the removal effect by cross-validation estimation. If certain variables have a negligible effect on the model's performance, then the elimination algorithm just prunes them. The process stops when any further removal is proven to hurt the ability of the model to predict correctly.

Here is a demonstration of how RFECV, Scikit-learn's implementation of recursive elimination, works. We will use the Boston dataset enhanced by second-degree polynomial expansion, thus working on a regression problem this time:

In: from sklearn.feature_selection import RFECV
from sklearn.cross_validation import KFold
from sklearn.cross_validation import train_test_split
X_train, X_test, y_train, y_test = 
    train_test_split(X, y, test_size=0.30, random_state=1)
    
lm = LinearRegression()
cv_iterator = KFold(
    n=len(X_train), n_folds=10, shuffle=True, random_state=101)
recursive_selector = RFECV(estimator=lm, step=1, cv=cv_iterator, scoring='mean_squared_error')
recursive_selector.fit(second_order.fit_transform(X_train),
y_train)
print ('Initial number of features : %i' % 
       second_order.fit_transform(X_train).shape[1])
print ('Optimal number of features : %i' % 
       recursive_selector.n_features_)

Out:   Initial number of features : 105
Optimal number of features : 52

Given an estimator (our model), a cross validation iterator, and an error measure, RFECV will find out after a while that half of the features can be dropped from the model without fear of worsening its performance:

In: essential_X_train = recursive_selector.transform(
    second_order.fit_transform(X_train))
essential_X_test  = recursive_selector.transform(
    second_order.fit_transform(X_test))
lm.fit(essential_X_train, y_train)
print ('cases = %i features = %i' % essential_X_test.shape)
print ('In-sample  mean squared error %0.3f' %  
mean_squared_error(y_train,lm.predict(essential_X_train)))
print ('Out-sample mean squared error %0.3f' % 
mean_squared_error(y_test,lm.predict(essential_X_test)))

Out:   cases = 152 features = 52
In-sample  mean squared error 7.834
Out-sample mean squared error 11.523

A test-based check will reveal that now the out-sample performance is 11.5. For further confirmation, we can also run a cross-validation and obtain a similar result:

In: edges = np.histogram(y, bins=5)[1]
binning = np.digitize(y, edges)
stratified_cv_iterator = StratifiedKFold(binning, n_folds=10, shuffle=True, random_state=101)
essential_X = recursive_selector.transform(
    second_order.fit_transform(X))
cv_score = cross_val_score(
    lm, essential_X, y, cv=stratified_cv_iterator, 
    scoring='mean_squared_error', n_jobs=1)
print ('Cv score: mean %0.3f std %0.3f' % (np.mean(np.abs(cv_score)), np.std(cv_score)))

Out: Cv score: mean 11.400 std 3.779