文档介绍：修剪决策树
决策树修剪的主要任务是抛弃一个或更多的子树,并用叶替代这些子树,使决策树简单化。
问题是修剪后的结果能达到我们期望算法降低预测误差率来提高分类器的质量,但误差率计算并不简单。
评价预测误差的一个可行方法是用另外一个新的有效检验样本,或用第四章中讲述的交叉确认法。
在具备可用的训练和检验样本的情况下,决策树修剪的基本思想是去掉那些对未知检验样本的分类精度没有帮助的部分树(子树),生成一个更简单,更容易理解的树。
有两种改进的递归分区方法:
1. 在某些情况下决定不把样本集合分区得更细。停止准则通常是基于一些统计检验,如χ2检验:如果分区前后分类精度没有显著的不同,那么用当前的点作为一个叶。该方法称为预剪法。
。称为后修剪。
,但它用具体的方法评估预测误差率,该方法称为悲观修剪。
基本思想:
对于树中的每个节点,可以用二项式分布统计表计算置信极限的上限Ucf的估计值。参数Ucf是所给节点的|Ti|和E的函数。%置信度,比较所给节点Ti的U25%(|Ti|/E)与它的叶的加权置信度。权值是每个叶的样本的总数。
基本思想:
如果子树中的某个根节点的预测误差比叶的U25% (子树的预测误差)加权和小,那么用它的根节点替换该子树,变成修剪后的树的一个新叶。
例如,决策树的子树如图7-9所示,根节点的子节点是用相应的类和参数(|Ti|/E)表示的叶。
问题是估计修剪子树并用它的根节点替换它作为一个新的归纳叶节点的概率。
为了分析用叶节点替换子树的概率,必须计算被替换节点和初始树的预测误差PE。
用默认置信度25%,上限置信极限可从统计表中求得:
U25%(6,0)=, U25%(9,0)=
U25%(1,0)=, U25%(16,1)=
初始树和被替换节点的预测误差是:
PEtree=6*+9*+1*=
PEtree=16*=
被替换的节点比当前的决策树的预测误差低,修剪决策树并用新的叶节点替换子树是可行的。
常见的六种修剪技术:
(Minimal plexity Pruning)-用于CRAT系统。
(Reduced Error Pruning) 。
(Minimal Error Pruning) 。
(Pessimistic Error Pruning) –用于ID3。
(Error Based Pruning)-。
。
算法:生成决策规则
大型的决策树较难理解,因为每个节点都有先行节点的检验结果建立的具休环境。为了理解它,可以把到达每个叶的路径转换成IF-THEN生成规则。这种规则叫做决策规则。
所有叶节点的决策规则集能够与树节点一样对样本进行分类。
图7-10所示是决策树转换成决策规则的一个例子。
分类模型中决策规则的数量可能非常大,可以删除那些不影响规则集的正确性的多余条件,对规则进行概化。
规则条件的删除准则如下:
设规则R是:If A Then 类-C
更一般化的规则R’是:If A’ Then 类-C
其中A’是A(A=A’∪X)中删掉条件X得到的。
数据库中满足条件A’的每个样本可以满足也可以不满足扩展条件A。