并行频繁项集挖掘算法研究

《并行频繁项集挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1分类号：TP391单位代码：10636密级：公开学号：20151301003硕士学位论文中文论文题目:并行频繁项集挖掘算法研究英文论文题目:ResearchonParallelFrequentItemsetsMiningAlgorithm论文作者：指导教师：专业名称：计算机应用技术研究方向：并行频繁项集挖掘算法所在学院：计算机科学学院论文提交日期：2018年月日论文答辩日期：2018年月日四川师范大学士学位论文附件2：论文独创性及使用授权声明四川师范大学学位论文独创性声明本人声明：所呈交学位论文，是本人在导师指导下，独立进行研究工作所取得的成果。

2、除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而引起的学术声誉上的损失由本人自负。学位论文作者：签字日期：年月日四川师范大学学位论文版权使用授权书本人同意所撰写学位论文的使用授权遵照学校的管理规定：学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥有学位论文的部分使用权，即：1）已获学位的研究生必须按学校规定提交印刷版和电子版学位论文，可以将学

3、位论文的全部或部分内容编入有关数据库供检索；2）为教学、科研和学术交流目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。本人授权万方数据电子出版社将本学位论文收录到《中国学位论文全文数据库》，并通过网络向社会公众提供信息服务。同意按相关规定享受相关权益。（保密的学位论文在解密后适用本授权书）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日并行关联规则频繁项集挖掘算法研究并行频繁项集挖掘算法研究作者:何镇宏指导老师:杨军摘要频繁项集挖掘用来发现数据项集中的频繁模式，在商品关联分析和超

4、市促销策略决策中有着广泛的应用。但是，传统的频繁项集挖掘算法的时间复杂度较高，因此许多国内外的学者们致力于提高相关算法的性能。随着大数据时代的到来，传统的频繁项集挖掘算法往往受限于单台计算机有限的计算能力和存储容量，无法满足用户对于处理更大规模的频繁项集挖掘问题的迫切需求。随着大数据技术的发展，基于Hadoop平台的频繁项集挖掘算法在时间效率上相比于单机算法有了很大的提高。最新的内存计算框架Spark相比于Hadoop平台具有并行计算，Spark已成为目前工业界搭建分布式计算平台的主流框架。因此，本文将Spark框架和频繁项集挖掘算法相结合，研究在

5、Spark平台下实现并行频繁项集挖掘算法，以提高频繁项集挖掘算法的时间效率。本文的主要工作包含如下几个方面。(1)学习研究了经典的频繁项集挖掘算法，包括Apriori算法，DHP算法，FP-Growth算法。(2)针对Apriori算法由K频繁项集生成K+1频繁项集的过程中，需要多次重复检测项集中的二项子集是否频繁的问题，提出了一种基于二维表的Apriori改进算法，用一个二维表记录二项子集是否频繁，从而减少了判断二项子集是否频繁需要多次扫描事务数据库的时间。实验结果表明，本文所提出的改进Apriori算法比原Apriori算法相比，可以明显减少算

6、法的运行时间。(3)学习研究了Spark框架的相关技术，基于Linux操作系统，运用Java结合Scala开发语言，搭建了基于Spark平台的分布式开发环境，用于实现所提出的并行频繁项集挖掘算法。(4)针对DHP在第一次统计桶中项集数目时，会生成许多重复的候选项集，提出了基于Spark单节点的压缩DHP算法，该算法用形象地数字形式代替重复的项集数，并且在第一次扫描事务数据库时就实施，通过实际的试验证明，提出的这个压缩改进算法在时间复杂度上明显比没有采用压缩DHP的单节点DHP算法要低。(5)针对单节点只有一个计算单元的不足，研究了基于集群的Spar

7、k分布式计算框架。利用Spark多节点集群分布式结构实现了分布式DHP算法和分布式FP-Growth算法，充分利用了集群的优势。在模拟数据和UCI数据集Pumsbstar上的实验结果表明，基于集群的并行策略比基于单节点的并行环境具有更好的时间效率。关键词：Spark平台；关联规则；频繁项集；挖掘算法；DHP；FP-Growth；I四川师范大学士学位论文ResearchonParallelFrequentItemsetsMiningAlgorithmABSTRACT:Frequentitemsetsminingisusedtodiscoverfreq

8、uentpatternsindataitemsets.Itiswidelyusedincommodityassociati