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

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

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

这样的决策过程最终形成一棵树,在这棵树上,每一个你提出的问题,都叫做决策结点,在最顶部的那个问题叫做根结点。每一个结论(同意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时,事件就确定了。

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180821G1HQ2D00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券