写在开始
在开始决策树算法之前，我们需要准备一些信息论的知识：
- 信息熵
- 条件熵
- 信息增益
- 交叉熵
- 相对熵
信息熵
套用西瓜书中的话，“信息熵”（infomation entropy）是度量样本集合纯度最常用的一种治标。 其公式定义如下：
就个人理解而言，信息熵所表示的是随机变量的不确定性，当信息熵的值越大时，表示整个系统的随机性越大。
以二分事件为例：
| 分类 | 结果A | 结果B |
|---|---|---|
| 事件一 | 0.5 | 0.5 |
| 事件二 | 0.2 | 0.8 |
那么我们可以计算事件一、二的信息熵如下：
从数值上可以看到，1>0.7219，因此可以做出判定，事件一所对应的系统随机性是要大于事件二的。
引用知乎上看到的回答，一个事件概率越大，所包含的信息量越小，概率越小，所包含的信息量越大，而一个事件所包含的信息量就是这个事件发生的概率的负对数
Ps:在这一部分，看到了很多种的解释，但是总是不能满意，大多都需要根据例子来补充，而很少能用简单易懂的一句话来解释，后续部分再补充吧
补充：
20180407：在知乎上看到了一个解释，其认为信息熵就是消除当前系统的不稳定性所需要付出的代价，因此当信息熵越小时，所需要付出的代价越小，系统越稳定。
20180921: 在《数学之美》一书中看到的解释，较为清楚，故记录下来：“一条信息的信息量和它的不确定性有直接的关系，。比如说，我们要搞清楚一件非常不确定的事，或是我们一无所知的事，就需要了解大量的信息。相反，如果我们对某事件已经有了较多的了解，那么不需要太多的信息就能把它搞清楚。所以，从这个角度来看，可以认为，信息量就等于不确定性的多少。”
条件熵
首先我们给出条件熵的公式：
那么什么是条件熵呢，我们参考条件概率给出的定义，所谓条件概率，就是在已知事件A发生的情况下，事件B发生的概率。而条件熵的定义也是类似的，就是在已知事件X发生的情况下，会对系统Y的信息熵产生的影响。举例说明：
以下说明部分参考知乎
| 序号 | 身高 | 长相 | 年龄 | 结婚 |
|---|---|---|---|---|
| 1 | 高 | 帅 | 大 | 嫁 |
| 2 | 矮 | 帅 | 大 | 不嫁 |
| 3 | 高 | 帅 | 大 | 嫁 |
| 4 | 矮 | 帅 | 大 | 嫁 |
| 5 | 矮 | 帅 | 大 | 不嫁 |
| 6 | 高 | 不帅 | 大 | 嫁 |
| 7 | 矮 | 帅 | 大 | 不嫁 |
| 8 | 高 | 不帅 | 大 | 嫁 |
| 9 | 矮 | 不帅 | 大 | 嫁 |
| 10 | 高 | 不帅 | 大 | 不嫁 |
从上面我们很容易可以计算到整个系统的信息熵：（记事件Y为结婚，事件X为身高，事件Z为长相）
那么所谓条件熵就是指，在我们已经知道某一条件时，会对整个系统产生什么样的影响，现在我们以身高为例：
从表中可以看出，属性为高的为序列 {1,3,6,8,10} ，计数为 5 ，在这些情况中，我们可以看到结果为嫁的序列为 {1,3,5,8} ，计数为 4，因此当X=高时的信息熵为：
同理，属性为敌的序列 {2,4,5,7,9} , 计数为 5 ，其中结果为嫁的序列为 {4,9} ，计数为 2 ，因此当X=矮时的信息熵为：
因此我们可以得到，在已知男生身高情况下，他的女朋友嫁给他的信息熵如下：
同理我们可以计算当已知事件Z时可以得到的结果：
信息增益
按照习惯，我们给出信息增益的公式：
信息增益这一概念，需要结合信息熵与条件熵来讲，总而言之，就是 在知道某一条件的情况下，整个系统的信息熵，究竟减少了多少。
就上面的例子而言，本身系统的信息熵为0.9710，在我们知道了男生的身高的情况下，可以得到系统的条件熵为0.6454，整体的信息增益就为 0.9710-0.6454=0.3256 ，而在知道男生长相的情况下，可以得到系统的条件熵为0.9525，那么信息增益就为 0.9710-0.9525=0.0185 ，可以轻易看出 0.3256>0.0185 ，因此我们可以得到结论，在做出决策时，知道男生的身高这一条件比知道男生的长相相对而言更为重要。
交叉熵
对于事件A，我们有两个分布，一个是事件的真实分布，我们记为p，另一个是非真实分布，也就是我们猜测的分布，记为q，那么交叉熵的公式如下：
在上面我们已经知道，信息熵的公式为：
对比之下可以看出，交叉熵与信息熵的差别在于 公式中的对数位置 ，在前面我们知道，信息熵就是我们在消除一个系统的不稳定性时，所需要付出的“代价”，但是在大多数情况下我们并不知道很多数据的真实分布，因此我们只能假定一个分布，即非真实分布，来拟合真实分布，那么利用这个非真实分布来消除系统的不稳定性所需要付出的代价，就是所谓的交叉熵。
举例说明：
已知一个袋子里有1个球，但是未知颜色，现在我们知道两种概率，一种为真实分布p，一种为非真实分布q，分布如下：
| 事件 | 蓝色球 | 紫色球 | 青色球 | 黑色球 |
|---|---|---|---|---|
| p | 0.5 | 0.1 | 0.1 | 0.3 |
| q | 025 | 0.25 | 0.25 | 0.25 |
那么我们利用利用p、q来进行计算，可以得到如下：
我们从数值可以看到，原先的信息熵为 1.6855 ，但由于我们未知真实的数据分布，采用非真实分布的信息熵为 2 ，导致消除系统不稳定性的代价增大，因而在设计系统时，我们经常会以交叉熵作为度量来减小交叉熵，实现更为合理的预测。
相对熵
相对熵的概念大致类似信息增益，这里给出公式进行理解
相对熵就是交叉熵减去信息熵，简而言之，就是当前采用的非真实分布消除不稳定性所需要的代价与真实分布所需要的代价之前的差值。
ID3与C4.5
ID3与C4.5算法是最传统的决策树分类算法，其最终会构建一颗决策树，决策树中有如下节点：
- 根节点 （决策树的开始）
- 中间节点 （中间的分支节点）
- 叶子节点 （分类结果）
在决策树的构建过程中，有 两个过程 是比较关键的：
- 如何开始，即如何选择合适的属性作为根节点去构建决策树
- 如何结束，即在何种情况下我们选择停止构建，将其作为叶子节点
在构建的过程中，有 一个属性 是比较关键的：即纯净度，我们在分类时要尽可能的保证叶子结点的纯净度，而如何衡量这一属性就要使用之前我们提到的信息熵。
ID3
在ID3构建决策树的过程中，我们选择分类节点的依据是信息增益。
C4.5
以往的学者在做研究的过程中发现，ID3算法所选取的信息增益，会倾向于选择可取值数目较多的属性，因为往往将数据分为更多类的属性，其信息增益会更大，但这是不合理的，因此C4.5算法对此提出了改进，选取增益率作为分类属性，所谓增益率，就是指在计算出信息增益的基础上，除以某一属性的固有值（Intrinsic value），我们记其为IV（a), 在这里a特指某一属性：
因为固有值是属性固定不变的值，当该属性可取值的数目比较多时，固有值也会更大，因此C4.5会导致算法更倾向于选择可取值较少的属性，所以，在实际操作的过程中，我们不应该直接以增益率为基准来划分属性，而是要先从候选划分属性中找出信息增益率高于平均水平的属性，再从中选取增益率最高的。
后续的相关问题
待补充
网友评论