版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、机器学习机器学习周志华第4章 决策树第5章 神经网络和深度学习第6章 支持向量机第8章 集成学习第9章 聚类关联规则学习第第4章章 决策树决策树根据训练数据是否拥有标记信息学习任务决策树决策树(decision tree)模型常常用来解决分类和回归问题。常见的算法包括 CART (Classification And Regression Tree)、ID3、C4.5等。半监督学习:输入数据部分被标识,部分没有被标识,介于监督学习与非监督学习之间。分类、回归聚类( ,)iix y监督学习(supervised learning)无监督学习(unsupervised learning)半监督学习
2、(semi-supervised learning)强化学习(reinforcement learning)二分类学习任务属性属性值 根结点:包含全部样本 叶结点:对应决策结果 “好瓜” “坏瓜” 内部结点:对应属性测试决策树学习的目的:为了产生一颗泛化能力强的决策树,即处理未见示例能力强。无需划分无法划分不能划分无需划分无法划分不能划分Hunt算法:1,2,3,4,5,6,8,10,151,2,3,4,56,8,151068,15815第(2)种情形:设定为该结点所含样本最多的类别利用当前结点的后验分布第(3)种情形:设定为其父结点所含样本最多的类别把父结点的样本分布作为当前结点的先验分布决
3、策树学习的关键是算法的第8行:选择最优划分属性什么样的划分属性是最优的?我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”越来越高,可以高效地从根结点到达叶结点,得到决策结果。三种度量结点“纯度”的指标:1. 信息增益2. 增益率3. 基尼指数1. 信息增益信息增益香农提出了“信息熵”的概念,解决了对信息的量化度量问题。香农用“信息熵”的概念来描述信源的不确定性。信息熵信息熵对于二分类任务2y 一个事件的信息量信息量就是这个事件发生的概率的负对数。信息熵信息熵是跟所有事件的可能性有关的,是平均而言发生一个事件得到的信息量大小。所以信息熵其实是信息量的期望。假设我们已经知道
4、衡量不确定性大小的这个量已经存在了,不妨就叫做“信息量信息量”不会是负数不确定性函数是概率的单调递减函数;可加性:两个独立符号所产生的不确定性应等于各自不确定性之和,即同时满足这三个条件的函数是负的对数函数,即fp1212()()()f ppf pf pf1()loglogiiif ppp 1 loglogniiiiEppp 信息增益信息增益一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”越大。决策树算法第8行选择属性著名的ID3决策树算法举例:求解划分根结点的最优划分属性根结点的信息熵:以属性“色泽”为例计算其信息增益1817p 2917p 数据集包含17个训练样例:
5、8个正例(好瓜)占9个反例(坏瓜)占对于二分类任务2y 用“色泽”将根结点划分后获得3个分支结点的信息熵分别为:属性“色泽”的信息增益为:若把“编号”也作为一个候选划分属性,则属性“编号”的信息增益为:根结点的信息熵仍为:()0.998Ent D 用“编号”将根结点划分后获得17个分支结点的信息熵均为:117221100()()( loglog)01111Ent DEnt D 则“编号”的信息增益为:1711( ,)()()0.99817vvGain DEnt DEnt D编号远大于其他候选属性信息增益准则对可取值数目较多的属性有所偏好2. 增益率增益率增益率准则对可取值数目较少的属性有所偏好
6、著名的C4.5决策树算法综合了信息增益准则信息增益准则和信息率准则信息率准则的特点:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。3. 基尼指数基尼指数基尼值基尼值基尼指数基尼指数著名的CART决策树算法 过拟合过拟合:学习器学习能力过于强大,把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质,导致泛化性能下降。 欠拟合欠拟合:学习器学习能力低下,对训练样本的一般性质尚未学好。过拟合无法彻底避免,只能做到“缓解”。剪枝,即通过主动去掉一些分支来降低过拟合的风险。预剪枝预剪枝决策树的剪枝策略后剪枝后剪枝预剪枝预剪枝:在决策树生成过程中,对每个结点在划分前先进
7、行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点后剪枝后剪枝:先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。留出法:将数据集D划分为两个互斥的集合:训练集S和测试集TDSTST 且预剪枝预剪枝1,2,3,14训练集训练集:好瓜好瓜 坏瓜坏瓜1,2,3,6,7,10,14,15,16,176,7,15,1710,16精度:正确分类的样本占所有样本的比例4,5,13(T,T,F)8,9(T,F)11,12(T,T)验证集验证集:4,5,8,9,11,12,13
8、3=75=7不足不足:基于“贪心”本质禁止某些分支展开,带来了欠拟合的风险预剪枝使得决策树的很多分支都没有“展开”优点优点:降低过拟合的风险减少了训练时间开销和测试时间开销后剪枝后剪枝先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。验证集验证集:4,5,8,9,11,124,13(T,F)5(F)9(F)8(F)11,12(T,T)验证集精度:37考察结点顺序:6,7,15,176,7,151767,157158,9(T,F)减去结点验证集变为:47训练集训练集:好瓜好瓜 坏瓜坏瓜1,2,3,6
9、,7,10,14,15,16,17后剪枝后剪枝决策树预剪枝预剪枝决策树保留了更多的分支欠拟合风险很小泛化能力优于预剪枝决策树训练时间开销比未减枝和预剪枝决策树大得多1.生产完全决策树2.所有非叶节点逐一考察知识回顾:知识回顾:1. 四类学习任务2. Hunt算法3种递归返回情形、第8行3. 3种度量结点“纯度”的指标: 信息增益 ID3 增益率C4.5 基尼指数 CART1. 过拟合、欠拟合2. 决策树剪枝 预剪枝 后剪枝离散属性:脐部 根蒂 色泽连续属性:密度 含糖率连续属性离散化技术:二分法C4.5决策树算法样本集连续属性,有n个不同的取值,将n个取值从小到大排序:划分点t(数值)(数值)
10、将划分为两个子集和12,.,na aaDaDtDtD121,.,.,iina aa aatDtDtt显然,对相邻的属性取值来说,t在区间中取任意值所产生的划分结果都相同ia1ia1,iia a根结点的信息熵仍为:()0.998Ent D 220044()( loglog)04444tEnt D +228855()(loglog)0.96113131313tEnt D ( ,)413()()()17170.263ttGain DEnt DEnt DEnt D密度,0.381根结点包含17个训练样本,密度有17个不同取值候选划分点集合包含16个候选值每一个划分点能得到一个对应的信息增益密度密度好瓜
11、好瓜0.243否0.245否0.343否0.360否0.403是10.437是20.481是30.556是40.593否0.680是50.634是60.639否0.657否0.666否0.697是70.719否0.774是80.381t tDtD选择“纹理”作为根结点划分属性与离散属性不同,若当前结点划分属性为连续属性,该连续属性还可被再次选作后代结点的最优划分属性。现实任务中,尤其在属性数目较多时,存在大量样本出现缺失值。出于成本和隐私的考虑1.属性值缺失时,如何进行划分属性选择?(如何计算信息增益)2.给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?(对于缺失属性值的样本如何将
12、它从父结点划分到子结点中):D训练集:D训练集中在属性a上没有缺失值的样本子集:vD被属性a划分后的样本子集D:kDD中属于第k类的样本子集无缺失值样本中在属性上取值的样本所占比例:无缺失值样本所占比例:kp 无缺失值样本中第k类所占比例:vr vaa无缺失值的样本子集上的信息增益D对于问题2:对于有缺失值的样本如何将它从父结点划分到子结点中若样本在划分属性a上的取值已知,则将划入与其取值对与其取值对应的子结点应的子结点,且样本权值在子结点中保持为若样本在划分属性a上的取值未知,则将同时划入所有子所有子结点结点,且样本权值在子结点中调整为,就是让同一个样本以不同的概率划入不同的子结点中。xxx
13、wvxr wxxxw其中,是为每个样本赋予的一个权重x运用运用:问题1属性值缺失时,如何进行划分属性选择?=属性值缺失时,如何计算缺失属性的信息增益?:vr 无缺失值样本中在属性上取值的样本所占比例vaa:kp 无缺失值样本中第k类所占比例根结点包含样本集中全部17个样本属性“色泽”无缺失值的样例子集包含14个样例:D=2,3,4,6,7,8,9,10,11,12,14,15,16,17D好瓜好瓜(6个)坏瓜坏瓜(8个)1417无缺失值样本所占比例:vr 无缺失值样本中在属性上取值的样本所占比例vaa:无缺失值样本所占比例“纹理”被用于对根结点进行划分问题2给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?样本划分原则:属性值已知,划入与其取值对应的子结点,样本权值不变,仍为属性值未知,划入所有子结点,样本权值调整为,让同一个样本以不同的概率划入不同的子结点中xwvxr w:vr 无缺失值样本中在属性上取值的样本所占比例vaa753,15 15 15“纹理”属性值缺失的样本编号为:8,10权值为:8和10同时进入三个分支中,权值分别为: 8 ,1 0D= 1xw0.3810.205每个属性d个属性描述的样本对样本分类坐标空间中的一个坐标轴d维空间中的一个数据点
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 越汇乌鸡卷持续改善
- 十五五智能传感与控制装备:数据要素资产化与合规挑战
- 万亿蓝海掘金 工业互联网平赛道 2026年广州市工业互联网平台内部创业孵化运营方案
- 双碳约束下智能卧推架:绿色制造与ESG合规新机遇
- 小镇青年崛起智能便携按摩器下沉市场消费行为变迁图谱解析
- 2025年初级护士资格证模拟试题库解析版权威答案汇编
- 湖北荆州中学2026-2027学年高一上学期期中考试生物试卷
- 商贸公司制度汇编
- 2026年医疗健康行业报告:ToB客户开发与关系维护策略研究
- 2026年养老产业市场分析报告及商业模式创新
- 2026年山东第一医科大学附属职业病医院(山东省职业病医院)公开招聘人员笔试模拟试题及答案解析
- 2026年软件工程师系统架构设计考核试题及答案
- 2026新材料测试评价分析及标准体系建设研究报告
- 4.1 《观察的范围》教案 2026-2027学年四年级上册数学北师大版
- 2026年高考数学命题特征分析及2027届高三复习备考策略讲座
- 2026年秋季道德与法治五年级上知识点
- 美国白宫 科学:一个新的黄金时代 致总统的报告
- 2026年全国卷新高考英语语法易错题卷(含解析)
- 2025中核集团原子能院校园招聘笔试参考题库附答案
- 《下尿路感染》课件
- 跟腱断裂术后康复护理
评论
0/150
提交评论