Entropy And Information Gain In Classification Trees

Why Entropy Is Used to Assess Classification Splits

A classification tree divides observations into groups and assigns a class prediction to each terminal node. A useful split tends to create child nodes whose class labels are more concentrated than those in the parent node. Entropy measures that concentration: a node with one class only has zero entropy, while a node with several similarly common classes has greater entropy.

Information gain measures how much the split reduces entropy, accounting for the sizes of the child nodes. A split that makes one small child perfectly pure but leaves most observations nearly unchanged may be less useful than a split that improves the class mix across larger groups. The key is to compare the parent entropy with the weighted average of the child entropies.

Definition: Suppose a node contains $n$ observations from $K$ classes, with $n_k$ observations in class $k$ and empirical proportion $p_k=n_k/n$. Its class entropy, measured in bits, is $$ H=-\sum_{k=1}^{K} p_k\log_2(p_k). $$ A term with $p_k=0$ is defined to be zero, since $\lim_{p\to 0^+}p\log_2(p)=0$.

For two classes, with proportions $p$ and $1-p$, this becomes $H=-p\log_2(p)-(1-p)\log_2(1-p)$. Entropy is zero when one class has proportion 1. It is largest when the classes are equally frequent; for two classes, that maximum is 1 bit at $p=0.5$. For $K$ equally frequent classes, the entropy is $\log_2(K)$.

These calculations describe the observed class mix in a node. They do not require a probability model for the observations: the proportions are empirical counts. In the formulas below, each observation has equal weight, and a candidate split assigns every parent observation to exactly one nonempty child. If a split has children $j=1,\ldots,J$, let $n_j$ be the number of observations in child $j$, so that $\sum_j n_j=n$.

Definition: The information gain of a candidate split is the parent entropy minus the child entropies weighted by their proportions of the parent sample: $$ \operatorname{Gain}=H_{\text{parent}}-\sum_{j=1}^{J}\frac{n_j}{n}H_j. $$ A larger information gain means a greater reduction in the weighted class uncertainty for that split.

Calculating Information Gain

Use the class counts at the parent and at every child. First calculate the parent entropy. Then calculate each child entropy from its own class proportions, weight it by the child’s share of the parent observations, and subtract the weighted sum from the parent entropy. Use base-2 logarithms throughout; changing the log base rescales entropy and gain, and can make numerical comparisons misleading if the base is not kept consistent.

Worked Example: Comparing Two Splits of the Same Parent

A hypothetical claims-screening node contains 12 cases: 8 cases in class “review” and 4 in class “no review.” Two candidate splits are proposed. Split A creates children with counts (5 review, 1 no review) and (3 review, 3 no review). Split B creates children with counts (4 review, 0 no review) and (4 review, 4 no review). Calculate both gains and identify the preferred split by information gain.

Method. Calculate the parent entropy, then subtract each split’s weighted child entropy. This comparison avoids judging a split by its purest child alone.

The parent proportions are $8/12=2/3$ and $4/12=1/3$. Therefore,

H_{\text{parent}}=-\frac{2}{3}\log_2\left(\frac{2}{3}\right)-\frac{1}{3}\log_2\left(\frac{1}{3}\right)=0.9183.

For Split A, the first child has proportions $5/6$ and $1/6$, giving entropy $0.6500$. The second child has proportions $3/6$ and $3/6$, giving entropy $1.0000$. Both children contain 6 of the 12 observations, so the weighted child entropy is

\frac{6}{12}(0.6500)+\frac{6}{12}(1.0000)=0.8250.

Thus, $\operatorname{Gain}_A=0.9183-0.8250=0.0933$.

For Split B, the first child is pure, with proportions 1 and 0, so its entropy is 0. The second child has proportions $4/8$ and $4/8$, so its entropy is 1.0000. The weighted child entropy is

\frac{4}{12}(0)+\frac{8}{12}(1.0000)=0.6667.

Thus, $\operatorname{Gain}_B=0.9183-0.6667=0.2516$. Split B is preferred by information gain. Its pure child is not the reason by itself: the other child and its size are also included in the calculation. The class counts in each proposed split sum to the parent counts, and the gains are nonnegative, as expected for these partitions.

Why the Weighted Formula Works

The weighting follows directly from how the split partitions the observations. If an observation is selected uniformly from the parent, the probability that it falls in child $j$ is $n_j/n$. The child entropy describes the class uncertainty for an observation known to be in that child; averaging these uncertainties over the possible children therefore uses weights $n_j/n$, not equal weights unless the children have equal sizes.

The same result can be expressed using the chain rule for entropy. Let $Y$ denote the class label and $C$ the child reached by the split. Because the split assigns each observation to one child, the child identity is determined by the predictor values. The joint entropy of class and child identity can be written in either order:

H(Y,C)=H(C)+H(Y\mid C)=H(Y)+H(C\mid Y).

Rearranging gives $H(Y)-H(Y\mid C)=H(C)-H(C\mid Y)$. The conditional class entropy is the weighted child entropy:

H(Y\mid C)=\sum_{j=1}^{J}P(C=j)H(Y\mid C=j) =\sum_{j=1}^{J}\frac{n_j}{n}H_j.

Consequently, information gain is $H(Y)-H(Y\mid C)$. Equivalently, it is the mutual information between the class label and the child identity: how much knowing the child reduces uncertainty about the class. This justifies both the subtraction and the child-size weights. The result applies to a partition of the parent observations; it does not justify comparing entropies computed on different samples as if they came from one split.

Entropy and Gini Can Prefer Different Splits

For classification trees, Gini impurity for class proportions $p_1,\ldots,p_K$ is $1-\sum_k p_k^2$. As with entropy, a split can be assessed by subtracting the child impurities weighted by child size from the parent impurity. Both measures are zero for a pure node and larger for a less concentrated class mix. However, they are different functions of the class proportions, so candidate splits need not be ranked identically.

Entropy uses logarithms and is relatively responsive to changes that distinguish very rare or very common classes; Gini uses squared proportions. Neither measure is universally “the” correct choice independent of the tree-building procedure. When comparing candidates, use the criterion specified for the tree and keep it consistent. A change in split ranking does not mean either calculation is wrong.

Worked Example: A Ranking Reversal Between Entropy and Gini

A hypothetical balanced parent node contains 100 observations: 50 in class A and 50 in class B. Candidate split A isolates 5 class-A observations into a child of size 5; the remaining child has 45 class-A and 50 class-B observations. Candidate split B creates two children of size 50, with class counts (31, 19) and (19, 31). Compare the information gains and Gini reductions. Report gains to four decimal places.

Method. Calculate the weighted reduction under each criterion from the same parent and child counts. This example avoids assuming that a ranking under one impurity measure must also hold under the other.

The parent is balanced, so its entropy is $1.0000$ and its Gini impurity is $1-(0.5^2+0.5^2)=0.5000$.

For candidate A, the size-5 child is pure, with entropy and Gini impurity both 0. The other child has proportions $45/95=9/19$ and $50/95=10/19$. Its entropy is

-\frac{9}{19}\log_2\left(\frac{9}{19}\right)-\frac{10}{19}\log_2\left(\frac{10}{19}\right)=0.9980.

The weighted child entropy is $(5/100)(0)+(95/100)(0.9980)=0.9481$, so the information gain is $1.0000-0.9481=0.0519$. For Gini, the other child has impurity

1-\left(\frac{9}{19}\right)^2-\left(\frac{10}{19}\right)^2=\frac{180}{361}=0.4986.

Its weighted child impurity is $(5/100)(0)+(95/100)(180/361)=0.4737$. The Gini reduction is $0.5000-0.4737=0.0263$.

For candidate B, each child has proportions $0.62$ and $0.38$, in opposite order. Each child entropy is

-0.62\log_2(0.62)-0.38\log_2(0.38)=0.9580.

The weighted child entropy is also $0.9580$, giving information gain $1.0000-0.9580=0.0420$. Each child’s Gini impurity is $1-0.62^2-0.38^2=0.4712$. The weighted child impurity is $0.4712$, giving a Gini reduction of $0.5000-0.4712=0.0288$.

Conclusion. Entropy prefers candidate A, since $0.0519>0.0420$; Gini prefers candidate B, since $0.0288>0.0263$. Both splits preserve the parent’s total class counts. The difference arises because entropy and Gini measure impurity differently, not because of a calculation inconsistency.

Multiclass Entropy and Zero Counts

Entropy extends directly to more than two classes: include one term for each class proportion. A class absent from a node contributes zero under the convention $0\log_2(0)=0$; it does not make the entropy undefined. In practice, calculating from class counts first helps avoid accidentally treating an absent class as a positive proportion.

Worked Example: A Three-Class Split

A hypothetical triage node contains 12 cases across three outcomes: 6 routine, 3 urgent, and 3 emergency. A proposed split produces one child with counts (4, 1, 1) and another with counts (2, 2, 2), in that class order. Calculate the information gain to four decimal places.

Method. Calculate the three-class entropy at the parent and both children, then weight each child entropy by its share of the 12 cases. This method avoids using a binary entropy formula for a three-class problem.

At the parent, the class proportions are $1/2,1/4,1/4$, so

H_{\text{parent}}=-\frac12\log_2\left(\frac12\right)-2\left[\frac14\log_2\left(\frac14\right)\right]=0.5+0.5+0.5=1.5000.

The first child has proportions $2/3,1/6,1/6$. Its entropy is

-\frac23\log_2\left(\frac23\right)-2\left[\frac16\log_2\left(\frac16\right)\right]=1.2516.

The second child has three equal proportions, so its entropy is $\log_2(3)=1.5850$. Both children contain 6 cases, making the weighted child entropy

\frac{6}{12}(1.2516)+\frac{6}{12}(1.5850)=1.4183.

The information gain is $1.5000-1.4183=0.0817$. The child counts add to the parent counts: (4, 1, 1) plus (2, 2, 2) equals (6, 3, 3). The positive gain is consistent with the split reducing weighted class uncertainty.

Common Mistakes and Practical Interpretation

Taking an unweighted average of child entropies. Unless all children have equal size, use $n_j/n$ as each child’s weight. A small child should not count as much as a much larger one.
Comparing only the purest child. A pure child can coexist with a large, highly mixed child. Include every child in the weighted sum.
Using the wrong logarithm base. Base 2 gives entropy in bits. Other bases rescale the values; do not mix bases within a comparison.
Treating a zero proportion as an error. Its entropy contribution is zero by convention. Do not attempt to take the logarithm of zero separately.
Assuming entropy and Gini rankings must match. They are different impurity criteria and can select different candidates, as the ranking-reversal example shows.

For a fixed parent, choosing the split with the largest information gain is equivalent to choosing the split with the smallest weighted child entropy, because the parent entropy is the same constant for every candidate. This conclusion applies to the entropy criterion; a tree using Gini evaluates candidates with Gini reductions instead. Entropy-based splitting is therefore one way to quantify progress toward more class-concentrated nodes, not a guarantee that every resulting prediction will be correct or that a larger training-sample gain will improve performance on new data.

Check Your Understanding

For each problem, calculate with base-2 logarithms. Answers are rounded to four decimal places.

A node contains 7 observations in class A and 3 in class B. Find its entropy. (Answer: $0.8813$ bits.)
A parent contains 8 positive and 4 negative cases. A split produces children (5 positive, 1 negative) and (3 positive, 3 negative). Find the information gain. (Answer: $0.0933$ bits.)
A balanced parent has 10 cases in each of two classes. A split creates two equal-size children with class counts (7, 3) and (3, 7). Find the entropy gain and Gini reduction, and state whether their rankings agree with each other for this split’s reduction. (Answer: Entropy gain $=0.1187$ bits; Gini reduction $=0.0800$; they are numerical reductions on different scales, so their magnitudes should not be compared as rankings.)
A parent has class counts (9, 3) across two classes. Its children have counts (4, 0) and (5, 3). Find the information gain. (Answer: $0.1750$ bits.)
A balanced parent has 100 cases in each of two classes. Candidate A isolates 4 cases from one class into a pure child; the other child has counts (96, 100). Candidate B creates two children of size 100 with counts (58, 42) and (42, 58). Which candidate has greater entropy gain, and which has greater Gini reduction? (Answer: Entropy gain: A $=0.0203$, B $=0.0185$, so entropy prefers A; Gini reduction: A $=0.0102$, B $=0.0128$, so Gini prefers B.)

What You'll Learn