Intermediate Decision Trees

1 Introduction

Numerous decision tree pruning methods have been de­ veloped to reduce decision tree error due to overfitting on the part of the decision tree induction method [Mingers, 1989]. Of course, as Schaffer [1993; 1994] emphasizes, no one pruning method can improve the performance of decision tree induction on all domains. However, certain pruning methods can improve performance on certain domains. Although this paper presents results indicat­ ing the possibility of yet another decision tree pruning method, the results also indicate in which domains such a pruning method might be useful.

The perspective on which these results are based is the intermediate decision tree. Section 3 defines the inter­ mediate decision tree, but, in general, an intermediate decision tree is one of the sequence of subtrees gener­ ated using a breadth-first traversal of a full decision tree (i.e., a decision tree whose leaf nodes contain examples of one class) . Previous results have shown that the inter­ mediate decision tree compares favorably to other prun­ ing methods [Holder, 1992a], and intermediate learned concepts in general address overfitting issues in both inductive and speedup learning [Holder , 1990; 1992b; Holder and Chaudhry, 1993] . The main result of this paper is that the best intermediate tree of a full decision tree is often better (less error) than the pruned tree. The suggested pruning strategy would be to find the number of splits leading to this minimum-error intermediate de­ cision tree. A pre-pruning strategy of performing just that number of splits would produce a pruned decision tree without the need to first generate the full tree.

At one extreme to this approach, Holte [1993] suggests that the smallest intermediate decision tree consisting of one split performs well in comparison to a larger decision tree. However, Elomaa [1994] qualifies Holte's results by showing the small difference between C4 .5 trees and one-split trees is significant in favor of the C4.5 trees. Elomaa further points out that in some domains sim­ ple classifiers will never outperform a multilevel decision tree. Exhaustive tests run by Murphy and Pazzani [1994] indicate that the smallest consistent decision trees have more error than slightly larger consistent trees. Weiss and Indurkhya [1994] conclude that with at least 100 examples, their cross-validation cost-complexity pruning method outperforms no pruning. Thus, although pruned decision trees clearly compare favorable to full decision trees, there is no indication that a particular level of tree complexity will prevail.

The results presented in this paper deal exclusively with decision trees produced by the C4.5 program [Quin­ lan, 1992]; therefore, Section 2 briefly summarizes the properties of this program. Section 3 discusses the inter­ mediate decision tree in detail. Section 4 presents the ex­ perimental results based on a large sampling of the Uni­ versity of California, Irvine Machine Learning Database Repository [Murphy and Aha, 1994]. The appendices describe these databases and show a sample of the ex­ perimental results. Section 5 considers specific hypothe­ ses regarding the performance of intermediate decision trees as compared to C4.5-pruned trees, derives specific conditions underwhich intermediate decision trees per­ form best, and describes the implied pruning strategy. Section 6 concludes with directions for future work .

2 Decision Tree Induction

The method of decision tree induction used throughout this paper follows the method employed by C4.5 [Quin­ lan, 1992]. C4.5 uses the standard recursive splitting technique to produce a decision tree whose leaf nodes contain training examples of one class. If a split branch yields a node with no training examples, then this node is replaced by a leaf node whose classification is the ma­ jority class of the parent node. If a node with examples from more than one class cannot be split further, then this node is replaced by a leaf node whose classification is the majority class of the examples at this node.

C4.5 uses the gain ratio criterion for selecting the test attribute at each non-leaf node. A continuous attribute A is split based on the best test A ::; T, where T is one of the values appearing in the examples. Examples with unknown values for an attribute are distributed across all values and weighted according to the frequency of the known values in the examples. Classification of ex­ amples with unknown values is treated similarly, where the class is based on the maximum sum of the weights of the classes in the leaf nodes reached by the example. Although C4.5 is capable of splitting based on subsets of attribute values, this feature was not utilized in the experiments.

C4.5 employs two types of pruning. During tree con­ struction C4.5 requires that any split result in at least two branches having a minimum number weight MW of examples. The default value of MW is 2, but can be changed by a program option. Larger values of MW help prevent overfitting of noisy data. The main post­ pruning strategy used in C4.5 is a form of pessimistic pruning in which a subtree's error is estimated based on the binomial probability distribution of E errors occur­ ring within N trials with a confidence factor CF. The default value of CF is 0.25, but can be changed by a program option. Smaller values of C F tighten the er­ ror estimate and increase the amount of pruning. In our experiments the values of MW and CF are tuned au­ tomatically using a hill-climbing approach described in Section 4.

3 Intermediate Decision Trees

An intermediate decision tree (IDT) of a decision tree is any subtree in the sequence of subtrees generated from a breadth-first traversal of the internal nodes (splits) of the decision tree. For example, Figure la-d depicts the ordered sequence of IDTs for the decision tree in Fig­ ure le.

Figure 2 reveals the motivation for the breadth-first traversal. The figure depicts typical error curves that plot the error of different sequences of IDTs for a deci­ sion tree whose final error corresponds to the rightmost point on the curve. 1 The best-first traversal orders the splits based on information gain. Both the depth-first and best-first traversals indicate high error until a major­ ity of the splits have been performed. The breadth-first traversal, however, quickly achieves a low error, which gradually ascends to the final error level. This behavior of the error curves is typical for many domains. The spe­ cific behavior in which the minimum of the breadth-first traversal is less than the final error is the motivation for our interest in intermediate decision trees.

1 These particular curves come from the DNF2 domain in [Pagallo and Haussler, 1990] .

4 Experiments

In order to evaluate the performance of intermediate trees, an extensive empirical investigation was performed using the decision tree induction program C4.5 Release 6.0 [Quinlan, 1992] on 66 databases from the UCI Ma­ chine Learning Databases Repository [Murphy and Aha, 1994]. Appendix A describes the databases.

Four different trees were considered for comparison: the full tree FT (no post-pruning), the pruned tree PT, the best (lowest error) intermediate tree of the full tree IFT, and the best intermediate tree of the pruned tree IPT. Experiments measured the classification error and number of splits for each tree averaged over 50 trials each using two-thirds training and one-third testing examples randomly sampled without replacement. Four different experiments were run, each attempting to minimize the error for a different tree.

A hill-climbing parameter tuner accomplished the minimization by tuning the MW and C F parameters in order to minimize the average test-set error for one of the four tree types. Starting from the default values (MW = 2, CF = 0.25), the tuner measures the aver­ age error (over 50 trials) for MW ± 1 and CF ± 0.05. If none of the four new parameter settings improve the error, then the search terminates. Otherwise, the search continues from the best new parameter setting. The re­ sulting optimized trees are subsequently referred to as FTopt, PT opt, IFT opt and IPTopt. Although the opti­ mized trees consider the test set to tune M W and C F, these trees are used only to indicate what is possible. The test set is not considered during the generation of the other trees or during the pruning phase.

In addition to measuring the average error and num­ ber of splits for each of the four tree types, the experi­ ment also measured the difference between the error and number of splits for the different pairwise combinations of trees. A one-sided, upper-tailed, matched-pairs test measured the significance of the differences. Subsequent mention of "significantly less" or "significantly greater" implies a significance level of 0.05 or less (i .e., the prob­ ability that the difference is significant is at lea<>t 0.95) .

The results are too numerous to completely tabulate in this paper, but Appendix B tabulates a sample of the experimental results when optimizing the pruned tree.

5 Discussion

Many conclusions can be drawn from the experimental results in terms of the performance of intermediate de­ cision trees, the types of databases for which they are useful, and the trees' role in a pruning strategy.

5.1 Hypotheses

Following is a series of hypotheses drawn from the experi­ mental results. The evidence indicates that intermediate decision trees outperform pruned trees in a majority of the databases.

Hypothesis 1: IFT has less error than PT.

Evidence 1: The results shown in Appendix B indicate that IFT has significantly less error than PTopt in 46/66 databases. PT opt has significantly less error than IFT in 5/66 databases. Results not shown indicate that IFTopt has significantly less error than PT in 52/66 databases, and PT has significantly less error than 1FT opt in 1/66 databases.

Hypothesis 2: IFT has less error than IPT.

Evidence 2: IFT has significantly less error than the IPTopt in 20/66 databases. IPTopt has significantly less error than IFT in 12/66 databases. IFTopt has signifi­ cantly less error than IPT in 32/66 databases. IPT has significantly less error than IFT opt in 7/66 databases.

Hypothesis 3: IPT has less error than FT.

Evidence 3: IPT has significantly less error than FT opt in 40/66 databases. FT opt has significantly less error than IPT in 5/66 databases. IPTopt has significantly less error than FT in 49/66 databases. FT has significantly less error than IPT opt in 4/66 databases.

Hypothesis 4: PT has less error than FT.

Evidence 4: PT has significantly less error than FT opt 27/66 databases. FT opt has significantly less error than PT in 10/66 databases. PTopt has significantly less error than FT in 32/66 databases. FT has significantly less error than PT opt in 7/66 databases.

Hypothesis 5: IFT has less error than FT.

Evidence 5: IFT has significantly less error than FT opt in 54/66 databases. 1FT opt has significantly less error than FT in 58/66 databases. IFT never has greater error than FT.

Hypothesis 6: IPT has less error than PT.

Evidence 6: IPT has significantly less error than PT opt in 53/66 databases. IPT opt has significantly less error than PT in 53/66 databases. IPT never has greater error than PT.

Based on the evidence, IFT performs better than PT in a majority of the databases, indicating that intermedi­ ate trees deserve attention when attempting to minimize the error of a decision tree. Furthermore, IPT performs better than PT in a majority of the databases, indicat­ ing that the pessimistic post-pruning used in C4.5 still has room for improvement . IFT tends to outperform IPT, indicating that a intermediate-tree-based pruning strategy should consider intermediate trees of the full (unpruned) tree instead of intermediates of the pruned tree. Also, the superiority of IFT over FT indicates that the breadth-first ordering is capturing a minimum in the error curve less than the error for both full and pruned trees.

Similar results measuring the number of splits indicate that the IFT has significantly fewer splits than FT, but significantly more splits than IPT. Results comparing the number of splits between 1FT and PT are inconclu­ sive. Thus, although 1FT has less error than PT and IPT, this gain comes with an increased number of splits.

5.2 Database Properties

Due to the large number of databases included in this study, we can attempt to discern patterns in the prop­ erties of databases in which the intermediate decision tree performs best. Specifically, we used C4.5 to pro­ duce rules governing the database properties from Ta­ ble 2 after labeling each database as a positive or nega­ tive example of the hypothesis. Specifically, databases in which 1FT had significantly less error than PT opt were labeled as positive examples; the remaining databases were labeled ne~ative . Using these examples, the C4 .5 rule generator lQuinlan, 1992] produced the following rules (the numbers to the right of each rule indicate the correct/incorrect classifications):

(Size > 23) & (Error > 0.027) rightarrow + (41/1) Default--++

These rules correctly classify 60/66 databases, where the errors consisted of one false positive and five false negatives. The last rule, describing 42/66 databases sug­ gests that 1FT has less error than PT for reasonable­ size databases in which more than 2.7% of the exam­ ples do not belong to the majority class. Verification of the accuracy of these rules requires application to other databases and is left for future work.

5.3 IDT-Based Pruning

The benefits of the intermediate decision tree (IDT) can be utilized in a cross-validation pruning method similar to that employed by Weiss and Indurkhya [1994] . Weiss and Indurkhya use cross-validation to empirically deter­ mine the best cost-complexity tradeoff for pruning the decision tree. The same method can be used to empir­ ically determine the number of splits corresponding to the best IDT.

Specifically, given a training and testing set, divide the training set into k disjoint subsets. For each subset i, generate a decision tree using the other k-1 subsets and prune back the tree in a reverse breadth-first order until the error on subset i is minimized. Record the number of splits made in this intermediate tree. Repeat this procedure for each of the k subsets, and determine the average number of splits for the best IDT. Then, generate a new decision tree using the entire training set, but only perform the number of splits (in breadth-first order) as determined by the cross-validation procedure.

Unfortunately, initial evaluation of this IDT-based pruning strategy shows that the C4.5 pruning outper­ forms IDT pruning in a majority of the databases. How­ ever, a closer look at the results reveals that IDT pruning consistently underestimates the number of splits needed to reach the minimum error of the intermediate deci­ sion tree. Further evaluation of modifications to this IDT-based method are necessary to develop a better­ performing pruner, but this is left to future work.

6 Conclusions

An extensive empirical study has revealed that the best intermediate decision tree outperforms the pruned tree produced by C4.5 in a majority of the databases avail­ able from the UCI repository. The larger number (66) of databases considered in this study allowed the detection of specific patterns in the database properties for which the intermediate decision tree will perform better than the pruned tree. Therefore, a pruning strategy based on finding the best intermediate decision tree (i.e., num­ ber of splits leading to this intermediate decision tree in a breadth-first order) may outperform current pruning strategies in databases satisfying the detected patterns. Further experimentation is required to verify this hy­ pothesis.

The relationships found between database properties and induction strategies are rare in the literature, and more work here will be of great benefit to the under­ standing of decision tree induction. Specifically, these relationships need to be tested on artificial databases de­ signed to verify and refine the patterns. The use of the C4.5 pruning parameter optimizer provides further infor­ mation from which to discern patterns between database properties and proper parameter settings.

No one inductive strategy will perform well on all databases. However, continued derivation and verifica­ tion of relationships between database properties and induction strategies will lead to improved guidelines for selecting the proper strategy.

A Databases

All databases used in the experiments were taken from the UCI Repository of Machine Learning Databases [Murphy and Aha, 1994]. Table 1 lists the 66 databases and the corresponding label used for the database throughout the paper. Although many more than 66 databases are available in the repository, the remainder were not included because they either were domain the­ ories, were data generators, had continuous class values, or (in the one case of David Slate's letter recognition database) took too long to process.

Some of the databases underwent minor modifications for use with C4.5. The ANN database consists of the combined examples from the data and test files, and at­ tributes with missing values for all examples were ig­ nored. For IMP, the Symboling attribute was used as the class: 1 if Symboling :::; 0, 2 if Symboling > 0. For BCR, attributes Age, Tumor-Size, Inv-Nodes and Deg­ Malig were changed to continuous.

Version 1 of the bridges (BR1-BR5) databases was used. In each database the Identifier attribute was ig­ nored, values of Y for the River attribute were changed to?, and fractional values of the Location attribute were rounded to the nearest integer. The five databases (BR1BR5) use attributes 2-8 and class attributes t-or-d, ma­ terial, span, rei-/ and type, respectively. Examples with missing class values (? or NIL) were deleted.

For HTC, class values of 2, 3 and 4 were changed to 1 to yield a two-class problem. The HOR database consists of the examples from both the training and testing files. Attribute 24 was used as the class attribute, attributes 3, 2.5, 26, 27 and 28 were ignored, values of 9 for the Age attribute were changed to 2, and values of 3 for the Capillary Refill Time attribute were changed to 2.

The FLR database used the flare2. data file. The three class attributes describing which type of flare ap­ peared (if any) were reduced to one binary class attribute as to whether any flare occurred. In databases THO-TH3 and TH5, attribute 28 was ignored, because all values were missing.

For the sponge (SPG) database, attribute 38 (L.Papilas) was used as the class attribute for its even distribution and minimal dependence on other at­ tributes. Attribute 1 (Sponge_Name) was ignored, as was attribute 37 (L.Numero_De_Papilas) for its depen­ dence on the class attribute. Attributes 7-28 were typed continuous, and case 65's illegal value of SLTIPO for attribute 10 was set to LTIPO.

The Wisconsin breast cancer database (BCW) was originally obtained from the University of Wisconsin Hospitals in Madison thanks to Dr. William H. Wol­ berg [Mangasarian and Wolberg, 1990). The breast can­ cer (BCR), lymphography (LYM) and primary tumor (PRI) databases were originally obtained from the U ni­ versity Medical Centre, Institute of Oncology, Ljubljana, Yugoslavia thanks to M. Zwitter and M. Soklic. The Cleveland heart disease database (HTC) was originally obtained from the Cleveland Clinic Foundation thanks to Dr. Robert Detrano.

Table 2lists the properties of the individual databases. The number in parentheses next to the Database label is the number of different class values appearing in the data. Size is the total number of available examples. Error is the classification error on all examples by guess­ ing the most frequent class appearing in the data. The next ten columns describe the non-class attributes of the database; empty entries indicate zeros in the first eight of these columns. Cont is the number of continuous at­ tributes. The next seven columns show the number of discrete attributes with the indicated number of differ­ ent (non-missing) values appearing in the data. Miss is the number of attributes containing missing values in the data, and Tot is the total number of attributes.

B Sample of Experimental Results

Experimental results for the 66 databases were gener­ ated for the optimization of the full tree, pruned tree, intermediate full tree and intermediate pruned tree. The number of splits used for each tree was also recorded, but only the error was optimized. The last three columns of Table 2 show a sample of the results when optimizing the pruned tree produced by C4.5 according to the hillclimbing optimization strategy described in Section 4) . The first two columns show the average error and stan­ dard deviation for 50 trials using two-thirds training and one-third testing sampled without replacement. The fi­ nal column shows the difference between the error of IFT and PTopt. The significance level of a one-sided, upper-tailed, matched-pairs test is shown in parenthe­ ses, where a value of 0.05 or less indicates a significant positive difference, and a value of 0.95 or more indicates a significant negative difference.