Information Gain

$Gain(S,A)$ = expected reduction in entropy due to sorting on $A$

$$Gain(S,A) \equiv Entropy(S)\ - \sum_{v \in Values(A)} \frac{\vert S_{v}\vert}{\vert S\vert} Entropy(S_{v})$$

file=./bookps/dt-s1.ps,width=6in