Decision Trees

Prediction answered one question. Given some features, how do we make predictions? Representation asks the next question. What if the features and the model shape are not expressive enough?

Imagine predicting whether someone should be approved to buy a house. The features are income, age, and savings. Linear models try to draw one global boundary. But the real decision process may look more like a sequence of rules.

if income > 100_000:
    if savings > 50_000:
        approve
    else:
        reject
else:
    reject

That does not look like one equation. It looks like a set of questions. So instead of fitting one global function, a decision tree learns a hierarchy of decisions.

A decision tree repeatedly asks yes or no questions. Each question splits the data into smaller pieces. Eventually each leaf predicts a class.

Income > 100k?
  no  -> Reject
  yes -> Savings > 50k?
           yes -> Approve
           no  -> Reject

A linear model learns one expression.

A tree learns many local rules. This makes trees powerful for thresholds, rule-like behaviour, and interactions. If the true boundary is shaped like an L, one line cannot represent it well. A tree can carve that shape using several rectangular regions.

The limitation we are overcoming is the global nature of linear models. A tree can make different decisions in different parts of the feature space.

A tree needs to choose which question to ask. It prefers questions that make the child nodes cleaner than the parent node.

The parent has 60 buyers and 40 non-buyers. It is mixed. After asking whether income is above 100k, the left and right nodes are much cleaner. That is why the tree likes the split.

Gini Impurity

A node is pure if almost every example belongs to one class. Gini impurity measures how mixed a node is.

Here $p_i$ is the fraction of class $i$ in the node. Smaller Gini means a purer node.

If a node contains 10 cats and 0 dogs, the probabilities are $1$ and $0$.

If a node contains 5 cats and 5 dogs, the probabilities are both $0.5$.

If a node contains 8 cats and 2 dogs, the probabilities are $0.8$ and $0.2$.

Squaring rewards dominance. As one probability grows, its square grows quickly. The sum of squared probabilities approaches one, so impurity approaches zero.

Entropy

Entropy measures uncertainty. It comes from information theory, where unlikely events carry more information than common ones.

A pure node with 10 cats and 0 dogs has no uncertainty.

By convention, $0\log 0=0$. A perfectly mixed node has maximum uncertainty for two classes.

A mostly pure node with 8 cats and 2 dogs has lower uncertainty.

Gini and entropy usually choose similar splits. They both ask the same question. How mixed is this node?

Choosing A Split

For every possible question, the tree computes the impurity of the parent, the weighted impurity of the children, and the reduction in impurity. It chooses the split with the largest reduction.

This small implementation builds a binary classification tree with Gini impurity. It searches thresholds, chooses the split with the largest impurity reduction, and recurses until the tree reaches a stopping condition.

import numpy as np

def gini(y):
    if len(y) == 0:
        return 0
    _, counts = np.unique(y, return_counts=True)
    p = counts / len(y)
    return 1 - np.sum(p ** 2)

def best_split(X, y):
    best = {"feature": None, "threshold": None, "gain": 0}
    parent = gini(y)

    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for threshold in thresholds:
            left = X[:, feature] <= threshold
            right = ~left
            if left.sum() == 0 or right.sum() == 0:
                continue

            child_impurity = (
                left.mean() * gini(y[left])
                + right.mean() * gini(y[right])
            )
            gain = parent - child_impurity

            if gain > best["gain"]:
                best = {
                    "feature": feature,
                    "threshold": threshold,
                    "gain": gain,
                }

    return best

class Node:
    def __init__(self, prediction=None, feature=None, threshold=None, left=None, right=None):
        self.prediction = prediction
        self.feature = feature
        self.threshold = threshold
        self.left = left
        self.right = right

def majority_class(y):
    values, counts = np.unique(y, return_counts=True)
    return values[np.argmax(counts)]

def build_tree(X, y, depth=0, max_depth=3, min_samples=2):
    if depth == max_depth or len(y) < min_samples or gini(y) == 0:
        return Node(prediction=majority_class(y))

    split = best_split(X, y)
    if split["feature"] is None:
        return Node(prediction=majority_class(y))

    left_mask = X[:, split["feature"]] <= split["threshold"]
    right_mask = ~left_mask

    return Node(
        feature=split["feature"],
        threshold=split["threshold"],
        left=build_tree(X[left_mask], y[left_mask], depth + 1, max_depth),
        right=build_tree(X[right_mask], y[right_mask], depth + 1, max_depth),
    )

def predict_one(node, x):
    if node.prediction is not None:
        return node.prediction
    if x[node.feature] <= node.threshold:
        return predict_one(node.left, x)
    return predict_one(node.right, x)