Decision trees

One split is a stump. Keep splitting and you get a tree.

The flowchart model: nonlinear, multi-class, no scaling — and prone to overfit.

From stump to tree

Week 1: one line on one feature. A decision stump.
A tree is that same split, applied recursively inside each region it carves.
max_depth=1 build_tree is the week-1 classifier.
Ask a yes/no question, split, then ask a fresh question in each half.

The data

Iris in 2-D: petal length vs width, three species. Setosa is one free cut away.

The math

Gini impurity — the chance you'd mislabel a random draw:

G = 1 - \sum_{k} p_k^{2}

A split's worth is the size-weighted impurity it removes:

\Delta(j, t) = G(\text{parent}) - \frac{|L|}{N}\,G(L) - \frac{|R|}{N}\,G(R)

Train a node by the argmax over every feature and threshold. That's the week-1 search, run over all features and again inside each child.

Watch it carve

Every frame is one real split, best-first. The plane gets chopped into boxes, each shaded by the class it predicts. Seven splits, training accuracy 0.993.

The overfitting gap

Train accuracy climbs to 0.998. Test accuracy peaks at 0.736 (depth 4), then falls to 0.662. Every split past depth 4 memorizes noise.

Scratch vs. library

DecisionTreeClassifier(max_depth=4) grows the same tree: 0.736 test, 16 leaves, identical to ours. On noisy Pima, three levels of tree beat the week-1 stump (0.732) by four thousandths — depth isn't free accuracy.

Takeaways

A tree is a stump you didn't stop building — recursive greedy splits.
Reach for it: readable model, mixed feature types, no scaling, nonlinear boundary.
Don't trust one deep tree: it memorizes. Cap depth, prune.
The payoff is the pile: average many trees → random forests; sequence them → boosting. Next chapters.