熵与分类问题详解程序员

世界杯决赛的两支球队中，哪支球队获得了冠军？（两个类别中选择其一）在对球队实力没有任何了解的情况下，每支球队夺冠的概率都是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。虽然表示的方式不同，但信息量差不多（这是一个很巧合的例子，仅用于说明信息量的含义，大多数词语都不会这么接近）。

在实际的情况中，每种可能情况出现的概率并不是相同的，所以
熵（entropy）就用来衡量整个系统的平均信息量，其计算公式如下

熵是平均信息量，也可以理解为不确定性。例如进行决赛的巴西和南非，假设根据经验判断，巴西夺冠的几率是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，计算信息量要综合考虑每种结果的可能性。

另一个会迷惑的问题是熵会大于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，就是对熵的一个典型的应用。

以经典的根据天气判断是否打高尔夫球的例子来说明

@relation weather.symbolic

@attribute outlook {sunny, overcast, rainy}
@attribute temperature {hot, mild, cool}
@attribute humidity {high, normal}
@attribute windy {TRUE, FALSE}
@attribute play {yes, no}

@data
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes
rainy,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个集合

sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
sunny,mild,normal,TRUE,yes

overcast,hot,high,FALSE,yes
overcast,cool,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes

rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
rainy,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

H-overcast = – 1 * log2 1 – 0 = 0

H-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

相当于
获得了有用的信息，使判断出结果所需的信息量减少了。所以ID3算法在每次分割时，都选取信息增益最大的属性，这样使用最少的分支判断就可以得到最终的结果。

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