探究决策树分类及剪枝算法研究

《探究决策树分类及剪枝算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、哈尔滨理工大学硕士学位论文决策树分类及剪枝算法研究姓名：张宇申请学位级别：硕士专业：计算机应用技术指导教师：郝忠孝20090301哈尔滨理工大学工学硕士学位论文决策树分类及剪枝算法研究摘要数据挖掘是从大量数据记录中挖掘出有价值的模式或规律等知识的复杂过程，已被广泛应用于金融、保险、运输及国防等领域。其中决策树分类算法是数据挖掘中最为广泛研究和应用的一个课题，所以决策树分类算法的研究具有很高的理论意义和应用价值。本文详细阐述了决策树的基本概念、主要研究内容和几种典型的决策树算法。由于在决策树生成过程中，会过度拟合训练数据，而且易受噪声数据的影响，所以剪枝操作是决策树生成过程中的一个重要步骤，本

2、文对四种主要的决策树剪枝算法进行了研究和比较。对多关系决策树分类算法(MRDTL)的研究与改进是本文的重点。在MRDTL算法生成的决策树中，用选择图表示树中节点。MRDTL算法直接在多个表上进行分类挖掘，而不需要将多个表连接成一个表后，再在该表上进行挖掘。MRDTL算法中的一个重要步骤是通过计算各限定词的信息增益来选择最优限定词，即选择具有最高信息增益的限定词添加到决策树中。MRDTL算法中在计算信息增益的时候会出现漏掉记录的情况，所以会导致计算计算信息增益的结果不准确。针对这一问题，本文改进了MRDTL算法中计算信息增益的方法。并对改进的计算方法进行了理论分析和实验验证。同时，根据改进的计

3、算信息增益的方法，相应的对建立补充表的算法进行了修改。关键词分类；决策树；多关系；选择图哈尔滨理工大学丁学硕士学位论文ResearchonDecisionTreeClassificationandPruningAlgorithmAbstractDataminingisacomplexprocessthatminesvaluablepatternsorrulesfromalargenumberofdatasets，andiswidelyusedinthefieldoffinance，insurance，transportationandnationdefense．Decisiontreealg

4、orithmisoneofthemostwidelystudiedandappliedsubjects．soresearchonthedecisiontreealgorithmhashightheoreticmeaningandrealisticvalue．Thebasicconceptofthedecisiontree，themainresearchingcontentandseveralclassicdecisiontreealgorithmsareintroduceddetailedly．Becauseofoverfittingthetrainingdatasetandtheeffec

5、tofnoisedataduringthebuildingprocess，pruningoperationbecomesoneofthemostimportantprocessesforbuildingadecisiontree．So，thepaperstudiesandcomparesfourmainpruningalgorithms．Thekeyofthedissertationistheresearchofmulti—relationaldecisiontreelearningalgorithmandthedevelopmentofit．Thenodesofthedecisiontre

6、emadebyMRDTLareexpressedinselectiongraph．Multi-relationaldecisiontreelearning(MRDTL)algorithmminesclassificationpatternsdirectlyfromseveraltablesinsteadofconnectingthemintoonetablefirstlyandthenminingpatterns．OneoftheimportantstepsinMRDTLisselectingtheoptimizationrefinementthroughcomputingtheirinfo

7、rmationgainandthenaddingitwhichhasthelargestinformationgaintothedecisiontree．However,themethodofcomputinginformationgaininMRDTLhasafaultofmissingrecordsandthiswillleadtotheincorrectcomputingresult．Aimingtot