孟月昊 冯文 林荣霞 陈铭师

摘  要： 为了解决大规模数据环境下挖掘出的关联规则过多，用户需要耗费大量时间在这些关联规则中寻找自己感兴趣规则的问题，提出了一种基于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等提高其销售策略。在这里，“气候/时间”是用户感兴趣的规则前部，“货物”是用户感兴趣的规则后部。但是传统的关联规则挖掘算法在面向大规模数据挖掘时存在一些不足之处，如挖掘出的冗余规则过多，用户需耗费大量时间对挖掘出的关联规则进行二次筛选来寻找自己感兴趣的部分。因此，迫切需要一种有效的并行化关联规则算法来提高挖掘用户感兴趣规则的效率。……