2.4　信息熵

在度量分支优劣的时候，我们用到了信息熵的概念。信息熵和热力学熵在本质上是相通的，它们度量了系统的不确定性或者说无序程度。在热力学中，熵和系统的微观状态数呈对数关系。在信息论中，熵有类似的定义，它与随机事件的概率呈对数关系。熵是一个抽象的概念，下面我们试图从具体的角度来理解熵是如何定义的。

为了理解熵的度量，我们通过一个例子来观察熵和信息的关系。考试单项选择题有A、B、C、D这4个选项，如果我们不知道题目怎么做，那么4个选项都有可能是正确答案，此时这个“系统”具有极大的不确定性，它的熵很大。现在，老师给我们提示说A和B都是错误的，因此系统的不确定性就大大降低了。因为老师带来了信息，我们得知可能的正确选项只剩下两个，信息使得熵减小了。所以说，信息和熵是互补的，信息蕴含着负熵。如果老师直接告诉我们正确答案，那么系统的不确定性就完全消除了，熵就减小到了0。由此可见，系统的熵等于完全消解它的不确定性所需要的信息量。

如何描述信息和熵的数量呢？我们需要一个单位，在数字世界里，最为通用的信息单位是比特（bit），也就是一个二进制位。回到单项选择题的例子，最初4个选项都有可能是正确的，为了区别这4种情况，我们需要log2 4=2比特（0、1、2、3这4种情况用二进制表示为00、01、10、11，需要2个二进制位，即2比特）。在老师给出提示后，只有两个选项之一是正确的，区分两种情况需要log2 2=1比特（0和1两种情况只需要1位二进制数就可以表示，因此是1比特）。因此，系统最初的熵是2比特，老师带来了1比特信息后，熵减小到了1比特。

我们更一般化地考虑一个离散变化的系统（连续变化的系统会有无穷多种状态），它的状态是不确定的，但是总是有限的N种可能状态之一。为了简化讨论，我们假设系统处于每一种状态的概率都是相等的。那么，我们需要log2 N位二进制数来区分0到N−1的不同状态，它的熵就等于log2 N。系统的熵（或者信息量）与状态数呈对数关系，对数底数的选择并不影响熵的相对大小，只影响衡量单位数量的熵的尺度。因此，不同底数对应于熵的不同单位，以2为底数的时候，单位是比特。当然我们也可以用自然对数来进行计算，那样的话，单位叫作奈特。

下面我们来看随机事件和随机变量。假设某个事件发生的概率为p，系统在事件发生前具有N种可能的等概率状态，事件发生使得可能的状态坍缩到p×N种。在这个过程中，熵从log2 N减小到log2 pN，这个事件的熵是log2 N−log2 pN=−log2 p。如果有一个随机变量x，它可以取集合X中的值，每个取值的概率为p（x），那么这个随机变量的熵H就是取各种可能值的熵的期望。

下面我们再回到决策树的问题。落入某个树节点的样本类标签是一个取值为{0，1}的随机变量，不同取值的概率就是正负样本的比例。假设类标签为1的概率是p，那么标签为0的概率就是（1−p），节点标签的熵是H=−p log2 p−（1−p）log2（1−p），就是我们前面用到的公式。

熵H和正样本比例p的关系如图2.3所示。可以看出，当样本比例接近于0或者1的时候，样本集纯度比较高，熵就很小。反之，当正负样本比例相当的时候，熵达到最大值。

图2.3　熵H和正样本比例p的关系