信息熵与分类算法

重光兰衣

信息熵与分类算法        在介绍熵之前，先从另一个概念说起：信息量        世界杯决赛的两支球队中，哪支球队获得了冠军？在对球队实力没有任何了解的情况下，每支球队夺冠的概率都是1/2，所以谁获得冠军这条信息的信息量是 - log2 1/2 = 1 bit。如果信息是四强中的球队谁获得了冠军，它的信息量是 - log2 1/4 = 2 bit。
        其实这正好对应了计算机对数字的表示，如果用二进制表示，每一位出现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。虽然表示的方式不同，但信息量差不多（这是一个很巧合的例子，仅用于说明信息量的含义，大多数词语都不会这么接近）。
8 l) k& @0 V, y& D& V      在实际的情况中，每种可能情况出现的概率并不是相同的，所以熵（entropy）就用来衡量整个系统的平均信息量，其计算公式如下   
. a) I* i- a% _7 e6 j
       熵是平均信息量，也可以理解为不确定性。例如进行决赛的巴西和南非，假设根据经验判断，巴西夺冠的几率是80%，南非夺冠的几率是20%，则谁能获得冠军的信息量就变为 - 0.8 * log2 0.8 - 0.2 * log2 0.2 = 0.257 + 0.464 = 0.721，小于1 bit了。经验减少了判断所需的信息量，消除了不确定性。
- k' b; w) K$ A3 ^( \        而且通过计算可以发现，巴西夺冠的几率越高，计算出的熵就越小，即越是确定的情况，不确定性越小，信息量越少。如果巴西100%夺冠，那么熵是0，相当于没有任何信息。当两队几率都是50%最难判断，所熵达到最大值1。其实之前的 - log2 1/2 = 1 bit 是简化了的计算过程，其结果也是通过熵的公式来计算的 - 0.5 * log2 0.5 - 0.5 * log2 0.5 = 1 bit，计算信息量要综合考虑每种结果的可能性。
' Z# M# m$ [7 P* F$ ?9 s        另一个会迷惑的问题是熵会大于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。
! g5 @* [3 u9 ]7 u- q& ~5 Z         数据挖掘分类问题中构建决策树的算法ID3和C4.5，就是对熵的一个典型的应用。
以经典的根据天气判断是否打高尔夫球的例子来说明

@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。构建决策树的过程就是通过各种天气特征，来消除不确定性（使熵减少）。
. g" ~+ N6 ?9 v& Z+ U% B$ V+ D6 `       在选择分裂属性之前会计算一个初始的熵，但这个值却不是刚才提到的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。
% |" X% @7 O6 L/ Y8 ~$ J8 U7 L        属性是如何使熵减少的呢？假设我们选取的是outlook，则通过这个属性可以将训练集划分成3个集合
% P1 U! }$ F9 {' F2 S, \
7 [; L6 d, W$ Y5 a: U; Z  p7 S

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，使得总体的熵（各个子集熵的平均值）减少。
; J1 k* K6 l3 E/ `7 ?0 v  pH-sunny = - 0.4 * log2 0.4 - 0.6 * log2 0.6 = 0.971
H-overcast = - 1 * log2 1 - 0 = 0
H-rainy = - 0.6 * log2 0.6 - 0.4 * log2 0.4 = 0.971
9 y4 b6 j4 T# X2 U0 b9 p8 Y3 GH-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
相当于获得了有用的信息，使判断出结果所需的信息量减少了。所以ID3算法在每次分割时，都选取信息增益最大的属性，这样使用最少的分支判断就可以得到最终的结果。
% `* n  p" ~/ K/ F$ H8 x
          熵表示不确定性，可以衡量混乱程度或纯净度，因此也用作分类或聚类结果的评价标准。类似地，在得到了所划分的n个集合后，分别计算每个集合的熵，公式中的n为集合中类别的个数，pi为第i个类别在该集合中出现的概率。如集合中有4个元素，分别属于4个类别，那么这个集合的熵就是2。之后计算各个集合熵的加权平均值，即是整个划分结果的熵。同理，熵越低表示划分得越准确。
( j0 |3 x! V& m% W3 I  C* R- D9 @
) u2 g# b+ x& J( D2 K
1 y4 b* o4 q8 K- A0 x! P; \# n

% G$ Q$ N" ?/ z0 d
( e: x4 @8 e, l- _  J' j1 m* T