3
$\begingroup$

The ID3 algorithm uses "Information Gain" measure.

The C4.5 uses "Gain Ratio" measure which is Information Gain divided by SplitInfo, whereas SplitInfo is high for a split where records split evenly between different outcomes and low otherwise.

My question is:

How does this help to solve the problem that Information Gain is biased towards splits with many outcomes? I can't see the reason. SplitInfo doesn't even take into account the number of outcomes, just the distribution of records in the split.

It may very well be that there is a low number of outcomes (say 2), and the records are split evenly between those 2 outcomes. In that case, SplitInfo is high, Gain Ratio is low, and a split with few outcomes is less likely to be chosen by C4.5.

On the other hand, it may be that there is a low number of outcomes, but the distribution is far from even. In that case, SplitInfo is low, Gain Ratio is high, and a split with many outcomes is more likely to be chosen.

What am I missing?

$\endgroup$
3
$\begingroup$

SplitInfo doesn't even take into account the number of outcomes, just the distribution of records in the split.

But it does take the number of outcomes into account. (Even if it is also dependent on distribution, as you noted). Your comparison is between two situations with the same ("low") number of outcomes, so it can't possibly illustrate how SplitInfo changes with a changing number of outcomes.

Consider the following 3 situations, all with even distribution for simplicity of comparison:

  • 10 possible outcomes with even distribution

    SplitInfo = -10*(1/10*log2(1/10)) = 3.32

  • 100 possible outcomes with even distribution

    SplitInfo = -100*(1/100*log2(1/100)) = 6.64

  • 1000 possible outcomes with even distribution

    SplitInfo = -1000*(1/1000*log2(1/1000)) = 9.97

So if you have to choose between 3 possible splitting scenarios, using only Information Gain as in ID3, the latter would be chosen. However, using SplitInfo in the GainRatio, it should be clear that as the number of choices goes up, the SplitInfo will also go up, and the GainRatio will go down.

All of that was explained with an assumption of evenly distributed splits. However, even with non-uniform distribution, the above will still hold true. SplitInfo will get higher as number of possible outcomes gets higher. Yes, if we hold number of possible outcomes constant and vary outcome distribution, then SplitInfo will have some variance... but so will Information Gain.

$\endgroup$
  • $\begingroup$ I consulted various sources but was not able to verify that the number of outcomes is part of SplitInfo. Which reference did you use ? $\endgroup$ – steffen Nov 9 '12 at 10:49
  • $\begingroup$ To be clear, number of outcomes is not explicitly a part of the formula. The formula is a summation though (represented in my examples above as a multiplication since each part of the summation is the same), and my examples show that number of outcomes affects the result. I used the book Data Mining Concepts and Techniques, 3e, by Jiawei Han. See image here: i.imgur.com/I6rfn.png $\endgroup$ – The111 Nov 9 '12 at 19:11

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.