I am wondering what the value range of information gain ratio is. I guess it is [0,1] but am not too sure about it.

  • Why would you say [0,1]? If the numerator is greater than the denominator it would be greater than 1. – Michael Chernick Dec 19 '17 at 16:27
  • Exactly - but can the numerator be greater? This is the question. – vern Dec 19 '17 at 16:29
  • This site repeats my assumption as a fact: pythonhosted.org/ibmdbpy/feature_selection.html – vern Dec 19 '17 at 16:37

tl;dr
Intuitively, the information gain ratio is the ratio between the mutual information of two random variables and the entropy of one of them. Thus, it is guaranteed to be in $[0,1]$ (except for the case in which it is undefined).


In the context of decision trees, let's denote:

  • $Ex$ is the set of training examples
  • $X$ is a randomly chosen example in $Ex$
  • $a$ is some feature
  • $A$ is the value of $a$ of $X$
  • $C$ is the class of $X$
  • $IG(Ex,a)$ is the information gain for splitting according to $a$
  • $IV(Ex,a)$ is the information value (aka intrinsic value) of $a$
  • $IGR(Ex,a)$ is the information gain ratio for splitting according to $a$
  • $H(Y)$ is the entropy of $Y$ (for any random variable $Y$)
  • $I(Y;Z)$ is the mutual information of $Y$ and $Z$ (for any two random variables $Y,Z$)

Then, by definition:

$IG(Ex,a)=H(C)-H(C|A)$

$IV(Ex,a)=H(A)$

$IGR(Ex,a)=\frac{IG(Ex,a)}{IV(Ex,a)}$

Thus:

$IGR(Ex,a)=\frac{H(C)-H(C|A)}{H(A)}$

First, if $H(A)=0$, then $IGR(Ex,a)$ is undefined. An example for such case is when $A$ is constant.

Now, let's assume that $H(A) \ne 0$.

As wikipedia mentions:

$I(C;A)=H(C)-H(C|A)$ and $I(A;C)=H(A)-H(A|C)$.

From the definition of mutual information, we can deduce that it's symmetric.

Thus, $H(C)-H(C|A)=I(C;A)=I(A;C)=H(A)-H(A|C)$

Therefore:

$IGR(Ex,a)=\frac{H(A)-H(A|C)}{H(A)}=1-\frac{H(A|C)}{H(A)}\le 1$
(The $\le 1$ is given by the non-negativity of entropy.)

We can also show that $IGR(Ex,a) \ge 0$, as explained here, and so it holds that $0 \le IGR(Ex,a) \le 1$.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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