云计算环境下频繁项目集挖掘算法研究

摘要

频繁项目集挖掘是数据挖掘研究中的基础研究内容。它在电子商务、网页查询分析、网络入侵检测和疾病诊断等领域有着广泛的应用。随着信息社会的不断发展，尤其是互联网领域的蓬勃发展，人类社会产生的数据呈爆炸式的增长，“大数据”研究应运而生。如何有效地存储和处理日益增长的数据成为目前亟待解决的问题。云计算的提出为“大数据”的存储、挖掘等问题提供了解决方案。本文对云计算环境下频繁项目集挖掘算法并行化作了较深入的研究，取得了如下成果: 1.提出了两种基于Apriori的迭代式Map/Reduce频繁项目集并行挖掘算法MRApriori和TR_MRApriori。MRApriori算法在每次迭代中，先在各计算节点使用Apriori算法计算出候选的k-项集，然后对各个节点的候选结果进行合并，以得到频繁的k-项集。为了提高MRApriori的算法效率，提出了基于事务约减的改进算法TR_MRApriori。TR_MRApriori算法通过记录每次迭代中对下一次迭代中有影响的事务号，大大减少了事务的访问量。实验结果表明TR_MRApriori算法比相关文献提出的方法具有更高的效率。 2.提出了一种基于FP-Growth的频繁项目集并行挖掘算法FPPM。FPPM算法先在每个计算节点上构造局部频繁模式树，并对之进行挖掘得到局部频繁项目集，接着合并局部频繁项目集以得到全局频繁项集，由于此时得到的结果并不完备，所以对合并后未达到最小支持度阈值的项目集，重新计算其支持度。实验结果表明FPPM算法具有较好的可扩展性，且能较好的解决相关文献算法网络通信量过大的问题。 3.提出了一种基于FP-Growth的频繁项目集并行挖掘算法SBPFP。该算法对样本数据计算出每个项目对应的子频繁模式树的挖掘时间，并以该时间为权重的度量因子。接着按权重将项目进行分组，然后将数据均衡划分到其所对应的计算节点上。最后在计算节点上获得该组项目所对应的频繁项目集。实验结果表明SBPFP算法具有较好的运行效率和可扩展性，同时该算法的运行负载性能比相关文献提出的算法更加均衡。 4.提出了一种基于Eclat的频繁项目集并行挖掘算法MREclat。MREclat首先将水平型数据库转换成垂直型数据库，然后将转换后的数据分发到各个计算节点上进行求解，在分发数据时引入了均衡策略使得负载达到平衡。实验结果表明MREclat具有较高的可扩展性和较好的加速比，且比相关文献提出的算法效率更高。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究现状

1．3 本文主要内容及组织结构

第2章 云计算和频繁项目集挖掘概述

2．1 引言

2．2 云计算相关技术

2．2．1 分布式文件系统----HDFS

2．2．2 Map／Reduce编程模型

2．3 频繁项目集挖掘

2．3．1 频繁项目集相关概念

2．3．2 频繁项目集求解算法

2．4 本章小结

第3章 基于Apriori的频繁项目集并行挖掘算法

3．1 Apriori算法

3．2 基于迭代式Map／Reduce的并行挖掘算法

3．2．1 MRApriori算法思想

3．2．2 MRApriori的改进算法TR_MRApriori

3．3 实验结果与分析

3．4 本章小结

第4章 基于FP-Growth的频繁项目集并行挖掘算法

4．1 FP-Growth算法

4．2 基于FP-Growth的并行挖掘算法：FPPM

4．2．1 算法思想

4．2．2 计算1-项集的支持数

4．2．3 求解局部频繁项目集

4．3 基于FP-Growth的并行挖掘算法SBPFP

4．3．1 算法思想

4．3．2 计算1-项集的支持数

4．3．3 均衡分组

4．3．4 计算频繁项目集

4．4 实验结果与分析

4．4．1 FPPM算法实验

4．4．2 SBPFP算法实验

4．5 本章小结

第5章 基于Eclat的频繁项目集并行挖掘算法

5．1 Eclat算法

5．2 基于EcIat的并行挖掘算法MREclat

5．2．1 算法思想描述

5．2．2 数据初始化

5．2．3 负载平衡改进

5．2．4 计算频繁项目集

5．3 实验结果与分析

5．4 本章小结

第6章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

附录 攻读硕士学位期间发表论文情况