Decision Trees & Ensembles
From interpretable trees to powerful ensembles
Decision Trees
Trees split feature space into regions to minimize impurity or error. They are easy to interpret but prone to overfitting.
Algorithm (ID3/CART):
- If node is pure or max depth reached → make leaf (majority class/mean).
- For each feature, compute split score (info gain/Gini/MSE).
- Pick best split; partition data; recurse on children.
Splitting Criteria
- Classification: Gini impurity, Information Gain (Entropy)
- Regression: Mean Squared Error reduction
Entropy(S) = - Σ pᵢ log₂ pᵢ
Gini(S) = 1 - Σ pᵢ²
InfoGain = Entropy(parent) - Σ (|Sᵥ|/|S|) Entropy(Sᵥ)
Pruning
Reduce overfitting by simplifying the tree.
- Pre-pruning: max depth, min samples split/leaf, min impurity decrease.
- Post-pruning: cost-complexity pruning using validation set (CART α parameter).
Random Forests (Bagging)
Ensemble of trees trained on bootstrap samples with feature subsampling.
- Reduces variance; robust to noise and overfitting.
- Out-of-bag (OOB) error as internal validation.
- Feature importance via impurity decrease or permutation.
Gradient Boosting
Build trees sequentially, each new tree fits the negative gradient (residuals) of the loss.
Initialize F₀(x) = argmin₍γ₎ Σ L(yᵢ, γ)
For m=1..M:
rᵢ = - [∂L(yᵢ, F(xᵢ)) / ∂F] evaluated at F=Fₘ₋₁
Fit tree hₘ(x) to rᵢ
Fₘ(x) = Fₘ₋₁(x) + η hₘ(x) // learning rate η
Popular libraries: XGBoost, LightGBM, CatBoost.
Quick Revision
- Decision tree splits: Entropy/Gini formulas.
- Pruning: pre vs post-pruning; control depth/min samples.
- Ensembles: RF reduces variance; Boosting reduces bias via sequential residual fitting.