数据挖掘分类算法之决策树算法ID3

最近在看数据挖掘(Data Mining)的相关书籍,一直尝试使用程序实现书中的一些算法,怎奈实力有限,连MATLAB和Weka中现成的工具箱都不会使用。也就只能了解了解算法原理才能维持得了生活这样子了。不过懂得算法原理,基本离实现也不远了。

说到决策树算法就不能不说数据挖掘中的分类问题。分类与预测不同,分类的目的是获得一个分类函数或分类模型(也常常成为分类器),该模型能把数据集的实例映射到某一个给定类别。首先要声明的是,分类和预测是不同的,分类与聚类是两回事。分类是给出分类标号,这种标号是离散且无序的;而预测则建立连续值函数模型。聚类是无监督的学习,相应地,分类则是有监督的学习。

以上是摘自最近在看的《纵观大数据:建模、分析及应用》书中的解释。

那么什么是决策树算法呢?

决策树(如下图所示)算法是一种经典的分类算法。它采用自顶向下、递归的、各个击破的方式构造决策树。树的每一个节点上使用信息增益度量选择属性,可以从生成2的决策树中提取出分类规则,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类型。

ID3使用信息增益作为属性选择度量。

在信息增益中,重要性的衡量标准就是看特征能够为分类系统带来多少信息,带来的信息越多,该特征越重要。在了解什么是信息增益之前,我们需要知道什么是信息熵。这个概念最早起源于物理学,在物理学中是用来度量一个热力学系统的无序程度,而在信息学里面,熵是对不确定性的度量。在1948年,香农引入了信息熵,将其定义为离散随机事件出现的概率,一个系统越是有序,信息熵就越低,反之一个系统越是混乱,它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

假设一个随机变量X的取值为

每一种取到的概率为

那么就有如下,

信息增益定义为原来的信息需求与新的需求之间的差,即:

其中,A表示样本的属性,Value(A)是属性A所有的取值集合。V是A的其中一个属性值,Sv是S中A的值为V的样例集合。

以上的公式大概看一下,知道怎么计算就OK!

接下来,请看一个例子,下表(请自行放大)是14天的打网球记录,通过天气、温度、湿度和风力来预测是否打了网球。

从以上表格中,我们可以获取如下信息:

一共14个数据样本,其中Yes(正例)9个,No(负例)5个,因此当前的信息熵计算如下

在决策树分类问题中,信息增益就是决策树在进行属性选择划分前和划分后信息的差值。

首先利用属性Outlook来分类,那么如下图

可以看出Outlook这一属性被分成了三个部分,由上述的信息熵公式可以得到,

然后利用属性Temperature来分类

可以看出Temperature这一属性被分成了三个部分,由上述的信息熵公式可以得到,

然后利用属性Humidity来分类

可以看出Humidity这一属性被分成了两个部分,由上述的信息熵公式可以得到,

接下来到Wind属性,

综上所述,第一个分裂的属性应该是Outlook。

Outlook的下一级节点中Sunny和Rain节点仍然需要进一步分裂,分别计算剩余的温度、湿度和风力三个变量的信息增益,取得最大的值作为分裂属性,以此类推;而Overcast节点已经不需要分裂,可以直接判决为Yes类即可。

于是我们对Sunny节点和Rain节点分别进行进一步分裂。

首先我们先对Sunny节点进行分裂,我们此时需要比较温度湿度和风力三个变量的信息增益。(接下来对于公式我就不一一解释了,直接上公式计算。)

根据以上的计算接过来看,可以明显的看出Humidity是Sunny属性下进一步的分裂属性。所以正确的决策树应为下图

接下来轮到Rain属性的进一步分裂了,依次比较温度、湿度、风力的信息增益。

综上所述,可以看出在进一步的属性分裂中Wind的信息增益是最大的,而且最终结果都可以直接作出判别,故不需要再进一步的属性分裂。

因而最终的决策树为

总结:上述阐述了一个完整的决策树ID3算法。在决策树的每一个非叶子结点划分之前,先计算每一个属性所带来的信息增益,选择最大信息增益的属性来划分,因为信息增益越大,区分样本的能力就越强,越具有代表性,很显然这是一种自顶向下的贪心策略。以上就是ID3算法的核心思想。

p.s.恭喜RNG获得MSI世界冠军!LPL重回世界之巅!这比赛看得人真的很心惊肉跳(Happy),最后一盘掉线暂停了好多次。还是恭喜Uzi拿下了自己的第二座冠军!

p.s.封面是五一数模校赛时候做题二——《红楼梦》作者预测,所做的主要人物词云图,具体关于怎么做词云详情百度最好Google!下次打算写一写最简单的SVM(支持向量机)?看有没有时间吧。吐槽一波CASIO的计算器,我算信息熵的时候,计算器上总显示堆栈错误,233333,这是个什么错误啊。。。只好把等式拆开慢慢计算了,但是学过数值分析的同学应该知道,这样会存在很大的误差,所以上述计算可信值只精确到小数点后5位,切记!

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

扫码关注云+社区

领取腾讯云代金券