决策树学习的剪枝方法.docVIP

决策树学习的剪枝方法 　　摘要：决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法，对噪音数据有很好的健壮性且能够学习浅析表达式。本论文主要介绍决策树学习的剪枝方法以及评价一棵决策树优劣的标准。 　　关键词：决策树学习 决策树学习的剪枝方法 　　1 简述 　　在决策树的生成过程中，如果对每一个分支都一直增长到恰好对训练样例完美地分类，这个策略并非总行的通的。事实上，当数据中有噪音或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，这个策略会遇到困难。 　　对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上却表现的更好时，我们说这个假设过度拟合训练样例。 　　图1描述了决策树学习的一个典型应用中过度拟合的影响。在这个例子中，ID3算法用来学习哪一种病人患有糖尿病。这副图的横轴表示决策树建造中树的结点总数，纵轴表示决策树做出的预测精度。实线表示决策树在训练样例上的精度，虚线表示在一套独立测试样例（没有被包含在训练样例中）上测量出的精度。可以看出，随着树的增长，在训练样例上的精度是单调上升的，然而，在独立的测试样例上测出的精度先上升后下降。说明对树的进一步精化尽管可以提高它在训练数据上的精度，却降低了它在测试样例上的精度。 　　过度拟合对于决策树?W习和其他一些学习算法是一个重要的实践难题，在决策树学习中解决这个问题的途径主要是对决策树进行修剪，有两种修剪方法：预修剪和后修剪。 　　2 决策树的后修剪学习算法 　　后修剪算法已经得到了广泛的应用，在这个算法中输入为一个未经修剪的决策树，输出为对它剪枝之后的决策树，这棵树是将原树中一个或几个子树删除所得的结果。剪枝过程中，将一些子树删除用一些叶结点来代替，这个叶结点所属的类用这棵子树中大多数训练实例所属的类代替，并且在相应的叶子上标记出所属这个类的训练实例所占的比例。 　　经过剪枝的决策树，对训练样例的错误率已经不为0，但由于在这种剪枝算法当中位于底层的子树将被优先剪掉，这些结点包含的实例很少，所以这种方法将减少噪音对决策树构造的影响。 　　后修剪算法有两种可能的剪枝策略，一种是自上而下的，一种是自下而上的。自下而上的算法是首先在最低层的内结点开始剪枝，剪去那些满足一定标准的内结点，生成新的决策树，然后在新的决策树上递归调用这个算法，直到没有新的结点可以剪枝为止。而与之相反，自上而下的算法是从根结点开始向下逐个考虑每个结点是否应该被剪枝。 　　后修剪的算法很多，这儿介绍两种比较常用的方法：错误率降低后修剪和规则后修剪。 　　（1） 错误率降低后修剪 　　错误率降低后修剪是一种自上而下的修剪方法，修剪过程由以下步骤组成：删除以此结点为根的子树；使它成为叶结点；把和该结点关联的训练样例的最常见分类赋给它。仅当修剪后的树对于验证集合的性能不比原树差时才删除该结点。 　　如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪是一个有效的方法.这个方法的主要缺点是当数据有限时，从中保留一部分用作验证集进一步减少了训练可以使用的样例。下面的这种方法在数据有限的许多实际情形下，也是有效的。 　　（2） 规则后修剪 　　规则后修剪是实践中一种发现高精度假设的非常成功的方法，这种方法的一个变体被成功的应用到C4.5系统中。规则后修剪包括下面的步骤： 　　1）从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生； 　　2）将决策树转化为等价的规则集，方法是从根结点到叶结点的每一条路径创建一条规则； 　　3）通过删除任何能导致估计精度提高的前件来修剪每一条规则； 　　4）按照修剪过的规则的估计精度对它们进行排序，并按照这样的顺序应用这些规则来分类后来的实例。 　　为什么修剪以前要把决策树转化成规则集呢？这样做主要有三个好处： 　　1）转化为规则集可以区分决策结点使用的不同上下文。因为贯穿决策结点的每条不同路径产生一条不同的规则，所以对于不同路径，关于一个属性测试的修剪决策可以不同。相反如果直接修剪树本身，只有两个选择，要么完全删除决策结点，要么保留它的本来状态。 　　2）转化为规则集消除了根结点附近的属性测试和叶结点附件的属性测试的区别。于是避免了凌乱的记录问题，比如，若是根结点被修剪了保留它下面的部分子树时如何保留它下面的部分子树时如何重新组织这棵树。 　　3）转化为规则集可以提高可读性。对人来说规则总是更容易理解的。 　　3 决策树预修剪学习算法 　　在生成一棵完整决策树的算法中都要求每一个叶结点中的训练实例都属于同一个类或者已经没有属性可供选择作为算法停止条件。然而在预修剪算法中，并不使用这个标准，而是在这个标准得到满足之前就停止继续扩展决策树。具体在什么时候停