Concept - Decision Tree Pruning

Why (s.335): a full tree overfits noise; prefer the simplest hypothesis that fits the data.

I. Pre-pruning: stop growing given stopping criteria (s.336)

• Minimum samples for a node split (min_samples_split)
• Minimum samples for a terminal node / leaf (min_samples_leaf)
• Maximum depth of tree (max_depth)
• also max_features (number of features considered per split) in the figure
• Example: root 100 samples -> split a<1/a>=1; leaf (30, label 1); node (70) -> split b<=10/b>10 -> leaves (30, label 1) and (40, label 2).

II. Post-pruning (s.337)

1. Split data into training and validation set.
2. Build a full tree that classifies the training data.
3. Until further pruning is harmful: greedily remove the node that most improves validation set accuracy.

Figure: train accuracy rises with nodes (~0.80 to ~0.98), test accuracy peaks near ~55 nodes (red dotted line, ~0.79) then falls.

Related

Concept - Overfitting | Concept - Decision Tree

Source chunk: 03 Text Classification - Chunk 12 (s.331-360)