Brayden Zhang

Decision Trees

3 min read

A decision tree is a model that predicts a target by recursively splitting the feature space into axis-aligned regions, choosing at each node the feature and threshold that best separate the data according to an impurity criterion.

Recursive Partitioning

Starting from the root with all training examples, the tree greedily picks the split that most reduces impurity, sends examples left or right based on a test like , and recurses on each child. Prediction for a new point follows the tests down to a leaf, whose stored value (majority class or mean target) is the output.

Splitting Criteria

For classification, two common impurity measures on a node with class proportions are:

A split with subsets is scored by the information gain (impurity decrease):

Gini vs entropy

Both are minimized at a pure node and maximized at a uniform mix. Gini is cheaper (no logarithm) and is the sklearn default; entropy penalizes impurity slightly more aggressively. In practice they usually produce very similar trees.

Stopping and Pruning

A fully grown tree can memorize the training set (one leaf per point), giving zero training error but poor generalization. Controls:

  • Pre-pruning (early stopping): limit max_depth, require min_samples_split or min_samples_leaf, or demand a minimum impurity decrease.
  • Post-pruning: grow fully, then collapse nodes that do not help a validation metric (cost-complexity pruning trades tree size against error via a penalty ).

Overfitting

Deep unpruned trees have very high variance: small data changes can reshape the whole tree. This is exactly what motivates averaging many trees (see Random Forest) to trade variance for a little bias.

Regression Trees

For continuous targets, replace impurity with variance (or sum of squared error) within a node, and let each leaf predict the mean target of its examples:

Code: From-Scratch Gini Tree

import numpy as np
 
def gini(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return 1.0 - np.sum(p ** 2)
 
def best_split(X, y):
    n, d = X.shape
    best = {"gain": 0.0, "feat": None, "thr": None}
    parent = gini(y)
    for j in range(d):
        for thr in np.unique(X[:, j]):
            left = X[:, j] <= thr
            if left.sum() == 0 or left.sum() == n:
                continue
            wl, wr = left.mean(), 1 - left.mean()
            child = wl * gini(y[left]) + wr * gini(y[~left])
            gain = parent - child
            if gain > best["gain"]:
                best = {"gain": gain, "feat": j, "thr": thr}
    return best
 
def build_tree(X, y, depth=0, max_depth=5, min_samples=2):
    # leaf conditions
    if len(y) < min_samples or depth >= max_depth or len(np.unique(y)) == 1:
        vals, counts = np.unique(y, return_counts=True)
        return {"leaf": vals[np.argmax(counts)]}
    s = best_split(X, y)
    if s["feat"] is None:
        vals, counts = np.unique(y, return_counts=True)
        return {"leaf": vals[np.argmax(counts)]}
    mask = X[:, s["feat"]] <= s["thr"]
    return {
        "feat": s["feat"], "thr": s["thr"],
        "left": build_tree(X[mask], y[mask], depth + 1, max_depth, min_samples),
        "right": build_tree(X[~mask], y[~mask], depth + 1, max_depth, min_samples),
    }
 
def predict_one(node, x):
    if "leaf" in node:
        return node["leaf"]
    branch = node["left"] if x[node["feat"]] <= node["thr"] else node["right"]
    return predict_one(branch, x)

In practice use sklearn

from sklearn.tree import DecisionTreeClassifier; clf = DecisionTreeClassifier(criterion="gini", max_depth=5).fit(X, y). It handles efficient split search, regression via DecisionTreeRegressor, and cost-complexity pruning through the ccp_alpha argument.

Decision trees are the base learner behind Random Forest and other Ensemble Learning methods, which exist precisely to tame a single tree’s high-variance position on the Bias-Variance Tradeoff.

Graph View