机器学习决策树ID3算法,手把手教你用Python实现

简介:

云栖号资讯:【点击查看更多行业资讯
在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来!


决策树的定义

决策树是我本人非常喜欢的机器学习模型,非常直观容易理解,并且和数据结构的结合很紧密。我们学习的门槛也很低,相比于那些动辄一堆公式的模型来说,实在是简单得多。

其实我们生活当中经常在用决策树,只是我们自己没有发现。决策树的本质就是一堆if-else的组合,举个经典的例子,比如我们去小摊子上买西瓜。水果摊的小贩都是怎么做的?拿起西瓜翻滚一圈,看一眼,然后伸手一拍,就知道西瓜甜不甜。我们把这些动作相关的因素去除,把核心本质提取出来,基本上是这么三条:

  • 西瓜表面的颜色,颜色鲜艳的往往比较甜
  • 西瓜拍打的声音,声音清脆的往往比较甜
  • 西瓜是否有瓜藤,有藤的往往比较甜

这三条显然不是平等的,因为拍打的声音是最重要的,可能其次表面颜色,最后是瓜藤。所以我们挑选的时候,肯定也是先听声音,然后看瓜藤,最后看颜色。我们把其中的逻辑抽象出来然后整理一下,变成一棵树结构,于是这就成了决策树。

1

这个决策树本质上做的还是分类的工作,将西瓜分成了甜的和不甜的。也就是说决策树是一个树形的分类器,这个也是决策树的基本定义。另外从图中我们还有一个启示,在这个问题当中,决策树的特征都是离散值,而不是连续值。也就是说决策树可以接受像是类别、标识这样非数值型的特征,而逻辑回归这些模型则不太行。

如果你对这些细节还理解不深刻也没有关系,我们可以先放一放,至少我们明白了决策树的大概结构以及工作原理。

对于每一条数据来说,它分类的过程其实就是在决策树上遍历的过程。每到一个中间节点都会面临一次判断,根据判断的结果选择下一个子树。而树上的叶子节点代表一种分类,当数据到了叶子节点,这个叶子节点的值就代表它的分类结果。

决策树的训练

明白了决策树的结构和工作原理之后,下面就是训练的过程了。

在理清楚原理之前,我们先来看下数据。我们根据上面决策树的结构,很容易发现,训练数据应该是这样的表格:

2

那么最后我们想要实现什么效果呢?当然是得到的准确率越高越好,而根据决策树的原理,树上的每一个叶子节点代表一个分类。那么我们显然希望最后到达叶子节点的数据尽可能纯粹,举个例子,如果一个叶子节点代表甜,那么我们肯定希望根据树结构被划归到这里的数据尽可能都是甜的,不甜的比例尽可能低。

那么我们怎么实现这一点呢?这就需要我们在越顶层提取规则的时候,越选择一些区分度大的特征作为切分的依据。所谓区分度大的特征,也就是能够将数据很好分开的特征。这是明显的贪心做法,使用这样的方法,我们只可以保证在尽可能高层取得尽可能好的分类结果,但是并不能保证这样得到的模型是最优的。生成最优的决策树本质上也是一个NP问题,我们当前的做法可以保证在尽量短的时间内获得一个足够优秀的解,但是没办法保证是最优解。

回到问题本身,我们想要用区分度大的特征来进行数据划分。要做到这一点的前提就是首先定义区分度这个概念,将它量化,这样我们才好进行选择。否则总不能凭感觉去衡量区分度,好在这个区分度还是很好解决的,我们只需要再一次引入信息熵的概念就可以了。

信息熵与信息增益

信息熵这个词很令人费解,它英文原文是information entropy,其实一样难以理解。因为entropy本身是物理学和热力学当中的概念,用来衡量物体分散的不均匀程度。也就是说熵越大,说明物体分散得程度越大,可以简单理解成越散乱。比如我们把房间里一盒整理好的乒乓球打翻,那么里面的乒乓球显然会散乱到房间的各个地方,这个散乱的过程可以理解成熵增大的过程。

信息熵也是一样的含义,用来衡量一份信息的散乱程度。熵越大,说明信息越杂乱无章,否则说明信息越有调理。信息熵出自大名鼎鼎的信息学巨著《信息论》,它的作者就是赫赫有名的香农。但是这个词并不是香农原创,据说是计算机之父冯诺依曼取的,他去这个名字的含义也很简单,因为大家都不明白这个词究竟是什么意思。

之前我们曾经在介绍交叉熵的时候详细解释过这个概念,我们来简单回顾一下。对于一个事件X来说,假设它发生的概率是P(X),那么这个事件本身的信息量就是:

3

比如说世界杯中国队夺冠的概率是1/128,那么我们需要用8个比特才能表示,说明它信息量很大。假如巴西队夺冠的概率是1/4,那么只要2个比特就足够了,说明它的信息量就很小。同样一件事情,根据发生的概率不同,它的信息量也是不同的。

那么信息熵的含义其实就是信息量的期望,也就是用信息量乘上它的概率:

4

同样,假设我们有一份数据集合,其中一共有K类样本,每一类样本所占的比例是6
,那么我们把这个比例看成是概率的话,就可以写出这整个集合的信息熵:

5

理解了信息熵的概念之后,再来看信息增益就很简单了。信息增益说白了就是我们划分前后信息熵的变化量,假设我们选择了某一个特征进行切分,将数据集D切分成了D1和D2。那么7
就叫做信息增益,也就是切分之后信息熵与之前的变化量。

我们根据熵的定义可以知道,如果数据变得纯粹了,那么信息熵应该会减少。减少得越多,说明切分的效果越好。所以我们就找到了衡量切分效果的方法,就是信息增益。我们根据信息增益的定义,可以很简单地理出整个决策树建立的过程。就是我们每次在选择切分特征的时候,都会遍历所有的特征,特征的每一个取值对应一棵子树,我们通过计算信息增益找到切分之后增益最大的特征。上层的结构创建好了之后, 通过递归的形式往下继续建树,直到切分之后的数据集变得纯粹,或者是所有特征都使用结束了为止。

这个算法称为ID3算法,它也是决策树最基础的构建算法。这里有一个小细节, 根据ID3算法的定义,每一次切分选择的是特征,而不是特征的取值。并且被选中作为切分特征的特征的每一个取值都会建立一棵子树,也就是说每一个特征在决策树当中都只会最多出现一次。因为使用一次之后,这个特征的所有取值就都被使用完了。

举个例子,比如拍打声音是否清脆这个特征,我们在一开始就选择了它。根据它的两个取值,是和否都建立了一棵子树。那么如果我们在子树当中再根据这个特征拆分显然没有意义,因为子树中的所有数据的这个特征都是一样的。另外,ID3算法用到的所有特征必须是离散值,因为连续值无法完全切分。如果西瓜的重量是一个特征,那么理论上来说所有有理数都可能是西瓜的质量,我们显然不可能穷尽所有的取值。
这一点非常重要,不仅关系到我们实现的决策树是否正确,也直接关系到我们之后理解其他的建树算法。

代码实现

理解了算法原理和流程之后,就到了我们紧张刺激的编码环节。老实讲决策树的算法实现并不难,比之前的FP-growth还要简单,大家不要有压力。

首先,我们来创造实验数据:

8

这份数据模拟的是学生考试,一共考三门,一共要考到150分以上才算是通过。由于ID3算法只能接受离散值的特征,所以我们要先将连续值转成离散值,我们根据每一门的考试分数,生成三个档次。大于70分的是2档,40到70分的是1档,小于40分的是0档。

为了方便编码,我们把预测值Y放在特征的最后,并且返回这三个特征的名称,方便以后用来建树。

我们运行一下数据查看一下结果:

9

下面,我们实现计算集合信息熵的函数。这个函数也很简单,我们只需要计算出每个类别的占比,然后套用一下信息熵的公式即可。

10

有了信息熵的计算函数之后,我们接下来实现拆分函数,也就是根据特征的取值将数据集进行拆分的函数。

11

本质上就是根据特征取值归类的过程,我们可以随便调用测试一下:

12

和我们预期一样,根据特征的取值将数据分成了若干份。接下来我们就要实现核心的特征的选择函数了,也就是要选择信息增益最大的特征对数据进行切分。

13

到这里,我们所有工具方法都已经开发完了,下面就到了我们紧张刺激的建树部分了。建树其实并没有什么大不了的,无非是通过递归来重复调用上面的方法来创造每一个分支节点而已。如果你熟悉树形数据结构,会发现它和其他树形数据结构的构建过程并没有什么两样。
我们来看下代码,整个过程也只有十几行而已。

14

我们运行一下这段代码,会得到一份dict,这个dict当中的层次结构其实就是决策树的结构:

15

我们这样看可能不太清楚,但是我们把这个dict展开就得到了下图的这棵树结构:

16

我们观察一下上图当中红圈的部分,这个节点只有两个分叉,而其他的节点都有三个分叉。这并不是代码有bug,而是说明数据当中缺失了这种情况,所以少了一个分叉。这其实非常正常,当我们训练数据的样本量不够的时候,很有可能无法覆盖所有的情况,就会出现这种没有分叉的情况。

到这里虽然决策树是实现完了,但是还没有结束,还有一个关键的部分我们没有做,就是预测。我们训练完了,总得把模型用起来,显然需要一个预测的函数。这个预测的函数也简单,它介绍一条数据以及我们训练完的树结构,返回分类的结果。其实也是一个递归调用的过程:

17

我们来创造一些简单的数据测试一下:

18

基本上和我们的预期一致,说明我们决策树就实现完了。

总结

我们的决策树虽然构建完了,但是仍然有很多不完美的地方。比如说,目前我们的模型只能接受离散值的特征,如果是连续值则无法进行拆分。而且我们每个特征只能用一次,有时候我们希望能够多次使用同一个特征。在这种情况下ID3就无法实现了。所以我们还需要引入其他的优化。

在后序的文章当中我们将会讨论这些相关的优化,以及决策树这个模型本身的一些特性。如果对此感兴趣,一定不要错过。

【云栖号在线课堂】每天都有产品技术专家分享!
课程地址:https://yqh.aliyun.com/live

立即加入社群,与专家面对面,及时了解课程最新动态!
【云栖号在线课堂 社群】https://c.tb.cn/F3.Z8gvnK

原文发布时间:2020-05-22
本文作者:承志
本文来自:“掘金”,了解相关信息可以关注“掘金”

相关文章
|
11天前
|
机器学习/深度学习 存储 算法
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
|
27天前
|
监控 算法 安全
深度洞察内网监控电脑:基于Python的流量分析算法
在当今数字化环境中,内网监控电脑作为“守城卫士”,通过流量分析算法确保内网安全、稳定运行。基于Python的流量分析算法,利用`scapy`等工具捕获和解析数据包,提取关键信息,区分正常与异常流量。结合机器学习和可视化技术,进一步提升内网监控的精准性和效率,助力企业防范潜在威胁,保障业务顺畅。本文深入探讨了Python在内网监控中的应用,展示了其实战代码及未来发展方向。
|
1天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
|
7天前
|
监控 算法 安全
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
28 10
|
25天前
|
存储 算法 安全
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
50 17
|
1天前
|
机器学习/深度学习 人工智能 自然语言处理
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
|
28天前
|
存储 算法 安全
U 盘管控情境下 Python 二叉搜索树算法的深度剖析与探究
在信息技术高度发达的今天,数据安全至关重要。U盘作为常用的数据存储与传输工具,其管控尤为关键。本文探讨Python中的二叉搜索树算法在U盘管控中的应用,通过高效管理授权U盘信息,防止数据泄露,保障信息安全。二叉搜索树具有快速插入和查找的优势,适用于大量授权U盘的管理。尽管存在一些局限性,如树结构退化问题,但通过优化和改进,如采用自平衡树,可以有效提升U盘管控系统的性能和安全性。
26 3
|
3月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
196 6
|
1月前
|
机器学习/深度学习 人工智能 算法
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
276 13
机器学习算法的优化与改进:提升模型性能的策略与方法
|
1月前
|
机器学习/深度学习 算法 网络安全
CCS 2024:如何严格衡量机器学习算法的隐私泄露? ETH有了新发现
在2024年CCS会议上,苏黎世联邦理工学院的研究人员提出,当前对机器学习隐私保护措施的评估可能存在严重误导。研究通过LiRA攻击评估了五种经验性隐私保护措施(HAMP、RelaxLoss、SELENA、DFKD和SSL),发现现有方法忽视最脆弱数据点、使用较弱攻击且未与实际差分隐私基线比较。结果表明这些措施在更强攻击下表现不佳,而强大的差分隐私基线则提供了更好的隐私-效用权衡。
53 14

推荐镜像

更多