熵、信息增益与决策树
最近数据挖掘的作业涉及到了熵,然而上课没怎么听懂,不知道
Entroy 、Information Gain
的概念,Gogle了下,发现StackOverflow
上有一篇极好的答案。为了理解透彻,尝试翻译了下。
假设我们现在需要生成一颗决策树,这颗决策树的作用是根据名字来判断性别。
给出如下的数据:
名字 性别
------------
Shley f
Brian m
Caroline f
David m
以这些数据来生成决策树,再来预测 Amro
(原作者的名字)的性别。
第一步,找出上述数据中与目标值(性别)相关的特征,例如:首尾字母、长度、元音个数等(选择方法可见维基百科)。经过选择后,我们的数据如下:
名字 是否以元音结尾 元音个数 长度 性别
-----------------------------------------------
Shley 1 3 6 f
Brian 0 2 5 m
Caroline 1 4 8 f
David 0 2 5 m
ok,现在我们就可以生成一颗决策树了,例如:
长度 < 7
| 元音个数 < 3: male
| 元音个数 > =3
| | 是否已元音结尾 = 1: female
| | 是否已元音结尾 = 0: male
长度 >= 7: female
每个结点都表示某个特征的检查,根据检查结果往左或往右,直到最终的预测结果。
现在来检验下这颗树的准确度。以 Amro
为例,长度小于 7 ,元音个数( a
与 o
)小于 3 ,所以最终结果是 male
,译者也试了下自己的名字 Nick
,长度小于 7,元音个数( i
)小于 1,结果也是 male
,看来这颗树的准确度不错233。
决策树的生成方式是从上至下的,经过上一个结点的判断后,才能进入下一个结点继续判断。然而,问题就来了,如何在每个结点选择需要判断的特征?换句话说,在之前的生成树中,为什么第一个结点是长度,而不是元音个数或者是否以元音结尾呢?
解决这个问题的思想就是
所选择的特征,其对给定的数据的分类能力是最强的。
这句奇奇怪怪的话是什么鬼意思?比如,在上面的例子中,如果有一个特征是:名字中是否含有 l
,有就是女生,没有就是男生,那这个特征的分类能力就是最强的了,因为它能够直接将所给数据分成男生或女生,根本就不需要上述繁琐的生成树了。 然而这个特征比较极端,能够一眼看出,像是 长度
这个特征就不太好看出,这个时候就需要万能的数学来加以衡量了。
经过特征 名字中是否含有 l
,判断后,所得的目标值 直接就是男生或者女生,不需要再通过其它特征判断,也称为纯净度 purity 最高,用信息 Information 来衡量。
熵 Entroy ,则是用来衡量不纯度 impurity。
对于结果只有两种情况的事件来说,其熵的计算公式是:
Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))
p(a)
与 p(b)
分别表示这两种情况的概率,通常以 2 为底计算对数。
以抛硬币的例子来说,正反面的概率都为 1/2
,则 Entropy = 1
。
下图表示了熵相对于概率的变化曲线。横轴表示其中一种情况的概率,纵轴表示熵的值,结合老师PPT上所说,熵越高,不纯度越低,我们所获知的信息就越多。也就是说抛硬币时,如果硬币正面的概率为 1
,那其实我们也得不到任何信息,概率恢复为 1/2
时,我们反而获得了最多的信息。开个奇怪的脑洞,那是不是说,生活中,不确定性才是我们真正需要的呢?
对于会出现多种结果的事件,熵的计算公式如下:
通常 b = 2
回到之前以名字判断姓名的的问题上,假设我们在构造决策树时,选择某个特征作为结点时,正在衡量 是否以元音结束
这个特征:
是否以元音结束
[9m,5f] <--- [..,..] 表示到达这个结点的数据及分类情况,刚开始是9个男生,5个女生
/ \
=1 =0
------- -------
[3m,4f] [6m,1f]
则在判断前,p(m) = 9/14
,p(f) = 5/14
,其熵计算如下:
Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403
判断后,对于左分支,即以元音结尾,其熵计算如下:
Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852
同理,对于右分支
Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917
判断结束之后,根据左右分支数据所占的比例(左右各占 7/14
),我们也能够计算出判断后的熵:
Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885
则这时,我们所获得的信息增益 Information Gain 为
Information_Gain = Entropy_before - Entropy_after = 0.1518
也就是说,经过上面的计算后,我们成功地将不纯度减少了 0.1518,其中信息 Information 以 bit 为单位。
在生成决策树的每个结点时,我们都要对每个特征进行上述的计算,然后根据贪婪法则(Greedy manner)选择信息增益最大的特征作为该结点的决策依据。从上往下,直到所有经过判断后得出的结点都只包含纯净的数据,在本例上,就是,只有男生或女生。如果不纯净,就要为这个结点按照上述的计算继续选择特征作为决策依据。
呼,终于翻译完了,一方面感觉翻译要做到 信雅达 真难;另一方面真心觉得,学习姿势有条件还是去看原文吧,译者水平不行就是坑,比如这篇XD。