Fp—Growth算法在MapReduce框架下的实现

舒远仲+戴海辉+吴小玲

摘 要：Fp-Growth算法是频繁模式挖掘的经典算法，已在许多领域得到了良好应用。传统Fp-Growth算法是基于内存的，而计算机内存却无法装载入大数据，故传统Fp-Growth算法并不能有效地处理大数据。提出一种新的基于MapReduce并行计算框架的Fp-Growth实现，使Fp-Growth算法在多台计算机上并行计算，从而实现大数据的有效处理。实验结果表明，该算法具有很好的扩展性，频繁模式挖掘效率随着用于计算的主机的增加而平稳提升。

关键词：大数据；Fp-Growth算法；MapReduce；数据挖掘

DOIDOI：10.11907/rjdk.171258

中图分类号：TP312

文献标识码：A 文章编号文章编号：1672-7800（2017）008-0025-04

0 引言

近年来，数据呈爆炸式增长，用于大数据的计算框架和基于大数据的各类算法成为研究热点。MapReduce是一种由Google提出的用于分布式并行数据处理的编程模型，它采用“分而治之”的思想，把对数据的处理分解为Map与Reduce两个核心阶段。在MapReduce中高度封装了Map和Reduce两个函数接口，工程师只需实现这两个接口就可实现大部分的并行数据处理工作[1-2]。MapReduce任务中的数据往往较多，会被分为多个分片，通常包含多个Map进程，它们可以并行地运行在不同的计算机上，极大提升了数据处理速度。在Map中，用户的输入被映射为一组组键值（Key-Value）对，这些键值对经过Shffule过程后，形成一组或多组有序的键值对，排列好的键值对将作为Reduce的输入值。Reduce阶段，数据将会被合并和归纳总结并输出。

Fp-Growth算法是数据挖掘中频繁模式挖掘的经典算法。目前，国内外已有学者对Fp-Growth算法进行并行化改造。杨勇等[3]对Fp-Growth算法中FP-tree的结构及挖掘过程进行了改进，他们在分析FP-tree单路径与多路径的不同挖掘方法后，提出了一种新的剪枝策略，从而在挖掘过程中缩减部分分支的迭代次数，最后运用MapReduce编程模型，对改进的Fp-Growth算法进行并行化。章志刚等[4]在MapReduce编程模型的基础上提出了一种基于Fp-Growth的频繁模式并行挖掘算法。该算法中，在每个计算节点上首先构造局部频繁模式树，并对它进行挖掘得到局部频繁项目集，然后合并所有局部频繁项目集从而得到全局频繁项集，但此时得到的结果并不完备，因此对合并后未达到最小支持度阈值的项目集，重新计算其支持数。Wei X等[5]提出了一种基于MapReduce的并行Fp-Growth挖掘策略，使最小支持度阈值和原始数据库变化时有效挖掘出频繁项。Riondato M等[6]提出了一种新的挖掘频繁项集的随机并行技术PARMA。PARMA中随机创建多个小的运算数据挖掘算法的并行样本，每个样本包含小规模的事务数据集，而后从每个样本中汇总筛选出频繁项集，最终得到所有頻繁集的一个近似解。

1 MapReduce编程模型

MapReduce中，每个Reduce的过程输入都是按键排序。将Map的输出进行排序、合并后作为Reduce的输入过程称为Shuffle。如图1所示，在Map端，输入分片经过Map方法处理后产生的输出没有简单将它写入磁盘，而是存储到一个内存中的环形缓冲区中（默认大小为100M），一旦缓冲区的内容大小达到阈值（默认为缓冲区大小的80%），缓冲区中的数据便开始溢出到磁盘中。在溢出的过程中，Map继续往该缓冲区中写入数据，如果该缓冲区被填满，Map将会被阻塞直至当前溢出写磁盘过程完成。在溢出过程中，线程根据数据键值对应的Reducer将数据分成相应的分区，在每个分区中，后台线程对分区中的数据进行内排序。每次环形缓冲区达到阈值时，都会生成一个新的溢出文件。因此默认情况下，当分片大于80M时，溢出工作完成后，会有几个已分区且已排序的溢出文件。在Map任务完成前，这些溢出文件经过一次或多次（默认情况下一次最多合并10个文件流）合并最终得到一个已分区且排序的输出文件。

在Reduce端，Reduce任务从所有的Map任务中选择自己对应的分区复制其中的数据。默认情况下，Reduce有5个线程来并行地取得Map的输出。如果Map输出较小，自会被复制到JVM的内存缓冲区中，否则，复制到磁盘中。一旦内存缓冲区达到阈值，则合并后溢出写到磁盘中。复制完所有的Map输出后，Reduce任务进入到合并阶段，合并因子默认为10，因此当Map数量很大时，要经过多次合并操作才能将数据输入到Reduce方法中。在Reduce方法中对已排序的Map输出中的每个键调用Reduce方法，最终Reduce方法的输出被写入HDFS文件系统中。

2 并行Fp-Growth算法实现

2.1 经典频繁模式挖掘方法

关联规则算法的核心在于如何高效地找出满足最小支持度的频繁项集[6]。针对这一问题，Agrawal与R·Srikant在1994年提出了Apriori算法，该算法中用到一个频繁项集的重要性质，即频繁项集的所有非空子集也是频繁项集，这样大大减少了候选项集的数量。然而，当频繁项集较多、事务数据库较大时，该算法的开销依然很大。为了克服Apriori的种种不足，韩家炜等[7-9]提出了基于频繁模式树的Fp-Growth算法，在Fp-Growth算法中采用了分治的策略：首先，扫描事务数据库，将代表频繁项集的事务压缩成一颗频繁模式树；然后，将这种压缩后的数据库划分为一组条件数据库，并分别对每个条件数据库进行挖掘，以此递归，直到找出所有频繁项。

Fp-Growth算法通过对原始事务数据库进行压缩，映射为内存中的一个频繁模式数据，而后对该树递归挖掘，从而找出所有的频繁项集。这极大提高了频繁项的查找效率，比Apriori算法大约快了一个数量级[10]。然而，当事务数据增大到一定程度时，单台计算机的内存将不足以存储构建的巨型频繁模式树，计算资源也难以支持对这种巨型频繁模式树进行递归挖掘的计算。因此，随着事务数据的不断增大，单节点的Fp-Growth算法将面临时间和空间的双重瓶颈[11]。对Fp-Growth算法进行并行化改造可以解决这一问题。Fp-Growth算法的并行化将利用多个节点的内存与计算资源，解决单节点算法的时间和空间瓶颈。本文将详细探讨基于MapReduce的Fp-Growth算法的并行化改进算法FPMMR（Frequent Pattern Mining based on MapReuce）。endprint