决策树误差降低剪枝算法的改进研究

发布时间：2021-10-11 00:45

　　决策树是数据挖掘中常用的分类和回归方法之一。本文主要讨论分类决策树。顾名思义,决策树为树状结构,从根结点开始逐渐开枝散叶,长成一棵具有多个分支和结点的大树。决策树遵循的是“分而治之”的策略,在分类问题中,每次划分选择一个特征变量将样本的集合分为若干部分,然后再对各部分进行相同的操作,直到特征变量全部选取完毕,每个样本都落入某个叶子结点中,这个叶子结点的类别由多数原则来决定。决策树具有计算复杂度不高、输出结果易于理解、对中间值的缺失不敏感、可以处理不相关特征数据等优点,因此在分类问题中应用较为广泛。一般来说,决策树的训练过程包括特征选择、树的生长、剪枝三个步骤。其中根据特征选择的不同标准,决策树可分为ID3、C4.5、CART三类,在实践中这三种标准生成的树的性能差异较小,几乎可以忽略不计。由于实际问题中变量的个数较多,由这些数据得到的决策树往往会变得大而复杂。然而,经验表明,大而复杂的决策树不仅解释起来较为困难,而且往往并不意味着可以得到更准确的分类结果,这说明决策树的生长具有过拟合的倾向。因此对决策树进行剪枝是很有必要的。剪枝可以简化决策树,提高泛化性能,避免对训练集的过拟合,是决策... 

【文章来源】：山东大学山东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：46 页

【学位级别】：硕士

【部分图文】：

图１．２：分类规则举例??

?山东大学硕士学位论文???ｘ＜０．４２??＇?＼?（?＼??ｙ＜０．４７?ｙ＜０．３３??ｊＴ＇ｈ??图１．２：分类规则举例??下图是按照决策树对应的分类规则对于二维平面的划分。??厶??４????￡＞■＿???－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－０??２?－?｜?。??！?ａ??〇?〇?！?＾??ｏ?；??０?０?０＿２?０?４?〇ｅ?０．８??Ｘ??图１．３：二维平面的划分??－３－??

?山东大学硕士学位论文???３．剪枝决策树容易产生过拟合的倾向，一般来说，过拟合的原因主要有以??下几个：（１）建模样本抽取错误，包括（但不限于）样本数量太少，抽样方法错??误，抽样时没有足够正确地考虑业务场景或业务特点，导致抽出的样本数据??不能有效代表业务逻辑或业务场景；（２）样本里的噪声数据干扰过大，大到??模型过分记住了噪声特征，反而忽略了真实的输入输出间的关系；（３）训练??模型过度导致模型非常复杂、参数多；（４）建模时的“逻辑假设”到了模型应??用时己经不能成立了。任何预测模型都是在假设的基础上才可以搭建和应用??的，常用的假设包括：假设历史数据可以推测未来，假设业务环节没有发生??显著变化，假设建模数据与后来的应用数据是相似的，等等。如果上述假设??违反了业务场景的话，根据这些假设搭建的模型当然就无法有效应用了。??基于上述原因，需要对决策树进行剪枝以缩小树结构的规模、缓解过??拟合。对于某个结点进行剪枝操作，就是把该结点延伸出的子树全部“删??除”掉，仅保留该结点本身。显然，经过剪枝操作的结点会变成叶子结点，??该结点内的样本类别由多数原则确定。??下图给出剪枝的示意图。??「???！?！?〇??＾?Ｖ?＼????＼??Ｉ⑦〇Ｉ〇?〇??／?＼！??！?〇?〇??Ｌ?１??图１．４：决策树剪枝示意图??剪枝方法和程度对决策树泛化能力的影响相当显著，Ｍｉｎｇｅｒｓ１１１进行??的实验研究表明，在数据带有噪声时通过剪枝可将决策树的泛化性能提??高２５％，因此对剪枝技术进行研究是很有必要的。??一?７－??


本文编号：3429463