Weakest-link pruning of a finite tree

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