Graphics Reference
In-Depth Information
/
When the number of relevant features
m
is smaller than
M
2, SFG is faster,
/
otherwise if
m
is greater than
M
2, then SBG is faster. As the value of
m
is usually
unknown, it would be impossible to know which scheme would be faster. Thus, the
bidirectional generation makes sense, and it is shown in operation in Algorithm 3.
In it, SFG and SBG are run in parallel and it stops if either find a satisfactory subset.
Algorithm 3
Bidirectional feature set generation - BG.
function
BG(
F
f
,
F
b
-fullset,
U
- measure)
initialize:
S
f
={}
S
f
holds the selected features
initialize:
S
b
={}
S
b
holds the removed features
repeat
f
f
= FindNext(
F
f
)
f
b
= GetNext(
F
b
)
S
f
=
S
f
∪{
f
f
}
F
b
=
F
b
−{
f
b
}
F
f
=
F
f
−{
f
f
}
}
until
(a)
S
f
satisfies
UorF
f
S
b
=
S
b
∪{
f
b
={}
or
(b)
S
b
does not satisfy
UorF
b
={}
return
S
f
if (a)
or F
b
∪{
f
b
}
if (b)
end function
Finally, there is another search direction used to not pursue any particular direc-
tion, instead, the direction is randomly chosen.
•
Random Generation (RG)
: It starts the search in a random direction. The choice of
adding or removing a features is a randomdecision. RG tries to avoid the stagnation
into a local optima by not following a fixed way for subset generation. Unlike SFG
or SBG, the size of the subset of features cannot be stipulated.
A random generation scheme produces subsets at random. Based on a good ran-
dom number generator attached with a function called
RandGen(F)
in such a way
that every combination of features
F
has a chance to occur and only once. This
scheme is summarized in Algorithm 4, where
S
is a subset of features.
From now on, we can combine these search directions with a suitable search
strategy to design the best FS algorithm for a certain problem we may encounter.
7.2.1.2 Search Strategies
Brute force search doesn't make sense when
M
is large. The more resources we
spend during the search process, the better the subset we may find. However, when
the resources are finite, as usual, we have to reduce the optimality of the selected
subsets. So, the purpose is to get a good trade-off between this optimality and the
lesser quantity of resources required. Since it is not an easy task, threemain categories
summarize the search strategies:
