7 A Review of Feature Reduction Methods …
125
of choice is used to evaluate this subset. This process of subset generation and
testing is repeated until the desired objective function is achieved [27, 28] (Fig. 7.1b).
Wrappers tend to perform better than filters in selecting features since they consider
feature dependencies and directly incorporate the specific biases and heuristics of the
learning algorithm into the selection process. However, this implies that the selected
features are unlikely to be optimal for any other classifiers [18].
The size of search space for m features is O(2
m ) [28]. Since evaluating the subsets
of such a search space is considered an NP-hard problem, the computational inefficiency of wrappers becomes evident when using larger datasets. However, search
algorithms have been proposed for selecting optimal subsets of the feature space.
Broadly, we consider two groups of search strategies for wrappers: sequential and
heuristic selection algorithms [25].
7.2.2.1 Sequential Selection Algorithms
Sequential selection can be achieved in two ways: forward selection and backward
elimination. Sequential forward selection (SFS) begins with an empty set of features,
and features are progressively incorporated into larger and larger subsets (one at a
time) until no further improvement is recorded in the evaluation criterion. A backward
elimination algorithm begins with the full set of features and iteratively eliminates
the least relevant features [28].
The sequential floating forward selection (SFFS) [45, 46] algorithm has been
suggested as an improvement over SFS because it includes flexible backtracking
capabilities. Similar to SFS, SFFS adds one feature at a time as determined by the
objective function. Meanwhile, it backtracks by eliminating one feature at a time
from the initial subset, followed by an evaluation. If an improvement is noticed in
the objective function, it leaves that feature out and moves on to add a new feature.
This process goes on iteratively until the desired goal is met with the fewest number
of features.
7.2.2.2 Heuristic Selection Algorithms
Heuristic search algorithms evaluate different subsets to optimize the objective function. Subsets can be generated by evaluating a search space or by generating solutions
to the optimization problem, with the learning algorithm’s performance being the
objective function [25]. Simulated annealing (SA) [47] and genetic algorithms (GA)
[48], two widely used heuristic algorithms, find a subset of features for wrappers. A
hybrid of these methods has also been suggested [49]. In GA, the chromosome bits
indicate if a feature should be included or not. SA, a stochastic algorithm, solves
for the global minimum of a function by improving the initial solution repeatedly
using small local perturbations until no such perturbations yield an improvement in
the objective function. This process is randomized such that there are occasional and
intentional deviations from the solution to lessen the probability of becoming stuck
125
of choice is used to evaluate this subset. This process of subset generation and
testing is repeated until the desired objective function is achieved [27, 28] (Fig. 7.1b).
Wrappers tend to perform better than filters in selecting features since they consider
feature dependencies and directly incorporate the specific biases and heuristics of the
learning algorithm into the selection process. However, this implies that the selected
features are unlikely to be optimal for any other classifiers [18].
The size of search space for m features is O(2
m ) [28]. Since evaluating the subsets
of such a search space is considered an NP-hard problem, the computational inefficiency of wrappers becomes evident when using larger datasets. However, search
algorithms have been proposed for selecting optimal subsets of the feature space.
Broadly, we consider two groups of search strategies for wrappers: sequential and
heuristic selection algorithms [25].
7.2.2.1 Sequential Selection Algorithms
Sequential selection can be achieved in two ways: forward selection and backward
elimination. Sequential forward selection (SFS) begins with an empty set of features,
and features are progressively incorporated into larger and larger subsets (one at a
time) until no further improvement is recorded in the evaluation criterion. A backward
elimination algorithm begins with the full set of features and iteratively eliminates
the least relevant features [28].
The sequential floating forward selection (SFFS) [45, 46] algorithm has been
suggested as an improvement over SFS because it includes flexible backtracking
capabilities. Similar to SFS, SFFS adds one feature at a time as determined by the
objective function. Meanwhile, it backtracks by eliminating one feature at a time
from the initial subset, followed by an evaluation. If an improvement is noticed in
the objective function, it leaves that feature out and moves on to add a new feature.
This process goes on iteratively until the desired goal is met with the fewest number
of features.
7.2.2.2 Heuristic Selection Algorithms
Heuristic search algorithms evaluate different subsets to optimize the objective function. Subsets can be generated by evaluating a search space or by generating solutions
to the optimization problem, with the learning algorithm’s performance being the
objective function [25]. Simulated annealing (SA) [47] and genetic algorithms (GA)
[48], two widely used heuristic algorithms, find a subset of features for wrappers. A
hybrid of these methods has also been suggested [49]. In GA, the chromosome bits
indicate if a feature should be included or not. SA, a stochastic algorithm, solves
for the global minimum of a function by improving the initial solution repeatedly
using small local perturbations until no such perturbations yield an improvement in
the objective function. This process is randomized such that there are occasional and
intentional deviations from the solution to lessen the probability of becoming stuck