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]以信息增益为准则来选择划分 属性 为分支结点权重，样本数越 多的分支结点的影响越大