Decision Trees & Random Forests
The most human model in machine learning: a flowchart that asks yes/no questions until it is confident. Watch data fall through the branches, learn how splits are chosen, and see why a forest beats a tree.
The Ball-Drop Classifier
Think of a decision tree as a Plinko machine for data. Every student is a ball — orange balls pass, ink balls fail — and every gate is a yes/no question. The ball falls, the gate deflects it left or right, and by the time it reaches a bucket, all balls in that bucket share a label. The tree learns by choosing questions that make each bucket as pure as possible.
Every bucket is a leaf · every gate is a learned question
Impurity, Information Gain & Greedy Splitting
A tree is grown top-down, greedily: at every node the algorithm tries every feature and every threshold, and keeps the split that produces the purest children. Purity is measured by:
Probability of mislabeling a random sample. 0 = pure node.
Gini and entropy behave almost identically in practice — scikit-learn defaults to Gini because it skips a logarithm.
Worked example: a node holds 4 pass + 4 fail (Gini = 0.5). Split on “Assignments > 5?” and the children hold 4+0 and 0+4 — Gini drops to 0. That information gain of 0.5 is why the tree asks this question first.
Repeat until pure — or until told to stop.
Measuring Surprise in Bits
Gini is one way to score a split; the original one is entropy. Entropy is the expected surprise of a random draw from the node. A bucket that holds one class surprises nobody; a 50/50 bucket is a coin flip every single time.
p_k is the share of class k in the node. The minus sign is only there because the logarithm of a probability is negative.
The base-2 logarithm is what makes the units bits. counts how many halvings it takes to narrow the field down to one outcome — a number of yes/no questions. Entropy is therefore a question budget, and since every split in a tree is a yes/no question, bits are its natural currency. Change the base and you only rescale that budget.
The parent's entropy minus the size-weighted average of the children's entropies — the bits of uncertainty the question removes.
Read it as a subtraction. A question that leaves its children as confused as the parent gains nothing; one that separates the classes cleanly gains everything. Because the score is always in bits, ID3 can compare wildly different questions — a height threshold against a diameter threshold — on the same scale.
The meter empties · the gain bar fills · then the split resets
One class holds everything. No surprise left to remove, so the tree stops here.
One full bit of uncertainty — the most a two-class node can ever carry.
— the ceiling for K equally likely classes is .
Take the entropy of the node, then try every feature and every cutoff, computing the information gain of each candidate partition.
Choose the partition with the maximum information gain and freeze it into a decision node on that feature and value.
Send each subset down its own branch and repeat the whole procedure there — the same greedy question, one level deeper.
Halt when a node is pure, features run out, or a depth or leaf-size limit is hit — then stamp the leaf with the majority class.
All three answer the same question — how mixed is this node — and in practice they usually crown the same winning split. When they disagree the gap is small; the real differences are cost to compute and how they behave at the extremes.
Overfitting, Depth & Pruning
Left unchecked, a tree keeps splitting until every leaf contains one training point — a perfect scoreboard on the data it memorized, and a disaster on anything new. A deep tree has learned noise, not signal.
The counter-moves are all limits on growth:
In the animation, the orange train error only ever falls as depth grows — but the ink test error turns around and climbs. The sweet spot is the bottom of that U, and Topic 05's cross-validation is how we find it.
Depth 1 = underfit · depth 20 = memorized the noise
Random Forests: Bagging + Voting
Each tree sees a bootstrap sample & a random feature subset
One deep tree is a nervous genius; a forest of slightly wrong trees is a calm committee. A random forest trains hundreds of trees on deliberately corrupted views of the data so their mistakes don't correlate:
Each tree trains on a random sample with replacement — about 63% unique rows, the rest are duplicates. Every tree sees a slightly different dataset.
At every split, only random features may compete. This stops one dominant feature from making all trees identical.
Classification = majority vote; regression = average of predictions. Variance shrinks roughly with for trees — while bias stays low.
Bonus: the ~37% of rows each tree never saw (out-of-bag) form a free validation set — cross-validation built into the training loop.
When to Reach for Trees
- · No scaling or normalization needed
- · Handles mixed & missing data gracefully
- · Captures non-linear interactions automatically
- · Fully interpretable (single tree)
- · Feature importance for free
- · Single trees overfit easily
- · Axis-aligned splits struggle on smooth diagonal boundaries
- · Forests lose the interpretability
- · Can't extrapolate beyond training range
- · Larger memory than linear models
- · n_estimators — more is safer, slower
- · max_depth — the overfit dial
- · max_features — decorrelation dial
- · min_samples_leaf — smoothing dial
Gradient boosting (XGBoost, LightGBM) grows trees sequentially, each one correcting the previous ensemble's residuals — it is the same ball-drop machinery aimed at what the committee still gets wrong. And when features become images or sequences instead of a tidy table, trees struggle and the neural networks of Topics 07–09 take over.