文档介绍：决策树课件
*
第1页，此课件共60页哦
主要内容
决策树算法概述
从学****角度看，决策树属有指导学****算法
目标：用于分类和回归
分类回归树及应用
CHAID算法及应用
QUEST算法及应用
模型的对比分析7页，此课件共60页哦
：信息增益
已知信号U的概率分布P(U)且收到信号V=vj，发出信号的概率分布为P(U|vj)，信源的平均不确定性：
称为后验熵。后验熵的期望(条件熵或信道疑义度)：
信息增益
信息消除随机不确定性的程度
第18页，此课件共60页哦
：生长算法
如何从众多输入变量中选择一个最佳分组变量：
。例如：
决策树建立之前：
第19页，此课件共60页哦
决策树建立过程中，考察输入变量，如T1：
第20页，此课件共60页哦
问题：类别值多的输入变量比类别值少的输入变量有更多的机会成为当前最佳分组变量
第21页，此课件共60页哦
信息增益率：
如何评价数值型输入变量消除平均不确定性的能力
首先分箱：
然后再根据上述方法判定
：生长算法
第22页，此课件共60页哦
如何从分组变量的众多取值中找到最佳分割点
默认策略：
对分类型分组变量：有k个类别，将样本分成k组，形成树的k个分支
对数值型分组变量：以MDLP分箱所得的最小组限值为界，将小于组限的样本划为一组，大于的划为另一组，形成两个分叉
数值型其他策略：
ChiMerge分箱法，合并分组变量的多个类别后再分支
：生长算法
第23页，此课件共60页哦
：剪枝算法
采用后修剪方法，从叶节点向上逐层剪枝，关键：
误差的估计、剪枝标准的设置
误差估计：利用统计学置信区间的估计方法，直接在训练样本集上估计误差
Clementine中1-默认75%。置信度用于控制剪枝的程度，决定了所允许的误差上限
第24页，此课件共60页哦
：剪枝算法
剪枝标准：“减少－误差（reduce -error）”法
k为待剪子树中叶节点的个数，pi为第i个叶节点所含样本占子树所含样本的比例，ei为第i个叶节点的估计误差，e为父节点的估计误差
第25页，此课件共60页哦
：剪枝算法
例：能否剪掉C节点下的3个叶节点（E、F、G）
估计3个节点的误差：、、
加权求和：
计算C节点的误差估计：
可剪掉叶节点E、F、G
第一个数字是本节点所含样本量N，第二个数为错判样本数E
第26页，此课件共60页哦
决策树对逻辑关系的表述并非是最简洁的
IF a AND b THEN yes
ELSE IF c AND d THEN yes
OTHERWISE no
第27页，此课件共60页哦
推理规则集的生成算法
PRISM（Patient Rule Induction Space Method，Cendrowska，1987），“覆盖”算法，规则在训练样本集上100％正确
基本思路：确定输出变量的某个类别为期望类别
在当前样本范围内，寻找能最大限度“覆盖”期望类别样本的推理规则
在M个样本范围内，按照正确覆盖率最大原则确定附加条件，得到一个再小些的样本范围，直到推理规则不再“覆盖”属于期望类别外的样本
从当前样本集合中剔除已经被正确“覆盖”的样本，检查剩余样本中是否还有属于期望类别的样本。如果有则回到第一步。否则结束。
第28页，此课件共60页哦
年龄段=A(2/5)，年龄段=B(4/4)，年龄段=C(3/5)，性别=0(6/8)，性别=1(3/6)，推理规则为：IF 年龄段=B THEN 是否购买=yes。剔除已被正确覆盖的4个样本
年龄段=A(2/5)，年龄段=C(3/5)，性别=0(4/6)，性别=1(1/4)，推理规则为：IF 性别=0 THEN 是否购买=yes
需附加逻辑与条件，样本范围为表中灰色部分。
年龄段=A(1/3)，年龄段=C(3/3)。推理规则修正为：
IF 性别=0 AND 年龄段=C THEN 是否购买=yes
Yes为期望类别
第29页，此课件共60页哦
：损失矩阵
不同