基于MapReduce的频繁模式挖掘算法的优化
王 波，王怀彬，张 超
【摘 要】分布式数据挖掘计算是大数据研究中非常重要的技术，现有的对频繁模式的分布式挖掘方法在处理大量数据集时仍然存在许多局限，如并行Apriori算法在多次扫描数据库过程中对I/O产生很大负担，并且有大量候选集产生.本文使用的FP-growth算法包括Fp-tree构建和频繁模式挖掘两个阶段.主要思想是在map阶段构建FP-tree之前，根据步长值及项目元素编码对FP-tree节点合并，并在shuffle阶段依据平衡算法划分给不同的reducer.平衡算法用来均衡工作负载.利用该算法来降低数据分配的随机性，避免数据挖掘阶段由于数据划分不均衡导致部分reducer开销过大的缺点.实验结果表明：与现有方法相比，在较大数据集情况下改进后的算法具有更好地运算效率和可伸缩性. 【期刊名称】天津理工大学学报 【年(卷),期】2018(034)001 【总页数】6
【关键词】MapReduce；频繁模式挖掘；FP-growth算法；平衡算法 大数据已经成为信息产业和社会中重要的研究领域，关联分析的目的是在大规模数据集中寻找隐藏在数据间的相互关系，这些关系可以表现为频繁项集或关联规则.现有的频繁模式挖掘算法主要有两类，一类是Apriori原理的算法[1-2]，主要是基于传统的Apriori算法进行改进，另一类算法和Apriori算法的结构完全不同，这些算法中FP-growth算法更加高效.对于大规模数据集，Apriori算法候选集过多需要重复扫描数据库导致程序效率比较低，其中一种解决方案通过设计一种更加有效地算法减少数据库扫描来降低I/O的负担.FP-growth算法
在2000年由韩家炜等人提出，算法采用分治策略将频繁项集数据以树的形式进行存储[3]，频繁模式树（FP-tree）中存储了频繁项集和关联信息，整个算法只需要扫描2次数据库.
MapReduce分布式处理框架可并行化处理大规模数据，并将许多机制封装起来，处理并行编程中分布式存储、工作调度、负载均衡以及网络通信等复杂问题，把处理过程高度抽象为map和reduce两个函数.具有顺序处理数据和节点就近分配数据等特性，数据扩展和系统规模扩展性良好[4].如今，并行分布式计算技术相当成熟，使得MapReduce框架应用更加广泛[5-7].Farzanyar Z等人提出了基于MapReduce的IMRApriori算法，使Apriori算法实现了并行化，通过支持度阈值的设定和mapper的数量关系减少了候选项集[8]，然而这种方式仍然需要多次读取数据库.LI Long-shu等人对FP-growth算法的MapReduce化进行了研究，通过实验证明了并行化改进后的MR-FP算法在事务呈数量级的增长的情况下仍有较高的性能[9].并行化过程中把相同项目结尾的patten输出到一个reducer里面，在reducer中仅对这一部分patten建立FP-tree[10]，虽然这种FP-tree会小很多，一般不会占用太多的内存，但是不同数据集长度构建的FP-tree复杂程度差异可能较大，在项集本身元素较多和大数据集情况下容易导致某些reducer的负载过大，因此，分配数据给reducer时应该考虑项集的复杂程度，以此减少数据分配时的随机性.
Hong-Yi Chang等人利用MapReduce模型把FP-growth和Apriori算法进行了结合，将所有数据分为不同组，每组数据在mapper阶段使用FP-tree存储候选集，在reducer阶段使用Apriori算法根据最小支持度进行计算[11]，这样的存储方式减少了传统Apriori算法多次扫描数据库所造成的过大I/O负
担，同时简化了传统FP-growth算法较为复杂的数据结构，充分利用了MapReduce中对于数据以键值对形式＜key，value＞的处理方式.但是在实验中，reducer占用了较多执行时间，主要原因是mapper输出的键值对过多并且比较复杂，导致shuffle排序操作比较耗时.
本文提出了一种基于MapReduce的FP-growth算法的优化方法，并将传统和本文提出方法的实验结果进行对比.
1 FP-growth算法
FP-growth算法将数据以FP-tree的形式存储，不需要生成候选集就可以完成Apriori算法的功能，整个过程分为两步[12]. 1.1 创建FP-tree
1）第一次扫描数据库，统计每个频繁项集元素的支持度，并将其按照降序排列，记为T.
2）再次扫描数据库，将频繁项集根据T重排.重排后的数据插入以null为根节点的FP-tree中.如果插入节点已经存在则支持度加1，否则创建支持度为1的节点，该节点指向项头表对应的元素. 1.2 挖掘FP-tree中的频繁模式
FP-growth是一种自下而上的搜索算法[13].从项头表中频率最低的元素开始向前遍历，根据节点支持度组合出满足条件的频繁项集.如果遍历的路径为单个路径，可直接进行组合，否则将多路径分解为单路径.伪代码如下：
2 Fp-tree节点合并与平衡算法
2.1 MapReduce模型
对于海量数据，FP-growth需要递归构建FP-tree，并且频繁遍历FP-tree，
基于MapReduce的频繁模式挖掘算法的优化
