AI Foundations

Decision Trees and Random Forests

A decision tree is a model that predicts by recursively splitting data on feature thresholds; a random forest averages many decorrelated trees, each trained on a bootstrap sample with a random subset of features, to cut the high variance that makes single trees overfit.

What a decision tree is

A decision tree is a supervised learning model that makes predictions by asking a sequence of yes or no questions about the input features. Each internal node tests one feature against a threshold (for example, "is petal length less than 2.5 cm?"), each branch corresponds to an answer, and each leaf holds a prediction: a class label for classification or a numeric value for regression. To classify a new example, the model starts at the root and follows the branches dictated by the example's feature values until it reaches a leaf.

The dominant algorithm for building such trees is CART (Classification and Regression Trees), introduced by Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone in their 1984 book of the same name. CART grows binary trees through recursive binary splitting: at each node it searches over every feature and every candidate threshold, picks the single split that most improves a purity criterion, partitions the data into two children, and repeats the process on each child until a stopping rule fires. scikit-learn uses an optimized version of CART.

Because the splits are axis-aligned and the prediction at each leaf is a simple constant, a fully grown tree is one of the most interpretable models available. The path from root to leaf reads as a chain of human-readable rules, which is why trees remain popular in domains where an auditable decision matters more than the last point of accuracy.

Internal nodes test a feature against a threshold; leaves hold the prediction.
CART grows binary trees by greedy recursive splitting, one split at a time.
Trees handle both classification (class labels) and regression (numeric outputs).
A trained tree is directly readable as a set of if-then rules.

How splits are chosen: impurity and information gain

Choosing a split means scoring how well a candidate threshold separates the data, then keeping the best one. For classification, CART measures the impurity of a node, meaning how mixed its class labels are. Two impurity measures dominate. Gini impurity is the probability that two items drawn at random from the node would have different labels; entropy comes from information theory and measures the average uncertainty of the label distribution. A pure node, where every example shares one label, has zero impurity under both measures.

A split is scored by how much it lowers impurity, weighted by the size of each child node. When entropy is the criterion, this reduction is called information gain. The algorithm evaluates every feature and threshold, computes the weighted impurity of the resulting children, and selects the split with the largest decrease. In practice Gini and entropy produce very similar trees, and Gini is slightly cheaper to compute because it avoids a logarithm, which is why it is scikit-learn's default criterion.

Regression trees use a different criterion since there are no class labels to count. Instead they minimize variance, typically by reducing the mean squared error within each child node. A split is good if the target values inside each resulting child are tightly clustered around their own mean. The leaf then predicts that mean.

Gini(t) = 1 - Σ_k p_k²     Entropy(t) = - Σ_k p_k log₂ p_k     IG = Entropy(parent) - Σ_j (n_j / n) · Entropy(child_j)

For a node t, p_k is the fraction of examples in class k. Gini impurity and entropy both reach 0 for a pure node. Information gain (IG) is the parent entropy minus the size-weighted average entropy of the children produced by a split.

Gini impurity and entropy both measure how mixed the labels at a node are.
Information gain is the entropy drop from a split, weighted by child sizes.
Gini is the default in scikit-learn because it skips the logarithm entropy needs.
Regression trees split to reduce variance (mean squared error) instead of impurity.

Why single trees overfit

Left unconstrained, recursive splitting continues until every leaf is pure, often isolating individual training examples. Such a tree achieves near-perfect accuracy on its training data while generalizing poorly, the textbook signature of overfitting. The deeper cause is variance: a small change in the training set, such as a few resampled rows, can flip an early split and reshape the entire tree below it. Decision trees are therefore described as low-bias, high-variance models.

The classical remedy is pruning. Cost-complexity pruning, part of the original CART method, first grows a large tree and then collapses the subtrees whose contribution to accuracy does not justify their added complexity, governed by a penalty on the number of leaves. An alternative is pre-pruning, which stops growth early by limiting tree depth, requiring a minimum number of samples per leaf, or demanding a minimum impurity decrease per split.

Pruning a single tree trades a little bias for less variance, but it does not eliminate the instability. The high variance of trees is precisely the weakness that ensemble methods exploit, and it is the reason a forest of trees usually beats any single pruned tree.

Unconstrained trees grow until leaves are pure and memorize the training set.
Tiny changes in data can flip early splits, so trees are high-variance models.
Cost-complexity pruning removes weak subtrees using a leaf-count penalty.
Pre-pruning caps depth, leaf size, or minimum impurity decrease to limit growth.

Random forests: decorrelating the trees

A random forest, introduced by Leo Breiman in his 2001 paper "Random Forests" (Machine Learning, volume 45, pages 5 to 32), turns the high variance of single trees into an advantage by averaging many of them. It builds on bagging, the broader ensemble idea of training each model on a bootstrap sample (a random draw of the training rows with replacement) and aggregating their predictions by voting or averaging. Averaging independent predictors reduces variance, so the ensemble is more stable than any member.

The defining addition of random forests is feature subsetting. At every split, instead of searching all features, each tree considers only a random subset (commonly the square root of the feature count for classification). This deliberately weakens individual trees but, crucially, decorrelates them: it prevents a few dominant features from forcing every tree into the same early splits. Because variance reduction from averaging depends on the trees being only weakly correlated, this random feature selection is what lets a forest drive variance down far more than bagging alone. For the broader landscape of bagging and boosting, see the ensemble-methods entry.

Forest trees are usually grown deep and left unpruned. A single deep tree overfits, but its errors are largely independent across trees, so averaging cancels much of the noise while preserving the low bias. The result is a model that is accurate, resistant to overfitting, and needs little tuning, which is much of why random forests became a default baseline for tabular data.

python

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier

X, y = load_iris(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, random_state=0)

# A single decision tree: high variance, easy to overfit
tree = DecisionTreeClassifier(criterion="gini", random_state=0).fit(X_tr, y_tr)
print("tree test acc:", tree.score(X_te, y_te))

# A random forest: bagging + random feature subsetting, with OOB error
rf = RandomForestClassifier(
    n_estimators=300, max_features="sqrt",
    oob_score=True, random_state=0,
).fit(X_tr, y_tr)
print("forest test acc:", rf.score(X_te, y_te))
print("out-of-bag score:", rf.oob_score_)
print("feature importances:", rf.feature_importances_)

Training a single tree and a random forest in scikit-learn. The forest exposes oob_score_ (an internal generalization estimate) and feature_importances_ (impurity-based importances).

Each tree trains on a bootstrap sample: rows drawn with replacement.
At each split, only a random feature subset is considered (often √(features)).
Feature subsetting decorrelates trees so averaging cancels more variance.
Trees are grown deep and unpruned; the ensemble, not the tree, controls overfitting.

Out-of-bag error and feature importance

Bootstrap sampling gives random forests a built-in validation set for free. Each bootstrap draw omits roughly a third of the training rows, since the probability that a given row is never selected across n draws approaches 1/e, about 0.368. For any row, the trees that did not see it during training form a held-out sub-ensemble, and their pooled prediction yields the out-of-bag (OOB) error. Averaged over all rows, OOB error gives a near-unbiased estimate of generalization performance without setting aside a separate validation split or running cross-validation.

Random forests also produce feature importance scores. The standard impurity-based measure, exposed by scikit-learn as feature_importances_, totals the impurity decrease that each feature contributes across all splits in all trees, normalized to sum to one. It is fast but biased toward high-cardinality and continuous features. A more reliable alternative is permutation importance, which shuffles one feature's values and measures how much OOB or validation accuracy drops; a large drop means the model genuinely relied on that feature.

Both quantities make forests more than a black box. OOB error supports model selection and early stopping; importance scores guide feature selection and offer a coarse window into which inputs drive predictions, though they describe associations within the model rather than causal effects.

About 36.8% of rows are out-of-bag for each tree (the 1/e bootstrap limit).
OOB error is a near-unbiased generalization estimate needing no separate holdout.
Impurity-based importance sums each feature's split improvements across the forest.
Permutation importance is less biased but costs extra shuffled evaluations.

Strengths, limits, and when to use them

Decision trees and random forests handle mixed numeric and categorical features, need little preprocessing (no feature scaling, since splits are threshold-based), tolerate missing values reasonably well, and capture non-linear interactions automatically. Random forests in particular tend to work well out of the box, which makes them a strong baseline on tabular data and a common benchmark for newer methods.

The trade-offs are real. A single tree is interpretable but unstable; a forest is stable but no longer a readable set of rules, trading the transparency of one tree for the accuracy of many. Forests can be memory-heavy and slow to predict when they contain hundreds of deep trees, and like all tree models they extrapolate poorly outside the range of the training data because every leaf prediction is bounded by the values seen during training.

On many structured tabular problems, gradient-boosted trees (a boosting ensemble covered under ensemble-methods) edge out random forests in raw accuracy, while deep neural networks tend to win on raw images, audio, and text. Random forests remain a dependable, low-tuning default when a reliable model is needed quickly and the data is tabular.

Tree models need no feature scaling and handle non-linear interactions natively.
A forest trades the single tree's readable rules for ensemble accuracy.
Tree models extrapolate poorly beyond the training data's observed range.
Gradient boosting often beats forests on accuracy; deep nets win on raw perceptual data.

Key takeaways

A decision tree predicts by recursively splitting features on thresholds; CART (Breiman et al. 1984) grows binary trees greedily.
Classification splits minimize Gini impurity (1 - Σ p_k²) or entropy; information gain is the entropy reduction from a split, and regression splits minimize variance.
Unconstrained single trees overfit because they are low-bias, high-variance: small data changes reshape the whole tree.
Random forests (Breiman 2001) average many bootstrap-trained trees and add random feature subsetting at each split to decorrelate them.
Decorrelation is what makes averaging effective; out-of-bag error gives a near-unbiased generalization estimate for free.
Forests expose feature_importances_; impurity-based importance is fast but biased, while permutation importance is more reliable.

Frequently asked questions

A decision tree is a single model that splits data on feature thresholds until it reaches leaf predictions. A random forest is an ensemble of many such trees, each trained on a bootstrap sample of the rows and a random subset of features at each split. The forest averages or votes across its trees, which sharply reduces the high variance that makes a single tree overfit.

A tree keeps splitting until its leaves are pure, which can mean memorizing individual training rows. It is a low-bias, high-variance model: a small change in the training data can flip an early split and rebuild the tree below it. Pruning, depth limits, and minimum-samples-per-leaf constraints reduce this, and ensembling into a random forest reduces it further.

In practice they produce very similar trees, so the choice rarely changes accuracy much. Gini impurity is the default in scikit-learn because it avoids computing a logarithm and is slightly faster. Entropy, paired with information gain, is the information-theoretic measure and can be preferred when that interpretation matters; trying both via cross-validation is reasonable but seldom decisive.

Because each tree trains on a bootstrap sample, roughly a third of the rows are left out of each tree. For any row, the trees that never saw it form a held-out sub-ensemble, and pooling their predictions gives the out-of-bag error. Averaged over all rows, it is a near-unbiased estimate of generalization performance, so it can stand in for a separate validation set or cross-validation.

More trees lower variance and never increase overfitting, but accuracy plateaus and compute grows linearly, so there is a point of diminishing returns. scikit-learn defaults to 100, and values in the low hundreds (such as 200 to 500) are common starting points. Monitoring the OOB error as trees are added shows when adding more stops helping.

The default impurity-based scores (feature_importances_ in scikit-learn) are fast but biased toward high-cardinality and continuous features, so they can overstate noisy variables. Permutation importance, which shuffles a feature and measures the accuracy drop, is more trustworthy. In every case, importance reflects how the model uses a feature, not a causal effect on the outcome.

Put the idea into practice

MemX is an AI memory agent built on these ideas: store anything, skip the folders, and find it again by asking in plain English.

Try MemX Free