Decision Trees

A decision tree is the simplest model that still feels like reasoning. It asks a sequence of yes or no questions about the features, "is petal length below 2.5 cm?", "is income above 60k?", and each answer walks you down to a leaf that holds a prediction. No weights, no gradient descent, no calculus at inference time. Just a nested set of if statements the model discovered on its own.

That simplicity is not a toy. The ensembles built from trees, random forests and gradient boosting, still win the majority of Kaggle competitions on tabular data and quietly power fraud detection, credit scoring, and ranking systems in production. Before you can understand those ensembles, you have to understand the single tree they are made of. This lesson is that tree: how it picks a split, the two classic recipes for scoring a split (Gini and entropy), the knobs that stop it from memorizing the training set, and the failure modes a deep-learning engineer needs to name in an interview.

The one question every tree keeps asking

Growing a tree is a single operation applied over and over: take a group of samples and split it into two groups that are each more "pure" than the parent. A pure group is one where almost every sample shares the same label, because then the tree can confidently predict that label and stop.

So the whole algorithm reduces to two questions:

1. How do we measure how mixed a group of labels is? (impurity)
2. How do we compare candidate splits so we can pick the best one? (information gain)

Answer those two and you have built a decision tree.

Play with the split step directly. In the builder below, pick a feature and drag the threshold. Each cut carves the plane into two axis-aligned regions, and the readout shows the impurity of each region and the information gain the cut buys you. Press Find best split to let the greedy search scan every candidate and land on the largest gain, exactly what the algorithm does at each node.

Notice three things while you play. First, the split lines are always axis-aligned: a tree can only ask about one feature at a time, so its regions are rectangles, never diagonals. Second, the best cut is the one that leaves each side as pure as possible. Third, once you split, you can split again inside a region, and that recursion is what lets a shallow-looking tree carve out surprisingly complex shapes.

Measuring impurity: Gini and entropy

We need a function that takes the class proportions in a node and returns a single "how mixed is this" score. Two functions dominate, and they agree on the essentials.

Let a node hold samples from $C$ classes, and let $p_i$ be the fraction of the node that belongs to class $i$.

Gini impurity is the probability that you misclassify a random sample if you label it by drawing from the node's own class distribution:

Entropy is the average number of bits needed to encode the class of a sample, borrowed straight from information theory:

For a two-class node with positive fraction $p$, these become $G = 2p(1-p)$ and $H = -p\log_2 p - (1-p)\log_2(1-p)$. Both share the same shape: zero at a pure node ($p = 0$ or $p = 1$) and maximum at a perfect 50/50 mix. Gini tops out at $0.5$; entropy tops out at $1$ bit. Drag the mix below and watch both rise and fall together.

The two curves almost never disagree about which split is better, so the choice between them is rarely about accuracy. Gini is slightly cheaper (no logarithm) and is scikit-learn's default; entropy is the one from classic information theory and the original ID3 algorithm. Treat them as two dialects of the same idea: lower is purer.

Information gain: scoring a split

Impurity scores a single node. To score a split, we compare the parent's impurity against the combined impurity of its children, weighted by how many samples fall into each:

Here $n$ is the number of samples at the parent, $n_k$ the number in child $k$, and $H$ can be entropy (for information gain proper) or Gini (then it is usually called the "Gini decrease"). The weighting matters: a split that produces one tiny pure child and one huge messy child barely helps, and the $n_k/n$ factors say so. The greedy tree evaluates this quantity for every feature and every candidate threshold, then keeps the split with the largest gain.

One split, computed by hand

Take a node of 10 samples: 6 positive (churned) and 4 negative (stayed). We test the split "tenure $\le 12$ months?" which sends 5 samples left and 5 right.

Step 1, parent impurity. With $p = 0.6$:

Step 2, child impurities. The left child is $20/80$ and the right child is pure:

Step 3, weight and subtract. Each child holds half the samples, so the weights are $5/10 = 0.5$:

Both scores agree the split is excellent: it drops Gini by $0.32$ and buys $0.61$ bits of information, largely because it isolates a perfectly pure right child. This is the exact arithmetic the builder above runs for every candidate cut. You can reproduce it in NumPy in a few lines:

CART vs ID3: two recipes, one idea

The measurement and the search combine into named algorithms. You will hear two in interviews.

The important takeaway is that they differ in the impurity function and the branching style, not in the core loop. Both are greedy: at each node they pick the single best split available right now and never look back.

Because a tree can only cut on one axis at a time, the boundary it learns is a staircase of rectangles. That is worth seeing directly. The visual below shows how a set of axis-aligned decisions partitions a 2D feature space, the same rectangular carving the builder produced, now on a denser problem.

The knobs: hyperparameters that stop overfitting

Left alone, a tree will keep splitting until every leaf is pure, which usually means one training point per leaf. That tree has memorized the training set and will generalize terribly. The cure is to constrain it. These are the hyperparameters a deep-learning engineer reaches for most:

The first two are pre-pruning (stop early); ccp_alpha is post-pruning (grow, then cut back). Post-pruning often generalizes better because a split that looks weak on its own can enable a strong split beneath it, and pre-pruning would never discover it.

Watch overfitting appear as you unleash depth. The playground below sweeps max_depth on a noisy make_moons problem and prints train and test accuracy side by side. Train accuracy climbs monotonically toward 1.0; test accuracy peaks and then sags. That gap is the tree memorizing noise.

See the whole thing run: fit, score, and read the tree

Here is a full decision tree end to end in scikit-learn: fit on the two-moons dataset, print train and test accuracy, then plot both the axis-aligned decision regions and the tree itself with plot_tree. Read the tree from the root: each box shows the split test, the Gini impurity, the sample count, and the class distribution. Change max_depth and rerun to watch the regions get jagged.

Where a single tree breaks

Trees are interpretable and fast, but a lone tree has real weaknesses. Naming them is standard interview fare, and every one of them motivates the ensembles later in this section.

Interview readiness