Concept30 min

Decision Trees

How does a tree choose its questions, and why does a deep tree memorise noise?

The situation

A lender wants loan rules it can read, learned from 160 past borrowers. The interviewer asks:

How does a decision tree choose its splits?

Running example: a lender's loan book, simulated: 160 past borrowers with annual income (₹ lakh) and credit score, and whether they repaid. The true rule is a mix of thresholds, plus 10% label noise (people are unpredictable). Test accuracy is measured on 600 new applicants. A second, 1-D example (delivery time vs distance) shows regression trees.

A loan officer's rules, learned from data

An experienced loan officer thinks in rules: "score above 690 and income above ₹6 lakh: approve; score above 780: approve almost regardless; otherwise, be careful." A linear model can't express "and" and "otherwise" without hand-built features. A decision tree learns exactly this kind of nested rule directly from past borrowers, and you can print it and read it.

The idea

Think of a game of twenty questions. Each yes-or-no question splits the group, and you always ask whichever question leaves each side the least mixed. Then you repeat on each side.

Illustrative, based on the lesson's loan officer rules.

Play

Try to break it. Move the threshold until the weighted Gini is as low as you can get it, then snap to the best split. Then switch to the other feature.

Find the best split yourself

Move the threshold, watch the impurity

Threshold

left: n, Gini

–

right: n, Gini

–

weighted Gini G (parent )

–

best possible on this feature

–

The algorithm does exactly this for every feature, sorts the values once, and sweeps the threshold, which costs about O(features × n log n) per level docs. Then it recurses on each child.

Now say why: why does the algorithm prefer this threshold, and which feature would it choose first?

Maths

In one breath

A decision tree asks a sequence of yes/no questions ("credit score > 690?", "income > ₹6 lakh?") and predicts the majority class (or the mean value) of whatever ends up in each leaf. It's built greedily: at every node, try every feature and threshold and keep the split that most reduces impurity (Gini, entropy, or squared error). Grown fully, a tree memorises the training data, so you limit depth, require minimum leaf sizes, or prune. Trees are readable, need almost no preprocessing, and handle non-linear patterns; they're also unstable and blocky, and those weaknesses are exactly what Random Forest and Gradient Boosting fix.What you'll be able to do after this: compute a split by hand, explain Gini vs entropy, show why a deep tree overfits, describe pruning, and say what trees are bad at.

repaid / "yes" regiondefaulted / "no" regionsplit / the modelimpurity numberstest data

Nodes, splits, leaves, and impurity

A node holds some borrowers and asks one question about one feature: x_j ≤ t? Yes goes left, no goes right. A leaf stops asking and predicts the share of repayers there (classification) or the mean target (regression). To choose questions, we need a number for how mixed a node is, its impurity. For a node where a share p repaid:

scikit-learn's impurity definitions tree guide.

Share of repayers in a node, p

All three are 0 for a pure node and peak at 50/50. Gini and entropy are curved (strictly concave), so a split that makes one child purer always reduces them a bit; plain misclassification error is flat-sided and often can't tell good splits apart. Gini and entropy almost always pick the same split; Gini is slightly cheaper (no logarithm). my take

One principle

Greedily pick the split that reduces impurity the most

scikit-learn's formulation tree guide. Greedy because finding the globally best tree "is known to be NP-complete", so practical algorithms choose the locally best split at each node.

Pruning

Grow big, then cut back the weakest branches

Stopping rules (max depth, min leaf size) decide early and can miss a useful split hiding behind a weak one. CART's alternative: grow a large tree, then prune it with minimal cost-complexity pruning:

scikit-learn: "A non-terminal node with the smallest value of α_eff is the weakest link and will be pruned" tree guide. Choose α by cross-validation (scikit-learn's cost_complexity_pruning_path lists the candidate α values).

Regression trees

Predict numbers with a staircase

max_depth

training MSE

–

test MSE (300 new)

–

noise floor (best possible)

≈ 2.25

Delivery time vs distance with a rush-hour bump around 6 km (simulated). Split by squared error; each leaf predicts the mean of its points, so the fit is a step function. Depth 3–4 follows the bump; depth 10 chases noise. Beyond 10 km the tree just repeats its last step: trees "are not good at extrapolation" docs.

In practice

CART, ID3, C4.5

Algorithm	Splits	Notes
ID3 (Quinlan, 1986)	Multi-way, categorical features only	Information gain (entropy)
C4.5 / C5.0 (Quinlan)	Multi-way; discretises continuous features	Gain ratio; converts trees to if–then rule sets
CART (Breiman et al., 1984)	Always binary	Gini or entropy for classification, squared error for regression; cost-complexity pruning. scikit-learn "uses an optimized version of the CART algorithm"

Summary from scikit-learn's tree guide docs. Every modern tree ensemble (Random Forest, XGBoost, LightGBM, CatBoost) is built on CART-style binary trees.

In practice

Scaling, categories, missing values, importance

No scaling needed

Splits compare a feature with a threshold, so any monotonic transform (log, standardise) gives the same tree. Trees "require little data preparation" docs.

Categorical features

CART can split a category set into two groups; scikit-learn's trees currently need encoding (one-hot or ordinal). LightGBM, CatBoost and scikit-learn's HistGradientBoosting handle categories natively.

Missing values

scikit-learn trees support NaN with splitter='best': the training split decides which side missing values go to; if none were seen, they go "to the child with the most samples" docs.

Feature importance

Impurity-based importance (total impurity decrease per feature) is free but biased toward high-cardinality features and computed on training data. Prefer permutation importance on held-out data for decisions. my take

Training a single tree you can trust

Start shallow (scikit-learn suggests max_depth=3) to read the structure.
Tune max_depth, min_samples_leaf (try 5) or ccp_alpha with cross-validation.
For imbalanced classes, use class weights or balanced sampling; trees "create biased trees if some classes dominate".
Inspect: print the rules (export_text), check that the splits make domain sense.
If accuracy matters more than one readable tree, move to an ensemble: Random Forest (variance) or Gradient Boosting (bias).

A single tree, or something else?

Use a single tree when

The rules themselves are the product (eligibility checks, triage guidelines)
You need a quick, explainable baseline
Regulation demands a transparent model and a small tree is accurate enough

Use an ensemble when

Accuracy matters most: gradient boosting is the tabular default
You want robustness with little tuning: Random Forest
Smooth or linear relationships: consider linear models too

The answer that sounds right

The trap

"Keep splitting until every leaf is pure"

With enough questions you can isolate every borrower in their own leaf: 100% training accuracy. But 10% of the labels are noise, so a tree that fits every point has memorised the noise. In the lab below, training accuracy climbs to 100% as depth grows, while test accuracy peaks at depth 4 (≈ 84.5%) and then falls. scikit-learn: decision trees "can create over-complex trees that do not generalize the data well. This is called overfitting" tree guide.

Grow it, and watch it overfit

Each split adds a rectangle

max_depth min_samples_leaf

leaves

–

training accuracy

–

test accuracy (600 new)

–

Every boundary is horizontal or vertical: each split looks at one feature. Deep trees carve tiny boxes around single noisy borrowers. Raising min_samples_leaf (no leaf may hold fewer than m borrowers) is a gentler brake than capping depth; scikit-learn suggests "min_samples_leaf=5 as an initial value" docs.

Instability

A slightly different sample, a different tree

–

Four samples of 160 borrowers from the same population, a depth-4 tree on each. The top split stays near a credit score of 690, but the lower boxes move around a lot. scikit-learn: "small variations in the data might result in a completely different tree being generated. This problem is mitigated by using decision trees within an ensemble" docs. High variance is the price of flexibility, and averaging many trees (Random Forest) is the cure.

Strengths and weaknesses, side by side

Strengths

Readable rules ("white box")
Captures interactions and thresholds automatically
No scaling; mixed feature types; fast prediction (O(depth))
The building block of the strongest tabular models

Weaknesses

Overfits unless constrained
Unstable: small data changes, different tree
Axis-aligned, blocky boundaries; a diagonal boundary needs many steps
Can't extrapolate; struggles with XOR / parity-type patterns

Say it

How does a decision tree choose its splits?

Say your answer out loud

Aim for 30 seconds. It feels different from reading it, and that's the point.

Tick what you covered

A tree recursively splits the data with yes-or-no questions on single features.
At each node, it greedily picks the feature and threshold that most reduce impurity.
Impurity is Gini or entropy for classification, and squared error for regression.
Fully grown trees overfit, so you limit depth or leaf size, or prune.
Trees are readable and need no scaling, but they're unstable and can't extrapolate.