Graphics Reference
In-Depth Information
Algorithm 4 Random feature set generation - RG.
function RG( F -fullset, U - measure)
initialize: S = S best ={}
S - subset set
initialize: C best = # ( F )
# - cardinality of a set
repeat
S = RandGen( F )
C = # ( S )
if C C best and S satisfies U then
S best = S
C best =
C
end if
until some stopping criterion is satisfied
return S best
Best set found so far
end function
Exhaustive Search : It corresponds to explore all possible subsets to find the optimal
ones. As we said before, the space complexity is O
2 M
. If we establish a threshold
m of minimum features to be selected and the direction of search, the search space
(
)
is 0 + 1 +···+ m , independent of the forward or backward generation.
Only exhaustive search can guarantee the optimality, however we can find an
optimal subset without visiting all possible states, by using exact algorithms such
as backtracking and branch and bound [ 38 ]. Nevertheless, they are also impractical
in real data sets with a high M .
Heuristic Search : It employs heuristics to carry out the search. Thus, it prevents
brute force search, but it will surely find a non-optimal subset of features. It draws
a path connecting the beginning and the end in Fig. 7.1 , such in a way of a depth-
first search. The maximum length of this path is M and the number of subsets
generated is O
. The choice of the heuristic is crucial to find a closer optimal
subset of features in a faster operation.
(
M
)
Nondeterministic Search : This third category arises from a complementary com-
bination of the previous two. It is also known as random search strategy and can
generate best subsets constantly and keep improving the quality of selected fea-
tures as time goes by. In each step, the next subset is obtained at random. There
are two properties of this type of search strategiy: (1) it is unnecessary to wait until
the search ends and (2) we do not know when the optimal set is obtained, although
we know which one is better than the previous one and which one is the best at
the moment.
7.2.2 Selection Criteria
After studying the essential approaches of search strategies and directions, the next
issue to tackle is the measurement of the quality or goodness of a feature. It is
necessary to distinguish between best or optimal subset of features and to be common
 
 
Search WWH ::




Custom Search