第四章:决策树
第四章：决策树
大纲 口基本流程 口划分选择 口剪枝处理 口连续与缺失值 多变量决策树
大纲 基本流程 划分选择 剪枝处理 连续与缺失值 多变量决策树
基本流程 决策树基于树结构来进行预测 色泽=? 青绿 根蒂= 蜷缩 敲声 浊响 好瓜
基本流程 决策树基于树结构来进行预测 色泽=? 根蒂=? 敲声=? 好瓜 青绿 蜷缩 浊响 …... … …... … …... …
基本流程 口决策过程中提出的每个判定问题都是对某个属性的“测试” 口决策过程的最终结论对应了我们所希望的判定结果 口每个测试的结果或是导出最终结论,或者导出进一步的判定问题, 其考虑范围是在上次决策结果的限定范围之内 口从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵泛化能力强, 即处理未见示例能力强的决策树
基本流程 决策过程中提出的每个判定问题都是对某个属性的“测试” 决策过程的最终结论对应了我们所希望的判定结果 每个测试的结果或是导出最终结论，或者导出进一步的判定问题， 其考虑范围是在上次决策结果的限定范围之内 从根结点到每个叶结点的路径对应了一个判定测试序列 决策树学习的目的是为了产生一棵泛化能力强， 即处理未见示例能力强的决策树
基本流程 Algorithn1决策树学习基本算法 输入: 训练集D={(x1,v1),…,(xm,ym)} 属性集A={a1,…,a} 过程:函数 TreeGenerate(D,A) 1:生成结点node (1)当前结点包含的 2:ifD中样本全属于同一类别 C then 样本全部属于同一类 3将mode标记为C类叶结点; return 别 5:ifA=0ORD中样本在A上取值相同then 6将node标记叶结点,其类别标记为D中样本数最多的类 return (2)当前属性集为空, 7: end if 或所有样本在所有属 8:从A中选择最优划分属性an; 性上取值相同 9:fora,的每一个值ado 10:为node生成每一个分枝;令D,表示D中在a,上取值为a"的样本子集; 11ifD,为空then 12将分枝结点标记为叶结点,其类别标记为D中样本最多的类: return 3)当前结点包含的 13. else 样本集合为空 14:以 TreeGeneratel(D,A-{a})为分枝结点 15: end if 16: end for 输出:以node为根结点的一棵决策树
基本流程 （1）当前结点包含的 样本全部属于同一类 别 （2）当前属性集为空， 或所有样本在所有属 性上取值相同 （3）当前结点包含的 样本集合为空
大纲 口基本流程 口划分选择 口剪枝处理 口连续与缺失值 多变量决策树
大纲 基本流程 划分选择 剪枝处理 连续与缺失值 多变量决策树
划分选择 口决策树学习的关键在于如何选择最优划分属性。一般而言,随着 划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可 能属于同一类别,即结点的“纯度”( purity)越来越高 口经典的属性划分方法: ●信息增益 增益率 基尼指数
划分选择 决策树学习的关键在于如何选择最优划分属性。一般而言，随着 划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可 能属于同一类别，即结点的“纯度”(purity)越来越高 经典的属性划分方法： ⚫ 信息增益 ⚫ 增益率 ⚫ 基尼指数
划分选择-信息增益 口“信息熵”是度量样本集合纯度最常用的一种指标,假定当前样 本集合D中第k类样本所占的比例为Pk(K=1,2,…,y),则的信 息熵定义为 Ent(D ∑ pk 10g2 pk Ent(D)的值越小,则D的纯度越高 口计算信息熵时约定:若p=0,则plog2p=0 口En(D)的最小值为0,最大值为og2
划分选择-信息增益 “信息熵”是度量样本集合纯度最常用的一种指标，假定当前样 本集合 中第 类样本所占的比例为 ，则 的信 息熵定义为 的值越小，则 的纯度越高 计算信息熵时约定：若 ，则 的最小值为 ，最大值为
划分选择-信息增益 口离散属性Q有V个可能的取值{al,a2,…,aY},用来进行划分,则 会产生V个分支结点,其中第0个分支结点包含了D中所有在属性a 上取值为α的样本,记为D°。则可计算出用属性对样本集进行 划分所获得的“信息增益” Gain(D,a)=Et(D)-∑ D Ent(d 为分支结点权重,样本数越 多的分支结点的影响越大 口一般而言,信息增益越大,则意味着使用属性α来进行划分所获 得的“纯度提升”越大 口ID3决策树学习算法[ Quinlan,1986]以信息增益为准则来选择划分 属性
划分选择-信息增益 离散属性 有 个可能的取值 ，用 来进行划分，则 会产生 个分支结点，其中第 个分支结点包含了 中所有在属性 上取值为 的样本，记为 。则可计算出用属性 对样本集 进行 划分所获得的“信息增益”： 一般而言，信息增益越大，则意味着使用属性 来进行划分所获 得的“纯度提升”越大 ID3决策树学习算法[Quinlan, 1986]以信息增益为准则来选择划分 属性 为分支结点权重，样本数越 多的分支结点的影响越大
划分选择-信息增益 信息增益实例 编号色泽根蒂敲声纹理脐部触感好瓜 青 缩浊响清晰凹陷硬滑 12345 黑蜷缩沉闷清晰凹陷硬滑 乌黑蜷缩浊响清晰凹陷硬滑 青绿蜷缩沉闷清晰凹陷硬滑 是是是 浅白蜷缩浊响清晰凹陷硬滑是 6青绿稍蜷浊响清晰稍凹软粘是 乌黑稍蜷浊响稍糊稍凹软粘是 8乌黑稍蜷浊响清晰稍凹硬滑 是—该数据集包含17 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 青绿使提清脆清断平坦软训练样本,y=2, 12浅白蜷缩浊响模糊平坦软粘其中正例占p1=n 13青绿稍蜷浊响稍糊凹陷硬滑 14浅白稍蜷沉闷稍糊凹陷硬滑 反例占P2=,计 164蜡浊i断魏精算得到根结点的信 17利滑怠熵为 2 Ent(D)=∑ Pr 10g2 Pk 1710g215+21og21)=0.998
划分选择-信息增益 信息增益实例 …... … …... … 该数据集包含 个 训练样本， ， 其中正例占 ， 反例占 ，计 算得到根结点的信 息熵为