信息熵与分类算法

重光兰衣

信息熵与分类算法        在介绍熵之前，先从另一个概念说起：信息量        世界杯决赛的两支球队中，哪支球队获得了冠军？在对球队实力没有任何了解的情况下，每支球队夺冠的概率都是1/2，所以谁获得冠军这条信息的信息量是 - log2 1/2 = 1 bit。如果信息是四强中的球队谁获得了冠军，它的信息量是 - log2 1/4 = 2 bit。
; A0 q1 S( c: L, [; C1 B        其实这正好对应了计算机对数字的表示，如果用二进制表示，每一位出现0和1的概率都是1/2，所以每一位的信息量是1bit。如果用十六进制表示，每一位出现任意一个符号的概率是1/16，所以每一位能表示 - log2 1/16 = 4 bit。所以1位十六进制的信息量，和4位二进制信息量是相同的。
         这样就比较好理解另一个经典的例子，英文有26个字母，假设每个字母出现的概率是一样的，每个字母的信息量就是 - log2 1/26 = 4.7；常用的汉字有2500个，每个汉字的信息量是 - log2 1/2500 = 11.3。所以在信息量相同的情况下，使用的汉字要比英文字母要少——这其实就是十六进制和二进制的区别，在这个例子中，apple成了5位26进制的数值，信息量4.7 * 5 = 23.5；而苹果成为2位2500进制的数值，信息量11.3 * 2 = 22.6。虽然表示的方式不同，但信息量差不多（这是一个很巧合的例子，仅用于说明信息量的含义，大多数词语都不会这么接近）。
: ]. y7 M5 ^& I- q0 y      在实际的情况中，每种可能情况出现的概率并不是相同的，所以熵（entropy）就用来衡量整个系统的平均信息量，其计算公式如下   

       熵是平均信息量，也可以理解为不确定性。例如进行决赛的巴西和南非，假设根据经验判断，巴西夺冠的几率是80%，南非夺冠的几率是20%，则谁能获得冠军的信息量就变为 - 0.8 * log2 0.8 - 0.2 * log2 0.2 = 0.257 + 0.464 = 0.721，小于1 bit了。经验减少了判断所需的信息量，消除了不确定性。
0 i: u- }$ o) S$ c, }6 U, y        而且通过计算可以发现，巴西夺冠的几率越高，计算出的熵就越小，即越是确定的情况，不确定性越小，信息量越少。如果巴西100%夺冠，那么熵是0，相当于没有任何信息。当两队几率都是50%最难判断，所熵达到最大值1。其实之前的 - log2 1/2 = 1 bit 是简化了的计算过程，其结果也是通过熵的公式来计算的 - 0.5 * log2 0.5 - 0.5 * log2 0.5 = 1 bit，计算信息量要综合考虑每种结果的可能性。
        另一个会迷惑的问题是熵会大于1吗？答案当然是肯定的，刚刚计算的最大值为1bit，是因为最终的结果只有两种情况。在有四支球队的时候，其最大值就是 - 0.25 * log2 0.25 - 0.25 * log2 0.25 - 0.25 * log2 0.25 - 0.25 * log2 0.25 = 2 bit，当四支球队夺冠概率不等的时候，熵会小于2 bit。
0 V4 j5 V4 n) q" W7 r# d3 h5 J# H         数据挖掘分类问题中构建决策树的算法ID3和C4.5，就是对熵的一个典型的应用。
4 i# \- A8 X, ~3 ?- n9 y% \以经典的根据天气判断是否打高尔夫球的例子来说明
+ a. ?/ a. W) y3 a8 J
) v& k" \# H6 v* }) C

@relation weather.symbolic @attribute outlook {sunny, overcast, rainy} @attribute temperature {hot, mild, cool} @attributehumidity {high, normal} @attribute windy {TRUE, FALSE} @attribute play {yes, no} @data sunny,hot,high,FALSE,nosunny,hot,high,TRUE,no overcast,hot,high,FALSE,yes rainy,mild,high,FALSE,yes rainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,no overcast,cool,normal,TRUE,yes sunny,mild,high,FALSE,no sunny,cool,normal,FALSE,yesrainy,mild,normal,FALSE,yes sunny,mild,normal,TRUE,yes overcast,mild,high,TRUE,yes overcast,hot,normal,FALSE,yesrainy,mild,high,TRUE,no

       因为最终的结果只有yes和no两种，判断是否打高尔夫球所需的信息量（熵、不确定性）是1 bit。构建决策树的过程就是通过各种天气特征，来消除不确定性（使熵减少）。
       在选择分裂属性之前会计算一个初始的熵，但这个值却不是刚才提到的1。因为在只知道Class Label的情况下，是有一些经验上的信息的。如训练集中，有9个yes和5个no，这就好比我们知道在两队的交手记录中巴西获胜过几次，所以由此可以推算出现yes的概率是9/14，出现no的概率是5/14。所以初始的熵为 H-init =  - 9/14 * log2 9/14 - 5/14 * log2 5/14 = 0.94。
        属性是如何使熵减少的呢？假设我们选取的是outlook，则通过这个属性可以将训练集划分成3个集合

/ p/ k& i/ [9 T

sunny,hot,high,FALSE,no sunny,hot,high,TRUE,no sunny,mild,high,FALSE,no sunny,cool,normal,FALSE,yessunny,mild,normal,TRUE,yes overcast,hot,high,FALSE,yes overcast,cool,normal,TRUE,yes overcast,mild,high,TRUE,yesovercast,hot,normal,FALSE,yes rainy,mild,high,FALSE,yes rainy,cool,normal,FALSE,yes rainy,cool,normal,TRUE,norainy,mild,normal,FALSE,yes rainy,mild,high,TRUE,no

        某些子集在分割后变得更加纯净了，如当 outlook = overcast 的时候，全部为yes，该子集的熵为0，使得总体的熵（各个子集熵的平均值）减少。
% I1 E: r& V& n; a1 x' J! S* nH-sunny = - 0.4 * log2 0.4 - 0.6 * log2 0.6 = 0.971
0 I. G4 Z4 i0 Y! Z6 KH-overcast = - 1 * log2 1 - 0 = 0
: t* Q  P: i: k9 @( sH-rainy = - 0.6 * log2 0.6 - 0.4 * log2 0.4 = 0.971
H-average = 0.971 * 5 / 14 + 0 * 4 / 14 + 0.971 * 5 / 14 = 0.694

        初始熵与分割后的总体熵的差值，就是信息增益 InfoGain = H-init - H-average = 0.94 - 0.694 = 0.246
& c4 k6 Q7 a: P; J相当于获得了有用的信息，使判断出结果所需的信息量减少了。所以ID3算法在每次分割时，都选取信息增益最大的属性，这样使用最少的分支判断就可以得到最终的结果。
0 S0 r4 s, K; `
3 L6 j" {# L- j) Y# w" v/ F0 r          熵表示不确定性，可以衡量混乱程度或纯净度，因此也用作分类或聚类结果的评价标准。类似地，在得到了所划分的n个集合后，分别计算每个集合的熵，公式中的n为集合中类别的个数，pi为第i个类别在该集合中出现的概率。如集合中有4个元素，分别属于4个类别，那么这个集合的熵就是2。之后计算各个集合熵的加权平均值，即是整个划分结果的熵。同理，熵越低表示划分得越准确。
1 q0 F9 O8 x9 I* e* x6 X8 F
+ j4 G4 j- m' C& \* l
! Q# U* f0 C9 i; F: e" H


9 Z/ p% i7 c6 l3 B; Q6 H% |( a- |/ J