Tree size and pruning
Section of Classification trees, part of Statistical learning
Tree size and pruning
| Type | Section |
| Taught in | Classification trees |
| Part | Statistical learning |
Grown until every leaf is pure, a tree can cut a noise island around a single training case. Its apparent error is then zero whenever the inputs are distinct, and that number is not an estimate of the error on a new draw. One control scores the whole tree by its leaf impurities and charges for the number of leaves:
I_{\mathrm{penalised}} =\sum_{\text{leaf nodes}} I(m)+\alpha\,|\{\text{leaf nodes}\}|,
where |\,\cdot\,| is the number of leaves and \alpha\ge 0 is the price of an extra leaf. The tree wanted is a minimiser of I_{\mathrm{penalised}}. One algorithm refuses a split that does not reduce the penalised criterion. Another grows a large tree and then prunes it back to the subtree with the best penalised score. Either way \alpha is still free. There is little theory that names a universal value. Cross-validation can choose it. The same cross-validation can instead watch the classification error directly and stop adding leaves when that error stops falling. Both uses of cross-validation are part of building the tree, so the cases that chose \alpha, or that chose where to stop, cannot also be the cases that estimate the error of the chosen tree. A separate test set can do the estimation. When the sample is too small for a permanent test set, the nested scheme on Estimating error rates puts the choice of \alpha inside each training split.
The display above sums leaf impurities without weights. The CART cost-complexity criterion weights each leaf by its share of the training sample and then adds a leaf penalty. The weighting is what makes \Delta I(m)\ge 0 imply that a split never increases the impurity term: the sample-weighted sum of leaf impurities equals the root impurity minus the sum of the weighted reductions along the tree, so \alpha is the only reason to refuse a split that reduces impurity. An unweighted sum of leaf impurities does not inherit that identity. Split impurity and pruning risk also need not be the same quantity. Gini may grow a classification tree while misclassification risk governs pruning.
In rpart, the complexity parameter cp is relative to the root-node risk, so its numerical value is not the unnormalised \alpha in the display above. A call that grows with the Gini split and then prunes at the cross-validated minimum is
fit <- rpart(class ~ ., data = train, method = "class",
parms = list(split = "gini"),
control = rpart.control(cp = 0.01))
printcp(fit)
pruned <- prune(fit, cp = fit$cptable[which.min(fit$cptable[, "xerror"]), "CP"])
predict(pruned, newdata = test, type = "class")The argument split = "information" grows by cross-entropy instead of Gini. printcp reports the cross-validated error by tree size. On the iris petal plane, a complexity parameter of 0.1 keeps a coarse axis-aligned partition, and a complexity parameter of 0.001 cuts the same observations into many more rectangles. The boundaries are unions of rectangles. They are not the linear cuts of a discriminant rule.
Used in
See also
Node impurity · Building a classification tree · Choosing a split · Invariance to a change of units · Multi-way splits and missing values · What a fitted tree can be trusted to mean · Laboratory: prune using training cross-validation · Decision tree