使用log函数可以实现8提到的要求.pk值越小,则log(pk)会更小.选用以2为底的对数函数,故当前样本集合D中第k类样本所占比例为pk(k=1,2,3,…,|y|),则D的信息熵为: E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k l o g 2 p k Ent(D) = -\sum\limits _{k=1}^{|y|}p_klog_2p_k Ent(D)=−k=1∑∣y∣pklog2pk
则: 使用 a 进行划分后的混乱程度 = 即每个子集的混乱程度乘以各自的权重之和 使用a进行划分后的混乱程度 = 即每个子集的混乱程度乘以各自的权重之和 使用a进行划分后的混乱程度=即每个子集的混乱程度乘以各自的权重之和
又混乱程度可以使用信息熵Ent(D)进行计算
则可以推导,计算公式为: G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a) = Ent(D) - \sum\limits _{v=1}^V \frac{|Dv|}{|D|}Ent(D^v) Gain(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv)
注: ∣ D ∣ 即表示集合 D 中的元素个数 |D| 即表示集合D中的元素个数 ∣D∣即表示集合D中的元素个数
以西瓜数据集举例说明
D包含若干属性,若使用某个属性a(即样本中的某列,例如色泽)对D进行划分,将D划分为多个子集
以西瓜数据为例,如使用属性色泽进行划分,则一共有3个属性值,则将全部数据划分为3个子集,即: D 按照色泽划分 = D 青绿 ∪ D 乌黑 ∪ D 浅白 D_{按照色泽划分} = D_{青绿} \cup D_{乌黑} \cup D_{浅白} D按照色泽划分=D青绿∪D乌黑∪D浅白
故a在D上的信息增益为: G a i n ( D , 色泽 ) = E n t ( D ) − ( ∣ D 青绿 ∣ ∣ D ∣ E n t ( D 青绿 ) + ∣ D 青绿 ∣ ∣ D ∣ E n t ( D 乌黑 ) ∣ D 浅白 ∣ ∣ D ∣ E n t ( D 浅白 ) ) Gain(D,{色泽}) = Ent(D) - (\frac{|D_{青绿}|}{|D|}Ent(D_{青绿}) +\frac{|D_{青绿}|}{|D|}Ent(D_{乌黑}) \frac{|D_{浅白}|}{|D|}Ent(D_{浅白}) ) Gain(D,色泽)=Ent(D)−(∣D∣∣D青绿∣Ent(D青绿)+∣D∣∣D青绿∣Ent(D乌黑)∣D∣∣D浅白∣Ent(D浅白))
上文中求信息增益中,我们是忽略掉编号这一列的,因为按照编号属性进行计算信息增益,会划分17个子集,每个子集的信息熵Ent均为0,则信息增益Gain就是D的信息熵Ent G a i n ( D , 编号 ) = E n t ( D ) − ( 0 + 0 + . . . . + 0 ) = E n t ( D ) = 0.998 Gain(D,{编号}) = Ent(D) - (0 + 0 + .... +0) = Ent(D) = 0.998 Gain(D,编号)=Ent(D)−(0+0+....+0)=Ent(D)=0.998
显然,这个信息增益非常高,单却是没有意义的,按照编号建立决策树,将会建立一个一层17分支的决策树.
故,我们需要找到一个方法,解决信息增益对数数目校多的属性偏好这一个问题
如使用Gain直接除V的数量(V是D按照属性a分组的所有子集,即D的子集数量),好像可以处理掉数目较多属性偏好的这个问题 G a i n ( D , 编号 ) V = 0.998 17 = 0.058 \frac {Gain(D,{编号})}{V} = \frac{0.998}{17} = 0.058 VGain(D,编号)=170.998=0.058
但是更适合的方法是除以IV(a),称为属性a的’固有值’（Intrinsic Value，IV）,也称’ 分离信息 ’ (Split information):算法如下: I V ( D , a ) = S p l i t I n f o r m a t i o n ( D , a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(D,a) =SplitInformation(D,a) = -\sum\limits _{v=1}^{V}\frac {|D^v|}{|D|}log_2\frac{|D^v|}{|D|} IV(D,a)=SplitInformation(D,a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣
故增益率定义为 G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( D , a ) Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(D,a)} Gain_ratio(D,a)=IV(D,a)Gain(D,a)
