Decision Tree Pruning with Cost-Complexity

MediumClassical ML

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), or None for 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.

Related free problems