Handbooks / Machine Learning Basics / Chapter 4

Decision Trees and Ensembles

7 pages · ~5 min✓ Reviewed

Builds on Model Evaluation. Next up: Neural Network Basics.

Machine Learning BasicsPage 1

Decision Trees: The Mental Model

1. What a Tree Is

Recursive split: one feature, one threshold at a time
Leaf predicts the majority class (classification)
Leaf predicts the mean target (regression)

Test x <= tbest split
Recurseeach child
Leafmajority / mean

2. How It Grows

Feature	Split test
Numeric	`x <= t`
Categorical	subset or one-vs-rest

Greedy top-down: best local gain, no look-ahead
So the tree is not globally optimal
No limit: splits until leaves are pure
Result: zero training error, high variance (overfit)

3. Strengths and Limits

Strength	Limit
No feature scaling	Axis-aligned boundaries
Non-linear interactions	Unstable to small data changes

Remember

An unconstrained tree memorises the training set: 0 train error, weak test score.

Machine Learning BasicsPage 2

Gini vs Entropy Splits

1. Impurity and gain

	Gini	Entropy
Formula	1 - sum(p_i^2)	-sum(p_i * log2 p_i)
Pure node	0	0
Balanced binary	max 0.5	max 1 bit

Information gain = parent impurity - weighted average of children's impurity
The split with the highest gain wins

2. Worked example

Node: 5 positives, 5 negatives → Gini 0.5, entropy 1.0
Split into (4,1) and (1,4): each child Gini 0.32

Parent (5+, 5-)Gini 0.5
(4,1) and (1,4)child Gini 0.32
Gain0.5 - 0.32 = 0.18

3. Gini vs entropy

Criterion	Note
Gini	cheaper (no log), near-identical trees
Entropy	penalizes mixed nodes slightly more
Regression trees	variance (MSE) reduction instead

Mistake

Raw gain favors high-cardinality features like IDs. Use gain ratio or drop ID-like columns.

Machine Learning BasicsPage 3

Pruning and Controlling Tree Depth

1. Pre vs post pruning

Pre-pruning stops growth early: max_depth, min_samples_split, min_samples_leaf, min_impurity_decrease
Post-pruning grows the full tree, then cuts weak subtrees
sklearn post-pruning = cost-complexity via ccp_alpha

	Pre-pruning	Post-pruning
Speed	faster	costlier
Sees full tree	no	yes
Risk	stops too early	none from stopping

2. Cost-complexity

Minimize error + alpha * leaves
Larger alpha → smaller tree
alpha=0 → full tree kept
Get candidates with cost_complexity_pruning_path, then cross-validate

python

from sklearn.model_selection import cross_val_score
path = DecisionTreeClassifier().cost_complexity_pruning_path(X, y)
best = max(path.ccp_alphas, key=lambda a: cross_val_score(
    DecisionTreeClassifier(ccp_alpha=a), X, y, cv=5).mean())

alpha picked by CV, never by the test set

3. Picking alpha safely

1Pruning pathcandidate alphas
2Cross-validatescore each alpha
3Refitbest alpha, all train data

Mistake

Tuning depth or alpha on the test set leaks it. Tune with CV; touch the test set once.

Machine Learning BasicsPage 4

Bagging and Random Forests

1. Bagging and OOB

Bagging: train trees on bootstrap samples, average or vote
Cuts variance, bias stays the same
Each bootstrap skips ~36.8% of rows (1/e)
Those OOB rows give a free score: oob_score=True

2. Random Forest vs Bagging

	Bagging	Random forest
Features per split	all p	random subset
Tree correlation	high if strong features dominate	lower
Ensemble variance	higher	lower

Rule of thumb max_features: sqrt(p) classification, p/3 regression
sklearn regressor default is 1.0 (all features): tune it

3. Tuning and Mistakes

n_estimators: more never overfits, only slower
max_features: lower decorrelates more
min_samples_leaf: larger smooths leaves

Mistake

Shallow trees: forests need deep, low-bias trees.

4. Interview Point

Why does OOB work? Each tree never saw ~36.8% of rows
Why random features? Decorrelates trees, lowering variance
Do more trees overfit? No, only slower

Machine Learning BasicsPage 5

Boosting: AdaBoost, Gradient Boosting, XGBoost

1. Core idea

Weak learner = barely better than chance; stump = depth-1 tree
Trained sequentially, each fixing the previous errors
Mainly cuts bias; bagging cuts variance

2. Three methods

Method	Each round	Rule
AdaBoost	Upweights misclassified samples	alpha = 0.5 * ln((1 - err) / err)
Gradient boosting	Tree fits negative gradient (residuals for squared error)	F = F + learning_rate * tree

XGBoost objective is regularized: L1/L2 on leaf weights
gamma penalty per split
Second-order gradients
Histogram split finding
Built-in missing-value handling

3. Knobs and mistakes

Low rate, many rounds, early stop; max_depth 3-8, subsample, colsample_bytree

python

from xgboost import XGBClassifier
m = XGBClassifier(learning_rate=0.05,
    n_estimators=1000, max_depth=4,
    subsample=0.8, colsample_bytree=0.8,
    early_stopping_rounds=50)
m.fit(X_tr, y_tr, eval_set=[(X_val, y_val)])

fragment: X_tr, y_tr, X_val, y_val are your split

Boosting overfits

Fitting residuals round after round eventually fits noise. High rate or too many rounds without early stopping overfits; a forest does not.

Machine Learning BasicsPage 6

Feature Importance and Tree Models Cheat Sheet

1. Feature Importance

Method	How	Data	Catch
`feature_importances_`	Sums impurity decrease per feature	Train	Biased to high-cardinality
Permutation	Shuffle one feature, measure score drop	Held-out	Fails with correlated features
SHAP	Additive attribution per prediction	Any rows	Needs an explainer

TreeExplainer is fast for tree ensembles
Impurity importance is also biased to continuous features

python

explainer = shap.TreeExplainer(model)
sv = explainer.shap_values(X_test)

call-site fragment: needs import shap and a fitted tree model

2. Which Model

Model	Effect	Trait
Single tree	High variance	Interpretable
Random forest	Variance down	Robust defaults
Boosting	Bias down	Best accuracy; tune, early stopping

3. Formulas

Gini = 1 - sum(p^2)
Entropy = -sum(p log2 p)
Gain = parent minus weighted children
OOB share = 36.8% of rows per bootstrap

Remember

Trust permutation or SHAP over impurity importance when features differ in cardinality.

Machine Learning BasicsPage 7

Check yourself

A node has 5 positives and 5 negatives (Gini 0.5). A split gives (3,2) and (2,3). What is the gain?

Each child: 1 - (0.36 + 0.16) = 0.48
Weighted average is also 0.48
Gain = 0.5 - 0.48 = 0.02, a weak split

A forest keeps improving up to 500 trees, but boosting at 2000 rounds gets worse on validation. Why?

Forest trees are averaged, so more trees only cut variance
Boosting keeps fitting residuals, so it ends up fitting noise
Fix: lower learning_rate, use early_stopping_rounds

You bootstrap 1000 rows for one tree. About how many rows are left out, and what are they for?

Each row is missed with chance (1 - 1/n)^n, about 36.8%
So roughly 368 rows are out-of-bag
They score the tree for free: oob_score=True