CART trees and pruning

Fix a finite labeled sample $(x_i,y_i{)}_{i=1}^n$ with $n\ge 1$, $x_i\in {\mathbb{R}}^p$ and $p\ge 1$. In regression, $y_i\in \mathbb{R}$. In classification, the labels lie in a fixed ordered finite set $\mathcal{C}=\{c_1<\cdots <c_K\}$ with $K\ge 1$. A finite empirical axis-aligned binary decision tree has root sample-index set $I_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}=\{1,\dots ,n\}$. Each internal node $v$ stores a coordinate $j\in \{1,\dots ,p\}$ and threshold $t\in \mathbb{R}$; its left and right child sample sets are $I_v^L=\{i\in I_v:x_{ij}\le t\}$ and $I_v^R=\{i\in I_v:x_{ij}>t\}$, and both are required to be nonempty. A leaf is a terminal node. The leaf sample sets partition $\{1,\dots ,n\}$, and each node's feature region is the intersection of its path inequalities. Every input feature vector follows the unique path determined by the stored comparisons.

For a regression leaf with sample set $I$, put $N_I=\mathrm{\mid }I\mathrm{\mid }$, ${\bar{y}}_I=N_I^{-1}{\sum }_{i\in I}{y}_i$, and $Q_I=N_I^{-1}{\sum }_{i\in I}(y_i-{\bar{y}}_I{)}^2$; its prediction is ${\bar{y}}_I$ and its total squared-error loss is $N_I{Q}_I$. For a classification leaf, put $p_{Ik}=N_I^{-1}\mathrm{\mid }\{i\in I:y_i=c_k\}\mathrm{\mid }$ and predict the class $c_k$ with largest $p_{Ik}$, choosing the least index in a tie. Its optional impurities are misclassification $Q_I^{\mathrm{m}\mathrm{i}\mathrm{s}}=1-{\max }_k{p}_{Ik}$, Gini $Q_I^{\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}}=1-{\sum }_{k=1}^K{p}_{Ik}^2$, and entropy $Q_I^{\mathrm{e}\mathrm{n}\mathrm{t}}=-{\sum }_{k=1}^K{p}_{Ik}\log p_{Ik}$, where $\log$ is the natural logarithm and $0\log 0=0$. A chosen classification criterion determines $Q_I$ and the corresponding total leaf impurity is $N_I{Q}_I$.

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.1–9.2.3, printed pp. 305–310

MIT OpenCourseWare, 15.097, Lecture 8: Decision trees, slides 14–15

Let $I$ be a nonempty finite set of sample indices and let $y_i\in \mathbb{R}$ for every $i\in I$. Put $N=\mathrm{\mid }I\mathrm{\mid }$ and ${\bar{y}}_I=N^{-1}{\sum }_{i\in I}{y}_i$. Among all constants $c\in \mathbb{R}$, the unique minimizer of ${\sum }_{i\in I}(y_i-c{)}^2$ is $c={\bar{y}}_I$, and the minimum value is ${\sum }_{i\in I}(y_i-{\bar{y}}_I{)}^2$.

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2, equations (9.10)–(9.14), printed p. 307

MIT OpenCourseWare, 15.097, Lecture 8: Decision trees, slide 16

Let $T_0$ be a fixed finite binary tree grown on the sample from an empirical decision tree. A subtree $T\subseteq T_0$ is obtained by collapsing zero or more internal nodes and all their descendants to leaves. For each leaf $m$ of $T$, let $N_m$ be its sample count and let $Q_m(T)$ be its regression squared-error impurity or its chosen classification impurity, computed as in the empirical decision-tree definition. Define the total training impurity $R(T)={\sum }_{m\in \mathrm{l}\mathrm{e}\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{s}(T)}{N}_m{Q}_m(T)$, the terminal-node count $\mathrm{\mid }T\mathrm{\mid }$, and for $\alpha \ge 0$ the cost-complexity criterion $C_{\alpha }(T)=R(T)+\alpha \mathrm{\mid }T\mathrm{\mid }$.

For a current nonterminal node $t$, let $I_t$ be its sample set and let $T_t$ be its current descendant subtree. Let $R(t)=N_t{Q}_t$ be the training impurity if $t$ is collapsed to a leaf, using the same response or class rule as for a leaf; let $R(T_t)$ be the sum of the impurities of the current descendant leaves. Define the weakest-link quotient $g(t)=[R(t)-R(T_t)]\mathrm{/}(\mathrm{\mid }{T}_t\mathrm{\mid }-1)$. The denominator is the number of leaves removed by collapsing $t$. This definition makes no claim that a weakest-link sequence globally minimizes $C_{\alpha }$ for every $\alpha$ or that validation selection guarantees test-risk performance.

Regression and classification leaf impurities and sample counts

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2–9.2.3, printed pp. 308–310

MIT OpenCourseWare, 15.097, Lecture 8: Decision trees, slides 14 and 16

Choosing $\alpha$ by validation or cross-validation is a data-selection procedure; by itself, that choice does not guarantee test-risk performance.

The inputs are observations $(x_i,y_i{)}_{i=1}^n$ with $n\ge 1$ and $x_i\in {\mathbb{R}}^p$ for an integer $p\ge 1$, a response mode (regression with $y_i\in \mathbb{R}$ or classification with labels in a fixed finite ordered class set), a fixed classification impurity criterion when in classification mode, and a finite integer maximum depth $d_{\max }\ge 0$. The root has sample set $\{1,\dots ,n\}$ and depth $0$. At a current leaf with nonempty sample set $I$ and depth $d<d_{\max }$, perform the following procedure.

1. For each coordinate $j\in \{1,\dots ,p\}$, sort the distinct observed values in that coordinate as $u_1<\cdots <u_r$. For each $k=1,\dots ,r-1$, form the candidate threshold $t=(u_k+u_{k+1})\mathrm{/}2$ and its child sets $I_L=\{i\in I:x_{ij}\le t\}$ and $I_R=\{i\in I:x_{ij}>t\}$. These are the finite candidates at the node; if no coordinate has at least two distinct values, the candidate set is empty.

2. For each candidate, compute its child score. In regression the score is ${\sum }_{i\in I_L}(y_i-{\bar{y}}_{I_L}{)}^2+{\sum }_{i\in I_R}(y_i-{\bar{y}}_{I_R}{)}^2$. In classification it is $\mathrm{\mid }{I}_L\mathrm{\mid }{Q}_{I_L}+\mathrm{\mid }{I}_R\mathrm{\mid }{Q}_{I_R}$ for the fixed chosen impurity criterion. Select the candidate with the smallest score; when scores tie, select the least pair $(j,k)$ by comparing coordinate first and cut index second.

3. Store the selected coordinate and threshold at the current node, create its left and right children, and apply this procedure to the left child and then the right child at depth $d+1$. If $d=d_{\max }$ or the candidate set is empty, leave the current node as a leaf.

The output is the finite tree whose leaves use the regression means or classification majority labels from the empirical decision-tree definition. No strictly positive loss reduction is required for a split below the depth cap, and the returned tree is not asserted to be globally optimal among all trees.

Empirical tree structure, leaf means, and classification impurities

Least-squares optimality of the regression leaf mean

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2–9.2.3, printed pp. 307–310

MIT OpenCourseWare, 15.097, Lecture 8: Decision trees, slides 14–16

The input is a fixed finite empirical decision tree $T_0$. Start with the current tree $T=T_0$ and output sequence $(T_0)$. At each iteration, if $T$ consists of its root leaf, stop and return the sequence. Otherwise, for every current nonterminal node $t$, compute $g(t)=[R(t)-R(T_t)]\mathrm{/}(\mathrm{\mid }{T}_t\mathrm{\mid }-1)$ using the current subtree quantities from the cost-complexity definition. Select a node minimizing $g(t)$; if several tie, select the node whose root-to-node address is least in lexicographic order with $L<R$. Collapse the current descendant subtree at that node to a leaf, using the empirical tree's leaf prediction rule on its sample set, and append the resulting subtree to the output sequence. Repeat on that new current tree.

The sequence contains the initial tree and each successive collapse through the root leaf. This procedure makes no claim that its subtrees globally minimize the cost-complexity criterion for every penalty or that a validation choice of penalty guarantees test-risk performance.

Empirical tree structure and leaf prediction rules

Subtree loss, leaf count, and weakest-link quotient

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2, printed p. 308

Fix a finite labeled sample, response mode, classification impurity criterion when needed, and finite maximum depth as in greedy CART growth. At any node where the procedure splits, its selected coordinate and midpoint threshold minimize the declared child-weighted empirical loss among all nonempty coordinate-threshold partitions of that node's sample, with the specified lexicographic tie rule. The procedure produces a finite tree of depth at most the maximum depth, with nonempty children at every split. This is a nodewise candidate-optimality result only; it gives no global tree-optimality claim.

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2–9.2.3, printed pp. 307–310

MIT OpenCourseWare, 15.097, Lecture 8: Decision trees, slides 14–16

Let $T_0$ be a finite empirical binary tree with $L_0\ge 1$ terminal nodes and nonempty sample set at every leaf. The weakest-link pruning procedure that repeatedly collapses a current nonterminal node minimizing $g(t)$ terminates at the root leaf after at most $L_0-1$ collapses. This is a termination statement only; it does not assert global cost-complexity optimality.

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2, printed p. 308