3
$\begingroup$

Suppose you are building random forest model, which split a node on the attribute, that has highest information gain. In the below image, select the attribute which has the highest information gain?

A) Outlook B) Humidity C) Windy D) Temperature

The Solution mentions "Solution: A

Information gain increases with the average purity of subsets. So option A would be the right answer."

What does average purity of subsets mean here ? enter image description here

$\endgroup$
5
  • $\begingroup$ Hint: What's the definition of information gain? How would you compute the information gain of some feature, such as "windy"? $\endgroup$
    – Sycorax
    Aug 18, 2018 at 16:39
  • $\begingroup$ Entropy = -∑ p(x) log (p(x)) would be the formula. $\endgroup$ Aug 18, 2018 at 19:05
  • $\begingroup$ That’s a formula for computing Shannon entropy. How do you apply that formula to this task? $\endgroup$
    – Sycorax
    Aug 18, 2018 at 19:09
  • $\begingroup$ Please add the [self-study] tag & read its wiki. Then tell us what you understand thus far, what you've tried & where you're stuck. We'll provide hints to help you get unstuck. $\endgroup$ Aug 19, 2018 at 15:58
  • $\begingroup$ I know that we need to use the entropy formula counting say yes in false and no in false and then yes in true and no in true. But I do not know how to proceed. Can any one help me how this calculation is exactly done ? $\endgroup$ Aug 22, 2018 at 16:14

2 Answers 2

3
$\begingroup$

Average purity of subsets means the average of purity metrics for each subset after the split. In your example, you split on Outlook and get 3 subsets, then you calculate information gain using the formula which takes into account sizes of subsets:

$$\text{Gain}(S, \text{Outlook}) = H(S) - \sum_{v\in Values(\text{Outlook})} \frac{|S_v|}{|S|} H(S_v) $$ $H(S)$ is entropy of the whole set, $H(S_v)$ is entropy of a subset,$\frac{|S_v|}{|S|}$ is length of a subset divided by length of the whole set . $$H(S)= -9/14 * \log_29/14 - 5/14*\log_2 5/14 = 0.94 $$ $$H(S_{\text{Sunny}}) = -2/5 * \log_22/5 - 3/5*\log_2 3/5 = 0.97$$ $$H(S_{\text{Overcast}}) = 0 $$ $$H(S_{\text{Rainy}}) = -3/5 * \log_23/5 - 2/5*\log_2 2/5 = 0.97 $$ $$\text{Gain}(S, \text{Outlook})= 0.94 - 0.97*5/14 - 0*4/14 - 0.97*5/14 = 0.94 - 0.347 -0.347 = 0.246$$ Average entropy (i.e. impurity): $\frac{0.97+0.97+0}{3}=0.6466$

If you split on Wind: $$H(S_{\text{false}}) = -6/8 * \log_26/8 - 2/8*\log_2 2/8 = 0.81$$ $$H(S_{\text{true}}) = -3/6 * \log_23/6 - 3/6*\log_2 3/6 = 1 $$ $$\text{Gain}(S, \text{Wind})= 0.94 - 0.81*8/14 - 1*6/14 = 0.049$$ Average entropy: $\frac{0.81+1}{2}=0.905$

And so on.

$\endgroup$
4
  • $\begingroup$ Thanks for the explanation but is there any way to intutively look and figure this out ? without calculations ? $\endgroup$ Aug 26, 2018 at 17:36
  • $\begingroup$ @Sheldon Could you elaborate what you don't understand here? Information Gain? Subset purity? $\endgroup$ Aug 26, 2018 at 20:07
  • $\begingroup$ Or do you mean look at the 4 splits and figure out which one has higher information gain? If yes, the best attribute to split on will have the purest subsets, which means they will consist only of "yes" or "no" labels, because a subset with only "yes"/"no" labels have entropy of zero. In other words we "gain information" when we lessen uncertainty/entropy, so the split which produces on average more purer (less entropic/uncertain) subsets has higher information gain. $\endgroup$ Aug 26, 2018 at 20:18
  • $\begingroup$ @Sheldon does that answer your question? $\endgroup$ Sep 13, 2018 at 19:35
1
$\begingroup$

A really good reference for this is the book An Introduction to Statistical Learning -- it's fairly readable for beginners, and although the solutions are implemented in R, they do a thorough explanation of the theory behind the various algorithms. It would be helpful to you here, and they give great examples. Chapter 8 focuses on tree-based methods like random forests. My explanation below will largely follow from their discussion.

Entropy in this case is defined as:

$D = -\sum_{k=1}^K \hat{p}_{mk} log(\hat{p}_{mk})$

where $\hat{p}_{mk}$ is the proportion of training observations in the mth region that are from the kth class. What this means is that entropy ($D$) will take on a value near zero when all of the $\hat{p}_{mk}$s are near zero or near one -- meaning that all of the observations in that node in the tree are from the same class. Entropy is one of the metrics commonly used, along with the Gini index, for evaluating the quality of a particular node split.

Since the goal of the random forest classifier is to try to predict classes accurately, you want to maximally decrease entropy after each split (i.e., maximize information gained with the split). Taking a node with lots of heterogenous examples and splitting it into relatively pure nodes will maximize this.

Once you understand how the proportions here work (i.e., what the ps in your equation from your comment are doing), it becomes easy to calculate the entropy.

$\endgroup$
1
  • $\begingroup$ I understand the theory behind it but how does it work looking at the values ? $\endgroup$ Aug 22, 2018 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.