Information Gain

In decision trees, we can prioritize nodes with higher information gain. Let the total number of samples is $n$ and samples in class 1 is $n_1$.

We can then define the entropy $I$ as the entropy before we split.

$$I(n,n_1)=-\left(\left(\frac{n_1}{n}\right){\log }_2\left(\frac{n_1}{n}\right)+\left(1-\frac{n_1}{n}\right){\log }_2\left(1-\frac{n_1}{n}\right)\right)$$

Next, $E(X)$ is the entropy after we split, given feature $X$ which has $k$ classes, and $m_i$ being the number of child nodes while $m_{i1}$ is the number of samples in class 1 of child $m_i$.

$$E(X)=-\left(\frac{m_1}{n}\right)I(m_1,m_{11})+\left(\frac{m_2}{n}\right)I(m_2,m_{21})+\cdots +\left(\frac{m_k}{n}\right)I(m_k{m}_{k_1})$$

So, we have Information Gain, which is the decrease of impurity if we split.

$$\text{Gain}(X)=I(n,n_1)-E(X)$$