认真的聊一聊决策树和随机森林

简介: 认真的聊一聊决策树和随机森林

随机森林是一种简单又实用的机器学习集成算法。


“随机“表示2种随机性,即每棵树的训练样本、训练特征随机选取。


多棵决策树组成了一片“森林”,计算时由每棵树投票或取均值的方式来决定最终结果,体现了三个臭皮匠顶个诸葛亮的中国传统民间智慧。


那我们该如何理解决策树和这种集成思想呢?


01 决策树



以分类任务为代表的决策树模型,是一种对样本特征构建不同分支的树形结构。

决策树由节点和有向边组成,其中节点包括内部节点(圆)和叶节点(方框)。内部节点表示一个特征或属性,叶节点表示一个具体类别。


微信图片_20220524134850.png


预测时,从最顶端的根节点开始向下搜索,直到某一个叶子节点结束。下图的红线代表了一条搜索路线,决策树最终输出类别C。


微信图片_20220524134903.png


决策树的特征选择


假如有为青年张三想创业,但是摸摸口袋空空如也,只好去银行贷款。


银行会综合考量多个因素来决定张三是不是一个骗子,是否给他放贷。例如,可以考虑的因素有性别、年龄、工作、是否有房、信用情况、婚姻状况等等。


这么多因素,哪些是重要的呢?

这就是特征选择的工作。特征选择可以判别出哪些特征最具有区分力度(例如“信用情况”),哪些特征可以忽略(例如“性别”)。特征选择是构造决策树的理论依据

不同的特征选择,生成了不同的决策树。


微信图片_20220524134917.png


决策树的特征选择一般有3种量化方法:信息增益、信息增益率、基尼指数


信息增益


在信息论中,熵表示随机变量不确定性的度量。假设随机变量X有有限个取值,取值  对应的概率为  ,则X的熵定义为:

QQ图片20220524135104.png

  

如果某件事一定发生(太阳东升西落)或一定不发生(钓鱼岛是日本的),则概率为1或0,对应的熵均为0

如果某件事可能发生可能不发生(天要下雨,娘要嫁人),概率介于0到1之间,熵大于0。

由此可见,熵越大,随机性越大,结果越不确定

我们再来看一看条件熵  ,表示引入随机变量Y对于消除X不确定性的程度假如X、Y相互独立,则X的条件熵和熵有相同的值;否则条件熵一定小于熵。

明确了这两个概念,理解信息增益就比较方便了。现在我们有一份数据集D(例如贷款信息登记表)和特征A(例如年龄),则A的信息增益就是D本身的熵与特征A给定条件下D的条件熵之差,即:


QQ图片20220524135115.png

 

数据集D的熵是一个常量。信息增益越大,表示条件熵  越小,A消除D的不确定性的功劳越大。


所以要优先选择信息增益大的特征,它们具有更强的分类能力。由此生成决策树,称为ID3算法


信息增益率


当某个特征具有多种候选值时,信息增益容易偏大,造成误差。引入信息增益率可以校正这一问题。


信息增益率  信息增益与D的熵之比:

QQ图片20220524135120.png

 

同样,我们优先选择信息增益率最大的特征,由此生成决策树,称为C4.5算法


基尼指数


基尼指数是另一种衡量不确定性的指标。


假设数据集D有K个类,样本属于第K类的概率为  ,则D的基尼指数定义为:

QQ图片20220524135123.png

 

其中  ,  是D中属于第k类的样本子集。

如果数据集D根据特征A是否取某一可能值a被分割成  和  两部分,则在给定特征A的条件下,D的基尼指数为:

QQ图片20220524135127.png

 

容易证明基尼指数越大,样本的不确定性也越大,特征A的区分度越差。

我们优先选择基尼指数最小的特征,由此生成决策树,称为CART算法


决策树剪枝


决策树生成算法递归产生一棵决策树,直到结束划分。什么时候结束呢?


  • 本属于同一种类型
  • 没有特征可以分割


这样得到的决策树往往对训练数据分类非常精准,但是对于未知数据表现比较差。

原因在于基于训练集构造的决策树过于复杂,产生过拟合。所以需要对决策树简化,砍掉多余的分支,提高泛化能力。


决策树剪枝一般有两种方法:


  • 预剪枝:在树的生成过程中剪枝。基于贪心策略,可能造成局部最优
  • 后剪枝等树全部生成后剪枝。运算量较大,但是比较精


决策树剪枝往往通过极小化决策树整体的损失函数实现


微信图片_20220524135259.png


假设树T有|T|个叶子节点,某一个叶子节点t上有  个样本,其中k类的样本有  个,

 为叶子节点t的熵,  是参数,则决策树的损失函数定义为:

QQ图片20220524135408.png  

其中熵为:

QQ图片20220524135412.png

 

损失函数第一项为训练误差,第二项为模型复杂度,用参数  来衡量二者的比重。


CART算法


CART表示分类回归决策树,同样由特征选择、树的生成及剪枝组成,可以处理分类和回归任务。


相比之下,ID3和C4.5算法只能处理分类任务


CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,依次递归地二分每个特征。


CART 对回归树采用平方误差最小化准则,对分类树用基尼指数最小化准则


02 bagging集成



机器学习算法中有两类典型的集成思想:bagging和bossting。


bagging是一种在原始数据集上,通过有放回抽样分别选出k个新数据集,来训练分类器的集成算法。分类器之间没有依赖关系。


随机森林属于bagging算法。通过组合多个弱分类器,集思广益,使得整体模型具有较高的精确度和泛化性能


03 随机森林



我们将使用CART决策树作为弱学习器的bagging方法称为随机森林


微信图片_20220524135327.jpg


由于随机性,随机森林对于降低模型方差效果显著。故随机森林一般不需要额外剪枝,就能取得较好的泛化性能。


相对而言,模型对于训练集的拟合程度就会差一些,相比于基于boosting的GBDT模型,偏差会大一些。


另外,随机森林中的树一般会比较深,以尽可能地降低偏差;而GBDT树的深度会比较浅,通过减少模型复杂度来降低方差(面试考点)

最后,我们总结一下随机森林都有哪些优点:

  • 采用了集成算法,精度优于大多数单模型算法
  • 在测试集上表现良好,两个随机性的引入降低了过拟合风险
  • 树的组合可以让随机森林处理非线性数据
  • 训练过程中能检测特征重要性,是常见的特征筛选方法
  • 每棵树可以同时生成,并行效率高,训练速度快
  • 可以自动处理缺省值
相关文章
|
存储 开发工具 异构计算
第三章 硬件描述语言verilog(二) 功能描述-组合逻辑(下)
第三章 硬件描述语言verilog(二) 功能描述-组合逻辑
1356 0
第三章 硬件描述语言verilog(二) 功能描述-组合逻辑(下)
|
Python
python、十六进制的颜色对照表
英文代码  形像颜色  HEX格式  RGB格式 LightPink 浅粉色 #FFB6C1 255,182,193 Pink 粉红 #FFC0CB 255,192,203 Crimson 猩红 #DC143C 220,20,60 LavenderBlush 脸红的淡紫色 #FFF0F5 255.
7791 0
python、十六进制的颜色对照表
|
数据采集 运维 算法
大数据项目管理:从需求分析到成果交付的全流程指南
【4月更文挑战第9天】本文介绍了大数据项目从需求分析到成果交付的全过程,包括需求收集与梳理、可行性分析、项目规划、数据准备与处理、系统开发与集成,以及成果交付与运维。文中通过实例展示了如何进行数据源接入、数据仓库建设、系统设计、算法开发,同时强调了需求理解、知识转移、系统运维的重要性。此外,还提供了Python和SQL代码片段,以说明具体技术实现。在大数据项目管理中,需结合业务和技术,灵活运用这些方法,确保项目的成功执行和价值实现。
2779 1
|
7月前
|
Linux C# Android开发
分享3款开源、免费的Avalonia UI控件库
分享3款开源、免费的Avalonia UI控件库
774 0
|
Kubernetes Nacos 开发者
Nacos 官网重大升级,提供官方发行版下载包,3.0 里程碑版本新特性预告
Nacos 官网重大升级,提供官方发行版下载包,3.0 里程碑版本新特性预告
1530 50
|
Web App开发 IDE 测试技术
深入理解自动化测试框架:以Selenium为例
【5月更文挑战第25天】 在软件开发的快速迭代中,自动化测试成为确保产品质量和缩短发布周期的重要环节。本文将深入剖析自动化测试框架Selenium,探讨其架构、运作机制以及在实际项目中的关键应用。通过对Selenium的系统梳理,旨在为软件测试工程师提供实战指导,帮助他们构建更高效、稳定的自动化测试环境。
105 8
|
11月前
|
人工智能 供应链 监控
数字供应链中的10个顶级成功案例
数字供应链中的10个顶级成功案例
|
机器学习/深度学习 数据采集 人工智能
【机器学习】集成学习(Bagging)——随机森林(RandomForest)(理论+图解+公式推导)
【机器学习】集成学习(Bagging)——随机森林(RandomForest)(理论+图解+公式推导)
1243 0
【机器学习】集成学习(Bagging)——随机森林(RandomForest)(理论+图解+公式推导)
|
JSON 前端开发 安全
Web前端开发中的跨域问题及解决方案
【2月更文挑战第8天】在Web前端开发中,跨域是一个常见且具有挑战性的问题。本文将深入探讨跨域产生的原因、影响以及多种解决方案,帮助开发者更好地理解和解决跨域问题。
|
机器学习/深度学习 安全 数据安全/隐私保护
「隐语小课」LDP和CDP在联邦学习中对于隐私性以及鲁棒性的作用
「隐语小课」LDP和CDP在联邦学习中对于隐私性以及鲁棒性的作用
546 0

热门文章

最新文章