《数据把掘概念与技术》第七章（7-4） 修剪决策树

7.4修剪决策树 决策树修剪的主要任务是抛弃一个或更多 的子树,并用叶替代这些子树,使决策树 首单化。 问题是修剪后的结果能达到我们期望算法 降低预测误差率来提高分类器的质量,但 差率计算并不简单。 °评价预测误差的一个可行方法是用另外 个新的有效检验样本,或用第四章中讲述 的交叉确认法

7.4 修剪决策树 • 决策树修剪的主要任务是抛弃一个或更多 的子树，并用叶替代这些子树，使决策树 简单化。 • 问题是修剪后的结果能达到我们期望算法 降低预测误差率来提高分类器的质量，但 误差率计算并不简单。 • 评价预测误差的一个可行方法是用另外一 个新的有效检验样本，或用第四章中讲述 的交叉确认法

)在具备可用的训练和检验样本的情況下 决策树修剪的基本思想是去掉那些对未知 检验样本的分类精度没有帮助的部分树 子树),生成一个更简单,更容易理解的 树 有两种改进的递归分区方法 1.在某些情况下决定不把样本集合分区 得更细。停止准则通常是基于些统计检 验,如X检验:如果分区前后分类精度没 有显著的不同,那么用当前的点作为 叶。该方法称为预剪法

• 在具备可用的训练和检验样本的情况下， 决策树修剪的基本思想是去掉那些对未知 检验样本的分类精度没有帮助的部分树 (子树)，生成一个更简单，更容易理解的 树。 • 有两种改进的递归分区方法： 1. 在某些情况下决定不把样本集合分区 得更细。停止准则通常是基于一些统计检 验，如χ 2检验：如果分区前后分类精度没 有显著的不同，那么用当前的点作为一个 叶。该方法称为预剪法

2用所选的精度准则回头去除树的一些点。 称为后修剪。 yC45采用后修剪方法,但它用具体的方法评 佔预测误差率,该方法称为悲观修 基本思想 对于树中的每个节点,可以用二项式分布统 计表计算置信极限的上限的估计值。参数 L是所给节点的不和E的函数。C4.5用25% 置信度,比较所给节点7的U5%(/E)与它 的叶的加权置信度。权值是每个叶的样本的 数

2.用所选的精度准则回头去除树的一些点。 称为后修剪。 • C4.5采用后修剪方法，但它用具体的方法评 估预测误差率，该方法称为悲观修剪。 • 基本思想： 对于树中的每个节点，可以用二项式分布统 计表计算置信极限的上限Ucf的估计值。参数 Ucf是所给节点的|Ti |和E的函数。C4.5用25% 置信度，比较所给节点Ti的U25%(|Ti |/E)与它 的叶的加权置信度。权值是每个叶的样本的 总数

基本思想: 如果子树中的某个根节点的预测误差比叶的 (子树的预测误差加权和小,那么用它 的根节点替换该子树,变成修剪后的树的一 例如,决策树的子树如图7-9乐示,根节点的 子节点是用相应的类和参数(/)表示的叶。 XI 类2(16,1 A=1 A=2 A=3 类1(6,0) 类1(90) 类2(1,0) 图7-9用一个叶节点替换修剪子树

• 基本思想： 如果子树中的某个根节点的预测误差比叶的 U25% (子树的预测误差)加权和小，那么用它 的根节点替换该子树，变成修剪后的树的一 个新叶。 • 例如，决策树的子树如图7-9所示，根节点的 子节点是用相应的类和参数(|Ti |/E)表示的叶

)问题是估计修剪子树并用它的根节点替换 它作为一个新的归纳叶节点的概率 ③为了分析用叶节点替换子树的概率,必须计 算被替换节点和初始树的预测误差PE。 用默认置信度25%,上限置信极限可从统 计表中求得: L256(60)=0.206,U25%(9,0)=0.143 L25(1,0)=0.750,U25(16,1)=0.157

• 问题是估计修剪子树并用它的根节点替换 它作为一个新的归纳叶节点的概率。 • 为了分析用叶节点替换子树的概率,必须计 算被替换节点和初始树的预测误差PE。 • 用默认置信度25%，上限置信极限可从统 计表中求得： U25%(6,0)=0.206, U25%(9,0)=0.143 U25%(1,0)=0.750, U25%(16,1)=0.157

③初始树和被替换节点的预测误差是 PEe=6*0.206+9*0.143+1*0.750=3,257 PE tree 16米0.157=2.512 被替换的节点比当前的决策树的预测误差低, 修剪决策树并用新的叶节点替换子树是可 行的

• 初始树和被替换节点的预测误差是： PEtree=6*0.206+9*0.143+1*0.750=3.257 PEtree=16*0.157=2.512 被替换的节点比当前的决策树的预测误差低， 修剪决策树并用新的叶节点替换子树是可 行的

3骨见的六种修剪技术 1. MCCP Minimal cost-complexity Pruning)-F3 于CRA系统 2. REP(Reduced Error Pruning 3,MEP(Minimal Error Pruning) 4PEP( Pessimistic Error Pruning)-用于ID3 5EBP( Error Based Pruning)-用于C4.5。 6. bootstrap

• 常见的六种修剪技术： 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

75c4.5算法:生成决策规则 大型的决策树较难理解,因为每个节点都 有先行节点的检验结果建立的具休环境。 为了理解它,可以把到达每个叶的路径转 换成 IF-THEN生成规则。这种规则叫做决策 规则。 所有叶节点的决策规则集能够与树节点 样对样本进行分类

7.5 C4.5 算法：生成决策规则 • 大型的决策树较难理解，因为每个节点都 有先行节点的检验结果建立的具休环境。 为了理解它，可以把到达每个叶的路径转 换成IF-THEN生成规则。这种规则叫做决策 规则。 • 所有叶节点的决策规则集能够与树节点一 样对样本进行分类

图710所示是决策树转换成决策规则的一 例子 根 If a=l andb=1 Then类1 A A=2 转换 If A=l and b=2 〓嚣z〓〓〓E X2: B Then类2 路径转换为规则 B B=2 If a=2 Then类1 类1 a)决策树 b)决策规则 图7-10决策树到决策规则的转换

• 图7-10所示是决策树转换成决策规则的一 个例子

分类模型中决策规则的数量可能非常大 可以删除那些不景响规则集的正确性的多 佘条件,对规则进行概化 规则条件的删除准则如下 设规则R是: If A Then类C 更一般化的规则R是: If a Then类C 其中A是A(A=AUX)中删掉条件X得到的。 数据库中满足条件A的每个样本可以满足也 可以不满足扩展条件A

• 分类模型中决策规则的数量可能非常大， 可以删除那些不影响规则集的正确性的多 余条件，对规则进行概化。 • 规则条件的删除准则如下： 设规则Ｒ是：If A Then 类-C 更一般化的规则R’是：If A’ Then 类-C 其中A’是A(A=A’∪X)中删掉条件X得到的。 • 数据库中满足条件A’的每个样本可以满足也 可以不满足扩展条件A