By

文章目录

最近数据挖掘的作业涉及到了熵，然而上课没怎么听懂，不知道 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。

文章目录