算法杂货铺——分类算法之决策树(Decision tree)

2023-05-16

3.1、摘要

      在前面两篇文章中,分别介绍和讨论了朴素贝叶斯分类与贝叶斯网络两种分类算法。这两种算法都以贝叶斯定理为基础,可以对分类及决策问题进行概率推断。在这一篇文章中,将讨论另一种被广泛使用的分类算法——决策树(decision tree)。相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置,因此在实际应用中,对于探测式的知识发现,决策树更加适用。

3.2、决策树引导

      通俗来说,决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友,于是有了下面的对话:

      女儿:多大年纪了?

      母亲:26。

      女儿:长的帅不帅?

      母亲:挺帅的。

      女儿:收入高不?

      母亲:不算很高,中等情况。

      女儿:是公务员不?

      母亲:是,在税务局上班呢。

      女儿:那好,我去见见。

      这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别:见和不见。假设这个女孩对男人的要求是:30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员,那么这个可以用下图表示女孩的决策逻辑(声明:此决策树纯属为了写文章而YY的产物,没有任何根据,也不代表任何女孩的择偶倾向,请各位女同胞莫质问我^_^):

      上图完整表达了这个女孩决定是否见一个约会对象的策略,其中绿色节点表示判断条件,橙色节点表示决策结果,箭头表示在一个判断条件在不同情况下的决策路径,图中红色箭头表示了上面例子中女孩的决策过程。

      这幅图基本可以算是一颗决策树,说它“基本可以算”是因为图中的判定条件没有量化,如收入高中低等等,还不能算是严格意义上的决策树,如果将所有条件量化,则就变成真正的决策树了。

      有了上面直观的认识,我们可以正式定义决策树了:

      决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

      可以看到,决策树的决策过程非常直观,容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法,下面介绍决策树的构造算法。

3.3、决策树的构造

      不同于贝叶斯算法,决策树的构造过程不依赖领域知识,它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。

      构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支,其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况:

      1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。

      2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试,按照“属于此子集”和“不属于此子集”分成两个分支。

      3、属性是连续值。此时确定一个值作为分裂点split_point,按照>split_point和<=split_point生成两个分支。

      构造决策树的关键性内容是进行属性选择度量,属性选择度量是一种选择分裂准则,是将给定的类标记的训练集合的数据划分D“最好”地分成个体类的启发式方法,它决定了拓扑结构及分裂点split_point的选择。

      属性选择度量算法有很多,一般使用自顶向下递归分治法,并采用不回溯的贪心策略。这里介绍ID3和C4.5两种常用算法。

3.3.1、ID3算法

      从信息论知识中我们直到,期望信息越小,信息增益越大,从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择,选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。

      设D为用类别对训练元组进行的划分,则D的熵(entropy)表示为:

     

      其中pi表示第i个类别在整个训练元组中出现的概率,可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。

      现在我们假设将训练元组D按属性A进行划分,则A对D划分的期望信息为:

     

      而信息增益即为两者的差值:

     

      ID3算法就是在每次需要分裂时,计算每个属性的增益率,然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见,我们假设训练集合包含10个元素:

      其中s、m和l分别表示小、中和大。

      设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实,下面计算各属性的信息增益。

     

     

     

      因此日志密度的信息增益是0.276。

      用同样方法得到H和F的信息增益分别为0.033和0.553。

      因为F具有最大的信息增益,所以第一次分裂选择F为分裂属性,分裂后的结果如下图表示:

      在上图的基础上,再递归使用这个方法计算子节点的分裂属性,最终就可以得到整个决策树。

      上面为了简便,将特征属性离散化了,其实日志密度和好友密度都是连续的属性。对于特征属性为连续值,可以如此使用ID3算法:

      先将D中元素按照特征属性排序,则每两个相邻元素的中间点可以看做潜在分裂点,从第一个潜在分裂点开始,分裂D并计算两个集合的期望信息,具有最小期望信息的点称为这个属性的最佳分裂点,其信息期望作为此属性的信息期望。

3.3.2、C4.5算法

      ID3算法存在一个问题,就是偏向于多值属性,例如,如果存在唯一标识属性ID,则ID3会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率(gain ratio)的信息增益扩充,试图克服这个偏倚。

      C4.5算法首先定义了“分裂信息”,其定义可以表示成:

     

      其中各符号意义与ID3算法相同,然后,增益率被定义为:

     

      C4.5选择具有最大增益率的属性作为分裂属性,其具体应用与ID3类似,不再赘述。

3.4、关于决策树的几点补充说明

3.4.1、如果属性用完了怎么办

      在决策树构造过程中可能会出现这种情况:所有属性都作为分裂属性用光了,但有的子集还不是纯净集,即集合内的元素不属于同一类别。在这种情况下,由于没有更多信息可以使用了,一般对这些子集进行“多数表决”,即使用此子集中出现次数最多的类别作为此节点类别,然后将此节点作为叶子节点。

3.4.2、关于剪枝

      在实际构造决策树时,通常要进行剪枝,这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。剪枝有两种:

      先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。

      后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。

      关于剪枝的具体算法这里不再详述,有兴趣的可以参考相关文献。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

算法杂货铺——分类算法之决策树(Decision tree) 的相关文章

  • 使用docker搭建开发环境

    我的主力机是windows windows下面有太多提升效率的软件 但是开发的时候不得不使用linux 就单单开发而言 我还是喜欢使用linux 所以就造成了我得在windows下面使用虚拟机 这是最开始的办法 后面得知有vagrant这个
  • ROS的单线程Spinning和多线程Spinning

    单线程Spinning ros spin 是最简单的单线程自旋 它会一直调用直到结束 用法 ros spin 另一个单线程spinning是ros spinOnce 它定期调用等待在那个点上的所有回调 用法 ros spinOnce 简单的
  • antd 的form 表单怎么回显数据_antd Form表单的initialValue问题

    在initial中是有初始值的 xff0c 但是却不显示初始值 xff0c 请大佬解答一下这个问题 const formItem 61 type 3 label 39 柜子编号 39 name 39 ID 39 width 39 150px
  • echarts 与 highcharts

    一 xff0e 简介 echarts echarts是百度公司前端开发的一个图表库 xff0c 2013年发布第一版 xff0c 主要采用canvas画图 xff0c 目前版本3 8 4 xff1b 完全免费 xff1b highchart
  • c语言不同源文件变量,我在哪里可以在c程序中声明全局变量,无论是在头文件还是源文件中...

    本问题已经有最佳答案 xff0c 请猛点这里访问 嗨 xff0c 我是一个C 43 43 开发者 xff0c 现在我正在做C编程 我的问题是 xff0c 在C程序中 xff0c 哪个地方更好地声明全局变量 头文件或源文件 如果我的全局变量未
  • ***网址大全

    网址大全 最全的 国内 基地 http www hackbase com 帝国 http www darkup com 中国 联盟 http www chinahacker com起点 网络 http www qdhack com 边缘 h
  • 监控硬盘容量计算

    如何快速的计算摄像头一天存储量 摄像机的码流即监控视频流的带宽 xff0c 分为主码流和子码流 xff0c 主码流用来存储 xff0c 子码流一般用来预览 xff0c 所以录像回放时大家看到的视频质量要高于预览时看到的 在不同分辨率 帧率以
  • 【原】Hadoop伪分布模式的安装

    Hadoop伪分布模式的安装 环境参数 1 Host OS xff1a Win7 64bit 2 IDE xff1a Eclipse Version Luna Service Release 2 4 4 2 3 虚拟机 xff1a VMwa
  • 背景建模技术(四):视频分析(VideoAnalysis)模块

    视频分析模块主要包含两个函数 xff0c 一个是VideoAnalysis setup xff08 xff09 xff0c 其主要功能就是确定测试的视频是视频文件或摄像头输入亦或是采用命令行参数 xff1b 第二个函数是VideoAnaly
  • ubuntu 安装docker + seagull实现图形化管理

    环境 xff1a ubuntu 14 04 server 通过Docker源安装最新版本 要安装最新的 Docker 版本 xff0c 首先需要安装 apt transport https 支持 xff0c 之后通过添加源来安装 sudo
  • Ethzasl MSF源码阅读(1):程序入口和主题订阅

    关于IMU融合知乎上的一篇问答 xff1a 有哪些开源项目是关于单目 43 imu做slam的 xff1f Ethz的Stephen Weiss的工作 xff0c 是一个IMU松耦合的方法 1 程序入口 xff1a ethzasl msf
  • 自动化运维的5大好处

    2019独角兽企业重金招聘Python工程师标准 gt gt gt 努力解决企业IT日益增长的运维挑战 xff0c 大多数运维团队面临的最核心问题在于 如何用更少的资源完成更多工作 自动化运维则是这一问题的理想解决方案 xff0c 特别是在
  • UP Board 串口使用心得

    前言 原创文章 xff0c 转载引用务必注明链接 本文使用Markdown写成 xff0c 为获得更好的阅读体验和正常的图片 链接 xff0c 请访问我的博客 xff1a http www cnblogs com sjqlwy p up s
  • [转]Linux守护进程基础

    为什么80 的码农都做不了架构师 xff1f gt gt gt 1 守护进程中涉及到的基本概念 1 1进程组 1 1 1 进程组基本概念 进程组是一个或多个进程的集合 xff0c 可以接收来自同一个终端的各种信号 每运行一个程序或是命令都将
  • Spring Cloud核心组件详解

    转自 xff1a 作者 xff1a 石杉的架构笔记 链接 xff1a https juejin im post 5be13b83f265da6116393fc7 来源 xff1a 掘金 著作权归作者所有 商业转载请联系作者获得授权 xff0
  • unity 3d开发的大型网络游戏

    unity 3d开发的大型网络游戏 一 总结 1 unity的官网 上面应该有游戏列表 2 unity3D是很好的3d游戏引擎 xff0c 也支持2d xff0c 也能做很多画面精良的3A级游戏 3 范围 xff1a 电脑游戏 xff0c
  • 多系统电脑切换系统操作步骤

    1 电脑搜索栏输 msconfig 会出现下图 2 点引导 xff0c 多个系统的话 xff0c 引导这里显示的是多条信息 3 切换系统 在引导框中选中自己要切换的系统 xff0c 然后点击设为默认值 xff0c 再点应用 xff0c 再确
  • STM32标准外设库、 HAL库、LL库

    工作以来一直使用ST的STM32系列芯片 xff0c ST为开发者提供了非常方便的开发库 到目前为止 xff0c 有标准外设库 STD库 HAL库 LL库 三种 前两者都是常用的库 xff0c 后面的LL库是ST最近才添加 xff0c 目前
  • 图形算法可视化

    最近看了一些和图形 算法可视化相关的文章和代码 xff0c 挺有意思 xff0c 于是自己也学着做了些东西 迷宫生成算法 迷宫小时候玩过 xff0c 但从来没琢磨过迷宫是怎么设计的 xff0c 以为就是有人慢慢画出来的 看过网上这篇文章后
  • C/C++变量命名规则

    变量命名规则是为了增强代码的可读性和容易维护性 以下为C 43 43 必须遵守的变量命名规则 xff1a 1 变量名只能是字母 xff08 A Z xff0c a z xff09 和数字 xff08 0 9 xff09 或者下划线 xff0

随机推荐

  • 会议论文重新投稿算不算侵权?这肯定是所多人都遇到过的问题。

  • ubutu使用apt-get 安装报:Err http://security.ubuntu.com precise-security InRelease 等

    今天安装了下ubutu xff0c 安装完后按照教程使用apt get install 安装相关软件 xff0c 报错 复制错误百度了很久 xff0c 基本都是说源了问题 更换了好几个源 xff0c 还是没有成功 最后看见这个帖子 xff0
  • [追加评论]三款SDR平台对比:HackRF,bladeRF和USRP

    这三个月 xff0c 有幸把3种板子都用到了 说说使用体会 我用过其中的HackRF xff0c bladeRF x115 xff0c USRP B210 我并没有仔细的测量各种板子的射频指标什么的 xff0c 只是做各种实验的时候用到它们
  • linux zip

    zip r myfile zip 将当前目录下的所有文件和文件夹全部压缩成myfile zip文件 xff0d r表示递归压缩子目录下所有文件 2 unzip unzip o d home sunny myfile zip 把myfile
  • Eclipse中文注释乱码解决

    将别人的项目或JAVA文件导入到自己的Eclipse中时 xff0c 常常会出现JAVA文件的中文注释变成乱码的情况 xff0c 主要原因就是别人的IDE编码格式和自己的Eclipse编码格式不同 总结网上的建议和自己的体会 xff0c 可
  • H3C子接口配置要点及实例说明

    xfeff xfeff 类型一 xff1a 以太网子接口配置要点 单臂路由 第一步 xff1a 在路由器对端的交换机上配置好vlan信息 xff08 如vlan10 vlan20 xff09 第二步 xff1a 将交换机上与路由器直接相连的
  • 常用的SQL聚合函数:

    AVG 返回集合的平均值 COUNT 返回集合中的项目数 MAX 返回集合中的最大值 MIN 返回集合中的最小值 SUM 返回集合中所有或不同值的总和 GROUP BY 将结果按照指定的列进行分组 HAVING 过滤分组后的结果 聚合函数不
  • int型除以int型

    int型除以int型得到的还是int型 就算你是这样的 xff1a float a 61 5 3 xff0c 虽然你定义的a是float型 xff0c 但a得到的结果依旧是1 0000而不是1 66666 5 3先得到1 xff0c 然后再
  • Keepalived两节点出现双VIP情况及解决方法【原创】

    1 故障现象 俩台服务器keepalived的vip在俩台服务器同时出现 A xff1a 10 70 12 72 B xff1a 10 70 12 73 2 问题分析 1 xff09 先分析那台服务器在提供服务 A xff1a 10 70
  • 10款值得推荐的论坛系统源码

    无论您是一个技术娴熟的站长朋友 xff0c 还是初入互联网并致力于在这片领土发展的准站长 xff0c 或者您只是一个还未毕业的学生 xff0c 在为了毕业设计 课程设计不停的搜集资料 xff0c 只要您需要的是社区论坛系统的源码 xff0c
  • make[1]: *** [storage/perfschema/unittest/CMakeFiles/pfs_connect_attr-t.dir/all] 错误 2 解决方法...

    make 2 storage perfschema unittest pfs connect attr t 错误 1 make 1 storage perfschema unittest CMakeFiles pfs connect att
  • Yii2 中cookie的用法(1)

    Yii使用 yii web Cookie对象来代表每个cookie xff0c yii web Request 和 yii web Response 通过名为 cookies 的属性维护一个cookie集合 xff0c 前者的cookie
  • 修改.srt格式字幕文件

    2019独角兽企业重金招聘Python工程师标准 gt gt gt 正文前 xff1a 20160821104107 下载了 惊天魔盗团2 电影来看 xff0c 发现字幕只有英文没有中文 打开 srt文件 xff0c 随便改了一下 xff0
  • VC6.0+MSDN 下载(含链接)安装 全教程

    Microsoft Visual Studio 6 0 简体中文企业版 下载路径显示不出 xff0c 这个软件比较好下载 xff0c 主要是MSDN MSDN CD1 http ftp sdshiyan cn soft program DN
  • Dynamic Drop Down(Translate Values)

    This code i have got Ittool box com It is very usefull we usually have requirement when we want to hide some translate v
  • Windbg实用手册

    摘要 Windbg的命令分为标准命令 xff0c 原命令和扩展命令 xff0c 输入问号 可以显示所有的标准命令的帮助信息 元命令以一个点 开始 xff0c 输入 help可以显示所有的原命令的帮助信息 扩展命令以叹号 开始 阅读全文 Ri
  • Spring注解@Component、@Repository、@Service、@Controller区别 .

    Spring 2 5 中除了提供 64 Component 注释外 xff0c 还定义了几个拥有特殊语义的注释 xff0c 它们分别是 xff1a 64 Repository 64 Service 和 64 Controller 在目前的
  • sql 语句中如何写判断

    当ID为26时 xff0c 查询的result是ok span class token keyword select span name span class token punctuation span span class token
  • 光流定位原理是什么??【转】

    转自 xff1a https www zhihu com question 35980316 Jessie Lee HIT 控制 无人机 光流是测速算法 xff0c 并不是直接定位的 简单理解 xff0c 光流就是通过检测图像中光点和暗点的
  • 算法杂货铺——分类算法之决策树(Decision tree)

    3 1 摘要 在前面两篇文章中 xff0c 分别介绍和讨论了朴素贝叶斯分类与贝叶斯网络两种分类算法 这两种算法都以贝叶斯定理为基础 xff0c 可以对分类及决策问题进行概率推断 在这一篇文章中 xff0c 将讨论另一种被广泛使用的分类算法