熵 条件熵 信息增益

版权声明：本文为博主-姜兴琪原创文章，未经博主允许不得转载。

在信息论和条件概率中，熵是表示随机变量不确定性的度量，设X是一个取有限个值的离散随机变量，其概率分布为

                             P(X=xi)=pi ,i=1,2,....,n

则随机变量X的熵定义为

                             H(X) = -累加 pi log pi  

熵越大，随机变量的不确定性就越大，从定义可验证

                            0<=H(p)<=logn

当随机变量只取两个值，例如1，0时，即X的分布为

                             P(X=1)=p  P(X=0)=1-p  0<=p<=1

熵为

                            H(p)=-p log2 P - (1-p)log2(1-p)

当p=0或p=1时 H(p)=0，随机完全没有不确定性。当p=0.5时H(p)=1，熵取值最大，随机变量不确定性。当p=0.5时，H(p)=1,熵取值最大，随机变量不确定性最大。

设有随机变量（x，y），其联合概率分布为

                             P(X=xi,Y=yi)=pij ,i=1,2,...,n;j=1,2,...,m

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(X|Y)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望

                                                              H(Y|X)=累加 pi H(Y|X=xi)

这里，pi=P(X=xi),i=1,2,...,n

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。此时，如果有0概率，令0log0=0

信息增益

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

                                                            g(D,A)=H(D)-H(D|A)

一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

决策树学习应用信息增益准则选择特征。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D)表示在特征A给定的条件下对数据集D进行分类的不确定性，那么他们的差，即信息增益，就表示由于特征A而使得对数据集D进行分类的不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

总结：信息增益为 数据集D的经验熵H(D) 与特征A对数据集D的经验熵H(D|A) 之差