摘 要

如今在竞争性企业中，知识发现或者说从大量的数据中提取知识，是一个理想型任务。数据挖掘是知识发现过程中的一个重要环节。同时，频繁模式在数据挖掘的任务，如聚类，分类和关联分析中发挥着核心作用。由于大量候选模式的产生，识别所有的频繁模式是一个非常耗时的过程。在过去的十年中，不断有许多学者和研究者提出各种频繁模式挖掘算法。然而，减少候选模式的数目和支持度计数的比较仍然是这一领域中存在的重要问题。

为此，本文提出了一种基于MapReduce的非迭代随机长度频繁模式发现并行算法——AMRK算法。该算法通过对Apriori算法的计算顺序进行重组，打破了迭代式求取频繁项集的思想，将逻辑运算与二进制映射相结合在非迭代并行算法的基础上研究了随机长度项目模式生成算法，并结合Hadoop技术框架和MapReduce编程模型实现了分布式并行化。最后，实验证明， AMRK算法比一般的并行算法的效率高很多。

关键词：数据挖掘；频繁模式；Apriori；Hadoop；MapReduce

Abstract

Nowadays, knowledge discovery or extracting knowledge from large amount of data is a desirable task in competitive businesses. Data mining is a main step in knowledge discovery process. Meanwhile, frequent patterns play a central role in data mining tasks such as clustering, classification, and association analysis. Identifying all frequent patterns is the most time consuming process due to a massive number of candidate patterns. For the past decade there have been an increasing number of efficient algorithms to mine the frequent patterns. However, reducing the number of candidate patterns and comparisons for support counting are still two problems in this field which have made the frequent pattern mining one of the active research themes in data mining.

So that, this paper proposes a kind of parallel algorithm for frequent pattern discovery in non iterative random length based on MapReduce - AMRK algorithm. The algorithm recombines the calculation sequence of the Apriori algorithm, breaking the iterative idea of seeking frequent item sets. I studied the random length pattern generation algorithm on the basis of iterative parallel algorithm by combining logic operation and binary mapping, and realized the diatributed parallelization through the combination with the Hadoop technology framework and MapReduce programming model. Finally, the experimental results show that the AMRK algorithm is much more efficient than the general parallel algorithm.

Key Words: data mining；frequent pattern；Apriori；Hadoop；MapReduce

目录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景与意义 1

1.2 研究现状 2

1.2.1国内外研究现状分析 2

1.2.2研究存在的问题 3

1.3 研究内容 4

1.4 结构安排 4

第2章 Apriori算法 6

2.1 Apriori算法概述 6

2.2 Apriori算法串行实现 7

2.2.1算法实例分析 7

2.2.2算法伪代码 8

2.2.3算法具体实现 9

2.2.4算法性能分析 11

第3章 Apriori算法并行化 12

3.1 非迭代Apriori并行算法 12

3.2随机长度项目模式生成算法 13

3.3 基于MapReduce的并行算法AMRK 15

3.3.1 Hadoop框架和MapReduce编程模型介绍 15

3.3.2 AMRK算法详细设计与实现 17

第4章 实验以及结果分析 22

4.1 实验环境的配置与搭建 22

4.1.1实验环境的配置 22

4.1.2实验环境的搭建 22

4.2 测试数据集 28

4.3实验方案设计 28

4.4实验结果与分析 29

4.4.1实验一结果与分析 29

4.4.2实验二结果与分析 30

4.4.3实验三结果与分析 34

第5章 总结与展望 36

5.1论文工作总结 36

5.2研究的创新点 37

5.3未来工作展望 37

参考文献 38

致谢 41

第1章 绪论

1.1 研究背景与意义

随着科学社会和信息技术的飞速发展，许多领域诸如生物科学、金融外贸、医学科研、电子商务等都产生了TB级甚至PB级的大量数据。这些数据大多是复杂的、异构的、有噪声的^[1]，很难进行处理。随着数据库和计算机科学技术的兴起，人们对海量数据的处理变得相对容易，但是如何从这些海量数据中发掘出更多具有价值的信息以及如何根据这些信息预测数据未来的发展趋势，这都成为人们面临的重大难题。对此,很多学者在这方面进行了大量研究，数据挖掘技术（DM，Data Mining）也就随之产生并不断成熟起来了。数据挖掘是数据库知识发现（KDD， Knowledge-Discovery in Databases)中的一个重要步骤^[2]，是统计学(Statistics)和计算机科学(Computer Science)的一个交叉学科^[3]，集机器学习、数据库技术、知识工程、信息检索、人工智能、模式识别、高性能计算、统计学以及可视化等于一体^[4-7]，包括特征化描述、分类预测、聚类分析、演变分析、孤立点分析挖掘方式^[8]，数据挖掘技术在商业决策、工程管理、科学研究等许多领域都有重要应用^[9]。在电子商务中，可以通过数据挖掘进行海量商品的相关信息的采集和分析商家客户购买操作之间的关系，从而改版网页，优化产品结构或者制定个性化方案^[10]。在通信行业，可以对用户呼叫信息、用户查询信息、用户使用信息等数据进行分析处理，从而得到客户在电子方面的使用模式，不断改进营销策略^[11]。在轨道交通领域，把乘客的刷卡记录作为数据源进行分析处理，根据人们的乘车需要和各站点的人流量制定出合理的消费套餐和站点设备信息^[12]。在生物学中，数据挖掘主要应用在生物学规律的发现上，通过对数以亿计的DNA序列进行统计学分析，发现蕴藏其中的生物奥秘^[13]。

频繁模式挖掘是分析关联规则的主要方法，主要是对项集、序列和子树三个模块进行频繁挖掘。频繁项集挖掘主要包括两个步骤:通过扫描数据库以及支持度比较找出频繁项集，再根据置信度通过计算求出强关联规则，而频繁项集的挖掘过程则是关联规则分析的核心步骤^[14]。频繁模式挖掘的方法在零售业、互联网(Web挖掘、入侵检测、互联网安全)、生物DNA序列分析、研究专家系统，以及科学与医疗研究等方面^[15] 都有重要应用。由此可见，无论是在理论研究方面还是在实际应用方面都具有非常适用的价值。