MRClose：一种基于MapReduce的并行闭频繁项集挖掘算法
2018-01-17胡娟
胡娟
频繁项集挖掘是最重要的数据挖掘任务之一，闭频繁模式项集是频繁项集的一种无损压缩形式，具有挖掘效率高、无冗余信息等优点。在大数据时代，基于单机的闭频繁项集挖掘算法不能适应海量数据的挖掘需求，需要并行的算法来解决。本文分析了并行闭频繁项集挖掘中搜索空间划分、剪枝策略的策略选择，设计了一种并行的全局闭项集筛选方法，提出一种基于MapReduce计算模型的并行闭频繁项集挖掘算法MRClose。实验表明提出的算法实现了较好的均衡负载和低I/O量，在执行效率和结果压缩两方面较并行频繁项集挖掘算法具有更好的效果。
【关键词】数据挖掘 并行 闭频繁项集挖掘 MapReduce Hadoop
1 引言
频繁项集挖掘（Frequent Itemset Mining，FIM）是最重要的数据挖掘任务之一，也是关联规则、分类、聚集、关联等众多数据挖掘任务的基础，自它被提出以来，受到了越来越多的关注。经典的FIM算法可以分为三类：“产生-计数”方法如Apriori、DHP、DIC等、“模式增长”方法如FP-Growth、LP-Tree、FIUT、IFP、FPL/TPL以及基于垂直数据格式的算法如Eclat等。闭频繁项集（Closed Frequent Itemset，CFI）是频繁项集的一种压缩形式，在尺寸上比频繁项集有较大地减少，消除了信息冗余且没有信息丢失，有利于挖掘结果的进一步使用。可以通过将FIM问题转换为CFIM问题来提高频繁项集挖掘效率。
与FIM类似，经典的CFIM算法也可以分为三类：“产生-计数”方法如A-Close等、“模式增长”方法如CLOSET、CLOSET+、AFOPT-Close等以及基于垂直数据格式的如CHARM等。随着信息技术的飞速发展，人类已经进入了大数据时代，需要分析和挖掘的数据量呈爆炸式增长，传统的单机算法已经不能满足大数据挖掘的要求，主要挑战是：单一计算机无法存储所需要挖掘的所有数据及挖掘过程中产生的中间结果；挖掘过程所需要的内存远远超过单一机器的存储量；计算时间太长无法忍受等问题。需要设计并行的CFIM算法解决上述问题。
MapReduce是一种简单易用的并行编程模型，由Google于2004年提出，因其自动容错、负载均衡、伸缩性好等优点，已有很多数据挖掘方法实现了基于MapReduce计算模型的并行化，显示出这种计算模式适用于多种并行数据挖掘任务。MapReduce计算模型流程图如图1所示。
Hadoop是MapReduce的一个开源实现，其核心组件是一个分布式文件系统HDFS及MapReduce并行编程模型。HDFS自动将海量数据进行分片，分别存储集群中不同的节点上；Map方法在存储数据分片的节点运行，通过数据本地化、减少IO来提高运行的效率。
陈光鹏等提出了一种基于MapReduce的CFIM并行算法，实现了经典算法AFOPT-Close算法的并行化，并討论了并行化后带来的局部闭项集和全局闭项集不一致的问题。Wang等将上述算法进行了改进，主要提升了检查局部闭项集是否为全局闭项集的效率。Gonen等实现了一种基于MapReduce的CFIM并行算法，算法使用了A-Close的基本思想，通过迭代产生G1-Gk（长度1～k的generators）及其闭项集，每一次迭代使用一个MapReduce任务实现，最后对所有计算得到的闭项集进行重复检查删去重复项，得到全局闭项集。
本文设计了一种并行的全局闭频繁项集筛选方法。提出了MRClose算法，该算法基于“模式增长”方法的基本思想和搜索空间划分策略，实现了对局部闭频繁项集的并行过滤。
2 相关研究讨论
Lucchese等提出了一个基于多核CPU的并行DCI-Closed算法MT-Closed，实现了CFIM的并行化，但该算法基于单一计算机的多线程架构，线程的数量是有限的，线程之间需要共享内存，海量数据无法装入单一计算机的内存中进行计算； D-Closed算法与MT-Closed类似，通过迭代搜索子树来搜索闭频繁项集，是一个分布式的并行CFIM算法，但它仍需要在不同节点之间共享搜索索引及候选的闭频繁项集。
已有一些研究将传统CFIM算法向MapReduce计算模型进行了迁移。陈光鹏等提出了一种基于MapReduce的CFIM并行算法，实现了经典算法AFOPT-Close算法的并行化。它的设计思想和基于MapReduce的FIM算法PFP十分相似，通过三个MapReduce任务完成并行挖掘。文献[9]通过减少第三个任务的I/O数据量进一步提升了上述算法的性能。Gonen等提出的基于MapReduce的CFIM算法基于A-Close算法的基本思想，通过多次迭代产生长度1～n的等价类最小闭项集G1～Gi及它们的闭包。现有算法主要是将CFIM的经典算法向MapReduce计算模型进行了迁移，没有从并行计算的负载均衡、降低I/O数据量等重要方面考虑CFIM并行化中关键问题的策略选择问题。
3 提出算法
本文提出的算法MRClose基于“模式增长”方法的基本思想和搜索空间划分策略，算法使用FP-Tree压缩存储子搜索空间，在并行挖掘局部闭频繁项集的过程中使用引理1、item skipping策略进行剪枝，对局部挖掘结果使用引理2进行校验。最后并行执行全局闭频繁项集的筛选，得到全局闭频繁项集。
给定一个事务数据集D和最小支持度minsup，算法主要包含5个步骤，主要框架如下：
Step 1：数据分片及存储。将数据集D分为若干个连续的分片，每个分片分别存储在集群中的计算节点上，一个节点可以存储一个或多个数据分片。这个过程可以由HDFS自动完成。
Step 2：并行计数。并行计数是MapReduce计算模型的经典用法，十分容易实现，可以使用一个MapReduce任务来统计D中所有项的支持度，得到频繁项的集合FList。endprint
Step 3：分组频繁项。若FList={I1，I2，…，In}，则整个搜索空间可以划分为{g（I1）， g（I2），…，g（In）}n个子搜索空间。当|FList|的值很大时，会在并行挖掘阶段产生n个子挖掘任务，带来极大的系统初始化成本、高I/O，也不利于负载均衡。为了减少子搜索空间的数量，可以将n个频繁项进行分组。设将n个频繁项分成m组，第i组中有得频繁项为{Ij，…，Ik}，则第i个子搜索空间为{g（Ij）∪，…，∪g（Ik）}，当g（Ij）∩g（Ik）≠□时，可以减少子搜索空间的事务数，进而可以减少节点之间的I/O数据量。为了进一步实现负载均衡，可以根据频繁项的支持度进行平衡分组。
Step 4：生成子搜索空间，并行挖掘局部闭频繁项集。这是算法最核心的步骤，使用一个MapReduce任务完成。Map方法输入每一条事务数据Ti，将Ti中非频繁项删去，剩下的频繁项按照FList中项的顺序进行排序得到Ti。若Ti中的所有项分属于m个组，则针对每个组输出<组号， Ti>，实际上生成的是所有子搜索空间。每一个Reduce处理一个组号相关的所有事务，构造FP-Tree后，使用FP-Grwoth算法进行挖掘，在挖掘过程中运用剪枝策略加快挖掘过程。最后该阶段得到的是所有的局部闭频繁项集。
Step 5：过滤得到全局闭频繁项集。该阶段可以使用一个MapReduce并行执行。Map方法读取每一个局部闭频繁项集，输出
4 实验结果分析
实验环境使用基于MapReduce计算模型的开源系统Hadoop 1.2.1做为平台搭建集群，具体方案为如下：使用1台计算机做为Master节点，CPU为 i7-4790 3.60Gz 8核，内存8G，操作系统为Red Hat Enterprise Linux Server 6.6，Java平台为Java 1.6；使用6台计算机做为Slave节点，CPU为 i3-4150 3.50Gz 4核，内存4G，操作系统为Red Hat Enterprise Linux Server 6.6，Java平台为Java 1.6。集群计算机之间使用百兆以太网相互连接。
为了适应实验数据集尺寸较小，提高并行化程序以优化集群的性能，实验环境将HDFS文件块的大小设置为256KB（默认为64MB）以增加Map任务数；将reduce任务数设置为12以充分利用每个计算节点的计算能力（平均每个节点执行2个reduce任务）。使用Java语言编写PFP和MRClose算法，比较两个算法的效率及结果压缩率。使用的实验数据集特征如表1所示。
retail是来自于FIMI的真实数据集，是一个非常稀疏的数据集；T10I4D100K是一个使用IBM Quest Data Generator生成的合成数据，相对来说比retail要密集一些。
4.1 实验结果分析
PFP和MRClose算法在retail数据集上最小支持度分别为0.01%、0.025%、0.05%时的执行时间如图2所示。
PFP和MRClose算法在retail数据集上最小支持度分别为0.01%、0.025%、0.05%时的结果集尺寸如图3所示。
从图2和图3可以看出：
（1）MRClose算法在稀疏数据集上的加速性十分有限，主要原因在于由稀疏数据压缩得到的FP-Tree具有分支很多、共享前缀很少的特征，运用剪枝策略减去的搜索空间在总搜索空间中的比重很低，对算法加速性贡献有限。
（2）MRClose算法在稀疏数据集上仍表现出了较好的结果压缩比例，压缩率与最小支持度呈反比。
PFP和MRClose算法在T10I4D100K数据集最小支持度分别为上1%、2%、5%时的执行时间如图4所示。
PFP和MRClose算法在T10I4D100K数据集最小支持度分别为上1%、2%、5%时的执行的结果集尺寸如图5所示。
从图4和图5可以看出：
（1）MRClose算法在密集数据集上的加速性比在稀疏数据集上有所提高，加速性与数据集的密集程度呈正比，与最小支持度也成正比，主要原因在于由密集数据压缩得到的FP-Tree具有更多的共享前缀，共享前缀越多，运用剪枝策略减去的子搜索空间也越大，对算法加速性贡献越大。
（2）数据集越密集，|L|和|G|之间的差值则越小，算法压缩率与最小支持度呈反比。
（3）从图2和图4可以看到，由于MRClose算法采用了均衡分组的策略，实现了较好的负载均衡。但在并行计算中，对算法效率有决定性影响的已不在是单个节点的计算效率，负载均衡、I/O数据量有更加显著的影响。在挖掘L时虽然運用了剪枝策略，但对整个算法的效率提升作用仍是比较有限的。
5 总结
本文讨论了并行CFIM算法在搜索空间划分、剪枝策略、全局闭频繁检查这三个关键方面的策略选择，提出了一种基于MapReduce计算模型的并行CFIM算法，算法MRClose基于“模式增长”方法的基本思想和搜索空间划分策略，采用FP-Tree压缩存储子搜索空间，在并行挖掘局部闭频繁项集的过程中进行了剪枝，对局部挖掘结果进行了并行筛选。实验验证了MRClose算法在负载均衡、算法加速、全局结果集筛选等方面的有效性。算法持续改进可以从两个方面来考虑：
（1）子搜索空间划分采用更加有效的数据结构存储，提高并行挖掘L的效率（特别是针对稀疏数据集提高剪枝策略的效率）；
（2）从L中并行筛选G时进一步考虑负载均衡的问题。
参考文献
[1]Han Jiawei，Kamber M.Data Mining： Concepts and Techniques[M].London，UK： Morgan Kaufmann，2006.
[2]N.Pasquier，Y.Bastide，R.Taouil，and L. Lakhal，Discovering frequent closed itemsets for association rules， Database Theory-ICDT99，1999，398-416.
[3]Pei Jian，Han Jiawei，Mao Runying. CLOSET：an efficient algorithm for mining frequent closed itemsets[C].Proc of the ACM SIG-MOD International Workshop on Data Mining and Knowledge Dis-covery.Dallas，USA，2000：21-30.
[4]Wang Jianyong，Han Jiawei，Pei Jian.CLOSET +：Searching for the best strategies for mining frequent closed itemsets[C].Proc of the 9th ACM SIGKDD International Conference on Knowledge Dis-covery and Data Min-ing.Washington，USA，2003：236-245.
[5]M.J.Zaki and C.Hsiao.CHARM：An efficient algorithm for closed itemset mining.Technical Report 99-10，Rensselaer Polytechnic Institute，1999.
[6]Liu Guimei，Lu Hongjun，Xu Yabo，et al.Ascending frequency ordered prefixtree：efficient mining of frequent patterns[C].Proc of the 8th International Conference on Database Systems for AdvancedApplica-tions.Kyoto，Japan，2003：65-72.
[7]Welcome to ApacheHadoop！[EB/OL].[2017-01-10].http：//hadoop.apache.org/.
[8]陈光鹏，杨育彬，高阳等.一种基于MapReduce的频繁闭项集挖掘算法[J].模式识别与人工智能，2012，25（02）：220-224.
[9]Wang S Q，Yang Y B，Chen G P，et al.MapReduce-based closed frequent itemset mining with efficient redundancy filtering[C].Proc of IEEE，International Conference on Data Mining Workshops.IEEE Computer Society，2012：449-453.
[10]C.Lucchese，S.Orlando，and R.Perego， Parallel mining of frequent closed patterns：harnessing modern computer architectures in DataMining[C]//Proc of ICDM 2007.Seventh IEEE International Conference on.IEEE，2007，pp.242-251.
作者單位
河海大学文天学院 安徽省马鞍山市 243000endprint
