decision tree

A decision tree predicts an outcome by asking a sequence of yes-or-no questions about the data, branching at each answer, until it reaches a leaf that holds the prediction — the same structure Kaggle's famous Titanic tutorial dataset uses to teach the method, where a tree built from 891 passenger records learns, entirely on its own, that asking "is this passenger female?" first is the single most informative question it could ask, because 74% of women aboard survived against just 19% of men. Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone formalized the modern CART algorithm in their 1984 book, and Ross Quinlan's ID3 (1986) and its successor C4.5 (1993) are the other lineage that shaped how trees are built today — both approaches reduce to the same core question asked over and over: which feature, and which threshold, best separates the data at this node.

Gini impurity and entropy are both ways of scoring how "mixed" a node's labels are, and a concrete node makes the arithmetic obvious. A node holding 10 passengers where 3 survived and 7 did not has a Gini impurity of 1 minus the sum of each class's squared proportion — 1 minus (0.3 squared plus 0.7 squared), which works out to 0.42; a node that is entirely one class scores 0 (perfectly pure), and a 50/50 split of two classes scores 0.5 (maximally impure for two classes). Entropy, used by ID3 and C4.5, measures the same intuition in information-theoretic bits instead, but both criteria do the identical job: at every candidate split, the tree computes how much the weighted impurity of the two resulting children drops compared to the parent, and picks whichever feature and threshold produces the biggest drop.

Left unconstrained, a tree will keep splitting until every leaf is pure, which is memorization rather than learning. A tree grown with no depth limit can carve out a leaf for every unique combination in the training set, reaching 100% training accuracy while generalizing badly to new data — the standard defenses are capping the max depth, requiring a minimum number of samples before a leaf is allowed to split further, and pruning, which grows a full tree first and then removes branches that fail to improve accuracy on a held-out validation set (see validation-set). None of these controls change what the tree is doing at each node; they only change how long it is allowed to keep doing it.

A single decision tree's biggest strength — full interpretability — is also exactly what limits its accuracy ceiling. Because every prediction traces back to a short, readable chain of if-then rules, a tree can be printed and explained to a non-technical stakeholder in a sentence, which is rare among competitive ML models; but any one tree is also high-variance, meaning small changes to the training data can produce a noticeably different tree. That instability is precisely the property that random forest and gradient boosting exploit — both build many trees rather than relying on one, a design choice covered in its own right where it belongs rather than repeated here.

The Titanic example earns its place as the field's go-to teaching case because it shows the mechanism with no hand-waving: the tree is never told that lifeboat policy favored women and children, it only ever asks "which single yes-or-no question about this row most reduces how mixed the survival outcomes are in the resulting groups" — and answering that question honestly, split after split, is the entire algorithm.