决策树过拟合

1、决策树学习的过拟合问题姓名：专业：通信与信号系统学号:一决策树学习简介决策树学习是一种逼近离散值目标函数的方法， 这种方法将从一组训练数据 中学习到的函数表示为一棵决策树。 决策树叶子为类别名，其他的结点由实体的 特征组成，每个特征的不同取值对应一个分枝。 若要对一个实体分类，从树根开 始进行测试，按特征的取值向下进入新结点，对新结点进行测试，过程一直进行 到叶结点，实例被判为属于该叶子结点所标记的类别。它可以表示任意的离散函 数和离散特征，可以将实例分成两个或多个类。二 决策树学习的过拟合问题产生原因决策树是判断给定样本与某种属性相关联的决策过程的一种表示方法。决策树的每个内部结点是对属性的

2、一个测试，每个分支代表一个测试输出，每个叶结 点表示某个类别或类别的分布。当一个待分类的样本沿根结点经内部结点的测试 达到某个叶结点时，贝U判定该样本属于此叶结点所标识的类别。建立决策树的过程，即树的生长过程是不断地把训练数据集进行划分的过 程，每次划分对应一个属性，也对应着一个内部结点，划分所选的属性应使划分 后的分组“差异”最大。决策树生成算法的不同主要体现在对“差异”的衡量方 式上。通常直接生成的完全决策树不能立即用于对未知样本进行分类。由于完全决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所 以此时它不是一棵分析新数据的最佳决策树。一棵完全决策树能非常准确地反映

3、 训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预 测，这种现象一般称为“过拟合”。过度拟合定义为：给定一个假设H，如果在假设空间上存在另一个假设 H '， 使得在训练集上H的错误率差比H'小，而在测试集上H的错误率却比H '要大， 那么称假设H过度拟合训练数据。通常导致决策树过拟合的原因有多种，但主要有以下两种：噪声数据导致过分拟合在现实世界中，数据伴有随机的错误或噪声往往是难以完全避免的。例如在 对用户是否离网的分类中，目标变量“是否流失”可能被错误的标记，利用此数 据拟合得到的模型，就有可能因为拟合错误标记的训练记录， 导致在模型应用阶 段产生

4、错误分类，不能很好的进行推广。缺乏代表性样本导致过分拟合在训练数据缺乏具有代表性的样本的情况下，往往需要继续细化模型才能得 到较好拟合训练集的模型，这样得到的模型同样可能具有较高的泛化误差。三 决策树过拟合问题的解决方法由于实际问题中存在太多不确定因素， 用决策树算法对训练集分类时，所得 到的决策树规模太大，难免会过度拟合训练数据。而实际上大而复杂的决策树并 不意味着可以得到更加准确的规则集。 另外，寻找最小决策树被证明是 NP问题, 所以在现实中找不到绝对的最小决策树。 为了避免过度拟合，我们只能通过分析 造成过度拟合的原因，来寻找一些简化技术来修剪决策树。避免决策树学习中过度拟合的途径可以

5、被分为两大类：预剪枝方法和后剪枝方法。预剪枝(pre-pruning )法预剪枝法通过提前停止分支的生长过程来实现，具体在什么时候停止决策树的生长有多种不同的方法：a. 一种最为简答的方法就是在决策树到达一定高度的情况下酒停止树的生长；b. 到达此结点的实例具有相同的特征向量， 而不必一定属于同一类，也可以 停止生长。这种情况可以处理数据中的数据冲突问题；c. 到达此结点的实例个数小于某一个阈值也可以停止树的生长；d. 计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行 扩展。如果在最好的情况下的扩展增益都小于阈值，即使有些叶子结点的实例不 属于同一类，也停止树的增长。该方法的优

6、点在于避免产生过分拟合训练数据的过于复杂的子树，但是，我们很难为提前终止选取正确的阀值， 阀值太高将导致拟合不足的模型， 而阀值太 低则不能充分地解决过分拟合问题。 此外，即便是使用已有的属性测试条件得不 到显著的增益，接下来的划分也可能产生较好的子树。预剪枝有一个缺点，即视野效果问题。也就是说在相同的标准下，也许当前 的扩展会造成过度拟合训练数据， 但是更进一步的扩展能够满足要求， 也有可能 准确地拟合训练数据。这将使得算法过早地停止决策树的构造。后剪枝(post-pruning )法后剪枝法从一个“充分生长”树中，按照自底向上的方式修剪掉多余的分支， 修剪有两种方法：(1) 用新的叶子结点

7、替换子树，该叶子结点的类标号由子树记录中的多数类确定；(2) 用子树中最常用的分支代替子树。J48决策树算法采用了子树提升与 子树替换的修剪策略。计算修剪前后的预期分类错误率，如果修剪导致预期分类错误率变大， 则放 弃修剪，保留相应结点的各个分支，否则就将相应结点分支修剪删去。 在产生一 系列经过修剪的决策树候选之后，利用一个独立的测试数据集，对这些经过修剪 的决策树的分类准确性进行评价，保留下预期分类错误率最小的(修剪后)决 策树。与预剪枝相比，后剪枝倾向于产生更好的结果，因为与预剪枝不同，后剪枝 是根据完全生长的树做出的剪枝决策，预剪枝则可能过早终止决策树的生长。下面介绍三种主要的后剪枝方

8、法：悲观错误剪枝 (Mistic Error Pruning ， PEP)，最小错误剪枝(Minimum Error Pruning ， MEP)代价复杂度剪枝 (Cost Complexity Pruning ，CCP。悲观错误剪枝(PEP悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补 REP中的缺陷，在评价子树的训练错误公式中添加 了一个常数，假定每个叶结点都自动对实例的某个部分进行错误的分类。该方法需要对决策树上所有的非叶子结点 A进行计算分析。搜索时从决策树 的根结点开始，计算每个分枝结点被剪后或者是被子树替换后的期望错误率。 为 了使数据

9、源的数据特性得到最大限度的保留，把数据源作为一个整体，而不是将 其分为训练集和测试集两个部分。 因此需要考虑最坏的情况，取置信区间的上限 作悲观情况下的错误估计。给定一个置信度C ,错误总数服从N项贝努利 (Bernoulli) 分布是很明显的，因而有概率等式如下：p口一 44 c q(1 q)/N在该公式中，q表示估计的错误率，N表示被修剪的子树下的实例总数， 假设E表示修剪后出现的错误实例数，那么f = E / N是实际观测到的错误率。令J，取置信区间的上限作为该结点的悲观错误率估计，则可得该结点的错误率计算公式如下:N2Z1Nf + 2N4N 2在该公式中，根号前的“ ”号表示取置信区间

10、的上限，q就是估计的悲观 错误率。给定一个期望错误率最高阈值C。当剪去结点A时，如果导致的错误率 q不高于给定的阀值C ,贝朋去结点A下的子树；否则，保留结点A下的子树。最小错误剪枝(MEPMEP算法希望通过剪枝得到一棵相对于独立数据集来说具有最小期望错误 率的决策树。所使用的独立数据集是用来简化对未知样本的错分样本率的估计 的，并不意味真正使用了独立的剪枝集，实际情况是无论早期版本还是改进版本 均只利用了训练集的信息。对于k类问题，定义样本到达结点t且属于第i类的期望概率为：P(t)二n't)，PaE m ；其中为由训练集得来的属于第i类的先验概率，m表示n (t)先验概率对期望概率

11、Pi(t)的影响程度，反映了剪枝的程度，为简单起见认为所有类别的m均相同。当一个新样本到达结点t而被分类时，结点t的期望错误率 表示为EER (t)二 min 1 Pi(t) = min n (t) n i(t) ，(1 Pa)m/ n (t)mii当m二k且pai =1/k时，可得EER (t)二 min n(t) ni(t) - k -1 / n(t) - k二e(t) ' k -1 / n(t) - ki在MEP中，自底向上计算每个内部结点t的期望错误率，称为静态错误STE (t)，STE (t)二e(t) k -1 / n(t) - k；树的期望错误称为动态错误 DYE (t)

12、，DYE (t)是其孩子结点的期望错误的加权和MEP算法自底向上顺序遍历完全决策树Tn并计算子树T的静态错误STE(t) 和动态错误DYE (t)，当子树Tt的静态错误和动态错误满足 STE空DYE (t)时则 剪枝，并用一个叶结点来代替，该叶结点所标识的类别由“大多数原则”来确定。代价复杂度剪枝(CCPCCP算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本 集，使得生成的的每个非叶子结点都有两个分支。因此，CCP算法生成的决策树是结构简洁的二叉树。CCP算法是通过在完全生长的树上剪去分枝实现的，通过删除结点的分支来 剪去树结点。最下面未被剪枝的结点成为树叶。 CCP用的成本复杂性

13、标准是分类 树的简单误分(基于验证数据的)加上一个对树的大小的惩罚因素。惩罚因素是有 参数的，我们用a表示，每个结点的惩罚。成本复杂性标准对于一个数来说是Err (T) a L(T),其中Err (T )是验证数据被树误分部分，L (T )是树T的叶结点数， a是每个结点的惩罚成本：一个从0向上变动的数字。当a = 0对树有太多的结点 没有惩罚，用的成本复杂性标准是完全生长的没有剪枝的树。在剪枝形成的一系 列树中，从其中选择一个在验证数据集上具有最小误分的树是很自然的，我们把这个树成为最小误分树。三种算法的比较在以上三种算法中，对于给定剪枝集，PEP剪枝算法中当某个子树T满足剪 枝条件时将不再对其后裔进行剪枝判断，因此PEP方法收敛速度较快，但最坏情况下仍然每个结点都要遍历，为线性复杂度。在MEP剪枝算法中m的选择比较关 键，因为剪枝程度通过m控制，m越大剪枝越严重。当m接近无穷时Pi(t)=mj， 而是对训练集中属于第i类样本所占比重的估计，只有当剪枝到只剩一个叶结点 时期望错误率最少，此时剪枝程度最大，m较小时剪枝程度也较小。大多数情况 下剪枝并不会使预测精度降低，只有个别邻域可能较难控制；而对于所生成