Deriving Entropy and Information Gain

Why Entropy Measures Node Uncertainty

A classification tree assigns observations to classes. At any node, the class proportions summarize how mixed the observations at that node are. If every observation belongs to one class, the node is pure. If several classes occur in substantial proportions, the class is less certain before we observe which particular case arrives at the node. Entropy quantifies this uncertainty.

For a node containing $n$ observations from $K$ possible classes, let $p_k$ be the proportion in class $k$, for $k=1,\ldots,K$. These are empirical proportions, so $p_k\geq 0$ and $\sum_{k=1}^{K}p_k=1$. Entropy is conventionally measured in bits by using logarithms to base 2.

Definition: The entropy of a node with class proportions $p_1,\ldots,p_K$ is $$ H=-\sum_{k=1}^{K}p_k\log_2(p_k), $$ where a term with $p_k=0$ is defined to equal zero: $0\log_2(0)=0$ by continuous extension. Entropy is zero for a pure node and is largest when all $K$ classes have equal proportions, in which case $H=\log_2(K)$ bits.

For two classes with proportions $p$ and $1-p$, the formula becomes $H=-p\log_2(p)-(1-p)\log_2(1-p)$. For example, a node split equally between two classes has entropy $1$ bit. A pure two-class node has entropy $0$ bits. Entropy is not a measure of the number of observations: duplicating every observation leaves the class proportions, and therefore the entropy, unchanged.

Information-Theoretic Interpretation

Suppose an observation selected at random from a node belongs to class $k$ with probability $p_k$. The information, or surprise, associated with observing that class is $-\log_2(p_k)$ bits. A rare class has a larger surprise value than a common class. Averaging that surprise over the class distribution gives

\sum_{k=1}^{K}p_k[-\log_2(p_k)] =-\sum_{k=1}^{K}p_k\log_2(p_k) =H.

Thus, entropy is the expected information in the class label before the label is known. It can also be interpreted as uncertainty about the class. A pure node has no uncertainty about the class, so its entropy is zero. A balanced distribution across more classes has greater uncertainty. The unit “bits” follows from the base-2 logarithm; changing the logarithm base changes the numerical unit, not the underlying ranking of class mixtures.

From Node Entropy to Information Gain

A proposed split divides the observations in a parent node into child nodes. A useful split tends to make the child nodes more class-homogeneous than the parent. To assess the uncertainty remaining after the split, calculate each child’s entropy and average those entropies using the fraction of parent observations sent to each child.

Let child $j$ contain $n_j$ observations, have entropy $H_j$, and let the parent contain $n=\sum_{j=1}^{J}n_j$ observations. The probability that a randomly selected parent observation goes to child $j$ is $n_j/n$. The expected entropy after the split is therefore $\sum_{j=1}^{J}(n_j/n)H_j$. Information gain is the parent entropy minus this expected child entropy.

Definition: For a proposed split of a node into $J$ children, the information gain is $$ \operatorname{IG} =H_{\text{parent}}-\sum_{j=1}^{J}\frac{n_j}{n}H_j. $$ The child entropies are calculated from their own class proportions. A positive information gain means that the split reduces the expected entropy; zero means it does not reduce it.

The weighting is part of the definition: it reflects the chance that a randomly selected observation from the parent enters each child. A small, very pure child should not count as much as a much larger child. Information gain is also the mutual information between the class label and the child to which the observation is assigned: it is the expected reduction in uncertainty about the class when the child membership becomes known.

Why the Information-Gain Formula Holds

Let $C$ denote the class label of a randomly selected observation from the parent, and let $Z$ denote the child reached by the proposed split. Before learning $Z$, uncertainty about $C$ is $H(C)=H_{\text{parent}}$. Once $Z=j$ is known, the class distribution is the distribution within child $j$, with entropy $H(C\mid Z=j)=H_j$. Averaging over the possible children gives the conditional entropy:

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

The reduction in uncertainty from learning the child is $H(C)-H(C\mid Z)$, which is exactly the information-gain formula. This also explains why an unweighted average of the child entropies is generally wrong: it treats each child as equally likely, even when their sizes differ.

Calculate the parent distribution.
Divide each class count by the parent total, then calculate $H_{\text{parent}}$.

Calculate each child distribution.
Use the class counts within that child to calculate its entropy $H_j$.

Average child entropy by size.
Multiply each $H_j$ by $n_j/n$ and add the results.

Subtract from parent entropy.
Information gain equals parent entropy minus the size-weighted average child entropy.

Worked Calculations

Worked Example: A Split With One Pure Child

A hypothetical claims-review node contains 8 cases: 6 are classified as “routine” and 2 as “escalated.” A proposed rule sends 4 routine cases to the left child. The right child contains the remaining 2 routine and 2 escalated cases. Calculate the parent entropy, expected child entropy, and information gain in bits. Round only the final results to four decimal places. This calculation avoids treating the number of pure children as the gain itself.

Parent entropy. The class proportions are $6/8=0.75$ and $2/8=0.25$:

H_{\text{parent}} =-0.75\log_2(0.75)-0.25\log_2(0.25) =-(0.75)(-0.4150)-(0.25)(-2) =0.811278\ldots

Left child entropy. The left child has 4 routine cases and no escalated cases, so its proportions are $1$ and $0$. Thus $H_L=-(1)\log_2(1)-0=0$.

Right child entropy. The right child has 2 cases in each class, so its proportions are $0.5$ and $0.5$:

H_R =-0.5\log_2(0.5)-0.5\log_2(0.5) =0.5+0.5 =1.

Each child contains 4 of the 8 cases, so the expected child entropy is $(4/8)(0)+(4/8)(1)=0.5$ bits. The information gain is $0.811278\ldots-0.5=0.311278\ldots$, or 0.3113 bits to four decimal places. The result is positive and smaller than the parent entropy, as expected.

Worked Example: Unequal Class Mixtures in Equal-Sized Children

A hypothetical policy-screening node contains 10 applications: 6 are flagged and 4 are not flagged. A split makes two children of 5 applications each. One child contains 4 flagged and 1 unflagged application; the other contains 2 flagged and 3 unflagged applications. Find the information gain in bits, rounding the final result to four decimal places. The method is to compute both child entropies and average them by their sizes.

Parent entropy. The proportions are $0.6$ and $0.4$:

H_{\text{parent}} =-0.6\log_2(0.6)-0.4\log_2(0.4) =0.9709506\ldots

First child entropy. Its proportions are $4/5=0.8$ and $1/5=0.2$:

H_1 =-0.8\log_2(0.8)-0.2\log_2(0.2) =0.7219281\ldots

Second child entropy. Its proportions are $2/5=0.4$ and $3/5=0.6$:

H_2 =-0.4\log_2(0.4)-0.6\log_2(0.6) =0.9709506\ldots

The children are equally large, so their expected entropy is $(5/10)(0.7219281\ldots)+(5/10)(0.9709506\ldots)=0.8464393\ldots$. Therefore

\operatorname{IG} =0.9709506\ldots-0.8464393\ldots =0.1245112\ldots \approx 0.1245\text{ bits}.

The check is that the expected child entropy is below the parent entropy, so the gain is positive. A common mistake avoided here is rounding each entropy too early; keeping additional digits until subtraction preserves the four-decimal final result.

Worked Example: A Three-Class Split With Unequal Class Counts

A hypothetical fraud-screening node contains 12 cases: 6 “clear,” 4 “review,” and 2 “refer.” A split creates two children of 6 cases each. The first has counts $(5,1,0)$ in that class order; the second has counts $(1,3,2)$. Calculate information gain in bits, rounding only the final answer to four decimal places. The key trap is to calculate entropy from proportions within each child, not from the original node proportions.

Parent entropy. The proportions are $1/2,1/3,1/6$:

H_{\text{parent}} =-\frac12\log_2\left(\frac12\right) -\frac13\log_2\left(\frac13\right) -\frac16\log_2\left(\frac16\right) =1.4591479\ldots

First child entropy. Its proportions are $5/6,1/6,0$. The zero-proportion term contributes zero:

H_1 =-\frac56\log_2\left(\frac56\right) -\frac16\log_2\left(\frac16\right) -0 =0.6500224\ldots

Second child entropy. Its proportions are $1/6,3/6,2/6$, or $1/6,1/2,1/3$. These are the parent proportions in a different order, so the entropy is $H_2=1.4591479\ldots$.

Both children have 6 of the 12 cases. The expected child entropy is $(6/12)(0.6500224\ldots)+(6/12)(1.4591479\ldots)=1.0545852\ldots$. Thus the information gain is $1.4591479\ldots-1.0545852\ldots=0.4045627\ldots$, or 0.4046 bits. The result is positive, and the second child’s entropy equals the parent’s because its class proportions match the parent’s.

Common Mistakes and Interpretation

The most frequent computational error is to average child entropies without using child sizes. Consider a split with a child containing 2 observations and another containing 8. The observations are not equally likely to arrive in the two children: their probabilities are $2/10$ and $8/10$. The expected child entropy must therefore be $(2/10)H_1+(8/10)H_2$, not $(H_1+H_2)/2$.

A second trap is confusing entropy with the fraction correctly classified by the majority-class label. Entropy uses all class proportions and logarithms; it is not simply the minority-class proportion or the misclassification rate. Also, when a class proportion is zero, omit its entropy term rather than attempting to evaluate $\log_2(0)$.

Information gain describes how much a particular split reduces uncertainty about the class in the training observations at that node. It does not, by itself, establish that the split will improve predictions on new observations. A split can fit sample-specific patterns, especially when the tree is allowed to grow extensively. Entropy and information gain are measures for evaluating class separation at a split, not guarantees of generalization performance.

Key takeaway: Compute entropy from class proportions, then subtract the child entropies averaged according to the proportions of observations entering each child. This difference is the expected reduction in class uncertainty, measured in bits.

Check Your Understanding

For each problem, calculate entropy and information gain in bits where requested. Round final numerical answers to four decimal places.

A node has 3 positive and 2 negative cases. A split creates a pure child with 2 positive cases and a child with 1 positive and 2 negative cases. What is the information gain? (Answer: 0.4200 bits)
A node has 4 “accepted” and 4 “declined” cases. A split creates two children, each with 3 accepted and 1 declined case in one child and 1 accepted and 3 declined cases in the other. What is the information gain? (Answer: 0.1887 bits)
A node has 5 “standard,” 3 “investigate,” and 2 “urgent” cases. A split creates children of 5 cases each, with counts $(4,1,0)$ and $(1,2,2)$, respectively. What is the information gain? (Answer: 0.3635 bits)
A binary-class node has 6 “event” and 4 “no event” cases. Candidate split A produces children $(4,1)$ and $(2,3)$; candidate split B produces children $(5,0)$ and $(1,4)$. Which split has greater information gain? (Answer: Split B; its gain is 0.6100 bits, compared with 0.1245 bits for split A.)
Why must child entropies be weighted by child size when calculating expected entropy after a split? (Answer: Because a randomly selected parent observation enters child $j$ with probability $n_j/n$, so the expected entropy is $\sum_j(n_j/n)H_j$, not an equal average over children.)

What You'll Learn