首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

决策树与信息增益

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

概念

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

如上图,最上面的一个点我们叫它根节点(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算法。

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

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券