Apriori并行算法的应用研究

Apriori并行算法的应用研究(任务书,开题报告,论文15000字)
摘  要
Apriori算法是一种典型的数据挖掘算法，对于频繁项集的挖掘，主要通过连接步以及剪枝步实现。但在传统的Apriori算法，存在着以下两个重大的问题：(1)在频繁项集的计算过程中需要产生大量的候选项集；(2)需要重复地扫描数据库，每产生一次候选项集都需要扫描一次数据库。
论文主要研究了如何解决传统的Apriori算法存在的（2）问题，目的是通过减少扫描原始事务集数据库的次数，以达到提高算法运行的效率，从而实现处理大数据集的效果。
研究结果表明：与传统的Apriori算法相对比，基于MapReduce并行框架设计的MMR-Apriori不仅仅能够达到处理大数据的效果，而且可以提高并行化的Apriori算法的运行效率。
本文的特色在于：MMR-Apriori算法的优化设计通过产生的1-频繁项集，建立对应的1-频繁项集索引表，根据索引表建立事务压缩映射表。一方面可以达到压缩原始事务集数据库，另一方面通过建立的1-频繁项集索引表以及事务压缩映射表，大大减少了统计迭代产生的k-候选集中每个项目集出现频率的时间。
关键字: 频繁项集；MapReduce并行框架；MMR-Apriori；事务压缩映射表

Abstract
Apriori algorithm is a classical data mining algorithm. For the mining of frequent itemsets, it is mainly achieved through connecting and pruning step. However, in the traditional Apriori algorithm, there are two major problems: (1) A large number of candidate sets need to be generated during the calculation of frequent itemsets (2) The database needs to be scanned repeatedly, and each generation of a candidate itemset requires a database scan.
The thesis mainly studies how to solve second questions mentioned above of the traditional Apriori algorithm. The purpose is to improve the efficiency of the algorithm by reducing the number of times of scanning the original transaction set database, thus achieving the effect of processing large data sets.
The research results show that compared with the traditional Apriori algorithm, the MMR-Apriori based on the MapReduce parallel framework can not only achieve the effect of processing big data, but also improve the running efficiency of the parallelized Apriori algorithm.
The characteristic of this paper lies in: The optimal design of MMR-Apriori algorithm establishes the corresponding 1- frequent itemsets index table bythe 1-frequent itemsets generated, and establishes the transactioncompression mapping table according to the index table. On the one hand, the original transaction set database can be greatly compressed, and on the other hand, the 1-frequent itemsets index table and the transaction compression mapping table are established, which greatly reduces the statistical time of occurrence of each itemset in the k-candidate set generated by iteration.
KeyWords：frequent itemsets；MapReduce parallel framework；MMR-Apriori；transaction compression mapping table
 
目录
第1章 绪论    1
1.1 研究背景    1
1.2 研究的目的及意义    1
1.2.1 目的    1
1.2.2 意义    2
1.3 国内外研究现状    2
1.4 课题研究内容    3
1.5 论文结构安排    3
第2章 Apriori算法    5
2.1 Apriori算法的描述    5
2.1.1 求解频繁项集过程    5
2.1.2 求解频繁项集实现算法    6
2.2 Apriori算法的分析    6
第3章 并行框架分析与Hadoop集群的搭建    7
3.1 并行框架分析    7
3.1.1 各并行框架的性能对比    7
3.1.2 Hadoop MapReduce编程框架    8
3.2 Hadoop集群的搭建    9
3.2.1 准备阶段    9
3.2.2 集群环境搭建    9
第4章 基于MapReduce框架的MMR-Apriori优化算法    15
4.1 相关定义    15
4.1.1 事务布尔矩阵(T)    15
4.1.2 1-频繁项集映射表    15
4.1.3 基于1-频繁项集事务压缩映射表    15
4.2 MMR-Apriori算法描述    15
4.2.1 产生1-频繁项集映射表    16
4.2.2 产生基于1-频繁项集事务压缩映射表    16
4.2.3 迭代生成k-频繁项集    16
4.3 MMR-Apriori算法实现代码    18
4.3.1 1-频繁项集映射表的实现过程    18
4.3.2 基于1-频繁项集事务压缩映射表的实现过程    20
4.3.3 迭代生成k-频繁项集的实现过程    22
4.4 MMR-Apriori算法实现示例    25
4.4.1产生1-频繁项集映射表示例    26
4.4.2产生基于1-频繁项集事务压缩映射表示例    27
4.4.3 迭代生成k-频繁项集示例    28
第5章 实验分析    30
5.1实验框架    30
5.1.1数据集    30
5.1.2实验方案    30
5.1.3实验环境    30
5.2实验结果分析    31
5.2.1实验算法简介    31
5.2.2结果分析    31
第6章 结语    34
参考文献    35
致谢    37