Page 379 - Introduction to Statistical Pattern Recognition

7 Nonparametric Classification and Error Estimation 36 1

samples can be hierarchically decomposed to subsets, sub-subsets and so on
[24]. In order to describe the procedure, let us set up a tree structure as in Fig.
7-17 where each node represents a subset, Sk. Each subset is decomposed into

Fig. 7-17 A solution tree in the branch and bound procedure.

several other subsets, and at the bottom of the tree each node represents an
individual sample. Each subset (or node) is characterized by the mean vector
of the samples in Sp, Mk, and the furthest distance from Mk to a sample in Sk,
dk .
When the NN sample of an unknown X is sought, the search begins from
the leftmost branch. After comparing the distances from X to X8, XI3, X,,,
and Xl0, X2s is found as the closest one to X. The computer back-tracks the
tree from S2 to SI and then moves to S3. However, before testing the
members of S3, it is tested whether or not the following inequality is satisfied.

d(X,Mx) > d(X.Xz5) + d3 . (7.87)
If the inequality is satisfied, there is no possibility that the distance between X
and any member of S3 is smaller than d(X,Xl5) [see Fig. 7-18]. Therefore, the
search moves to S4 without testing the members of S3.
The procedure works well in a low-dimensional space. An experimental
result for a uniform distribution in a two-dimensional space shows that only 46
distance computations are needed to find the NN among 1000 samples. In this