![](https://csdnimg.cn/release/download_crawler_static/86306416/bg9.jpg)
DECISION TREE CONSTRUCTION: SURVEY 353
the Gini index of diversity
9
, which has been used for tree construction in statistics
(Breiman, et al. 1984), pattern recognition (Gelfand, Ravishankar and Delp, 1991) and se-
quential fault diagnosis (Pattipati and Alexandridis, 1990). Breiman et al. pointed out that
the Gini index has difficulty when there are a relatively large number of classes, and sug-
gested the twoing rule (Breiman, et al. 1984) as a remedy. Taylor and Silverman (1993)
pointed out that the Gini index emphasizes equal sized offspring and purity of both chil-
dren. They suggested a splitting criterion, called mean posterior improvement (MPI), that
emphasizes exclusivity between offspring class subsets instead.
Bhattacharya distance (Lin and Fu, 1983), Kolmogorov-Smirnoff distance (Friedman,
1977, Rounds, 1980, Haskell and Noui-Mehidi, 1991) and the χ
2
statistic (Belson, 1959,
Hart, 1984, Mingers, 1987, Zhou and Dillon, 1991, White and Liu, 1994) are some other
distance-based measures that have been used for tree induction. Though the Kolmogorov-
Smirnoff distance was originally proposed for tree induction in two-class problems
(Friedman, 1977, Rounds, 1980), it was subsequently extended to multiclass domains
(Haskell and Noui-Mehidi, 1991) Class separation-based metrics developed in the ma-
chine learning literature (Fayyad and Irani, 1992a, Zhengou and Yan, 1993) are also dis-
tance measures. A relatively simplistic method for estimating class separation, which
assumes that the values of each feature follow a Gaussian distribution in each class, was
used for tree construction in (Luo, Scherp and Lanzo, 1987).
Rules derived from dependence measures: These measure the statistical dependence
between two random variables. All dependence-based measures can be interpreted as
belonging to one of the above two categories (Ben-Bassat, 1987).
There exist many attribute selection criteria that do not clearly belong to any category in
Ben Bassat’s taxonomy. Gleser and Collen (1972) and Talmon (1986) used a combination
of mutual information and χ
2
measures. They first measured the gain in average mutual
information I(T
i
) due to a new split T
i
, and then quantified the probability P (I(T
i
)) that
this gain is due to chance, using χ
2
tables. The split that minimized P (I(T
i
)) was chosen by
these methods. A permutation statistic was used for univariate tree construction for 2-class
problems in (Li and Dubes, 1986). The main advantage of this statistic is that, unlike most
of the other measures, its distribution is independent of the number of training instances.
As will be seen in Section 4, this property provides a natural measure of when to stop tree
growth.
Measures that use the activity of an attribute have been explored for tree construction
(Moret, Thomason and Gonzalez, 1980, Miyakawa, 1989). The activity of a variable is
equaltothe testing cost of the variabletimesthea priori probability that it will be tested. The
computationalrequirements forcomputingactivityare thesameas those fortheinformation-
based measures. Quinlan and Rivest (1989) suggested the use of Risannen’s minimum
description length (Risannen, 1989) for deciding which splits to prefer over others and also
for pruning. Kalkanis (1993) pointed out that measures like information gain and Gini
index are all concave (i.e., they never report a worse goodness value after trying a split than
before splitting), so there is no natural way of assessing where to stop further expansion
of a node. As a remedy, Kalkanis suggested the use of the upper bounds in the confidence
intervals for the misclassification error as an attribute selection criterion.
10
Thetotal number of misclassified pointshasbeen exploredas a selection criterion by many
authors. Two examples are Heath’s sum minority (Heath, Kasif and Salzberg, 1993b) and