Decision Trees

Grow a tree split by split using Gini impurity and see how it partitions the plane

Intermediate

Dataset:

Max depth4Min samples to split5

Impurity

Show test points

Each region is a leaf, shaded by its majority class (stronger colour = purer leaf). The dashed box is the node being split next and the magenta line is its best threshold.

Splits: 0 / 10
Leaves / depth: 1 / 0
Train accuracy: 54%
Test accuracy: 47%

Split scan for the next node

Node with 140 samples (64 blue, 76 orange), Gini 0.496. Every threshold on x and on y is tried; the lowest weighted child impurity wins: y ≤ 0.550 (gain 0.168).

split on xsplit on yparent impurity

Accuracy vs max depth

training accuracytest accuracy

Deeper trees keep fitting the training set better, but past a point they memorise noise and test accuracy stalls or drops. Tap the chart to set max depth.

Tree

Left branch = condition true. [blue, orange] are the training samples reaching each node. The dashed node is the next one to split.

How a decision tree learns

A decision tree classifies a point by asking a sequence of simple questions. Start at the root, check one feature against a threshold, go left if the answer is yes and right if it is no, and repeat until you reach a leaf. The leaf predicts the majority class of the training samples that ended up there.

CART (Classification and Regression Trees) builds the tree top-down. For the current node it tries every feature and every threshold between neighbouring values, scores each candidate by how pure the two children would be, and keeps the best one. Then it repeats on each child until a stopping rule kicks in.

Axis-aligned splits

Each internal node asks one yes/no question about one feature, such as "x ≤ 0.42?". The plane is cut into rectangles.

Impurity

A node is pure when all its samples share a class. Gini impurity and entropy are both 0 for a pure node and largest for a 50/50 mix.

Greedy growth

CART picks the single best split for the current node and never looks ahead. It is fast, but can miss splits that only pay off later (XOR).

Stopping rules

Max depth and a minimum number of samples per split stop the tree before it memorises every noisy point.

Key formulas

Impurity of a node

Gini = 1 − Σₖ pₖ² Entropy = −Σₖ pₖ log₂ pₖ

pₖ: fraction of the node’s samples in class k

Scoring a split

Gain = I(parent) − (n_L / n)·I(left) − (n_R / n)·I(right)

n, n_L, n_R: samples in the parent, left child and right child
I(·): the chosen impurity (Gini or entropy)

Information gain

With entropy as the impurity, the gain is called information gain: the number of bits of uncertainty about the class that the question removes. Gini and entropy usually choose the same or very similar splits.

Overfitting

Grown without limits, a tree keeps splitting until every leaf is pure, carving tiny boxes around single noisy points. Training accuracy reaches 100% while test accuracy falls. Limit depth, require more samples per split, prune, or average many trees (random forests).

How to use this visualizer

1
Pick a dataset. The tree starts as a single root node covering the whole plane.
2
Read the split scan: each curve shows the weighted child impurity for every threshold on x or y. The lowest point is the split CART will make.
3
Press Next split to apply it. A line divides the dashed region and two children appear in the tree diagram.
4
Keep stepping, or press Grow full tree. Undo split walks back one step at a time.
5
Raise max depth and lower min samples, then turn on Show test points: watch small boxes form around noise.
6
Use the accuracy vs depth chart to find the depth where test accuracy stops improving.
7
Load XOR: the first split barely helps because no single line separates the classes, which shows how greedy growth works.

Finding the best split in code

Python

import numpy as np

def gini(y):
    if len(y) == 0:
        return 0.0
    p = np.bincount(y) / len(y)
    return 1 - (p ** 2).sum()

def best_split(X, y):
    best = (None, None, gini(y))              # feature, threshold, weighted impurity
    for f in range(X.shape[1]):
        values = np.unique(X[:, f])
        for t in (values[:-1] + values[1:]) / 2:  # midpoints
            left = X[:, f] <= t
            w = (left.sum() * gini(y[left]) + (~left).sum() * gini(y[~left])) / len(y)
            if w < best[2]:
                best = (f, t, w)
    return best

Complexity

Time complexity

O(d · n log n · depth)

Training: at each level of the tree, every feature is sorted and swept once over the samples it holds. Predicting one point takes O(depth).

Space complexity

O(nodes + n)

The tree itself plus index lists for the samples at each node.

Practice problems

Problem 1: Score a split with Gini

A node holds 10 samples: 6 blue and 4 orange. A split sends 5 blue and 1 orange left, and 1 blue and 3 orange right. Compute the Gini impurity of the node, of each child, and the gain.

Show solution

Parent: 1 − (0.6² + 0.4²) = 1 − 0.52 = 0.48

Left (5, 1): 1 − ((5/6)² + (1/6)²) = 1 − 26/36 ≈ 0.278

Right (1, 3): 1 − ((1/4)² + (3/4)²) = 1 − 10/16 = 0.375

Weighted: 0.6 × 0.278 + 0.4 × 0.375 = 0.167 + 0.150 = 0.317

Gain = 0.48 − 0.317 ≈ 0.163

Problem 2: Choose the threshold

One feature, sorted: values 1, 2, 3, 4, 5, 6 with labels A, A, B, A, B, B. Which threshold does CART choose using entropy?

Show solution

Candidates are the midpoints 1.5, 2.5, 3.5, 4.5, 5.5. Parent entropy = 1 (3 A, 3 B).

2.5: left (A, A) H = 0; right (B, A, B, B) H = 0.811 → weighted 4/6 × 0.811 = 0.541

4.5: left (A, A, B, A) H = 0.811; right (B, B) H = 0 → weighted 0.541

3.5: left (A, A, B) H = 0.918; right (A, B, B) H = 0.918 → weighted 0.918

1.5 and 5.5: one pure child of 1, the other (2, 3) mix: 5/6 × 0.971 = 0.809

2.5 and 4.5 tie with information gain 1 − 0.541 = 0.459; CART keeps the first one found, x ≤ 2.5.

Discussion

Questions, ideas or a different approach? Join the conversation.