决策树与信息增益

今天我们开始介绍决策树。它既可以用于分类，也可以用于回归。这里我们主要介绍更加常见的分类用法。

概念

决策树，顾名思义，它的形状类似于一棵树，我们可以简单把它画出来：

如上图，最上面的一个点我们叫它根节点（root node），最下面不再进行分类的点我们叫它叶节点（leaf node）。

决策树的分类过程是这样的：

从根节点开始，根据数据的某一个特征进行分类，那么它的子节点中就储存了分类后的结果；然后，在子节点中，从剩余特征中选择一个再进行分类，将结果储存在子节点的子节点中；如此重复下去，直到子节点中的数据是“纯净”的，即只含有一个类别，也就是到达了叶节点。此时，决策树构建完成。

那么问题随之而来，数据有那么多特征，到底选择哪个进行分类最合适呢？

别急，我们先介绍一些基本概念，随后就会解答这个问题。

信息量与熵

·信息量

信息论的创始人香农认为

信息是用来消除随机不确定性的东西。

那么用什么来衡量不确定性的大小呢？信息量。

举个例子，“太阳从东方升起”，这句话的信息量是0。因为太阳肯定从东方升起，概率是1，并没有消除不确定性，所以这句话没有任何信息量。

再比如说，“某一片沙漠下雨了”，这句话的信息量就很大。为什么呢？通常情况下，沙漠不下雨的概率比较大，而且沙漠下不下雨这个事件是随机的，是不确定的。但这句话就消除了不确定性，而且是消除了很大的随机性（因为下雨的概率很小）。

从上面的例子我们可以看出，信息量好像和事件发生的概率成反比。也就是说，事件发生的概率越大，信息量越低；概率越小，信息量越大。

那信息量到底该如何量化呢？有没有什么函数能表示呢？下面我们来一步一步构建它。

首先，信息量h(x)和概率p(x)是有关系的，h(x)是因变量，p(x)是自变量。我们知道，自变量p(x)的取值是0-1的，而h(x)和p(x)又是反比的关系。那有没有什么函数在0-1的区间内是单调递减的呢？

有很多函数都满足，但我们最常见的就是-log()函数。它的图像是这样的：

从图中可以看出，-log()函数就是把我们熟悉的log()函数沿x轴“翻”上去的结果。而且，-log()函数不仅在0-1内是递减的，还要保证它的值是大于0的。因为我们的信息量不可能是负数。

因此，信息量的大小可以表示为

·熵

上面我们介绍了单个事件的不确定性可以用信息量来衡量。那如果有一堆事件，每个事件发生的概率不同，这些事件总体的不确定性该如何衡量呢？

我们一般用这些事件信息量的期望来反应出事件的不确定性。

假设每个事件发生的概率为p(x)，对应的信息量为h(x)，则总体的期望为

我们把上式就叫做随机变量X的信息熵，简称熵。熵同样反映了随机变量的不确定程度。

信息增益

让我们回到文章开头提出的问题，面对茫茫多的特征，该怎么选择才能对数据集进行合适的分类呢？

一种方法就是使用信息增益。

现在假设我们有一个数据集，每一个实例数据都对应了一个类别D，那么这些类别的信息熵就是H(D)。现在选定一个特征A，在给定A的前提下，再观察A中的类别D，此时其熵为H(D|A)。

那么我们的信息增益g(D,A)即可表示为

g(D,A)=H(D)-H(D|A)

为什么可以这么做呢？

我们来看，H(D)表示原始数据类别的不确定性；H(D|A)表示给定特征A之后的类别的不确定性；那么二者的差就表示这种不确定性减少了多少。我们总是希望减少的越多越好。

因此，在计算完数据中所有的特征后，我们会选择信息增益最大的那个特征来对根节点进行分类。

今天的内容到此为止，下一篇我们会举个具体的例子来说明如何用信息增益来生成决策树，以及使用信息增益的算法——ID3算法。