前后部项约束关联规则并行化算法

时间：2024-05-04

孟月昊冯文林荣霞陈铭师

摘要：为了解决大规模数据环境下挖掘出的关联规则过多，用户需要耗费大量时间在这些关联规则中寻找自己感兴趣规则的问题，提出了一种基于Map/Reduce并行化编程模型的前后部项约束关联规则挖掘算法FRPFP。通过对用户感兴趣的规则前后部项进行标记和分组挖掘，并在各分组挖掘过程中根据标记的规则前后部约束项，对事务集进行压缩，从而筛选出有效的频繁项集，最终得到含有用户感兴趣项的关联规则。该算法在Spark框架中实现，实验结果表明，该算法能够有效地减少冗余规则的产生，计算开销较少，具有较好的规模增长性。

关键词：项约束; 关联规则; 数据挖掘; FRPFP算法

中图分类号：TP311.11 文献标识码：A 文章编号：1006-8228（2021）08-01-07

Parallel algorithm for fore-part and rear-part item-constrained association rules

Meng Yuehao， Feng Wen， Lin Rongxia， Chen Mingshi

（32753Army， Wuhan， Hubei 430010， China）

Abstract： To solve the problem that too many association rules are mined in large-scale data environments， users need to spend a lot of time to find the rules they interested in， a fore-part and rear-part item-constrained association rule mining algorithm FRPFP based on Map/Reduce parallel programming model is proposed. By marking and grouping the fore-part and rear-part items of the rules of interest to the user， and compressing the transaction set according to the fore-part and rear-part constraint items of the tagged rules during the group mining process， a valid set of frequent items is filtered out， and the association rules containing the items of interest to the user are finally obtained. The algorithm is implemented in Spark framework， and the experimental results show that the algorithm can effectively reduce the generation of redundant rules， which has less computational overhead and has better scale growth.

Key words： item-constrained; association rule; data mining; FRPFP algorithm

0 引言

目前，关联规则广泛应用于互联网领域的推荐系统[1]和点击流分析[2]等场景。在这些实际应用场景中，商家往往希望通过关联规则挖掘出用户感兴趣的、有明显规则前后部约束的逻辑关系。例如，购物篮分析可以研究“气候/时间→货物”的关系，从而指导电子商务巨头，如亚马逊、eBay等提高其销售策略。在这里，“气候/时间”是用户感兴趣的规则前部，“货物”是用户感兴趣的规则后部。但是传统的关联规则挖掘算法在面向大规模数据挖掘时存在一些不足之处，如挖掘出的冗余规则过多，用户需耗费大量时间对挖掘出的关联规则进行二次筛选来寻找自己感兴趣的部分。因此，迫切需要一种有效的并行化关联规则算法来提高挖掘用户感兴趣规则的效率。

关联规则的并行化研究主要聚焦于对经典的Apriori算法和FP-growth算法的并行化改造[3-6]。早期主要针对Apriori算法的并行化改造[7]。近年来，FP-growth算法的并行化改造研究相对多起来。文献[6]提出的PFP算法是目前应用较为广泛的FP-growth并行化的算法，其算法思想已在Spark MLlib工具包中实现。文献[8]提出的FPPM算法优化了FP-tree的构建方法，减少了冗余枝的生成，提高了并行化挖掘效率。由于未考虑项约束，这些算法在应对上述应用需求方面会生成大量冗余无关的关联规则。

当前，项约束关联规则[9-11]的研究成果在一定程度上可以应用于上述用户关心的逻辑需求。其中，文献[12-13]对前后部约束关联规则进行了形式化定义，描述了有明确的规则前后部约束的逻辑关系，并给出了基于Apriori和FP-growth算法的前后部约束关联规则挖掘算法。算法能够挖掘出用戶感兴趣的、有明显的规则前后部约束的逻辑关系。但算法仅仅是基于单机环境进行优化挖掘的，在面对大规模数据集挖掘时，存在计算开销过大等问题。文献[14]提出的CPFP算法虽然是基于项约束条件的并行化关联规则挖掘，但只侧重于事物集的压缩和FP-tree的剪枝，在后续挖掘频繁项集过程中缺乏对用户需求的针对性，从而仍会产生较多的冗余频繁项集和无关规则。

针对项约束关联规则并行化研究这一现状，本文提出了一种基于Map/reduce并行编程模型的前后部项约束关联规则并行化算法 FRPFP（Fore-part and Rear-part Parallel FP-Growth，简称FRPFP）。该算法能够基于规则前部和规则后部项约束，压缩候选项集空间，并进行分组筛选频繁项集，从而有效减少冗余规则的产生。

1 前后部项约束关联规则相关理论

由confidence （X→Y）=sup_count （X ∪Y）/sup_count（X）可知，若要求取前后部项约束关联规则X→Y，则必需知道（X ∪Y）和X这两种频繁项集的支持度，而X为规则前部，Y为规则后部，则（X ∪Y）表示同时具有规则前部和后部项的频繁项集，故定义前后部项集IFRt及对应的前后部频繁项集LFRt。而（X）表示只具有前部项的频繁项集，故定义前部项集FSj及对应的前部频繁项集LFj。因此，FRPFP算法的思想在于：通过挖掘出所有的前后部频繁项集LFRt和前部频繁项集LFj，来达到求取符合项约束条件的关联规则以及减少冗余规则数量的目的。整个算法核心是围绕如何挖掘出所有的LFRt和LFj来进行求解的。

2 FRPFP算法思想

2.1 算法流程

FRPFP算法流程分为四个步骤，通过二个Map/Reduce操作来完成，如图1所示。为更直观形象地理解本算法，本文以包含8个事务的事务集D作为案例，如图2（a）所示，假定用户感兴趣的规则前部集合F={I2，I5}，规则后部集合R={I1，I3}，minsup=0.25。

步骤1 计算频繁1-项集。通过一次Map/Reduce来完成。计算频繁1-项集采用Map/Reduce里的词频统计思想，频繁1-项集的结果采用表MFR-list来描述。MFR-list四个要素：项名、支持度计数、标签和指针。首先统计各项sup_count，筛选掉小于minsup值的项，将剩余项按照sup_count从大到小排序;接着根据用户兴趣对项加上标签，如果该项属于前部项集合，则标记为f，如果该项属于后部项集合，则标记为r;最后为各项加入指针，使得MFR-list具有项头表的功能，用于链接后续构建的FP-tree上的节点。

对事务集D完成步骤1后，生成的MFR-list如图2（b）所示。MFR-list的第一列的项按照sup_count由大到小排序，第二列为项的sup_count值，第三列为存放前后部项的标签信息，第四列的值暂为空指针。

步骤2 分组建立FP-tree。此操作通过一次Map/Reduce来完成。在Map阶段，首先对事务集D中的每条事务T按照项的sup_count降序重新排列。其次，构建分组列表G-list，并按照G-list对每条事务进行分组和筛选，压缩分组事务集的空间，具体方法见2.2.1节。在Reduce阶段，对压缩后的分组事务集构建分组FP-tree。

步骤3 挖掘LFR和LF。在步骤2建立的各分组FP-tree上，挖掘出所有前后部频繁项集和前部频繁项集，并分别放入集合LFR和LF中。具体方法见2.2.2节。

步骤4 输出关联规则。将各组挖掘结果归并至同一计算节点，遍历LFR，针对每个LFRt若存在对应的前部频繁项集LFj，则计算每個前后部频繁项集的置信度，若其置信度大于等于minconf，则输出强关联规则。若不存在对应的前部频繁项集LFj，则不考虑。

2.2 算法具体描述

2.2.1 分组建立FP-tree

分组建立FP-tree通过一次Map/Reduce来完成。本节重点阐述Map阶段对事务集D进行分组并压缩分组事务空间的方法。

⑴ 事务排序

根据MFR-list，对有标签的项构建分组列表G-list，对每条事务T按照MFR-list中项的sup_count值降序排列，并根据结论1删除未作标签项，如图3（a）中的项I4。对事务集D按照MFR-list （图3（a）），得到降序排列后的事务集合，如图3（b）第三列。

⑵ 筛选分组

按照分组列表G-list对事务集合进行分组，并根据结论2，去掉只标记有r项的分组事务。而只标记有f项的分组事务，由于会生成前部频繁项集，故保留。以事务集D为例，按照图3（a）的分组列表G-list对事务集合进行分组，如图3（b）第四列。对已分组的事务1→{I1，I3}和3→{I1}，由于只包含后部项，故删除此两条事务。

具体伪代码如下：

Mapper阶段：

1.Sort-D （D， MFR-list） { //删除事务中冗余项，并对事务排序

2. foreach T in D do

3. foreach item in T do

4. if （item.support

5. then 从T中删除item

6. Sortby（item.sup_count）.descend按照sup_count

对T中的项降序排列

7. Output Dsorted //输出排序后的事务集合Dsorted

}

8.Partition-D（Dsorted，G-list） {//按照G-list分组，并删除冗余事务

9. D_P←partition（Dsorted，G-list） //按照G-list分组

10. foreach Di in D_P do

11. foreach T in Di do

12. if item∈T，且item标记为r

13. then 删除T

}

在Reduce阶段，将筛选后的分组事务按照相同的Group-id归并至同一个Reducer中，并建立分组FP-tree。以事务集D为例，1号、2号和3号分组的事务集合如图3（b）第五列所示。基于Group1的事务集合构建的分组FP-tree如图4所示。需要指出的是，为了便于搜索分组FP-tree，以MFR-list作为项头表，使分组中的前部项和后部项通过指针指向它在分组FP-tree中的位置。如图4所示，I5，I3是Group1中的项，且I5为前部项（标记为f），I3为后部项（标记为r），故分别通过指针指向I5和I3在1号分组FP-tree中的位置。

2.2.2 挖掘LFR和LF

在Reducer中，通过扫描分组FP-tree进行挖掘，得到包含前后部频繁项集的集合LFR和前部频繁项集集合LF。具体挖掘方法分为二步：①发现分枝;②在分枝上挖掘LFR和LF。

⑴ 发现分枝

针对每个分组建立的FP-tree，挖掘标记为f或r的本分组项。如图4所示，以事务集合D的Group1建立的FP-tree为例，I5和I3属于Group1，且标记分别为f和r。I5在Group1的FP-tree上有两个分支：null→I2：1→I5：1和null→I2：2→I1：2→I3：2→I5：2。I3在Group1的FP-tree上有两个分支：null→I2：4→I1：4→I3：4，和null→I2：1→I3：1。

⑵ 在分枝上挖掘LFR和LF

根据经典FP-growth算法挖掘频繁项集的思想：以待挖掘项为后缀挖掘FP-tree，构造条件模式树，从而生成包含后缀的频繁项集。因此利用生成的频繁项集必定包含后缀项这一特性，在挖掘分组FP-tree分枝时，以本分组包含的项作为后缀，确保生成的IFRt和FSj必定包含本分组项，这样的LFRt和LFj既是局部频繁项集也是全局频繁项集。

遍历每个分枝，根据MFR-list的label中标记的信息，将分枝上的节点项分别放入规则前部项集合F和规则后部项集合R，并分别求出前部项集集合FS和后部项集集合RS。具体分三种情况，若挖掘的是标记为f的本分组项的分枝，则分为以下两种情况。

⑴ 分枝上既有标记为f的节点也有标记为r的节点，则只保留FS中包含本分组项的前部项集FSj，然后与RS中的后部项集RSn两两组合连接，生成前后部项集IFRt并输出，即IFRt=FSj?RSn，同时输出保留的前部项集FSj。

⑵ 分枝上的节点均标记为f，即规则后部集合R为空集，则直接输出FS中包含本分组项的前部项集FSj。

以Group1的FP-tree为例，图5是挖掘标记为f的本分组项I5的分枝。

由图5可知，I5属于Group1的本分组项且被标记为f。选取I5一条分枝null→I2：2→I1：2→I3：2→I5：2，將标记为f的I5，I2放入规则前部集合F，标记为r的I3，I1放入规则后部集合R，并求出前部项集集合FS与后部项集集合RS。由于I5属于Group1的本分组项，故只保留FS中包含I5的前部项集FSj，将筛选后的FSj与RSn两两进行组合连接，输出前后部项集IFRt，同时输出前部项集FSj，输出结果如图中所示。

而I5的另一条枝null→I2：1→I5：1，由于I2，I5均标记为f，则生成的规则后部集合R为空集。同理，由于I5属于Group1的本分组项，故只保留FS中包含I5的前部项集FSj，输出前部项集<{I5}，1>，<{I2，I5}，1>。

若挖掘的是标记为r的本分组项的分枝，只存在一种情况：只保留RS中包含本分组项的后部项集RSn，然后与FS中的前部项集FSj两两组合连接，生成前后部项集IFRt并输出，但不输出前部项集FSj。如图6所示是挖掘标记为r的本分组项I3的分枝。

由图6可知，I3属于1号组的本分组项且被标记为r。选取I3一条分枝null→I2：4→I1：4→I3：4，由于I3出现在规则后部项集合R中，故只保留RS中包含I3的后部项集RSn，然后与前部项集FSj两两组合连接，输出前后部项集IFRt。

最后将本组挖掘出的IFRt、FSj进行合并，如I5的两条枝均有生成{I5}，{I2，I5}，故将其合并。得到候选项集CFRt和CFsj，并根据最小支持度minsup求出前后部频繁项集LFRt和前部频繁项集LFj，并分别放入前后部频繁项集集合LFR和前部频繁项集集合LF中。如图7是Group1所挖掘出的本分组项I5的前后部频繁项集集合LFR和前部频繁项集集合LF。

具体伪代码如下所示。

In Reducer：

1. gen-LFR（FP-tree，MFR-list，G-list[i]，minsup） {

//发现分枝

2. foreach item in G-list[i] { //对每组的分组项

3. if item.link ≠ null then

4. Branchset←find branch（item.link，FP-tree）;

5. foreach branch in Branchset do

6. F←findFore-part（branch， MFR-list）;

7. R←findRear-part（branch， MFR-list）;

8. FS←non-empty-powerset（F）;

9. RS←non-empty-powerset（R）;

//挖掘本分组项标记为f的情况：

10. if item.label= ‘f

11. then保留FS中包含本分组项的前部项集FSj

12. if R≠Φ then //挖掘标记有f和r节点的分枝

13. foreach （FSj∈FS ，RSn∈RS） do

14. IFRt←FSj?RSn//生成前后部项集IFRt

15. else 重复步骤（11） // R≠Φ即挖掘只标记有f

节点的分枝

//挖掘本分组项标记为r的情况

16. if item.label=‘r then//若本分组项被标记为r

17. 保留RS中包含本分组项的后部项集RSn

18. 重复步骤（13）、（14）生成IFRt。

//合并项集生成LFR，LF

19. CFRt，CFj←aggregate（IFRt，FSj）//将相同的IFRt，FSj进行合并

生成候选项集CFRt，CFj

20. foreach CFRt，CFj do //合并同时判断频繁项集

21. if CFRt，CFj ≥ minsup×D then

22. LFRt，LFj←CFRt，CFj //生成频繁项集LFRt，LFj

23. LFR，LF←add LFRt，LFj //将LFRt，LFj添加进LFR，LF

}

24. i++

}

3 实验结果与分析

3.1 算法性能测试及分析

本文提出的FRPFP算法采用Scala编程并在Spark框架下实现。实验环境为：3台CPU主频为3.6GHz，内存为16G的台式机，Ubuntu16.04，Hadoop2.7.2，Spark1.6.1，scala2.10.4，JDK1.7.0_51。实验从不同数据量的运行时间以及生成的关联规则数量两个方面比较FRPFP算法与其他算法的优劣;并从规模增长性方面分析了FRPFP算法本身的性能。采用http：//fimi.ua.ac.be/data/的T40I10D100k数据集作为实验数据集。

3.1.1 FRPFP算法与其他算法对比分析

⑴ 不同数据量运行时间对比

对FRPFP、PFP[6]、FPPM[8]以及CPFP[14]算法进行对比。把数据集分成10组，设置最小支持度minsup为10%，最小置信度minconf为50%。由于FRPFP算法对挖掘的项有约束，因此为减小因项的数目和种类不同导致挖掘的复杂程度不同的影响，每组数据集将所有频繁1-项集随机均分成两组并标记为f或r，构建MFR-list。共进行10次实验，取10次实验结果的平均值作为本组实验的运行时间，结果如图8所示。

从图8中可以看出，FRPFP算法和同属于项约束算法的CPFP相比，计算时间更少，但和侧重于性能提高的FPPM算法相比，所用时间较多。

⑵ 生成关联规则数目结果对比

为了测试FRPFP算法挖掘关联规则的效果，利用实验⑴中的10组测试集得出的关联规则的结果进行对比。由于PFP和FPPM算法均未对挖掘的项有约束条件，故挖掘的是所有关联规则。而CPFP和FRPFP算法均对挖掘的关联规则有约束，故生成的关联规则数量不同。具体结果如表1所示。

結合表1中的实验结果，FRPFP算法生成的关联规则数与PFP、FPPM算法相比，大大减少了冗余规则的产生，与CPFP算法相比，生成的规则数也较少。

3.1.2 FRPFP算法本身的性能

数据量规模增长性测试。规模增长性是指处理节点不变的条件下，扩大数据规模时，并行算法的性能。计算公式为sizeup （D，m）=tm×D /tD，式tm×D中表示对规模为m×D的数据集运行算法所用的时间，tD表示对规模为D的数据集运行算法所用的时间。根据图8中的实验数据，可得FRPFP算法数据量规模增长性曲线如图9所示。

从图9的实验效果可以看出，FRPFP算法具有良好的数据规模增长性。

4 结束语

本文提出的FRPFP算法属于项约束关联规则算法的一种，在挖掘关联规则方面，能够减少大量冗余规则的产生，不仅提高了用户筛选自己感兴趣的关联规则的效率，降低了时间成本，而且算法也具有较好的规模增长性，在计算开销的时间花费上与传统的算法相比也较少，能够较好的适用于大规模数据集的挖掘。

参考文献（References）：

[1] W. Lin， S. A. Alvarez， and C. Ruiz.Efficient Adaptive Support Association Rule Mining for Recommender Systems[J].DataMining and Knowledge Discovery，2002.6（1）：83-105

[2] B. Mobasher， H. Dai， T. Luo， and M. Nakagawa.Effictive

Personalization Based on AssociationRule Discovery from Web Usage Data[C]//ACM CIKM 2001 10th International Conference on Information andKnowledge Management，2001：9-15

[3] 米允龙，姜麟，米春桥.MapReduce环境下的否定粗糙关联规则算法[J].计算机集成制造系统，2014.20（11）：2894-2903

[4] HE B.The algorithm of mining frequent itemsets based on

MapReduce[C]//Proceedings of InternationalConference on Soft Computing Techniques and Engineering Application.Ber-lin， Ger-many：Springer Verlag，2014.15：1827-1831

[5] QIU H，GU R，YUAN C， et al. YAFIM：A parallel frequent

itemset mining algorithm with Spark[C]//2014 IEEE InternationalParallel&Distributed Processing Symposium Workshops.[S.l.]：IEEE，2014：1664-1671

[6] Haoyuan Li，Yi Wang，Dong Zhang，Ming Zhang，Edward Y.

Chang. PFP：Parallel FP-Growth forQuery Recommendation[J].ACM Conference on Recommender Systems，2008.39（5）：107-114

[7] A. Savasere， E. Omiecinski， and S.B. Navathe.An

EfficientAlgorithm for Mining Association Rules in Large Databases[J].Vldb Journal，1995：432-444

[8] 章志刚，吉根林.一种基于FP-growth的频繁项目集并行挖掘算法[J].计算机工程与应用，2014.50（2）：103-106

[9] 陈平，王利刚，李博涵.基于项约束的关联规则挖掘研究综述[J].制造业制动化，2014.36（8）：10-15

[10] 陶再平.基于约束的关联规则挖掘[M].浙江工商大学出版社，2012.

[11] AGRAWAL R，SHAFERJ C. Parallel Mining of Association rules[J].IEEE Transactions on Konwledge and Data Engineering，1996.8（6）：962-969

[12] 孟月昊，王朝霞，郭宇棟.基于规则前后部约束的关联规则挖掘算法[J].后勤工程学院学报，2017.33（1）：79-84

[13] 李赞，王朝霞，孟月昊，隋昊.基于FP-growth的前后部项约束关联规则改进算法[J].舰船电子工程，2018.38（9）：21-26