3乌黑蜷缩浊响清晰凹陷硬滑是4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否10青绿硬挺清脆清晰平坦软粘否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷浊响稍糊凹陷硬滑否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否

信息熵:

描述信息的混乱程度,越接近1越混乱(纯度越低),0则不混乱(纯度越高)

以西瓜数据集为例,前7列(包含编号列)均为属性列,不是划分类别的指标,此例上一个瓜是否为好瓜是判断类别的唯一标准,则按照好瓜(是),好瓜(否)分为2类,即二分类问题故D的信息熵仅由最后一列(好瓜)进行计算简单看来:

好瓜的比例:(记为P(好瓜));坏瓜的比例:(记为P(坏瓜)),进行一次对比,最混乱情况也就是各一半,纯度最高情况则全部是好瓜/坏瓜.

如出现多个类别,则每个类别占比相同时最混乱,只有一个类别数据时纯度最高举例说明

(例1)

(情况2.2):P好瓜​101​,P坏瓜​109​这样看来,在二分类问题中,取每个情况取最大的pk,比较大小,越大的纯度越高即可但是三分类问题就会有点问题(例3)

3.1

(情况3.1):P1​106​,P2​102​,P3​102​

3.2

(情况3.2):P1​106​,P2​103​,P3​101​

在例3的情况下,仅仅比较最大值6/10都是一样的,那么就需要比较第二大的值,3/102/10,故3.2的纯度大于情况3.1由此可见,比较两个样本D信息熵的方法有了但是不太方便,如果要用一个值来量化纯度(混乱程度),思路很清晰,同一个情况(一个集合D)中的分类占比越大,则对纯度程度的贡献就越大.即在(情况3.2)中

3/10

1/10使用log函数可以实现8提到的要求.pk值越小,则log(pk)会更小.选用以2为底的对数函数,故当前样本集合D中第k类样本所占比例为pk(k1,2,3,…,|y|),则D的信息熵为:

Ent(D)

使用a进行划分后的混乱程度即每个子集的混乱程度乘以各自的权重之和又混乱程度可以使用信息熵Ent(D)进行计算则可以推导,计算公式为:

Gain(D,a)

Gain(D,a)Ent(D)−v1∑V​∣D∣∣Dv∣​Ent(Dv)

即表示集合

D包含若干属性,若使用某个属性a(即样本中的某列,例如色泽)对D进行划分,将D划分为多个子集以西瓜数据为例,如使用属性色泽进行划分,则一共有3个属性值,则将全部数据划分为3个子集,即:

按照色泽划分

D按照色泽划分​D青绿​∪D乌黑​∪D浅白​故a在D上的信息增益为:

Gain(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浅白​))可以看出,属性(色泽)对样本集D进行划分所能获得的纯度提升程度即为:Gain(D,色泽).

上文中求信息增益中,我们是忽略掉编号这一列的,因为按照编号属性进行计算信息增益,会划分17个子集,每个子集的信息熵Ent均为0,则信息增益Gain就是D的信息熵Ent

0.998

Gain(D,编号)Ent(D)−(00....0)Ent(D)0.998显然,这个信息增益非常高,单却是没有意义的,按照编号建立决策树,将会建立一个一层17分支的决策树.故,我们需要找到一个方法,解决信息增益对数数目校多的属性偏好这一个问题如使用Gain直接除V的数量(V是D按照属性a分组的所有子集,即D的子集数量),好像可以处理掉数目较多属性偏好的这个问题

0.998

VGain(D,编号)​170.998​0.058但是更适合的方法是除以IV(a),称为属性a的’固有值’Intrinsic

ValueIV,也称’

{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

IV(D,a)SplitInformation(D,a)−v1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​故增益率定义为

Gain\_ratio(D,a)

Gain_ratio(D,a)IV(D,a)Gain(D,a)​但是会带来一个新的问题,这个增益率会对数目较少的属性,有更强的偏好.(正好与信息增益的偏好相反)

8.故C4.5决策树算法,不是直接取增益率最高的属性,而是使用了一个启发式:

从候选划分属性中选出信息增益大于平均水平的属性,再选增益率最高的.

如有错误,敬请指正!

代码部分请参考:决策树代码实例(全部代码,包含绘图,ID.3算法,西瓜书示例)