决策树算法应用及并行化研究

电子科技大学UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA硕士学位论文MASTERTHESIS论文题目决策树算法应用及并行化研究学科专业计算机应用技术作者姓名李伟学号201121060481指导教师杨波教授I分类号密级UDC学位论文决策树算法应用及并行化研究李伟指导教师杨波教授电子科技大学成都（姓名、职称、单位名称）申请学位级别硕士学科专业计算机应用技术提交论文日期2014.03.26论文答辩日期2014.05.20学位授予单位和日期电子科技大学2014年6月29日答辩委员会主席评阅人IRESEACHONAPPLICATIONANDPARALELLIZATIONOFDECISIONTREEALGORITHMAMasterThesisSubmittedtoUniversityofElectronicScienceandTechnologyofChinaMajor:ComputerAppliedTechnologyAuthor:LiWeiAdvisor:Prof.YangBoSchool:SchoolofComputerScience&EngineeringII独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：日期：年月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）作者签名：导师签名：日期：年月日摘要III摘要在信息科技飞速发展的今天，各行各业每天都会产生大量的数据，这些数据中蕴含着丰富的知识。对于善于运用数据分析的用户来讲这就是一笔财富，而对于不了解或者不会对数据进行发掘的用户就是数据垃圾。对于不同类型的数据需运用不同的挖掘算法，但传统的数据挖掘算法处理的数据量是有限的，当数据量显著增大时，就需要更合适的数据挖掘算法来处理。云计算是近几年兴起的新概念，在计算机领域，从某种意义上来讲，可以把云计算当做一种网络，一种可以处理海量数据的新模式。开发云计算架构下的数据挖掘系统是当前处理海量数据挖掘的一种趋势。通过对传统算法的改进，将算法移植到云计算平台，借助云技术的并行化处理能力，海量数据的挖掘问题也将迎刃而解。基于以上的研究背景，首先本文将对数据挖掘技术和云计算平台进行研究，然后对数据挖掘决策树算法进行处理，结合实际工作情况，对C4.5算法的应用进行研究，并使用罗比达法则对算法效能进行改进。然后根据海量数据挖掘的要求，将能产生简单决策树结构的算法-CART，进行基于随机森林模型的改进。随机森林模型对于决策树建树的数据类型、数据缺失、属性类别以及决策属性类别多值要求都不高，基于这些优点将CART算法应用到随机森林模型中能克服CART算法的弊端。最后本文将对算法并行化进行研究，通过对几个并行模型的研究，选择最合适的MapReduce编程模型将改进的CART算法实现。通过实验，将改进的CART算法在串行和并行模式下分析大量数据，实验表明算法在有效性、处理速度和加速比等方面都有较好的表现，以此验证算法改进的有效性。关键词：云计算，决策树，C4.5，CART，MapReduceABSTRACTIVABSTRACTNowadays,withtherapiddevelopmentofinformationtechnology,massivedatawhichcontainawealthofknowledgearecreatedamongbusinesses.Thesedataarefortuneforthosewhoaregoodatdiscoveringknowledge,whilearedatarubbishforthosewhoarenot.Differentdataminingalgorithmsshouldbeadoptedfordifferenttypesofdata,howevertraditionalalgorithmscanonlyprocesslimitedamountofdata.Therefore,weneedmoresuitabledataminingalgorithms.Cloudcomputingisanewconcept,incomputersciencefield,cloudcomputingcanbeconsideredasnetworkoranewpattentodealwithmassivedatatosomeextent.It’satrendofdevelopingmassivedataminingalgorithmsbasedoncloudcomputingarchitechture.Withtheparallelprocessingcapabilities,wecanimprovethetraditionalalgorithmsandtransplanttheimprovedalgorithmsintocloudplatform,andthenwecanhandlemassivedataminingproblemseasily.Basedontheresearchbackgroundabove,thisthesiswillfirstlydosomeresearchondataminingtechnologyandcloudcomputingplatform.Afterprocessingthedecisiontreealgorithm,thisthesisfocusonthepracticalapplicationindaliywork,atthesametime,byusingtheL’Hospitalrulestoimprovethisalgorithmforthecalculatingperformance.Secondly,accordingtothedemandingofminingmassivedata,thisthesisimprovestheCARTalgorithm,whichcanproducesimplestructureddecisiontreebyusingrandomforestmodel.Asthereasonthattherandomforestmodelisoflessdemandingformissingdata,attributecategoryandmulti-valuedofdecisionattribute,andsoon,applyingtheCARTalgorithmtotherandomforestmodelcanovercomethedrawbacksofCART.Lastly,weresearchontheparallelizationoftheimprovedalgorithm.Bycomparingseveralparallelmodels,wechoosethemostsuitableMapReducemodeltoimplementtheimprovedCARTalgorithm.Wedoexperimentstoanalysismassivedatainserialandparallelmode,theresultsshowthatthenewalgorithmachievesbetterperformanceintheaspectsofeffectiveness,algorithmprocessingspeedandacceleration.Keywords:CloudComputing，DecisionTree，C4.5，CART，MapReduce目录V目录第一章绪论.........................................................11.1课题背景及研究意义............................................................................................................11.2研究现状...............................................................................................................................21.2.1数据挖掘的研究现状.................................................................................................21.2.2数据挖掘中决策树算法并行化研究现状.................................................................41.3本文主要工作及论文结构....................................................................................................5第二章云计算和数据挖掘技术概述.....................................62.1数据挖掘技术概述................................................................................................................62.1.1数据挖掘技术及知识发现特征分析.........................................................................62.1.2数据挖掘模式.............................................................................................................62.1.3数据挖常用算法.........................................................................................................72.2云的概念...............................................................................................................................82.2.1云相关的网络技术...................................................................................................102.2.2云的平台...................................................................................................................112.3本章小结....................................