第六章决策树PPT课件

1、第六章 决策树卓汉逵2021年10月9日课程网站：/AI/动机 搜索 基于符号搜索 命题符号、状态符号、动作符号 现实应用中的原始数据 无结构（例如图片、数值向量） 符号搜索之前需要想办法从无结构数据中自动获得符号 分类模型 社会主义改革开放伟大构想是不断从成功和失败样例中学习得到的精华。结构 基于树结构的分类 内部节点是特征 叶子节点是列表 边表示特征的值colorredbluegreenshapecirclesquaretriangle-+-colorredbluegreenshapecircle squaretriangle B C A B

2、 C意义 可以表达任意合取和析取式 可以表达任意关于离散特征值向量的分类函数 可以写成规则集合，例如，析取范式. red circle pos red circle A blue B; red square B green C; red triangle Ccolorredbluegreenshapecirclesquaretrianglenegposposnegnegcolorredbluegreenshapecirclesquaretriangle B C A B C自顶向下的决策树归纳法 通过自顶向下选择特征来分割数据集: + : +: : colorredbluegreen: + :

3、+: 自顶向下的决策树归纳法 通过自顶向下选择特征来分割数据集shapecirclesquare triangle: + : +: : : + : +: colorredbluegreen: + : +pos: negpos: negneg决策树归纳方法伪代码DTree(examples, features) If 所有 examples 属于同一类，返回以该类为类标的叶子节点.Else if features为空，返回叶子节点，并以examples中占最多样本的标签标记该结点Else 选择特征 F 并创建节点 R For F 每个可能值 vi : 令 examplesi 为具有值 vi的样本

4、子集添加从 R 出发的边E，并标记该边为vi. If examplesi 为空返回叶子节点，并以examples中占最多样本的标签标记该节点Else 调用 DTree(examplesi , features F)，并将结果作为连接于E的子树 返回以R为根节点的子树 如何选择特征？ 目标是令树越小越好，为什么？ 奥卡姆剃刀定律（Occams Razor, Ockhams Razor） 寻找最小决策树(nodes, leaves, or depth)计算复杂度高 自顶向下归纳是一种贪婪搜索方法，不能保证获得最小树 机器学习的经验:“贪婪往往可以获得好的效果” 指导思想： 尽量选择可以创建只单一类

5、标样本子集的特征，使得它更接近叶子节点 一种选择特征的有效启发方法：信息增益 （information gain)熵对于二分类，一个集合S的熵 (混杂)是： 其中 p1 是S中正类的比例， p0 是负类的比例如果所有样本属于同一类，熵为0(我们定义 0log(0)=0)如果正负类一样多 (p1=p0=0.5), 熵为 1.对于具有c个类的多分类问题, 熵的定义可以一般化为：)(log)(log)(020121ppppSEntropyciiippSEntropy12)(log)(二分类熵变化曲线信息增益11特征F 的信息增益是通过选择F后熵的期望减量 其中 Sv 是 S 的子集，v 是F 的取值

6、样本 S : : + : + : : )()(),()(vFValuesvvSEntropySSSEntropyFSGain2+, 2 : E=1 sizebig small1+,1 1+,1E=1 E=1Gain=1(0.51 + 0.51) = 02+, 2 : E=1 colorred blue2+,1 0+,1E=0.918 E=0Gain=1(0.750.918 + 0.250) = 0.3112+, 2 : E=1 shapecircle square2+,1 0+,1E=0.918 E=0Gain=1(0.750.918 + 0.250) = 0.311过拟合 一个可以对训练集进

7、行精确分类的决策树，不一定可以对测试集进行精确的分类 训练集可能有噪声数据导致决策树拟合偏差 决策树可能对一部分数据进行精确拟合，而不能反映整体数据分布的趋势一个模型h 被称为是训练集的过拟合，如果存在另外一个模型 h 使得h 在训练集上比 h 更精准，但是在测试集上比h 更差hypothesis complexityaccuracyon training dataon test data过拟合的例子voltage (V)current (I)测试测试欧姆定律欧姆定律: V = IR (I = (1/R)V)与欧姆定律不一致利用 9次多项式可以完美拟合这个10个点(利用n-1次多项式可以拟合

8、n 个点) 测试10个点 对这10个点进行拟合策略抽取voltage (V)current (I)Testing Ohms Law: V = IR (I = (1/R)V) 线性函数不能完美拟合数据，但是泛化性更强 与欧姆定律一致决策树易于对噪声过拟合 类标或者特征噪声很容易导致过拟合 添加噪声样本 : pos (实际是 neg)shapecirclesquaretrianglecolorredbluegreenposnegposnegnegpos避免过拟合的方法 两种方法： 提前剪枝: 在自顶向下生成决策树过程中，当没有足够数据可支撑判定类标 后剪枝: 先生成完整的决策树，在剪掉没有足够数据

9、支撑判定类标的子树 直接以剩下数据集中占大多数的类标作为最终的类标 或者根据剩下的数据集计算类标的分布避免错误的剪枝 在后剪枝的基础上，进行交叉验证1.将训练集分为 “grow” 和 “validation” 两个集合2.根据grow集合建立完整决策树3.循环直到在validation集合上的精度下降:4. 对每个非叶子节点 n:5. 临时剪掉以 n 为根的子树，6. 将 n 替换为以子树样本集中占多数的类标作为类标的叶子7. 计算剪枝后的决策树在validation集合上的精度8. 永久剪掉令决策树在validation集合上精度提高最多的子树避免错误的剪枝问题 浪费了训练集中的数据（validation 集合） 这种浪费的严重性取