Decision trees constitute a fundamental family of supervised learning models designed to learn decision rules from labeled training data. In classification, these rules assign an observation to a categorical class label; in regression, they estimate a continuous numerical value. Within this family, the CART (Classification and Regression Trees) algorithm occupies a central position because it formalizes the construction of strictly binary trees capable of handling both categorical and numerical features while incorporating cost-complexity pruning mechanisms to control model complexity (Breiman et al. 1984; Hastie et al. 2009).
Unlike algorithms such as ID3, which was originally formulated for classification trees with multi-way splits on categorical features, CART builds strictly binary trees. At each internal node, the algorithm evaluates a boolean question (“does a specific condition hold?”) to split data into two disjoint subsets: those meeting the condition and those that do not. The fundamental goal is selecting splits that recursively yield increasingly homogeneous child nodes with respect to the target variable.
In classification tasks, node homogeneity is measured using an impurity function. CART typically employs the Gini index, though entropy is also widely supported. In regression tasks, split criteria rely on variance reduction or Mean Squared Error (MSE) minimization. This chapter focuses primarily on CART for classification, exploring binary tree structure, Gini index calculations, categorical and continuous variable splitting rules, impurity reduction, pruning, and computational complexity.
A decision tree represents a hierarchy of conditional rules. Each internal node contains a test condition on a predictor variable, each branch represents a test outcome, and each leaf node assigns a class prediction. Classifying a new observation involves traversing the tree from root to leaf by sequentially evaluating learned branch conditions.
CART was introduced by Breiman, Friedman, Olshen, and Stone in 1984 as a unified framework for constructing classification and regression trees (Breiman et al. 1984). Its defining features include:
Binary partitioning is a key characteristic: even if a categorical feature takes more than two values, CART does not create multi-way branches. Instead, it evaluates all non-equivalent binary groupings of categories into two subsets to find the split yielding maximum purity gain.
Supervised classification starts with a training set:
\[ D = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n}, \]
where \(\mathbf{x}_i \in \mathcal{X}\) represents predictor features for observation \(i\) and \(y_i \in \{1, 2, \dots, K\}\) is its target class label. The goal is learning a mapping \(f: \mathcal{X} \to \{1, 2, \dots, K\}\) predicting target labels for new observations.
A node is pure if all contained observations belong to a single class, making leaf prediction unambiguous. Conversely, if a node mixes observations across multiple classes, it is impure, warranting further splits if informative candidate questions remain available.
If \(p_{k,t}=1\) for some class \(k\), the node is pure. As class proportions spread across multiple classes, impurity increases. This intuition is formalized by the Gini index.
The Gini index measures node impurity based on class distribution. For \(K\) target classes, it is defined as:
This expression can be interpreted as the probability of incorrectly classifying a randomly chosen node element if it were randomly labeled according to the empirical class distribution of the node (Breiman et al. 1984; James et al. 2021).
In binary classification with classes “Yes” and “No”, if \(p\) is the proportion of positive instances:
\[ Gini(D_t)=1-p^2-(1-p)^2=2p(1-p). \]
The minimum Gini value is \(0\), achieved when \(p=0\) or \(p=1\) (pure node). The maximum binary Gini value is \(0.5\), achieved when \(p=0.5\) (equal 50/50 mixture).
import numpy as np
import pandas as pd
def gini_from_counts(counts):
counts = np.asarray(counts, dtype=float)
probs = counts / counts.sum()
return 1 - np.sum(probs**2)
# Example: 9 "Yes" records and 5 "No" records
gini_raiz = gini_from_counts([9, 5])
print(f"Root Gini = {gini_raiz:.3f}")Root Gini = 0.459In this example, initial impurity is approximately \(0.459\), indicating that the root node contains a mixture of both classes.
In CART, a split divides node dataset \(D_t\) into left (\(D_L\)) and right (\(D_R\)) child subsets. Split quality is evaluated by computing the weighted average impurity of both child nodes, rather than evaluating child purity in isolation. This prevents favoring splits that isolate tiny pure nodes at the expense of overall dataset purity.
CART selects the candidate split \(s\) that minimizes weighted Gini impurity. Equivalently, this maximizes impurity reduction (Gini gain).
Both formulations yield identical split rankings for a given node: minimizing \(Gini_s(D_t)\) is mathematically equivalent to maximizing \(\Delta Gini(s,D_t)\) because parent impurity \(Gini(D_t)\) is constant during evaluation.
Suppose a categorical feature \(A\) takes values in a finite set:
\[ \mathcal{A}=\{a_1,a_2,\dots,a_m\}. \]
Rather than creating an \(m\)-way branch, CART constructs binary questions of the form:
\[ A \in S_A, \]
where \(S_A\) is a non-empty proper subset of \(\mathcal{A}\). For example, if:
\[ \text{income} \in \{\text{low}, \text{medium}, \text{high}\}, \]
candidate split subsets include:
\[ \text{income} \in \{\text{low}\}, \qquad \text{income} \in \{\text{medium}\}, \qquad \text{income} \in \{\text{low}, \text{medium}\}. \]
Each question partitions observations into two subsets: matching instances and non-matching instances.
We subtract 2 because empty and full set subsets do not form valid splits. We divide by 2 because subset \(S_A\) and its complement \(\mathcal{A} \setminus S_A\) define the exact same physical data partition (simply swapping left and right branch assignments).
from itertools import combinations
def binary_partitions(values):
values = tuple(values)
m = len(values)
partitions = []
seen = set()
full = frozenset(values)
for r in range(1, m):
for comb in combinations(values, r):
left = frozenset(comb)
right = full - left
key = frozenset([left, right])
if key not in seen:
seen.add(key)
partitions.append((set(left), set(right)))
return partitions
for left, right in binary_partitions(["low", "medium", "high"]):
print(left, "vs", right){'low'} vs {'high', 'medium'}
{'medium'} vs {'high', 'low'}
{'high'} vs {'medium', 'low'}For continuous numerical features, CART evaluates candidate cut-points. For continuous feature \(A\), a split takes the form:
\[ A < c \quad \text{vs.} \quad A \geq c. \]
Standard procedure sorts unique observed values of \(A\), computes midpoints between consecutive sorted values, and evaluates each midpoint as a candidate threshold \(c\).
Consider the toy dataset:
\[ (20,\text{Yes}),\quad (25,\text{Yes}),\quad (30,\text{No}),\quad (40,\text{No}). \]
Sorted values are \(20, 25, 30, 40\), yielding candidate midpoints:
\[ 22.5, \qquad 27.5, \qquad 35. \]
For each threshold \(c\), child subsets are formed:
\[ D_L=\{A<c\}, \qquad D_R=\{A\geq c\}, \]
and weighted Gini impurity is computed.
import pandas as pd
edad = pd.DataFrame({
"age": [20, 25, 30, 40],
"target": ["Yes", "Yes", "No", "No"]
})
def gini(labels):
counts = pd.Series(labels).value_counts().to_numpy()
return gini_from_counts(counts)
def weighted_gini_for_cut(df, feature, target, c):
left = df[df[feature] < c]
right = df[df[feature] >= c]
n = len(df)
return (len(left)/n)*gini(left[target]) + (len(right)/n)*gini(right[target])
values = sorted(edad["age"].unique())
cuts = [(values[i] + values[i+1]) / 2 for i in range(len(values)-1)]
resultados = pd.DataFrame({
"cutpoint": cuts,
"weighted_gini": [weighted_gini_for_cut(edad, "age", "target", c) for c in cuts]
})
resultados| cutpoint | weighted_gini | |
|---|---|---|
| 0 | 22.5 | 0.333333 |
| 1 | 27.5 | 0.000000 |
| 2 | 35.0 | 0.333333 |
The optimal cut-point is \(c=27.5\), producing pure child nodes (2 “Yes” on the left, 2 “No” on the right) and yielding a weighted Gini of 0.
Consider a dataset predicting whether a customer purchases a laptop computer (buy_laptop). Predictor features are age, income, student, and credit_rating.
datos = pd.DataFrame({
"id": range(1, 15),
"age": ["youth", "youth", "middle_aged", "senior", "senior", "senior", "middle_aged", "youth", "youth", "senior", "youth", "middle_aged", "middle_aged", "senior"],
"income": ["high", "high", "high", "medium", "low", "low", "low", "medium", "low", "medium", "medium", "medium", "high", "medium"],
"student": ["no", "no", "no", "no", "yes", "yes", "yes", "no", "yes", "yes", "yes", "no", "yes", "no"],
"credit_rating": ["fair", "excellent", "fair", "fair", "fair", "excellent", "excellent", "fair", "fair", "fair", "excellent", "excellent", "fair", "excellent"],
"buy_laptop": ["no", "no", "yes", "yes", "yes", "no", "yes", "no", "yes", "yes", "yes", "yes", "yes", "no"]
})
datos| id | age | income | student | credit_rating | buy_laptop | |
|---|---|---|---|---|---|---|
| 0 | 1 | youth | high | no | fair | no |
| 1 | 2 | youth | high | no | excellent | no |
| 2 | 3 | middle_aged | high | no | fair | yes |
| 3 | 4 | senior | medium | no | fair | yes |
| 4 | 5 | senior | low | yes | fair | yes |
| 5 | 6 | senior | low | yes | excellent | no |
| 6 | 7 | middle_aged | low | yes | excellent | yes |
| 7 | 8 | youth | medium | no | fair | no |
| 8 | 9 | youth | low | yes | fair | yes |
| 9 | 10 | senior | medium | yes | fair | yes |
| 10 | 11 | youth | medium | yes | excellent | yes |
| 11 | 12 | middle_aged | medium | no | excellent | yes |
| 12 | 13 | middle_aged | high | yes | fair | yes |
| 13 | 14 | senior | medium | no | excellent | no |
The target label contains 9 “yes” and 5 “no” instances, giving an initial root impurity:
gini_inicial = gini(datos["buy_laptop"])
print(f"Initial Gini = {gini_inicial:.3f}")Initial Gini = 0.459Evaluating all non-equivalent binary partitions across categorical features:
def weighted_gini_categorical(df, feature, target, left_values):
left_values = set(left_values)
left = df[df[feature].isin(left_values)]
right = df[~df[feature].isin(left_values)]
n = len(df)
return (len(left)/n)*gini(left[target]) + (len(right)/n)*gini(right[target])
def best_categorical_split(df, feature, target):
values = sorted(df[feature].unique())
rows = []
for left, right in binary_partitions(values):
wg = weighted_gini_categorical(df, feature, target, left)
rows.append({
"feature": feature,
"left_subset": tuple(sorted(left)),
"right_subset": tuple(sorted(right)),
"weighted_gini": wg,
"gini_reduction": gini(df[target]) - wg
})
return pd.DataFrame(rows).sort_values("weighted_gini")
resumen = pd.concat([
best_categorical_split(datos, col, "buy_laptop").head(1)
for col in ["age", "income", "student", "credit_rating"]
], ignore_index=True)
resumen.sort_values("weighted_gini")| feature | left_subset | right_subset | weighted_gini | gini_reduction | |
|---|---|---|---|---|---|
| 0 | age | (middle_aged,) | (senior, youth) | 0.357143 | 0.102041 |
| 2 | student | (no,) | (yes,) | 0.367347 | 0.091837 |
| 3 | credit_rating | (excellent,) | (fair,) | 0.428571 | 0.030612 |
| 1 | income | (high,) | (low, medium) | 0.442857 | 0.016327 |
Here, isolating category middle_aged on feature age yields a substantial Gini reduction because all middle_aged records in the dataset belong to class “yes”. CART recurses on child nodes until stopping criteria are met.
Gini reduction measures absolute purity improvement relative to parent node impurity. For instance, if root impurity is:
\[ Gini(D)=0.459, \]
and a candidate split produces:
\[ Gini_s(D)=0.357, \]
the Gini reduction is:
\[ \Delta Gini = 0.459-0.357=0.102. \]
Higher Gini reduction signals a better split. CART systematically tests all available feature splits at a node, selecting the one with maximum impurity reduction, and repeats this process recursively on each child node.
Trees cannot grow indefinitely without overfitting. Partitioning stops when any of the following conditions are met:
min_samples_split);max_depth) has been reached;Stopping rules play a critical role: unconstrained trees memorize training noise, ruining generalization performance.
A key architectural feature of CART is cost-complexity pruning. The tree is initially allowed to grow deep, after which weak branches providing minimal predictive gain relative to tree complexity are pruned (Breiman et al. 1984).
For tree \(T\), cost-complexity objective combines empirical error with a complexity penalty:
where \(R(T)\) is empirical training error, \(|T|\) is the number of terminal leaf nodes, and \(\alpha \ge 0\) controls complexity penalty. Setting \(\alpha=0\) keeps the unpruned full tree. Larger \(\alpha\) values favor smaller, simpler trees.
Pruning yields simpler, more interpretable models less prone to overfitting. In scikit-learn, cost-complexity pruning is configured via ccp_alpha (Pedregosa et al. 2011).
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.compose import ColumnTransformer
from sklearn.preprocessing import OneHotEncoder
from sklearn.pipeline import Pipeline
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
X = datos[["age", "income", "student", "credit_rating"]]
y = datos["buy_laptop"]
preprocess = ColumnTransformer(
transformers=[("cat", OneHotEncoder(handle_unknown="ignore"), X.columns)]
)
modelo = Pipeline(steps=[
("preprocess", preprocess),
("tree", DecisionTreeClassifier(criterion="gini", random_state=42))
])
modelo.fit(X, y)
pred = modelo.predict(X)
print(f"Training Accuracy = {accuracy_score(y, pred):.3f}")Training Accuracy = 1.000import matplotlib.pyplot as plt
modelo_simple = Pipeline(steps=[
("preprocess", preprocess),
("tree", DecisionTreeClassifier(
criterion="gini",
max_depth=3,
random_state=42
))
])
modelo_simple.fit(X, y)
feature_names = modelo_simple.named_steps["preprocess"].get_feature_names_out()
plt.figure(figsize=(14, 6))
plot_tree(
modelo_simple.named_steps["tree"],
feature_names=feature_names,
class_names=modelo_simple.named_steps["tree"].classes_,
filled=True,
rounded=True
)
plt.show()
Visualizing decision trees enables inspecting learned split conditions, node impurities, and leaf class distributions. Interpretability remains a chief advantage of decision trees over black-box models.
Trees translate directly into IF-THEN rules. Each root-to-leaf path forms a single rule. For example:
\[ \text{IF age} \neq \text{middle\_aged AND student} = \text{yes THEN buy\_laptop} = \text{yes}. \]
Extracted rules make model logic transparent to non-technical stakeholders, allowing auditability for bias or counter-intuitive logic.
from sklearn.tree import export_text
arbol = modelo_simple.named_steps["tree"]
reglas = export_text(arbol, feature_names=list(feature_names))
print(reglas)|--- cat__age_middle_aged <= 0.50
| |--- cat__student_yes <= 0.50
| | |--- cat__age_senior <= 0.50
| | | |--- class: no
| | |--- cat__age_senior > 0.50
| | | |--- class: no
| |--- cat__student_yes > 0.50
| | |--- cat__credit_rating_fair <= 0.50
| | | |--- class: no
| | |--- cat__credit_rating_fair > 0.50
| | | |--- class: yes
|--- cat__age_middle_aged > 0.50
| |--- class: yes
While this chapter focuses on classification, CART applies equally to regression tasks. For regression trees, leaf nodes predict continuous numerical values (typically node mean target values).
Split selection in regression minimizes node variance or Residual Sum of Squares (RSS):
Thus, CART unifies classification and regression under a common framework: recursively partitioning feature space into internally homogeneous regions.
CART training complexity depends on sample size \(n\), feature count \(m\), feature types, and final tree depth. For numerical features, sorting values at each node takes \(O(mn \log n)\) initial time.
Overall training complexity for balanced binary trees can be estimated as:
\[ O(mn\log n). \]
Factors influencing complexity:
Hyperparameters like max_depth, min_samples_split, and ccp_alpha keep computational and structural complexity in check.
CART offers significant benefits:
Key limitations include:
CART is a cornerstone decision tree algorithm. Its core mechanic is recursively partitioning feature space using binary splits to minimize node impurity. In classification, the Gini index provides an effective impurity measure; in regression, RSS minimization guides partitioning.
The CART framework combines interpretability, versatility, and mathematical clarity. Impurity-weighted split selection, Gini gain maximization, and cost-complexity pruning allow building accurate models while controlling overfitting. Beyond its standalone utility, CART provides the essential foundation for state-of-the-art ensemble techniques across modern data science.