Decision Tree Grafting

1 Introduction

Decision tree pruning [Breiman et al., 1984; Quinlan, 1987] is a widely accepted method for post-processing decision trees. Pruning removes nodes from an inferred decision tree. It has been demonstrated to improve the predictive accuracy of inferred decision trees in a wide variety of domains [Breiman et al., 1984; Quinlan, 1987]. A classifier can be viewed as partitioning an instance space. Each partition associates a set of possible objects with a class. Pruning reduces the number of partitions imposed on an instance space by a decision tree.

In contrast to pruning, a number of recent studies have suggested that predictive accuracy may also be improved by more complex partitioning of an instance space than that formed by standard decision tree induction. Pre­ dictive accuracy has been improved both by:

• grafting additional leaves [Webb, 1996]; and
• developing multiple classifiers that are used in conjunction to classify objects [Ali et al., 1994; Breiman, 1996; Dietterich and Bakiri, 1994; Kwok and Carter, 1990; Oliver and Hand, 1995; Nock and Gascuel, 1995; Schapire, 1990; Wolpert, 1992] .

The latter approaches lead to complex implicit parti­ tioning of the instance space through resolution of the conflicts between the individual classifiers' partitions.

Direct grafting forms an explicit representation of the final partitioning of the instance space by adding new branches to a decision tree after the completion of con­ ventional decision tree induction.

The increase in predictive accuracy resulting from more complex partitioning of the instance space can be explained as follows. Conventional machine learn­ ing techniques consider only areas of the instance space directly occupied by training examples. Areas of the in­ stance space that are not occupied by training examples are assigned to partitions ·as a side-effect of partition­ ing occupied areas. This occurs without consideration of the available evidence relating to appropriate parti­ tioning of these regions. Explicit examination of such areas may provide evidence as to the most likely class for previously unseen objects that fall therein. If there is such evidence and the appropriate classification differs from that currently assigned to the region, a new parti­ tion can be formed. This is achieved by grafting a new leaf onto the tree.

The use of multiple classifiers obtains this result in a more indirect manner. Each classifier will form differ­ ent partitions. Regions occupied by no training exam­ ples may fall within different partitions for each classifier. The strength of evidence associated with that region for each classifier can be evaluated and a most highly sup­ ported prediction made.

Consider an abstract example (Figure 1). This illus­ trates a simple instance space occupied by objects of three classes ( *, · and o). 0 b jects are described by two attributes A and B. These attributes define a two di­ mensional instance space. An instance of unknown class is also depicted (?) . On visual inspection it is plausible that this unknown case belongs to class o as it is close to a number of instances of this class. However, most deci­ sion tree learners would create a partition that assigned this point to class *· Figure 2 indicates the partitions created by C4.5 [Quinlan, 1993], a pre-eminent exam­ ple of a decision tree learner. In contrast, it is plausi­ ble to assign the shaded region to class o. The C4.5x [Webb, 1996] grafting procedure identifies such regions and grafts new leaves onto the decision tree to form ap­ propriate new partitions of the instance space.

The primary focus of Webb's [1996] grafting research was to examine the effect of complexity on predictive accuracy. Consequently, C4.5x was designed to control other potential confounding factors, specifically resub­ stitution performance. These measures could reduce the predictive accuracy of the inferred trees [Webb, 1996].

This paper seeks to extend Webb's [1996] grafting re­ search by developing grafting techniques aimed to maxi­ mize predictive accuracy. Four key changes to the C4.5x approach are presented: allowing grafting to alter resub­ stitution performance; the ordered addition of multiple new branches in the place of a single original leaf; the use of a significance test to restrict the selection of new branches; and allowing grafting within leaves occupied by no training examples.

Evaluation on twenty representative learning domains demonstrates that the application of the new techniques frequently results in the induction of decision trees with improved predictive accuracy.

2 Techniques for decision tree grafting

The new post-processor, C4.5+, operates by examining each leaf l of an inferred tree in turn. It climbs the tree examining each ancestor node n for evidence supporting alternative partitions within l. This evidence is obtained by considering cuts that could have been employed at n, that would provide stronger evidence in support of a particular class . dominating a region within l than that provided by the distribution of objects at l. In doing so, it only considers cuts that fall within the range of values for an attribute that can reach l. It also excludes from consideration cuts that would reclassify an object at l that is correctly classified by l. A set of such cuts are assembled. These are used to graft new branches and leaves onto the decision tree between l and its par­ ent. At present there is no consideration of potential new branches on discrete valued attributes, although in principle this should be straight forward.

The evidence in support of each cut is evaluated us­ ing a Laplacian accuracy estimate [Niblett and Bratko, 1 986]. Because each leaf relates to a binary classification (an object belongs to the class in question or does not) , the binary form of Laplace is used. For threshold t on attribute a at leaf l, the evidence in support of labeling the partition below t with class x is the maximum value for an ancestor node n of l for the formula ~$~ where T is the number of objects at n for which min < a :::; t; and Pis the number of those objects that belong to class x . Calculation of the evidence in support of labeling a par­ tition above a threshold differs only in that the objects for which t < a :::; max are instead considered. Where l contains no training objects, it is treated as containing all objects at its parent for the sake of these calculations.

The best such :::; and > cut for each attribute is de­ termined. A list of all these cuts is created, C.

The strength of evidence in support of the current la­ beling of l is calculated using the Laplace accuracy esti­ mate considering the objects at l, where Tis the number of objects at l and Pis the number of those objects that belong to the class with which l is labeled.

Any cuts that do not have greater support than that for l are removed from C. A binomial test is also em­ ployed to further remove from C cuts for which there is insufficient evidence that the resulting leaf is drawn from a better distribution of examples than the original leaf (see Step 3 of the algorithm presented in Appendix A). C is sorted from the cut with highest support to that with lowest support .. Trailing elements of C that support the creation of new leaves for the same class as l are deleted as they will not alter the tree's classifications. Then the cuts in C are inserted in order creating a sequence of new branches and leaves between l's parent and l.

This approach ensures that all new partitions define true regions. That is, for any attribute a and value v it is not possible to partition on a :::; v unless it is possible for both objects from the domain with values of a greater than v and objects with values less than or equal to v to reach the node being partitioned (even though it is pos­ sible that no objects from the training set will fall within the new partition). In particular, this ensures that new cuts are not simple duplications of existing cuts at an­ cestors to the current node. Thus, every modification adds non-redundant complexity to the tree.

This algorithm is presented in Appendix A. C4.5+ differs from C4.5x [Webb, 1996] by

1. adding multiple leaves at each original leaf - C4.5x added the new leaf with maximal support only;

1. using a binomial test to prevent the addition of leaves for which there is insufficient evidence that the leaf is drawn from a better distribution of ex­ amples (Algorithm Step 3) ;
2. allowing new leaves to reclassify training examples (although only if those examples are misclassified by the original leaf); and
3. using the training examples at the parent node when a leaf has no training examples - C4.5x did not allow grafting additional leaves onto an existing leaf that covers no training examples.

Adding multiple leaves can be expected to be bene­ ficial as every piece of additional evidence can be uti­ lized. However, initial experimentation suggested that adding leaves for which the level of additional support was marginal, while often beneficial, could also often re­ duce predictive accuracy. The use of a binomial test to evaluate the comparative strength of support for a new leaf is intended to reduce the risk of adding leaves that appear better by chance alone.

Allowing new leaves to reclassify training examples has intuitive appeal. If there is evidence that a region of the instance space should be associated with a given class, the existence of an object of that class in that region should not prevent a system from forming that associa­ tion. For example, the object at A = 4, B = 4 in Figure 1 should not stop C4.5+ from relabeling that region as be­ longing to ·· C4.5x prohibited such grafting actions to avoid experimental confounds arising from differing re­ substitution accuracy between treatments [Webb, 1996].

The training examples from the parent node are used for leaves that cover no training examples, as the parent node provides the best available evidence' of the class dis­ tribution in the neighborhood of the leaf. Such leaves are prime candidates for modification as the local evidence in support of any given class assignment is unlikely to be strong.

3 Example

C4.5 creates the following decision tree for the exam­ ple training set illustrated in Figure 1. The partitions created by this tree are illustrated in Figure 2.

A > 7 : o (10.0) A <= 7 : I A <= 2 * (4.0) I A > 2 : I I B <= 5 * (5.0/1.0) I I B > 5 : · (11.0)

C4.5 has placed cuts on A at values 7 and 2. A > 7 is assigned to class o and A ~ 2 is assigned to *. In the region for 2 < A ~ 7, a cut has been placed at B = 5. B ~ 5 has been assigned to * and B > 5 to ·. The figures in brackets indicate the numbers of training examples at each leaf and, where applicable, the number of these that are misclassified.

C4.5+ examines each of the 4 leaves in turn. At each leaf it climbs the tree looking for cuts that would not reclassify any training examples correctly classified at the leaf. The leaf for A > 7 has only the root as an ancestor. No better cuts can be found.

To process the leaf for A ~ 2 the system climbs to its parent node, at which no better cuts can be found, and then to the root. At the root, all values are considered on both attributes that are greater or less than those of the (in all cases correctly classified) training examples from the leaf. There are no training examples with lower values on A or with greater values on B than those of the examples at the leaf. Values on A greater than those at the leaf are not considered as such a cut imposed at the leaf would define a new region of zero volume. All values are considered on B less than 6, the lowest value for an example at the leaf. A cut at 5 results in a partition containing 1 ·, 4 * and 9 o. The Laplace accuracy estimate for the region B ~ 5 for the majority class o is 1 9 4 "t 1 2 = 0.625. The class distributions and accuracy estimates of the remaining possible cuts are:

The best of these cuts is at value 3 with accuracy esti­ mate 0.909. The original leaf is occupied by four points all of which are correctly classified resulting in an accu­ racy estimate of lli = 0.833. The probability of ob­ taining the class distribution (9 positive and 0 negative) given the estimated accuracy for the original leaf (0.833) is less than 0.05, so the selected cut is grafted between the original leaf and its parent. The dominating class ( o) for the new region in the ancestor node from which the evidence was obtained is assigned to the new leaf.

Next the system considers the leaf below the branch B ~ 5. Theaccuracyestimateatthisleafis tH = 0.714. At the parent node (the node reached by the branches A~ 7 then A> 2), a cut at A= 5 creates a leaf contain­ ing 10 · and no examples of other classes. The resulting accuracy estimate is 0.917. The probability of obtaining this distribution given the estimated accuracy for the leaf is less than 0.05, so the new cut is accepted. Another cut, at B = 3, is found at the root . The partition formed by this cut contains 9 o and no other examples. The re­ sulting accuracy estimate is lli = 0.909 The probability of obtaining this class distribution given the estimated accuracy at the original leaf is also less than 0.05. In consequence, this cut is also accepted. Other potential ~ cuts on these attributes receive lower accuracy esti­ mates and so are discarded. Branches for the two cuts are grafted in order of their accuracy estimate.

No appropriate new cuts can be found for the leaf below B > 5.

The partitions imposed by the resulting tree are illus­ trated in Figure 3. The new partitions labeled a and c are assigned too and partition b to *· While partition a may have less intuitive support than b or c, the support for any classification within this region is weak and the class <> is at least as plausible as either alternative.

4 Experimental evaluation

The postprocessing algorithm was implemented as an extension to C4.5 Release 8 [Quinlan, 1993].

It was evaluated by application to twenty represen­ tative learning tasks from the UCI Machine Learning Repository. These datasets are described in Table 1. They show considerable diversity in size, number of classes, and type and number of attributes, within there­ striction that all contain continuous attributes, as these are the only attributes on which grafting is implemented.

Three variants of the system were tested. All included the full system as described in Appendix A. None was C4.5 release 8 with no post-processing. One added at most one new leaf to each existing leaf. This was achieved by discarding all but the highest valued tuple after Step 3.

C4.5 employs a two stage process to infer decision trees from data. An initial unpruned tree is created. This is then simplified to produce a pruned tree. Each variant of the post-processing algorithm was used to post-process both pruned and unpruned trees produced by C4.5.

Ten stratified ten-fold cross validation experi~ents were performed for each data set. In each of these ex­ periments, the data set was divided into ten subsets of as close as possible to equal size with as close as possi­ ble to identical class distributions. For each subset, each treatment was applied to learn a decision tree from all the remaining subsets, and then applied to predict the class of each object in the selected subset.

Table 2 presents the predictive accuracy obtained for each treatment in these experiments. The mean percent­ age error over all one hundred sets of predictions is pre­ sented for each treatment. Two summary lines present for each of the other treatments

• a win-loss summary of the number of data sets for which the mean error is lower or higher than that of all; and
• the one-tailed binomial probability of obtaining such a win-loss result by chance.

It can be seen that all has lower error than none signifi­ cantly (at the 0.05 level) more often both for pruned and unpruned trees. However, the advantage to all over one is not significant at the 0.05 level.

The magnitude of the changes also differs greatly. The largest increase in error resulting from the addition of all grafts is 1.0% for the iris data. The largest reduction in error is 2.9% for unpruned trees on the hepatitis data. The postprocessing of pruned trees results in reductions of 1.0% or more for seven of the twenty datasets.

It is interesting to compare the performance of post­ processing both pruned and unpruned trees. Pruning then grafting produces lower error than grafting alone for twelve data sets whereas the reverse is true for only three. A one-tailed binomial sign test reveals that this difference is significant at the 0.05 level (p = 0.017). It appears that both pruning and grafting have a valuable role to play in decision tree induction. It is possible that this results from the abilities of pruning to identify parti­ tions where the local information is insufficient to create sensible sub-partitions and of grafting to use non-local information to then create suitable sub-partitions. The reduction in resubstitution error brought about by graft­ ing (Table 3) lends some support to this explanation.

Table 4 presents the number of nodes obtained by each treatment employing the same format as in Ta­ ble 2. Adding all nodes produces more complex trees than either of the other treatments for every data set.

5 Conclusions

The experimental results suggest that C4.5+ is success­ ful in identifying regions of the instance space occupied by no training examples for which initial tree induc­ tion has made poor class choices. Grafting new nodes to correct these poor class assignments can significantly improve the predictive accuracy of the inferred decision trees. The extension of the techniques to graft multiple new branches at each leaf of the original tree led to more reductions than increases in error when compared to the C4.5x technique of adding at most one new branch per leaf. However, the frequency with which the addition of more branches increases error and the failure to obtain a statistically significant advantage in this respect sug­ gests that there is room for further improvement in the filtering that is used to select which of the potential new branches should be grafted to the tree.

Research on grafting to date has examined only the addition of tests on continuous attributes. The tech­ niques should extend in a straight forward manner to dis­ crete attributes. The development of appropriate graft­ ing techniques for discrete attributes is a promising di­ rection for future research.

The application of both grafting and pruning results in lower average error significantly more often than does grafting alone. It is possible that this is due to the abil­ ity of pruning to identify partitions of the instance space where the local information is insufficient to create sen­ sible sub-partitions. Grafting can then use non-local in­ formation to generate appropriate sub-partitions.

However, many benefits have counterweighing costs and grafting is no exception. The increase in accuracy obtained through grafting is often modest. This is ob­ tained at the expense of large increases in decision tree complexity. In applications where classifier complexity is a significant factor, this trade-off deserves careful con­ sideration before grafting is employed.

It has been argued herein that grafting has a simi­ lar effect to the induction and application of multiple classifiers, with the difference that grafting incorporates its complex instance space partitioning into a single ex­ plicit decision tree instead of requiring the resolution of multiple distinct partitionings to determine the ultimate underlying partitioning to be applied. Exploration of this hypothesized relationship provides further promis­ ing avenues for future research.

A Algorithm

Let cases(n) denote the set of all training examples that can reach node n, unless there are no such examples in which case cases(n) shall denote the set of all training examples that can reach the parent of n.

Let value(a,x) denote the value of attribute a for training example x.

Let pos(X, c) denote the number of objects of class c in the set of training examples X .

Let class(x) denote the class of object x.

Let Laplace( X, c) = poi~~~+l where X is a set of training examples, lXI is the number of training examples and cis a class.

Let upperlim(n, a) denote the minimum value of a cut con attribute a for an ancestor node x of n with respect to which n lies below the a ~ c branch of x. If there is no such cut, upperlim(n,a) = oo. This determines an upper bound on the values for a that may reach n .

Let lowerlim(n, a) denote the maximum value of a cut con attribute a for an ancestor node x of n with respect to which n lies below the a > c branch of x . If there is no such cut , lowerlim(n, a) = -oo. This determines a lower bound on the values for a that may reach n .

Let prob(x, n,p) be the probability of obtaining x or more positive objects in a random selection of n objects if the prob­ ability of selecting a positive object is p.

To post-process leaf l dominated by class c

1. Initialize to {} a set of tuples t representing potential cuts.
2. For each continuous attribute a
3. (a) Find values of
4. n: n is an ancestor of l v : 3x: x E cases(n) & v = value( a, x) & v ~ min(value(a,y): y E cases(l) & class(y) =c) & v > lowerlim(l, a) k: k is a class

that maximize C' = Laplace( { x : x E cases( n) & value( a, x) ~ v & value( a, x) > lowerlim(l, a)}, k).

• (b) Add to t the tuple (n, a, v, k, .C', ~)
• (c) Find values of
• n: n is an ancestor of l v : 3x : x E cases(n) & v = value(a, x) & v > max(value(a,y) : y E cases(l) & class(y) =c) & v ~ upperlim(l, a) k: k is a class

that maximize .C' = Laplace( {x : x E cases(n) & value( a, x) > v & value( a, x) :S upperlim(l, a)}, k).

• (d) Add tot the tuple (n,a,v,k,.C',>)
• Remove from t all tuples (n, a, v, k, .C, x) such that .C :S Laplace(cases(l), c) or prob(x, n, Laplace(cases(l), c)) ~ 0.05.
• Remove from t all tuples (n, a, v, c, .C, x) such that there is no tuple ( n', a', v', k', .C', x') such that k' I c & .C' < .C.
• For each (n, a, v, k, .C, x) in t ordered on L from highest to lowest value

If x is :S then

• (a) replace l with a node n with the test a :S v.
• (b) set the ~ branch for n to lead to a leaf for class k .
• (c) set the > branch for n to lead to l.

else (x must be >)

• (a) replace l with a node n with the test a :S v.
• (b) set the > branch for n to lead to a leaf for class k.
• (c) set the :S branch for n to lead to l.