程序员经验分享-hwhale

决策树算法

2023-05-16

目录

1. 概述

1.1 算法导入

1.2 决策树定义

1.3 决策树发展

1.4 结构

1.5 从树到规则

2.决策树的构建

2.1 基本原理

2.2 特征选择

2.3 实例分析--ID3

2.4 增益率--C4.5算法

2.5 基尼指数--CART算法

 3. 决策树剪枝

 3.1 预剪枝

 3.2 后剪枝

 3.3 预剪枝vs后剪枝

 4. 连续值与缺失值处理

4.1 连续值处理

4.2 缺失值处理

5. 决策树的本质 

6. 决策树算法总结

1. 概述

1.1 算法导入

决策树基于“树”结构来进行决策。

1.2 决策树定义

  • 决策树( Decision Tree) 又称为判定树，是数据挖掘技术中的一-种重要的分类与回归方法，它是一种以树结构(包括二叉树和多叉树)形式来表达的预测分析模型。
  • 决策树(Decision Tree) 是有监督学习的一种算法。
  • 决策树有两种:分类树和回归树。

1.3 决策树发展

  • 第一个决策树算法: CLS (Concept Learning System)
  • 使决策树受到关注、成为机器学习主流技术的算法: ID3
  • 最常用的决策树算法: C4.5
  • 可以用于回归任务的决策树算法: CART (Classification and Regression Tree
  • 基于决策树的最强大算法: RF (Random Forest)

1.4 结构

  • 决策树由节点和分支组成。
  • 节点有三种类型:根节点，内部节点和叶节点。-般的，一棵决策树包含一个根节点，若干个内部节点和若干个叶节点。
  • 分支:用于连接各个节点。

        决策树学习的目的是为了产生一棵泛化能力强的决策树

1.5 从树到规则

        决策树转换成if- then规则:
                ●由决策树的根 节点到叶节点的每一条路径构建一 条规则;
                ●路径上内部节点的特征对应着规则的条件，而叶节点的类标签对应着规则的结论。

         互斥并且完备:每一个实例都被有且仅有一条路径或一条规则所覆盖。

2.决策树的构建

2.1 基本原理

策略:自上而下分而治之
        ●.自根至叶的递归过程， 在每个中间结点寻找一 个“划分” 属性。
        ●1)开始:构建根节点;所有训练数据都放在根节点，选择-个最优特征，按着这一特征将训练数据集分割成子集，进入子节点。
        ●2)所有子集按内部节点的属性递归的进行分割。
        ●3)如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
        ●4)每个子集都被分到叶节点.上，即都有了明确的类，这样就生成了一颗决策树。

策略:分而治之”(divide- -and-conquer)
        自根至叶的递归过程，在每个中间结点寻找一个“划分”(split or test)属性
        三种停止条件:
                (1)当前结点包含的样本全属于同一类别，无需划分;
                (2)当前属性集为空，或是所有样本在所有属性.上取值相同，无法划分;
                (3)当前结点包含的样本集合为空，不能划分.

伪代码：

解释：

训练集D={(x1,y1),(x2,y2).....}  x表示输入，y表示标签；x中有许多属性；属性集A={a1,a2,.....}

属性：要学习，不要学习；学习则为属性；

类别：要学习，不要学习；属于两种类别；C表示类别.

终止条件1：样本进来属于同一个类别，直接输出结果是C类返回。

终止条件2：没法划分了，特征向量中所有属性都用完了；或者D样本中的属性A都相同；然后将此节点标记为叶子节点，将样本D中数目最多的类当做类别返回。

终止条件3：当对数据进行划分成多个分支，如果存在分支中没有数据（分支为空），将划分前类别数目多的当做类别返回。

        决策树算法的核心：如何选择最优划分属性。

2.2 特征选择

        特征(属性)选择
                ●特征选择 是决定用哪个特征来划分特征空间。
                ●特征选择表示从众多 的特征中选择-个特征作为当前节点分裂的标准。
                ●如何选择特征有 不同的量化评估方法，从而衍生出不同的决策树。

        ◆特征选择的准则是什么?什么样的划分属性是最优的?
        我们希望决策树的内部节点所包含的样本尽可能属于同一类别，即节点的纯度”越来越高，可以高效地从根结点到达叶节点，得到决策结果。

        信息熵(entropy)是度量样本集合“ 纯度”最常用的一种指标
                ●假定当前样本集合D中第k类样本所占的比例为pk
                ●则D的信息熵定义为

                 若p=0，则plog2 p=0。Ent(D )的最小值为0，最大值为log2 |y|

        Ent (D)的值越小，则D的纯度越高。

        信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化。离散属性a的取值: {a,.,.,a"}          Dv:D中在a,上取值为aV的样本集合
        以属性a对数据集D进行划分所获得的信息增益为:

         ●信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。

        ●决策树算法第8行选择属性:       著名的ID3决策树算法

2.3 实例分析--ID3

         该数据集包含17个,   训练样例 |y|= 2,    其中正例占p1=\frac{8}{17}     反例占p2= \frac{9}{17}
         根节点的信息熵为:

        ●以属性“色泽”为例，其对应的3个数据
                子集分别为:D1(色泽=青绿)、D2(色泽=乌黑)、D3(色泽=浅白)
        ●^{D^{1}}(色泽=青绿)包含的编号为:{1,4,6,10,13,1 7}
        ●其中正样本占3/6、负样本占3/6

 分别计算^{D^{1}}(色泽=青绿）、^{D^{2}}（色泽=乌黑）、^{D^{3}}（色泽=浅白）

 属性“色泽”的信息增益为:

 再计算其他五个属性的信息增益：

显然，属性“纹理”的信息增益最大，选为划分属性

 开始递归：

        ●第一个分支( "纹理=清晰" )
        ●该分支包含的样例集合D1中有编号为{1,2,3,4,5,6,8,10,15}的9个样例
        ●用属性集合为{色泽，根蒂，敲声，脐部，触感}，基于D1计算出各属性的信息增益:

 "根蒂"、"脐部"、"触感" 3个属性均取得了最大的信息增益，可任选其中之一作为划分属性.

         ●对每个分支做进一 步划分，最终得到决策树

        分析发现信息增益会对对属性越多被选中的概率越大，属性较少的选中概率越小...

2.4 增益率--C4.5算法

        信息增益:对可取值数目较多的属性有所偏好( 缺点)

        增益率:

  •  属性a的可能取值数目越多(即V越大)，则IV(a)的值通常就越大。
  • 启发式:先从候选划分属性中找出信息增益高于平均水平的，再从中选取增益率最高的。

2.5 基尼指数--CART算法

        反映了从D中随机抽取两个样例,其类别标记不一致的概率
        Gini(D)越小，数据集D的纯度越高

                        

        属性a的基尼指数: 

        在候选属性集合中，选取那个使划分后基尼指数最小的属性

 3. 决策树剪枝

         研究表明:划分选择的各种准则虽然对决策树的尺寸有较大影响,但对泛化性能的影响很有限；例如信息增益与基尼指数产生的结果，仅在约2%的情况下不同；剪枝方法和程度对决策树泛化性能的影响更为显著；剪枝是决策树防止过拟合的手段，在数据带噪时甚至可能将泛化性能提升25%

        为了尽可能正确分类训练样本，有可能造成分支过多，出现过拟合可通过主动去掉一些分支来降低过拟合的风险
        基本策略:
                ◆预剪枝(pre-pruning):提前终止某些分支的生长
                ◆后剪枝(post-pruning):生成一棵完全树， 再“回头”剪枝

 原先的决策树只有训练集；现在我们挑选10个数据当做训练集，另外7个当做验证集

         使用训练集后生成的决策树，我们再使用验证集的数据对生成的决策树进行验证。验证后发现7个数据有4个数据是错误的，模型很不理想；模型出现过拟合，如何解决这个问题？——剪枝

 3.1 预剪枝

        若不划分，则将其标记叶节点，类别标记为训练样例中最多的”类别，若选“好瓜”验证集中，{4,5,8}被分类正确， 得到验证集精度为3/7=42.9%

        若划分,根据结点2,3,4的训练“好瓜”、集分别标记为‘好瓜”、“坏瓜”验证集中，{4,5,8,11,12} 的样例被划分正确，验证集精度提升为5/7=71.4%

 根据“脐部”划分完成后是否需要根据“色泽"来划分？我们分析划分后的精度。

 3.2 后剪枝

        先生成一棵完整的决策树，其验证集精度测得为42.9%

         首先考虑结点6若将其替换为叶结点，根据落在其上的训练样例{7,15}将其标记为“好瓜”，测得验证集精度提高至57.1%，于是可以剪枝。

        剪枝后的决策树:

        考虑结点5若将其替换为叶结点，根据落在其上的训练样例{6,7,15}将其标记为“好瓜”，测得验证集精度仍为57.1%，于是可以不剪枝。

        再考虑父节点结点2若将其替换为叶结点，根据落在其.上的训练样例{1,2,3,14}将其标记为“好瓜”，测得验证集精度提升至71 .4%，于是可以剪枝。剪枝后的决策树:

 考虑结点3,1若将其替换为叶结点，先后替换为叶结点，均未测得验证集精度提升，不需要剪枝。

最终经过后剪枝得到的决策树：

 3.3 预剪枝vs后剪枝

        时间开销:
                ●预剪枝:训练时间开销降低，测试时间开销降低
                ●后剪枝:训练时间开销 增加，测试时间开 销降低
        过/欠拟合风险:
                ●预剪枝:过拟合风险降低，欠拟合风险增加
                ●后剪枝:过拟合风险降低，欠拟合风险基本不变
        泛化性能:
                后剪枝通常优于预剪枝

 4. 连续值与缺失值处理

4.1 连续值处理

        连续属性如何划分?
        由于连续属性的可取值数目不再有限,因此不能直接根据连续属性的可取值来对结点进行划分。基本思路:连续属性离散化，常见做法:二分法。

4.2 缺失值处理

        现实应用中，经常会遇到属性值“缺失”(missing)现象仅使用无缺失的样例->对数据的极大浪费
使用带缺失值的样例，需解决:
        Q1:如何进行划分属性选择?
        Q2:给定划分属性，若样本在该属性上的值缺失，如何进行划分?
        基本思路:样本赋权，权重划分

        假设还是这个数据集，并且数据集有部分数据是缺失的。学习开始时，根结点包含样例集D中
全部17个样例，权重均为1

划分前：以属性“色泽”为例，该属性上无缺失值的样例子集D包含14 个样例，信息熵为

划分后：令\widetilde{^{D^{1}}}(色泽=青绿）、\widetilde{^{D^{2}}}（色泽=乌黑）、\widetilde{^{D^{3}}}（色泽=浅白）分别表示在属性“色泽”上样本子集，有

 因此，样本子集\widetilde{D}上属性“色泽”的信息增益为

 于是，样本集D上属性“色泽”的信息增益为

 类似地可计算出所有属性在数据集上的信息增益:

5. 决策树的本质 

树的分类本质--轴平行分类

  •         每个属性视为坐标空间中的一个坐标轴d个属性描述的样本就对应了d维空间中的一个数据点对样本分类===》在这个坐标空间中寻找不同类样本之间的分类边界
  •         决策树的分类边界特点:   轴平行，即它的分类边界由若干个与坐标轴平行的分段组成

 产生“轴平行”分类面实例分析：当属性是连续属性，我们使用二分法将其分类并构造一个决策树，通过构造密度与含糖率数据的值分布，我们就可以找到一个与轴平行区分好瓜与坏瓜的分类面。

         当学习任务所对应的分类边界很复杂时，需要非常多段划分才能获得较好的近似

 我们可以给决策树叠加一些东西，让他可以实现更加平滑的分类边界——斜决策树

“斜决策树”(oblique decision tree)不是为每个非叶结点寻找最优划分属性而是建立一个线性分类器

         所以决策树不单纯是一棵树，而是一颗可以挂载东西嵌入很多模型算法        的树，更复杂的“混合决策树”甚至可以在结点嵌入神经网络或其他非线性模型

6. 决策树算法总结

优点:
        (1)速度快:计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的谓词。
         (2)准确性高:挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要。
         (3) 非参数学习，不需要设置参数。

缺点:
        (1)缺乏伸缩性:由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集。
        (2)为了处理大数据集或连续值的种种改进算法(离散化、取样)不仅增加了分类算法的额外开销，而且降低了分类的准确性,对连续性的字段比较难预测，当类别太多时，错误可能就会增加的比较快，对有时间顺序的数据，需要很多预处理的工作。

决策树算法实现：

from sklearn.tree import Decis ionTreeClassifier
model = Decis ionTreeClassifier( )
 

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

决策树算法 的相关文章

  • slf4j下log.info()无法输出到控制台&重复打印

    在logback xml中添加如下 lt logger name 61 34 你要在哪个类或者包下使用log的全限定名 34 level 61 34 日志输出等级 这里要用log info 所以级别是INFO 34 additivity 6

  • 在php中使用redis cluster 集群

    目前我们用到的 php 的 redis 扩展 主要有2个 xff0c 第一个是最常用的 phpredis 它是用c写的php的高效扩展 xff1a https github com phpredis phpredis xff0c 还有1个是

  • csdn markdown帮助文档

    欢迎使用Markdown编辑器写博客 本Markdown编辑器使用 StackEdit 6 修改而来 xff0c 用它写博客 xff0c 将会带来全新的体验哦 xff1a Markdown和扩展Markdown简洁的语法 代码块高亮 图片链

  • Springboot+Thymeleaf配置与使用

    Springboot 43 Thymeleaf配置与使用 前言 Springboot默认是不支持JSP的 xff0c 默认使用thymeleaf模板引擎 所以这里介绍一下springboot使用Thymeleaf的实例以及遇到的问题 配置与

  • git 解决pull origin 错误 error: The following untracked working tree files would be overwritten by merge

    error The following untracked working tree files would be overwritten by merge bin AndroidManifest xml Please move or re

  • SpringBootTest单元测试组件

    SpringBootTest单元测试组件 一 SpringbootTest 使用Junit4开发 1 添加依赖 span class token tag span class token tag span class token punct

  • ICE C++ Hello World

    ICE C 43 43 Hello World实例教程 1 概述 本文演示了如何编写一个最简单的C 43 43 ICE Internet Communications Engine 应用程序 xff0c 包括必要环境的安装 该应用程序包含客

  • 华为工作的感悟

    参考 xff1a http www openlab net cn forums thread 1002986 1 p10035795 北邮北 xff0c 清华硕 xff0c 一年两个月的华为生活总结 xff0c 算了 xff0c 贴出来了

  • MRCP 媒体资源控制协议

    媒体资源控制协议 xff08 Media Resource Control Protocol MRCP xff09 是一种通讯协议 xff0c 用于语音服务器向客户端提供各种语音服务 如语音识别和语音合成 MRCP并不定义会话连接 xff0

  • Hadoop中VIntWritable编码方式解析

    最近因为实验室的云计算项目 xff0c 开始学习Hadoop xff0c 有时间就记录一下自己在学习过程中的一些小收获吧 Hadoop权威指南 在序列化这一节有个例子程序 xff0c 叫做TextPair xff0c 代码略长 xff0c

  • 测试分析报告

    测试分析报告 1 引言 1 1 1 编写目的 1 1 2 背景 1 1 3 定义 2 1 4 参考资料 2 2 测试概要 2 3 测试结果及发现 3 3 1 测试 1 xff08 normal xff09 3 3 2 测试 2 xff08

  • MapReduce中的二次排序

    在MapReduce操作时 xff0c 我们知道传递的 lt key value gt 会按照key的大小进行排序 xff0c 最后输出的结果是按照key排过序的 有的时候我们在key排序的基础上 xff0c 对value也进行排序 这种需

  • 基于哈夫曼编码的文件压缩解压

    这个程序是研一上学期的课程大作业 当时 xff0c 跨专业的我只有一点 C 语言和数据结构基础 xff0c 为此 xff0c 我查阅了不少资料 xff0c 再加上自己的思考和分析 xff0c 实现后不断调试 测试和完善 xff0c 耗时一周

  • Errors were encountered while processing 解决方法

    在执行更新或者安装软件命令时 sudo apt get upgrade sudo apt get install 遇到 xff1a Errors were encountered while processing 查看错误信息发现 xff1

  • JSON传list数据到springMVC后台并用对象接收

    在项目中经常获取前台table中的数据 然后拼接传向后台 之前一直按照JSON格式拼接 但是非常容易出问题 而且遇到了类似List lt beans gt list 这样的参数 springMVC转化为对象会报错 正确的做法是按下面这种做法

  • Java解析网络数（Json）运用CloseableHttpClient

    最近做用Java网络爬取数据的部分 xff0c 发现在使用Apache的httpclient的时候 xff0c 发现Idea提示DefaultHttpClient等常用的类已经不推荐使用了 现在运用 CloseableHttpClient

  • 【Linux】Ubuntu18.0.4安装wine 失败遇到的问题和解决的思路 尝试覆盖共享/usr/share/doc/ 处理时有错误 /tmp/apt-dpkg-install-6NvbtI/

    bug说明 xff1a dpkg 处理归档 var cache apt archives libattr1 1 2 4 47 2 amd64 deb unpack 时出错 xff1a 尝试覆盖共享的 usr share doc libatt

  • 算法模型---时间序列模型

    文章来源 时间序列 时间序列是时间间隔不变的情况下收集的不同时间点数据集合 xff0c 这些集合被分析用来了解长期发展趋势及为了预测未来 时间序列与常见的回归问题的不同点在于 1 时间序列是跟时间有关的 而线性回归模型的假设 xff1a 观

  • java: 找不到符号 符号: 类 BASE64Encoder 位置: 程序包 sun.misc

    1 问题 新项目编译报错如下 xff1a java 找不到符号 符号 类 BASE64Encoder 位置 程序包 sun misc 2 解决方案 依图如下 xff0c 修改jdk对应的版本即可

  • tar 打包隐藏文件

    前言 xff1a 先说一下遇到的场景 xff1a 前段时间在配合做 DevOps xff0c 组内有块代码是 php 的 xff0c 需要用 tar 命令打包归档上传到 nexus 库 xff0c 后来发现解压出来的包居然缺失了隐藏文件 x

随机推荐

  • The server selected protocol version TLS10 is not accepted by client preferences [TLS12] 报错处理

    一 问题描述 xff1a 项目工程需求要连接 SqlServer 服务器 xff0c 但是报错了 xff0c 完整错误如下 xff1a com microsoft sqlserver jdbc SQLServerException 驱动程序

  • 23种设计模式

    目录 创建型 1 Factory Method xff08 工厂方法 xff09 2 Abstract Factory xff08 抽象工厂 xff09 3 Builder xff08 建造者 xff09 4 Prototype xff08

  • SpringBoot开启异步多线程

    前言 xff1a SpringBoot 的异步多线程需要从 java 的多线程基础说起 xff0c 可以参考 java 多线程实现的三种方式区别 SpringBoot 在此基础上进行了多次封装 xff0c 所以使用起来非常方便 一 核心参数

  • 制作 java-sdk 的两种方式

    前言 xff1a 平时maven工程里 pom 中的引用的依赖就是别人开发好的 sdk 包 xff1b 工作中为了方便一些开发也需要自定义开发 sdk 包 xff0c 下面介绍下怎么开发 一 两种方式 我们平时引用 sdk 有两种方式 xf

  • SpringBoot 之 AOP

    前言 xff1a Spring 三大核心思想是啥 xff0c 还记得不 xff1f IOC xff08 控制反转 xff09 xff0c DI xff08 依赖注入 xff09 xff0c AOP xff08 面向切面编程 xff09 回顾

  • mongodb 的常用数据操作

    摘要 xff1a 主要记录一些常见 的mongodb 的增删改查 xff0c 方便以后查阅 1 增 基本格式 xff1a db test doc insert 或 db test doc save 样例 xff1a db test doc

  • Python键盘输入转换为列表

    Python输入字符串转列表是为了方便后续处理 xff0c 这种操作在考试的时候比较多见 1 在Python3 0以后 xff0c 键盘输入使用input函数 eg1 span class hljs prompt gt gt gt span

  • java.lang.NoSuchMethodError 原因和处理方案

    问题描述 工程中明明有该方法 xff0c 却提示 java lang NoSuchMethodError 错误 1 原因 java 的类加载机制是把所有不同名称的本类和引用类的包全部加载到内存 xff0c 这样就有一个问题 xff0c 如果

  • java：try...catch跳过异常继续处理循环

    问题描述 在代码循环体中 xff0c 抛出异常后代码会停止执行 xff0c 导致代码不能完整运行 解决方案很简单 xff0c 捕获异常并简单处理一下就可以 1 捕获异常继续执行代码 只贴核心样例代码 public void getTest

  • python去掉空格常用方式

    前言 xff1a 处理字符串时经常要定制化去掉无用的空格 xff0c python 中要么用存在的常规方法 xff0c 或者用正则处理 1 去掉左边空格 string 61 34 it is blank space test 34 prin

  • 20190226-LCD_GUI

    LCD GUI 这里需要先剃度填色 xff0c 然后再显示汉字 xff0c 最后在显示符号和数字 xff0c 否则会被覆盖 xff0c 显示不出来汉字或者数字符号

  • Arch安装

    从2021年4月起 xff0c Arch Linux安装镜像中已经包含了一个官方的简易安装程序archinstall 可以支持在连接网络后进行英文交互式安装 Arch Linux News Installation medium with

  • 存储过程懂不懂

    存储过程的官方定义是这么说的 xff1a 存储过程 xff08 Stored Procedure xff09 是一组为了完成特定功能的 SQL 语句集 xff0c 经编译后存储在数据库中 用户通过指定存储过程的名字并给出参数 xff08 如

  • ArchLinux的用户配置和KDE安装

    用户配置 建立用户 目标是新建一个普通用户 xff0c 这个普通用户可以使用sudo提权 以下默认使用username作为用户名 建立无密码用户并创立其默认用户组 useradd username 更改账户密码 passwd usernam

  • Zsh的简单配置

    Zsh 简体中文 ArchWiki archlinux org 本配置的目标是增加一些简单的功能以及一个能过得去的界面 安装 安装zsh xff08 本体 xff09 和zsh completions xff08 补全 xff09 两个包

  • Arch（KDE Plasma）中文化

    Localization 简体中文 Simplified Chinese 简体中文 ArchWiki 生成中文locale xff08 这一步在安装篇就有写 xff09 在 etc locale gen中取消中文的zh CN UTF 8 U

  • yay的安装与使用与Anbox的安装

    yay的安装 安装 首先安装所需软件包base devel和git pacman Syu base devel git 之后使用git clone下载代码 git clone URL FORM AUR 这里的 URL FROM AUR 指从

  • linux下利用C语言实现对文件的操作（创建、复制、修改权限、修改文件名）

    今天在ubuntu下编写一个了C程序实现如下功能 xff1a xff08 1 xff09 创建一个文本文件 xff0c 写入 Hello World xff01 xff08 2 xff09 获取该文件的所有权限 xff08 3 xff09

  • 设计模式案例分析与实现

    1 UML类图及Java实现 案例 xff1a 某基于C S的即时聊天系统登录模块功能描述如下 xff1a 用户通过登录界面 LoginForm 输入账号和密码 xff0c 系统将输入的账号和密码与存储在数据库 User 表中的用户信息进行

  • 决策树算法

    目录 1 概述 1 1 算法导入 1 2 决策树定义 1 3 决策树发展 1 4 结构 1 5 从树到规则 2 决策树的构建 2 1 基本原理 2 2 特征选择 2 3 实例分析 ID3 2 4 增益率 C4 5算法 2 5 基尼指数 CA

热门标签