信息熵

什么是信息熵

信息熵用于度量”预测随机变量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),恒大比赛结果的信息熵为


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。

决策树以及条件信息熵在决策树中的应用

决策树解决的是分类问题。分类问题是基于历史数据,建立预测模型,对未知数据进行分类。比如对球赛结果的预测,其实是将比赛的结果分类到胜、平、负三类中去的。

构建决策树需要考虑的问题

  1. 根节点放置哪个条件属性
  2. 下面的节点放置什么属性
  3. 什么时候停止树的生长

使用条件信息熵解决上述问题

  1. 根节点放置哪个条件属性。使用贪心算法,选择条件信息熵最小的条件属性,即不确定性最小的条件属性。比如球赛预测如果有两个条件属性,属性一是主客场,属性二是天气条件,如果H(Y|主客场) < H(Y|天气),即主客场的条件信息熵更小,那么Gain(X,Y)就更大,即信息增益更大,那么应该选择主客场属性作为根节点。
  2. 下面的节点放置什么属性。继续选择当前分支下可选条件属性中条件信息熵最小的属性。
  3. 什么时候停止树的生长。如果信息熵已经小到一定程度,那么不应该让决策树继续生长,而是产生叶子节点,即胜、平或者负。

决策树的构造准则

  1. 分类简单
  2. 树结构简单

决策树的其他问题

  1. 连续型属性,上面提到的球赛预测都是离散型属性,比如主客场只有胜、平、负三种取值。而像年龄这种属性就是连续型属性。
  2. 决策树剪枝,因为决策树每一层的条件属性都是用贪心算法选择的,所以可能不是全局最优的,需要进行剪枝。
  3. 决策树常用算法 C4.5