海量数据下基于Hadoop的分布式FP-Growth算法
|
摘要
针对大数据环境下的关联挖掘问题,采取两次扫描数据库,将事务添加到相互独立的数据分区的方式,对传统FP-Growth算法进行分布式改造,进而提出了基于Hadoop框架的分布式FP-Growth算法以实现海量数据的频繁模式FP挖掘.仿真结果表明,在数据处理量逐渐增大的过程中,该算法相比较传统算法其运行时间和内存消耗的优势愈加明显,当数据处理量达到70万条时,该算法比传统算法节省约2/3的运行时间,而内存消耗仅为传统算法的1/5.说明该算法在处理海量数据时,能够显著提高FP的挖掘效率并降低内存的消耗量.
In view of the large data problem of association mining by the method of taking two times of scanning database and adding the transaction to the independent data partition,distributed renovation of traditional FPGrowth algorithm was taken,the distributed FP-Growth algorithm based on Hadoop framework was then put forward so as to realize the frequent pattern FP huge amounts of data mining. The simulation results showed that in the process of increasing data processing,the algorithm was compared with the traditional algorithm advantages of its running time and memory consumption were becoming ever more obvious. When the amount of data processing reached 700,000 items,the algorithm saved about 2/3 running time than the traditional algorithm,while the memory consumption was only 1/5 of the traditional algorithm. It showed that the algorithm could significantly improve the mining efficiency of FP and reduced the memory consumption when dealing with massive data.
In view of the large data problem of association mining by the method of taking two times of scanning database and adding the transaction to the independent data partition,distributed renovation of traditional FPGrowth algorithm was taken,the distributed FP-Growth algorithm based on Hadoop framework was then put forward so as to realize the frequent pattern FP huge amounts of data mining. The simulation results showed that in the process of increasing data processing,the algorithm was compared with the traditional algorithm advantages of its running time and memory consumption were becoming ever more obvious. When the amount of data processing reached 700,000 items,the algorithm saved about 2/3 running time than the traditional algorithm,while the memory consumption was only 1/5 of the traditional algorithm. It showed that the algorithm could significantly improve the mining efficiency of FP and reduced the memory consumption when dealing with massive data.
引文
[1]刘智勇.关联规则挖掘的并行化算法研究[D].南京:东南大学,2016.
[2]董金凤.数据挖掘中关联规则算法的改进与并行化处理[D].哈尔滨:哈尔滨理工大学,2016.
[3]孙兵率.基于MapReduce的数据挖掘算法并行化研究与应用[D].西安:西安工程大学,2015.
[4] HAN J W,PEI J,YIN Y W. Mining frequent patterns without candidate generation[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data,New York:ACM,2000:1.
[5]黄明.基于空间分区的空间聚类研究[D].武汉:武汉大学,2010.
[6]邱勇,兰永杰.高效FP-TREE创建算法[J].计算机科学,2004(10):98.
[7]赵兰草. QAR数据的异常检测与分析算法研究[D].天津:中国民航大学,2014.
[8]茹蓓,贺新征.高效的数据流完全频繁项集挖掘算法[J].计算机工程与设计,2017,38(10):2759.
[9]王翔.基于云计算棉花仓储海量数据挖掘算法研究[D].北京:首都师范大学,2014.
[10]周诗慧.基于Hadoop的改进的并行FpGrowth算法[D].济南:山东大学,2013.
[11]邵伟.基于FP-Tree的关联规则挖掘算法研究[D].西安:西安电子科技大学,2010.
[12]朱付保,白庆春,汤萌萌,等.基于MapReduce的数据流频繁项集挖掘算法[J].华中师范大学学报(自然科学版),2017,51(4):429.
[13]白川平,杨志翀.基于加权滑动窗口的数据流频繁项集挖掘算法[J].宁夏师范学院学报,2017,38(6):49.
[14]胡健,吴毛毛.一种改进的数据流最大频繁项集挖掘算法[J].计算机工程与科学,2014,36(5):963.
[15]刘慧婷,候明利,赵鹏,等.不确定数据流最大频繁项集挖掘算法研究[J].计算机工程与应用,2016,52(19):72.
[2]董金凤.数据挖掘中关联规则算法的改进与并行化处理[D].哈尔滨:哈尔滨理工大学,2016.
[3]孙兵率.基于MapReduce的数据挖掘算法并行化研究与应用[D].西安:西安工程大学,2015.
[4] HAN J W,PEI J,YIN Y W. Mining frequent patterns without candidate generation[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data,New York:ACM,2000:1.
[5]黄明.基于空间分区的空间聚类研究[D].武汉:武汉大学,2010.
[6]邱勇,兰永杰.高效FP-TREE创建算法[J].计算机科学,2004(10):98.
[7]赵兰草. QAR数据的异常检测与分析算法研究[D].天津:中国民航大学,2014.
[8]茹蓓,贺新征.高效的数据流完全频繁项集挖掘算法[J].计算机工程与设计,2017,38(10):2759.
[9]王翔.基于云计算棉花仓储海量数据挖掘算法研究[D].北京:首都师范大学,2014.
[10]周诗慧.基于Hadoop的改进的并行FpGrowth算法[D].济南:山东大学,2013.
[11]邵伟.基于FP-Tree的关联规则挖掘算法研究[D].西安:西安电子科技大学,2010.
[12]朱付保,白庆春,汤萌萌,等.基于MapReduce的数据流频繁项集挖掘算法[J].华中师范大学学报(自然科学版),2017,51(4):429.
[13]白川平,杨志翀.基于加权滑动窗口的数据流频繁项集挖掘算法[J].宁夏师范学院学报,2017,38(6):49.
[14]胡健,吴毛毛.一种改进的数据流最大频繁项集挖掘算法[J].计算机工程与科学,2014,36(5):963.
[15]刘慧婷,候明利,赵鹏,等.不确定数据流最大频繁项集挖掘算法研究[J].计算机工程与应用,2016,52(19):72.