Graphics Reference
In-Depth Information
7.4.2 Heuristic Methods
FS based on heuristics involve most of the existing proposal in specialized literature.
Generally, they do not have any expectations of finding an optimal subset with a
rapid solution, which tries to be closer to an optimal one. The simplest method is
to learn a model and select the features used by the DM algorithm (if the algorithm
allows us to do it, like a decision tree or an ANN [
49
]). It can be viewed as a simple
version of a FS belonging to the C12 class.
A more sophisticated version of a C12 feature selector consists of doing a back-
ward selection using a wrapper classifier. A sequential forward selection algorithm
(C9) works as follows: begin with an empty set
S
, in each iteration (with a maxi-
mum of
M
), choose one feature from the unchosen set of features that gives the best
accuracy combining with the already chosen features in
S
. Other hybridizations of
search direction, such as bidirectional or floating selection, are described for wrapper
methods in [
23
].
Regarding the other evaluation measures, we can find some proposals in literature:
•
SetCover [
10
] belongs to the C8 class.
•
The set of algorithms presented in [
37
] belong to the C7 class.
•
The algorithm proposed in [
24
] belongs to the C10 class, specifically by using
information theory measures.
How about combinations C13, C14 and C15? In them, the features are randomly
generated, but the search is heuristic. One implementation of these combinations
is adopting a heuristic search algorithm and in each sub-search space, randomly
generate the features and these subsets of features form the possible sub-search
spaces.
One of the heuristic methods that deserves mention is the
Mutual Information
based FS (MIFS)
[
5
], which is based on the single computation of the MI measure
between two features at the same time, and replacing the impossible exhaustive search
with a greedy algorithm. Given already selected features, the algorithm chooses the
next feature as the one that maximizes information about the class to the average MI
with the selected features. MIFS is described in the Algorithm 8, and belongs to the
C10 category.
7.4.3 Nondeterministic Methods
Also known as stochastic methods, they add or remove features to and from a subset
without a sequential order, allowing the search to follow feature subsets that are
randomly generated.
Common techniques in this category are genetic algorithms and simulated anneal-
ing . In [
18
], a comparison of genetic algorithms with sequential methods is presented,
it is very difficult to fairly compare them because of the parameter adjustment. The
