In decision tree classifier most of the algorithms use Information gain as spiting criterion. We select the feature with maximum information gain to split on.
I think that using accuracy instead of information gain is simpler approach. Is there any scenario where accuracy doesn't work and information gain does?
Can anyone explain what are the advantages of using Information gain over accuracy as splitting criterion?
Decision trees are generally prone to over-fitting and accuracy doesn't generalize well to unseen data. One advantage of information gain is that -- due to the factor $-p*log(p)$ in the entropy definition -- leafs with a small number of instances are assigned less weight ($lim_{p \rightarrow 0^{+} } p*log(p) = 0$) and it favors dividing data into bigger but homogeneous groups. This approach is usually more stable and also chooses the most impactful features close to the root of the tree.
EDIT: Accuracy is usually problematic with unbalanced data. Consider this toy example:
Weather Wind Outcome
Sunny Weak YES
Sunny Weak YES
Rainy Weak YES
Cloudy Medium YES
Rainy Medium NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Rainy Strong NO
Weather and Wind both produce only one incorrect label hence have the same accuracy of 16/17. However, given this data, we would assume that weak winds (75% YES) are more predictive for a positive outcome than sunny weather (50% YES). That is, wind teaches us more about both outcomes. Since there are only few data points for positive outcomes we favor wind over weather, because wind is more predictive on the smaller label set which we would hope to give us a rule that is more robust to new data.
The entropy of the outcome is $ -4/17*log_2(4/17)-14/17*log_2(14/17)) =0.72$. The entropy for weather and outcome is $14/17*(-1/14*log_2(1/14)-13/14*log_2(13/14)) = 0.31$ which leads to an information gain of $0.41$. Similarly, wind gives a higher information gain of $0.6$.
I believe this issue is addressed in the Elements of Statistical Learning (https://hastie.su.domains/ElemStatLearn/printings/ESLII_print12_toc.pdf.download.html) around pg. 360 (maybe slightly different depending on the edition you have):
"We classify the observations in node $m$ to class $k(m) = \arg\max_k > \hat{p}_{mk}$, the majority class in node $m$. Different measures $Q_m(T)$ of node impurity include the following:
Misclassification error: $1 - \hat{p}_{mk(m)} = \frac{1}{N_m} \sum_{i \in R_m} \mathbb{I}(y_i > \neq k(m)).$
Gini index: $ \sum_{k \neq k'} \hat{p}_{mk} \hat{p}_{mk'} = \sum_{k=1}^K \hat{p}_{mk} (1 - \hat{p}_{mk}). $
Cross-entropy or deviance: $ -\sum_{k=1}^K \hat{p}_{mk} \log \hat{p}_{mk}. $
For two classes, if $p$ is the proportion in the second class, these three measures are $1 - \max(p, 1 - p)$, $2p(1-p)$, and $-p\log p - > (1-p)\log(1-p)$, respectively. They are shown in Figure 9.3. All three are similar, but cross-entropy and the Gini index are differentiable, and hence more amenable to numerical optimization.
Comparing equations (9.13) and (9.15), we see that we need to weight the node impurity measures by the number $N_{mL}$ and $N_{mR}$ of observations in the two child nodes created by splitting node $m$.
In addition, cross-entropy and the Gini index are more sensitive to changes in the node probabilities than the misclassification rate. For example, in a two-class problem with 400 observations in each class (denoted by $(400, 400)$), suppose one split creates nodes $(300, > 100)$ and $(100, 300)$, while another split creates nodes $(200, 400)$ and $(200, 0)$. Both splits produce a misclassification rate of 0.25, but the second split produces a pure node and is probably preferable. Both the Gini index and cross-entropy are lower for the second split. For this reason, either the Gini index or cross-entropy should be used when growing the tree. To guide cost-complexity pruning, any of the three measures can be used, but typically it is the misclassification rate.
The Gini index can be interpreted in two interesting ways. Rather than classify observations to the majority class in the node, we could classify them to class $k$ with probability $\hat{p}_{mk}$. Then the training error rate of this rule in the node is $\sum_{k \neq k'} > \hat{p}_{mk} \hat{p}_{mk'}$—the Gini index. Similarly, if we code each observation as 1 for class $k$ and 0 otherwise, the variance over the node of this 0-1 response is $\hat{p}_{mk}(1 - \hat{p}_{mk})$. Summing over classes $k$ again gives the Gini index."
