The CART (Classification and Regression Trees) algorithm is a systematic framework for transforming complex decision-making problems into a sequence of simple, binary, data-driven decisions. It operationalizes decision-making as a recursive partitioning process that divides the input space into disjoint regions where the target variable behaves as uniformly as possible.
At its core, CART formalizes the incremental model of decision-making, in which a complex decision is decomposed into a sequence of simpler choices, each involving a limited number of alternatives and minimizing decision costs locally at each step.
Decision-Making as Incremental Optimization
In real-world decision-making, decisions are rarely made all at once. Instead, they are made incrementally, with each step narrowing the space of possibilities. CART mirrors this logic by:
- Restricting each decision to a binary choice
- Optimizing decisions locally at each step
- Ensuring that each decision reduces uncertainty about the outcome
A classic everyday example is determining whether milk is safe to consume. The decision is not made immediately but proceeds through a sequence of checks (expiration date, smell, appearance), with the final decision being either to discard the milk or use it in cooking. CART encodes this same logic using data and statistical criteria rather than intuition.
Data-Driven and Replicable Decision Steps
Unlike human decision-making, which often relies on intuition or trial-and-error, CART enforces analytical and replicable rules. Each decision step is derived from a single feature, chosen to maximally distinguish the distributions of the target variable between the resulting groups.
These distributions determine the expected costs of decisions. CART seeks splits that make these distributions as different as possible, thereby minimizing uncertainty and improving predictive accuracy.
Recursive Partitioning With Supervision
CART operates in a supervised learning setting. The algorithm has access to a labeled dataset consisting of predictors (features) and a target variable (label).
The partitioning is recursive:
- Start with all observations in a single group
- Split the group into two subgroups using a rule based on one feature
- Apply the same splitting logic independently to each subgroup
This recursion continues until further splitting no longer improves homogeneity.
Nodes, Branches, and Tree Structure
A CART model is represented as a tree composed of nodes and branches.
A node represents a subset of observations.
A branch (or split) represents a rule that partitions observations based on a feature value.
The tree has a hierarchical structure:
- The root node contains all observations and has no incoming branches
- Parent nodes produce splits
- Child nodes receive observations from a split
- Leaf (terminal) nodes have no outgoing branches
The depth of a tree is defined as the number of layers minus one. The root node is always at depth zero.
Interpreting Leaf Nodes as Decision Rules
Each leaf node corresponds to a rule that maps feature values to a predicted outcome. To interpret a leaf node:
- Select the leaf node
- Trace the decision path backward to the root
- Record all feature conditions encountered
- Remove redundant conditions
For example, the following paths:
- $DEBTINC > 44.162$ and $DEBTINC > 45.657$
can be simplified to:
- $DEBTINC > 45.657$
because the first condition is implied by the second. CART therefore produces minimal and interpretable rules.
Historical Origins of CART
CART was formally introduced in 1984 by Leo Breiman, Jerome Friedman, Charles J. Stone, and Richard A. Olshen. Their work unified statistical theory, algorithmic efficiency, and interpretability. The first commercial implementation was developed by Salford Systems, making CART one of the earliest widely adopted data mining tools.
Core Properties of CART
CART supports two model types:
- Classification trees for categorical targets
- Regression trees for continuous targets
The algorithm exhibits several important properties:
- Robust handling of missing values
- Resistance to outliers, which are isolated into separate nodes
- Stability under collinearity among predictors
- Invariance under monotone transformations such as logarithms or square roots
These properties make CART particularly suitable for real-world, messy data.
Binary Splits as the Fundamental Operation
CART restricts all decisions to binary splits, regardless of feature type.
Interval or Ordinal Features
Splits take the form:
- ${x : x \le a}$ and ${x : x > a}$
If a feature has $s$ distinct values, it can generate up to $s – 1$ candidate splits.
Nominal Features
Splits take the form:
- ${x : x \in A}$ and ${x : x \notin A}$
where $A$ is a non-empty subset of categories.
Such features can generate up to $2^{s-1} – 1$ unique splits because larger subsets mirror smaller ones and are redundant.
No split is allowed to produce an empty node.
Impurity Metrics: Quantifying Homogeneity
The objective of CART is to reduce impurity at each split.
Categorical Targets
Let $p_{ij}$ denote the proportion of class $j$ in node $i$.
Entropy
Entropy is defined as:
$-\sum_{j=1}^k p_{ij} \log_2 p_{ij}$
- Maximum entropy occurs under uniform distribution
- Minimum entropy (zero) occurs when all observations belong to one class
- Base-2 logarithms reflect the binary nature of splits
Gini Index
The Gini Index is defined as:
$1 – \sum_{j=1}^k p_{ij}^2$
- Maximum when class proportions are uniform
- Zero when the node is pure
Both entropy and Gini measure class mixture but weight probabilities differently.
Continuous Targets (Regression Trees)
For regression trees, impurity is measured by squared deviation from the mean:
$\sum (y_j – \bar{y}_j)^2$
This directly measures within-node variance.
Evaluating a Candidate Split
When a split produces $D$ child nodes, each with $N_d$ observations and impurity $V_d$, the overall impurity of the split is:
$I = \frac{\sum_{d=1}^D N_d V_d}{\sum_{d=1}^D N_d}$
CART selects the split that minimizes this weighted impurity, ensuring that larger nodes contribute proportionally to the decision.
Recursive Optimization Process
The CART algorithm proceeds as follows:
- Evaluate all features at a node
- Enumerate all valid binary splits
- Compute impurity for each split
- Select the split with minimum impurity
- Partition the data
- Repeat recursively for each child node
The recursion stops when impurity cannot be reduced further or when stopping criteria are met.
CART as Recursive Data Partitioning
Through recursive binary splitting, CART partitions the feature space into disjoint regions with minimal internal variability. Each region corresponds to a leaf node with a constant predicted value.
In medical and public health research, this methodology is often referred to as recursive data partitioning, emphasizing its statistical roots and interpretability.
Conceptual Interpretation
CART transforms decision-making into a structured hierarchy of rules. Each rule is locally optimal, data-driven, and interpretable. The final model is a collection of simple conditions that jointly approximate complex relationships between predictors and outcomes.
This combination of statistical rigor, algorithmic efficiency, and interpretability explains why CART remains a foundational algorithm in modern machine learning.