On this page
A decision tree classifies a point by asking yes-or-no questions about its features.
Each question is a threshold on one feature; a leaf votes for the class most common among its training points. A regression tree's leaf predicts its points' mean.
A tree (Section 3) is grown once, a forest (Section 4) grows each tree once on its own resample, and boosting (Section 6) adds one small tree per round. One balanced tree costs about points × features × log(points) (scikit-learn documentation).
This schematic follows the notebook's hand-built Iris tree: petal features, three species, root cut at the petal-width median.
The tree tries every feature and threshold and keeps the split whose children are purest, scored by one of two classic measures.
The Decision_tree notebook in the Machine-Learning-Concepts repo cuts Iris petal width at its median by hand: weighted child gini 0.443. The best root split scores 0.333, a tie between petal length and petal width; either cut separates setosa.
Split scoring in NumPy; f and 1 − f are the children's shares.
import numpy as np
def gini(y):
p = np.bincount(y) / len(y)
return 1 - (p ** 2).sum()
def splits(X):
for j in range(X.shape[1]):
vals = np.unique(X[:, j])
for thr in vals[:-1]:
yield j, thr
def best_split(X, y):
best = (0.0, None, None)
for j, thr in splits(X):
left = X[:, j] <= thr
f = left.mean()
gl = gini(y[left])
gr = gini(y[~left])
kids = f*gl + (1-f)*gr
gain = gini(y) - kids
if gain > best[0]:
best = (gain, j, thr)
return bestThe tree recurses on each child until a max depth or until every leaf is pure; depth 1 asks one question. Unchecked it memorizes the noise (depth 125 in the notebook), the high-variance failure of Bias and Variance.
Each point has features x1 and x2 and a class label y. The tree grows greedily: each node keeps its own best split, and earlier splits are never revisited.
Figure 4. Pick the purest split, cut, repeat on each side, then let the leaves vote.
A random forest trains many deep trees, each on a bootstrap resample (same size as the data, drawn with replacement), and averages their votes.
A forest by hand, each tree on its own bootstrap sample idx; X, y are training points and Xte held-out test points.
import numpy as np
from sklearn.tree import DecisionTreeClassifier
Tree = DecisionTreeClassifier
rng = np.random.default_rng(0)
T, n = 20, len(X)
ts = []
for t in range(T):
idx = rng.integers(0, n, n)
h = Tree(max_depth=5)
h.fit(X[idx], y[idx])
ts.append(h)
P = [h.predict(Xte) for h in ts]
votes = np.mean(P, axis=0)
y_hat = (votes > 0.5).astype(int)Figure 6. Trained on 400 of 500 blob points: one tree's boundary is jagged around stray points; more voting trees smooth it.
Each tree sits out about a third of the data.
The forest's vote on each point, counting only the trees that never saw it, gives the out-of-bag error, an estimate of test error that needs no held-out data.
With oob_score=True the forest stores that accuracy, and one minus it is the out-of-bag error.
from sklearn.ensemble import RandomForestClassifier
RF = RandomForestClassifier
rf = RF(20, max_depth=5)
rf.set_params(oob_score=True)
rf.set_params(max_features=None)
rf.fit(X, y)
oob_error = 1 - rf.oob_score_The Random Forests paper (Breiman, 2001) tested this on sonar returns labeled mine or rock, varying m (scikit-learn's max_features; the paper writes F). Strength is each tree's own accuracy; correlation is how alike two trees' votes are. Figure 7 redraws the paper's Figure 1 from values read off the published plot (PDF).
Boosting grows trees in sequence, each fitting the mistakes left so far.
Each small tree fits the residuals, the signed mistakes so far, and nudges the prediction toward it.
Boosting by hand with step size LR.
import numpy as np
from sklearn.tree import DecisionTreeRegressor
Tree = DecisionTreeRegressor
LR, ROUNDS = 0.01, 100
F = np.full(len(y), y.mean())
for _ in range(ROUNDS):
r = y - F
h = Tree(max_depth=3)
h.fit(X, r)
F = F + LR * h.predict(X)The notebook's 100 rounds at learning rate 0.01 land at 82.7%, still underfit: each round moves the prediction only slightly.
Figure 9. Each round fits the mistakes left; halos, rings on points still off by more than 0.45, fall from 400 to 36 by round 20.
A forest and a boosted model on the same split.
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier as RF
from sklearn.ensemble import HistGradientBoostingClassifier as HGB
from sklearn.model_selection import train_test_split
n, d = 5000, 20
X, y = make_classification(n, d)
parts = train_test_split(X, y)
Xtr, Xte, ytr, yte = parts
forest = RF(100, oob_score=True)
forest.set_params(n_jobs=-1)
forest.fit(Xtr, ytr)
boost = HGB(learning_rate=0.1)
boost.fit(Xtr, ytr)
oob = forest.oob_score_
acc_rf = forest.score(Xte, yte)
acc_gb = boost.score(Xte, yte)| Setting | Where it enters | Raise it | Lower it | Default |
|---|---|---|---|---|
n_estimators, T | Trees in the forest vote | Smoother vote, more time; adding trees does not raise test error, it stops helping | At 1, a single jagged tree | 100 |
max_depth | Questions on one path | Finer cuts until it memorizes noise | At 1, one question (a stump) | None (grow until pure) in RandomForestClassifier; None in HistGradientBoostingClassifier, which caps each tree at 31 leaves (max_leaf_nodes) |
min_ | Smallest allowed leaf | Smoother, smaller trees | At 1, a leaf can hold one stray point | 1 in RandomForestClassifier, 20 in HistGradientBoostingClassifier |
max_, m | Inputs each split may choose from | Trees grow alike | Diverse but weaker trees | "sqrt" of the features in RandomForestClassifier |
learning_, LR | Step toward each new tree in the boosting card | Fits faster, overfits sooner | Needs many more rounds | 0.1 |
max_iter | Boosting rounds | Fits more of the residual | Underfits | 100, stopping early past 10,000 samples |
RandomForestClassifier trains its trees in parallel. HistGradientBoostingClassifier bins each feature into 255 bins for speed and native missing values; its rounds run in order. Permutation importance on held-out data is safer than impurity-based feature_importances_, which favor features with many distinct values.
Trees suit tabular data with mixed types or missing values, and models you need to read.
| Cause | Symptom | Fix |
|---|---|---|
| a deep tree memorized the noise | Train accuracy near 100%, test lower | cap the depth (depth limits are regularization for trees), prune, or vote a forest |
| every split tests one feature | Staircase boundary on a diagonal | add a combined feature such as x1 + x2, or use a linear model |
| greedy splits score one feature at a time, and in an XOR pattern neither helps alone | Misses a pattern that needs two features together | grow deeper or boost so later splits can pick it up |
| a leaf can only repeat values it saw | Flat predictions past the training range | a linear model when you must extrapolate |
| Method | What changes | When to use |
|---|---|---|
| Extra Trees | each cut point is drawn at random instead of searched | a faster forest that is often just as accurate |
| AdaBoost | reweights the points the last tree got wrong | boosting with very small trees |
| Gradient boosting | each tree fits the residuals (Section 6) | tabular data where accuracy matters most |
| XGBoost, LightGBM | histogram splits, a penalty on leaf weights, column sampling | production gradient boosting at scale |
| Pruning | grows deep, then cuts branches that do not pay for themselves | one readable tree that does not memorize |
In XGBoost, reg_lambda (default 1) penalizes large leaf weights, so raising it shrinks each tree's push, and colsample_bynode below its default 1 samples columns per split.
from xgboost import XGBClassifier
m = XGBClassifier()
m.set_params(tree_method="hist")
m.set_params(reg_lambda=1.0)
m.set_params(colsample_bynode=0.5)Trees cut one feature at a time; Support Vector Machines (SVM) draw one boundary with the widest margin between classes.