决策树-程序员宅基地

技术标签: 机器学习  分类  

决策树(decision tree)是一种基本的分类与回归方法,此处主要讨论分类的决策树。

决策树学习的算法通常是一个递归地选择最优特征(选择方法的不同,对应着不同的算法),并根据该特征对训练数据进行分割,使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。下面为一个实例图:

在这里插入图片描述

构造流程:

1) 开始:构建根节点,将所有训练数据都放在根节点,选择一个最优特征,按着这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。

2) 如果这些子集已经能够被基本正确分类,那么构建叶节点,并将这些子集分到所对应的叶节点去。

3)如果还有子集不能够被正确的分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的节点,如果递归进行,直至所有训练数据子集被基本正确的分类,或者没有合适的特征为止。

4)每个子集都被分到叶节点上,即都有了明确的类,这样就生成了一颗决策树。

决策树的特点:

优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
缺点:可能会产生过度匹配的问题
适用数据类型:数值型和标称型

其中常用的分类树算法有ID3、C4.5、CART

下面是一些信息论的知识

l 信息熵(information entropy)

熵(entropy)是表示随机变量不确定性的度量,设X是一个取有限值的离散随机变量,其概率分布为:

在这里插入图片描述

则随机变量X的熵定义为:

在这里插入图片描述

熵越大,随机变量的不确定性越大;也就是H(X)越小,随机变量的X的纯度越高。

l 信息增益(information gain)

训练数据集D采用特征a进行划分之后的信息增益Gain(D,a)为:

在这里插入图片描述

其中

在这里插入图片描述

l 信息增益率(information gain
ratio)

特征a对训练数据集D的信息增益Gain_ratio(D,a)定义为其信息增益Gain(D,a)与训练数据集D关于特征a的值的熵IV(a)之比,即

在这里插入图片描述

其中

代表以属性a进行划分,第V类的子集数量。

l 基尼指数(Gini index)

基尼指数Gini(D)表示集合D不确定性,基尼指数Gini(D,a)表示集合D经A=a分割后的不确定性(类似于熵),基尼指数越小,样本的不确定性越小。分类问题中,假设有K个类,样本点属于第k类的概率为pk,则概率分布的基尼指数定义为

在这里插入图片描述

显然,Gini反映了在样本中随机抽取两个样本,其标记不一样的概率,因此基尼指数越小,数据集D的纯度越高。也就是说选择使得划分后基尼指数最小的属性作为最有划分属性。例如对于属性a,其基尼指数为:

在这里插入图片描述

下面分别阐述ID3、C4.5、CART算法

  1. ID3算法(基于信息增益作为属性选择的度量)
    基本思想:对于含有多个特征和类别标签的的数据集,利用信息增益作为选取特征的指标,进而选取出划分数据集最好的特征。
    算法流程在这里不做阐述。
    缺点:
    ID3算法只有树的生成, 所以该算法生成的树容易产生过拟合;
    ID3算法本身并未给出处理连续数据的方法;
    ID3算法不能处理带有缺失值的数据集, 故在算法挖掘之前需要对数据集中的缺失值进行预理;
    使用ID3算法构建决策树时, 若出现各属性值取值数分布偏差大的情况, 分类精度会大打折扣。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

剪枝处理:剪枝是决策树学习算法对付"过拟合"的主要手段。

过拟合原因:

1)噪声导致的过拟合:拟合了被误标记的样例,导致误分类。

2)缺乏代表性样本导致的过拟合:缺乏代表性样本的少量训练集作出的决策会出现过拟合。

3)多重比较造成的过拟合:复杂模型。

基本策略有"预剪枝" 和"后剪枝";

预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点;

后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。

判断决策树泛化性能是否提升:留出法,即预留一部分数据用作"验证集"以进行性能评估。

例如:在预剪枝中,对于每一个分裂节点,对比分裂前后决策树在验证集上的预测精度,从而决定是否分裂该节点。而在后剪枝中,考察非叶节点,对比剪枝前后决策树在验证集上的预测精度,从而决定是否对其剪枝。

两种方法对比:

1)预剪枝使得决策树的很多分支都没有"展开”,不仅降低过拟合风险,而且显著减少训练/测试时间开销;但,有些分支的当前划分虽不能提升泛化性能,但在其基础上进行的后续划分却有可能导致性能显著提高,即预剪枝基于"贪心"本质禁止这些分支展开,给预剪枝决策树带来了欠拟含的风险。

2)后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下,后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树,但后剪枝过程是在生成完全决策树之后进行的,并且要自底向上地对树中的所有非叶结点进行逐一考察,因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

对于剪枝内容补充,博客网址:https://blog.csdn.net/xo3ylAF9kGs/article/details/78623265

对于回归树以后再进行补充。

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

智能推荐

C/C++软件工程师就业求职手册学习笔记---第十二章_c/c++软件工程师就业求职手册 .pdf-程序员宅基地

文章浏览阅读814次。第十二章泛型编程templateT max(Ta,T b){ return a>b?a:b;}max(1,2.0);函数模板重点是模板,是用来产生函数的模板。模板函数重点是函数,他是一个由模板生成的函数。类模板用于产生类,如Point_T就是类模板,模板类就是由模板生成的类。 函数模板和类模板区别:函数模板可以不用声明指定类型,编译器可以_c/c++软件工程师就业求职手册 .pdf

collections.sort()对中文进行排序(转)按拼音顺序-程序员宅基地

文章浏览阅读962次。http://hi.baidu.com/xigua366/blog/item/0007d20a3664978d0a7b82e0.html Collator collatorChina = Collator.getInstance(java.util.Locale.CHINA); // 用于将中文按拼音排序_collections.sort 按汉字拼音

Can't create handler inside thread that has not called Looper.prepare()_can't create handler inside thread thread[thread-6-程序员宅基地

文章浏览阅读312次。下面是转载一哥们的博客,之所以转载他的是因为 他的解决问题的 方式挺好,层层递进,步步追溯!转载:https://www.jianshu.com/p/86459c23bdf5Crach描述:在子线程中 调用了这句:Toast.makeText(this, "", Toast.LENGTH_LONG) .show();然后就崩溃了:java.lang.Runtime..._can't create handler inside thread thread[thread-6,5,main] that has not call

Android apk 安全措施详细说明(签名、混淆、加固、H5安全方案)_apk安全-程序员宅基地

文章浏览阅读5.6k次。文章简介:当一个Android app 开发完成后,我们总是希望对app进行一些安全措施,防止自己开发的apk被别人二次打包和签名上传到应用市场,同时防止apk被别人拿到之后进行反编译进行二次开发。那么我们应该都做哪些防护措施呢?下面来一一说明。1、apk签名打正式包之前,需要对apk进行签名,如果您是用Android Studio开发工具,那么打包、签名就非常简单了。具体怎么签名,网上文章很多,这里不做详细描述。那么我们重点说说为什么要对apk进行签名呢?(1)apk签名是应用程序作者对apk进行_apk安全

进阶《Python高性能编程》中文PDF+英文PDF+源代码-程序员宅基地

文章浏览阅读799次。入门使用高性能 Python,建议参考《Python高性能编程》,例子给的很多,讲到高性能就会提到性能监控,里面有cpu mem 方法的度量,网络讲了一点异步,net profiler 没讲。笔记集合把可能把工作中遇到的性能问题,记录了解决方案。性能分析对于高性能编程的作用,就好比复杂度分析对于算法的作用,它本身不是高性能编程的一部分,但却是最终有效的一种评判标准。学习参考:《Python高..._《python高性能编程》百度网盘

如何实时修改网页的javascript代码_js"+"临时修改"+"代码-程序员宅基地

文章浏览阅读2.9w次,点赞38次,收藏120次。最近在做upload-labs需要修改网页的js代码,貌似比较复杂,记录留念一下。首先我们打开开发人员工具做修改,试图在element编辑框内修改代码,把上传的文件改为允许php,然而修改的代码并不会生效,因为chrome已经在内存里加载了这段代码,要重新加载代码只能靠刷新,然而刷新会丢失我们所作的修改,那么应该怎么做呢?其实很简单,首先需要在source-overrides界面里面select folder for overrides,然后选择一个文件夹。我随便选了一个文件夹,就有权限访问的_js"+"临时修改"+"代码

随便推点

C#: 线程间操作无效: 从不是创建控件“dataGridView”的线程访问它-程序员宅基地

文章浏览阅读1.7k次。最近在修改自动化小工具,用多线程来解决后台拷贝导致WinForm界面卡死的情况,但是遇到过错:线程间操作无效: 从不是创建控件“dataGridView”的线程访问它。这是因为在多线程程序中,新创建的线程不能访问UI线程创建的窗口控件,如果需要访问窗口中的控件,有2种解决方法:1. 在Form_Load中添加://取消跨线程检查Control.CheckForIl..._线程间操作无效: 从不是创建控件“datagridview4”的线程访问它。

SpringBoot注解之@Transactional(事务控制)_spring boot @trasaaction-程序员宅基地

文章浏览阅读559次。@Transactional-----------------------------------------------------------------------------------------------------------------------------通过AOP,在方法执行时控制事务事务基本要素原子性(Atomicity): 事务开始后所有操作,要么全部做完,..._spring boot @trasaaction

LeetCodeOJ:2. Add Two Numbers-程序员宅基地

文章浏览阅读320次。Total Accepted: 129010 Total Submissions: 572407 Difficulty: MediumYou are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of

java定时任务实现的几种方式_java 接口定时任务并进行业务编写-程序员宅基地

文章浏览阅读3k次。在开发测试工具的应用后台,经常听到同事说要做个定时任务把做日志处理,或者数据清理,包括做些复杂的业务计算逻辑,在选择定时任务的时候,怎么能够快速实现,并且选择一种更适合自己的方式呢? 我这里把定时任务的实现收集整理了一些方法,希望可以帮到刚开始做定时任务的同学,写得不对的地方请指正。一 Java 基本的定时任务,总结方法有三种: 1.1 创建一个thread_java 接口定时任务并进行业务编写

ElasticSearch快速入门-程序员宅基地

文章浏览阅读118次。安装包下载1)Elasticsearch官网: https://www.elastic.co/products/elasticsearch单节点Linux环境安装1、解压elasticsearch-5.2.2.tar.gz到/opt/module目录下tar -zxvf elasticsearch-5.2.2.tar.gz -C /opt/module/2、在/opt/module/elasticsearch-5.2.2路径下创建data和logs文件夹3、修改配置文件/o..

三坐标基础概念认知_三坐标体系-程序员宅基地

文章浏览阅读1.4k次。1.三坐标测量系统组成坐标测量系统主要由机床本体、测头系统、电气系统以及软件系统四大部分组成。2.机床本体知识掌握一、机械结构认知其他硬件了解拓展知识·气浮块工作示意图电气系统知识掌握测量机控制柜面板认知测头系统知识掌握一、测头系统组成一般来说,测头系统基本是由测座、测力模块、测针三部分组成。当然,有些多功能测头和部分高端的测头还配置其他相关测量配件及相关连接件。二、测头工作原理机械式测头一般都包含有3个电子接触器,当测杆接触物体使测杆偏斜时,至少有一个接触器断开,此时_三坐标体系

推荐文章

热门文章

相关标签