并行fp-growth关联规则算法研究

《并行fp-growth关联规则算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、屯各Ｈ故丈達ＵＮＦＣＭＩＮＡＩＶＥＲＳＩＴＹＯＦＥＬＥＣＴＲＯＮＩＣＳＣＩＥＮＣＥＡＮＤ下ＥＣＭＮ０Ｌ０９Ｙ〇专业学位硕±学位论文ＭＡＳＴＥＲＴＨＥＳＩＳＦＯＲＰＲＯＦＥＳＳＩＯＮＡＬＤＥＧＲＥＥ纖．－一．片．气斬．＇，－？．；．－＿Ｉ．■，＇．‘－－．Ｖ论支题目并行巧－ｇｒｏｗｔｈ关联规则算獅焼亡专业学位类如工程硕壬学号２０１３２２２２０２１５作者姓名类书青？；Ｉ指营教师文军副教授—

2、独创性声明本人声明所呈交的学位论文廷本人在导师指导Ｆ进行的研巧工作及取得的研究成果。据我所知，除了文中特別加臥标注和致谢的地方夕Ｋ论文中不包含其他人百经发表或撰写过的研究成果，也不包含为获得电子科技大学或巧它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均曰在论文中作了明确的说明并表示谢意。作者整名＝若车＾日期：方）成年＾月＾日论文使用授权本学位论文作者完全了解电子科技大学巧关保留、使用学位论文的规定，有权保留并向国家有关部口或机构送交论文的复印件和磁蟲，。＾本人授权电子科技大学

3、可＞允许论文被查阅和借阅＾＾将学位论文的全部或部分，Ｗ采用影印、缩印或扫描内容编入有关数据库进行检索可等制手段保存、汇编学位论文。复（保密的学位论文在解密后应遵）巧此规定作者签：心名：书导师签名寺导６：年月弓日期日分类号密级注1UDC学位论文并行FP-growth关联规则算法研究（题名和副题名）娄书青（作者姓名）指导教师文军副教授电子科技大学成都（姓名、职称、单位名称）申请学位级别硕士专业学位类别工程硕士工程领域名称软件工程提交论文日期2016.03.18论文答辩日期2016.05.24学位授予单位和日期电子科技大学2016年

4、6月答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号。RESEARCHONPARALLELFP-GROWTHASSOCIATIONRULESAMasterThesisSubmittedtoUniversityofElectronicScienceandTechnologyofChinaMasterofEngineeringMajor:LouShuqingAuthor:Prof.WenJunSupervisor:SchoolofInformationandSchool:SoftwareEngineering摘要摘要关联规则是数据挖掘领域中一种基

5、本且重要的模型，其中频繁模式增长算法（FP-growth算法）是关联规则里的经典算法，但随着所需处理的数据集越来越大，FP-growth算法的挖掘效率变得低下，甚至不能在内存中构建一棵全局的FP-tree，因此，并行的FP-growth算法就相继被提出。但传统的FP-growth并行算法并没有考虑各个计算子节点的负载均衡问题，以及节点间通信消耗的问题。关联规则挖掘在企业财务管理中也有很好的应用，随着企业规模的不断壮大，企业财务管理变得尤为重要。其中，企业财务风险分析是企业财务管理中的重要一环，目前已有的企业财务风险分析方法主要是从定性与定量两个角度考虑，

6、但是都有其不足，而且定量财务风险分析所采用的Apriori算法也不能很好地应对海量财务数据所带来的挑战。针对上述问题，论文的主要工作如下：（1）针对频繁1-项集F-list分组投影时会造成计算子节点间负载不均衡以及节点间存在大量通信传输的问题，论文提出了两种优化并行算法：1、基于贪心策略的负载优化算法（GFP），该算法用于数据水平投影过程中，它利用贪心策略对F-list中的项进行分组，每次根据局部负载量最优策略进行划分，最终使得各个计算子节点具有相似的负载量。实验表明，GFP比传统的Hash分组方法能更好地实现负载均衡。2、基于通信量优化的FP-grow

7、th并行算法（TFP），GFP算法虽然可以解决负载均衡问题，但当某个频繁项目的最大的条件模式基被投影到其他节点上时，会出现大量的数据传输，导致节点之间的通信量增大。为了解决这一问题，TFP算法在为每个频繁项目分组时，优先考虑将其分到需要最小通信量的节点上去。实验表明，TFP算法满足节点负载均衡的同时，也保证了节点之间具有较小的通信量，从而比传统的FP-growth并行算法效率更高。（2）针对企业财务风险定量分析中存在的不足，论文采用并行FP-growth优化算法TFP替代Apriori算法，使得财务风险分析系统具有处理大规模数据集的能力，从而降低了时间和

8、空间复杂度。最终，论文设计并实现了一个基于并行FP-growth的企业财务风险分