当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

广东工业大学:《机器学习》课程教学资源(课件讲义)第7讲 集成学习(决策树)

资源类别:文库,文档格式:PDF,文档页数:74,文件大小:7.41MB,团购合买
点击下载完整版文档(PDF)

07决策树 周志华《机器学习》第四章 李航《统计机器学习》第五章

07 决策树 周志华《机器学习》第四章 李航《统计机器学习》第五章

大纲 口基本流程 口划分选择(特征选择 ▣剪枝处理 口连续与缺失值 口多变量决策树

大纲 p 基本流程 p 划分选择(特征选择) p 剪枝处理 p 连续与缺失值 p 多变量决策树

基本流程 决策树基于树结构来进行预测 色泽=? 青绿 根蒂=? 蜷缩 敲声=? 浊响 好瓜

基本流程 决策树基于树结构来进行预测 色泽=? 根蒂=? 敲声=? 好瓜 青绿 蜷缩 浊响 …... … …... … …... …

基本流程 ▣决策过程中提出的每个判定问题都是对某个属性的“测试” 口决策过程的最终结论对应了我们所希望的判定结果 口每个测试的结果或是导出最终结论,或者导出进一步的判定问题, 其考虑范围是在上次决策结果的限定范围之内 口从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵泛化能力强, 即处理未见示例能力强的决策树

基本流程 p 决策过程中提出的每个判定问题都是对某个属性的“测试” p 决策过程的最终结论对应了我们所希望的判定结果 p 每个测试的结果或是导出最终结论,或者导出进一步的判定问题, 其考虑范围是在上次决策结果的限定范围之内 p 从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵泛化能力强, 即处理未见示例能力强的决策树

基本流程 Algorithm1决策树学习基本算法 输入: ·训练集D={x1,1),,(xm,m)片; 。属性集A=(a1,,aa 过程:函数TreeGenerate(D,A) 1上:生成结点node: (1)当前结点包含的 2:ifD中样本全属于同一类别C then 样本全部属于同一类 3:将node标i记为C类叶结点:return 别 4:end if 5:ifA=0ORD中样本在A上取值相同thcn■ 6:将node标记叶结点,其类别标记为D中样本数最多的类:return (2)当前属性集为空, 7:end if 或所有样本在所有属 8:从A中选择最优划分属性a 性上取值相同 9:fora.的每一个值a:do 10:为node生成每一个分枝;令D,表示D中在a.上取值为a:的样本子集: 1:ifD,为空then 12: 将分枝结点标记为叶结点,其类别标记为D中样本最多的类:return (3)当前结点包含的 13:else 样本集合为空 14 以TreeGenerate(De,A-{a.)为分枝结点 15:end if 16:end for 输出:以node为根结点的一棵决策树

基本流程 (1)当前结点包含的 样本全部属于同一类 别 (2)当前属性集为空, 或所有样本在所有属 性上取值相同 (3)当前结点包含的 样本集合为空

大纲 口基本流程 口划分选择(特征选择) ▣剪枝处理 口连续与缺失值 口多变量决策树

大纲 p 基本流程 p 划分选择(特征选择) p 剪枝处理 p 连续与缺失值 p 多变量决策树

划分选择 口决策树学习的关键在于如何选择最优划分属性。一般而言,随着 划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可 能属于同一类别,即结点的"纯度”(purity)越来越高 口经典的属性划分方法: ·基尼指数(CART) ●信息增益(ID3) ● 增益率(C4.5)

划分选择 p 决策树学习的关键在于如何选择最优划分属性。一般而言,随着 划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可 能属于同一类别,即结点的“纯度”(purity)越来越高 p 经典的属性划分方法: l 基尼指数(CART) l 信息增益(ID3) l 增益率(C4.5)

划分选择与决策树的种类 决策树的假设 信息是可区分的 决策树的种类 ■按任务分:分类树(Classification tree)与回归树(Decision tree) ■按特征选择方法分:ID3决策树算法、C4.5决策树算法、CART决策树算法 时间 模型 任务 树 特征选择 基尼系数(Gini) 1984 CART 分类 二叉树 回归 平方误差(MSE) 1986 ID3 分类 多叉树 信息增益(Information Gain) 1993 C4.5 分类 多叉树 信息增益比(Information Gain Ratio) 知乎@刘启林

划分选择与决策树的种类 p 数据集 的纯度可用“基尼值”来度量 越小,数据集 的纯度越高 p 属性 的基尼指数定义为: p 应选择那个使划分后基尼指数最小的属性作为最优划分属性,即 p CART [Breiman et al., 1984]采用“基尼指数”来选择划分属性 反映了从 中随机抽 取两个样本,其类别 标记不一致的概率

划分选择-信息增益红D3 口“信息熵”是度量样本集合纯度最常用的一种指标,假定当前样 本集合D中第类样本所占的比例为P(K=1,2,,1门),则D的信 息熵定义为 10川 Ent(D)=- p&log2 PR k=1 Ent(D)的值越小,则D的纯度越高 ▣计算信息熵时约定:若p=0,则plog2p=0 口Ent(D)的最小值为0,最大值为log2Dy

划分选择-信息增益ID3 p “信息熵”是度量样本集合纯度最常用的一种指标,假定当前样 本集合 中第 类样本所占的比例为 ,则 的信 息熵定义为 的值越小,则 的纯度越高 p 计算信息熵时约定:若 ,则 p 的最小值为 ,最大值为

划分选择-信息增益缸D3 ▣离散属性a有V个可能的取值{a,a a'}.,用a来进行划分,.则 会产生V个分支结点,其中第个分支结点包含了D中所有在属性 上取值为a"的样本,记为D"。则可计算出用属性a对样本集D进行 划分所获得的“"信息增益”: Gain(D,a)=Ent(D)- Ent(D) 1 为分支结点权重,样本数越 多的分支结点的影响越大 一般而言,信息增益越大,则意味着使用属性α来进行划分所获 得的“纯度提升”越大 口ID3决策树学习算法[QuinIan,1986]以信息增益为准则来选择划分 属性

划分选择-信息增益ID3 p 离散属性 有 个可能的取值 ,用 来进行划分,则 会产生 个分支结点,其中第 个分支结点包含了 中所有在属性 上取值为 的样本,记为 。则可计算出用属性 对样本集 进行 划分所获得的“信息增益”: p 一般而言,信息增益越大,则意味着使用属性 来进行划分所获 得的“纯度提升”越大 p ID3决策树学习算法[Quinlan, 1986]以信息增益为准则来选择划分 属性 为分支结点权重,样本数越 多的分支结点的影响越大

点击下载完整版文档(PDF)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共74页,可试读20页,点击继续阅读 ↓↓
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有