信息熵与分类算法

重光兰衣

信息熵与分类算法        在介绍熵之前，先从另一个概念说起：信息量        世界杯决赛的两支球队中，哪支球队获得了冠军？在对球队实力没有任何了解的情况下，每支球队夺冠的概率都是1/2，所以谁获得冠军这条信息的信息量是 - log2 1/2 = 1 bit。如果信息是四强中的球队谁获得了冠军，它的信息量是 - log2 1/4 = 2 bit。
# {- \! K' g( b0 Q5 [        其实这正好对应了计算机对数字的表示，如果用二进制表示，每一位出现0和1的概率都是1/2，所以每一位的信息量是1bit。如果用十六进制表示，每一位出现任意一个符号的概率是1/16，所以每一位能表示 - log2 1/16 = 4 bit。所以1位十六进制的信息量，和4位二进制信息量是相同的。
7 f! q% i2 B& d1 |- \2 p. r; h         这样就比较好理解另一个经典的例子，英文有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。虽然表示的方式不同，但信息量差不多（这是一个很巧合的例子，仅用于说明信息量的含义，大多数词语都不会这么接近）。
      在实际的情况中，每种可能情况出现的概率并不是相同的，所以熵（entropy）就用来衡量整个系统的平均信息量，其计算公式如下   
& Q$ G) q$ M3 i) }& M# H+ [
% W9 Q: s6 ]" O# n) K       熵是平均信息量，也可以理解为不确定性。例如进行决赛的巴西和南非，假设根据经验判断，巴西夺冠的几率是80%，南非夺冠的几率是20%，则谁能获得冠军的信息量就变为 - 0.8 * log2 0.8 - 0.2 * log2 0.2 = 0.257 + 0.464 = 0.721，小于1 bit了。经验减少了判断所需的信息量，消除了不确定性。
        而且通过计算可以发现，巴西夺冠的几率越高，计算出的熵就越小，即越是确定的情况，不确定性越小，信息量越少。如果巴西100%夺冠，那么熵是0，相当于没有任何信息。当两队几率都是50%最难判断，所熵达到最大值1。其实之前的 - log2 1/2 = 1 bit 是简化了的计算过程，其结果也是通过熵的公式来计算的 - 0.5 * log2 0.5 - 0.5 * log2 0.5 = 1 bit，计算信息量要综合考虑每种结果的可能性。
9 m0 l4 e0 j) c- H1 H        另一个会迷惑的问题是熵会大于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。
         数据挖掘分类问题中构建决策树的算法ID3和C4.5，就是对熵的一个典型的应用。
; Q& [' F! z0 h5 o9 o. v1 w+ m9 ^以经典的根据天气判断是否打高尔夫球的例子来说明
; {, a: P) V% V) W) 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。
& s# e% {, V5 s! P3 [$ L        属性是如何使熵减少的呢？假设我们选取的是outlook，则通过这个属性可以将训练集划分成3个集合

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，使得总体的熵（各个子集熵的平均值）减少。
H-sunny = - 0.4 * log2 0.4 - 0.6 * log2 0.6 = 0.971
1 p* x/ q8 T9 ?5 s( g1 a' z& OH-overcast = - 1 * log2 1 - 0 = 0
5 c8 p' k2 e$ X3 H7 EH-rainy = - 0.6 * log2 0.6 - 0.4 * log2 0.4 = 0.971
, R7 B3 I7 A) B. s* xH-average = 0.971 * 5 / 14 + 0 * 4 / 14 + 0.971 * 5 / 14 = 0.694
7 e7 F- A0 o' \9 ^& C
        初始熵与分割后的总体熵的差值，就是信息增益 InfoGain = H-init - H-average = 0.94 - 0.694 = 0.246
3 k; e, a5 r  k7 P2 N5 w5 c相当于获得了有用的信息，使判断出结果所需的信息量减少了。所以ID3算法在每次分割时，都选取信息增益最大的属性，这样使用最少的分支判断就可以得到最终的结果。

3 _, H9 p) J; c( D) H          熵表示不确定性，可以衡量混乱程度或纯净度，因此也用作分类或聚类结果的评价标准。类似地，在得到了所划分的n个集合后，分别计算每个集合的熵，公式中的n为集合中类别的个数，pi为第i个类别在该集合中出现的概率。如集合中有4个元素，分别属于4个类别，那么这个集合的熵就是2。之后计算各个集合熵的加权平均值，即是整个划分结果的熵。同理，熵越低表示划分得越准确。
, z( `2 i8 {: w4 n0 q- n

- [, Z  G# k3 x6 Q; z


3 Q$ T' [2 C3 T" v& I8 n