316.

[Cover] [Contents] [Index]

Page 83

aries are derived and the tree is designed manually to separate classes in a hierarchical fashion. The construction of a tree by manual design methods is time-consuming and may not provide satisfactory results, particularly when the number of classes is large and there is spectral overlap between classes.

Swain and Hauska (1977) proposed a heuristic search technique based on a mathematical evaluation function for solving problems that are more complex. Other strategies for an optimal hierarchical tree design are described by Kulkarni and Laveen (1976), Qing-Yun and Fu (1983) and Kurzinski (1983). The design of an optimum tree classifier, which will be reflected in both performance and computational efficiency, depends on the choice of the tree structure, the choice of features used in each terminal node, and the decision rules for performing the classification at each non-terminal node. Lee and Richards (1985) describe a classification strategy in which the classes are hierarchically separated in a piecewise linear fashion. In this approach, computational demands increase only linearly with the number of features used, and classification accuracy is claimed to be comparable to that of the ML classifier.

Kim and Landgrebe (1991) propose a hybrid approach to the design of decision tree classifiers The rationale underlying their technique is that a class must simultaneously be of informational value and separable from other classes. As we know, supervised procedures, based upon training samples, can guarantee the former but not the latter; unsupervised procedure can guarantee the latter but not the former. Further, only terminal nodes must be both of separable and informational value. Non-terminal nodes are not required to be classes of informational value, but they must represent separable classes.

This hybrid approach combines both supervised and unsupervised procedures to design the binary tree by determining the initial cluster centres with the training data and successively dividing each cluster into two subclusters. The means and covariance of clusters are then computed. If the separated groups are informational classes, the design is complete, otherwise new subdivisions are required. The advantage of the hybrid approach is that it is more likely to converge to classes of informational value, because clustering initialisation provides early guidance in that direction. Empirical tests comparing the hybrid design classifier with the conventional ones suggest that the former produces higher accuracy with fewer features (Kim and Landgrebe, 1991).

Interest in the use of automatic methods of designing and using decision tree classifiers has grown in recent years. Quinlan (1993) introduced the C4.5 algorithm (which has now progressed to C5.0). He notes that the building of a decision tree requires a ‘divide and conquer’ strategy that uses a recursive testing procedure with the aim of generating a small tree. The evaluation of all possible trees is computationally out of the question;

[Cover] [Contents] [Index]