为了精确地定义信息增益,我们先定义信息论中广泛使用的一个度量标准,称为熵(entropy),它刻画了随意例子集的纯度(purity)。
给定包括关于某个目标概念的正反例子的例子集S,那么S 相对这个布尔型分类的熵为：
Entropy(S) = -p⊕log2p⊕ -pΘlog2pΘ
当中p⊕是在S 中正例的比例,pΘ是在S 中负例的比例。
在有关熵的全部计算中我们定义0log0 为0。
举例说明,如果S 是一个关于某布尔概念的有14 个例子的集合,它包括9 个正例和5 个反例(我们採用记号[9+,5-]来概括这样的数据例子)。
那么S 相对于这个布尔分类的熵(Entropy)为:
Entropy ([9+, 5−]) = −(9 / 14) log 2 (9 /14) − (5 / 14) log 2(5 / 14) =0.940
注意,如果S 的全部成员属于同一类,那么S 的熵为0。比如,如果全部的成员是正的 ( p⊕=1 ) , 那么 pΘ 就是 0 , 于是 Entropy(S) =− 1 ⋅ log ( 1 ) − (0) ⋅log (0) = −1 ⋅ 0 − 0 ⋅ log 0 = 0 。
另外,当集合中正反例子的数量相等时熵为1。
如果集合中正反例的数量不等时,熵介于0 和1 之间。下图显示了关于某布尔分类的熵函数随着p⊕从0 到1 变化的曲线。
信息论中熵的一种解释是,熵确定了要编码集合S 中随意成员(即以均匀的概率随机抽出的一个成员)的分类所须要的最少二进制位数。举例来说,如果p ⊕ 是1,接收者知道抽出的例子必为正,所以不必发不论什么消息,此时的熵为0。还有一方面,如果是p⊕0.5,必须用一个二进制位来说明抽出的例子是正还是负。
如果p⊕ 是0.8,那么对所需的消息编码方法是赋给正例集合较短的编码,可能性较小的反例集合较长的编码,平均每条消息的编码少于1 个二进制位。
更一般的,如果目标属性具有c个不同的值,那么S 相对于c 个状态(c-wise)的分类的熵定义为:
2) 用信息增益度量期望的熵减少
已经有了熵作为衡量训练例子集合纯度的标准,如今能够定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益”。简单的说,一个属性的信息增益就是由于使用这个属性切割例子而导致的期望熵减少。
当中Values(A)是属性A 全部可能值的集合。
Sv是S 中属性A 的值为v 的子集(也就是,S v ={s∈S|A(s)=v})。
请注意,等式的第一项就是原来集合S 的熵，第二项是用A 分类S 后熵的期望值。这个第二项描写叙述的期望熵就是每个子集的熵的加权和。
|Sv |权值为属于Sv 的例子占原始例子S 的比例。
所以Gain(S,A)是由于知道属性A的|S |值而导致的期望熵减少。
换句话来讲,Gain(S,A)是由于给定属性A 的值而得到的关于目标函数值的信息。
当对S 的一个随意成员的目标值编码时,Gain(S,A)的值是在知道属性A 的值后能够节省的二进制位数。
信息增益正是ID3 算法增长树的每一步中选取最佳属性的度量标准。
下图概述了怎样使用信息增益来评估属性的分类能力。在这个图中,计算了两个不同属性:湿度(Humidity)和风力(Wind)的信息增益：