Is it normal for exhaustive feature selector to run for three days?

Question

I'm trying to optimize my features in a dataset to get a better predictive model. I used Exhaustive feature selector from mlxtend. This checks all possible combinations of features. I have a dataset with 80+ features, and I set the maximum of features to be selected to 20 with 10-Fold cross validation. There are 9k entries and the estimator is Random Forest Regressor. It's been roughly three days this has been running. Is this normal? Previously I have run Recursive Feature Elimination on the same dataset with 10 fold cross validation. It took roughly 24 hours.

efs = EFS(RandomForestRegressor(), 
      min_features=3,
      max_features=20,
      scoring='neg_mean_squared_error',
      cv=10)

     efs.fit(X, Y)

Answer 1

An exhaustive search means that the 10-fold CV is run for every possible subset of features. The number of possible subsets of size 20 for a set of 80 features is:

$$\binom{80}{20}=3.5\ 10^{18}$$.

And this is only for size 20 exactly, so the total number is higher.

So yes, it might take a very long time. You could estimate the duration before running a potentially very long experiment like this:

• First take a lower maximum number of features and calculate the corresponding number of runs. For instance with 5 as maximum the number of subsets would be roughly around 24 millions (I let you calculate the exact number).
• Then run the experiment and measure the duration. Applying a simple proportion you can estimate how much time it would takes for any maximum number of features. You might find out that your current experiment would take many years ;)

Exhaustive search on a large set is rarely a good idea, I'd suggest looking at genetic search.