2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 1
机器学习第 3章 决策树学习
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 2
概论
决策树学习是应用最广的归纳推理算法之一
是一种逼近离散值函数的方法
很好的健壮性
能够学习析取表达式
ID3,Assistant,C4.5
搜索一个完整表示的假设空间
归纳偏置是优先选择较小的树
决策树表示了多个 if-then规则
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 3
提纲
决策树定义
适用问题特征
基本 ID3算法
决策树学习的归纳偏置
训练数据的过度拟合
更深入的话题
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 4
决策树表示法
决策树
– 通过把实例从根节点排列到某个叶子节点来分类实例。
– 叶子节点即为实例所属的分类
– 树上每个节点说明了对实例的某个属性的测试
– 节点的每个后继分支对应于该属性的一个可能值
图 3-1
决策树代表实例属性值约束的合取的析取式。
从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 5
决策树学习的适用问题
适用问题的特征
– 实例由“属性 -值”对表示
– 目标函数具有离散的输出值
– 可能需要析取的描述
– 训练数据可以包含错误
– 训练数据可以包含缺少属性值的实例
问题举例
– 根据疾病分类患者
– 根据起因分类设备故障
– 根据拖欠支付的可能性分类贷款申请
分类问题
– 核心任务是把样例分类到各可能的离散值对应的类别
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 6
基本的决策树学习算法
大多数决策树学习算法是一种核心算法的变体
采用自顶向下的贪婪搜索遍历可能的决策树空间
ID3是这种算法的代表
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 7
基本的决策树学习算法（ 2）
ID3的思想
– 自顶向下构造决策树
– 从“哪一个属性将在树的根节点被测试”开始
– 使用统计测试来确定每一个实例属性单独分类训练样例的能力
ID3的过程
– 分类能力最好的属性被选作树的根节点
– 根节点的每个可能值产生一个分支
– 训练样例排列到适当的分支
– 重复上面的过程
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值
否则开始
– 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
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 9
最佳分类属性
信息增益
– 用来衡量给定的属性区分训练样例的能力
– ID3算法在增长树的每一步使用信息增益从候选属性中选择属性
用熵度量样例的均一性
– 熵刻画了任意样例集的纯度
– 给定包含关于某个目标概念的正反样例的样例集 S，那么 S相对这个布尔型分类的熵为
Entropy(S)=-p+log2p+ - p-log2p-
– 信息论中对熵的一种解释，熵确定了要编码集合 S中任意成员的分类所需要的最少二进制位数
– 更一般地，如果目标属性具有 c个不同的值，那么 S相对于 c个状态的分类的熵定义为
Entropy(S)=?
c
i ii pp1 2log
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 10
最佳分类属性（ 2）
用信息增益度量期望的熵降低
– 属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低
– Gain(S,A)是在知道属性 A的值后可以节省的二进制位数
– 例子
)( )(||)(),( AV a l u e sv vv SE n t r o p ySSSE n t r o p yASGa in
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 11
ID3算法举例
表 3-2
– …
– 继续这个过程，直到满足以下两个条件中的一个
所有的属性已经被这条路经包括
与这个节点关联的所有训练样例都具有相同的目标属性值
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 12
决策树学习中的假设空间搜索
观察 ID3的搜索空间和搜索策略，认识到这个算法的优势和不足
– 假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间
– 维护单一的当前假设（不同于第二章的变型空间候选消除算法）
– 不进行回溯，可能收敛到局部最优
– 每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 13
决策树学习的归纳偏置
ID3的搜索策略
– 优先选择较短的树
– 选择那些信息增益高的属性离根节点较近的树
– 很难准确刻画 ID3的归纳偏置
近似的 ID3的归纳偏置
– 较短的树比较长的树优先
– 近似在于 ID3得到局部最优，而不一定是全局最优
– 一个精确具有这个归纳偏置的算法,BFS-ID3
更贴切近似的归纳偏置
– 较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 14
限定偏置和优选偏置
ID3和候选消除算法的比较
– ID3的搜索范围是一个完整的假设空间，但不彻底地搜索这个空间
– 候选消除算法的搜索范围是不完整的假设空间，但彻底地搜索这个空间
– ID3的归纳偏置完全是搜索策略排序假设的结果，来自搜索策略
– 候选消除算法完全是假设表示的表达能力的结果，来自对搜索空间的定义
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 15
限定偏置和优选偏置
优选偏置
– ID3的归纳偏置是对某种假设胜过其他假设的一种优选，对最终可列举的假设没有硬性限制
限定偏置
– 候选消除算法的偏置是对待考虑假设的一种限定
通常优选偏置比限定偏置更符合归纳学习的需要
优选偏置和限定偏置的结合
– 考虑第 1章的例子
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 16
为什么短的假设优先
ID3的归纳偏置的哲学基础
奥坎姆剃刀
– 优先选择拟合数据的最简单的假设
科学上的例子
– 物理学家优先选择行星运动的简单假设
– 简单假设的数量远比复杂假设的数量少
– 简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 17
为什么短的假设优先
奥坎姆剃刀的困难
– 我们反问，使用上页的推理，应该优先选择包含恰好 17个叶子节点和 11个非叶子节点的决策树？
– 假设的规模由学习器内部使用的特定表示决定
从生物进化的观点看内部表示和奥坎姆剃刀原则
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 18
决策树学习的常见问题
决策树学习的实际问题
– 确定决策树增长的深度
– 处理连续值的属性
– 选择一个适当的属性筛选度量标准
– 处理属性值不完整的训练数据
– 处理不同代价的属性
– 提高计算效率
针对这些问题,ID3被扩展成 C4.5
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 19
避免过度拟合数据
过度拟合
– 对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例
– 定义：给定一个假设空间 H，一个假设 h?H，如果存在其他的假设 h’?H，使得在训练样例上 h的错误率比 h’小，但在整个实例分布上 h’的错误率比 h小，
那么就说假设 h过度拟合训练数据。
– 图 3-6的例子
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 20
避免过度拟合数据（ 2）
导致过度拟合的原因
– 一种可能原因是训练样例含有随机错误或噪声
– 当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 21
避免过度拟合数据（ 3）
避免过度拟合的方法
– 及早停止树增长
– 后修剪法
两种方法的特点
– 第一种方法更直观
– 第一种方法中，精确地估计何时停止树增长很困难
– 第二种方法被证明在实践中更成功
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 22
避免过度拟合数据（ 4）
避免过度拟合的关键
– 使用什么样的准则来确定最终正确树的规模
解决方法
– 使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。
– 使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。
– 使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 23
避免过度拟合数据（ 5）
方法评述
– 第一种方法是最普通的，常被称为训练和验证集法。
– 可用数据分成两个样例集合：
训练集合，形成学习到的假设
验证集合，评估这个假设在后续数据上的精度
– 方法的动机：即使学习器可能会被训练集合误导，
但验证集合不大可能表现出同样的随机波动
– 验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。
– 常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 24
错误率降低修剪
将树上的每一个节点作为修剪得候选对象
修剪步骤
– 删除以此节点为根的子树，使它成为叶结点
– 把和该节点关联的训练样例的最常见分类赋给它
– 反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点
继续修剪，直到进一步的修剪是有害的为止
数据分成 3个子集
– 训练样例，形成决策树
– 验证样例，修剪决策树
– 测试样例，精度的无偏估计
如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 25
规则后修剪
从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生
将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则
通过删除任何能导致估计精度提高的前件来修剪每一条规则
按照修剪过的规则的估计精度对它们进行排序，
并按这样的顺序应用这些规则来分类后来的实例
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 26
规则后修剪（ 2）
例子
– 图 3-1的最左一条路径
– if (outlook=sunny)?(Humidity=High) then
PlayTennis=No
– 考虑删除先行词 (outlook=sunny)和
(Humidity=High)
– 选择使估计精度有最大提升的步骤
– 考虑修剪第二个前件
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 27
规则后修剪（ 3）
规则精度估计方法
– 使用与训练集不相交的验证集
– 基于训练集合本身
被 C4.5使用，使用一种保守估计来弥补训练数据有利于当前规则的估计偏置
过程
– 先计算规则在它应用的训练样例上的精度
– 然后假定此估计精度为二项式分布，并计算它的标准差
– 对于一个给定的置信区间，采用下界估计作为规则性能的度量
评论
– 对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度越来越远
– 不是统计有效（此概念第 5章介绍），但是实践中发现有效
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 28
规则后修剪（ 4）
把决策树转化成规则集的好处
– 可以区分决策节点使用的不同上下文
– 消除了根节点附近的属性测试和叶节点附近的属性测试的区别
– 提高了可读性
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 29
合并连续值属性
ID3被限制为取离散值的属性
– 学习到的决策树要预测的目标属性必须是离散的
– 树的决策节点的属性也必须是离散的
简单删除上面第 2个限制的方法
– 通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 30
合并连续值属性（ 2）
例子,Temperature应该定义什么样的基于阈值的布尔属性
– 选择产生最大信息增益的阈值
– 按照连续属性排列样例，确定目标分类不同的相邻实例
– 产生一组候选阈值，它们的值是相应的 A值之间的中间值
– 可以证明产生最大信息增益的 c值位于这样的边界中
（ Fayyad1991）
– 通过计算与每个候选阈值关联的信息增益评估这些候选值
方法的扩展
– 连续的属性分割成多个区间，而不是单一阈值的两个空间
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 31
属性选择的其他度量标准
信息增益度量存在一个内在偏置，偏向具有较多值的属性
避免方法，其他度量，比如增益比率
增益比率通过加入一个被称作分裂信息的项来惩罚多值属性，分裂信息用来衡量属性分裂数据的广度和均匀性
SplitInformation(S,A)=
GainRatio(S,A)=
分裂信息项阻碍选择值为均匀分布的属性
问题，当某个 Si?S。解决方法：采用一些启发式规则，
比如仅对增益高过平均值的属性应用增益比率测试
ci ii SSSS1 2 || ||log|| ||
),(),( ASm ationSplitInfor ASG ain
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 32
属性选择的其他度量标准（ 2）
基于距离的度量
– 定义了数据划分间的一种距离尺度
– 计算每个属性产生的划分与理想划分间的距离
– 选择最接近完美划分的属性
– Lopez de Mantaras定义了这个距离度量，证明了它不偏向有大量值的属性
此外
Mingers实验，不同的属性选择度量对最终精度的影响小于后修剪得程度和方法的影响
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 33
缺少属性值的训练样例
例子，医学领域
经常需要根据此属性值已知的实例来估计这个缺少的属性值
为了评估属性 A是否是决策节点 n的最佳测试属性，要计算决策树在该节点的信息增益
Gain(S,A)。假定 <x,c(x)>是 S中的一个训练样例，
并且其属性 A的值 A(x)未知
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 34
缺少属性值的训练样例（ 2）
处理缺少属性值的
– 一种策略是赋给它节点 n的训练样例中该属性的最常见值
– 另一种策略是赋给它节点 n的被分类为 c(x)的训练样例中该属性的最常见值
– 更复杂的策略，为 A的每个可能值赋予一个概率，而不是简单地将最常见的值赋给 A(x)
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 35
处理不同代价的属性
实例的属性可能与代价相关
优先选择尽可能使用低代价属性的决策树，仅当需要产生可靠的分类时才依赖高代价属性
通过引入一个代价项到属性选择度量中，
可以使 ID3算法考虑属性代价
Tan和 Schlimmer的例子
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 36
小结和补充读物
决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法
ID3算法
– 贪婪算法
– 从根向下推断决策树
– 搜索完整的假设空间
– 归纳偏置，较小的树
过度拟合问题
ID3算法的扩展
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 37
小结和补充读物（ 2）
Hunt
Quinlan
Mingers
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 38
附录
C4.5 is a software extension of the basic ID3 algorithm
designed by Quinlan to address the following issues not
dealt with by ID3,
– Avoiding overfitting the data
– Determining how deeply to grow a decision tree,
– Reduced error pruning,
– Rule post-pruning,
– Handling continuous attributes,
– e.g.,temperature
– Choosing an appropriate attribute selection measure,
– Handling training data with missing attribute values,
– Handling attributes with differing costs,
– Improving computational efficiency,
机器学习第 3章 决策树学习
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 2
概论
决策树学习是应用最广的归纳推理算法之一
是一种逼近离散值函数的方法
很好的健壮性
能够学习析取表达式
ID3,Assistant,C4.5
搜索一个完整表示的假设空间
归纳偏置是优先选择较小的树
决策树表示了多个 if-then规则
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 3
提纲
决策树定义
适用问题特征
基本 ID3算法
决策树学习的归纳偏置
训练数据的过度拟合
更深入的话题
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 4
决策树表示法
决策树
– 通过把实例从根节点排列到某个叶子节点来分类实例。
– 叶子节点即为实例所属的分类
– 树上每个节点说明了对实例的某个属性的测试
– 节点的每个后继分支对应于该属性的一个可能值
图 3-1
决策树代表实例属性值约束的合取的析取式。
从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 5
决策树学习的适用问题
适用问题的特征
– 实例由“属性 -值”对表示
– 目标函数具有离散的输出值
– 可能需要析取的描述
– 训练数据可以包含错误
– 训练数据可以包含缺少属性值的实例
问题举例
– 根据疾病分类患者
– 根据起因分类设备故障
– 根据拖欠支付的可能性分类贷款申请
分类问题
– 核心任务是把样例分类到各可能的离散值对应的类别
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 6
基本的决策树学习算法
大多数决策树学习算法是一种核心算法的变体
采用自顶向下的贪婪搜索遍历可能的决策树空间
ID3是这种算法的代表
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 7
基本的决策树学习算法（ 2）
ID3的思想
– 自顶向下构造决策树
– 从“哪一个属性将在树的根节点被测试”开始
– 使用统计测试来确定每一个实例属性单独分类训练样例的能力
ID3的过程
– 分类能力最好的属性被选作树的根节点
– 根节点的每个可能值产生一个分支
– 训练样例排列到适当的分支
– 重复上面的过程
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值
否则开始
– 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
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 9
最佳分类属性
信息增益
– 用来衡量给定的属性区分训练样例的能力
– ID3算法在增长树的每一步使用信息增益从候选属性中选择属性
用熵度量样例的均一性
– 熵刻画了任意样例集的纯度
– 给定包含关于某个目标概念的正反样例的样例集 S，那么 S相对这个布尔型分类的熵为
Entropy(S)=-p+log2p+ - p-log2p-
– 信息论中对熵的一种解释，熵确定了要编码集合 S中任意成员的分类所需要的最少二进制位数
– 更一般地，如果目标属性具有 c个不同的值，那么 S相对于 c个状态的分类的熵定义为
Entropy(S)=?
c
i ii pp1 2log
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 10
最佳分类属性（ 2）
用信息增益度量期望的熵降低
– 属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低
– Gain(S,A)是在知道属性 A的值后可以节省的二进制位数
– 例子
)( )(||)(),( AV a l u e sv vv SE n t r o p ySSSE n t r o p yASGa in
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 11
ID3算法举例
表 3-2
– …
– 继续这个过程，直到满足以下两个条件中的一个
所有的属性已经被这条路经包括
与这个节点关联的所有训练样例都具有相同的目标属性值
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 12
决策树学习中的假设空间搜索
观察 ID3的搜索空间和搜索策略，认识到这个算法的优势和不足
– 假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间
– 维护单一的当前假设（不同于第二章的变型空间候选消除算法）
– 不进行回溯，可能收敛到局部最优
– 每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 13
决策树学习的归纳偏置
ID3的搜索策略
– 优先选择较短的树
– 选择那些信息增益高的属性离根节点较近的树
– 很难准确刻画 ID3的归纳偏置
近似的 ID3的归纳偏置
– 较短的树比较长的树优先
– 近似在于 ID3得到局部最优，而不一定是全局最优
– 一个精确具有这个归纳偏置的算法,BFS-ID3
更贴切近似的归纳偏置
– 较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 14
限定偏置和优选偏置
ID3和候选消除算法的比较
– ID3的搜索范围是一个完整的假设空间，但不彻底地搜索这个空间
– 候选消除算法的搜索范围是不完整的假设空间，但彻底地搜索这个空间
– ID3的归纳偏置完全是搜索策略排序假设的结果，来自搜索策略
– 候选消除算法完全是假设表示的表达能力的结果，来自对搜索空间的定义
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 15
限定偏置和优选偏置
优选偏置
– ID3的归纳偏置是对某种假设胜过其他假设的一种优选，对最终可列举的假设没有硬性限制
限定偏置
– 候选消除算法的偏置是对待考虑假设的一种限定
通常优选偏置比限定偏置更符合归纳学习的需要
优选偏置和限定偏置的结合
– 考虑第 1章的例子
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 16
为什么短的假设优先
ID3的归纳偏置的哲学基础
奥坎姆剃刀
– 优先选择拟合数据的最简单的假设
科学上的例子
– 物理学家优先选择行星运动的简单假设
– 简单假设的数量远比复杂假设的数量少
– 简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 17
为什么短的假设优先
奥坎姆剃刀的困难
– 我们反问，使用上页的推理，应该优先选择包含恰好 17个叶子节点和 11个非叶子节点的决策树？
– 假设的规模由学习器内部使用的特定表示决定
从生物进化的观点看内部表示和奥坎姆剃刀原则
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 18
决策树学习的常见问题
决策树学习的实际问题
– 确定决策树增长的深度
– 处理连续值的属性
– 选择一个适当的属性筛选度量标准
– 处理属性值不完整的训练数据
– 处理不同代价的属性
– 提高计算效率
针对这些问题,ID3被扩展成 C4.5
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 19
避免过度拟合数据
过度拟合
– 对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例
– 定义：给定一个假设空间 H，一个假设 h?H，如果存在其他的假设 h’?H，使得在训练样例上 h的错误率比 h’小，但在整个实例分布上 h’的错误率比 h小，
那么就说假设 h过度拟合训练数据。
– 图 3-6的例子
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 20
避免过度拟合数据（ 2）
导致过度拟合的原因
– 一种可能原因是训练样例含有随机错误或噪声
– 当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 21
避免过度拟合数据（ 3）
避免过度拟合的方法
– 及早停止树增长
– 后修剪法
两种方法的特点
– 第一种方法更直观
– 第一种方法中，精确地估计何时停止树增长很困难
– 第二种方法被证明在实践中更成功
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 22
避免过度拟合数据（ 4）
避免过度拟合的关键
– 使用什么样的准则来确定最终正确树的规模
解决方法
– 使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。
– 使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。
– 使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 23
避免过度拟合数据（ 5）
方法评述
– 第一种方法是最普通的，常被称为训练和验证集法。
– 可用数据分成两个样例集合：
训练集合，形成学习到的假设
验证集合，评估这个假设在后续数据上的精度
– 方法的动机：即使学习器可能会被训练集合误导，
但验证集合不大可能表现出同样的随机波动
– 验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。
– 常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 24
错误率降低修剪
将树上的每一个节点作为修剪得候选对象
修剪步骤
– 删除以此节点为根的子树，使它成为叶结点
– 把和该节点关联的训练样例的最常见分类赋给它
– 反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点
继续修剪，直到进一步的修剪是有害的为止
数据分成 3个子集
– 训练样例，形成决策树
– 验证样例，修剪决策树
– 测试样例，精度的无偏估计
如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 25
规则后修剪
从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生
将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则
通过删除任何能导致估计精度提高的前件来修剪每一条规则
按照修剪过的规则的估计精度对它们进行排序，
并按这样的顺序应用这些规则来分类后来的实例
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 26
规则后修剪（ 2）
例子
– 图 3-1的最左一条路径
– if (outlook=sunny)?(Humidity=High) then
PlayTennis=No
– 考虑删除先行词 (outlook=sunny)和
(Humidity=High)
– 选择使估计精度有最大提升的步骤
– 考虑修剪第二个前件
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 27
规则后修剪（ 3）
规则精度估计方法
– 使用与训练集不相交的验证集
– 基于训练集合本身
被 C4.5使用，使用一种保守估计来弥补训练数据有利于当前规则的估计偏置
过程
– 先计算规则在它应用的训练样例上的精度
– 然后假定此估计精度为二项式分布，并计算它的标准差
– 对于一个给定的置信区间，采用下界估计作为规则性能的度量
评论
– 对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度越来越远
– 不是统计有效（此概念第 5章介绍），但是实践中发现有效
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 28
规则后修剪（ 4）
把决策树转化成规则集的好处
– 可以区分决策节点使用的不同上下文
– 消除了根节点附近的属性测试和叶节点附近的属性测试的区别
– 提高了可读性
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 29
合并连续值属性
ID3被限制为取离散值的属性
– 学习到的决策树要预测的目标属性必须是离散的
– 树的决策节点的属性也必须是离散的
简单删除上面第 2个限制的方法
– 通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 30
合并连续值属性（ 2）
例子,Temperature应该定义什么样的基于阈值的布尔属性
– 选择产生最大信息增益的阈值
– 按照连续属性排列样例，确定目标分类不同的相邻实例
– 产生一组候选阈值，它们的值是相应的 A值之间的中间值
– 可以证明产生最大信息增益的 c值位于这样的边界中
（ Fayyad1991）
– 通过计算与每个候选阈值关联的信息增益评估这些候选值
方法的扩展
– 连续的属性分割成多个区间，而不是单一阈值的两个空间
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 31
属性选择的其他度量标准
信息增益度量存在一个内在偏置，偏向具有较多值的属性
避免方法，其他度量，比如增益比率
增益比率通过加入一个被称作分裂信息的项来惩罚多值属性，分裂信息用来衡量属性分裂数据的广度和均匀性
SplitInformation(S,A)=
GainRatio(S,A)=
分裂信息项阻碍选择值为均匀分布的属性
问题，当某个 Si?S。解决方法：采用一些启发式规则，
比如仅对增益高过平均值的属性应用增益比率测试
ci ii SSSS1 2 || ||log|| ||
),(),( ASm ationSplitInfor ASG ain
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 32
属性选择的其他度量标准（ 2）
基于距离的度量
– 定义了数据划分间的一种距离尺度
– 计算每个属性产生的划分与理想划分间的距离
– 选择最接近完美划分的属性
– Lopez de Mantaras定义了这个距离度量，证明了它不偏向有大量值的属性
此外
Mingers实验，不同的属性选择度量对最终精度的影响小于后修剪得程度和方法的影响
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 33
缺少属性值的训练样例
例子，医学领域
经常需要根据此属性值已知的实例来估计这个缺少的属性值
为了评估属性 A是否是决策节点 n的最佳测试属性，要计算决策树在该节点的信息增益
Gain(S,A)。假定 <x,c(x)>是 S中的一个训练样例，
并且其属性 A的值 A(x)未知
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 34
缺少属性值的训练样例（ 2）
处理缺少属性值的
– 一种策略是赋给它节点 n的训练样例中该属性的最常见值
– 另一种策略是赋给它节点 n的被分类为 c(x)的训练样例中该属性的最常见值
– 更复杂的策略，为 A的每个可能值赋予一个概率，而不是简单地将最常见的值赋给 A(x)
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 35
处理不同代价的属性
实例的属性可能与代价相关
优先选择尽可能使用低代价属性的决策树，仅当需要产生可靠的分类时才依赖高代价属性
通过引入一个代价项到属性选择度量中，
可以使 ID3算法考虑属性代价
Tan和 Schlimmer的例子
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 36
小结和补充读物
决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法
ID3算法
– 贪婪算法
– 从根向下推断决策树
– 搜索完整的假设空间
– 归纳偏置，较小的树
过度拟合问题
ID3算法的扩展
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 37
小结和补充读物（ 2）
Hunt
Quinlan
Mingers
2003.11.18 机器学习 -决策树学习 译者：曾华军等 作者,Mitchell 讲者：陶晓鹏 38
附录
C4.5 is a software extension of the basic ID3 algorithm
designed by Quinlan to address the following issues not
dealt with by ID3,
– Avoiding overfitting the data
– Determining how deeply to grow a decision tree,
– Reduced error pruning,
– Rule post-pruning,
– Handling continuous attributes,
– e.g.,temperature
– Choosing an appropriate attribute selection measure,
– Handling training data with missing attribute values,
– Handling attributes with differing costs,
– Improving computational efficiency,
