8.1: Exhaustive Feature Selection

Exhaustive search method is a complete search method. It follows a brute-force approach. In this method, all possible combinations of features are tested to find the best possible combination of features. This guarantees an optimal solution. However, the computational resource and time required for an exhaustive search are very high. It requires 2^N combinations for N features. Even with a relatively smaller N, search space can increase exponentially. This makes it computationally expensive and sometimes computationally prohibitive.

Python library mlxtend has a module ExhaustiveFeatureSelector for performing the exhaustive search. It also allows deciding the minimum and the maximum number of acceptable features. Based on these thresholds, all possible feature combinations are generated. This can reduce the computational complexity to a certain extent, as the number of possible feature combinations is restricted. However, this comes at the cost of possibly missing out on a better combination that wasn't explored because it was higher or lower than the acceptable number of features specified in the module.

It is computationally prohibitive to use exhaustive feature selection in its true sense to find the best combination of features for a model, from amongst all possible permutations and combinations. Hence, we will not be using this method for feature selection. In the rest of the sections of this chapter, we will try to solve the limitations of exhaustive feature selection with the help of metaheuristic algorithms.