基于MapReduce的分布式关联规则挖掘算法研究

摘要

在数据挖掘的研究范畴中,关联规则挖掘算法是至关重要的一个分支。关联规则算法因其目的明确、实现灵活、求解方便有效、应用范围广泛等特点成为挖掘数据深层价值的重要手段。它的应用在互联网飞速发展的今天拥有更加突出研究意义。信息化迅速加快的今天,数据呈现出爆炸式的增长,此刻,分布式关联规则算法有了更广阔的发展空间。本文先分析了传统的关联规则算法,随后着重研究了分布式条件下的关联规则算法。论文采用目前较为成熟的Hadoop分布式平台,对分布式关联规则算法的改进提出了全新的思路。针对目前基于MapReduce分布式关联规则算法的不足首先引入了全局剪枝策略,提高了算法效率。然后运用频繁矩阵存储的方式减少了内存的消耗。
　　首先,在全面了解关联规则算法背景和研究现状之后,针对现有算法无法处理大规模数据以及分布式数据的缺点,应用Hadoop平台实现对规则和知识的发现的过程。应用MapReduce计算模型可以有效地解决数据分块处理运用多台计算机协同处理海量数据的问题。使得以前难以解决的问题变得简单。
　　其次,针对现有的MapReduce关联规则算法,提出了大规模数据分布式处理的MPAOR(Map Apriori OneReduce Algorithm)算法,本算法在实现了已有的MPAriori(Map Reduce Apriori Algorithm)算法的基础上加入了全局剪枝的技术,使得计算频繁项集的计数量再一次减少,同时论文把频繁矩阵的存储方式加入到分布式关联规则算法中,提出了MapReduce计算模型的频繁矩阵存储的MFMDAP(Map Frequentmatrix Distributed Apriori Algorithm)算法。实验表明论文提出的算法提高了算法的效率,并且节省了内存的使用量,这有利于大粒度数据的计算和存储。在实验中验证了算法的有效性。
　　最后,对全局剪枝的分布式频繁项集算法(MPAOR)和基于频繁矩阵的算法(MFMDAP)的优点和不足进行说明,总结了论文研究的成果和以后的研究方向。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究背景及意义

1.2国内外研究现状

1.3论文的主要研究工作

1.4论文的组织结构

第2章 相关技术研究

2.1 频繁项集的定义与应用

2.2关联规则的发现

2.3二元组计数及项集计数的内存使用情况

2.4 串行生成频繁项集过程

2.5分布式产生频繁项集过程

2.6本章小结

第3章 基于MapReduce的关联规则算法

3.1分布式系统的存储和运算

3.2全局剪枝的MapReduce关联规则算法（MPAOR）

3.3频繁矩阵的MapReduce关联规则算法（MFMDAP）

3.4改进算法的性能分析

3.5本章总结

第4章 实验环境介绍以及实验结果分析

4.1 实验环境设计

4.2 集群实验环境的搭建

4.3 仿真试验中MapReduce的数据流程

4.4 数据集来源说明

4.5 实验结果和算法比较

4.6 本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢