探析决策树过拟合问题研究

《探析决策树过拟合问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、合肥工业大学硕士学位论文决策树过拟合问题研究姓名：王强申请学位级别：硕士专业：计算机应用技术指导教师：胡学钢20080501决策树过拟合问题研究摘要数据库知识发现是(KnowledgeDiscoveryinDatabases，简称KDD)是当前涉及人工智能和数据库等学科的一门相当活跃的研究领域，分类是其中的一个重要研究方向。决策树是分类中常用的模型之一，自1966年被提出以来已经得到了广泛的研究和应用。然而，由于种类偏见，过拟合等问题，使决策树优化成为研究人员关注的热点。本文基于针对可疑实例分析以及结点纯度差变化趋势两个方面分别对决策树构造算法中的

2、过拟合问题处理展开研究，主要工作如下：1．综述并分析了现有决策树经典算法及主要优化算法。2．提出了基于可疑实例影响度分析的改进的C4．5rules算法，将可疑实例进行有效划分，并计算其全局影响度大小，使得分类规则能有效避开可疑实例而更加正确的反应数据的真实情况。3．针对传统决策树过拟合现象普遍且大多数预剪枝算法严重依赖领域知识的问题，提出基于结点纯度差(PDN，PurityDistanceofNode)变化趋势的决策树优化算法，通过跟踪相邻父子结点问的最大纯度差变化趋势，判定停止建树的时机，可以独立于领域知识实现有效的预剪枝并很好地控制了过拟合的发

3、生，同时大大减小了决策树规模。一4．基于上述研究，实现了原型系统，从理论和实验上证明了所提出的算法的正确性和有效性。关键词：知识发现：分类；可疑实例；结点纯度；过拟合：OverfittingProblemResearchingonDecisionTreeAbstractKnowledgeDiscoveryinDatabases(KDD)isanactiveresearchdomainnowadays，anditisrelatedtoafewsubjectssuchasartificialintelligenceanddatabase．Classif

4、icationisanimportantresearchfieldinKDD．Decisiontreeisoneofthemodelsthatareoftenusedinclassification，andithasbeenwidelyresearchedandappliedsinceitwasproposedin1966．However,decisiontreehassomedisadvantagessuchasvarietybias，lackofanti·noisecapability，etc，andoptimizationofdecision

5、treehasbecomearesearchhotspot．Thedissertationfocusesonsuspectinstancesanalysisandprutitydistanceofnodetwoaspects，andthemainachievementsareasfollows：1．Anoverviewandanalysisofclassicalandoptimizeddecisiontreealgorithmsisputforward．2．TheImprovedC4．5rulesAlgorithmBasedOnImpact·Mea

6、surementOfTheSuspectInstances，devidethesuspectinstancesfromtheoriginaldataeffectivelyandcomputetheirimpact-measurementsbytheinformationgainesofit’Sattributes。thatbasedontheforwardworksclassificationrulescanavoidthesuspectinstanceseffectivelyandperformtheturesituationofthedata．

7、3．Accordingtotheproblemsthatover—fittingisseriousandpre-pruningdependonthefieldknowledgeoftraditionaldecisiontreealgorithm，DecisionTreePre-PruningBasedonPDNTrendalgorithmispresented，whichisbasedonpuritydistanceofthenodes，findthetimethatwhenstopthedecisiontreegrowingbywatchingt

8、hebiggestpuritydistancetrendofthenodes，achievepre—pruningnotd