Feature Selection - Data Preprocessing in Data Mining - page 177

The rest of this section presents some representative and so-considered classical
FS algorithms in the specialized literature. The algorithms are described and their
components are identified by using the components described above. We categorize
them according to the search strategy in the next subsections. Also, we provide a
discussion on one variant: feature weighting schemes.

7.4.1 Exhaustive Methods

Exhaustivemethods cover thewhole search space.We find six combinations (C1-C6)
within this category and corresponding to a forward or a backward search (growing
or reducing gradually the subset of features selected, respectively) with any kind of
evaluation measure which must be satisfied in each step.
In particular, we will detail the combination C2, corresponding with the con-
sistency measure for forward search, respectively. Here, the most famous method
is Focus [ 2 ]. It considers all the combinations among A features starting from an

empty subset: 1 subsets first, 2 subsets next, etc. When Focus finds a subset
that satisfies the consistency measure, it stops. The details of this method is shown
in Algorithm 7. Focus needs to generate

i subsets in order to find a minimum
subset of m features that satisfies the consistency criterion. If m is not small, the run-
time is quite prohibitive. Heuristics variations of Focus replaces the pure consistency
objective with the definition of good subsets.

i

m

Algorithm 7 Focus algorithm.
function Focus( F - all features in data D , U - inconsistency rate as evaluation measure)
initialize: S ={}

for i 1to M do

for each subset S of size i do
if CalU( S , D )=0 then

=

CalU( S , D ) returns inconsistency

return S - a minimum subset that satisfies U
end if
end for
end for
end function

Other exhaustive FSmethods deserve to bementioned in this section. An overview
of these methods can be found in [ 10 ]:

• Automatic Branch and Bound (ABB) [ 30 ], belonging to the C5 class.

• Best First Search (BFS) [ 60 ], belonging to the C1 class.

•

Beam Search [ 12 ], belonging to the C3 class.

•

Branch and Bound (BB) [ 38 ], belonging to the C4 class.