频繁项集挖掘算法及其基于Spark的并行化研究

发布时间：2017-09-01 13:36

  本文关键词：频繁项集挖掘算法及其基于Spark的并行化研究

  更多相关文章： 数据挖掘 关联规则 频繁项集 Spark 并行计算

【摘要】：频繁项集挖掘自首次提出以来,因其具有较高的时间复杂度,引起许多国内外的研究者们致力于提高相关算法的性能。尤其是随着大数据时代的到来,传统的频繁项集挖掘算法往往受限于单台计算机有限的计算能力和存储容量,无法满足用户对于处理更大规模的频繁项集挖掘问题的迫切需求。本文对当前频繁项集挖掘算法的优缺点进行了比较和总结,并对近年来流行的Spark并行计算技术进行了学习和研究,提出了一种优化的项集表示方式,称之为HybridNodeset。同时,提出了一种基于该项集表示方式的串行频繁项集挖掘算法,称之为HybridFIN算法。实验结果表明,与当前性能较好的频繁项集挖掘算法相比,该算法在处理不同类型的数据集时的性能更加稳定,并且能在更短的时间内完成计算任务。另外,对该项集表示方式进行了扩展性研究,将其应用于最大频繁项集挖掘,并改进了基于MFI-Tree的投影策略,提高了该算法的执行速度。为了充分利用集群的计算能力,提出了一种基于Spark的并行频繁项集挖掘算法,称之为PHybridFIN算法。该算法通过映射事务数据集的方式来将原始问题分解为若干个子问题进行求解,并采用了事务树来减少网络传输方面的时间开销。实验结果表明,该算法的执行速度超过了Spark机器学习算法库中的PFP算法。最后,对PHybridFIN算法中映射事务数据集的过程进行了改进,提出了PHybridFIN+算法。该算法采用了完全不同的并行化策略,无需映射事务数据集。实验结果表明,该算法的性能有了进一步的提升。
【关键词】：数据挖掘 关联规则 频繁项集 Spark 并行计算
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13
【目录】：

• 摘要6-7
• ABSTRACT7-10
• 第1章 绪论10-16
• 1.1 研究背景和意义10-12
• 1.2 国内外研究现状12-14
• 1.2.1 串行频繁项集挖掘算法的研究现状12-13
• 1.2.2 并行频繁项集挖掘算法的研究现状13-14
• 1.3 本文的主要工作及创新点14-15
• 1.4 本文的组织结构15
• 1.5 本章小结15-16
• 第2章 相关研究工作16-29
• 2.1 频繁项集挖掘的定义16
• 2.2 串行频繁项集挖掘算法16-22
• 2.2.1 FP-Growth算法16-19
• 2.2.2 FIN算法19-21
• 2.2.3 dFIN算法21-22
• 2.3 串行最大频繁项集挖掘算法22-24
• 2.3.1 FP-Max算法22-24
• 2.4 并行频繁项集挖掘算法24-26
• 2.4.1 PFP算法24-26
• 2.5 Spark并行计算技术26-28
• 2.6 本章小结28-29
• 第3章 基于HybridNodeset的串行频繁项集挖掘算法29-46
• 3.1 HybridFIN的基本思想29
• 3.2 HybridNodeset的定义和性质29-36
• 3.3 HybridNodeset的性能分析36-38
• 3.4 HybridFIN算法描述38-41
• 3.5 实验结果和分析41-45
• 3.5.1 实验环境与数据集41-42
• 3.5.2 性能测试结果42-45
• 3.6 本章小结45-46
• 第4章 基于HybridNodeset的串行最大频繁项集挖掘算法46-54
• 4.1 MHybridFIN算法的基本思想46
• 4.2 MHybridFIN算法描述46-49
• 4.3 实验结果和分析49-53
• 4.3.1 实验环境与数据集49-50
• 4.3.2 性能测试结果50-53
• 4.4 本章小结53-54
• 第5章 基于HybridNodeset的并行频繁项集挖掘算法54-61
• 5.1 PHybridFIN算法的基本思想54
• 5.2 PHybridFIN算法描述54-57
• 5.3 实验结果和分析57-60
• 5.3.1 实验环境与数据集57-58
• 5.3.2 性能测试结果58-60
• 5.4 本章小结60-61
• 第6章 基于HybridNodeset的并行频繁项集挖掘改进算法61-69
• 6.1 PHybridFIN+算法的基本思想61
• 6.2 PHybridFIN+算法描述61-65
• 6.3 实验结果和分析65-68
• 6.3.1 实验环境和数据集65-66
• 6.3.2 性能测试结果66-68
• 6.4 本章小结68-69
• 第7章 总结和展望69-71
• 7.1 全文工作总结69-70
• 7.2 未来工作展望70-71
• 参考文献71-74
• 附录一 作者攻读硕士学位期间发表的学术论文74-75
• 附录二 作者攻读硕士学位期间参与的科研项目75-76
• 致谢76

【相似文献】

中国期刊全文数据库 前10条

1 肖基毅,邹腊梅,刘丰;频繁项集挖掘算法研究[J];情报杂志;2005年11期

2 蔡进;薛永生;张东站;;基于分区分类法快速更新频繁项集[J];计算机工程与应用;2007年09期

3 胡学钢;徐勇;王德兴;张晶;;基于多剪枝格的频繁项集表示与挖掘[J];合肥工业大学学报(自然科学版);2007年04期

4 胡学钢;刘卫;王德兴;;基于剪枝概念格模型的频繁项集表示及挖掘[J];合肥工业大学学报(自然科学版);2007年09期

5 栾鸾;李云;盛艳;;多关系频繁项集的并行获取[J];微电子学与计算机;2008年10期

6 李彦伟;戴月明;王金鑫;;一种挖掘加权频繁项集的改进算法[J];计算机工程与应用;2011年15期

7 陈立潮,张建华,刘玉树;提高频繁项集挖掘算法效率的方法研究[J];计算机工程与应用;2002年10期

8 朱玉全,孙志挥,赵传申;快速更新频繁项集[J];计算机研究与发展;2003年01期

9 宋宝莉;张帮华;何炎祥;朱骁峰;;带有多个可转化约束的频繁项集挖掘算法[J];计算机科学;2003年12期

10 王自强,冯博琴;频繁项集的简洁表示方法研究[J];系统工程理论与实践;2004年07期

中国重要会议论文全文数据库 前10条

1 栾鸾;李云;盛艳;;多关系频繁项集的并行获取[A];2008年全国开放式分布与并行计算机学术会议论文集(下册)[C];2008年

2 杨晓明;王晨;汪卫;张守志;施伯乐;;频繁项集的精简表达与还原问题研究[A];第二十一届中国数据库学术会议论文集（技术报告篇）[C];2004年

3 邓传国;;频繁项集挖掘与学生素质测评应用研究[A];2007系统仿真技术及其应用学术会议论文集[C];2007年

4 李彤岩;李兴明;;基于分布式关联规则挖掘的告警相关性研究[A];2007通信理论与技术新发展——第十二届全国青年通信学术会议论文集（下册）[C];2007年

5 王洪利;冯玉强;;频繁项集挖掘算法Apriori的改进研究[A];全国第九届企业信息化与工业工程学术会议论文集[C];2005年

6 陈晓云;李龙杰;马志新;白伸伸;王磊;;AFP-Miner:一种新高效的频繁项集挖掘算法[A];2006年全国理论计算机科学学术年会论文集[C];2006年

7 李坤;王永炎;王宏安;;一种基于乐观裁剪策略的挖掘数据流滑动窗口上闭合频繁项集的算法[A];第二十五届中国数据库学术会议论文集（二）[C];2008年

8 邹远娅;周皓峰;王晨;汪卫;施伯乐;;FSC——利用频繁项集挖掘估算视图大小[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

9 杨晓雪;衡红军;;一种对XML数据进行关联规则挖掘的方法研究[A];第二十二届中国数据库学术会议论文集（技术报告篇）[C];2005年

10 谢志军;陈红;;EFIM——数据流上频繁项集挖掘的高性能算法[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

中国博士学位论文全文数据库 前3条

1 温磊;基于有向项集图的关联规则挖掘算法研究与应用[D];天津大学;2004年

2 董杰;基于位表的关联规则挖掘及关联分类研究[D];大连理工大学;2009年

3 贾彩燕;关联规则挖掘的取样复杂性分析[D];中国科学院研究生院（计算技术研究所）;2004年

中国硕士学位论文全文数据库 前10条

1 王立俊;基于多重最小支持度的氋效用频繁项集挖掘算法研究[D];广西大学;2015年

2 陈国俊;基于Hadoop的云存储系统的研究与应用[D];电子科技大学;2014年

3 尹艳红;基于Apriori算法的增量式关联规则控制研究[D];大连理工大学;2015年

4 田苗凤;大数据背景下并行动态关联规则挖掘研究[D];兰州交通大学;2015年

5 李雪迪;基于本体论的精细化数据分析[D];南京邮电大学;2015年

6 许静文;基于模糊等价类的频繁项集精简表示算法研究[D];合肥工业大学;2015年

7 王大伟;大数据环境下的关联规则提取算法研究[D];辽宁工业大学;2016年

8 廖友金;基于有向图的关联规则挖掘研究与改进[D];东南大学;2015年

9 王苏琦;基于Hadoop的不确定频繁项集并行挖掘方法研究[D];南京大学;2013年

10 韩宏莹;并行数据挖掘技术在电信网管告警中的应用研究[D];长春工业大学;2016年

，

本文编号：772389