Decision Trees

A decision tree is a supervised machine learning model that learns to make predictions by asking a sequence of yes/no questions about input features, forming a branching tree structure where each leaf node represents a final prediction. Decision trees matter because they are one of the few ML models that are simultaneously powerful enough to solve real problems and transparent enough for a human to read and understand every decision. Remarkably, the same algorithm that classifies whether a patient has a disease can be printed on a single sheet of paper and checked by a doctor — something almost no modern deep learning model can claim.

The core insight

A decision tree learns to mimic the way humans naturally reason: by asking a series of targeted questions, each narrowing down the possibilities, until only one answer remains. The "aha moment" is realizing that the algorithm's entire job is to figure out which question to ask first — because the best first question is the one that splits your messy, mixed-up data into the cleanest, most separated groups possible. Once you understand that idea (called impurity reduction), everything else in the algorithm follows naturally. Every split, every branch, every stopping rule is just a systematic way of chasing that cleaner separation.

How It Works

At its core, a decision tree repeatedly splits the training data into two groups by testing one feature at a time. To decide which feature to split on and where to split it, the algorithm measures how "impure" or "mixed" each resulting group would be. The most common impurity measure for classification is Gini Impurity.

\quad G(S) = 1 - \sum_{k=1}^{K} p_k^2

Explanation: Gini Impurity measures how often a randomly chosen element from set S would be incorrectly labelled — zero means perfectly pure (all one class), and higher values mean more mixing.

Symbols:

$G(S)$ — the Gini impurity of a set $S$
$K$ — the total number of classes
$p_k$ — the proportion of examples in $S$ that belong to class $k$

At every candidate split, the algorithm computes the weighted average impurity of the two child nodes that would result:

\quad \text{Weighted Impurity} = \frac{|S_L|}{|S|} G(S_L) + \frac{|S_R|}{|S|} G(S_R)

Explanation: This weights each child's impurity by how large it is — a very impure but tiny child group is less concerning than a very impure and large one.

Symbols:

$S_L$ , $S_R$ — the left and right subsets produced by the split
$|S|$ — number of examples in parent set; $|S_L|$ , $|S_R|$ — sizes of each child

The algorithm picks whichever feature and threshold minimises equation [2]. This process repeats recursively at each node until a stopping condition is met — for example, a maximum depth, a minimum number of samples per leaf, or until all leaves are pure. Here is the simplest possible working example in Python: ```python from sklearn.tree import DecisionTreeClassifier, export_text from sklearn.datasets import load_iris

# Load a classic dataset X, y = load_iris(return_X_y=True)

# Train a shallow tree (max_depth prevents overfitting) clf = DecisionTreeClassifier(max_depth=3, random_state=42) clf.fit(X, y)

# Print the human-readable rules print(export_text(clf, feature_names=load_iris().feature_names)) ``` Running this prints something like: ``` |--- petal width (cm) <= 0.80 | |--- class: 0 |--- petal width (cm) > 0.80 | |--- petal width (cm) <= 1.75 | | |--- class: 1 | |--- petal width (cm) > 1.75 | | |--- class: 2 ``` Every line is a human-readable rule. You can hand this to a botanist and they can classify flowers with a ruler — no computer required. For regression problems (predicting a number rather than a class), the impurity measure switches from Gini to Mean Squared Error within each node:

\quad \text{MSE}(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar{y})^2

Explanation: A regression leaf is "pure" when all the target values in it are close to their mean — meaning the tree's constant prediction of $\bar{y}$ at that leaf would have low error.

Symbols:

$y_i$ — the true target value for example $i$
$\bar{y}$ — the mean target value of all examples in set $S$

```python from sklearn.tree import DecisionTreeRegressor import numpy as np

# Toy regression example X = np.array([[1],[2],[3],[4],[5],[6],[7],[8]]) y = np.array([1.2, 1.9, 3.1, 3.8, 5.2, 5.9, 7.0, 8.1]) reg = DecisionTreeRegressor(max_depth=2) reg.fit(X, y) print(reg.predict(4.5)) # Predicts a number, not a class ```

researcher · Leo Breiman | 1928 – 2005 | CART Algorithm and Ensemble Methods

Leo Breiman was a statistician at UC Berkeley who became one of the most influential figures in applied machine learning, fundamentally shaping how decision trees are built and used. In 1984, he co-authored the landmark book Classification and Regression Trees (CART) with Friedman, Olshen, and Stone, which introduced the systematic binary splitting and pruning procedures that underpin nearly every modern tree implementation including scikit-learn. Remarkably, Breiman spent years as a consultant and freelance statistician living in a cabin in Bolinas, California before returning to academia — and it was this outsider perspective that led him to later invent Random Forests, recognising that trees worked best when combined rather than perfected.

Figure

Decision Tree Split Diagram

Figure

Overfitting vs Pruning Diagram

Intuition

The Mental Model

Imagine you are playing the game 20 Questions. A good player does not start with "Is it a golden retriever?" — that is too specific and wastes a question if wrong. Instead they ask "Is it an animal?" — a question that cleanly splits everything in the universe into two large, useful groups. A decision tree is an algorithm that plays 20 Questions automatically, on your data. It tries every possible question ("Is petal length > 3cm?", "Is petal length > 3.1cm?", "Is sepal width > 2.5cm?", ...) and picks whichever one produces the two most sorted groups — groups where one type of thing clusters together as much as possible. Think of your training data as a jar of mixed jellybeans. Each question is like putting a divider in the jar. A great divider mostly puts red jellybeans on one side and yellow ones on the other. A terrible divider leaves both sides equally mixed. The algorithm is simply searching for the best dividers, one at a time. The danger of growing the tree too deep is like putting in so many dividers that you eventually have one jellybean per compartment — you have perfectly sorted this specific jar, but you have learned nothing useful about jellybeans in general.

Historical Development

Origins · 1 minhow this was discovered

History

1963

Morgan & Sonquist develop AID (Automatic Interaction Detection) at the University of Michigan — one of the earliest systematic tree-based partitioning methods for survey data analysis.

1972

The concept of information gain from information theory begins to be applied to feature selection problems, laying the mathematical groundwork for splitting criteria.

1979

J. Ross Quinlan at the University of Sydney develops ID3 (Iterative Dichotomiser 3), the first widely-used decision tree algorithm, using Shannon entropy and information gain as splitting criteria.

1984

Breiman, Friedman, Olshen, and Stone publish Classification and Regression Trees (the "CART" book), introducing binary splits, Gini impurity, cost-complexity pruning, and cross-validation — the foundation of scikit-learn's implementation.

1986

Quinlan publishes a landmark paper extending ID3 to handle continuous features and missing values, making tree learning practical for real-world messy datasets.

1993

Quinlan releases C4.5 (and the companion book), which adds pruning, probability estimates at leaves, and handles continuous attributes more rigorously — for years, C4.5 was the most widely cited ML algorithm in the literature.

1995

Tin Kam Ho introduces the Random Subspace Method, a precursor to Random Forests, showing that randomising feature selection dramatically reduces tree variance.

2001

Leo Breiman publishes the Random Forests algorithm in Machine Learning, combining hundreds of decision trees into an ensemble — transforming trees from a standalone classifier into the backbone of one of the most powerful general-purpose ML methods available.

2016

XGBoost (Chen & Guestrin) wins numerous Kaggle competitions using gradient-boosted decision trees, cementing tree-based methods as the dominant approach in structured/tabular data ML, a position they hold today against even deep learning.

Why It Matters

Real-World Impact

Medical Diagnosis (Clinical Decision Rules)Decision trees are used directly in clinical settings — for example, the Wells Score for deep vein thrombosis is essentially a hand-coded decision tree that doctors follow step-by-step. ML-trained trees have extended this to cancer screening and ICU triage tools.

Credit Scoring (Banking)Banks use decision trees and tree ensembles to approve or deny loan applications. The transparency requirement — regulators need to know why a loan was denied — makes single decision trees especially valuable here, as the full reasoning can be printed and audited.

Fraud Detection (Stripe, PayPal)Real-time payment fraud detection systems use gradient-boosted trees (built on individual decision tree learners) because they are fast to evaluate at inference time — a transaction can be scored in microseconds — and handle the mix of numerical and categorical features typical of financial data.

scikit-learn's `DecisionTreeClassifier`The reference implementation, used in millions of Python ML pipelines worldwide, implements CART exactly as described by Breiman et al. (1984). It supports Gini and entropy criteria, max depth, min samples per leaf, and cost-complexity pruning via `ccp_alpha`.

XGBoost / LightGBM (Kaggle and Industry)These gradient boosting libraries build hundreds of shallow decision trees sequentially, each correcting the errors of the last. They consistently win structured-data competitions on Kaggle and are used in production at companies like Uber (trip pricing), Microsoft (ad click prediction), and Alibaba (recommendation systems).

Customer Churn Prediction (Telecom / SaaS)Telecom companies use decision trees to identify customers likely to cancel. A tree model is preferred over a neural network because the output — "Customer called support 3+ times AND contract ends in < 30 days → high churn risk" — can be handed to a sales team as a concrete action rule.

Decision Trees

How It Works

Intuition

Historical Development

Why It Matters

Prerequisites

What This Leads To

See Also

Where this leads