1.6 信息熵

熵简单地说是对信息论中度量不确定性和无序程度的一种测度。熵值越大，就代表信息越混乱和不确定。反过来说，熵值越小，所代表的信息则更加有序和规范。

熵的定义：离散型的随机变量X的概率p（x）=P（X=x），x∈R。X的熵H（X）为：

假设0≤p（x）≤1，一个二元信息熵可以简单地表示为：

H（X）=-p（x）log2p（x）-（1-p（x））log2p（x）

熵曲线如图1-3所示。

从图1-3中可以看出，当p（x）=0.5时，熵达到最大，不确定性也达到最大。p（x）=0或者p（x）=1时的熵最小，不确定性最小。

随机变量的熵小于等于随机变量取值个数的对数值：H（x）≤log2|x|。当且仅当概率平均分布的时候，H（x）的最大值为。

信息熵，可以应用于有监督的算法。决策树ID3、C4.5就是应用熵作为测度的分类算法，我们下面用举例进行说明。

1.ID3算法

ID3算法的核心原则是“最大信息熵增益”。所谓最大信息熵增益即，每次进行下一次分裂时，计算出所有类别对应的当前特征的熵，选择能够使得熵增益最大的那一个类别进行下一步的分裂。假设有一组数据，设D为其某一个特征类别，则根据熵的定义可以得到D的熵为：

其中pi表示第i个类别整个训练元组发生的概率，在离散的随机过程中，可以用i出现的数量除以整个数据的总数量n作为估计。

由于对初始数据进行划分的类别不止一项，这就需要对已经进行D分类的数据再次分类。假设此次的类别为A，则特征A对数据集D划分的条件熵为：

因此，二者的差值即为信息增益：

ΔA=entro D-entroAD

ID3算法则是根据每次如何分裂来使得ΔA的值最大，来决定下一步的走向。

表1-7的这个例子是通过调查10个微博账号来介绍ID3算法如何构造决策树的。

设W、F、X和P来表示微博更新频率、主要发布内容、性别和账号是否绑定手机，下面来计算增益。

选一个初始的分裂项，这里选择P，则P的熵为：

entro P=-0.7log20.7-0.3log20.3=0.7*0.51+0.3*1.74=0.879

之后根据公式来计算剩余3个属性对P的期望。

1）W对P的期望为：

则信息增益ΔAW=0.879-0.554=0.325

2）F对P的期望为：

则信息增益ΔAF=0.879-0.879=0

3）X对P的期望为：

则信息增益ΔAX=0.879-0.79=0.089

因为W具有最大的信息增益，所以第一次分裂选择W为分裂属性。

决策树示意图如图1-4所示。

在图1-4的基础上，再递归使用这个方法计算下一分裂属性，最终就可以得到整个决策树。

2.C4.5算法

尽管ID3算法能够对下次分裂项的决策有所帮助，但其本身存在一个问题：它一般会优先选择有较多属性值的类别，因为属性值多的类别相对属性值少的类别有相对较大的信息增益。因此ID3的后继算法C4.5使用了增益率（Gain Ratio）来作为选择分支的准则，同时还引入“分裂信息（Split Information）”来惩罚取值较多的分类，其定义为：

联合熵：如果（X，Y）表示一对离散随机变量在一起时的不确定性度量，X，Y～p（x，y），则它们的联合熵H（X，Y）

合熵是描述一对随机变量平均所需信息量的测度。

条件熵：给定随机变量X的情况下，随机变量Y的条件熵定义为。

自信息的定义：自信息表示事件X发生的不确定性，也用来表示事件所包含的信息量

I（X）=-log2P（X）

互信息的定义：事件X、Y之间的互信息等于X的自信息减去Y条件下X的自信息。

I（X；Y）=H（X）-H（X|Y）=log2P（X，Y）/（P（X）P（Y））

互信息I（X；Y）表示已知Y值后X不确定性的减少量。Y的值透露了有关多少X的信息量。

通过图1-5可以对联合熵、条件熵和互信息有一个更加直观和形象的了解。