ML5.2 · LESSON 2 OF 6

Impurity

Choose a split by impurity reduction and distinguish bagging, random forests and boosting.

THE IDEA

How mixed is a node?

When you cut, you want the two sides to be cleaner than the whole. To compare cuts you need a number for how mixed a node is. Two classics:

Gini impurity: pick two examples at random (with replacement) from the node; this is the chance they have different classes. With class fractions p_k it is 1 − Σ p_k².
Entropy: −Σ p_k log₂ p_k, measured in bits. It is the average number of yes/no questions needed to find the class of a random example if you ask smartly.

Both are 0 for a pure node, both are largest for an even mix, and they only look at the class fractions: not at what the classes mean or how important they are. Edit the counts below and compare.

Class A count Class B count

AAAB

4 examplesclass A fraction 0.75

Gini 1 - (3/4)² - (1/4)² = 1 - 0.5625 - 0.0625 = 0.375 Entropy -(0.75 × log2(0.75) + 0.25 × log2(0.25)) = 0.8113 bits

Both curves are 0 at the ends (a pure node), peak at a 50/50 mix, and are symmetric: swapping the names of the classes changes nothing. Gini peaks at 0.5, entropy at 1 bit.

Change the counts of two classes. The dots on the curves mark the node you built.

Worked numbers

A node with 3 red and 1 blue example has fractions 0.75 and 0.25. Gini = 1 − 0.75² − 0.25² = 0.375. Entropy = −(0.75 log₂ 0.75 + 0.25 log₂ 0.25) = 0.8113 bits. A 50/50 node scores Gini 0.5 and entropy exactly 1 bit. For a two-class node the largest Gini is 0.5, but with K equally likely classes Gini can reach 1 − 1/K and entropy log₂ K.

Predict first. Node A holds 9 examples of one class and 1 of another. Node B holds 5 and 5. Which is purer, and roughly by how much in Gini?

The common mistake

Impurity measures class mixture, and nothing else. A leaf with Gini 0 on the training data is not necessarily reliable (it might contain two examples), and a high-impurity node is not necessarily an unimportant one. Also, an empty node has no fractions at all: dividing by a count of zero gives a nan, so code must return 0 for it explicitly. Likewise, in entropy a class with count 0 must be skipped, because log₂ 0 is undefined.

The two traps in numpy

>>> import numpy as np
>>> p = np.array([0.0, 1.0])
>>> -np.sum(p * np.log2(p))     # 0 * log2(0) is nan
nan                              # (plus a RuntimeWarning)
>>> p = p[p > 0]                 # keep only the classes present
>>> -np.sum(p * np.log2(p))
-0.0

Chapter context

A decision tree recursively asks questions that partition data. An ensemble combines many models to improve behavior, but the way those models are trained determines what kind of errors the combination can reduce.

TRY IT YOURSELF

Part 1. Do it by hand

Set the class counts to meet each target. Each task ticks from the live counts and stays ticked.

Class A count Class B count

AAAB

4 examplesclass A fraction 0.75

Gini 1 - (3/4)² - (1/4)² = 1 - 0.5625 - 0.0625 = 0.375 Entropy -(0.75 × log2(0.75) + 0.25 × log2(0.25)) = 0.8113 bits

Both curves are 0 at the ends (a pure node), peak at a 50/50 mix, and are symmetric: swapping the names of the classes changes nothing. Gini peaks at 0.5, entropy at 1 bit.

To do: Make a pure node of at least 10 examples (impurity exactly 0)
To do: Build a node of exactly 20 examples whose Gini is 0.32
To do: Find a node of at least 20 examples with entropy between 0.9 and 0.99 bits
To do: Make the most impure two-class node there is: Gini 0.5 and entropy 1 bit

Part 2. Do it in code

Write gini(y) = 1 minus the sum of squared class proportions. Write entropy(y) = minus the sum of p * log2(p) over the classes present.
y is any array of class labels (ints, possibly negative or not contiguous, or strings).
An empty node has impurity 0.0. A pure node has impurity 0.0. Never return nan: a class with zero count must not be fed to log2.

import numpy as np

def proportions(y):
    # helper: the proportion of each class present in y (empty list for empty y)
    pass

def gini(y):
    pass

def entropy(y):
    pass

print(gini([0, 0, 1, 1]), entropy([0, 0, 1, 1]))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Find binary Gini for equal class proportions.

A1.0, because an evenly mixed node is the most impure and Gini ranges up to 1.B0.5, because 1 - (0.5 squared + 0.5 squared) = 1 - 0.5.C0.25, because each class contributes 0.5 squared and the two terms are averaged.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

G(p)=1-\sum_kp_k^2,\quad \Delta G=G_{parent}-\frac{n_L}{n}G_L-\frac{n_R}{n}G_R.

A boosted additive model has the form $F_{t+1}(x)=F_t(x)+\eta h_t(x)$ . The stage target depends on the loss and boosting method.

Worked example

A parent contains three red examples and one blue example. Its Gini is 1−0.75²−0.25²=0.375. Split into a left child with two red examples and a right child with one red and one blue. Weighted child Gini is 2/4×0 + 2/4×0.5 = 0.25, giving gain 0.125.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
gini = lambda counts: 1-sum((n/sum(counts))**2 for n in counts)
parent = gini([3,1])
children = .5*gini([2,0]) + .5*gini([1,1])
assert isclose(parent, .375)
assert isclose(children, .25)
assert isclose(parent-children, .125)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Feature importance is not causal influence. A pure training leaf need not generalize. Bagging and boosting are different training strategies, not interchangeable names for averaging.