机器学习 第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 决策树学习的适用问题 • 适用问题的特征 – 实例由“属性-值”对表示 – 目标函数具有离散的输出值 – 可能需要析取的描述 – 训练数据可以包含错误 – 训练数据可以包含缺少属性值的实例 • 问题举例 – 根据疾病分类患者 – 根据起因分类设备故障 – 根据拖欠支付的可能性分类贷款申请 • 分类问题 – 核心任务是把样例分类到各可能的离散值对应的类别
基本的决策树学习算法 大多数决策树学习算法是一种核心算法 的变体 采用自顶向下的贪婪搜索遍历可能的决 策树空间 ID3是这种算法的代表 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 6 基本的决策树学习算法 • 大多数决策树学习算法是一种核心算法 的变体 • 采用自顶向下的贪婪搜索遍历可能的决 策树空间 • ID3是这种算法的代表
基本的决策树学习算法(2) ID3的思想 自顶向下构造决策树 从“哪一个属性将在树的根节点被测试”开始 使用统计测试来确定每一个实例属性单独分类训练 样例的能力 D3的过程 分类能力最好的属性被选作树的根节点 根节点的每个可能值产生一个分支 训练样例排列到适当的分支 重复上面的过程 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 7 基本的决策树学习算法（2） • ID3的思想 – 自顶向下构造决策树 – 从“哪一个属性将在树的根节点被测试”开始 – 使用统计测试来确定每一个实例属性单独分类训练 样例的能力 • ID3的过程 – 分类能力最好的属性被选作树的根节点 – 根节点的每个可能值产生一个分支 – 训练样例排列到适当的分支 – 重复上面的过程
表3-1用于学习布尔函数的D3算法概要 D3(Examples, Target attribute, Attributes) 创建树的root节点 如果 Examples都为正,返回abe+的单节点树root 如果 Examples都为反,返回habe-的单节点树root 如果 Attributes为空,那么返回单节点roo, labehExamples中最普遍的 Target attribute值 否则开始 A←- Attributes中分类 examples能力最好的属性 root的决策属性←A 对于A的每个可能值ⅵ 在root下加一个新的分支对应测试A=vi 令 Examples为 Examples中满足A属性值为v的子集 如果 Examples为空 在这个新分支下加一个叶子节点,节点的 label=Examples中最普遍的 bute值 否则在新分支下加一个子树ID3( Examples, Target attribute, Attributes-{A}) 结束 返回root 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 8 表3-1 用于学习布尔函数的ID3算法概要 • ID3(Examples, Target_attribute, Attributes) • 创建树的root节点 • 如果Examples都为正,返回label=+的单节点树root • 如果Examples都为反,返回label=-的单节点树root • 如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值 • 否则开始 – AAttributes中分类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-log p 信息论中对熵的一种解释,熵确定了要编码集合S中任意成员的分类 所需要的最少二进制位数 更一般地,如果目标属性具有c个不同的值,那么S相对于c个状态的 分类的熵定义为 Entropy(S)∑-pkgP 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 9 最佳分类属性 • 信息增益 – 用来衡量给定的属性区分训练样例的能力 – ID3算法在增长树的每一步使用信息增益从候选属性中选择属性 • 用熵度量样例的均一性 – 熵刻画了任意样例集的纯度 – 给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个 布尔型分类的熵为 Entropy(S)=-p+log2p+ - p-log2p- – 信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类 所需要的最少二进制位数 – 更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的 分类的熵定义为 Entropy(S)= = − c i pi pi 1 2 log
最佳分类属性(2) 用信息增益度量期望的熵降低 属性的信息增益,由于使用这个属性分割样 例而导致的期望熵降低 Gain(S, A)=Entropys) Entropys) Gain(S,A)是在知道属性A的值后可以节省的 二进制位数 例子 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 10 最佳分类属性（2） • 用信息增益度量期望的熵降低 – 属性的信息增益，由于使用这个属性分割样 例而导致的期望熵降低 – Gain(S,A)是在知道属性A的值后可以节省的 二进制位数 – 例子 = − ( ) ( ) | | ( , ) ( ) v Values A v v Entropy S S S Gain S A Entropy S
