Decision trees: how CART chooses every split
A decision tree asks one yes-or-no question at a time. At every node it tries every threshold on every feature and keeps the one that makes the children purest. Add your own points and watch the rules change.
Interactive simulation. It needs JavaScript; the text below explains what it shows.
What you are looking at
The plot shows the regions the tree assigns to each class and every split line (thicker lines are higher in the tree). The panel lists the tree as rules, with the information gain of each split and the class counts in each leaf.
Things to try
- Start at depth 1 on XOR: no single split helps, so the tree must go two levels deep.
- Set depth 8 and leaf size 1: training accuracy hits 100% by isolating the noisy points.
- Click to add a few points of the wrong class inside a region and watch new splits appear.
How it works in real systems
Single trees are rarely used alone; random forests and gradient boosting (XGBoost, LightGBM, CatBoost) combine hundreds of them and remain the strongest classical models for tabular data. Their splits are found exactly this way, with histogram tricks for speed.
Code lab
The same idea in real code, step by step. Copy each block into a notebook or a file and run it in order.
Step 1 · Impurity and the best split, from scratch
Gini impurity of a node with class shares p is 1 − Σ p². A split is good when the weighted impurity of the children is much lower than the parent's.
import numpy as np
def gini(y):
p = np.bincount(y, minlength=2) / max(1, len(y))
return 1 - (p ** 2).sum()
def best_split(X, y, min_leaf=1):
best = (0, None, None) # (gain, feature, threshold)
parent = gini(y)
for f in range(X.shape[1]):
order = np.argsort(X[:, f]); xs, ys = X[order, f], y[order]
for i in range(min_leaf, len(y) - min_leaf + 1):
if i < len(y) and xs[i - 1] == xs[i]: continue
gain = parent - (i * gini(ys[:i]) + (len(y) - i) * gini(ys[i:])) / len(y)
if gain > best[0]: best = (gain, f, (xs[i - 1] + xs[min(i, len(y) - 1)]) / 2)
return best
Step 2 · Grow the tree recursively
Split until the node is pure, too small, or at the maximum depth.
def grow(X, y, depth=0, max_depth=3, min_leaf=3):
gain, f, t = best_split(X, y, min_leaf)
if depth == max_depth or f is None or gain <= 0:
return {"leaf": int(np.bincount(y).argmax()), "n": len(y)}
L = X[:, f] < t
return {"f": f, "t": t, "l": grow(X[L], y[L], depth + 1, max_depth, min_leaf),
"r": grow(X[~L], y[~L], depth + 1, max_depth, min_leaf)}
def predict(node, x):
while "leaf" not in node:
node = node["l"] if x[node["f"]] < node["t"] else node["r"]
return node["leaf"]
rng = np.random.default_rng(0)
X = rng.uniform(0, 1, (200, 2)); y = ((X[:, 0] > 0.5) ^ (X[:, 1] > 0.5)).astype(int) # XOR
tree = grow(X, y)
print(np.mean([predict(tree, x) == t for x, t in zip(X, y)]))
Step 3 · With scikit-learn, and why forests win
export_text prints the same kind of rules as the simulation. A single deep tree overfits; averaging many randomised trees (random forest) or adding shallow trees one by one (gradient boosting) generalises far better.
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.ensemble import RandomForestClassifier, HistGradientBoostingClassifier
from sklearn.model_selection import cross_val_score
t = DecisionTreeClassifier(max_depth=3, min_samples_leaf=3, criterion="gini").fit(X, y)
print(export_text(t, feature_names=["x", "y"]))
for m in [DecisionTreeClassifier(), RandomForestClassifier(300), HistGradientBoostingClassifier()]:
print(type(m).__name__, cross_val_score(m, X, y, cv=5).mean().round(3))