1
$\begingroup$

I'm learning about decision trees, and I feel like up till now I've understood them and the math behind them pretty well except for one thing: the gain ratio.

As I understand, the gain ratio is implemented in order to punish for features that may take on A LOT of possible values.

If a feature takes on a lot of possible values, it becomes plausible that if we split on that feature there may be values that only point to a single class, but simply because there are only 1 or 2 data points with that value for that feature anyways.

In other words, the only reason that we would get low entropy for splitting on that feature is because the feature could take on a lot of values, and therefore a lot of those values pointed specifically to a single label. So our decision tree algorithm would end up splitting up on something like "ID #", and wrongly calculate that we just had a HUGE information gain.

However, this only seems like a problem because "ID#" is a feature we shouldn't be splitting on to begin with. I mean, if we had another feature that also took on a lot of possible values, but each of those values actually DID imply some label for that datapoint, then wouldn't applying the gain ratio mean that we are actually messing up our decision tree by punishing what was actually a very good split with tons of information gain?

Isn't it better to just identify which feature will have nothing to do with our labeling BEFORE we feed in the training data to the algorithm?

IDK, I just don't see why the gain ratio would really be useful...

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I had the same doubt when I was doing my Master's Degree. First of all, you don't include something as random as 'IDs'. This is where data preprocessing comes in. Let's take a dataset which has users and their movie genre preferences based on variables like gender, group of age, rating, blah, blah. With the help of information gain, you split at 'Gender' (assuming it has the highest information gain) and now the variables 'Group of Age' and 'Rating' could be equally important and with the help of gain ratio, it will penalise a variable with more distinct values which will help us decide the split at the next level.

Improve this answer
$\endgroup$
2
  • $\begingroup$ OKaaaay, Awesome! So we only use gain ratio when we are in between splitting on two different possible features! Is it in order pick the one that is more probable for the test data to have a previously seen value for, because thats the vibe I was getting from the ID example, the reason its a bad split it had such a high chance of taking on different values (in this case, no other person will have the same ID). $\endgroup$
    – joshuaronis
    Sep 18, 2018 at 14:58
  • $\begingroup$ That makes ALOT more sense. Every explanation I've read uses IDs and it keeps on making me think of why anyone have that in a dataset in the first place?!!!! Thanks Danny! I'd like your post but I don't have enough reputation yet. $\endgroup$
    – joshuaronis
    Sep 18, 2018 at 15:01
0
$\begingroup$

Information gain is one of the heuristics that helps to select the attributes for selection.

As you know decision trees a constructed top-down recursive divide-and-conquer manner. Examples are portioned recursively based on selected attributes.

In ID3 algorithms we use select the attributes with the highest information gain.

Let $p_i$ be the probability that an arbitrary tuple in $D$ belongs to class $C_i$. So $p_i = |C_{i,d}|/|D|$ Expected information (entropy) needed to classify a tuple in $D$ $$Info(D) = -\sum_{i=1}^{m}{p_i*\log(p_i)}$$

Information needed (after using A to split D into v portions) to classify D: $$Info_A(D) = -\sum_{j=1}^{v}{D_j/D * Info_j(D)}$$

Information gained by branching on attribute A

$$Gain(A) = Info(D) - Info_A(D)$$

In C4.5 algorithm we need to divide the information difference by $SplitInfo(A)$

$$Gain(A) = (Info(D) - Info_A(D))/SplitInfo(A)$$

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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