AI, machine learning and deep learning · Intermediate

Decision tree splits and entropy

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

Decision trees split data by asking questions that make the resulting groups as pure as possible. Entropy measures the impurity of a group, and information gain tells us how much a split reduces it. The tree greedily picks the split with the highest gain at each node.

Intuition

Imagine playing twenty questions. A good question cuts your uncertainty sharply, while a poor one leaves you almost as confused as before. Entropy quantifies that uncertainty: a group that is half sick and half healthy is maximally uncertain, while a group that is all healthy has zero uncertainty. A split is good if the child groups, weighted by size, are much less uncertain than the parent. The algorithm tries candidate questions, computes the weighted entropy of the children, and keeps the one with the biggest drop.

Key equations

H(S)=−∑kpklog2⁡pk
(1)

Entropy of set S, where p_k is the fraction of samples in class k (0 log 0 is taken as 0).

Hsplit=∑j|Sj||S|H(Sj)
(2)

Weighted average entropy of the child nodes S_j after a split.

IG=H(S)−Hsplit
(3)

Information gain: the reduction in entropy achieved by the split.

Derivation

  1. Start with a node containing samples from several classes; let p_k be the proportion of class k.
  2. Surprise of seeing class k is -log2 p_k bits; rare outcomes are more surprising.
  3. Average the surprise over the class distribution to get H(S) = -sum p_k log2 p_k.
  4. For two classes, H is 0 when p=0 or 1 and reaches its maximum of 1 bit at p=0.5.
  5. A split sends fractions |S_j|/|S| of the data to children; weight each child's entropy by its fraction.
  6. Information gain is parent entropy minus weighted child entropy; it is never negative.
  7. Greedy rule: evaluate all candidate features and thresholds, choose the largest gain, then recurse on each child until nodes are pure or a stopping rule applies.

Worked example

Problem

A node has 10 patients: 6 diseased, 4 healthy. A test splits them into Left (5 diseased, 1 healthy) and Right (1 diseased, 3 healthy). Compute the information gain.

  1. Parent: p=0.6 and 0.4. H = -(0.6 log2 0.6 + 0.4 log2 0.4) = 0.6(0.737) + 0.4(1.322) = 0.971 bits.
  2. Left (6 samples): p=5/6 and 1/6. H = (5/6)(0.263) + (1/6)(2.585) = 0.219 + 0.431 = 0.650 bits.
  3. Right (4 samples): p=1/4 and 3/4. H = 0.25(2) + 0.75(0.415) = 0.5 + 0.311 = 0.811 bits.
  4. Weighted: (6/10)(0.650) + (4/10)(0.811) = 0.390 + 0.325 = 0.715 bits.
  5. IG = 0.971 - 0.715 = 0.256 bits.

Answer Information gain is about 0.26 bits.

Common mistakes

  • Forgetting to weight child entropies by their sample fractions, which overrates tiny pure children.
  • Using natural log in one place and log base 2 in another, so values are not comparable.
  • Thinking a high-entropy node is one with many samples; entropy depends on class mix, not size.
  • Assuming greedy splitting finds the globally optimal tree.
  • Growing the tree until every leaf is pure, which overfits; information gain also favors features with many distinct values.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

scene.py(92 lines)
from manim import *
from blocks import *
import numpy as np
import sys

# Tiny dataset: (feature value x, label)
DATA = [(1, 0), (2, 0), (3, 0), (4, 1), (5, 1), (6, 1), (7, 1), (8, 0)]


def entropy(labels):
    """Shannon entropy in bits of a list of 0/1 labels."""
    n = len(labels)
    if n == 0:
        return 0.0
    p = sum(labels) / n
    if p in (0.0, 1.0):
        return 0.0
    return float(-(p * np.log2(p) + (1 - p) * np.log2(1 - p)))


def run_splits(data):
    """Try every threshold, record weighted entropy of each split."""
    base = entropy([y for _, y in data])
    trace = []
    xs = [x for x, _ in data]
    for k in range(1, len(data)):
        t = (xs[k - 1] + xs[k]) / 2
        left = [y for x, y in data if x <= t]
        right = [y for x, y in data if x > t]
        w = len(left) / len(data) * entropy(left) + len(right) / len(data) * entropy(right)
        trace.append({"t": t, "k": k, "w": w, "gain": base - w})
    best = max(trace, key=lambda s: s["gain"])
    return base, trace, best


BASE, TRACE, BEST = run_splits(DATA)


def make_val(s, color=WHITE, best=False):
    """Status text for one recorded split."""
    if best:
        txt = "Best: t=%.1f  gain=%.2f" % (s["t"], s["gain"])
    else:
        txt = "t=%.1f  weighted H=%.2f  gain=%.2f" % (s["t"], s["w"], s["gain"])
    return Text(txt, font_size=26, color=color).move_to(DOWN * 1.9)


class Main(Scene):
    def construct(self):
        self.camera.background_color = "#101418"
        TitleCard(self, "Decision tree split", "Choose the threshold with highest gain")

        # Points as bars (value = x), colour = class (green=1, red=0)
        bars = ArrayBars([x for x, _ in DATA], max_width=8.0, max_height=2.2)
        bars.move_to(UP * 0.3)
        for i, (_, y) in enumerate(DATA):
            bars.bars[i].set_fill(C_GOOD if y else C_BAD, opacity=1)
        self.play(FadeIn(bars))
        info = Text("Entropy before split: %.2f bits" % BASE, font_size=26, color=C_ACCENT)
        info.to_edge(UP, buff=1.2)
        self.play(FadeIn(info))

        # Sweep thresholds using the recorded trace
        slot = 8.0 / len(DATA)
        left_x = bars.bars[0].get_left()[0] - (slot - bars.bars[0].width) / 2

        def make_line(k, color=C_ACCENT):
            x = left_x + slot * k
            return DashedLine([x, -1.3, 0], [x, 2.2, 0], color=color)

        line = make_line(TRACE[0]["k"])
        val = make_val(TRACE[0])
        self.play(Create(line), FadeIn(val), run_time=0.5)
        for s in TRACE[1:]:
            self.play(Transform(line, make_line(s["k"])),
                      Transform(val, make_val(s)), run_time=0.5)
        # Jump to best split
        self.play(Transform(line, make_line(BEST["k"], C_GOOD)),
                  Transform(val, make_val(BEST, C_GOOD, True)), run_time=0.7)
        self.wait(0.5)
        StepCaption(self, "Pick the split that lowers entropy the most.")
        self.wait(1)


if __name__ == "__main__" and "--selftest" in sys.argv:
    assert abs(entropy([0, 1]) - 1.0) < 1e-9
    assert entropy([1, 1, 1]) == 0.0
    assert len(TRACE) == len(DATA) - 1
    assert abs(BASE - 1.0) < 1e-9
    assert BEST["t"] == 3.5
    assert all(s["gain"] <= BEST["gain"] + 1e-12 for s in TRACE)
    print("ok")

The Manim scene code that draws this lesson's animation in the Signals AI app (Python, Manim Community).

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.