Graphics Reference
In-Depth Information
Algorithm 1 provides details for SFG. Here, the best feature
f
is chosen by
FindNext(
F
)
.
f
is added into
S
and removed from
F
,growing
S
and shrinking
F
.
There can be two stopping criteria, either when the
F
set is empty or when
S
satisfies
U
. Adopting only the first criterion, we can obtain a ranked list of features.
Algorithm 1
Sequential forward feature set generation - SFG.
function
SFG(
F
-fullset,
U
- measure)
initialize:
S
={}
S
stores the selected features
repeat
f
= FindNext(
F
)
S
=
S
∪{
f
}
F
=
F
−{
f
}
until
S
satisfies
UorF
={}
return
S
end function
To the contrary of SFG, Algorithm 2 illustrates the direction SBG, where the
search starts with the full set
F
and finds a feature subset
S
by removing one feature
at a time. The function
GetNext(
F
)
finds out the least relevant feature
f
which will
be removed from
F
. In this case, also
F
shrinks and
S
grows, but
S
only stores the
irrelevant features.
Algorithm 2
Sequential backward feature set generation - SBG.
function
SBG(
F
-fullset,
U
- measure)
initialize:
S
={}
S
holds the removed features
repeat
f
= GetNext(
F
)
F
=
F
−{
f
}
}
until
S
does not satisfy
UorF
S
=
S
∪{
f
={}
return
F
∪{
f
}
end function
There are other search directions that base their existence in the usual case in
which the optimal subset should be in the middle range of the beginning and the
end of the search space. So, it is very intuitive to start from both ends and perform
a bidirectional search. The probability of finding the optimal subset is increased
because a search in one direction usually finishes faster than in the other direction.
•
Bidirectional Generation (BG)
: Begins the search in both directions, performing
SFG and SBG concurrently. They stop in two cases: (1) when one search finds the
best subset comprised of
m
features before it reaches the exact middle, or (2) both
searches achieve the middle of the search space. It takes advantage of both SFG
and SBG.
