7.4 修剪决策树
? 决策树修剪的主要任务是抛弃一个或更多
的子树，并用叶替代这些子树，使决策树
简单化。
? 问题是修剪后的结果能达到我们期望算法
降低预测误差率来提高分类器的质量，但
误差率计算并不简单。
? 评价预测误差的一个可行方法是用另外一
个新的有效检验样本，或用第四章中讲述
的交叉确认法。
? 在具备可用的训练和检验样本的情况下，
决策树修剪的基本思想是去掉那些对未知
检验样本的分类精度没有帮助的部分树
(子树 )，生成一个更简单，更容易理解的
树。
? 有两种改进的递归分区方法,
1,在某些情况下决定不把样本集合分区
得更细。停止准则通常是基于一些统计检
验，如 χ2检验：如果分区前后分类精度没
有显著的不同，那么用当前的点作为一个
叶。该方法称为预剪法。
2.用所选的精度准则回头去除树的一些点。
称为后修剪。
? C4.5采用后修剪方法，但它用具体的方法评
估预测误差率，该方法称为悲观修剪。
? 基本思想,
对于树中的每个节点，可以用二项式分布统
计表计算置信极限的上限 Ucf的估计值。参数
Ucf是所给节点的 |Ti|和 E的函数。 C4.5用 25%
置信度, 比较所给节点 Ti的 U25%(|Ti|/E)与它
的叶的加权置信度。权值是每个叶的样本的
总数。
? 基本思想,
如果子树中的某个根节点的预测误差比叶的
U25% (子树的预测误差 )加权和小，那么用它
的根节点替换该子树，变成修剪后的树的一
个新叶。
? 例如，决策树的子树如图 7-9所示，根节点的
子节点是用相应的类和参数 (|Ti|/E)表示的叶。
? 问题是估计修剪子树并用它的根节点替换
它作为一个新的归纳叶节点的概率。
? 为了分析用叶节点替换子树的概率,必须计
算被替换节点和初始树的预测误差 PE。
? 用默认置信度 25%，上限置信极限可从统
计表中求得,
U25%(6,0)=0.206,U25%(9,0)=0.143
U25%(1,0)=0.750,U25%(16,1)=0.157
? 初始树和被替换节点的预测误差是,
PEtree=6*0.206+9*0.143+1*0.750=3.257
PEtree=16*0.157=2.512
被替换的节点比当前的决策树的预测误差低，
修剪决策树并用新的叶节点替换子树是可
行的。
? 常见的六种修剪技术,
1.MCCP(Minimal cost-complexity Pruning)-用
于 CRAT系统。
2.REP(Reduced Error Pruning) 。
3.MEP(Minimal Error Pruning) 。
4.PEP(Pessimistic Error Pruning) –用于 ID3。
5.EBP(Error Based Pruning)-用于 C4.5。
6.bootstrap。
7.5 C4.5 算法：生成决策规则
? 大型的决策树较难理解，因为每个节点都
有先行节点的检验结果建立的具休环境。
为了理解它，可以把到达每个叶的路径转
换成 IF-THEN生成规则。这种规则叫做决策
规则。
? 所有叶节点的决策规则集能够与树节点一
样对样本进行分类。
? 图 7-10所示是决策树转换成决策规则的一
个例子。
? 分类模型中决策规则的数量可能非常大，
可以删除那些不影响规则集的正确性的多
余条件，对规则进行概化。
? 规则条件的删除准则如下,
设规则Ｒ是,If A Then 类 -C
更一般化的规则 R’是,If A’ Then 类 -C
其中 A’是 A(A=A’∪ X)中删掉条件 X得到的。
? 数据库中满足条件 A’的每个样本可以满足也
可以不满足扩展条件 A。
? 我们可以将满足条件 A’中的每个样本按是否
满足条件 A构建一个列联表，如表 7-3所示。
? 由此可得,
规则 R的误差率估计,Ucf(Y1+E1,E1)
规则 R’的误差率估计,Ucf(Y1+Y2+E1+E2,E1+E2)
? 如果 R’的误差估计比 R的大，删除没有意义。
? C4.5算法不是去观察被删除的条件的所有可
能的子集，而是进行贪心法删除：每一步删
除一个最小悲观误差的条件。这类算法并不
能保证每一步的最小会使全局最小。
? 例如：表 7-4是规则 R的列关联表。
? 初始规则 R的误差估计,
Ucf(Y1+E1,E1)= Ucf(9,1)=0.183
? 概化规则 R’的误差估计,
Ucf(Y1+Y2+E1+E2,E1+E2)=Ucf(16,1)=0.157
? 后者误差率比前者小，可以替换。
? 问题是规则概化使规则不再是相互排斥和完
备的，会出现一些满足多个规则的样本和没
有规则的样本。
? 对于, 多规则满足, 时，Ｃ 4.5采用 冲突解
决 方案。
? 对于没有规则覆盖的样本采用默认规则或默
认类。默认类的合理选择是训练集中出现最
多的类。 C4.5采用仅选择包含最多训练样本
而不是被任何规则包含的类来作为默认类。
? 简化决策树和决策规则的另一种方法是对分
类数据的属性值进行分组。用分组来减少属
性值的数量
? 在构建分类模型时我们所关心的是训练数据
的不充分可能不能发现有用的模式，或发现
了这些模式但模型极其复杂。
? 图 7-11是属性值分组前后决策规则的例子。
7.6 决策树和决策规则的局限性
? 和许多统计方法不一样，逻辑方法不依赖
属性值的分布或属性独立性的假设，而且
更健壮，但也有一些缺点和局限性。
? 如果数据样本在 N-维空间用图形表示，其
中 N是属性的数据，那么一个逻辑分类器把
空间划分成几个区域，每个域有一类标识。
根据新样本落进的区域确定其类别。
?用 N-维空间的正交超平面给出决策规则
的图形化表示。图 7-12为用超矩形的接
近非正交的分类。图中一种是正交超平
面，一种是通过属性的线性（或非线性）
组合的分类。分类问题变得极度复杂，
并且有大量的规则和更大的误差。
?另一个分类问题是，如果 m个条件中有
n个条件是存在的就支持所给的类。为
了用规则表示这个分类器，必须对某个
类定义 个区域。 ? ?m
n
? 医学诊断决策是该分类问题的一个典型例
子。如果 11种症状中有 4种支持一个所给疾
病的诊断，那么该分类器将在仅关于有病
症状的 11维空间产生 330区域，和 330个决
策规则一致。因此，对这种非线性问题运
用决策规则的正交分类方法时必须谨慎。
7.7 关联分类方法
? CMAR(Classification based on Multiple
apssociation Rules，基于多维关联规则的
分类 )是生成频繁项集的频繁模式或叫 FP-方
法中采用的分类方法。该问题放在此处介
绍在于它是解决分类问题的基于逻辑的方
法。
? 假定给出有 n个属性 (A1,A2,…,An)的数据样
本。属性是分类型的或是连续型。
? 对于连续型的属性，我们认为在预处理时
已经分区。一个训练样本集中的每个样本
都存在一个和它关联的类标识。设
C={c1,c2,…,cn}是一个有限类标识集。
? 一般地，一个模式 P={a1,a2,…,an}是不同属
性 (1≤k≤n)的属性值集。如果一个样本具有
该模式中给出的所有属性的值就说它是符
合这个模式 P的。
? 对于规则 R:P→ c，符合模式且类标识是 c的
数据样本的个数叫做对规则 R的支持度，用
sup(R)表示。符合模式 P且类标识是 c的数
据样本数和符合模式 P的样本总数的比率叫
做置信度，用 conf（ R）表示。
? CMAR分为两个阶段,
1.生成或训练规则
2.分类或检验
? 在规则生成阶段，计算规则 R:P→ c 的完备
集，使支持度和置信度通过所给的阈值。
在检验阶段，当出现一个新的样本，由一
组关联规则表示的分类器选择符合该样本
且具有最高置信度的规则，用此规则来预
测新的样本的类别。
? 例如，表 7-5给出训练数据集，支持度的阈
值是 2，置信度的阈值是 70%。
? 首先，扫描训练集，找出频繁项集，
F={a1,b2,c1,d3}，按支持度大小升序排列，
即,
F-list={a1,b2,c1,d3}
? 第二步，再次扫描训练集构建 FP树，如图
7-13所示。
▲ 构造步骤,
第一个样本,(a1,c1)为频繁项集中的值。
第二个样本,(a1,b2,c1)为频繁项集中的值。
第三个样本,(d3)为频繁项集中的值。
第四个样本,(a1,b2,d3)为频繁项集中的值。
第五个样本,(a1,b2,c1,d3)为频繁项集中的
值。
? 第三步，通过把所有的规则分区成不重叠
的子集生成分类规则。
a)包含 d3的规则； b)包含 c1不包含 d3的规则；
c)包含 b2但不包含 d3或 c1的规则；
d)仅包含 a1的规则。
▲ 包含 d3规则有,
(a1,b2,c1,d3):C,(a1,b2,d3):C和 (d3):A。
求训练集中所有频繁模式的问题被归结为挖
掘 d3-投影数据库中的频繁模式。本例
(a1,b2,d3)出现两次，支持度等于给定阈
值 2。同样，基于这个频繁模式的规则，
(a1,b2,d3)→C 有 100%的置信度 (超出阈值 )，
这是所给的数据库投影中生成的唯一规则。
? 第四步,d3的所有节点和它们相应的类标
识被合成为它们的 FP树的双亲节点。见图
7-13b所示。
? 对于 c1，投影数据库同样重复前面的步骤
挖掘剩下的规则集，然后是 b2投影数据库，
最后是 a1投影数据库。本例中,(a1,c1)是
支持度 3的频繁模式，但置信度小于阈值。
对于模式 (a1,b2)和 (a1)，有相同的结论。
因此，本例生成的仅有关联规则是
(a1,b2,d3)→C,支持度等于 2，置信度 100%。
? 决策树修剪的主要任务是抛弃一个或更多
的子树，并用叶替代这些子树，使决策树
简单化。
? 问题是修剪后的结果能达到我们期望算法
降低预测误差率来提高分类器的质量，但
误差率计算并不简单。
? 评价预测误差的一个可行方法是用另外一
个新的有效检验样本，或用第四章中讲述
的交叉确认法。
? 在具备可用的训练和检验样本的情况下，
决策树修剪的基本思想是去掉那些对未知
检验样本的分类精度没有帮助的部分树
(子树 )，生成一个更简单，更容易理解的
树。
? 有两种改进的递归分区方法,
1,在某些情况下决定不把样本集合分区
得更细。停止准则通常是基于一些统计检
验，如 χ2检验：如果分区前后分类精度没
有显著的不同，那么用当前的点作为一个
叶。该方法称为预剪法。
2.用所选的精度准则回头去除树的一些点。
称为后修剪。
? C4.5采用后修剪方法，但它用具体的方法评
估预测误差率，该方法称为悲观修剪。
? 基本思想,
对于树中的每个节点，可以用二项式分布统
计表计算置信极限的上限 Ucf的估计值。参数
Ucf是所给节点的 |Ti|和 E的函数。 C4.5用 25%
置信度, 比较所给节点 Ti的 U25%(|Ti|/E)与它
的叶的加权置信度。权值是每个叶的样本的
总数。
? 基本思想,
如果子树中的某个根节点的预测误差比叶的
U25% (子树的预测误差 )加权和小，那么用它
的根节点替换该子树，变成修剪后的树的一
个新叶。
? 例如，决策树的子树如图 7-9所示，根节点的
子节点是用相应的类和参数 (|Ti|/E)表示的叶。
? 问题是估计修剪子树并用它的根节点替换
它作为一个新的归纳叶节点的概率。
? 为了分析用叶节点替换子树的概率,必须计
算被替换节点和初始树的预测误差 PE。
? 用默认置信度 25%，上限置信极限可从统
计表中求得,
U25%(6,0)=0.206,U25%(9,0)=0.143
U25%(1,0)=0.750,U25%(16,1)=0.157
? 初始树和被替换节点的预测误差是,
PEtree=6*0.206+9*0.143+1*0.750=3.257
PEtree=16*0.157=2.512
被替换的节点比当前的决策树的预测误差低，
修剪决策树并用新的叶节点替换子树是可
行的。
? 常见的六种修剪技术,
1.MCCP(Minimal cost-complexity Pruning)-用
于 CRAT系统。
2.REP(Reduced Error Pruning) 。
3.MEP(Minimal Error Pruning) 。
4.PEP(Pessimistic Error Pruning) –用于 ID3。
5.EBP(Error Based Pruning)-用于 C4.5。
6.bootstrap。
7.5 C4.5 算法：生成决策规则
? 大型的决策树较难理解，因为每个节点都
有先行节点的检验结果建立的具休环境。
为了理解它，可以把到达每个叶的路径转
换成 IF-THEN生成规则。这种规则叫做决策
规则。
? 所有叶节点的决策规则集能够与树节点一
样对样本进行分类。
? 图 7-10所示是决策树转换成决策规则的一
个例子。
? 分类模型中决策规则的数量可能非常大，
可以删除那些不影响规则集的正确性的多
余条件，对规则进行概化。
? 规则条件的删除准则如下,
设规则Ｒ是,If A Then 类 -C
更一般化的规则 R’是,If A’ Then 类 -C
其中 A’是 A(A=A’∪ X)中删掉条件 X得到的。
? 数据库中满足条件 A’的每个样本可以满足也
可以不满足扩展条件 A。
? 我们可以将满足条件 A’中的每个样本按是否
满足条件 A构建一个列联表，如表 7-3所示。
? 由此可得,
规则 R的误差率估计,Ucf(Y1+E1,E1)
规则 R’的误差率估计,Ucf(Y1+Y2+E1+E2,E1+E2)
? 如果 R’的误差估计比 R的大，删除没有意义。
? C4.5算法不是去观察被删除的条件的所有可
能的子集，而是进行贪心法删除：每一步删
除一个最小悲观误差的条件。这类算法并不
能保证每一步的最小会使全局最小。
? 例如：表 7-4是规则 R的列关联表。
? 初始规则 R的误差估计,
Ucf(Y1+E1,E1)= Ucf(9,1)=0.183
? 概化规则 R’的误差估计,
Ucf(Y1+Y2+E1+E2,E1+E2)=Ucf(16,1)=0.157
? 后者误差率比前者小，可以替换。
? 问题是规则概化使规则不再是相互排斥和完
备的，会出现一些满足多个规则的样本和没
有规则的样本。
? 对于, 多规则满足, 时，Ｃ 4.5采用 冲突解
决 方案。
? 对于没有规则覆盖的样本采用默认规则或默
认类。默认类的合理选择是训练集中出现最
多的类。 C4.5采用仅选择包含最多训练样本
而不是被任何规则包含的类来作为默认类。
? 简化决策树和决策规则的另一种方法是对分
类数据的属性值进行分组。用分组来减少属
性值的数量
? 在构建分类模型时我们所关心的是训练数据
的不充分可能不能发现有用的模式，或发现
了这些模式但模型极其复杂。
? 图 7-11是属性值分组前后决策规则的例子。
7.6 决策树和决策规则的局限性
? 和许多统计方法不一样，逻辑方法不依赖
属性值的分布或属性独立性的假设，而且
更健壮，但也有一些缺点和局限性。
? 如果数据样本在 N-维空间用图形表示，其
中 N是属性的数据，那么一个逻辑分类器把
空间划分成几个区域，每个域有一类标识。
根据新样本落进的区域确定其类别。
?用 N-维空间的正交超平面给出决策规则
的图形化表示。图 7-12为用超矩形的接
近非正交的分类。图中一种是正交超平
面，一种是通过属性的线性（或非线性）
组合的分类。分类问题变得极度复杂，
并且有大量的规则和更大的误差。
?另一个分类问题是，如果 m个条件中有
n个条件是存在的就支持所给的类。为
了用规则表示这个分类器，必须对某个
类定义 个区域。 ? ?m
n
? 医学诊断决策是该分类问题的一个典型例
子。如果 11种症状中有 4种支持一个所给疾
病的诊断，那么该分类器将在仅关于有病
症状的 11维空间产生 330区域，和 330个决
策规则一致。因此，对这种非线性问题运
用决策规则的正交分类方法时必须谨慎。
7.7 关联分类方法
? CMAR(Classification based on Multiple
apssociation Rules，基于多维关联规则的
分类 )是生成频繁项集的频繁模式或叫 FP-方
法中采用的分类方法。该问题放在此处介
绍在于它是解决分类问题的基于逻辑的方
法。
? 假定给出有 n个属性 (A1,A2,…,An)的数据样
本。属性是分类型的或是连续型。
? 对于连续型的属性，我们认为在预处理时
已经分区。一个训练样本集中的每个样本
都存在一个和它关联的类标识。设
C={c1,c2,…,cn}是一个有限类标识集。
? 一般地，一个模式 P={a1,a2,…,an}是不同属
性 (1≤k≤n)的属性值集。如果一个样本具有
该模式中给出的所有属性的值就说它是符
合这个模式 P的。
? 对于规则 R:P→ c，符合模式且类标识是 c的
数据样本的个数叫做对规则 R的支持度，用
sup(R)表示。符合模式 P且类标识是 c的数
据样本数和符合模式 P的样本总数的比率叫
做置信度，用 conf（ R）表示。
? CMAR分为两个阶段,
1.生成或训练规则
2.分类或检验
? 在规则生成阶段，计算规则 R:P→ c 的完备
集，使支持度和置信度通过所给的阈值。
在检验阶段，当出现一个新的样本，由一
组关联规则表示的分类器选择符合该样本
且具有最高置信度的规则，用此规则来预
测新的样本的类别。
? 例如，表 7-5给出训练数据集，支持度的阈
值是 2，置信度的阈值是 70%。
? 首先，扫描训练集，找出频繁项集，
F={a1,b2,c1,d3}，按支持度大小升序排列，
即,
F-list={a1,b2,c1,d3}
? 第二步，再次扫描训练集构建 FP树，如图
7-13所示。
▲ 构造步骤,
第一个样本,(a1,c1)为频繁项集中的值。
第二个样本,(a1,b2,c1)为频繁项集中的值。
第三个样本,(d3)为频繁项集中的值。
第四个样本,(a1,b2,d3)为频繁项集中的值。
第五个样本,(a1,b2,c1,d3)为频繁项集中的
值。
? 第三步，通过把所有的规则分区成不重叠
的子集生成分类规则。
a)包含 d3的规则； b)包含 c1不包含 d3的规则；
c)包含 b2但不包含 d3或 c1的规则；
d)仅包含 a1的规则。
▲ 包含 d3规则有,
(a1,b2,c1,d3):C,(a1,b2,d3):C和 (d3):A。
求训练集中所有频繁模式的问题被归结为挖
掘 d3-投影数据库中的频繁模式。本例
(a1,b2,d3)出现两次，支持度等于给定阈
值 2。同样，基于这个频繁模式的规则，
(a1,b2,d3)→C 有 100%的置信度 (超出阈值 )，
这是所给的数据库投影中生成的唯一规则。
? 第四步,d3的所有节点和它们相应的类标
识被合成为它们的 FP树的双亲节点。见图
7-13b所示。
? 对于 c1，投影数据库同样重复前面的步骤
挖掘剩下的规则集，然后是 b2投影数据库，
最后是 a1投影数据库。本例中,(a1,c1)是
支持度 3的频繁模式，但置信度小于阈值。
对于模式 (a1,b2)和 (a1)，有相同的结论。
因此，本例生成的仅有关联规则是
(a1,b2,d3)→C,支持度等于 2，置信度 100%。
