A decision tree predicts by asking a sequence of yes/no questions about the features — "is income ≤ 52k?", "is age ≤ 25?" — until it reaches a leaf that holds a prediction. Trees handle numeric and categorical inputs, need no feature scaling, capture interactions and non-linearities automatically, and can be read by a human. On their own they overfit easily; as building blocks they power the strongest tabular models in use today, Random Forest and Gradient Boosting.
This page focuses on classification trees (CART) under Classification; regression trees use the same algorithm with a variance criterion.
A tree is a binary graph. Each internal node holds a test xj ≤ t on a single feature; samples that pass go left, the rest go right. Each leaf stores the class counts of the training samples that landed there, so the tree can output both a hard label (the majority class) and a probability (the class fraction). Prediction is a walk from root to leaf: O(depth) comparisons, which makes trees very cheap at inference time.
The example shows why trees are popular in regulated settings: the path to "Reject" is literally income ≤ 52k and debt_ratio > 0.4. That explanation is exact, not an approximation — as long as the tree stays small.
CART builds the tree greedily, top-down. At each node it tries every feature and every candidate threshold (midpoints between sorted unique values) and picks the split that most reduces impurity. For a node with class proportions pk:
G = 1 − Σ pk2 — the probability of misclassifying a random sample labelled at random by the node's distribution. The scikit-learn default.H = −Σ pk log2 pk; the reduction is called information gain (ID3/C4.5 lineage).The split score is the weighted child impurity: (nL/n)·I(L) + (nR/n)·I(R); the best split minimizes it. Gini and entropy almost always pick similar splits; Gini is slightly cheaper to compute. Recursion stops when a node is pure, hits max_depth, has fewer than min_samples_split samples, or no split improves impurity by at least min_impurity_decrease.
Finding the optimal tree is NP-hard, so the greedy algorithm is a heuristic: it can miss splits that only pay off two levels down (the classic XOR problem). Ensembles compensate for this by averaging or sequentially correcting many greedy trees.
Every split is perpendicular to one feature axis, so a tree partitions the feature space into axis-aligned hyper-rectangles and predicts a constant in each. This gives trees two useful properties: they are invariant to monotone transforms of each feature (log, rank, scaling change nothing), and they handle interactions naturally (split 2a and 2b above can use different features).
The downside is that a diagonal or curved boundary must be approximated by a staircase of many small boxes. A linear model such as Logistic Regression represents the same boundary with a handful of parameters, which is why trees and linear models often have complementary strengths.
Grown to full depth, a tree keeps splitting until each leaf is pure, which memorizes noise: training error goes to zero while validation error climbs. Trees are also high-variance — a small change in the data can change the root split and therefore the whole tree. Controls:
max_depth, min_samples_leaf, min_samples_split, max_leaf_nodes. min_samples_leaf is often the most effective single knob because it also smooths leaf probabilities.R(T) + α|leaves(T)|. scikit-learn exposes the path via cost_complexity_pruning_path and the parameter ccp_alpha; choose α by cross-validation.
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.tree import DecisionTreeClassifier, export_text
X, y = load_breast_cancer(return_X_y=True, as_frame=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, stratify=y, random_state=0)
# 1) Full-depth tree: perfect on train, worse on test
full = DecisionTreeClassifier(random_state=0).fit(X_tr, y_tr)
print("full depth", full.get_depth(), "train", full.score(X_tr, y_tr), "test", round(full.score(X_te, y_te), 3))
# 2) Cost-complexity pruning, alpha chosen by CV
path = full.cost_complexity_pruning_path(X_tr, y_tr)
grid = GridSearchCV(
DecisionTreeClassifier(random_state=0),
{"ccp_alpha": np.unique(path.ccp_alphas), "min_samples_leaf": [1, 5, 10]},
cv=5,
).fit(X_tr, y_tr)
best = grid.best_estimator_
print("pruned depth", best.get_depth(), "leaves", best.get_n_leaves(),
"test", round(best.score(X_te, y_te), 3))
# 3) Human-readable rules and impurity-based importances
print(export_text(best, feature_names=list(X.columns), max_depth=3))
imp = sorted(zip(best.feature_importances_, X.columns), reverse=True)[:5]
for v, name in imp:
print(f"{name:<25} {v:.3f}")
export_text prints the tree as nested if/else rules. For plots use sklearn.tree.plot_tree. Impurity-based importances are fast but biased toward high-cardinality features; prefer sklearn.inspection.permutation_importance on held-out data when importance matters.
| Strength | Limitation |
|---|---|
| No scaling; mixed feature types; robust to monotone transforms and outliers in X. | High variance — unstable to small data changes. |
| Captures interactions and non-linear thresholds automatically. | Staircase approximation of smooth or diagonal boundaries. |
| Transparent rules when shallow. | Cannot extrapolate beyond the training range (constant leaves). |
| Fast inference; the base learner for RF, XGBoost, LightGBM. | Single trees are rarely the most accurate model. |
Use a single, shallow tree when the rules themselves are the deliverable (eligibility logic, triage, a model a domain expert must audit) or to explore which features and thresholds matter. When accuracy is the goal, use a tree ensemble.
class_weight or stratified sampling and evaluate with PR-AUC.