决策树和信息熵

有没有玩过或听过这样一个游戏:参与游戏的一方在脑海里想好某个事物,然后其他参与者向他提问的方式猜答案,回答者只能回答是还是不是。问问题的人通过答复信息的判断推理,不断缩小待猜事物的范围,最后给出答案。

其实上面的过程就类似于决策树的工作原理。这个概念真的很简单,你都不需要了解机器学习的知识,就能搞明白决策树是如何工作的,所以决策树算法非常流行,也是最经常使用的数据挖掘算法之一。

就像上面那个游戏,关键点在于如何高效的问问题,那决策树的关键,就在于如何划分数据集。

划分数据集的大原则就是:将无序的数据变得更加有序。那用什么衡量有序和无需呢?就是信息熵。

要说信息熵,先说说信息量。信息量的公式如下:

其中p(x)是事件发生的概率。从公式可以看出,发生概率越大,信息量越小。显然是这样,我如果说太阳从东边升起,基本没什么信息量。如果我说太阳从西边升起,那信息量就太大了。

下面我们正式引出信息熵。

信息量度量的是一个具体事件发生了所带来的信息,而熵则是在结果出来之前对可能产生的信息量的期望——考虑该随机变量的所有可能取值,即所有可能发生事件所带来的信息量的期望。说白了就是对所有信息量求和:

所以说,熵越大,不确定性越大,越无序;熵越小,确定性越大,越有序。

所以我们构建决策树划分数据集的时候,应该选择划分前后信息熵变化最大的那种方式。划分前后信息熵变化称为信息增益(information gain),但实际上在数据集划分后,信息熵是减少的,信息熵减少也叫信息增益,这也是经常会困扰初学者的一个地方。下篇文章,我们将用python代码构建一个决策树。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180322G0K8O300?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券