Decision Trees (DT)

Definition

A decision tree is a supervised learning model that predicts by asking a sequence of yes/no questions about the input — "prior default? income above $51,500?" — until it reaches a leaf that holds an answer. The structure is obvious. The only non-obvious part, and the thing worth reading a page about, is how the tree chooses each question, because nobody writes those questions down. The algorithm invents them by brute force: at every node it enumerates every feature and every threshold, scores each candidate split by how much it reduces the mixing of the labels, and keeps the winner.

That score has a name — impurity — and it is one line of arithmetic you can do in your head. Everything else about trees (depth limits, pruning, why a single tree is unstable, why forests exist) follows from the fact that the choice is made greedily, one node at a time, with no way to look ahead. This page works one split all the way through on ten rows of data so you can see the numbers that decide it.

How It Works

The number the tree is minimising

The most common impurity measure is Gini impurity. For a node containing a mix of classes, where p₁, p₂, … are the fractions of the node belonging to each class:

Gini = 1 − (p₁² + p₂² + … )

That is the whole formula. Read it as: the probability that two rows pulled at random from this node have different labels. A node where every row shares one label scores 0 — pull two rows, they always agree. A node split evenly between two classes scores 1 − (0.5² + 0.5²) = 0.5, the worst a two-class node can do. Everything in between is a number telling you how mixed the node is.

The tree's goal at every node is to find the split whose children are, on average, purer than the parent. The reduction is the gain:

gain = impurity(parent) − [ (n_left/n) × impurity(left) + (n_right/n) × impurity(right) ]

The weighting matters. A split that carves off two perfectly pure rows out of a thousand is nearly useless, and the n/n weights say so by shrinking its contribution to almost nothing.

A worked split: two candidates, one winner

Here are ten loan applicants. Two features — annual income and whether the applicant has a prior default on record — and one label, whether the loan was repaid.

The parent node. All ten rows: 6 repaid, 4 defaulted, so p = 0.6 and 0.4.

Gini(parent) = 1 − (0.6² + 0.4²) = 1 − (0.36 + 0.16) = 0.48

Candidate 1 — split on prior default. The "yes" branch takes B, C, E, I: 1 repaid out of 4. The "no" branch takes A, D, F, G, H, J: 5 repaid out of 6.

Gini(yes) = 1 − ((1/4)² + (3/4)²) = 1 − (0.0625 + 0.5625) = 0.375
Gini(no)  = 1 − ((5/6)² + (1/6)²) = 1 − (0.6944 + 0.0278) = 0.2778

weighted  = (4/10 × 0.375) + (6/10 × 0.2778) = 0.15 + 0.1667 = 0.3167
gain      = 0.48 − 0.3167 = 0.1633

Candidate 2 — split on income at $51,500. (That threshold is not arbitrary; the next section explains where it comes from.) Below it sit A, B, C, D, E: 2 repaid out of 5. At or above it sit F, G, H, I, J: 4 repaid out of 5.

Gini(low)  = 1 − (0.4² + 0.6²) = 1 − (0.16 + 0.36) = 0.48
Gini(high) = 1 − (0.8² + 0.2²) = 1 − (0.64 + 0.04) = 0.32

weighted   = (5/10 × 0.48) + (5/10 × 0.32) = 0.24 + 0.16 = 0.40
gain       = 0.48 − 0.40 = 0.08

Prior default wins, 0.1633 against 0.0800 — twice the gain — so it becomes the root of the tree, and the income question is pushed down into whichever branch still needs it. Notice that the low-income child scored 0.48, identical to the parent: that half of the split learned literally nothing, and it drags the weighted average up. A split is only as good as its worse child.

If you prefer entropy to Gini, the same table gives Entropy(parent) = 0.971 bits and an information gain of 0.256 bits for the prior-default split — a different unit, the same winner. The two measures agree on the vast majority of real splits; Gini is the default in scikit-learn because it avoids a logarithm per candidate.

Continuous features: sort, then test the gaps

A tree has no concept of "income" as a quantity. It converts a continuous feature into a finite set of yes/no questions by sorting the values and testing the midpoints between consecutive distinct ones. The ten incomes above — 22, 28, 31, 39, 45, 58, 61, 74, 88, 96 — give nine candidate thresholds: 25, 29.5, 35, 42, 51.5, 59.5, 67.5, 81, 92. The tree scores all nine and keeps the best. In this data that best is 51.5, the midpoint of 45 and 58, worth a gain of 0.08; the next best candidates, 25 and 92, are worth only 0.036 each.

Two consequences fall straight out of this. First, trees never need feature scaling: only the order of the values matters, so standardising income, taking its logarithm, or measuring it in yen produces an identical tree. That is a real advantage over anything distance-based or gradient-trained. Second, the cost of a node is a sort plus a linear scan — for m features and n rows, roughly m × n log n at the root — which is why fitting a tree on tabular data is fast enough that ensembles of hundreds of them are practical.

Where the splitting stops, and why depth is the knob

Left alone, the recursion does not stop until every leaf is pure. It always can: give a leaf one row and its impurity is 0. On a 10,000-row training set that means up to 10,000 leaves, one per example, and zero training error — the tree has memorised the data rather than learned it. This is overfitting in its most naked form, and trees reach it faster than almost any other model family because nothing in the fitting procedure resists it.

Depth is the main control because its effect is exponential. A tree of depth d has at most 2^d leaves: depth 3 gives 8, depth 10 gives 1,024, depth 20 gives 1,048,576. On 10,000 rows, any depth beyond about log₂(10,000) ≈ 13 is already in the regime where leaves hold single examples, so a max_depth of 20 is not "a bit deeper" than 13 — it is unlimited in practice. The complementary knobs work on the same problem from the other end: min_samples_leaf refuses to create a leaf below a given size, and min_impurity_decrease refuses a split whose gain is not worth taking. Requiring 20 samples per leaf caps a 10,000-row tree at 500 leaves however deep you let it go.

Pruning: grow it too far on purpose, then cut back

Stopping early has a known failure: the greedy search cannot look ahead, so a split with a gain of 0.001 may be the only thing standing between the tree and two excellent splits below it. A depth limit throws those away.

Cost-complexity pruning, from the original 1984 CART book, fixes this by growing the tree to full size and then removing subtrees. It scores a tree as its error plus a penalty per leaf, R(T) + α|T|, where |T| is the number of leaves. At α = 0 the full tree wins; as α rises, whole subtrees stop paying for themselves and collapse into single leaves; at a large enough α only the root survives. Choosing α by cross-validation picks the tree size that generalises, rather than the one you guessed. In scikit-learn this is the ccp_alpha parameter.

Types

The three named algorithms people still cite differ in specific, checkable ways — splitting criterion, how they treat categorical features, and whether they prune.

ID3 (Quinlan, 1986) is the ancestor. It splits on information gain using entropy, handles only categorical features, and makes one branch per category — a six-value feature produces a six-way split. It does not prune and has no mechanism for continuous features or missing values. Its notorious flaw is a bias toward high-cardinality features: split on a customer ID with 1,000 distinct values and every child holds one row, so the information gain is the maximum possible while the predictive value is zero.

C4.5 (Quinlan, 1993) is ID3 with that flaw patched and the practical gaps filled. It replaces information gain with gain ratio, dividing the gain by the entropy of the split itself — for a 1,000-value ID that divisor is log₂(1,000) ≈ 9.97 bits against 1 bit for a binary feature, a roughly tenfold penalty that removes the incentive. It handles continuous features by threshold search, routes rows with missing values down both branches with fractional weights, and prunes after growing.

CART (Breiman, Friedman, Olshen and Stone, 1984) is what almost every modern library actually implements. It uses Gini for classification and variance reduction for regression, makes strictly binary splits even on categorical features, and prunes by cost complexity. The binary-only rule is why scikit-learn requires categorical features to be encoded numerically first. The regression variant is the same algorithm with a different score: instead of Gini it minimises the squared error within each child, and the leaf predicts the mean of its rows rather than the majority class.

Real-World Applications

Clinical decision rules are the strongest case for a genuine single tree, because the model has to be executed by a doctor from memory. The PECARN pediatric head-injury rule was derived by binary recursive partitioning on a cohort of more than 42,000 children (Kuppermann et al., The Lancet, 2009) and came out as six yes/no questions per age group, with a reported negative predictive value of 99.95% in children aged two and over. It is used in emergency departments to decide against a CT scan. No ensemble could occupy that role: the output had to be something a clinician can apply at the bedside without a computer.

Credit scoring is the other durable one, for regulatory rather than clinical reasons — a lender must be able to state the specific reasons for a denial, which favours models whose decisions attribute to named inputs. AI in finance covers what the rules require and why gradient-boosted trees rather than deep networks dominate underwriting; the point here is that the attributability comes from the tree structure underneath.

Exploratory analysis is the everyday use and the least discussed. Fitting a depth-3 tree to a new dataset takes seconds and tells you which two or three features carry the signal and roughly where their interesting thresholds lie — a fast, readable first pass before anything heavier, and a practical form of feature selection.

As a component, the single largest deployment of decision trees is invisible: they are the base learner inside random forests and gradient boosting, which remain the strongest general-purpose models for tabular data. Every XGBoost model is a few hundred to a few thousand trees of the kind described above.

Key Concepts

• The three kinds of node: the root holds all training rows, every internal one holds a single test, and a leaf holds a prediction — the majority class for classification, the mean for regression.
• Greedy construction: the best split at each node is chosen without regard to what it makes possible below. Finding the globally optimal tree is NP-hard, so mainstream libraries do not try.
• Built-in ranking of features: summing the weighted impurity reduction a column earns across every node it splits scores how much work it did — cheap to compute, and biased toward high-cardinality columns for exactly the ID3 reason above.
• Axis-aligned split: every test compares one feature to one constant, so every boundary a tree can draw is perpendicular to a feature axis.

Challenges

A single tree is high-variance, and the root is where it shows. Because the whole structure hangs off one greedy first choice, changing a handful of training rows can change that choice and invalidate everything beneath it. In the ten-row table above, flip applicant A from repaid to defaulted — one row in ten — and the prior-default gain falls from 0.1633 to 0.0833 while the income split at 51.5 rises to 0.1800. The root swaps, and every question below it is re-derived on different data. A model whose top-level explanation changes when one row moves is not a stable explanation, whatever its accuracy. This instability is the entire reason ensemble methods exist: averaging many decorrelated trees cancels the variance while keeping the flexibility, which is what random forests and gradient boosting do and where the practical accuracy lives.

A diagonal boundary is expensive, and the arithmetic is unforgiving. Every split is axis-aligned, so a true boundary running at 45° through two features has to be approximated by a staircase. Take the unit square with the boundary x + y = 1. A staircase of k steps whose corners touch that line leaves k right triangles uncovered, each with legs 1/k, so the misclassified area is k × ½(1/k)² = 1/(2k). Getting that below 1% needs k = 50 steps, which is 100 leaves and 99 internal nodes; below 0.1% needs k = 500, so 1,000 leaves. Error falls only linearly in the size of the tree. Logistic regression represents the same boundary exactly with three numbers — two weights and an intercept — and a single neural network unit does the same. When your features interact smoothly and diagonally, a tree is the wrong shape, and no amount of depth fixes the shape.

Interpretability is a property of the depth, not of trees as a family. A depth-3 tree is at most eight leaves and eight rules, which a person can read, argue with, and sign off on — this is the claim that makes trees attractive in the domains explainable AI cares about. A depth-20 tree can hold over a million leaves, and a prediction path through it that names twenty conditions is not an explanation anyone can check. The commonly repeated "decision trees are interpretable" is true of the trees people draw in tutorials and false of the trees that win accuracy comparisons, and the gap between those two is exactly the accuracy-versus-interpretability trade-off.

Splitting bias and thin leaves. Impurity-based selection favours features with many distinct values, because more candidate thresholds means more chances at a high score — the ID3 problem above, still present in Gini implementations and still visible in built-in importances. And because a leaf's prediction is estimated from whatever rows land in it, a leaf holding three rows gives you a probability with three rows' worth of confidence, which is how a tree that looks precise turns out to be guessing.

Code Example

Fitting a shallow tree and printing it as text is usually more informative than any accuracy number, because it shows you exactly which splits the algorithm chose and in what order.

from sklearn.tree import DecisionTreeClassifier, export_text
import numpy as np

# The ten applicants from the worked example above.
# Columns: income ($k), prior_default (1 = yes)
X = np.array([[22, 0], [28, 1], [31, 1], [39, 0], [45, 1],
              [58, 0], [61, 0], [74, 0], [88, 1], [96, 0]])
y = np.array([1, 0, 1, 0, 0, 1, 1, 1, 0, 1])  # 1 = repaid

tree = DecisionTreeClassifier(criterion="gini", max_depth=2, random_state=0)
tree.fit(X, y)

# The tree as text. The root test is the split worked out by hand above.
print(export_text(tree, feature_names=["income", "prior_default"]))

# Gini(parent) = 0.4800, straight from the class balance.
p = y.mean()
print(f"Gini(parent) = {1 - (p**2 + (1 - p)**2):.4f}")

# Impurity-weighted importances: prior_default 0.583, income 0.417.
for name, imp in zip(["income", "prior_default"], tree.feature_importances_):
    print(f"{name}: {imp:.3f}")

# Unconstrained, the same ten rows are memorised: 6 leaves, depth 3, 100% training accuracy.
full = DecisionTreeClassifier(random_state=0).fit(X, y)
print(full.get_n_leaves(), full.get_depth(), full.score(X, y))

The printed tree splits on prior_default <= 0.50 at the root, matching the hand calculation, and only then reaches for income. Drop max_depth and the tree keeps splitting until every leaf is pure — training accuracy 1.0 on data it has simply memorised. Overfitting a tree takes one omitted keyword argument, which is why the depth and pruning controls above are not optional extras.