决策树过度拟合.doc

决策树学习的过拟合问题 姓名： 专业：通信与信号系统 学号： 一 决策树学习简介 决策树学习是一种逼近离散值目标函数的方法，这种方法将从一组训练数据中学习到的函数表示为一棵决策树。决策树叶子为类别名，其他的结点由实体的特征组成，每个特征的不同取值对应一个分枝。若要对一个实体分类，从树根开始进行测试，按特征的取值向下进入新结点，对新结点进行测试，过程一直进行到叶结点，实例被判为属于该叶子结点所标记的类别。它可以表示任意的离散函数和离散特征，可以将实例分成两个或多个类。 二 决策树学习的过拟合问题产生原因 决策树是判断给定样本与某种属性相关联的决策过程的一种表示方法。决策树的每个内部结点是对属性的一个测试，每个分支代表一个测试输出，每个叶结点表示某个类别或类别的分布。当一个待分类的样本沿根结点经内部结点的测试达到某个叶结点时，则判定该样本属于此叶结点所标识的类别。 建立决策树的过程，即树的生长过程是不断地把训练数据集进行划分的过程，每次划分对应一个属性，也对应着一个内部结点，划分所选的属性应使划分后的分组“差异”最大。决策树生成算法的不同主要体现在对“差异”的衡量方式上。 通常直接生成的完全决策树不能立即用于对未知样本进行分类。由于完全决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所以此时它不是一棵分析新数据的最佳决策树。一棵完全决策树能非常准确地反映训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象一般称为“过拟合”。 过度拟合定义为：给定一个假设，如果在假设空间上存在另一个假设，使得在训练集上H的错误率差比小，而在测试集上的错误率却比要大，那么称假设过度拟合训练数据。 通常导致决策树过拟合的原因有多种，但主要有以下两种： ⑴噪声数据导致过分拟合 在现实世界中，数据伴有随机的错误或噪声往往是难以完全避免的。例如在对用户是否离网的分类中，目标变量“是否流失”可能被错误的标记，利用此数据拟合得到的模型，就有可能因为拟合错误标记的训练记录，导致在模型应用阶段产生错误分类，不能很好的进行推广。 ⑵缺乏代表性样本导致过分拟合 在训练数据缺乏具有代表性的样本的情况下，往往需要继续细化模型才能得到较好拟合训练集的模型，这样得到的模型同样可能具有较高的泛化误差。 三 决策树过拟合问题的解决方法 由于实际问题中存在太多不确定因素，用决策树算法对训练集分类时，所得到的决策树规模太大，难免会过度拟合训练数据。而实际上大而复杂的决策树并不意味着可以得到更加准确的规则集。另外，寻找最小决策树被证明是NP问题，所以在现实中找不到绝对的最小决策树。为了避免过度拟合，我们只能通过分析造成过度拟合的原因，来寻找一些简化技术来修剪决策树。 避免决策树学习中过度拟合的途径可以被分为两大类：预剪枝方法和后剪枝方法。 ㈠预剪枝（pre-pruning）法 预剪枝法通过提前停止分支的生长过程来实现， 具体在什么时候停止决策树的生长有多种不同的方法： a.一种最为简答的方法就是在决策树到达一定高度的情况下酒停止树的生长； b.到达此结点的实例具有相同的特征向量，而不必一定属于同一类，也可以停止生长。这种情况可以处理数据中的数据冲突问题； c.到达此结点的实例个数小于某一个阈值也可以停止树的生长； d.计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展。如果在最好的情况下的扩展增益都小于阈值，即使有些叶子结点的实例不属于同一类，也停止树的增长。 该方法的优点在于避免产生过分拟合训练数据的过于复杂的子树，但是，我们很难为提前终止选取正确的阀值，阀值太高将导致拟合不足的模型，而阀值太低则不能充分地解决过分拟合问题。此外，即便是使用已有的属性测试条件得不到显著的增益，接下来的划分也可能产生较好的子树。 预剪枝有一个缺点，即视野效果问题。也就是说在相同的标准下，也许当前的扩展会造成过度拟合训练数据，但是更进一步的扩展能够满足要求，也有可能准确地拟合训练数据。这将使得算法过早地停止决策树的构造。 ㈡后剪枝（post-pruning）法 后剪枝法从一个“充分生长”树中，按照自底向上的方式修剪掉多余的分支，修剪有两种方法： 用新的叶子结点替换子树，该叶子结点的类标号由子树记录中的多数类确定； 用子树中最常用的分支代替子树。J48决策树算法采用了子树提升与子树替换的修剪策略。 计算修剪前后的预期分类错误率，如果修剪导致预期分类错误率变大，则放弃修剪，保留相应结点的各个分支，否则就将相应结点分支修剪删去。在产生一系列经过修剪的决策树候选之后，利用一个独立的测试数据集，对这些经过修剪的决策树的分类准确性进行评价， 保留下预期分类错误率最小的 （修剪后） 决策树。 与预剪枝相比，后剪枝倾向于产生更好的结果，因为与预剪枝不同