基于传递收缩剪枝策略的并行频繁项集挖掘算法的研究

□ 赵明

基于传递收缩剪枝策略的并行频繁项集挖掘算法的研究

□ 赵明

关联分析作为数据挖掘中探寻事物之间联系紧密程度的方式之一，被广泛应用于商业，社交分析等领域，其中如何高效挖掘到频繁项集一直都是研究重点。FP-growth以频繁模式树FP-tree为数据结构，极大降低了I/O吞吐，且利用并行计算，提高了计算效率。但因其需要占用大量内存，使得并行规模受到限制。本文设计了基于传递收缩剪枝策略的FP-growth算法，通过限制FP-tree的搜索空间，及时进行剪枝项合并，并将其在分布式平台Spark并行化。通过实验对比证明，较Hadoop上提升25%；相比原有的FP-growth算法PFP，在Spark平台计算提升10%左右。

FP-growth算法；频繁项集挖掘；传递收缩剪枝策略；Spark；

关联规则作为寻找海量数据中事物联系紧密程度的方法之一，随着近几年电子商务的迅猛发展，在商业领域中，显示出了强大的生命力。而对频繁项集的挖掘，作为关联规则的核心思想，已成为各类学者研究的焦点。但当其面对互联网的海量数据时，计算量和I/O量都非常大，传统的串行算法已不能胜任，通过并行化频繁项集挖掘算法拓展它们的使用场景。

频繁项集挖掘算法FP-growth，虽降低了对数据库的I/ O，但其在构建树形结构时，仍占用了大量的内存资源。虽可以使用并行化可以缓解其过高的内存占用，但因其依赖进程间的通信来协调树形变化，往往导致并行计算效率较低、内存开销大且不能够实现多节点的横向扩展。对此本文提出了如下创新点：

（1）TCPFP(Transitive Compression Pruning FP-growth algorithm)算法利用了传递收缩剪枝策略对FP-growth频繁项集的搜索空间进行限制，通过传递收缩剪枝，及时进行项合并，降低了内存占用，提高算法挖掘速度。

（2）在Spark平台上并行化了基于传递收缩剪枝的FP-growth算法TCPFP。利用其弹性分布式数据集及基于内存计算模式，在对比传统的FP-growth算法在Hadoop或Spark平台的挖掘效率上，提升挖掘效率10%。

一、关联规则挖掘算法

Apriori算法作为关联规则的经典挖掘算法之一，利用了频繁项集的先验知识。将频繁项集中任意一非空子集划为频繁项集。但其运算过程中，需要占用巨大的I/O，拼接产生过多的候选集，效率不高。之后也有利用动态项集计数算法DIC(Dynamic Itemset Counting)；或是采用分治法的思想来解决内存不够用的分块挖掘算法(Partition)等。

相比Apriori算法，2000年提出FP-growth算法以频繁模式树为基础，只扫描两次数据库，大大降低了I/O吞吐。采用深度优先的搜索方式，提高挖掘效率。FP-growth算法有两个主要步骤：1.频繁模式树FP-tree的构造；2.对FP-tree进行频繁模式挖掘。FP-tree构造时，将数据库中所有的记录信息压缩进去，保留每条交易记录中数据项之间的联系。通过扫描数据库，计算出所有的频繁1-项集，并按支持度计数排序，删去小于最小支持度的频繁项；再来插入到FP-tree中，通过共享相同的数据项前缀，把项头表(Header table)中的每个频繁项链接到FP-tree中去。然后，对频繁模式进行挖掘。若FP-tree中的含有单个路径L，则直接抽取条件模式基；若不包含单个路径，则对项头表中每个元素生成条件模式。然后构造其元素的条件模式基和条件模式树，若条件模式树不为空，则递归找出所有的频繁项集。

传统单线程递归挖掘频繁项集，效率底下，随着Ha⁃doop分布式并行执行的思想流传开来。国内外学者，将频繁项集挖掘与并行化结合起来，展开多方面的研究。Rion⁃dato等人将FP-growth算法以Hadoop框架为基础研究提出了PARMA算法，主要是采用减小事务集的大小从而得到时间上的节省。或利用数据本地化的思想减少FP-growth算法在Hadoop中的网络通信量。还有针对FP-tree和项头表的数据结构进行改进以及对单路径问题进行优化，并在Spark上并行实现的。但因其在内存中占用大量空间构建树形结构，会使其因数据项过多或过深导致FP-tree构造失败，或递归构建了空间复杂度过高的条件模式基。即便其利用了分布式计算平台，也需要消耗大量内存用于维护树形的进程通讯，会使得分布式节点难以横向拓展，并行优势无法彻底发挥出来。因此本文针对FP-growth算法内存占用高，搜索空间复杂，引入传递收缩剪枝策略对搜索空间进行限制，使得其在分布式平台Spark上有着较高的挖掘效率。

二、基于传递收缩剪枝策略的FP-growth算法TCPFP

1.符号定义及理论证明

在挖掘频繁项集中，我们定义叶子节点上的频繁项y。在FP-tree上，以y为起点，倒序遍历直到root的一串节点序列，我们称为y的传递路径R。即y和root节点的之间连接的一条路径，包含y本身以及root节点。一般的对于频繁项y，不止一条传递路径R。通过对传递路径进行收缩，删去频繁项y，作为y的传递收缩路径，简称收缩路径Rc。

Figure 1 Schematic diagram of FP-tree图1：FP-tree示意图

如上图所示，假设y为I3，则有R为{I3,I2,I4,Root},{I3, I5,I4,Root},{I3,I1,I5,I4,Root}三条路径。而对于I5来说，其传递路径只有一条{I5,I6,Root}。同理，我们可以得到频繁项I3的收缩路径Rc为{I2,I4,Root}，{I5,I4,Root}，{I1,I5,I4, Root}，而I5的收缩路径为{I6,Root}。

剪枝策略：传递收缩剪枝TCP。若频繁项y存在多条收缩路径Rc1到Rcn，路径之间存在非空交集。通过提取交集，合并收缩路径，将频繁项y的支持度累加计算，收缩路径的起点频繁项，减去因为收缩合并移除的支持度。

证明：若包含频繁项y的N个频繁项集中存在包含关系，如A包含B。但A不包含B的任何真超集，则令A∪B形成一个闭频繁项集。因此在两个频繁项集A,B中，y的收缩路径Rc1和Rc2存在交集路径Ry。则FP-tree在剪枝之前得到y的条件模式基为{{Rc1：m},{Rc2：n}}，产生的频繁模式为{Ry：m+n}。FP-tree在剪枝之后得到y的条件模式基为{Rc1∩Rc2：m+n}，产生的频繁模式为{Ry：m+n}。FP-tree在剪枝之后与剪枝前得到包含y的频繁模式一样。因此，下界路径Rc2就可以剪枝合并在路径Rc1上。

所以根据剪枝策略，对I3进行剪枝，则有三条收缩路径的Rc的交集为{I4,Root}，所以经过剪枝和项合并之后有R{I3,I4,Root}，生成的条件模式基为{I3,I4,Root：6}。

2.算法流程设计

在建立好频繁模式树FP-tree之后，我们可以利用传递收缩剪枝策略TCP来对FP-tree进行剪枝和挖掘，其操作步骤如下：

第一步：判断建立好的FP-tree是否包含无分支的单路径，若存在单路径R，把该路径R中每个元素和模式合并生成频繁项集，条件模式基即为生成的频繁模式记为{R：m}，m为路径R中节点的支持度。

第二步：从底部开始遍历FP-tree的项头表Header ta⁃ble，得到每个叶子节点上的频繁项y的传递路径R，并将所有传递路径按频繁项统计出来，得到所有频繁项y在FP-tree上的传递路径R1～Rn。

第三步：将传递路径进行收缩，在对应频繁项路径集合中，删去该频繁项y，获得收缩路径Rc1到Rcn。

第四步：寻找每个频繁项的收缩路径中是否存在交集，若存在提取交集，剪枝合并，将支持度叠加的同时减去上一级的支持度。

第五步：检查FP-tree经过剪枝合并后，判断频繁项是否存在多条传递路径，若是回到第一步，如果不是则继续向下执行第六步。

第六步：对项头表中的每个频繁项y，生成频繁模式记为{Ry：m}，该模式中的m等于y的支持度。

根据算法TCPFP，图1中的FP-tree有I3和I1作为叶子节点上的频繁项，其收缩路径存在交集，其中I3提取交集之后其路径R为{I3,I4,Root}，I1为{I1,Root}。在进行项合并时，与I3直连枝干节点，支持度会降低。所以可以看到，原有的I2,I5会因I3合并，支持度分别将至0和1。剪去支持度为0的枝干，构成新的FP-tree如图2。

Figure 2 The FP-tree after pruning图2：经修剪之后的FP-tree

三、Spark并行化

Spark作为分布式并行数据处理框架，利用了MapRe⁃duce计算思想，将job基于内存模式进行并行计算，省去了Hadoop中大量的磁盘上的I/O。对于FP-growth算法的并行化，主要通过并行投影的方式对数据库进行划分，再对每个投影数据库进行FP-growth处理。按照MapReduce的计算思想，操作分为三步。

第一步：数据切分与并行计数。这里不同的分布式计算平台会有着不同的方案，Hadoop会利用HDFS设定的block（通常为64MB）来切分存储在不同的DataNode的节点磁盘上；Spark会利用弹性式数据分布集RDD将数据库中的数据序列化后引入内存。然后，我们可以通过Mapper方法将每个投影数据库中的项并行统计，得到形如＜key=”items”，value=”sum”＞的键值对；通过Reducer方法对所有键值对按照value值排序，删除不满足最小支持度的键值对。

第二步：均衡分组。将每个投影数据库中的频繁项gid均衡分组，使得分布式处理能力相差不大，并将分组情况写到一个频繁项分组表Glist中去。

第三步：FP-growth挖掘。利用多个job在不同的主机上分别处理不同的投影数据库。Mapper端根据Glist来产生互不依赖的事务记录。Reducer端对这些来自不同分组的数据库建立FP-tree进行频繁项集挖掘。

算法TCPFP在Spark上面并行化的时，会在第三步操作有所不同，即频繁项集的挖掘。其具体操作：

（1）map。读取Glist到内存中，删掉不在其投影上的频繁项，并根据出现顺序，将事务T中的前n项作为一个事务保留到gid的分组中去。生成形如＜key=“gid”，value= {t1,t2,…,tn}＞的键值对。

（2）combiner。将上一步并行分组后的互不依赖的事务记录，利用Combiner将键值对中key值一样的进行合并。方便后期生成FP-tree。

（3）reduceByKey。根据事务组中的记录，创建本地FP-tree。利用基于传递收缩剪枝策略的FP-growth算法限制搜索空间进行频繁项的挖掘。输出形如＜key=“num”，value=“itemsets”＞的键值对。

图3为整个FP-growth在Spark上并行化的流程示意图。通过从HDFS中读取数据库信息之后，Spark将整个计算过程包括中间结果都运行在内存上。降低了频繁的I/O。

Figure3 The process of FP-growth algorithm parallel exe⁃cution on Spark图3：FP-growth算法在Spark上并行执行的流程

相比于Hadoop将每一步的中间结果都会输出到HDFS中进行存储，一般HDFS都是由位于机架上的磁盘阵列构成，这个读取写入会占用大量的时间，降低处理效率。Spark利用了基于内存的读写模式，使得整体计算挖掘效率大幅提高。

四、实验结果及分析

为了验证TCPFP算法的有效性，本文设计了在分布式并行计算的环境下对比，原有的PFP（FP-growth）算法与TCPFP算法，以及TCPFP在Spark以及Hadoop平台上的不同。

实验利用了4台主机搭建而成的Hadoop集群，统一安装ubuntu14.04运行Hadoop2.6和Saprk1.5.2。使用JDK版本为1.8，Scala2.11.7。通过局域网将集群连接起来。采用电子商务网站的订单数据集总计400W条，通过复制拷贝增加数据集量。其四台主机的节点分布具体配置如表1.

Table 1 Experimental environment configuration表1 实验环境配置

通过配置不同的数据集大小，我们获得如图4中的测试结果。可以对比看出原有的PFP算法在Spark上运行时间，以及TCPFP在Hadoop和Spark上面运行时间的对比。

Figure4 The mining time of PFP and TCPFP on distribut⁃ed platforms图4：PFP及TCPFP在各分布式平台上的挖掘时间

可以很明显地看出Spark在对比Hadoop时有明显效率提升，约为25%以上的提升。利用了收缩剪枝策略的TCP⁃FP，比传统的频繁项集挖掘算法快10%左右。另外，我们在数据集拷贝4份达2000W条时，设立一组PFP与TCPFP的对比试验。针对性的分析对比其在各个Spark中各个阶段的用时长短。

Figure5 The comparison of operation time between PFP and TCPFP on Spark platform图5：Spark平台上PFP与TCPFP各阶段运算时间比较

从图5中可以看出，将TCPFP与PFP算法分步骤比较时，map和combiner阶段区别不大，其主要就是reduce⁃ByKey阶段，说明算法TCPFP能通过及时项合并与剪枝，减少了约12%的挖掘时间。

五、总结

针对原有频繁项集挖掘中的迭代次数多运算量，本文利用了Spark分布式平台，将原PFP算法进行并行计算。面对并行计算中的树规模变大导致的内存占用大，效率下降等问题，设计了基于传递收缩剪枝策略的TCPFP算法，实验对比了Hadoop平台中TCPFP，以及Spark平台中PFP的运算结果，证明TCPFP算法相比于PFP在Saprk平台上提升了挖掘效率10%左右。

[1]孟小峰，慈祥.大数据管理：概念、技术与挑战[J].计算机研究与发展，2013，50（1）.

[2]LAMINE M，NHIEN L，TAHAR M.Distributed Fre⁃quent Itemsets Mining in Heterogeneous Platforms[J]. Journal of Engineering，Computing and Architecture，2007，1(2)：1-12.

[3]Agrawal R，Srikant R.Fast algorithms for mining asso⁃ciation rules.20[J].Proc.int.conf.very Large Databases Vldb，1994，23(3)：21-30.

[4]Brin S，Motwani R，Ullman J D，et al.Dynamic itemset counting and implication rules for market basket data [J].Acm Sigmod Record，2001，26(2)：255-264.

[5]Savasere A，Omiecinski E，Navathe S B.An Efficient Algorithm for Mining Association Rules in Large Data⁃bases[J].Vldb Journal，1995：432-444.

[6]Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[J].Acm Sigmod Record，2000，29 (2)：1-12.

[7]马月坤，刘鹏飞，张振友,等.改进的FP-Growth算法及其分布式并行实现[J].哈尔滨理工大学学报，2016，(2).

[8]Riondato M，Debrabant J A，Fonseca R，et al.PAR⁃MA：A Parallel Randomized Algorithm for Approxi⁃mateAssociationRulesMininginMapReduce[C]// Proceedingsofthe21stACMInternationalConfer⁃enceonInformationandKnowledgeManagement (CIKM 2012).2012：85-94.

[9]章志刚,吉根林.一种基于FP-Growth的频繁项目集并行挖掘算法[J].计算机工程与应用，2014，（2）.

[10]邓玲玲，娄渊胜，叶枫.FP-growth算法改进与分布式Spark研究[J].微型电脑应用，2016，32（5）.

[11]HAN Jiawei，KAMBER Micheline.数据挖掘：概念与技术[M].北京：机械工业出版社，2013.

[12]谢朋峻.基于MapReduce的频繁项集挖掘算法的并行化研究[D].南京：南京大学，2012.

[13]Duong Q H，Liao B，Fournier-Viger P，et al.An effi⁃cient algorithm for mining the top-k，high utility itemsets，usingnovelthresholdraisingandpruning strategies[J].Knowledge-Based Systems，2016，104：106-122.

责任编辑：夏晓畅

湖北省咸宁市公安局。

TP392

A

2095-5103（2016）20-0079-04

10.11907/rjdk.1511517