S089 · Decision Trees — Gini, Entropy, Splits

Module M11: Classical ML · Session 89 of 130 · Track: ML 🌳

What you'll be able to do after this session

• Explain Decision Trees to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S084 — The ML Mental Model — Features, Labels, Train/Val/Test

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Decision Trees, Clearly Explained — StatQuest — the yes/no picture that clicks in one video.
• 🎥 Deep dive (30–60 min) · Decision and Classification Trees, Clearly Explained — StatQuest — Gini/entropy, splits, pruning, worked by hand.
• 🎥 Hands-on demo (10–20 min) · Decision Trees in Python — Krish Naik — end-to-end sklearn with visualisation.
• 📖 Canonical article · scikit-learn — Decision Trees — the reference implementation notes.
• 📖 Book chapter / tutorial · ISLR ch.8.1 — The Basics of Decision Trees (free PDF) — canonical treatment with worked examples.
• 📖 Engineering blog · Kaggle — Winning solutions almost all use gradient-boosted trees — practical tutorial + why trees dominate tabular ML.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: The most interpretable model.

A decision tree is the simplest possible model that non-experts can actually read. You start at the root, ask a yes/no question about one feature ("is age > 40?"), branch left or right, ask another question, and eventually arrive at a leaf which gives you the prediction. Every leaf is a rectangular region of feature space; the tree carves your data into boxes.

The magic is in how the tree chooses which question to ask at each node. It looks at every possible feature, every possible split threshold, and picks the one that best "separates the classes" — i.e., the split that makes each resulting side more pure than the parent. Two common purity measures:

• Gini impurity = 1 - Σ pᵢ². Zero when the node has only one class. Fast to compute — sklearn's default.
• Entropy = -Σ pᵢ · log₂(pᵢ). Zero when pure, maximal when uniform. Called information gain when we measure the reduction.

Both work almost identically in practice. Split → recurse → split → recurse, until a stopping rule fires (max depth, min samples in leaf, no improvement).

Trees have huge selling points: they handle numeric and categorical features natively, they don't need feature scaling, they capture non-linear patterns and interactions automatically, and they're visually interpretable ("if income > 50k AND age > 35 AND owns house = yes, then default = no"). Banks and regulators love them.

They have one enormous weakness: variance. A single tree memorises the training set and predicts erratically on new data. That's why plain decision trees are rarely used alone in production. The fix is next session — combine hundreds of trees into a forest (S090) or gradient-boosted ensemble (LightGBM/XGBoost — later modules). Trees + averaging is what wins Kaggle.

Gotcha to carry forever: An un-pruned decision tree WILL memorise your training data perfectly and generalise terribly. Always set max_depth, min_samples_leaf, or use cost-complexity pruning.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Here's a tiny tree learning "should I play tennis?" from weather:

Worked example — Gini calculation by hand. Suppose a node has 10 samples: 6 positive, 4 negative. Consider splitting on "age > 30" which sends 5 samples left (4 pos, 1 neg) and 5 right (2 pos, 3 neg).

Before split: Gini_parent = 1 - (6/10)² - (4/10)² = 1 - 0.36 - 0.16 = 0.48.

After split:

• Left: Gini = 1 - (4/5)² - (1/5)² = 1 - 0.64 - 0.04 = 0.32
• Right: Gini = 1 - (2/5)² - (3/5)² = 1 - 0.16 - 0.36 = 0.48
• Weighted: (5/10)·0.32 + (5/10)·0.48 = 0.40

Gain = 0.48 - 0.40 = 0.08. Repeat for every possible feature and threshold; pick the best.

Comparison table:

Regression trees. Same algorithm, different objective: minimise variance (or MSE) instead of Gini. Predict = mean of samples in the leaf.

Pruning. Grow a big tree, then chop back branches that don't help val error. Cost-complexity pruning uses ccp_alpha in sklearn.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Train a decision tree, visualise it, then watch it overfit — and fix that with max_depth.

# pip install scikit-learn matplotlib
import numpy as np
from sklearn.datasets import load_iris, load_breast_cancer
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
 
# ---------- 1. Fit a tiny interpretable tree on Iris ----------
iris = load_iris()
tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(iris.data, iris.target)
print("Iris tree structure:
")
print(export_text(tree, feature_names=list(iris.feature_names)))
 
# ---------- 2. Show overfitting on breast cancer ----------
X, y = load_breast_cancer(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
 
print(f"{'depth':>6} {'train acc':>10} {'test acc':>10} {'gap':>8}")
for d in [1, 2, 3, 5, 8, 15, None]:
    t = DecisionTreeClassifier(max_depth=d, random_state=0).fit(X_tr, y_tr)
    tr = accuracy_score(y_tr, t.predict(X_tr))
    te = accuracy_score(y_te, t.predict(X_te))
    print(f"{str(d):>6} {tr:>10.3f} {te:>10.3f} {tr-te:>8.3f}")
 
# ---------- 3. Use cross-validation to pick depth ----------
from sklearn.model_selection import cross_val_score
best_d, best_score = None, -1
for d in range(1, 20):
    s = cross_val_score(DecisionTreeClassifier(max_depth=d, random_state=0),
                        X_tr, y_tr, cv=5).mean()
    if s > best_score:
        best_d, best_score = d, s
print(f"
CV picks max_depth={best_d}  (val acc={best_score:.3f})")
 
# ---------- 4. Feature importance — free interpretability ----------
best = DecisionTreeClassifier(max_depth=best_d, random_state=0).fit(X_tr, y_tr)
importances = sorted(zip(load_breast_cancer().feature_names, best.feature_importances_),
                     key=lambda t: -t[1])
print("
Top 5 features by importance:")
for name, imp in importances[:5]:
    print(f"  {name:35s} {imp:.4f}")
 
# ---------- 5. Cost-complexity pruning ----------
path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(X_tr, y_tr)
print(f"
CCP alphas explored: {len(path.ccp_alphas)}")
scores = []
for a in path.ccp_alphas[:-1]:
    t = DecisionTreeClassifier(random_state=0, ccp_alpha=a).fit(X_tr, y_tr)
    scores.append((a, accuracy_score(y_te, t.predict(X_te)), t.get_n_leaves()))
best_ccp = max(scores, key=lambda t: t[1])
print(f"Best ccp_alpha={best_ccp[0]:.5f}  test_acc={best_ccp[1]:.3f}  leaves={best_ccp[2]}")

Observe when you run it:

1. export_text prints an actual if-else tree you can read aloud — this is the interpretability win.
2. Depth-None tree hits 100% train accuracy — pure memorisation.
3. Test accuracy peaks around depth 3-5, then flattens or drops with depth. Classic overfitting curve.
4. Sklearn's CV picks a shallow tree; deeper is not better.
5. Feature importance ranks worst radius / worst concave points at the top — same features human doctors focus on.

Try this modification: switch criterion="gini" to criterion="entropy" and rerun the depth sweep. You'll see barely any difference — the two criteria produce nearly identical trees in practice. Then set min_samples_leaf=20 — an alternative regulariser that often works better than max_depth alone.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Where single decision trees are actually deployed. Rarely alone — but as building blocks of RandomForest (S090), XGBoost, LightGBM, and CatBoost, which together power the majority of tabular ML in production. If you can access the internet and Kaggle, look at any tabular competition winner from the last 8 years — 90%+ are boosted tree ensembles.

Interpretability laws are pushing trees. GDPR's "right to explanation", India's DPDP Act, the EU AI Act — all pressure companies toward interpretable models for high-stakes decisions (loans, hiring, healthcare). Shallow trees or SHAP explanations of tree ensembles are the industry go-to.

Handling categorical features. Sklearn's trees historically required numeric encoding (one-hot or label-encoded). CatBoost's big innovation was native categorical handling with target encoding — often the difference between 70% and 78% AUC on real tabular data.

Missing values. Trees can handle missing values naturally by learning "which side to send NaNs" as part of the split. XGBoost defaults to this; sklearn as of 1.3 supports it too via HistGradientBoostingClassifier. Life-changing when your data has 30% missingness.

The "predict the majority class" trap. On imbalanced datasets, an untuned tree will predict the majority class for every leaf. Fix with class_weight="balanced", threshold tuning, or resampling.

Ops story — Airbnb search ranking. For years used GBDTs (gradient-boosted decision trees) as the primary ranker. Simpler than deep learning, easier to explain, easier to iterate. Migrated selectively to deep models only where the data volume justified it.

Trees vs neural nets on tabular data. As of 2025, gradient-boosted trees still generally beat deep learning on tabular data, even with fancy architectures like TabTransformer or NODE. On images/text/audio, deep learning dominates. Rule of thumb: tabular → boost trees; unstructured → deep net.

Common bugs. Forgetting to seed random_state (results change every run), fitting on the whole dataset including test (leakage), using max_depth=None with min_samples_split=2 (overfits catastrophically), interpreting feature_importances_ as causal (it's not — it's just "what the model used", which can be a proxy for the real cause).

(e) Quiz + exercise · 10 min

1. What does a decision tree ask at each internal node, and how does it choose what to ask?
2. Define Gini impurity in one sentence. What is its value for a pure node?
3. Why do decision trees overfit so easily and name three ways to control it.
4. Why don't decision trees require feature scaling?
5. Given a leaf containing samples with classes {A, A, A, B, B}, what does the tree predict for classification? What about regression targets {2, 3, 4, 6, 10}?

Stretch (connects to S033 — Dynamic Programming): Growing a decision tree is a greedy algorithm — each split is locally optimal but not globally. Sketch what a DP-based globally optimal decision tree would look like, and explain why nobody uses it in practice.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Decision Trees? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S090): Random Forest & Bagging
• Previous (S088): Bias–Variance Trade-off & Learning Curves
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.