Entropy and Information Gain

1. Entropy

Entropy is a measure of impurity, disorder or uncertainty of a data set $S$ with respect to its class labels. For a data set that contains $c$ classes with probabilities $p_1, p_2, \dots, p_c$ (estimated as relative frequencies $p_i = |C_i|/|S|$):

$$H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i$$

Units: bits (base 2; base $e$ gives nats).

Properties:

1. $0 \le H(S) \le \log_2 c$.
2. $H(S) = 0$ when the set is pure (all records belong to one class) - no disorder.
3. $H(S)$ is maximum when all classes are equally likely, i.e. $p_i = 1/c$, giving $H = \log_2 c$ (maximum uncertainty).
4. Entropy depends only on the class distribution, not on which attribute is tested.

2. Information gain

Information gain of a test on attribute $A$ with values $v_1 \dots v_n$ is the reduction in entropy (uncertainty about the class) obtained by splitting $S$ on $A$:

$$Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$$

The second term is the weighted (expected) entropy after the split - the average impurity of the children, each child weighted by its share of the records. Hence

$$Gain(S,A) = \text{impurity before the split} - \text{average impurity after the split}$$

Interpretation. The larger the gain, the better the attribute separates the classes. The learning algorithm (ID3) at every node chooses the attribute with the maximum information gain; a gain of 0 means the attribute does not separate the classes at all, while a gain equal to $H(S)$ means the split produces perfectly pure children.

3. Worked numeric example

A set $S$ of 10 records has 6 positives and 4 negatives:

$$H(S) = -\frac{6}{10}\log_2 0.6 - \frac{4}{10}\log_2 0.4 = 0.6(0.7370) + 0.4(1.3219) = \mathbf{0.9710\ bits}$$

Attribute $A$ has two values:

Branch	Records	Class mix	$H$ of branch
$A = a_1$	5	5 Pos, 0 Neg	0
$A = a_2$	5	1 Pos, 4 Neg	0.7219

$$E(S,A) = \frac{5}{10}(0) + \frac{5}{10}(0.7219) = 0.3610$$

$$Gain(S,A) = 0.9710 - 0.3610 = \mathbf{0.6100\ bits}$$

So testing $A$ removes about 61% of the initial uncertainty. (For a second candidate attribute with a smaller gain, the algorithm would pick $A$.)

4. Remarks used in exams

• In the decision-tree problem of Q4(a), $H(S) = 1.4566$ bits, $Gain(\text{Height}) = 1.2729$ and $Gain(\text{Gender}) = 0.3219$, so Height is chosen at the root.
• Gain ratio (C4.5) divides gain by the split information $-\sum \frac{|S_v|}{|S|}\log_2\frac{|S_v|}{|S|}$ to remove the bias towards attributes with many values.
• Gini index (CART), $Gini = 1 - \sum p_i^2$, is an impurity measure equivalent in spirit to entropy.