Building the decision tree

We use a divide-and-conquer algorithm to build a decision tree: we split a big node into a few sub-nodes, and then keep splitting those sub-nodes as above, until each of them contains only one class.

In splitting, the rule of thumb is, we split the big node in a way that maximizes the “purity” of those sub-nodes. That is to say, each sub-node contains more samples from only one class.

Information entropy is a measurement of the “purity” of a set. Assume a set \(D\) contains \(N\) classes, and their proportions are \(p_1,p_2,\dots,p_N\). The definition of information entropy is \[ H(D)=-\sum_{k=1}^Np_k\log p_k. \] The smaller \(H(D)\) is, the higher purity that set \(D\) has.

1. ID3 algorithm (Quinlan, 1986)

Among all possible splitting, choose the attribute \(a\) that maximizes the information gain: \[ Gain(D,a)=H(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}H(D^v), \]

where \(V\) is the number of possible values of attribute \(a\).

It makes some sense, however, it is in favor of the attribute that splits the node into more sub-nodes. Specifically, if we include the idendity attribute in our feature, i.e. each sample has a unique indentity, then it will increase the information entropy to zero. Thus the indentity will always be the chosen one to split. But the generalization ability of this decision tree will be poor, which is not plausible.

2. C4.5 algorithm (Quinlan, 1993)

To avoid splitting the node into fragiles,C4.5 algorithm takes the number of sub-nodes into account. It maximizes gain ratio instead of information gain. The definition of gain ratio: \[ GainRatio(D,a)=\frac{Gain(D,a)}{IV(a)}, \] where \(IV(a)\) is the intrinsic value of attribute \(a\), defined by \[ IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log \frac{|D^v|}{|D|}. \]

A notable fact is that, by maximizing the gain ratio, it tends to choose attributes with less sub-nodes, exactly the opposite to ID3 algorithm. \(C4.5\) algorithm takes both of them into account: it maximizes the gain ratio only among those attributes with information gain above the average.

3. CART (classification and regression trees, Breiman et al., 1984)

CART uses a new measurement of “purity”: Gini index, defined as follows: \[ Gini(D)=\sum_{k=1}^N\sum_{k^\prime\neq k}p_kp_k^\prime=1-\sum_{k=1}^Np_k^2. \] The notation is the same as above. For any attribute \(a\), splitting by \(a\) changes the Gini index to \[ Gini(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v). \]

CART maximizes \(Gini(D,a)\) among all possible attributes \(a\).

Pruning

To prevent overfitting, we prune the decision tree for a better generalization performance.

1. Prepruning

When building the decision tree, we may stop early, not necessarily until each node contains only one class. For each splitting, we use cross-validation to test whether the current splitting increases the generalization performance. If not, we stop splitting the current node immediately.

Prepruning can reduce the fitting complexity, but it risks ill-fitting. Some splittings themselves cannot improve generalization performance, but based on those, some further splittings may be very helpful. But prepruning totally ignores them.

2. Postpruning

After we expand all the nodes of a decision tree, we can prune it from the leaf nodes to the root. We also use cross-validation to test whether the current splitting increases the generalization performance. In the comparison, we can take the “good future splitting” into account. Therefore, compared with prepruning, it is much less likely to get ill-fitted. However, since we have to expand all possible nodes at first, and then test all of them, the computation can be a burden.

Other issues

Example

R-package for CART algorithm.

library(rpart)
library(rpart.plot)
library(tree)

data(kyphosis)
set.seed(1)

tree <- rpart(Kyphosis ~ . , kyphosis)
rpart.plot(tree)

Past versions of unnamed-chunk-1-1.png

Session information

sessionInfo()

R version 3.6.0 (2019-04-26)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 10 x64 (build 17134)

Matrix products: default

locale:
[1] LC_COLLATE=English_United States.1252 
[2] LC_CTYPE=English_United States.1252   
[3] LC_MONETARY=English_United States.1252
[4] LC_NUMERIC=C                          
[5] LC_TIME=English_United States.1252    

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] tree_1.0-40      rpart.plot_3.0.7 rpart_4.1-15    

loaded via a namespace (and not attached):
 [1] workflowr_1.4.0 Rcpp_1.0.1      digest_0.6.19   rprojroot_1.3-2
 [5] backports_1.1.4 git2r_0.25.2    magrittr_1.5    evaluate_0.14  
 [9] stringi_1.4.3   fs_1.3.1        whisker_0.3-2   rmarkdown_1.13 
[13] tools_3.6.0     stringr_1.4.0   glue_1.3.1      xfun_0.7       
[17] yaml_2.2.0      compiler_3.6.0  htmltools_0.3.6 knitr_1.23