Cost-complexity criteria for subtrees

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.