杨健兵

(南通科技职业学院 信息与智能工程学院，江苏 南通 226007)

MapReduce框架下改进Apriori算法的研究

杨健兵

(南通科技职业学院 信息与智能工程学院，江苏 南通 226007)

MapReduce是一种编程模型，这种模型编程简单，可以用于大规模数据集的并行计算。Apriori算法是一种发现频繁项集的基本算法，通过该算法，可以产生关联规则。针对Apriori的特点，研究了在MapReduce编程模型下，Apriori的实现方法。实验结果表明：该方法在对大数据集进行频繁项集挖掘时, 可充分利用云计算的优势, 从而能获得更好的时效性。

Apriori；数据挖掘；关联规则；MapReduce

0 引言

随着计算机和互联网技术的飞速发展，海量的数据不断地产生。数据挖掘技术是通过数据挖掘算法从海量数据中找到有意义的模式或知识，这些知识对于企业和政府决策起了很大的作用。传统的数据挖掘算法往往在普通的计算机上运行，面对大量的数据时，在计算能力、处理速度、存储容量、带宽速度等多个方面往往表现出力不从心。云计算在计算机网络的基础上，将计算机庞大的处理程序通过云计算机平台分解成小子程序，采取分而治之的方式加以解决。

在大规模数据集的并行运算方面，MapReduce[1]是一种用得比较多的编程模型，其主要思想是Map和Reduce，它可以在程序开发人员不会分布式并行编程的情况下，将程序运行在分布式系统上。

Hadoop[2-4]是一个由Apache基金会所开发的分布式系统基础架构。用户可以在不知晓分布式文件系统实现细节的环境下开发分布式程序。HDFS和MapReduce是 Hadoop的框架最重要的设计，HDFS为海量的数据存储提供了可能，而MapReduce则为海量的数据提供了计算。通过Apache开源社区Hadoop项目[5]，程序设计人员实现了该模型，使的该模型进行分布式并行计算成为可能。

多种Apriori算法已经在云计算编程模型MapReduce上实现。本文结合各自算法的思想与MapReduce 的运行机理，提出MapReduce框架下Apriori算法的研究。在MapReduce的框架下，Apriori算法的使用范围由单机扩展到云计算平台，极大地减少了Apriori算法的运行时间，显著地提高了运行的效率。

1 MapReduce编程模型

图1 MapReduce 运行流程图

MapReduce在海量数据进行并行计算中使用广泛，美国的Google 公司首次开发出了该技术框架。由Map和Reduce这两个核心步骤组成。MapReduce 接受到一个作业时，将该作业拆分成一系列任务，然后把这些任务按照一定的原则分配到不同的机器节点上去执行，当Map 处理完任务以后，将会产生一些中间文件，这些中间文件就成了Reduce的输入数据。Reduce把前面若干个Map 产生的中间结果进行排序汇总后一并输出。MapReduce的数据流图如图1 所示。

2 Apriori算法在MapReduce框架下的实现

2.1 Apriori算法

Apriori算法是一种挖掘关联规则的频繁项集算法。Apriori算法使用迭代方法，该迭代方法使用逐层搜索的技术，通过k项集产生(k+1)项集。首先，通过扫描整个数据库，累计每个项的数量，计算满足最小支持度的项，找到频繁1项集，该集合记为L1项集。然后通过L1项集找到频繁2项集，该集合记为L2。通过使用L2找到L3，迭代下去，直到不能再找到频繁K项集。

定义1 频繁项集的所有非空子集一定也是频繁的。

证明：根据定义，如果项集I不能满足最小支持度min_sup，则I不是频繁的，即P(I)

Apriori的核心思想是连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。Apriori算法的串行计算流程如图2所示。

图2 Apriori算法的串行计算流程

(1)连接步

为了找出Lk，通过将Lk-1与自身连接产生候选k项集的集合。该候选项集的集合为Ck。设l1和l2是Lk-1项集。li[j]表示li的第j项。Apriori算法假定事务或者项集中的项按照字典序排列，对于(k-1)项集li，这意味着把项排序，使得li[1] < li[2]< …< li[k-1]。执行连接lk-1和lk-1，如果它们前(k-2)个项相同。即lk-1的元素l1和l2是可连接的。连接l1和l2产生的结果项集是{l1[1], l1[2]]，…，l1[k-1]，l2[k-1]}。

(2)剪枝步

Ck是Lk的超集，也就是说，Ck的成员可以是也可以不是频繁的，但所有的频繁k项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk。然后Ck可能很大，因此所涉及的计算量很大。为了压缩Ck，可以用以下办法使用定义1。任何非频繁的(k-1)项集都不在频繁k项集的子集。因此，如果一个候选k项集的(k-1)项集不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除。

2.2 Apriori算法分析

传统的Apriori算法首先通过生成频繁1项集，通过频繁1项集产生频繁2项集，依次类推。在产生频繁项集的过程中，每产生一个频繁项集，就需要扫描整个数据库。但数据量比较大的时候，每次扫描数据库需要耗费大量的时间，这种扫描数据库过程增加了系统运行的时间，降低了系统效率。

2.3 改进的Apriori算法在MapReduce模型下实现

输入部分：在HDFS的文件系统中存储事务数据库D以及最小支持度阈值min_sup。输出部分：L,D中的频繁项集。

①L1=find_frequent_1_itemsets(D)。

②Map过程，通过L1把每条记录转换成行向量，行向量记住v。

③reduce过程，生成矩阵，计算候选项集的局部支持度。

④计算全局支持度。

⑤得到关联规则。

该算法共分为两个阶段。在第一阶段，执行算法第①步查找候选项集，通过计算得到频繁项集L1。然后把L1存放到数据库中以备第二阶段使用。在MapReduce第二阶段，采用改进的Apriori算法，该改进的算法采用矩阵思想来计算候选项集的局部支持度。在reduce任务中，合并相同的key再生成矩阵，算出局部支持频度。通过计算出来的局部支持频度计算全局支持频度，如果全局支持频度大于最小支持频度阈值，则把候选项集归为频繁项集。最后根据频繁项集得到关联规则。

2.4 算法实例分析

假定D 有9 条交易记录，D={T100、T200、T300、T400、T500、T600、T700、T800、T900}，如表1所示，I 是项目的集合，且I={I1，I2，I3，I4，I5}。把D 上传到HDFS 中，且其被分成两个数据块D1={ T100、T200、T300、T400、T500 }和D2={ T600、T700、T800、T900}。最小支持频度阈值为3。

改进的Apriori算法在执行MapReduce第一阶段任务的时候会生成频繁1项集。以T100为例，它将产生键值对：、、，其他交易记录也会产生相应的键值对。所以我们得到I1的支持频度为6，它大于最小支持频度。通过类似的方法，可以获得L1{，，}。

表1 事务数据

改进的Apriori算法在执行MapReduce第二阶段任务的时候，在Map阶段，把表1的数据分成D1和D2两个部分，将D1和D2分配给不通的Map任务进行执行。通过使用频繁1项集L1把数据转换成一个行向量v，向量中的元素为频繁1项集中所对应的元素，即I1，I2，I3。如果数据中存在该向量的元素，则对应部分为‘1’，否则为‘0’。数据的行向量表示如表2和表3所示。

表2 数据块D1向量表示

表3 数据块D2向量表示

TIDI1I2I3T600011T700101T800111T900111

设表2数据块D1向量用矩阵来表示，该矩阵为G1，表3数据块D2向量用矩阵来表示为G2，设它们的转置矩阵分别是G1’和G2’，则G1’和G2’分别如表4和表5所示。

表4 数据块D1的转置矩阵G1

表5 数据块D2的转置矩阵G2″

在Reduce阶段，可以设置两个Reduce任务，分别处理不同的key键值，具有相同key的都被送到同一Reduce任务进行执行。以表2为例，首先生成矩阵G1，然后再生成转置矩阵G1′，另外一个任务也是相同的方法进行处理。

数据块D1的转置矩阵G1′可以看做是由一系列行向量组成的，即I1={1,0,0,1,1}，I2={1,1,1,1,0} I3={0,0,1,0,0}，由于频繁1项集为{I1，I2，I3}，所以可以计算出候选Lk(k>=2)项集肯定是{I1，I2，I3}这几个频繁1项集的组合。根据G1′的实际情况，它的候选项集分别是{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}。以{I1，I2}为例，它的局部支持度为{1,0,0,1,1}&{1,1,1,1,0}=1&1+0&1+0&1+1&1+1&0=2。运用相同的计算方法，{I1，I3}，{I2，I3}，{I1，I2，I3}的局部支持度分别是1，1，0。

对于转置矩阵G2’可以同样计算出{I1，I2}，{I1，I3}，{I2，I3}，{I1，I2，I3}的局部支持度为2，3，3，2。

在执行完MapReduce第二阶段任务后，把候选项集所对应的局部支持度累加起来，就可以生成全局支持度计数，进而可以生成频繁项集。由于在本实例中设定的最小支持度阈值为3，根据规则可以生成频繁项集为{I1}，{I2}，{I3}，{I1，I2}，{I1，I3}，{I2，I3}。

2.5 改进的Apriori算法分析

改进的Apriori算法在计算频繁项集的过程中，对数据库仅需要两次扫描。同时利用MapReduce模型，可以在大量数据的情况下进行平行计算。这种模型的使用降低了空间复杂度和时间复杂度，高效利用了平行的优势。特别是在数据量非常大的情况下，能够提高系统效率，节省时间。

3 实验结果

通过实验，改进的Apriori算法在MapReduce框架下实现效果进行了展示和评估。

3.1 实验环境

本实验在南京工业大学云平台进行实验。该平台由一系列IBM服务器构建。其中管理节点1个，计算机节点16个，网络采用万兆网络，操作系统采用RedHat Linux。在硬件配置上，每一个节点的CPU 采用Intel Xeon 2.0GCPU，8G内存，100G硬盘，软件配置Hadoop 。

3.2 实验数据

实验数据来自于某大型超市数据库交易记录信息，在进行数据分析之前，我们对数据进行了预处理，包括数据的清理、集成、变换等。为了便于实验，对这些文件进行了多次备份并进行了合并以得到不同大小的文件。数据集规模大小如图表6所示。

表6 预处理后数据集

3.3 实验结果

图3 两种不同算法数据分析图

在处理大数据的过程中，在MapReduce框架下改进Apriori算法所使用的时间明显要大于在MapReduce框架下改进的Apriori算法。并且从图3中可以看出，在数据量由10百万条增加到40百万条的时候，传统的Apriori算法用时明显增加，而MapReduce框架下改进的Apriori算法所消耗的时间增加不是太多，这说明MapReduce框架下改进的Apriori算法在处理大规模数据集的时候拥有更大的加速比，更适合处理大量的数据。

4 结语

随着互联网业务的不断发展，每天都有大量的数据产生，对于产生的数据用数据挖掘的方法对它进行分析并提取有益的信息已经成为大家关注的对象。在源源不断的数据产生以后，我们可以通过在MapReduce框架下改进的Apriori算法进行关联规则分析，从而产生对现实有意义的知识。

本文提出了一个思路，在面对大量数据的时候如何使用MapReduce框架去处理这些数据。实验表明，该解决方法在面对大量数据的时候可以极大地提高运行速度、缩短运行时间、提高运行效率。

[1] Dean j,Ghemawat S. MapReduce simplified data processing on large cluster[J].Communication of the ACM,2006,51(1):107-113.

[2] Dean Jeffrey,Ghemawat Sanjay.Mapreduce:simplified data processing on large clusters[J]．Communications of the ACM,2005,51(1):107-113.

[3] 刘骞，陈明．基于改进的Map/Reduce及模式空间划分的数据挖掘[J]．微电子学与计算机，2011(08)：140-142.

[4] 李建江，崔健，王聃，等.Mapreduce并行编程模型研究综述[J].电子学报，2011(11)：2635-2642.

[5] Apache Hadoop. Hadoop[EB/OL].[2011-02-15].http://hadoop.apache.org.

责任编辑：程艳艳

Research of Improved Apriori Algorithm under MapReduce Framework

YANG Jianbing

(Department of Information and Intelligence Engineering,Nantong Vocational College of Science and Technology, Nantong 226007, China)

MapReduce is a programming model, which is simple, can be used for parallel computing of large-scale data sets. Apriori algorithm is a basic algorithm to discover frequent item sets, and association rules are generated from it. In view of the characteristics of Apriori, this paper analyzes the realization method of Apriori under MapReduce programming model. Experimental results show that the proposed method can make full use of the advantages of cloud computing in the frequent item sets mining on large data sets, having better effectiveness.

Apriori; data mining; association rule; MapReduce

2016-09-02

杨健兵(1976-)，江苏海门人，讲师，硕士，主要从事数据挖掘和人工神经网络方面研究。

TP301

A

1009-3907(2016)08-0040-04