基于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]. 计算机工程, 2020, 46(8): 27-34.
[2]	郭威, 谢光伟, 张帆, 李敏. 一种分布式存储系统拟态化架构设计与实现[J]. 计算机工程, 2020, 46(6): 12-19.
[3]	王斌, 房新秀, 魏天佑. 基于差异节点集的加权频繁项集挖掘算法[J]. 计算机工程, 2020, 46(5): 150-156.
[4]	王芝辉, 王晓东. 基于神经网络的文本分类方法研究[J]. 计算机工程, 2020, 46(3): 11-17.
[5]	张海军, 陈映辉. 基于类图像处理与向量化的大数据脚本攻击智能检测[J]. 计算机工程, 2020, 46(3): 129-137,143.
[6]	王玉奇, 高建华. 一种基于关联规则的Web应用统计测试方法[J]. 计算机工程, 2020, 46(3): 206-213.
[7]	李洁, 朱洪亮, 陈玉玲, 辛阳. 基于哈希存储与事务加权的并行Apriori改进算法[J]. 计算机工程, 2020, 46(11): 109-116.
[8]	王重仁, 王雯, 佘杰, 凌晨. 融合深度神经网络的个人信用评估方法[J]. 计算机工程, 2020, 46(10): 308-314.
[9]	王豫新, 高美凤. 一种改进的固件增量更新算法[J]. 计算机工程, 2020, 46(10): 210-215.
[10]	张继炎, 郑汉垣. 云环境下基于预算分配的科学工作流调度研究[J]. 计算机工程, 2019, 45(9): 40-48.
[11]	白玲玲, 宁振虎, 薛菲, 杨永丽. 隐马尔可夫模型在恶意域名检测中的应用[J]. 计算机工程, 2019, 45(9): 161-168.
[12]	徐云涛, 许武军, 翟梦琳. 基于B/S架构的高并发虹膜识别系统[J]. 计算机工程, 2019, 45(8): 102-106,112.
[13]	张玺君, 袁占亭, 张红, 高玮军, 张恩展. 交通轨迹大数据预处理方法研究[J]. 计算机工程, 2019, 45(6): 26-31.
[14]	钱雪忠,姚琳燕. 面向稀疏高维大数据的扩展增量模糊聚类算法[J]. 计算机工程, 2019, 45(6): 75-81.
[15]	向程冠,熊世桓,王东,熊伟程. 基于关联规则与相似度的社交好友推荐算法[J]. 计算机工程, 2019, 45(4): 175-180.