Keep the Decision Tree and Estimate the Class Probabilities Using its Decision Boundary

1 Introduction

Decision Tree (DT) algorithms are very popular and widely used for classification purpose, since they provide relatively easily an intelligible model of the data, contrary to other learning methods. Intelligibility is a very desirable property in artificial intelligence, considering the interactions with the end-user, all the more when the end-user is an expert. On the other hand, the end-user of a classification system needs additional information rather than just the output class, in order to asses the result: This information consists generally in confusion matrix, accuracy, specific error rates (like specificity, sensitivity, likelihood ratios, including costs, which are com-

cision aid system, the most valuable information is the class membership probability. Unfortunately, DT can only provide piecewise constant estimates of the class posterior probabilities, since all the cases classified by a leaf share the same posterior probabilities. Moreover, as a consequence of their main objective, which is to separate the different classes, the raw estimate at the leaf is highly biased. On the contrary, methods that are highly suitable for probability estimate produce generally less intelligible models. A lot of work aims at improving the class probability estimate at the leaf: Smoothing methods, specialized trees, combined methods (decision tree combined with other algorithms), fuzzy methods, ensemble methods (see section 2). Actually, most of these methods

Stephan Bernard (2) (2) Cemagref, LISC F-63172 Aubiere, France stephan.bernard@cemagref.fr Guillaume Deffuant (2)

(2) Cemagref, LISC 63172 Aubiere, France

guillaume.deffuant@cemagref.fr

(except smoothing) induce a drastic change in the fundamental properties of the tree: Either the structure of the tree as a model is modified, or its main objective, or its intelligibility.

The method we propose here aims at improving the class probability estimate without modifying the tree itself, in order to preserve its intelligibility and other use. Besides the attributes of the cases, we consider a new feature, the distance from the decision boundary induced by the DT (the boundary of the inverse image of the different class labels). We propose to use this new feature (which can be seen as the margin of the DT) to estimate the posterior probabilities, as we expect the class membership probability to be closely related to the distance from the decision boundary. It is the case for other geometric methods, like Support Vector Machines (SVM). A SVM defines a unique hyperplane in the feature space to classify the data (in the original input space the corresponding decision boundary can be very complex). The distance from this hyperplane can be used to estimate the posterior probabilities, see [Platt, 2000] for the details in the two-class problem. In the case of DT, the decision boundary consists in several pieces of hyperplanes instead of a unique hyperplane. We propose to compute the distance to this decision boundary for the training cases. Adapting an idea from [Smyth et al., 1995], we then train a kernel-based density estimator (KDE), not on the attributes of the cases but on this single new feature.

The paper is organized as follows: Section 2 discusses related work on probability estimate for DT. Section 3 presents in detail the distance-based estimate of the posterior probabilities. Section 4 reports the experiment performed on the numerical databases of the UCI repository, the comparison between the distance-based method and smoothing methods. Section 5 discusses the use of geometrically defined subsets of the training set in order to enhance the probability estimate. We make further comments about the use of the distance in the concluding section.

2 Estimating Class Probabilities with a DT

Decision Trees (DT) posterior probabilities are piecewise constant over the leaves. They are also inaccurate. Thus they are of limited use (for ranking examples, or to evaluate the risk of the decision). This is the reason why a lot of work has been done to improve the accuracy of the posterior probabilities and to build better trees in this concern.

Traditional methods consist in smoothing the raw conditional probability estimate at the leaf pr (c|x) = kn , where k is the number of training cases of the class label classified by the leaf, and n is the total number of training cases classified by the leaf. The main smoothing method is the Laplace correction pL (and its variants like m-correction). The correction pL(c|x) = k+1 n+C , where C is the number of classes, shifts the probability toward the prior probability of the class ([Cestnik, 1990; Zadrozny and Elkan, 2001]). This improves the accuracy of the posterior probabilities and keep the tree structure unchanged, but the probabilities are still constant over the leaves. In order to bypass this problem, smoothing methods can be used on unpruned trees. The great number of leaves allows the tree to learn the posterior probability with more accuracy (see [Provost and Domingos, 2003]). The intelligibility of the model is most reduced in this case, so specialized building and pruning methods are developped for PET's (see for instance [Ferri and Hernandez, 2003]).

In order to produce smooth and case-variable estimate of the posterior probabilities, Kohavi [1996] deploys a Naive Bayes Classifier (NBC) at each leaf, using a specialized induction algorithm. Thus the partition of the space in NBTree is different from classical partition, since its objective is to better verify the conditional independance assumption at each leaf. In the same idea, Zang and Su [2004] use NBC to evaluate the choice of the attribute at each step. But the structure of the tree is essentialy different.

Other methods obtain case-variable estimates of the posterior probabilities by propagating a case through several paths at each node (mainly fuzzy methods like in [Umano et al., 1994] or in [Quinlan, 1993]; Or, more recently, [Ling and Yan, 2003]). These methods aim at managing the uncertainty both in the input and in the training database.

Smyth, Gray and Fayyad [1995] propose to keep the structure of the tree and to use a kernel-based estimate at each leaf. They consider all the training examples but use only the attributes involved in the path of the leaf. The dimension of the subspace is then at most the length of the path. But the resulting dimension is nevertheless far too high for this kind of technique and the method cannot be used in practice.

We propose here to reduce the dimension to 1, since KDE is very effective in very low dimensions. We preserve the structure of tree, and our method theoretically applies as soon as it is possible to define a metric on the input space.

3 Distance-based Probability Estimate for DT

3.1 Algebraic Distance as a New Feature

We consider an axis-parallel DT (ADT) operating on numerical data: Each test of the tree involves a unique attribute. We note Γ the decision boundary induced by the tree. Γ consists of several pieces of hyperplanes which are normal to the axes. We also assume that it is possible to define a metric on the input space, possibly with a cost or utility function.

Let x be a case, c(x) the class label assigned to x by the tree, d = d(x, Γ) the distance of x from the decision boundary Γ. The decision boundary Γ divides the input space into different areas (possibly not connected areas) which are labeled with the name of the class assigned by the tree.

By convention, in a two-class problem, we choose one class (the positive class) to orient Γ: If a case stands in the positive class area, its algebraic distance will be negative.

Definition 1 Algebraic distance to the DT (2-class problem)

The algebraic distance of x is h(x) = -d(x, Γ) if c(x) is the positive class c and h(x) = +d(x, Γ) otherwise.

This definition extends easily to multi-class problems. For each class c, we consider Γc, the decision boundary induced by the tree for class c: Γc is the inverse image of the class c area. (We have Γc ⊂ Γ).

Definition 2 Class-Algebraic distance to the DT

The c-algebraic distance measures the distance of a case to class c area. Actually, algebraic distance is a particular case of c-algebraic distance where c is the positive class.

These definitions apply to any decision tree. But in the case of axis-parallel DT (ADT) operating on numerical data, a very simple algorithm computes the algebraic distance (adapted from the distance algorithm in [Alvarez, 2004]). It consists in projecting the case x onto the set F of leaves f whose class label differs from c(x) (in a two class problem). In a multi-class problem, each class c is considered in turn. When c(x) = c, the set F contains the leaves whose labels differs from c; Otherwise it contains the leaves whose class label is c. The nearest projection gives the distance.

Algorithm 1 AlgebraicDistance(x,DT,c)

0. d =∞; 1. Gather the set F of leaves f whose class c(f) verifies: (c(f) Xor c(x)) = c; 2. For each f ∈ F do: { 3. compute pf(x) = projectionOntoLeaf(x,f); 4. compute df(x) = d(x, pf(x)); 5. if (df (x) < d) then d = df (x) } 6. Return hc(x) = -sign(c(x) = c) ∗ d Algorithm 2 projectionOntoLeaf(x,f = (Ti)i∈I) 1. y = x; 2. For i = 1 to size(I) do: { 3. if y doesn't verify the test Ti then yu = b } where Ti involves attribute u with threshold value b

1. Return y

The projection onto a leaf is straightforward in the case of ADT since the area classified by a leaf f is a hyper-rectangle defined by its tests. The complexity is in O(Nn) in the worst case where N is the number of tests of the tree and n the number of different attributes of the tree.

The distance to the decision boundary presents two main advantages, because it is a continuous function: it is relatively robust to the uncertainty of the value of the attributes for new cases, and to the noise in the training data, assuming that only the thresholds of the tests are modified (not the attributes).

3.2 Kernel Density Estimate (KDE) on the Algebraic Distance

Kernel-based density estimation is a non-parametric technique widely used for density estimation. It is constantly improved by researches on algorithms, on variable bandwidth and bandwidth selection (see [Venables and Ripley, 2002] for references).

Univariate KDE basically sums the contribution of each training case to the density via the kernel function K. To estimate the density f(x) given a sample M = {xi}i∈[1,n] , one computes ˆ f(x) = 1n ∑ni=1 1b K ( x-xi b ), where K is the kernel function and b the bandwidth (b can vary over M).

Many methods could be used in this framework to compute the distance-based kernel probability estimate of the class membership. (We could also use kernel regression estimate). We have used very basic KDE for simplicity.

We consider here the algebraic distance h(x) as the attribute on which the KDE is performed. So we compute the density estimate of the distribution of the algebraic distance, from the set of observations h(x), x ∈ S:

In order to estimate the conditional probabilities, we consider the set S of training cases and its subset Sc of cases such that c(x) = c. We estimate the density of the two populations: ˆ f the density estimate of the distribution of the algebraic distance to the decision boundary;

ˆ

fc, the density estimate of the distribution of the algebraic distance of points of class c.

ˆ

ˆ

f is computed on S and fc on Sc. We then derive from the Bayes rule, if ˆ p(c) estimates the prior probability of class c:

Definition 3 Distance-based kernel probability estimate

ˆ p (c|h(x)) is called the distance-based kernel (DK) probability estimate

The algorithm is straightforward. We note S the training set used to build the decision tree DT .

Algorithm 3 DistanceBasedProbEst(x,DT,c,S)

1. Compute the algebraic distance

y = h(x) = AlgebraicDistance(x, DT, c);

1. Compute the subset S(x) of S from which the probability density is estimated: Default value is S(x) = S;
2. Select Sc(x) = {x ∈ S(x), c(x) = c};
3. Compute ˆ f (y) = 1 nb ∑xi∈S(x) K ( y-h(xi) b ) ;
4. Compute ˆ fc(y) = 1 nb ∑xi∈Sc K ( y-h(xi) b ) ;
5. Compute and Return ˆ p (c|h(x)) from equation (2)

Several possibilities can be considered for the set S(x) used to compute the kernel density estimate, we discuss them in section 5. The simplest method consists in using the whole sample S. The algebraic distance is taken into account globally, without any other consideration concerning the location of the cases. We call the corresponding conditional probability estimate ˆ pg the global distance-based kernel (GDK) probability estimate. Figure 1 shows how the GDK probability estimate varies over a test sample, compared with the Laplace probability estimate which is piecewise constant.

4 Experimental Study

4.1 Design and Remarks

We have studied the distance-based kernel probability estimate on the databases of the UCI repository [Blake and Merz, 1998] that have numerical attributes only and no missing values. For simplicity we have treated here multi-class problems as 2-class problems. We generally chose as positive class the class (or a group of class) with the lowest frequency in the database.

For each database, we divided 100 bootstrap samples into separate training and test sets in the proportion 2/3 1/3, respecting the prior of the classes (estimated by their frequency in the total database). It is certainly not the best way to build accurate trees for unbalanced datasets or different error costs, but here we are not interested in building the most accurate trees, we just want to study the distance-based kernel probability estimate. For the same reason we grow trees with the default options of j48 (Weka's [Witten and Frank, 2000] implementation of C4.5) although in many cases different options would build better trees. For unpruned trees we disabled the collapsing function. We used Laplace correction smoothing method to correct the raw probability estimate at the leaf for pruned trees and unpruned trees. We also built NBTree on the same samples.

We used two different metrics in order to compute the distance from the decision boundary, the Min-Max (MM) metric and the standard (s) metric. Both metrics are defined with the basic information available on the data: An estimate of the range of each attribute i or an estimate of its mean Ei and of its standard deviation si. The new coordinate system is defined by (3).

The parameters of the standard metric are estimated on each training sample. (On each bootstrap sample for the Min-Max metric, to avoid multiple computation when an attribute is outside the range). In practice, the choice of the metric should be guided by the data source. (For instance, the accuracy of most sensors is a function of the range, therefore it suggests to use an adapted version of the Min-Max coordinate system.)

To compute the kernel density estimate of the algebraic distance we choose simplicity and used the standard algorithm available in R [Venables and Ripley, 2002] with default options, although the setting of KDE parameters (choice of the kernel, optimal bandwidth, etc.) or specialized algorithms (also available in some dedicated packages) would certainly give better results. We systematically used the default option except for the bandwidth selection, since it is inappropriate for using the Bayes rule in equation (2): We used the same bandwidth for ˆ f as for ˆ fc. We set it to a fraction τ of the range of the algebraic distance . This is the only parameter we used to control the KDE algorithm. More sophisticated methods could obviously be used but the Bayes rule in equation (2) should be reformulated if variable bandwidths are used.

4.2 Results for the Global Distance-based Kernel Probability Estimate

In order to compare our method with other methods of probability estimate, we used the AUC, the Area Under the Receiving Operator Characteristic (ROC) Curve (see [Bradley, 1997]). The AUC is widely use to assess the ranking ability of the tree. Although this method cannot distinguish between good scores and scores that are good probability estimates, it doesn't make any hypothesis on the true posterior probability, so it is useful when the true posterior probability are unknown (since it is clear that good probability estimates should produce on average better AUC). We also used Mean Squared Error and log-loss, although these methods make strong hypothesis on the true posterior probability.

Table 1 shows the difference of the AUC from global distance-based kernel (GDK) probability estimate and the Laplace correction. Apart from a few cases, it gives better values than Laplace correction (within a 95% confidence interval). From the intelligibility viewpoint, it is interresting to note that GDK probability estimate on pruned tree is generally better than smoothing method on unpruned tree (which is better than smoothing method on pruned tree). We also performed a Wilcoxon unlateral paired-wise test on each batch of 100 samples. The tests confirm exactly the significant results from Table 1 (with p-values always < 0.01).

The choice of the metric has a limited effect on the result in term of AUC. The difference is always of a different order except for vehicle, pima and especially glass for which it can reach 10-2 .

We used several bandwidths, with τ from 5 to 15% of the range of the algebraic distance: Results vary very smoothly with the bandwidth, Table 1 would present completely similar results.

Table 2 shows the comparison using Mean Squared-Error (MSE) as a metric to measure the quality of the probability (p(c|x) -

estimate. The error at test point x is se(x) = ∑c ˆ p(x|c))2 , where p(c|x) is the true conditional probability (here p(c|x) is set to 1 when c(x) = c). se(x) is then summed over each test sample. The performance of the GDK probability estimate diminishes quickly when τ increases, although the AUC remains better. This is easily comprehensible: when τ increases, the kernel estimate tends to erase sharp variations. As a consequence, probability estimate cannot reach the extremes (0 or 1) easily. The Log loss metric is not shown since it gives useless results (almost always infinite).

5 Local estimate: Partition of the Space

In order to get more local estimate, the first idea would be to use the leaves to refine the definition of the sets S(x) used to run the kernel density estimate (step 2 of algorithm 3). S(x) would be simply the leaf that classifies x. However, we'll argue on a simple example that this option shows severe drawbacks, and that a definition based on the geometry of the DT boundary should generally be preferred.

5.1 DT Boundary-based partition

The rationale behind our partition is to consider the groups of points for which the distance is defined by the same normal to the decision surface, because these points share the same axis defining their distance, and they relate to the same linear piece of the decision surface.

Let {H1, H2, .., Hk} be the separators used in the nodes of the tree, and S the learning sample. To partition the total sample S, we associate with each separator Hi a subset Si of S, which comprises the examples x such that the projection of x onto the decision boundary Γ belongs to Hi. Generically, the projection p(x) of x onto Γ is unique, but p(x) can belong to several separators. In that case we associate to x the separator Hi defining p(x) with the largest margin. We define S(x) as Si. The KDE is then run on the h(xj), xj ∈ Si, as explained previously.

5.2 Advantage of our partition

We now illustrate on a simple example the advantage of our partition compared with the partition generated by the leaves. Suppose that the learning examples are uniformly distributed in a square in a space x, y, and that the probability of class 1 depends only on axis x, with the following pattern (Figure 2):

• For x growing from -0.5 to 0, the probability of class 1 grows smoothly from 0.1 to 0.9, with a sigmoid function centered on -0.25.
• For x growing from 0 to 0.5, the probability of class 1 decreases sharply from 1 to 0 around x = 0.25.

A typical decision tree obtained from a sample generated with this distribution is represented on figure 2 (top). It has three leaves, two yield class -1 and are defined by a single separation, and one yields +1 and is defined by both separations (the gray area on the figure). The partition defined by the leaves thus generates 3 subsets.

Figure 2 (bottom) shows the partition obtained with our method. It includes only two subset, one for each separation. Figure 3 shows the results obtained with a kernel estimation (a simple Parzen window of width 0.1) on the leaf partition, and on our partition, compared with the actual probability function which was used to generate the sample. One can notice that our partition gives a result which is very close to the one that would be obtained with a kernel estimation on the x axis. This is not the case for the leaf partition, which introduces strong deviations from the original probability.

The main explanation of these deviations is a side effect which artificially increases the probability of 1 around the border, in the case of the leaf partition. Actually, this is the same bias as the one obtained when estimating directly the probabilities on the leaves. Moreover, the leaf partition introduces an artificial symmetry on both sides of the leaf, because of the averaging on all the examples at similar distance of the boundary. These problems are not met with our partition. We claim that the problems illustrated in this example have good chances to occur very frequently with the leaf partition. In particular, the side effect due to the border of the leaf will always induce a distortion, which is avoided with our partition. Artificial symmetries will always be introduced when a leaf includes several separators.

Table 3 shows the results of the comparison between local distance-based kernel estimate and smoothing method at the leaf for some databases. Because of the partition of the space, the results from the AUC comparison and MSE are not necessarily correlated, and MSE is globally better than for the global DK probability estimate.

6 Conclusion

We have presented in this article a geometric method to estimate the class membership probability of the cases that are classified by a decision tree. It applies a posteriori to every axis-parallel tree with numerical attributes. The geometric method doesn't depend on the type of splitting or pruning criteria that is used to build the tree. It only depends on the shape of the decision boundary induced by the tree, and it can easily be used for real multi-class problem (with no particular class of interest). It consists in computing the distance to the decision boundary (that can be seen as the Euclidean margin). A kernel-based density estimator is trained on the same learning sample than the one used to build the tree, using only the distance to the decision boundary. It is then applied to provide the probability estimate. The experimentation was done with basic trees and very basic kernel estimate functions. But it shows that the geometric probability estimate performs well (the quality was measured with the AUC and the MSE).

We also proposed a more local probability estimate, based on a partition of the input space that relies on the decision boundary and not on the leaves boundaries.

The main limit of the method is that the attributes are numeric. It could be extended to ordered attributes, but it cannot be used with attributes that have unordered modalities. The methods could also be used with oblique trees, but the algorithms to compute the Euclidean distance are far less efficient. Further work is in progress in order to improve the local estimate. Another feature, linked to the nearest part of the decision boundary, could be used to train the kernel density estimator (which are still very efficient in dimension 2).