一种基于MapReduce的频繁项集挖掘算法
2015-04-30孙兵率
孙兵率
摘要摘要：随着大数据时代的到来，针对Apriori算法和FPGrowth算法在挖掘海量规模数据频繁项集时，存在内存不足、计算效率低等问题，提出一种Aggregating_FP算法。该算法结合MapReduce并行计算框架与FPGrowth算法，实现频繁项集的并行挖掘，对每个项进行规约合并处理，仅输出包含该项的前K个频繁项集，提高了海量数据决策价值的有效性。在Hadoop分布式计算平台上对多组规模不同的数据集进行测试。实验结果表明，该算法适合大规模数据的分析和处理，具有较好的可扩展性。
关键词关键词：频繁项集；MapReduce；Hadoop；可扩展性
DOIDOI：10.11907/rjdk.151007
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2015）004007503
0引言
随着大数据时代的到来，数据库的容量越来越大，已经达到PB，甚至EP水平，传统的数据分析方法和技术不能完全满足数据处理需要。为能快速得到隐藏在海量数据背后的具有决策价值的知识，需要结合当前数据技术开拓新的数据挖掘方法。
MapReduce[1]是Google提出的利用集群来处理大规模数据集的并行计算框架，Hadoop[2]是Apache基金会开发的一个分布式系统架构，其开源实现了MapReduce。Hadoop通过组织一定规模集群，构建分布式平台对大规模数据进行计算和存储，已经成为目前主流的云计算技术平台。国内外诸多学者在Hadoop平台上基于MapReduce对数据挖掘算法进行了研究[35]。
频繁项集挖掘是关联规则分析的关键步骤，针对Apriori算法和FPGrowth算法在挖掘海量规模数据频繁项集时的性能瓶颈，本文提出一种Aggregating_FP算法，该算法运用了MapReduce并行计算框架与FPGrowth算法“分而治之”的思想。
1相关概念
1.1频繁项集
假设I={i1，i2，…，in}是项（Item）的集合，给定一个事务数据库D={T1，T2，…}，其中每个事务（Transaction）Ti是I的非空集合，即TiI，每一个事务都与一个唯一的标识符TID相对应。项的集合称为项集（Itemset），事务T是项的集合，并且TI，设A、B分别是I中的一个项集。
定义1：规则A→B在数据库D中具有支持度S，表示S是D中事务，同时包含AB的百分比，它是概率P（AB），即：
S（A→B）=P（AB）=ABD（1）
其中，|D|表示事务数据库D的个数，|AB|表示A、B两个项集同时发生的事务个数。
定义2：项的集合称为项集（Itemset），包含k个项的项集称为k项集。如果项集满足最小支持度，则它称之为频繁项集（Frequent Itemset）。
1.2MapReduce
MapReduce采用“分而治之”的思想，将一个大的计算任务分解为多个较小的子任务，子任务的计算过程相互独立，分发到集群中各节点分别执行，再将各节点的执行结果进行汇总，得到最终结果。MapReduce计算过程分为两个阶段：Map（映射）和Reduce（规约），Map负责执行分解后的子任务，得到一系列中间结果；Reduce负责将这些中间结果进行汇总规约。图1描述了MR的运行机制。
2频繁项集算法
2.1Apriori算法
Apriori算法是目前频繁项集挖掘算法中最为经典的算法，Apriori算法通过逐层迭代的方式挖掘频繁项集，面对海量数据，存在性能瓶颈：①事务数据库扫描次数过多，I/O负载过大；②可能产生数量庞大的候选项集。
2.2FPGrowth算法
FPGrowth算法采用“分而治之”的思想，首先将数据库的事务集压缩到一棵FPTree，然后对这颗FPTree进行递归挖掘，逐步得到频繁项集。但FPTree的大小受高度和宽度的双重影响，难免会存在以下缺陷：
（1）如果事务数据库D的规模达到海量级别，FPTree算法将所有事务数据库中的频繁项压缩至内存中的一棵频繁模式树，树的高度或宽度可能达到内存无法接受的规模。因此，这个过程可能会失败。
（2）FPGrowth算法挖掘频繁项集过程中，每一次递归计算都会生成一颗新的条件频繁模式树，每一次遍历条件频繁模式树的时间消耗占据了该算法时间复杂度的主要部分，当面对海量规模的数据集，该算法的处理能力在空间维度和时间维度上都将会达到极限。
3改进的频繁项集并行挖掘算法
FPGrowth算法的设计初衷是采用“分而治之”的策略，这与MapReduce并行计算框架的核心思想是不谋而合的。结合MapReduce计算框架，对FPGrowth算法的构造树、挖掘树等过程进行并行化改进，不失为解决海量数据性能瓶颈的一种途径。为提高输出频繁项集数据的有效性，挖掘出所有的频繁项集后，不直接输出，而作进一步改进。改进如下：分别对包含某一项item的所有频繁项集进行规约合并，筛选出关联度最高的前K个频繁项集进行组合输出。整个改进处理过程，称之为Aggregating_FP算法。该算法从两个方面实现FP_Growth算法的并行改进：
> 分散存储
> 并行计算
Aggregating_FP算法需要利用3个MapReduce任务来完成频繁项集的挖掘，即先后启动3个Job任务，分别定义为：Job_Counting，Job_Generating和Job_Aggregating。算法流程如图2所示。其中，Job_Counting的主要任务是并行统计事务数据库中所有项的支持度；Job_Generating的主要任务是根据事务集的分组情况，构建各节点的本地FP_Tree，挖掘各组包含的频繁项集；Job_Aggregating的主要任务是归并各组挖掘结果，输出最后的频繁项集。
3个MapReduce任务在Aggregating_FP算法中分别发挥不同的作用，而每个Job任务均需要通过设计Map函数和Reduce函数来实现，具体设计过程如下：
3.1Job_Counting任务分析
Job_Counting通过设计Map函数和Reduce函数，统计整个事务数据库中所有项的支持度。
完成Map函数的所有输入后，MapReduce框架会先合并具有相同key'的value'（可能是{1，1，…，1}），成为一个集合S（key'），然后将键值对作为输入传至Reduce函数。
Reduce函数统计计算不同节点传递过来的S（key'），输出sum（S（key'）），即为项Skey'的支持度计数。结果命名为FList。
3.2Job_Generating任务分析
为达到可行的并行计算，各节点构造的本地FPTree规模不能太大。先将FList中的项划分为Q组，分别给此Q组项集赋予一个独立的groupID，组成一个GList。
Map函数的主要任务是根据GList分组情况将本地事务数据集生成相互独立的Q个事务组。Map函数输入格式
Reduce函数的主要任务是对分配给本节点的组号为groupID的所有事务集进行频繁项集挖掘。与传统算法FPGrowth不同，递归过程中不需要遍历整个表头，只需遍历GList中与组号groupID对应的项。为了更好地适应海量数据的频繁项集挖掘，在递归创建模式子树中，发现符合条件的模式组合后并不直接输出，仅输出前K个具有较高关联度的频繁项集。Reduce最终输出格式定义为：
3.3Job_Aggregating任务分析
Job_Aggregating的任务是读取Job_Generating中所有Reduce函数实例输出，对于每一个项aj，输出与其相关的K个关联度最高的频繁项集。
Map函数输入格式
MapReduce框架汇总合并key"相同的键值对，传递给Reduce函数，输入格式形如，其中S（aj）是所有含项aj的频繁项集集合，Reducer函数从集合S（aj）中筛选出支持度最高的前K个频繁项集并输出。
4实验结果与分析
试验环境：服务器安装vSphere虚拟化软件，创建10个虚拟机，安装Hadoop1.2.1，搭建Hadoop集群，包括1个NameNode，9个DataNode。其中，服务器参数配置：64bit X86处理器，32G内存，1T硬盘空间。
本试验数据集源自http：//fimi.ua.ac.be/data/，该数据集由比利时某超市零售店提供，认为每条记录表示一个顾客的一次购物行为，一次购物行为表示一个事务，而每个事务对应的项表示顾客一次购买的商品。
本实验用Hadoop MapReduce实现Aggregating_FP算法，并在不同数目节点的集群中对3个不同规模的数据集进行频繁项集挖掘，实验过程中，支持度阈值取为200，FList分为100组，令参数K=50，3个数据集T1，T2、T3分别包含的记录数据为88 163条、420 815条和2 104 075条。
当Hadoop集群中节点数为1，3，5，7，9时，测试T1，T2，T33个数据集在集群中Aggregating_FP算法的并行计算执行时间，结果如图3所示。可以看出，当数据规模较大时，随着集群节点数目的增加，集群的并行计算效率有很大提升，说明并行Aggregating_FP算法适于大规模数据的频繁项集挖掘。
统计数据集T1，T2，T3分别在1，3，9个节点的集群中执行时间。结果显示，随着数据集规模的增大，通过增加集群节点，算法的执行时间呈平稳的平滑曲线，集群计算能力具有很好的可扩展性。
5结语
本文探讨了Apriori算法和FPGrowth算法在对海量规模数据进行频繁项集挖掘时的性能瓶颈，提出了一种Aggregating_FP算法，并基于Hadoop平台对频繁项集的并行挖掘过程进行了研究和实现。试验结果表明，该并行算法具有很好的可扩展性，通过对频繁项集结果的进一步处理，提高了海量数据决策价值的有效性。
参考文献参考文献：
[1]DEAN J， GHEMAWAT S.MapReduce： simplified data processing on large clusters[J].Communications Of The ACM，2008，51（1）：107113.
[2]APACHE HADOOP.Hadoop[EB/OL].http：//hadoop.apache.org.
[3]虞倩倩，戴月明，李晶晶.基于MapReduce的ACOKmeans并行聚类算法[J].计算机工程与应用，2013，49（16）：117120，136.
[4]曾青华，袁家斌，张云洲.基于Hadoop的贝叶斯过滤Mapreduce模型[J].计算机工程.2013，39（11）：5760，64.
[5]ZHUOBO RONG.Complex statistical analysis of big data：implementation and application of apriori and FPGrowth algorithm based on MapReduce[C].Proceedings of 2013 4th IEEE International Conference on Software Engineering and Service Science （ICSESS）， Beijing， IEEE， 2013：968972.
责任编辑（责任编辑：陈福时）
