文章目录

最近数据挖掘的作业涉及到了熵,然而上课没怎么听懂,不知道 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 ,元音个数( ao )小于 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/14p(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,其中信息 Informationbit 为单位。

在生成决策树的每个结点时,我们都要对每个特征进行上述的计算,然后根据贪婪法则(Greedy manner)选择信息增益最大的特征作为该结点的决策依据。从上往下,直到所有经过判断后得出的结点都只包含纯净的数据,在本例上,就是,只有男生或女生。如果不纯净,就要为这个结点按照上述的计算继续选择特征作为决策依据。


呼,终于翻译完了,一方面感觉翻译要做到 信雅达 真难;另一方面真心觉得,学习姿势有条件还是去看原文吧,译者水平不行就是坑,比如这篇XD。

文章目录