Optimization and implementation of parallel FP-Growth algorithm based on Spark

doi:10.11772/j.issn.1001-9081.2018041219

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (11): 3069-3074.DOI: 10.11772/j.issn.1001-9081.2018041219

Previous Articles Next Articles

Optimization and implementation of parallel FP-Growth algorithm based on Spark

GU Junhua^1,2, WU Junyan², XU Xinyun², XIE Zhijian², ZHANG Suqi³

1. School of Artificial Intelligence and Data Science, Hebei University of Technology, Tianjin 300401, China;
2. Hebei Province Key Laboratory of Big Data Computing(Hebei University of Technology), Tianjin 300401, China;
3. School of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China

Received:2018-04-30 Revised:2018-05-31 Online:2018-11-10 Published:2018-11-10
Supported by:
This work is partially supported by the Science-Technology Program of Hebei Province (17210305D), the Science-Technology Program of Tianjin (16ZXHLSF0023), the Natural Science Foundation of Tianjin (15JCQNJC00600), the Science-Technology Program of Tianjin (15ZXHLGX00130)

基于Spark的并行FP-Growth算法优化及实现

顾军华^1,2, 武君艳², 许馨匀², 谢志坚², 张素琪³

1. 河北工业大学人工智能与数据科学学院, 天津 300401;
2. 河北省大数据计算重点实验室(河北工业大学), 天津 300401;
3. 天津商业大学信息工程学院, 天津 300134

通讯作者: 张素琪
作者简介:顾军华(1966-),男,河北石家庄人,教授,博士,CCF会员,主要研究方向:数据挖掘、智能信息处理、信息采集与集成、智能计算与优化、功能与信息展示、软件工程、项目管理;武君艳(1994-),女,山西晋中人,硕士研究生,主要研究方向:数据挖掘、计算机仿真、机器学习;许馨匀(1995-),女,河北石家庄人,硕士研究生,主要研究方向:情感分析、自然语言处理、深度学习;谢志坚(1995-),男,河北沧州人,硕士研究生,主要研究方向:机器学习、数据挖掘;张素琪(1980-),女,河北邢台人,讲师,博士,CCF会员,主要研究方向:机器学习、数据挖掘。
基金资助:
河北省科技计划项目（17210305D）；天津市科技计划项目（16ZXHLSF0023）；天津市自然科学基金资助项目（15JCQNJC00600）；天津市科技计划项目（15ZXHLGX00130）。

Abstract

Abstract: In order to further improve the execution efficiency of Frequent Pattern-Growth (FP-Growth) algorithm on Spark platform, a new parallel FP-Growth algorithm based on Spark, named BFPG (Better Frequent Pattern-Growth), was presented. Firstly, the grouping strategy F-List was improved in the size of the Frequent Pattern-Tree (FP-Tree) and the amount of partition calculation to ensure that the load sum of each partition was approximately equal. Secondly, the data set partitioning strategy was optimized by creating a list P-List, and then the time complexity was reduced by reducing the traversal times. The experimental results show that the BFPG algorithm improves the mining efficiency of the parallel FP-Growth algorithm, and the algorithm has good scalability.

Key words: big data platform, association rule, frequent itemset, Frequent Pattern-Growth (FP-Growth) algorithm, Spark

摘要： 为了进一步提高在Spark平台上的频繁模式增长（FP-Growth）算法执行效率，提出一种新的基于Spark的并行FP-Growth算法——BFPG。首先，从频繁模式树（FP-Tree）规模大小和分区计算量对F-List分组策略进行改进，保证每个分区负载总和近似相等；然后，通过创建列表P-List对数据集划分策略进行优化，减少遍历次数，降低时间复杂度。实验结果表明，BFPG算法提高了并行FP-Growth算法挖掘效率，且算法具有良好的扩展性。

关键词: 大数据平台, 关联规则, 频繁项集, 频繁模式增长算法, Spark

CLC Number:

TP181

GU Junhua, WU Junyan, XU Xinyun, XIE Zhijian, ZHANG Suqi. Optimization and implementation of parallel FP-Growth algorithm based on Spark[J]. Journal of Computer Applications, 2018, 38(11): 3069-3074.

顾军华, 武君艳, 许馨匀, 谢志坚, 张素琪. 基于Spark的并行FP-Growth算法优化及实现[J]. 计算机应用, 2018, 38(11): 3069-3074.

References

[1] 张素琪,梁志刚,胡利娟,等.改进的多维关联规则算法研究及应用[J].计算机工程与科学,2012,34(9):174-179.(ZHANG S Q, LIANG Z G, HU L J, et al. Research and application of improved multi-dimensional association rule algorithm[J]. Computer Engineering and Science, 2012, 34(9):174-179.)
[2] HAN J, PEI J, YIN Y. Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2000:1-12.
[3] ESSALMI H, FAR M E, MOHAJIR M E, et al. A novel approach for mining frequent itemsets:AprioriMin[C]//Proceedings of the 20164th IEEE International Colloquium on Information Science and Technology. Piscataway, NJ:IEEE, 2017:286-289.
[4] 崔妍,包志强.关联规则挖掘综述[J]. 计算机应用研究,2016,33(2):331-334.(CUI Y, BAO Z Q. Association rule mining overview[J]. Application Research of Computers, 2016, 33(2):331-334.)
[5] 马强,杨金民. 基于MapReduce的频繁项集并行挖掘算法[J]. 计算机应用与软件,2015, 33(9):13-17. (MA Q, YANG J M. Parallel mining algorithm of frequent item set based on MapReduce[J]. Computer Applications and Software, 2015,33(9):13-17.)
[6] LI H, WANG Y, ZHANG D, et al. PFP:parallel FP-growth for query recommendation[C]//Proceedings of the 2008 ACM Conference on Recommender Systems. New York:ACM,2008:107-114.
[7] 朱文飞,齐建东,洪剑珂. Hadoop下负载均衡的频繁项集挖掘算法研究[J].计算机应用与软件,2016,33(5):36-39.(ZHU W F, QI J D, HONG J K. research on load balanced frequent itemsets mining algorithm based on Hadoop[J]. Computer Applications and Software, 2016, 33(5):36-39.)
[8] 章志刚,吉根林.一种基于FP-Growth的频繁项目集并行挖掘算法[J].计算机工程与应用,2014,50(2):103-106. (ZHANG Z G, JI G L. Parallel algorithm for mining frequent item sets based on FP-Growth[J]. Journal of Computer Engineering and Application, 2014,50(2):103-106.)
[9] ZAHNG F,LIU M, GUI F, et al. A distributed frequent itemset mining algorithm using Spark for big data analytics[J]. Cluster Computing, 2015,18(4):1493-1501.
[10] DENG L L, LOU Y, et al. Improvement and research of FP-Growth algorithm based on distributed spark[C]//Proceedings of the 2015 International Conference on Cloud Computing and Big Data. Piscataway, NJ:IEEE, 2015:105-108.
[11] 方向,张功萱.基于Spark的PFP-Growth并行算法优化实现[J].现代电子技术,2016,39(8):9-13. (FANG X, ZHANG G X. PFR-Growth parallel algorithm optimization based on Spark[J]. Modern Electronics Technique, 2016, 39(8):9-13.)
[12] LI C, HUANG X. Research on FP-Growth algorithm for massive telecommunication network alarm data based on Spark[C]//Proceedings of the 2016 IEEE International Conference on Software Engineering and Service Science. Piscataway, NJ:IEEE, 2017:875-879.
[13] 张稳,罗可.一种基于Spark框架的并行FP-Growth挖掘算法[J].计算机工程与科学, 2017,33(8):1403-1409. (ZHANG W, LUO K. A parallel FP-Growth mining algorithm based on spark framework[J]. Computer Engineering and Science, 2017,33(8):1403-1409.)
[14] 陆可,江雨燕, 杜萍萍,等.基于Spark的并行FP-Growth算法优化与实现[J]. 计算机应用与软件,2017,34(9):273-277.(LU K, JIANG Y Y, DU P P, et al. Parallel FP-Growth algorithm optimization and implementation based on Spark[J]. Computer Applications and Software, 2017,34(9):273-277.)
[15] ZHOU L, WANG X. Research of the FP-Growth algorithm based on cloud environments[J]. Journal of Software, 2014, 9(3):676-682.
[16] 高权,万晓东.基于负载均衡的并行FP-Growth算法[J].计算机工程,2018,39(6):37-72. (GAO Q, WAN X D. Load-balanced parallel FP-Growth algorithm[J]. Computer Engineering, 2018, 39(6):37-72.)
[17] Frequent itemset mining dataset repository[EB/OL].[2012-10-21].http://fimi.ua.ac.be/data/.

Optimization and implementation of parallel FP-Growth algorithm based on Spark

基于Spark的并行FP-Growth算法优化及实现

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LIU Bin, HE Jinrong, LI Yuancheng, HAN Hong. Apple price prediction method based on distributed neural network [J]. Journal of Computer Applications, 2020, 40(2): 369-374.
[2]	GU Junhua, WANG Feng, QI Yongjun, SUN Zheran, TIAN Zepei, ZHANG Yajuan. Retrieval method of pulmonary nodule images based on multi-scale convolution feature fusion [J]. Journal of Computer Applications, 2020, 40(2): 561-565.
[3]	ZHANG Xiajie, ZHU Jinghua, CHEN Yang. Distributed rough set attribute reduction algorithm under Spark [J]. Journal of Computer Applications, 2020, 40(2): 518-523.
[4]	CHENG Wenliang, WANG Zhihong, ZHOU Yu, GUO Yi, ZHAO Junfeng. Design of distributed computing framework for foreign exchange market monitoring [J]. Journal of Computer Applications, 2020, 40(1): 173-180.
[5]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[6]	WANG Chunying, ZHANG Xun, ZHAO Jinxiong, YUAN Hui, LI Fangjun, ZHAO Bo, ZHU Xiaoqin, YANG Fan, LYU Shichao. Analysis of attack events based on multi-source alerts [J]. Journal of Computer Applications, 2020, 40(1): 123-128.
[7]	YU Yongbin, QI Minhui, Nyima Tashi, WANG Lin. Association rule mining algorithm for Hopfield neural network based on threshold adaptive memristor [J]. Journal of Computer Applications, 2019, 39(3): 728-733.
[8]	LIU Jing, XIAO Guanfeng. Bus arrival time prediction system based on Spark and particle filter algorithm [J]. Journal of Computer Applications, 2019, 39(2): 429-435.
[9]	LIU Zihao, LI Ling, YE Feng. Anomaly detection method for hydrologic sensor data based on SparkR [J]. Journal of Computer Applications, 2019, 39(2): 436-440.
[10]	DU Yuan, ZHANG Shiwei. Improved canonical-order tree algorithm based on restructure [J]. Journal of Computer Applications, 2019, 39(2): 441-445.
[11]	LI Longyang, DONG Yihong, SHI Weijie, PAN Jianfei. SQM: subgraph matching algorithm for single large-scale graphs under Spark [J]. Journal of Computer Applications, 2019, 39(1): 46-50.
[12]	ZHAO Wenfang, WANG Jingli, SHANG Min, LIU Yanan. Forecasting model of pollen concentration based on particle swarm optimization and support vector machine [J]. Journal of Computer Applications, 2019, 39(1): 98-104.
[13]	CUI Chen, ZHENG Linjiang, HAN Fengping, HE Mujun. Design of secondary indexes in HBase based on memory [J]. Journal of Computer Applications, 2018, 38(6): 1584-1590.
[14]	CHEN Liu, FENG Shan. Two-level confidence threshold setting method for positive and negative association rules [J]. Journal of Computer Applications, 2018, 38(5): 1315-1319.
[15]	WU Renbiao, LIU Chao, QU Jingyi. Storage method for flight delay platform based on HBase and Hive [J]. Journal of Computer Applications, 2018, 38(5): 1339-1345.