通俗理解决策树算法中的信息增益
在决策树算法的学习过程中，信息增益是特征选择的一个重要指标。它定义为一个特征能够为分类系统带来多少信息，带来的信息越多，说明该特征越重要，相应的信息增益也就越大。
1. 概念
我们前面说了，信息熵是代表随机变量的复杂度（不确定度），条件熵代表在某一个条件下，随机变量的复杂度（不确定度）。
而我们的信息增益恰好是：信息熵 - 条件熵。
换句话说，信息增益代表了在一个条件下，信息复杂度（不确定性）减少的程度。
那么我们现在也很好理解了，在决策树算法中，我们的关键就是每次选择一个特征，特征有多个，那么到底按照什么标准来选择哪一个特征。
这个问题就可以用信息增益来度量。如果选择一个特征后，信息增益最大（信息不确定性减少的程度最大），那么我们就选取这个特征。
2. 例子
我们有如下数据：
| 样本 ID | 身高 | 结果 |
|---|---|---|
| 1-6, 8-9, 11-12 | 矮/中/高 | 嫁/不嫁 |
可以求得随机变量 X（结果）的信息熵为：
嫁的个数为 6 个，占 1/2，那么信息熵为： $$H(X) = -\frac{1}{2}\log_{10}\frac{1}{2} - \frac{1}{2}\log_{10}\frac{1}{2} = -\log_{10}\frac{1}{2} \approx 0.301$$
现在假如我知道了一个人的身高信息。
身高有三个可能的取值 {矮，中，高}：
- 矮包括 {1,2,3,5,6,11,12}，共 7 个，其中嫁 1 个，不嫁 6 个
- 中包括 {8,9}，共 2 个，其中嫁 2 个，不嫁 0 个
- 高包括 {4,7,10}，共 3 个，其中嫁 3 个，不嫁 0 个
先回忆一下条件熵的公式如下：
$$H(Y|X) = \sum P(x_i) H(Y|x_i)$$
我们先求出公式对应的值：
$$H(Y|X=\text{矮}) = -\frac{1}{7}\log_{10}\frac{1}{7} - \frac{6}{7}\log_{10}\frac{6}{7} \approx 0.178$$
$$H(Y|X=\text{中}) = -1\log_{10}1 - 0 = 0$$
$$H(Y|X=\text{高}) = -1\log_{10}1 - 0 = 0$$
概率分布：
$$P(X=\text{矮}) = 7/12, P(X=\text{中}) = 2/12, P(X=\text{高}) = 3/12$$
则可以得出条件熵为：
$$\frac{7}{12} \times 0.178 + \frac{2}{12} \times 0 + \frac{3}{12} \times 0 \approx 0.103$$
那么我们知道信息熵与条件熵相减就是我们的信息增益，为：
$$0.301 - 0.103 = 0.198$$
所以我们可以得出我们在知道了身高这个信息之后，信息增益是 0.198。
3. 结论
我们可以知道，本来如果我对一个人什么都不知道的话，作为他的伴侣决定是否在一起的不确定性有 0.301 这么大。
当我们知道对方的身高信息后，不确定度减少了 0.198，不确定度只有 0.103 这么大了。也就是说，身高这个特征对于我们来说，决定关系走向是很重要的。
至少我们知道了身高特征后，原来没有底的心里已经明朗一半多了，减少 0.198 了（大于原来的一半了）。
这就类似于相亲节目里面的桥段了，请问嘉宾，你只能知道一个人的一个特征。请问你想知道哪个特征。
假如其它特征我也全算了，信息增益是身高这个特征最大。那么我可以说，我想知道男嘉宾的一个特征是身高特征。因为它在这些特征中，对于我挑选伴侣是最重要的，信息增益是最大的，知道了这个特征，不确定度减少的是最多的。
希望能对理解信息增益有所帮助。
