基于Hadoop平台的改进关联规则挖掘算法

doi:10.3969/j.issn.1000-3428.2016.10.012

摘要/Abstract

摘要： 数据采集方式的增多导致单处理器下的关联规则挖掘受到I/O和内存的限制。针对该问题,对传统挖掘算法进行改进。借助Hadoop平台的优势,通过累加迭代的方法降低算法的时间复杂度,并利用MapReduce编程特点,通过一次遍历和MapReduce任务调度完成频繁项集挖掘,在强关联挖掘中通过Sqoop组件将外部表Hive中的数据迁移到Redis,实现数据的高速读取。实验结果表明,该方法可有效提高挖掘效率,提高幅度随数据集规模同步增大,并且具有较好的加速比和扩展性。

关键词: Hadoop平台, MapReduce编程, 关联规则, 大数据, 数据挖掘

Abstract: Development of ways for data acquisition leads to limit of traditional association rule mining by I/O and memory.Aiming at this problem,this paper puts forward an improved method,which uses advantages of the Hadoop platform,reduces the time complexity of the algorithm by incremental iterative method,and makes full use of the features of MapReduce programming.It completes the frequent itemset mining through traverse and MapReduce task scheduling,which improves the efficiency of processing.In the mining of strong association,with the help of Sqoop,the external tables are migrated from Hive to Redis,which makes the data read more efficient.Experimental results show that the proposed method can improve processing efficiency.With the data increasing,the advance becomes more obvious,and improved algorithm also has better speedup and scalability,which is able to quickly mine the association rules in large data.

Key words: Hadoop platform, MapReduce programming, association rule, big data, data mining

中图分类号:

TP338.6

王英博,马菁,柴佳佳,赵彬. 基于Hadoop平台的改进关联规则挖掘算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.10.012.

WANG Yingbo,MA Jing,CHAI Jiajia,ZHAO Bin. Improved Association Rule Mining Algorithm Based on Hadoop Platform[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.10.012.

参考文献

参考文献［1］Han Jiawei,Pei Jian,Yin Yiwen.Mining Frequent Patterns Without Candidate Generation［C］//Proceed-ings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2000:1-12. ［2］Agrawal R,Imielinki T,Swami A.Mining Association Rules Between Sets of Items in Large Database［C］//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,1993:207-216. ［3］Borthakur D,Gray J,Sarma J S,et al.Aiyer:Apache Hadoop Goes Realtime at Facebook［C］//Proceedings of the 38th ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2011:1071-1080. ［4］王智钢,王池社,马青霞.分布式并行关联规则挖掘算法研究［J］.计算机应用与软件,2013,30(10):113-119. ［5］Nguyen D,Vo B,Le B.Efficient Strategies for Parallel Mining Class Association Rules［J］.Expert Systems with Applications,2014,41(10):4716-4729. ［6］陆嘉恒.Hadoop实践［M］.北京:机械工业出版社,2012. ［7］Lu Bingliang,Wei Shuchao.One More Efficient Parallel Initialization Algorithm of K-means with MapReduce［C］//Proceedings of the 4th International Conference on Computer Engineering and Networks.Berlin,Germany:Springer,2014:845-852. ［8］Mukhopadhyay D,Agrawal C,Maru D,et al.Addressing Name Node Scalability Issue in Hadoop Distributed File System Using Cache Approach［C］//Proceedings of 2014 International Conference on Information Technology.Washington D.C.,USA:IEEE Press,2014:321-326. ［9］Yang Xinyue,Zhen Liu,Fu Yan.MapReduce as a 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. (下转第79页) (上接第74页) ［10］杨勇,高松松.基于MapReduce的关联规则并行增量更新算法［J］.重庆邮电大学学报:自然科学版,2014,26(5):670-678. ［11］马盈.基于MapReduce构造多维数据及关联规则挖掘算法的研究与应用［D］.长春:东北师范大学,2013. ［12］Thusoo A,Sarma J S,Jain N,et al.Hive:A Petabyte Scale Data Warehouse Using Hadoop［C］//Proceedings of the 26th International Conference on Data Engineer-ing.Washington D.C.,USA:IEEE Press,2010:996-1005. ［13］Ji Zhanlin,Ganchev I,O’Droma M,et al.A Distributed Redis Framework for Use in the UCWW［C］//Proceed-ings of 2014 International Conference on Cyber-enabled Distributed Computing and Knowledge Discovery.Washington D.C.,USA:IEEE Press,2014:241-244. ［14］Chen Changai,Jiang Shan.Research of the Big Data Platform and the Traditional Data Acquisition and Transmission Based on Sqoop Technology［J］.The Open Automation and Control Systems Journal,2015,15(7):1174-1180. ［15］范飞,黄文明,邓珍荣.Oozie工作流在Mahout分布式数据挖掘中的应用［J］.桂林电子科技大学学报,2014,34(1):25-29. ［16］Wasi-ur-Rahman M,Huang Jian,Jose J,et al.Under-standing the Communication Characteristics in HBase:What Are the Fundamental Bottlenecks?［C］//Pro-ceedings of 2012 IEEE International Symposium on Performance Analysis of Systems and Software.Washington D.C.,USA:IEEE Press,2012:122-123. ［17］Lee C,Zheng Y.Automatic SQL-to-NoSQL Schema Transformation over the MySQL and HBase Data-bases［C］//Proceedings of 2015 IEEE International Con-ference on Consumer Electronics.Washington D.C.,USA:IEEE Press,2015:426-427. 编辑金胡考

[1]	魏文浩, 唐泽坤, 刘刚. 基于距离和密度的PBK-means算法[J]. 计算机工程, 2020, 46(9): 68-75.
[2]	郭威, 谢光伟, 张帆, 李敏. 一种分布式存储系统拟态化架构设计与实现[J]. 计算机工程, 2020, 46(6): 12-19.
[3]	史明阳, 王鹏, 汪卫. 有监督时间序列分割与状态识别算法[J]. 计算机工程, 2020, 46(5): 131-138.
[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): 67-73.
[10]	白玲玲, 宁振虎, 薛菲, 杨永丽. 隐马尔可夫模型在恶意域名检测中的应用[J]. 计算机工程, 2019, 45(9): 161-168.
[11]	王慧健, 刘峥, 李云, 李涛. 基于神经网络语言模型的时间序列趋势预测方法[J]. 计算机工程, 2019, 45(7): 13-19,25.
[12]	张玺君, 袁占亭, 张红, 高玮军, 张恩展. 交通轨迹大数据预处理方法研究[J]. 计算机工程, 2019, 45(6): 26-31.
[13]	钱雪忠,姚琳燕. 面向稀疏高维大数据的扩展增量模糊聚类算法[J]. 计算机工程, 2019, 45(6): 75-81.
[14]	向程冠,熊世桓,王东,熊伟程. 基于关联规则与相似度的社交好友推荐算法[J]. 计算机工程, 2019, 45(4): 175-180.
[15]	陈娇娇,朱卫平,屠明暄,唐熠杰,孙泽宇. 大型商场中移动群组识别与位置预测方法[J]. 计算机工程, 2019, 45(3): 78-84.