Entropy and Information Gain

Entropy measures disorder in a set of labels; information gain, the drop in entropy from a split, guides decision trees.

Measuring disorder

Entropy quantifies the impurity or unpredictability of a set of labels. A node whose examples are all one class has entropy 0 (perfectly pure, no surprise); a node split evenly between two classes has entropy 1 bit (maximum uncertainty). For classes with probabilities p_i, entropy H = -sum p_i * log2(p_i).

Information gain

Information gain measures how much a split reduces entropy. It is the entropy of the parent node minus the weighted average entropy of the child nodes it produces. A split with high information gain separates the classes cleanly. Decision trees choose, at each node, the feature and threshold that maximize information gain.

import numpy as np
def entropy(y):
    p = np.bincount(y) / len(y)
    p = p[p > 0]
    return -(p * np.log2(p)).sum()

def info_gain(parent, left, right):
    n = len(parent)
    w = (len(left)*entropy(left) + len(right)*entropy(right)) / n
    return entropy(parent) - w

Gini impurity, a close cousin

Decision trees often use Gini impurity, 1 - sum p_i^2, instead of entropy. It measures the chance of misclassifying a random element if labeled by the node's class distribution. Gini and entropy give very similar trees; Gini is slightly cheaper because it avoids the logarithm, which is why it is the common default.

Links to information theory

Entropy comes from information theory, where it is the average number of bits needed to encode outcomes from a distribution. The same quantity appears in the cross-entropy loss and in mutual information, a filter criterion for feature selection. In decision trees, information gain is what makes each split as informative as possible about the target.