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.
-
$\begingroup$ Why would you say [0,1]? If the numerator is greater than the denominator it would be greater than 1. $\endgroup$– Michael R. ChernickDec 19, 2017 at 16:27
-
$\begingroup$ Exactly - but can the numerator be greater? This is the question. $\endgroup$– vernDec 19, 2017 at 16:29
-
$\begingroup$ This site repeats my assumption as a fact: pythonhosted.org/ibmdbpy/feature_selection.html $\endgroup$– vernDec 19, 2017 at 16:37
1 Answer
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$.