Decision Tree Pruning with Cost-Complexity
Problem statement
Cost-complexity pruning (minimal cost-complexity, or weakest-link pruning) is a post-pruning method that trades a tree's training error against its size. For every internal node it computes an effective alpha: the complexity penalty per leaf at which collapsing that node's subtree into a single leaf becomes worthwhile.
Implement compute_pruning_alphas(tree) that returns the effective alpha of every internal node, sorted ascending.
The tree is a nested dictionary. Every node has the keys:
'samples': number of training samples reaching the node'errors': misclassification count if this node were turned into a leaf'left','right': child subtrees (dicts), orNonefor a leaf
A node is a leaf when both children are None; every internal node has two children. For an internal node $t$ with subtree $T_t$:
$$\alpha_{\text{eff}}(t) = \frac{R(t) - R(T_t)}{|T_t| - 1}$$
where $R(t)$ is the node's own errors, $R(T_t)$ is the sum of errors over all leaves of the subtree, and $|T_t|$ is the number of leaves in the subtree. Round each alpha to 4 decimals. A tree that is a single leaf has no internal nodes, so return [].
Example
Input:
tree = {'samples': 200, 'errors': 80,
'left': {'samples': 120, 'errors': 30,
'left': {'samples': 70, 'errors': 10, 'left': None, 'right': None},
'right': {'samples': 50, 'errors': 15, 'left': None, 'right': None}},
'right': {'samples': 80, 'errors': 25, 'left': None, 'right': None}}
compute_pruning_alphas(tree)
Output:
[5.0, 15.0]
Reasoning: Left internal node: $R(t) = 30$, its leaves have $10 + 15 = 25$ errors over 2 leaves, so $\alpha = (30 - 25)/(2 - 1) = 5$. Root: $R(t) = 80$, leaves have $10 + 15 + 25 = 50$ errors over 3 leaves, so $\alpha = (80 - 50)/(3 - 1) = 15$. The node with $\alpha = 5$ is the weakest link and is pruned first.
Show hint
What does the penalized objective look like if you compare keeping a subtree with collapsing it to one leaf?
Relevant roles: ML Engineer, Data Scientist and Applied Scientist.