Classification tree

A classification tree partitions predictor space recursively and attaches a class probability vector to each terminal region. For a categorical response, a fitted leaf commonly uses its observed class proportions and predicts their largest entry. Binary numerical splits compare one coordinate with a threshold. Growing a tree greedily by reducing classification-tree deviance gives an interpretable rule but does not globally optimize the tree. Cost-complexity tree pruning and cross-validation control complexity and assess prediction error.

Pruning balances a tree's empirical loss $R(T)$ against the number of leaves. Increasing $\alpha$ favors a nested sequence of smaller subtrees, obtained by removing splits with the smallest effective cost per removed leaf. Choose complexity using cross-validation or a validation set, and assess the selected tree on a separate test set. The loss can be deviance or misclassification loss; the chosen convention must be specified.

Maximizing a node's multinomial likelihood gives class probabilities ${\hat{p}}_{tk}=n_{tk}/n_t$. Twice the negative maximized log-likelihood relative to perfect classification is the displayed deviance, with $0\log 0=0$. It equals twice the node size times its Shannon entropy. A split is chosen by maximizing $D(t)-D(t_L)-D(t_R)$, and tree deviance is the sum over terminal nodes. The training misclassification count is instead ${\sum }_t(n_t-{\max }_k{n}_{tk})$; the two criteria are different.