Minimum Splits Based Discretization for Continuous Features

1 Introduction

Continuous values refer to linearly ordered values, mainly numeric values. While continuous values are common in real applications, many learning algorithms focus on unordered discrete values. A common practice is to discretize continuous values into intervals so as to provide useful information with respect to classes. Dis­ cretization can be performed either on the whole dataset prior to induction, i.e, global discretization, or on local regions during induction, i.e. , local discretization. We focus on local discretization as it takes into account the context sensitivity of the nature. One example of local discretization is the entropy-based C4.5 [Quinlan, 1993], in which continuous values are split into two intervals, i.e., binary splitting, for consideration at a node. How­ ever, as pointed out in [Fayyad and Irani, 1993], an in­ teresting range is usually an internal interval within the feature's range, and to get to such an interval a binary­ split-at-a-time leads to unnecessary and excessive parti­ tioning of the examples. We now provide further reasons for multi-way splits.

One frequent argument against multi-way splitting is that a multi-way split can be "simulated" by a series of binary splittings. Though theoretically true, this argu­ ment is false in the process of generating decision trees where there is no guarantee that all "simulating" binary splittings will be finished up before considering other features because the splitting at each level is performed independently. As a result, a structured multi-way split is hardly simulated by binary splits in practice. In ad­ dition, by restricting to only binary splits, an unstruc­ tured feature could be selected instead of a structured but never explored multi-way split of a continuous fea­ ture, making the simple structure disappear. Consider the following two decision trees built in one of the 10fold cross validation on Iris dataset. The first tree is produced by the multi-way split proposed in this paper, and the second by C4.5. Though both trees have the same size and same error rate on test data, the first tree classifies most examples at the first level using simple rules and thus is preferred. The reason why C4.5 didn't select petal length at the first level is because the op­ timal binary split of petal length loses to that of petal width. As a result, the simple one-level test for most examples, as in the first tree, is not discovered. This example also reveals the bias of the tree size measure: it does not take the frequency, i.e., importance, of rules into consideration.

petal length <= 1. 9 : Iris-setosa (45 . 0) petal length<= 4.7 : Iris-versicolor (41.0/1.0) petal length > 5 : Iris-virginica (38.0) petal length <= 5 : I petal width<= 1.7 : Iris-versicolor (4.0) I petal width> 1.7 : Iris-virginica (7.0/1.0) petal width <= 0.6 : Iris-setosa (45.0) petal width > 0.6 : I petal width> 1.7 : Iris-virginica (43.0/1.0) I petal width<= 1.7 : I I petal length <= 5 : Iris-versicolor (45.0/1.0 I I petal length> 5 : Iris-virginica (2.0)

Searching for a good multi-way split is significantly more complicated than searching for a good binary split .

The brute-force solution is exponential ink -1, where k is the number of intervals considered. Since the number of intervals in a multi-way split is unknown and not fixed a prior, goodness measures such as the gain that are al­ ways improved by further splitting do not work directly, and have to be coupled with other constraints or criteri­ ons. In this paper, we address the search problem in two steps. First, we ·define the notion of minimum splits as a necessary condition for a good split. A minimum split wrt a threshold of impurity is a split that minimizes the number of intervals subject to the threshold. We propose a dynamic programming algorithm for finding a mini­ mum split for any impurity measure that is additive in the sense that the impurity of several intervals is the sum of the impurities of each interval. This includes most standard impurity measures, such as entropy [Quinlan, 1993], twoing rule and Gini index [Breiman et al., 1984], Sum Minority, inconsistency rate, and others. The dy­ namic programming algorithm runs in a quadratic time in the number of starting intervals. We describe two ap­ proximation algorithms that can compute nearly optimal solutions efficiently for large datasets.

We then propose a method of determining the "best" split from a collection of minimum splits called candidate splits, found in a single run of the algorithm for finding minimum splits. The "best" split of continuous values is the caadidate split that has the smallest product of en­ tropy and number of intervals. Intuitively, this product measures the total information, rather than the average information like the standard entropy, of all intervals. We compared the proposed minimum split method with Release 8 of C4.5, a substantial improvement of early re­ leases on handling continuous values. The study shows that multi-way splits usually build decision trees that are shallow and classify more examples at upper levels of the tree, compared to binary splits. We propose the notion of testing depth to capture this aspect of simplicity of decision trees, which is not addressed by the tree size.

Several recent papers have examined discretization of continuous values. One approach, e.g., [Kerber, 1992; Richeldi and Rossotto, 1995], starts with one inter­ val per value and repeatedly merges adjacent intervals based on some "similarity" measure. It could be diffi­ cult to specify a good threshold of similarity so that not too many intervals are constructed. Another approach aims at finding a split that optimizes some goodness criterion. Examples are [Quinlan, 1993; Catlett, 1991; Holte, 1993; Chiu et al., 1990; Fulton et al., 1995; Auer et al., 1995]. See [Dougherty et al., 1995 ] for more on these work. In these methods, additional con­ straints, such as the maximum number of intervals, the minimum nu,mber of examples in each interval, a penalty function on the number of intervals, are needed to control the number of intervals. [Catlett, 1991;

Fayyad and Irani, 1993] use recursive application of bi­ nary splitting to obtain a multi-way split coupled with some criterion for stopping the splitting process. The problem with such splittings is that some optimal k-way splits do not come from hi-partitioning an interval in an optimal (k- 1)-way split. For example, if Sum Minor­ ity is the impurity measure (i.e., the number of examples belonging to minority classes in an interval), the optimal 3-way split (ABBBB)(AAA)(BBBBA) cannot be ob­ tained by hi-partitioning one interval in any of the (only) two optimal binary splits

(A)( B B B BAAAB B B BA), (ABBBBAAABBBB)(A),

where A and B present examples of different classes. The approach of multivariate decision trees considers a combination of several continuous features rather than a single feature at a node test. Such decision trees are still univariate ones on the transformed features. Therefore, the search for univariate decision trees of high perfor­ mance is a fundamental and important research area.

2 Minimum splits

We propose the notion of minimum splits as a necessary condition for a good split. The motivation is simple: for a given threshold of impurity, a good split should have no unnecessary splitting with respect to the threshold, that is, no intervals in the split can be merged with­ out exceeding the threshold. We formalize this notion below. Assume that the training examples are initially partitioned into X 1 , ... , Xk such that all examples in X; have a smaller value than those in Xj for i < j. X 1, ... , Xk are called bins. A simple case is that each bin X; corresponds to one observed value. Other cases which give a smaller k will be considered in Section 2.4. By splitting bins X 1, . .. , Xk into several intervals, we mean that' adjacent bins may be put into the same in­ terval, but no examples in the same bin can be placed in different intervals.

2.1 Definition

Definition 2.1 (Minimum splits) Given threshold 1 of impurity, a n-way split of X 1 , ... , Xk is minimum wrt 1 if n is the lowest value so that no more than 1 impurity is produced. A minimum split of X 1 , ... , Xk wrt 1 is strong if it has the smallest impurity among all minimum splits of X 1 , .. . , Xk wrt I · The minimum split problem is to find a minimum split wrt a given threshold of impurity.

All minimum splits wrt 1 (if any) have the same num­ ber of intervals but may have different impurities. All strong minimum splits wrt 1 (if any) have both the same number of intervals and the same impurity. The split se­ lection algorithm in the next section will always choose a strong minimum split. The minimum split problem has immediate application in feature selection. For example, if the impurity measure is the inconsistency rate, detect­ ing irrelevant continuous features is equivalent to finding features whose minimum splits with respect to zero im­ purity have only one interval. As another example, if a discrete feature A has entropy a, solving the minimum split problem for a continuous feature C with respect to a gives the minimum number of intervals for C to beat A in entropy. With this information, one can choose the feature that has fewer branches.

We now examine algorithms for finding a minimum split for a general impurity measure that is additive as explained in Introduction; algorithms for a strong minimum split can be obtained easily from such algo­ rithms. Let imp( i , j) denote the impurity of the single interval containing all continuous values in X ;, . .. , Xj. Let /(x,j) and M(x , j) , respectively, denote the num­ ber of intervals and the impurity of a minimum split of X1 , ... , Xi with respect to x . I(x , j) and M(x , j) are undefined if there is no such minimum split . From the minimality of the number of intervals and the additivity of the impurity measure,

where only defined I(x - imp(j + 1, i) , j) are consid­ ered. That is, a minimum split of X 1 , ... , X; wrt x comes from a minimum split of X 1 , ... , Xj wrt threshold x- imp(j + 1, i), 0 ~ j < i, such that the right-most cutpoint j minimizes I(x-imp(j+ 1, i) , j) . Assume that j' minimizes I(x- imp(j + 1, i) , j). Then

However, such a recursive computation of I(x , i) and M ( x, i) is very expensive because of repeated calls of the same computation. We present a dynamic programming algorithm which runs in quadratic time in the number of starting bins.

2.2 The dynamic programming algorithm

We compute I(x , i) and M(x , i) in the increasing order of x and i. For a general impurity such as the real-valued entropy, it does not work to enumerate all possible values for x . Our approach is to represent the domain [0 , -y) of x by a number of values determined from a desired precision of impurity denoted f below. For example, a difference in entropy less than 0.01 is usually considered insignificant, so we can choose f = 0.01. Now if threshold "")' = 0.3562, there are 37 values for x to be examined: 0.00, 0.01 , 0.02, . . . , 0.36. In implementation, we replace the domain [0, -y) of x with the integers {0, 1, .. . , -yjf }, where "")' is rounded to precision f. Accordingly, imp(j + 1, i) is replaced with Round(imp(j + 1, i)/f) , i.e., the rounding of imp(j + 1, i) / f to the closest integer.

However , one critical issue must be addressed with care: the error caused by rounding imp(j + 1, i)/f could accumulate through intervals and cause defined /(x , i) to be undefined. To see this, let f = 0.01 , imp(1 , 1) = 0.545, and imp(2, 2) = 0.255. Thus, X1 , X2 can be split into two intervals at cutpoint j = 1 without exceeding thresh­ old x = 0.80. On the other hand, Round(imp(2, 2)/f) = 26, which leaves only 0.80/f- 26 = 54 for X1 , making /(54, 1) undefined because Round(imp(1 , 1)/f) =55. As a result , the split at j = 1 is mistakenly not consid­ ered. In general, since x - Round(imp(j + 1, i)/f) is the threshold for splitting X 1 , . . . , X j , the error caused by the rounding may accumulate through intervals. To avoid this, we perform the rounding at each interval in such a way that the accumulated error is always within ±f. This is done by replacing Round( imp(j + 1, i)/f) with Round(imp(j + 1, i)/f, E(j)) , where E(j) is the ac­ cumulated error up to X j. As before, Round(imp(j + 1, i)/f , E(j)) returns the rounding of imp(j + 1, i)/f, but the rounding direction is to reduce the error in E(j). See below. We have omitted the part of re­ trieving cutpoints as it can be easily done by storing the right-most cutpoint j for each pair of x and i . Ini­ tially, I(x , 0) = M(x , 0) = 0 for x = 0, 1, ... , -y/f ; all other elements of I and M are undefined. y abbreviates Round(imp(j + 1, i)/f, E(j)) .

Round(u , v) :

if v 2: 0 then return floor(u);

else return ceiling(u) ;

Dynamic Programming Algorithm:

for x = 0 to "")' / f do

E(O) = 0.0;

for i = 1 to k do

(*) find a j , 0 ~ j < i, such that

I(x - y, j) is defined and minimized;

if found then

Section 3 will discuss how to determine threshold -y while applying the minimum split problem to select a good split of continuous values. The precision f is usu­ ally chosen so that the number "")' / f of impurity values considered is between 10 and 100, usually between 10 and 20. A too large -y/f does not necessarily improve the test quality since a very small difference is likely due to randomness.

Let us consider the complexity of the above algo­ rithm. Matrix imp( i , j) can be computed outside the main loop. For impurity measures that use only count information of examples and classes, such as entropy, Sum Minority, and many others, matrix imp(i , j) can be computed incrementally from small i , j to large ones in time O(W * k 2 ), where W is the number of classes.

Theorem 2.1 Let f. be the precision of the impurity measure. The dynamic programming finds a minimum split fork bins (if any) wrt "Y impurity in 0( ( "Y /f.+ W) * k 2 ) time, where W is the number of classes.

The largest k corresponds to the case where each bin contains exactly examples that have the same continuous value. A smaller k is possible by merging adjacent bins, which will be considered in subsection 2.4. Note that the dynamic programming not only returns a minimum split of x1' ... 'xk wrt "'f , but also a minimum split of x1 , .. . ,xk wrt x , where X= O,f. , . . . , "'f-f. for "free". In Section 3, these minimum splits form the search space of the optimal split . To find a strong minimum split , the only change required is to add the minimization of M(x- y,;j ) + y *f. as the second order requirement in step (*) of the above dynamic programming algorithm.

2.3 The greedy algorithm

If the number k of bins is large, the dynamic program­ ming algorithm could be expensive. We present a linear time algorithm by greedily merging adjacent intervals until the threshold "Y is exceeded. Initially, each bin X; itself forms an interval. Let imp0 be the impurity for this initial state. At each step the two adjacent intervals whose merging adds the least impurity are merged, thus greedily maximizing the number of mergings or mini­ mizing the number of intervals. We assume imp0 ~ "Y , otherwise, there is no minimum split wrt "Y· For an in­ terval I; , let imp(!;) denote the impurity of I;. I; U Ii+1 denotes the merged interval of two adjacent intervals I; and /;+1.

Greedy Algorithm:

exceed= false ; n= k ; z =impo ; while (exceed= false and n > 1) do find the pair of adjacent intervals (Ij , Ij+l} minimizing ~ = imp(Ii U Ij+l)- imp(Ii)- imp(Ii+l); if z + ~ ~ "Y then merge Ij and Ij+1; z = z + ~; n = n -1; else exceed= true ;

Finding the next pair (Ii, Ii+d for merging in a fixed time without scanning all pairs of adjacent intervals is the key of efficiency. For this purpose, we use the B­ tree [Elmasri and Navathe, 1994] from the database re­ search to index pairs of adjacent intervals (Ii, Ij+l) in the increasing order of increment~= imp(Ij U Ij+l)­ imp(Ii) - imp(Ii +1). With the B-tree of branching fac­ tor b (i.e., the average number of branches at a node) on k indexed values, search, insertion and deletion of a value~ can be done by accessing a number of tree nodes equal to the height of the B-tree, that is, logbk . Usually a large b, e.g., more than 20, is chosen to reduce the height of the B-tree. For example, if b = 20 and if there are three million distinct values, inserting, deleting, and searching a ~ value needs to access at most 5 nodes of the tree.

We build the initial B-tree by inserting increment ~ for all pairs of adjacent bins (Xj, Xi+ I) . Within each iteration, we find the smallest ~ at the front of the leaf level (remember increments ~ are sorted at leaves) and merge the two intervals that define this ~- Sup­ pose that intervals Ia, h, Ie, Id are adjacent and that pair (h, I e) is merged. After the merging, ~ab for (/a , h) and ~be for (h, Ie) are affected, and ~ed for (/e,Id) should be deleted. In the B-tree, this is done by deleting old ~ab, ~be , ~ed and inserting new ~ab, ~be · To find the old ~ab , ~be, we store two pointers, PI and Pr , to­ gether with increment ~ of every adjacent pair (It , I2) . PI points to the increment ~for adjacent pair (/o , h), and Pr points to the increment~ for pair (/2 , fa). There­ fore, after ~be is deleted, PI and Pr stored at ~be give the addresses of the old ~ab and ~ed for deletion. The new ~ab and ~cd are then inserted into the B-tree. The PI and Pr links are updated to reflect that new ~ab and ~cd are adjacent on these links. It can be seen that these operations cost only a small factor of the height of the B-tree, which still can be considered a constant for large data size.

Theorem 2.2 The greedy algorithm runs in time O(h * k) for k bins, where h is the height of the B-tree on k- 1 indexed values.

For a large branching factor of the B-tree, h is practi­ cally a constant as explained early.

2.4 The hybrid algorithm

The third strategy is a compromise between optimality and speed through the following two-phase hybrid ap­ proach: the initial bins X 1 , . . . 1 X k are formed by plac­ ing all examples having the same continuous value in a bin. In the first phase, we apply the greedy algorithm to X 1' ... I xk to merge adjacent bins. Due to the greedy nature, bins that are merged into the same interval have similar class distribution and thus little or no impurity is introduced. Let k' be the number of intervals pro­ duced. Note that k' < k. In the second phase, . we apply the dynamic programming algorithm to the k' intervals produced by the greedy algorithm, by treating such in­ tervals as starting bins. The idea is to run a fast but less accurate algorithm on the initial large data and switch to an accurate but slower algorithm after the number of intervals is reduced. By applying the greedy algorithm as interval reduction, the quadratic term k 2 in Theorem

2.1 is reduced to k' 2 · In general, the switching point k' represents a trade-off between optimality and speed.

3 The optimal split

We now address the central question of how to determine the optimal split for a continuous feature at a node of decision trees. Once the optimal split is determined for every continuous feature, any existing selection criterion for discrete features is applied to select the best feature at the node. We use the entropy [Quinlan, 1993] as the impurity measure.

As motivated in Section 2, a good split must be a min­ imum split, therefore we consider only minimum splits when searching for the optimal split. Since any thresh­ old larger than eb gives a minimum split having at most two intervals, where eb is the entropy of optimal binary splits, we need only to consider thresholds not more than eb. In other words, the search space of the optimal split is the set of minimum splits of X 1, ... , xk wrt X, where x = 0, E, 2E, ... , eb, which have at least two intervals. From Section 2, these minimum splits can be found in a single run of the dynamic ·programming algorithm wrt eb. We call these splits candidate splits for feature A. The set of candidate splits is empty only if all examples belong to the same class, in which case there is no need of splitting at the node. If the greedy algorithm is run in­ stead, splits after each iteration form an approximation of candidate splits.

Let I ( x, k) and M ( x, k) denote the number of inter­ vals and entropy of a minimum split of X 1 , ... , Xk wrt x . In the search for the goodness measure of a split, we observed that the product I(x, k) * M(x, k) usually gives a reasonable quality measure of the minimum split. On one hand, a "good" split usually has both a small number of intervals and a small entropy, thus yielding a small product. On the other hand, a small product but a "not-so-small" interval number entails a very small entropy, thus a nearly pure classification with no unnec­ essary splitting (due to minimum splits). It is possible, however, that some of these intervals are very small. We avoid such splits by requiring a minimal number of ex­ amples in an interval of a minimum split. With these said, we have:

The optimal split for a continuous feature: choose the candidate split that has the smallest prod­ uct of entropy and number of intervals.

There is a natural interpretation for the above selec­ tion. Suppose that feature A is split into d intervals, with n; examples and e; entropy for the ith interval. Let N be the total number of examples. The entropy of the split is then given by

This is exactly the weighed average of entropies for all intervals. Therefore, the above minimum product selec­ tion aims at minimizing the total entropy of a split. The following corollary says that the optimal split is well be­ haved by being actually a strong minimum split.

Corollary 3.1 The optimal split selected above is a strong minimum split of X 1 , ... , Xk wrt some x.

In fact, if the optimal split is not strong, there must be another minimum split (also in the set of candidate splits) having the same number of intervals but a smaller entropy, which yields a smaller product and thus it is preferred to the other one.

4 Empirical evaluation

We compared three algorithms: Release 8 of C4.5 (the latest release) with the default setting, the multi-way splitting based on dynamic programming, the multi­ way splitting based on the greedy algorithm. These algorithms are denoted by C4.5(R8), Dynamic, and Greedy, respectively. The hybrid algorithm is not in­ cluded because its performance is expected to lie be­ tween Dynamic and Greedy. In Dynamic, the bins to start with correspond to examples having the contin­ uous value. Unlike early releases, C4.5(R8) improves the performance on continuous values by employing an MDL-inspired penalty to adjust the gain of a binary split of continuous values. As shown in [Quinlan, 1996], C4.5(R8) compares favorably with the multi-way split method T2 [Auer et al., 1995] and the discretization method [Fayyad and Irani, 1993]. Therefore, we choose C4.5(R8) as a benchmark. Dynamic and Greedy deter­ mine the optimal split of continuous values as in Section 3 and select a feature for branching as in C4.5 using the optimal splits for continuous features. All three algo­ rithms are applied to 15 datasets from the UCI reposi­ tory [Murphy and Aha, 1994], all involving some continu­ ous features and some involving many. All experiments are performed using 10-fold cross validation. The size and error rate of pruned decision trees are collected on test data. A summary is given in Table 1. The numbers following ± are standard errors.

In Table 1, the testing depth of a decision tree is de­ fined as the average length of root-to-leaf paths weighed by the numbers of examples covered by leaves. Thus, the testing depth measures the average number of tests needed to classify an example, thus, the average com­ plexity of rules used. A decision tree with a small testing depth is likely to classify examples by simple rules. This aspect of complexity is not refl~cted by the simple tree size. We highlight a few results shown in Table 1: (a) Except for a few datasets, Dynamic wins over Greedy in all three measurements. (b) On tree size Dynamic wins over C4.5(R8) in 12 out of 15 datasets, with 1 tie, and on error rate Dynamic wins over C4.5(R8) in 8 out of 15, with 2 ties. (c) On tree size, C4.5(R8) performs better than Greedy in general, and on error rate, about half­ half. (d) On testing depth, both Dynamic and Greedy win over C4.5(R8) for all 15 datasets. Decision trees produced by Dynamic and Greedy usually are not as deep as those produced by C4.5(R8); they tend to have more "parallel" branches at a node, instead of "nested" ones into the tree. After comparing actual trees, we feel that "parallel" branches are easier to understand than "nested" ones. In running time, Dynamic is slowest and the other two are comparable. In this regard, the hy­ brid algorithm could be more promising to offer both quality trees and fast speed. In conclusion, the proposed multi-way splitting of continuous values shows some ad­ vantages over C4.5(R8). We believe that for many ap­ plication domains a multi-way splitting coupled with a careful control on over-splitting is a powerful technique for handling continuous values.