机器人课件3.决策树学习.ppt

2003.11.18 机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏 机器学习 第3章 决策树学习 概论 决策树学习是应用最广的归纳推理算法之一 是一种逼近离散值函数的方法 很好的健壮性 能够学习析取表达式 ID3, Assistant, C4.5 有哪些信誉好的足球投注网站一个完整表示的假设空间 归纳偏置是优先选择较小的树 决策树表示了多个if-then规则 提纲 决策树定义 适用问题特征 基本ID3算法 决策树学习的归纳偏置 训练数据的过度拟合 更深入的话题 决策树表示法 决策树 通过把实例从根节点排列到某个叶子节点来分类实例。 叶子节点即为实例所属的分类 树上每个节点说明了对实例的某个属性的测试 节点的每个后继分支对应于该属性的一个可能值 图3-1 决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。 决策树学习的适用问题 适用问题的特征 实例由“属性-值”对表示 目标函数具有离散的输出值 可能需要析取的描述 训练数据可以包含错误 训练数据可以包含缺少属性值的实例 问题举例 根据疾病分类患者 根据起因分类设备故障 根据拖欠支付的可能性分类贷款申请 分类问题 核心任务是把样例分类到各可能的离散值对应的类别 基本的决策树学习算法 大多数决策树学习算法是一种核心算法的变体 采用自顶向下的贪婪有哪些信誉好的足球投注网站遍历可能的决策树空间 ID3是这种算法的代表 基本的决策树学习算法（2） ID3的思想 自顶向下构造决策树 从“哪一个属性将在树的根节点被测试”开始 使用统计测试来确定每一个实例属性单独分类训练样例的能力 ID3的过程 分类能力最好的属性被选作树的根节点 根节点的每个可能值产生一个分支 训练样例排列到适当的分支 重复上面的过程 表3-1 用于学习布尔函数的ID3算法概要 ID3(Examples, Target_attribute, Attributes) 创建树的root节点 如果Examples都为正,返回label=+的单节点树root 如果Examples都为反,返回label=-的单节点树root 如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值 否则开始 A?Attributes中分类examples能力最好的属性 root的决策属性?A 对于A的每个可能值vi 在root下加一个新的分支对应测试A=vi 令Examplesvi为Examples中满足A属性值为vi的子集 如果Examplesvi为空 在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值 否则在新分支下加一个子树ID3（ Examplesvi,Target_attribute,Attributes-{A}） 结束 返回root 最佳分类属性 信息增益 用来衡量给定的属性区分训练样例的能力 ID3算法在增长树的每一步使用信息增益从候选属性中选择属性 用熵度量样例的均一性 熵刻画了任意样例集的纯度 给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为 Entropy(S)=-p+log2p+ - p-log2p- 信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数 更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为 Entropy(S)= 最佳分类属性（2） 用信息增益度量期望的熵降低 属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低 Gain(S,A)是在知道属性A的值后可以节省的二进制位数 例子 ID3算法举例 表3-2 … 继续这个过程，直到满足以下两个条件中的一个 所有的属性已经被这条路经包括 与这个节点关联的所有训练样例都具有相同的目标属性值 决策树学习中的假设空间有哪些信誉好的足球投注网站 观察ID3的有哪些信誉好的足球投注网站空间和有哪些信誉好的足球投注网站策略，认识到这个算法的优势和不足 假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间 维护单一的当前假设（不同于第二章的变型空间候选消除算法） 不进行回溯，可能收敛到局部最优 每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强 决策树学习的归纳偏置 ID3的有哪些信誉好的足球投注网站策略 优先选择较短的树 选择那些信息增益高的属性离根节点较近的树 很难准确刻画ID3的归纳偏置 近似的ID3的归纳偏置 较短的树比较长的树优先 近似在于ID3得到局部最优，而不一定是全局最优 一个精确具有这个归纳偏置的算法，BFS-ID3 更贴切近似的归纳偏置 较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先 限定偏置和优选偏置 ID3和候选消除