机器学习 第3章决策树学习 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 1 机器学习 第3章 决策树学习
概论 决策树学习是应用最广的归纳推理算法之一 是一种逼近离散值函数的方法 很好的健壮性 能够学习析取表达式 ID3. Assistant. C4.5 搜索一个完整表示的假设空间 归纳偏置是优先选择较小的树 决策树表示了多个i-then规则 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏 2
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 2 概论 • 决策树学习是应用最广的归纳推理算法之一 • 是一种逼近离散值函数的方法 • 很好的健壮性 • 能够学习析取表达式 • ID3, Assistant, C4.5 • 搜索一个完整表示的假设空间 • 归纳偏置是优先选择较小的树 • 决策树表示了多个if-then规则
提纲 决策树定义 适用问题特征 基本ID3算法 决策树学习的归纳偏置 训练数据的过度拟合 更深入的话题 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 3 提纲 • 决策树定义 • 适用问题特征 • 基本ID3算法 • 决策树学习的归纳偏置 • 训练数据的过度拟合 • 更深入的话题
决策树表示法 决策树 通过把实例从根节点排列到某个叶子节点来分类实 例 叶子节点即为实例所属的分类 树上每个节点说明了对实例的某个属性的测试 节点的每个后继分支对应于该属性的一个可能值 图3-1 决策树代表实例属性值约束的合取的析取式。 从树根到树叶的每一条路径对应一组属性测试 的合取,树本身对应这些合取的析取。 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 4 决策树表示法 • 决策树 – 通过把实例从根节点排列到某个叶子节点来分类实 例。 – 叶子节点即为实例所属的分类 – 树上每个节点说明了对实例的某个属性的测试 – 节点的每个后继分支对应于该属性的一个可能值 • 图3-1 • 决策树代表实例属性值约束的合取的析取式。 从树根到树叶的每一条路径对应一组属性测试 的合取，树本身对应这些合取的析取
决策树学习的适用问题 适用问题的特征 实例由“属性-值”对表示 目标函数具有离散的输出值 可能需要析取的描述 训练数据可以包含错误 训练数据可以包含缺少属性值的实例 问题举例 根据疾病分类患者 根据起因分类设备故障 根据拖欠支付的可能性分类贷款申请 分类问题 核心任务是把样例分类到各可能的离散值对应的类别 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 5 决策树学习的适用问题 • 适用问题的特征 – 实例由“属性-值”对表示 – 目标函数具有离散的输出值 – 可能需要析取的描述 – 训练数据可以包含错误 – 训练数据可以包含缺少属性值的实例 • 问题举例 – 根据疾病分类患者 – 根据起因分类设备故障 – 根据拖欠支付的可能性分类贷款申请 • 分类问题 – 核心任务是把样例分类到各可能的离散值对应的类别