数据挖掘算法——利用信息熵构建决策树

决策树算法普遍存在于我们的日常生活中，我们在不经意间就会使用到决策树。比如你在纠结是否要去一家公司工作时，可能会用到下面的决策树：

整个决策过程是这样的：如果公司待遇高，你可能就愿意去；如果待遇不高，你可能会继续考虑公司的平台好不好。如果连平台都不好，那就直接拒绝。如果平台很好，你就会继续考虑自己在这个平台上是否有成长空间，如果没有，你就会拒绝。如果有成长空间，你会觉得即便待遇不高，也可以答应。

这样的决策过程最终形成一棵树，在这棵树上，每一个你提出的问题，都叫做决策结点，在最顶部的那个问题叫做根结点。每一个结论（同意or拒绝）叫做叶子结点。

在上面那张图的右边，标出了一个depth，指的是决策树的深度。这棵决策树的depth=3，意思最多用3次判断，就能得出结论。根据奥卡姆剃刀定律，决策树越简单越好，depth自然也是越小越好。

在上面这个例子中，每一个决策结点都是能用“是”或者“否”来判断的疑问句，而实际上我们拿到的真实数据集，内容往往是一些具体的数值，所以在决策结点一般会有一个阈值，我们将数据集中具体的数值和这个阈值进行比较，来划分出分支。

理解了什么是决策树，接下来的问题就是：如何构建决策树？从上面的例子可以看出来，构建决策树的关键在于：每一个决策结点上，你应该问什么问题，也就是放置什么样的判断条件。这个判断条件由两部分组成：

还是拿上面那个例子来举例，比如根结点用工资这个维度来划分，阈值是1万。那如果一份工作的工资是2万，大于阈值，这份工作就可以接受。

我们在构建决策树时，就是在做这样两件事情：找到合适的决策维度，以及合适的阈值。能解决这两个问题的方法很多，其中一个方法就是利用信息熵。

想一想我们利用决策树究竟在做一件什么事情。是不是在把一件原本非常不确定的事情，逐步划分，直到得出一个确定的分类结果。

一件事情的不确定程度，我们可以用信息熵来表示。信息熵越大，我们就认为这件事越不确定。所以构建决策树的过程，就是信息熵逐渐减少的过程。

信息熵是信息论的一个基础概念，用数学公式表示如下：

公式的意思是，在某个事件中，有k种可能的结果，i是其中的一种，p指的是i发生的概率。我们对这个概率求一下log，然后再和这个概率本身相乘一下，得到的值，还得取一下负，最后把所有这样的值（一共有k个），加在一起求个和，就是这个事件的信息熵。

举个例子：

左边事件有三种可能性，每一个都是三分之一的概率，它算出来的信息熵是1.0986。右边这个事件算出来的信息熵是0.8018。右边的信息熵更小，所以右边事件的确定性更高。事实上也是如此，右边事件中有一种可能性的概率高达70%，这就比较确定了。

最确定的情况，则如下图所示：

这种情况的信息熵等于零，它的三种可能性中，第一个可能性的概率为1，也就是百分之百发生。这就很确定了。

所以如果想让信息熵降低，其实就是把可能性往某一种分类结果上推。如果还不清楚，我们可以用二分类的问题来画一张信息熵的变化图，直观的看一下。

所谓二分类问题，就是事件只有两种情况，其中一种情况的概率是x，那么另一种情况的概率就是（1 - x），那信息熵的计算公式就可以变成如下图所示：

我们把x的概率从0.01取到0.99，就可以绘制出下面这张图：

可以看出，x的概率在0.5的时候，信息熵的值最大，也就是说当二分类问题五五开时，不确定度最高。所以当把概率向某一种可能性推的时候，信息熵就会下降，直到某一种情况概率为1时，事件就确定了。

所以在利用信息熵构建决策树时，就是去比较每一个判断条件带来的信息熵递减程度。选出导致信息熵递减程度最大的判断条件，然后把它放到根结点的位置。接着重复执行这样的步骤，直到构建出完整的决策树为止。