版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第4章
决策树目录特征选择决策树生成算法CART决策树剪枝第一节第二节第三节第一节特征选择34.1特征选择
决策树构建的关键在于每次划分子树时,选择哪个属性特征进行划分。
信息论中,熵(entropy)用于描述随机变量分布的不确定性。对于离散型随机变量X,假设其取值有n个,分别是,用频率表示概率,随机变量的概率分布为则X的熵,也即概率分布
的熵定义为44.1特征选择5
若给定离散型随机变量,假设X和Y的取值个数分别为n和m,则其联合概率分布为其中N表示总样本数,表示且的样本数目。边缘概率分布为其中N表示总样本数,表示的样本数目。定义给定X的条件下Y的条件熵为4.1.1信息增益6
根据上面对熵及条件熵的介绍,就可以引入信息增益的概念。
信息增益是最早用于决策树模型的特征选择指标,也是ID3算法的核心。对于给定样本集合,设
为数据集中任一属性变量,其中
表示该属性的可能取值,使用属性进行数据集划分获得的信息增益定义为其中
表示属性取值为时的样本子集,为对应的样本数目,为中标签为的样本数目。4.1.2信息增益比7
信息增益比(Informationgainratio)定义为信息增益与数据集在属性
上的分布的熵
之比,即其中
如果一个属性的可取值数目较多,则使用信息增益进行特征选择时会获得更大的收益。用信息增益比进行特征选择则会在一定程度上缓解此问题。第二节决策树生成算法CART4.2决策树生成算法CART9
除ID3和C4.5算法外,CART是另外一种常用的决策树算法。CART算法的核心是使用了基尼指数作为特征选择指标,下面介绍基尼指数的定义。
给定数据集D,其中共有K个类别,用频率代替概率,数据集的概率分布为对于数据分布p或者数据集D,其基尼系数定义为4.2决策树生成算法CART10
可以看到,当样本均匀分布时,
的值最大,值反映的是样本集合的纯度,当样本均匀分布时,每个类别都包括数目相等的样本,此时纯度最低,值最大;当所有的样本都只属于一个类别时,其他类别包含的样本数目都为0,此时纯度最高,值为0.所以,样本集合的基尼值越低,集合的纯度越高。样本集合D关于属性
的基尼指数定义为CART用于分类决策树生成时,在特征选择阶段使用的就是基尼指数,对所有可用属性进行遍历,选择能够使样本集合划分后基尼指数最小的属性进行子树生成。4.2决策树生成算法CART11
与ID3和C4.5算法不同,CART决策树生成的是一棵二叉树。对任一离散属性
的任一可能取值,将样本集合 D按照和划分为和两个子集,然后按照如下公式计算基尼指数其中和分别表示和中的样本数目。
4.2决策树生成算法CART12
当属性
是连续变量时,按照一定的标准选择为连续变量选择合适的切分点a,将样本集合划分为和两个子集,然后按照如下公式计算基尼指数
其中和分别表示上小于a和大于a的样本子集的数目。遍历完所有属性即属性值后,选择能够使
或最小的属性值将当前样本集合划分到两棵子树中。第三节决策树剪枝4.3决策树剪枝14
由于决策树的强大建模能力,在训练集上生成的决策树容易产生过拟合的问题,需要对决策树进行剪枝以降低模型的复杂度,提高泛化能力。
剪枝分为预剪枝和后剪枝,预剪枝在构建决策树的过程进行,而后剪枝则在决策树构建完成之后进行。4.3.1预剪枝15
对决策树进行预剪枝时一般通过验证集进行辅助。每次选择信息增益最大的属性进行划分时,首先在验证集上对模型进行测试,如果划分之后能够提高验证集的准确率,则进行划分;否则,将当前节点作为叶节点,并以当前节点包含的样本中出现次数最多的样本作为当前节点的预测值。
由于决策树本身是一种贪心的策略,并不一定能够得到全局的最优解。使用预剪枝的策略容易造成决策树的欠拟合。4.3.2后剪枝16对于一棵树,其代价函数定义为经验损失和结构损失两个部分:经验损失是指模型是对模型性能的度量,结构损失是对模型复杂度的度量。
根据奥卡姆剃刀原则,决策树模型性能应尽可能的性能高,复杂度应可能的低。经验损失可以使用每个叶节点上的样本分布的熵之和来描述,结构损失可以用叶节点的个数来描述。4.3.2后剪枝17设决策树中T叶节点的数目为M,代价函数的形式化描述如下其中为第i个叶节点中样本的数目,为对应节点上的熵。自底向上剪枝的过程中,对所有子节点均为叶节点的子树,如果将某个子树进行剪枝后能够使得代价函数变小且在所有子树中最小,则将该子树剪去,然后重复这个剪枝过程直到代价函数不再变小为止。显然,剪枝后叶节点的数目
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 工作经验交流模板课件
- 工作角色转变课件
- 古筝介绍课件
- 工作纪律模板课件
- 《工程训练及劳动教育》课件全套 李小蕴 第1-14章 绪论、铸造成形 -综合创新训练
- 高职基础化学课件
- 地塞米松用药指南2026
- 骨折后栓塞课件
- 2026大学大四(机电一体化技术)机电一体化系统试题及答案
- 公众号放课件
- 北京2026年11月小学五年级数学期中试卷及答案
- 人教版八年级英语上册Unit1-Unit 8语法知识点+练习题(含答案)
- 《盘活存量土地和低效用地典型案例2026版》
- 医务人员手卫生规范(WS-T313-2019)
- 2026年特种设备安全管理人员(A证)考试练习题库(附答案)
- 2027年江苏省高职单招职业技能考试题库附完整答案详解(考点梳理)
- 减轻外周静脉补钾疼痛方法总结2026
- 2024年云南省选调公务员笔试真题汇编含答案解析(夺冠)
- 合并CKD的冠心病糖尿病患者血运重建方案
- 物业服务标准化培训课件
- 2024人教版八年级生物上册期末复习必考知识点提纲填空练习版(含答案)
评论
0/150
提交评论