Page 135 -

122 4 Statistical Classification

Optimal methods

I. Exhaustive search
The exhaustive search of all subsets F of F, will certainly yield an optimum subset.
This is rarely done, however, given the computational burden usually implied by
such a search.

2. Branch and bound search
The branch and bound algorithm is a well-known method of finding optimal
solutions in combinatorial problems with a monotonic criterion. In the present
case, it will guarantee the optimal solution if the used criterion J(F) is monotonic
(e.g. the Bhattacharyya distance). We will now explain the most important aspects
of this powerful search method, whose implementation details can be found in
Narendra and Fukunaga (1977).
Let D be a set of discarded features, which at the end of the search will have
m=t-d discarded features. We will arbitrarily enumerate these features from 1 to m
and represent the search process depending on J(D) as a tree. Figure 4.35
represents this tree for k5 and d=2, with values of J(D) for some nodes. Each path
in the tree represents a sequence of discarded features. Notice that for building the
tree, we only have to enumerate features with higher indices at each node, since the
order of the discarded features is of no importance. Furthermore, given the
monotonicity of the class separability criterion, it can only decrease when going
downwards in the tree (increasing the number of discarded features).

Start

X, (0.765) Level 1

x, x4 x5 X4 (0.768) X5 (0.76) X5 (0.77) X4 X5 X5 Level 3

Figure 4.35. Branch-and-bound tree for t=5 and d=2. Followed optimal paths have
the criterion values in bold.