基于pvm的sliq算法的并行化研究

《基于pvm的sliq算法的并行化研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号UDC密级学号彳屈火季硕士学位论文论文题目：基于PVM的SLIQ算法的并行化研究论文作者：薛峙煮嘉、簟：‰警蓉：熊忠阳副教授重庆大学申请学位级别：硕士专业名称：计算机系统结构论文提交日期：2003年5月8日答辩日期：2003年6月11日学位授予单位：重庆大学授位日期：2003年6月30日答辩委员会主席：廖晓峰教授博导论文评阅人：李相枢教授欧灵副教授2003年5月8日重庆大学硕士学位论文中文摘要摘要数据挖掘作为知识发现过程关键技术，已逐步得到广泛应用。分类是数据挖掘及CRM的重要组成部分。SLIQ串行算法是由IBMAlmaden研究中心提出的一种高速可伸

2、缩的分类算法，广泛应用于大型商业的CRM、信用等级分级等领域。随着应用中数据量的迅速膨胀，采用并行技术是提高数据挖掘效率的一个重要途径。本文首先分析了串行SLIQ算法的原理和特点，针对其不足提出了一些改进方法，然后在基于PVM的环境下实现了算法的并行化，分析了算法的时间复杂度和加速比，提高了SLIQ算法的效率，具有一定的理论意义和实用价值。串行SLIQ算法通过预排序和广度优先技术，能够更加快速和准确地处理大量数据集，并能同时处理离散字段和连续字段。但是，原算法在计算决策树节点的最佳分割点的时候，存在着对属性和记录的多余计算问题。本文提出应该动态的删除叶子节点

3、的记录以及当前节点的祖先节点的分割属性，从而可以明显地减少不必要的计算以及属性表在磁盘和内存之问的IO交换操作。由于难以解决数据挖掘中任务划分的问题，SLIQ算法并行化的主要方向是实现数据的并行。SLIQ算法采用了新颖的数据结构，需要预先建立属性表，所以应该采取基于属性的数据分割策略。算法在把属性表和类表进行预先分配时采用的是静态平衡策略，对数据的分配按照数据量平均分配，将连续属性和离散属性分别平均分配到各个结点上；在执行分裂后，由于需要计算的属性不断减少，则采用了动态负载平衡的策略，通过消息传递的方式将部分计算任务分配给负载较轻的处理机单元。通过对串行和并

4、行算法时间复杂度的计算表明，当数据集充分大时，由于连续属性的排序计算操作分散到各个处理机单元上进行，显著降低了计算时间，从而可以得到近似于处理机个数的加速比，对于离散属性，本并行算法对串行算法的性能提高有限。关键词：SUQ，并行，算法，PVM重鏖查堂堡主兰垡笙塞茎苎塑茎ABSTRACTAsacriticalapplicationofKDD(KnowledgeDiscoveryinDatabase)，Dataminingismoreandmorewidelyused．ClassificationisanimportantpartofDataMingandapp

5、licationofCRM(CustomerRelationshipManagement)．SLIQalgorithmisafastandscalableclassificationalgorithmfordatamining，whichisbroughtforwardbyIBMAlmadenResearchCenterin1996．ThetypicalapplicationofSLIQliesinCRM，creditranking，etcinlargebusiness．Followedbytherapidextensionofdatasize，theusa

6、geofparalleltechnologyisaveryimportantmethodtoimprovetheefficiencyofDataMing．SLIQusesnovelpre—SOrtingandbreadth-firsttechniquestobuildadecisiontreefastandaccuratelyonalargedataset，andcandealbothcategoricalandnumericattributes．Buttheprimaryalgorithmcontainstheabundantcomputingonattr

7、ibuteandrecord．Thepaperbringforwardtheopinionthattherecordattachedtoleafnodeandtheattributesituatedattheancestorofpresentnodeoughttodeleteddynamically，ascarldecreaseunnecessarycomputingand10exchangeoperatingbetweenlocaldiskandmemory-Becauseofthedifficultyofsolutionoftaskdivision，th

8、ecoreidealoftheparallelSLI