决策树学习-程序员宅基地

技术标签: 算法  神经网络和深度学习  机器学习  决策树  

决策树学习是应用最广的归纳推理算法之一,它是一种逼近离散值函数的方法。在这种方法中学习到的函数被表示为一颗决策树,学习得到的决策树也能再被表示为多个if-then规则,以提高可读性。
决策树学习方法对噪声数据有很好的健壮性且能够学习析取表达式。
决策树学习算法有很多,比如ID3、C4.5、ASSISTANT等等。这些决策树学习方法搜索一个完整表示的假设空间,从而避免了受限假设空间的不足。决策树学习的归纳偏置是优先选择较小的树。

 

决策树表示法

决策树通过把实例从根节点排列(sort)到某个叶子节点来分类实例,叶子节点即为实例所属的分类。
树上的每一个节点说明了对实例的某个属性(attribute)的测试,并且该节点的每一个后继分枝对应于该属性的一个可能值。

分类实例的方法是
  从这颗树的根节点开始,测试这个节点指定的属性;
  然后按照给定实例的该属性值对应的树枝向下移动;
  然后这个过程再以新节点为根的子树上重复。

决策树示例:
例子:在一个水果的分类问题中,采用的特征向量为:{颜色,尺寸,形状,味道},其中:
            颜色属性的取值范围:红,绿,黄
            尺寸属性的取值范围:大,中,小
            味道属性的取值范围:甜,酸
            形状属性的取值范围:圆,细
样本集:一批水果,知道其特征向量及类别
问   题:一个新的水果,观测到了其特征向量,应该将其分类哪一类?

通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction)。从树根到树叶的每一条路径对应一组属性测试的合取树本身对应这些合取的析取
上述例子可对应如下析取式:
               (颜色=绿∧尺寸=大)
            ∨(颜色=绿∧尺寸=中)
            ∨(颜色=绿∧尺寸=小)
            ∨(颜色=黄∧形状=圆∧尺寸=大)
            ∨(颜色=黄∧形状=圆∧尺寸=小)
            ∨(颜色=黄∧形状=细)
            ∨(颜色=红∧尺寸=中)
            ∨(颜色=红∧尺寸=小∧味道=甜)
            ∨(颜色=红∧尺寸=小∧味道=酸)

决策树的适用问题

决策树学习适合解决具有以下特征的问题
1.实例是由“属性-值”对表示的:实例是用一系列固定的属性和它们的值来描述的。
2.目标函数具有离散的输出值:决策树给每个实例赋予一个布尔型的分类。决策树方法很容易扩展到学习有两个以上输出值的函数。
3.可能需要析取的描述:决策树很自然地代表了析取表达式。
3.训练数据可以包含错误:决策树学习对错误有很好的健壮性,无论是训练样例所属的分类错误,还是描述这些样例的属性值错误。
4.训练数据可以包含缺少属性值的实例:决策树甚至可以再有未知属性值的训练样例中使用。

ID3算法

大多数已开发的决策树学习算法是一种核心算法(CLS算法)的变体。该算法采用自顶向下的贪恋搜索遍历可能的决策树空间。这种方法是ID3算法(Quinlan 1986)和后继的C4.5(Quinlan 1993)的基础。

ID3是一种自顶向下增长树的贪婪算法
  在每个节点选取能最好分类样例的属性;
  继续这个过程指导这棵树能完美分类训练样例;
  或所有的属性都已被使用过。
构造过程是从“哪一个属性将在树的根节点被测试”这个问题开始。
  分类能力最好的属性被选作树的根节点的测试。
  然后为根节点属性的每个可能值产生一个分枝,并把训练样例排列到适当的分枝(也就是,样例的该属性值对应的分枝)之下。
  算法从不回溯重新考虑以前的选择。

ID3算法的核心问题:

选取每个结点上要测试的属性。 如何衡量一个属性价值的高低呢? 这个问题没有统一答案。 ID3算法选择信息增益(Information Gain)最大的属性作为决策树结点。

熵(ENTROPY)

对于数据集合D,若任意一个数据d(d∈D)有c个不同取值选项。 那么数据集D对于这c个状态的熵为

其中Pi是数据集D中取值为i(或者说属于类别i)的数据的比例(或者概率)。 如果数据有c种可能值,那么熵的最大可能值为log2c。 定义0log0=0。

信息增益

属性A对于数据集D的信息增益Gain(D,A)
  由于使用该属性分割数据集D,而导致数据集D期望熵减少的程度。

Values(A)是属性A所有可能值的集合。 Dv是D中属性A的值为v的子集,即Dv={d|d∈D,A(d)=v}。 Entropy(D)是D未用属性A分割之前的熵。 Entropy(Dv)是D用属性A分割之后的熵。 属性A的每一个可能取值都有一个熵,该熵的权重是取该属性值的数据在数据集D中所占的比例。

决策树节点划分

任意一个结点n,可以出现以下三种情况
1.结点n中的样本属于同一类,即结点n绝对纯净。此时结点n不可进一步划分。
2.结点n中的样本不属于同一类,但是不存在任何一个划分可以使其子结点的平均熵低于结点n。此时结点n不可进一步划分。
3.可以用一个属性对结点n进行划分,从而使结点n的子结点具有更低的熵。此时结点n可以进一步划分。

确定叶节点

一个策略是: 对于每一个可以进一步划分的结点都进行划分,直到得到一个不可划分的子结点,并将该子结点定为叶结点。 这种策略完美分类训练数据, 但是当训练数据不能覆盖真实数据分布时,就会过度拟合。

实践中决策树学习不要追求训练样本的完美划分,不要绝对追求叶结点的纯净度。 只要适度保证叶结点的纯净度,适度保证对训练样本的正确分类能力就可以了。 当然叶结点纯净度也不能过低,过低则是欠学习。 我们应该在过度拟合与欠学习之间寻求合理的平衡。 即,在结点还可以进一步划分的时候,可根据预先设定的准则停止对其划分,并将其设置为叶结点

测试集方法:将数据样本集合分为训练集与测试集。 根据训练集构建决策树,每展开一层子结点,并将其设为叶结点,就得到一棵决策树,然后采用测试集对所得决策树的分类性能进行统计。 重复上述过程,可以得到决策树在测试集上的学习曲线。 根据学习曲线,选择在测试集上性能最佳的决策树为最终的决策树。

阈值方法 在决策树开始训练之前,先设定一个阈值作为终止学习的条件。 在学习过程中如果结点满足了终止条件就停止划分,作为叶结点。 终止条件 可以选择为信息增益小于某阈值, 或者结点中的数据占全体训练数据的比例小于某阈值等等。

叶节点的类别:对于叶结点n,如果在该结点对应的样本中,属于第i类的样本数量最多,则判该叶结点为第i类。

ID3算法伪代码

  • 第一步 创建根结点。
  • 第二步 根结点数据集为初始数据集。
  • 第三步 根结点属性集包括全体属性。
  • 第四步 当前结点指向根结点。
  • 第五步 在当前结点的属性集和数据集上,计算所有属性的信息增益。
  • 第六步 选择信息增益最大的属性A作为当前结点的决策属性。
  • 第七步 如果最大信息增益小于等于0,则当前结点是叶子结点,标定其类别,并标记该结点已处理。执行第十四步。否则执行第八步。
  • 第八步 对属性A的每一个可能值生成一个新结点。
  • 第九步 把当前结点作为新结点的父结点。
  • 第十步 从当前结点数据集中选取属性A等于某个值的数据,作为该值对应新结点的数据集。
  • 第十一步 从当前结点属性集中去除属性A,然后作为新结点的属性集。
  • 第十二步 如果新结点数据集或者属性集为空,则该新结点是叶子结点,标定其类别,并标记该结点已处理。
  • 第十三步 标记当前结点已处理。
  • 第十四步 令当前结点指向一个未处理结点。如果无未处理结点则算法结束。否则执行第五步。

ID3算法特点

ID3算法的假设空间就是所有可能决策树的集合,也是一个关于现有属性的有限离散值函数的完整空间。
ID3算法运用爬山法搜索假设空间, 并未彻底地搜索整个空间,而是当遇到第一个可接受的树时,就终止了。
ID3算法实际上用信息增益度量作启发式规则,指导爬山搜索。
ID3的搜索策略是:

  • 优先选择较短的树,而不是较长的;
  • 选择那些高信息增益高属性更靠近根结点的树。
  • 优先选择短的树,即复杂度小的决策树,更符合奥坎姆剃刀原则,也就是优先选择更简单的假设。

基本的ID3算法不回溯,对已经做过的选择不再重新考虑。

  • ID3算法收敛到局部最优解,而不是全局最优。
  • 可以对ID3算法得到的决策树进行修剪,增加某种形式的回溯,从而得到更优解。

ID3算法在搜索的每一步都使用当前的所有训练数据。
使用全体数据的统计属性(信息增益)可以大大降低个别错误训练数据对学习结果的影响。 所以ID3算法可以很容易地扩展到处理含有噪声的训练数据。
 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43135178/article/details/111283672

智能推荐

postfi收发邮件-程序员宅基地

文章浏览阅读735次。第一步初始化操作关闭防火墙,挂载,改selinux,安装软件配置主要文件#配置邮件服务器主机名76 myhostname = mail.baidu.com#配置域名(这个邮件服务器管理的是哪个区域范围的邮件发送)83 mydomain = baidu.com#指定邮件发送时的域名99 myorigin = $mydomain#指定网络接口(默认只监听本地但是如果要与外界通信那么就...

postman使用之三:API请求和查看响应结果-程序员宅基地

文章浏览阅读1k次。请求postman支持很多请求类型,界面左侧可以看到请求类型:get、post、put、patch等,右侧是发送和保存按钮,下方是请求支持的认证方式、信息头、信息体、私有脚本和测试结果。下面我们介绍下常用的get和put请求。get请求只需要选择get请求,输入接口地址,然后save,选择相应的文件夹post请求1. 选择get请求,输入接口地址,在header和body输..._postman怎么查询protobuf协议结果

KVM详解(八)——KVM虚拟机自启动_kvm虚拟机自动启动-程序员宅基地

文章浏览阅读3.1k次,点赞5次,收藏14次。今天继续给大家介绍Linux运维相关知识,本文主要内容是KVM虚拟机的自启动设置。一、KVM虚拟机自启动简介二、libvertd服务自启动三、磁盘自动挂载四、设置虚拟机自启动_kvm虚拟机自动启动

Kubuntu kde 好用的 快捷键_kde6 快捷键-程序员宅基地

文章浏览阅读7.9k次。1 krunner一般情况,这个东西可以呼唤出来,如果吧焦点设置在桌面上,但是当我们的焦点在其他应用中,敲击键盘上的字符就千呼万唤不出来了。一直都不知道怎么吧这个东西找出来,今天终于找到了解决方案。这个东西较 krunner。http://en.wikipedia.org/wiki/Run_command 既然找到了,我们把它加到系统的快捷键中。在 trigger 中添加对应的快捷_kde6 快捷键

SSL/TLS详解-程序员宅基地

文章浏览阅读3k次,点赞5次,收藏20次。面试问到Https加密协议,不太会?来看看这篇文章吧_ssl/tls

计算机网络——网线制作和局域网组建_网线制作和局域网组建实验-程序员宅基地

文章浏览阅读5.1k次,点赞10次,收藏40次。一、实验目的: 了解双绞线特性,掌握双绞线的分类与典型应用。 熟悉无屏蔽双绞线网线制作的标准和方法。 了解网线制作的技能技巧。 掌握测试仪的使用。 利用做好的网线通过交换机或路由器组建局域网。二、实验内容: 无屏蔽双绞线网线制作。 利用做好的网线通过交换机或路由器组建局域网。..._网线制作和局域网组建实验

随便推点

gitlab服务器502恢复过程_gitbale timeout: run: unicorn-程序员宅基地

文章浏览阅读3.5k次,点赞3次,收藏4次。gitlab服务器502恢复过程查看日志# gitlab-ctl restart sidekiq ok: run: sidekiq: (pid 6278) 0s# gitlab-ctl hup unicorn # gitlab-ctl statusrun: gitlab-workhorse: (pid 3747) 168s; run: log: (pid 3342) 193s..._gitbale timeout: run: unicorn

【愚公系列】2023年03月 .Net Core使用cpolar内网穿透功能实现钉钉回调事件的监听_alibabacloud.sdk.dingtalk-程序员宅基地

文章浏览阅读1w次,点赞6次,收藏7次。cpolar是一款拥有远程控制和内网穿透功能的软件。而且还可以监控端口的HTTP请求,利用实时的cpolar Web UI开发者工具,让您调试代码更容易。您可以监听所有隧道上的HTTP消息包,分析消息包的结构内容,找出问题点。还可以单击重放(Replay)按钮,重新发送该HTTP信令请求。_alibabacloud.sdk.dingtalk

html5制作涂鸦板,HTML5实现涂鸦板-程序员宅基地

文章浏览阅读1.3k次。最近闲的,看了看html5,强大的绘图功能让我惊奇,于是,写了个小玩意---涂鸦板,能实现功能有:画画,改色,调整画笔大小html5的绘图可以分为点,线,面,圆,图片等,点和线,这可是所有平面效果的基点,有了这两个东西,没有画不出来的东西,只有想不到的算法。先上代码了:html效果:好了,一个简陋的画图界面就搞好啦,下面开始写一些画线的代码$.Draw = {};$.extend($.Draw, ..._html涂鸦板

Ubuntu管理文件所有权和用户权限_ubuntu python生成的文件权限用户设置-程序员宅基地

文章浏览阅读1k次。简析chown和chmod用法 简析chown和chmod用法修改文件所有权--chown更改文件权限--chmod修改文件所有权–chown计算机网络实验在执行完python脚本后,由于以sudo模式启动,生成的文件夹所有者为root,文件夹右下角有小锁,其他用户没有访问修改的权力。用到语句:chown [选项] [更改目标所有者][:[更改目标组]] 文件名或:chown [选项] ..._ubuntu python生成的文件权限用户设置

用物理学突破深度学习理论瓶颈? Google-斯坦福发布《深度学习统计力学》综述论文,30页pdf阐述深度学习成功机制...-程序员宅基地

文章浏览阅读679次。来源:专知【导读】深度学习革新了很多应用,但是背后的理论作用机制一直没有得到统一的解释。最近来自谷歌大脑和斯坦福的学者共同在Annual Review ..._深度学习和力学理论结合

python画图保存成html格式、用浏览器打开页面为空白_无法在web浏览器中从python打开html文件,而是打开记事本...-程序员宅基地

文章浏览阅读1.0k次。Note that on some platforms, trying to open a filename using this function, may work and start the operating system’s associated program. However, this is neither supported nor portable.这里的问题是webbrows..._drawings保存html格式是空的