学习笔记：信息熵与决策树
信息熵
什么是信息熵
信息熵用于度量”预测随机变量Y的取值“的难度。信息熵越大说明Y的取值的不确定性越大，即预测难度越大。本文用H(Y)表示预测Y值的信息熵。
下表为两只球队的虚拟的胜、负、平历史记录，显然预测恒大比赛结果的难度要远小于绿城。因为恒大90%都是胜场，预测恒大胜就可以了。而绿城胜、平、负的概率都是三分之一，很难预测绿城的比赛结果。这里随便变量Y就是比赛结果，显然预测恒大比赛结果（即Y的取值为胜、平或者负）的信息熵要小于绿城，即不确定性小于绿城。
| 球队 | 胜 | 平 | 负 |
|---|---|---|---|
| 恒大 | 90% | 5% | 5% |
| 绿城 | 34% | 33% | 33% |
信息熵的计算方式
信息熵有很多计算公式，不同的计算公式获得的结果也是不同的，公式如下图所示
条件信息熵
条件信息熵度量的是”在X条件下预测Y的取值的难度”。
还是以足球比赛举例，X代表主客场，有主场和客场两种取值，如果恒大主场胜率90%，客场胜率50%，那么显然X不同时，信息熵也是不一样的。x1表示主场，x2表示客场，主场的信息熵表示为H(Y|x1)，客场为H(Y|x2)，恒大比赛结果的信息熵为
H(Y|X) = P(x1)*H(Y|x1) + P(x2)*H(Y|x2)
P(x1)和P(x2)分别表示主场和客场出现的概率。如果X还有更多的取值，如x3，x4，那么和上面类似，进行加权求值即可。
信息增益
信息增益度量的是X对预测Y的能力，这里我理解为对预测Y的难度影响程度
信息增益的计算公式为：
Gain(X,Y) = H(Y) - H(Y|X)
Gain(X,Y)越大，说明X对预测Y的难度影响越大，当H(Y)等于H(Y|X)时，Gain(X,Y)=0，信息增益为0，此时X对Y对预测Y的影响程度为0。
决策树以及条件信息熵在决策树中的应用
决策树解决的是分类问题。分类问题是基于历史数据，建立预测模型，对未知数据进行分类。比如对球赛结果的预测，其实是将比赛的结果分类到胜、平、负三类中去的。
构建决策树需要考虑的问题
- 根节点放置哪个条件属性
- 下面的节点放置什么属性
- 什么时候停止树的生长
使用条件信息熵解决上述问题
- 根节点放置哪个条件属性。使用贪心算法，选择条件信息熵最小的条件属性，即不确定性最小的条件属性。比如球赛预测如果有两个条件属性，属性一是主客场，属性二是天气条件，如果
H(Y|主客场) < H(Y|天气)，即主客场的条件信息熵更小，那么Gain(X,Y)就更大，即信息增益更大，那么应该选择主客场属性作为根节点。 - 下面的节点放置什么属性。继续选择当前分支下可选条件属性中条件信息熵最小的属性。
- 什么时候停止树的生长。如果信息熵已经小到一定程度，那么不应该让决策树继续生长，而是产生叶子节点，即胜、平或者负。
决策树的构造准则
- 分类简单
- 树结构简单
决策树的其他问题
- 连续型属性，上面提到的球赛预测都是离散型属性，比如主客场只有胜、平、负三种取值。而像年龄这种属性就是连续型属性。
- 决策树剪枝，因为决策树每一层的条件属性都是用贪心算法选择的，所以可能不是全局最优的，需要进行剪枝。
- 决策树常用算法 C4.5