Core ML1984foundational10 min read

Classification and Regression Trees

أشجار التصنيف والانحدار

Breiman, L. · Friedman, J. · Olshen, R. · Stone, C. — Chapman and Hall/CRC

The problem

Before CART, building a classifier or regressor required either rigid parametric assumptions (e.g. linearity) or hand-crafted expert rules. Linear models couldn't capture complex interactions between features, and expert-system rules were brittle — change the domain and you start from scratch. There was no general, automatic method that could handle both and , deal with missing data, work with mixed types, and produce human-readable decisions.

The contribution

CART: a unified algorithm that builds binary decision trees for both classification and regression. At each , the algorithm finds the best binary by exhaustively searching over all features and all thresholds to maximize purity ( for classification, reduction for regression). The tree grows greedily until pure, then is pruned back using with to find the right tree size. Surrogate splits handle missing data. The result is a model that is interpretable, nonparametric, handles interactions automatically, and requires no .

The impact

CART is the seed of an entire ecosystem. Random Forests (2001) grow hundreds of randomized CART trees and vote. (1999) chains small CART trees sequentially, each correcting the last. XGBoost, LightGBM, CatBoost — the workhorses of tabular data in industry — are all descendants. CART proved that a single, well-designed could match expert knowledge, and its descendants now power most production ML on structured data.

Imagine you're a doctor in an emergency room. A patient arrives and you need to decide quickly: admit or discharge?

You don't run every possible test. You start with the most telling question: "Is their blood pressure dangerously high?" If yes, go left — ask about chest pain. If no, go right — ask about fever. Each answer narrows the diagnosis until you reach a decision.

That's exactly how a decision tree works: a flowchart of binary questions, ordered so the most informative question comes first. CART is the algorithm that builds this flowchart automatically from data — no doctor required.

The problem: rigid models or brittle rules

Before CART, practitioners faced a painful choice:

Linear models (e.g. ) assume the is a straight line. But real data is rarely that clean — a patient's risk might spike only when both blood pressure and cholesterol are high, an interaction a linear model misses without manual feature engineering.
Expert systems encode domain knowledge as hand-written if-then rules. They work brilliantly in narrow domains but shatter when the domain shifts. Maintaining thousands of rules as knowledge evolves is an engineering nightmare.

What was missing was a method that discovers the rules automatically from data, handles nonlinear interactions, works for both classification and regression, and produces output a human can read and trust.

The idea: ask the best question, then recurse

CART builds a tree top-down using recursive binary splitting. The intuition is simple: at every node, look at all possible ways to split the data into two groups, pick the split that makes the two groups as pure as possible, and repeat on each group until every leaf contains only one class (or a single predicted value for regression).

Think of it as a game of 20 questions optimized by a statistician: each question is chosen to eliminate the most uncertainty, and the game tree branches until every path leads to a confident answer.

Three key decisions define the algorithm:

How to measure purity — what makes one split better than another?
When to stop splitting — how big should the tree grow?
How to prune — how to cut back an overgrown tree without losing accuracy?

Open in Lab

Watch CART build a tree step by step. Click "Next Split" to see the algorithm pick the best question at each node.

The demo wakes as you arrive…

Measuring purity: Gini impurity

Imagine picking two random items from a group. If the group is pure (all one class), you'll always pick two of the same class. If the group is maximally mixed, you'll often pick two different classes. Gini impurity measures exactly this: the probability of misclassifying a randomly chosen item if you labeled it randomly according to the group's class distribution.

A Gini of 0 means the node is perfectly pure — all items belong to one class. A Gini of 0.5 (for two classes) means maximum disorder — a 50-50 mix. CART's goal at each split is to find the feature and threshold that reduce Gini the most.

Why Gini and not ? Both work well in practice, but Gini avoids the logarithm computation, making it slightly faster. Breiman chose Gini as the default because it produces trees nearly identical to entropy-based trees but with less computation.

Gini(t) = 1 - \sum_{k=1}^{K} p_k^2

Gini impurity at node t — p_k = fraction of items in class k at this node · K = number of classes · When one class dominates, most p_k² terms are small and one is large, so 1 − Σp_k² → 0 (pure). When classes are evenly split, p_k² terms are all small, so 1 − Σp_k² is large (impure).

For regression trees, purity is measured differently. Instead of class proportions, CART minimizes the variance () within each node. The predicted value at a leaf is simply the average of all samples that land there.

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

Regression split criterion — variance at node t — y_i = actual value of sample i · ȳ_t = mean of all samples at node t · The split that creates two child nodes with the smallest combined MSE wins.

Open in Lab

Drag the class ratio slider to see how Gini and entropy change. Notice they agree on which split is best — Gini is just faster to compute.

The demo wakes as you arrive…

The greedy search: finding the best split

At every node, CART performs an exhaustive search. For each feature, it sorts the values, considers every midpoint between consecutive values as a potential threshold, and computes the Gini gain (or variance reduction) for each. The split with the highest gain wins.

This is a greedy algorithm: it picks the locally best split at each step without looking ahead. Finding the globally optimal tree is NP-hard, so greedy splitting is the practical compromise. Despite this, CART trees perform remarkably well because the recursive structure lets later splits correct earlier ones.

For a node with $n$ samples and $p$ features, the cost is $O(n \cdot p \cdot \log n)$ — dominated by sorting each feature once, then scanning the sorted list for the best threshold.

\Delta Gini(s, t) = Gini(t) - \frac{|t_L|}{|t|} Gini(t_L) - \frac{|t_R|}{|t|} Gini(t_R)

Gini gain — the improvement from split s at node t — t_L, t_R = left and right child nodes after split · |t_L|/|t| = fraction of samples going left · The split that maximizes ΔGini is chosen.

Pruning: growing then cutting back

A fully grown tree memorizes the training data — every leaf is pure, but the tree overfits badly. It has learned the noise, not the signal. Imagine a tree so detailed it has a separate branch for every patient in a hospital: it would perfectly predict their outcomes but fail completely on a new patient.

CART's elegant solution is cost-complexity . The idea: first grow the largest possible tree $T_0$ , then find a nested sequence of smaller trees by progressively snipping the weakest branches. Each pruned tree trades a little training accuracy for a lot of simplicity. Cross-validation picks the tree size that generalizes best to unseen data.

The cost-complexity criterion balances fit and complexity with a single parameter $\alpha$ :

R_\alpha(T) = R(T) + \alpha \cdot |\widetilde{T}|

Cost-complexity criterion — R(T) = training error of tree T · |T̃| = number of leaf nodes · α = complexity penalty. Small α → big tree (low bias, high variance). Large α → small tree (high bias, low variance). Cross-validation finds the sweet spot.

Open in Lab

Drag the α slider to prune the tree. Watch how training accuracy drops slightly but test accuracy peaks at the right tree size.

The demo wakes as you arrive…

Surrogate splits: handling missing data

Real-world data is messy — patients miss appointments, sensors fail, fields are left blank. Most models of the era simply deleted rows with , throwing away precious information.

CART introduced an ingenious solution: surrogate splits. For every primary split, CART finds backup features whose split patterns closely mimic the primary split. When a sample reaches a node with a missing value for the primary feature, CART uses the best surrogate feature instead — like having a backup question ready when the first one can't be answered.

This also reveals hidden correlations: if "income" is the primary split and "education level" is its best surrogate, the tree is telling you these features move together.

Variable importance: which features matter?

One of CART's most practical gifts is . For each feature, CART sums the total Gini gain (or variance reduction) across every node where that feature was used as a splitter. Features that appear high in the tree and create large purity improvements rank highest.

This gives practitioners an automatic feature ranking — no separate step needed. A doctor building a diagnostic tree immediately sees which lab values matter most. This is why CART and its descendants remain dominant in medicine, finance, and anywhere decisions must be explained.

The same idea in code

CART: Gini-based classification tree, completepython

Simplified to show the idea — not the real implementation.

import numpy as np

def gini(y):
    """Gini impurity: probability of misclassifying a random sample."""
    classes, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return 1 - np.sum(probs ** 2)

def best_split(X, y):
    """Find feature + threshold that maximizes Gini gain."""
    best_gain, best_feat, best_thresh = -1, None, None
    parent_gini = gini(y)

    for feat in range(X.shape[1]):
        thresholds = np.unique(X[:, feat])
        for t in thresholds:
            left = y[X[:, feat] <= t]
            right = y[X[:, feat] > t]
            if len(left) == 0 or len(right) == 0:
                continue
            # Weighted child impurity
            w_l = len(left) / len(y)
            gain = parent_gini - w_l * gini(left) - (1-w_l) * gini(right)
            if gain > best_gain:
                best_gain, best_feat, best_thresh = gain, feat, t

    return best_feat, best_thresh, best_gain

def build_tree(X, y, depth=0, max_depth=5):
    """Recursively build a CART classification tree."""
    # Leaf: pure node or max depth reached
    if len(np.unique(y)) == 1 or depth >= max_depth:
        classes, counts = np.unique(y, return_counts=True)
        return {"leaf": True, "class": classes[np.argmax(counts)]}

    feat, thresh, gain = best_split(X, y)
    if feat is None:
        classes, counts = np.unique(y, return_counts=True)
        return {"leaf": True, "class": classes[np.argmax(counts)]}

    left_mask = X[:, feat] <= thresh
    return {
        "leaf": False,
        "feature": feat,
        "threshold": thresh,
        "left": build_tree(X[left_mask], y[left_mask], depth+1, max_depth),
        "right": build_tree(X[~left_mask], y[~left_mask], depth+1, max_depth),
    }

# That's the core of CART.
# Pruning = grow a full tree, then trim branches whose removal
# improves cross-validated accuracy. The tree you deploy is
# the pruned one — compact, interpretable, and generalizable.

Why it mattered

1984
CART — the original
Breiman, Friedman, Olshen & Stone publish Classification and Regression Trees. First unified framework for binary decision trees with Gini impurity, cost-complexity pruning, and surrogate splits.
1986
ID3 → C4.5 (Quinlan)
Quinlan's C4.5 extends ID3 with gain ratio, multi-way splits, and handling of continuous attributes. A parallel evolution alongside CART that popularized entropy-based splitting.
1996
Bagging (Breiman)
Breiman introduces Bootstrap Aggregating — train many trees on random subsamples of the data and average their predictions. Reduced variance dramatically.
1999
Gradient Boosting (Friedman)
Friedman chains small CART trees sequentially, each fitting the residual errors of the previous. Gradient Boosting Machines become the gold standard for tabular data.
2001
Random Forests (Breiman)
Breiman combines bagging with random feature selection at each split. Random Forests become the default "first try" algorithm in ML — hard to beat, impossible to break, trivial to tune.
2016
XGBoost dominates Kaggle
Chen & Guestrin's XGBoost adds regularization and systems optimizations to gradient boosting. Wins the majority of Kaggle structured-data competitions. LightGBM and CatBoost follow.
2026
Trees everywhere
Tree-based ensembles remain the default for tabular data in industry. Medical diagnosis, credit scoring, fraud detection, recommendation systems — wherever data comes in rows and columns, CART's descendants are the first tool practitioners reach for.

Breiman didn't just build a classifier. He built a language for asking questions about data — a language so natural that Random Forests and Gradient Boosting are just different dialects of it. Every time you interact with a recommendation engine, a medical risk score, or a fraud alert, chances are a forest of CART trees is working behind the scenes.

CitationBreiman, Friedman, Olshen, Stone. Classification and Regression Trees. Chapman and Hall/CRC, 1984.

Terms in this paper

Decision Treeشجرة القرار الإحصائية
Gini Impurityشائبة جيني
Cost-Complexity Pruningتشذيب التعقيد-التكلفة
Surrogate Splitالتقسيم البديل
Recursive Partitioningالتقسيم التكراري
Variable Importanceأهمية المتغيرات
Binary Treeالشجرة الثنائية