基于MapReduce的并行关联规则增量更新算法

doi:10.3969/j.issn.1000-3428.2016.02.004

摘要/Abstract

摘要： 为解决传统关联规则挖掘算法在大数据环境下运行效率较低的问题,基于频繁模式增长(FP-growth)算法,提出一种面向大数据的并行关联规则增量更新算法。利用MapReduce编程模型与云计算平台,对FP-growth算法各步骤进行并行化处理。在增量更新挖掘过程中,使用已有的频繁项集和1-项集对新增事务集构建频繁模式树,通过扫描原始事务数据库完成频繁项集的更新。实验结果表明,与传统关联规则挖掘算法相比,该算法具有更高的挖掘效率和扩展性,适用于海量数据的关联规则增量挖掘。

关键词: 大数据, 云计算, MapReduce编程模型, 频繁项集, 增量更新, 关联规则

Abstract: Under the environment of big data,the traditional association rule mining algorithms have lower efficiency caused by the rapidly increasing data.Aiming at the problem,this paper proposes a parallel incremental updating algorithm of association rules based on the Frequent Pattern Growth(FP-growth) algorithm.Each step of incremental FP-growth algorithm is realized to parallel process by using the MapReduce programming model and cloud computing platform.In the updating process,it uses the existing incremental of frequent itemsets and 1-set to construct frequent pattern tree of the new transaction after completing frequent itemsets updating by scanning the original transaction database one time.Experimental results show that the algorithm has better efficiency and expansibility compared with the traditional association rule mining algorithm,therefore it can be applied to the association rules incremental mining of massive data.

Key words: big data, cloud computing, MapReduce programming model, frequent itemset, incremental updating, association rule

中图分类号:

TP311

程广,王晓峰. 基于MapReduce的并行关联规则增量更新算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.02.004.

CHENG Guang,WANG Xiaofeng. Incremental Updating Algorithm of Parallel Association Rule Based on MapReduce[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.02.004.

参考文献

参考文献［1］Agrawal R,Imielinski T,Swami A.Mining Association Rules Between Sets of Items in Large Database［C］//Proceedings of 1993 ACM-SIGMOD International Con-ference on Management of Date.New York,USA:ACM Press,1993:206-216. ［2］Han Jiawei,Pei Jian,Yin Yiwen.Mining Frequent Patterns Without Candidate Generation［C］//Proceed-ings of 2000 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2000:1-12. ［3］Cheung D W.Maintenance of Discovered Association Rules in Large Database:An Incremental Updating Approach［C］//Proceedings of the 12th IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,1996:106-114. (下转第32页) (上接第25页) ［4］Ayan N F,Tansel A U,Arkun E.An Efficient Algorithm to Update Large Itemsets with Early Pruning［C］//Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,1999:287- 291. ［5］Hong T P.A Fast Updated Frequent Pattern Tree［C］//Proceedings of IEEE International Conference on Systems,Man,and Cybernetics.Washington D.C.,USA:IEEE Press,2006:2167-2172. ［6］Lin Chunwei,Hong T P.Using the Pre-FUFP Algorithm for Handling New Transactions in Incremental Ming［C］//Proceedings of CIDM’07.Washington D.C.,USA:IEEE Press,2007:598-603. ［7］孟小峰,慈祥.大数据管理:概念、技术与挑战［J］.计算机研究与发展,2013,50(1):146-169. ［8］Yang Xinyue,Liu Zhen,Fu Yan.MapReduce as Programming Model for Association Rules Algorithm on Hadoop［C］//Proceedings of the 3rd International Conference on Information Sciences and Interaction Sciences.Washington D.C.,USA:IEEE Press,2010:99-102. ［9］Li Haoyuan,Wang Yi,Zhang Dong,et al.PFP:Parallel FPGrowth for Query Recommendation［C］//Proceed-ings of 2008 ACM Conference on Recommended Systems.New York,USA:ACM Press,2008:125-137. ［10］朱晓峰,李玲娟,徐小龙,等.基于MapReduce的关联规则增量更新算法［J］.计算机技术与发展,2012,22(4):115-118. ［11］李春喜,赵雷.一种改进的增量挖掘算法［J］.计算机工程,2010,36(24):42-44. ［12］邹海,朱四红.基于HFUFP-tree的增量挖掘算法研究［J］.计算机应用与软件,2011,28(9):102-105. ［13］Jeffrey D,Sanjay G.MapReduce:Simplified Date Processing on Large Clusters［J］.Communications of the ACM,2008,51(1):107-113. ［14］Frequent Itemset Mining Dataset Repository［EB/OL］.［2015-02-07］.http://fimi.ua.ac.be/data/. 编辑陆燕菲

[1]	张继炎, 郑汉垣. 云环境下基于预算分配的科学工作流调度研究[J]. 计算机工程, 2019, 45(9): 40-48.
[2]	白玲玲, 宁振虎, 薛菲, 杨永丽. 隐马尔可夫模型在恶意域名检测中的应用[J]. 计算机工程, 2019, 45(9): 161-168.
[3]	徐云涛, 许武军, 翟梦琳. 基于B/S架构的高并发虹膜识别系统[J]. 计算机工程, 2019, 45(8): 102-106,112.
[4]	张玺君, 袁占亭, 张红, 高玮军, 张恩展. 交通轨迹大数据预处理方法研究[J]. 计算机工程, 2019, 45(6): 26-31.
[5]	钱雪忠,姚琳燕. 面向稀疏高维大数据的扩展增量模糊聚类算法[J]. 计算机工程, 2019, 45(6): 75-81.
[6]	向程冠,熊世桓,王东,熊伟程. 基于关联规则与相似度的社交好友推荐算法[J]. 计算机工程, 2019, 45(4): 175-180.
[7]	陈娇娇,朱卫平,屠明暄,唐熠杰,孙泽宇. 大型商场中移动群组识别与位置预测方法[J]. 计算机工程, 2019, 45(3): 78-84.
[8]	刘彪,王宝生,邓文平. 云环境下支持弹性伸缩的容器化工作流框架[J]. 计算机工程, 2019, 45(3): 7-13.
[9]	蒋猛,禹明刚,王智学. 多策略自适应大规模本体映射算法[J]. 计算机工程, 2019, 45(3): 14-19.
[10]	张伟,王志杰. 分布式环境下时态大数据的连接操作研究[J]. 计算机工程, 2019, 45(3): 20-25,31.
[11]	吴睿雪, 彭长根, 刘波涛, 丁红发, 谢明明. 基于关联规则的多敏感属性匿名算法[J]. 计算机工程, 2019, 45(11): 126-132.
[12]	李建鹏, 史国振, 李莉, 孙德洋, 郑戈威. 异构云环境中的实时密码服务调度策略[J]. 计算机工程, 2019, 45(10): 1-7.
[13]	朱敏惠,陈燕俐,胡媛媛 . 支持代理重加密的基于身份可搜索加密方案[J]. 计算机工程, 2019, 45(1): 129-135,140.
[14]	刘雨潇,王毅,袁磊,吴钊. 基于期限约束与关键路径的云工作流调度[J]. 计算机工程, 2018, 44(8): 30-37.
[15]	谢彬,张琨,蔡颖,蒋彤彤,麻孟越. 移动目标关联共现规则挖掘算法研究[J]. 计算机工程, 2018, 44(8): 61-67,73.