基于条件模式的一种无分组并行频繁模式挖掘算法

匡哲君; 周航; 周东岱; 周晋鹏; 杨鲲

doi:10.1631/FITEE.1800467

Your Location：

Home >

Browse articles >

基于条件模式的一种无分组并行频繁模式挖掘算法

常规文章 | Updated：2022-05-19

- 基于条件模式的一种无分组并行频繁模式挖掘算法
- A non-group parallel frequent pattern mining algorithm based on conditional patterns
- 信息与电子工程前沿（英文） 2019年20卷第9期页码：1234-1245
- Affiliations：
  
  College of Computer Science and Technology, Changchun University, Changchun 130022, China
  School of Economics, Changchun University, Changchun 130022, China
  School of Information Science and Technology, Northeast Normal University, Changchun 130117, China
  Division of Engineering Science, University of Toronto, Ontario M5S2E8, Canada
  School of Computer Science and Electronic Engineering, University of Essex, Colchester CO43SQ, UK
- Author bio：
  
  [ "Zhe-jun KUANG, E-mail: kuangzhejun@ccu.edu.cn" ]
  [ "Hang ZHOU, E-mail:zhouhang0311@163.com" ]
  Dong-dai ZHOU, E-mail:ddzhou@nenu.edu.cn
- Funds：
  
  Project supported by the Fundamental Research Funds for the Central Universities, China (No. 2412015KJ005), the Twelfth Five-Year Plan Project of the Education Department of Jilin Province, China (No. 557), and the Thirteenth Five-Year Plan for Scientific Research of the Education Department of Jilin Province, China (No. JJKH20191197KJ)
- DOI：10.1631/FITEE.1800467
  中图分类号： TP301
- 收稿：2018-08-05，
  
  修回：2019-;8-23，
  
  纸质出版：2019-09
- Accepted：
Scan QR Code
匡哲君, 周航, 周东岱, 等. 基于条件模式的一种无分组并行频繁模式挖掘算法[J]. 信息与电子工程前沿（英文）, 2019,20(9):1234-1245.

Zhe-jun KUANG, Hang ZHOU, Dong-dai ZHOU, et al. A non-group parallel frequent pattern mining algorithm based on conditional patterns[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(9): 1234-1245.
匡哲君, 周航, 周东岱, 等. 基于条件模式的一种无分组并行频繁模式挖掘算法[J]. 信息与电子工程前沿（英文）, 2019,20(9):1234-1245. DOI： 10.1631/FITEE.1800467.

Zhe-jun KUANG, Hang ZHOU, Dong-dai ZHOU, et al. A non-group parallel frequent pattern mining algorithm based on conditional patterns[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(9): 1234-1245. DOI： 10.1631/FITEE.1800467.

摘要

频繁项集挖掘是关联规则挖掘的主要方法。由于计算空间和性能限制，特别是当数据集剧增时，挖掘频繁项的关联需要大量时间和资源。在大数据环境下的关联数据挖掘过程中，通常采用MapReduce模型进行任务划分及并行处理，从而提高算法执行效率。为确保关联规则在任务划分和并行处理期间不被破坏，需要将内部关系数据存储在计算机空间中。与原始数据集相比，存储冗余的内部关系数据将显著增加空间的使用。研究发现，频繁模式挖掘算法的形成主要依赖于条件模式基。基于并行频繁模式（PFP）算法理论，本文提出一种无分组的PFP（NG-PFP）挖掘算法。该算法取消了分组模式，减少了子任务之间的数据冗余。实验结果表明，无分组模型在计算效率和空间利用率方面都有显著提高。

Abstract

Frequent itemset mining serves as the main method of association rule mining. With the limitations in computing space and performance

the association of frequent items in large data mining requires both extensive time and effort

particularly when the datasets become increasingly larger. In the process of associated data mining in a big data environment

the MapReduce programming model is typically used to perform task partitioning and parallel processing

which could improve the execution efficiency of the algorithm. However

to ensure that the associated rule is not destroyed during task partitioning and parallel processing

the inner-relationship data must be stored in the computer space. Because inner-relationship data are redundant

storage of these data will significantly increase the space usage in comparison with the original dataset. In this study

we find that the formation of the frequent pattern (FP) mining algorithm depends mainly on the conditional pattern bases. Based on the parallel frequent pattern (PFP) algorithm theory

the grouping model divides frequent items into several groups according to their frequencies. We propose a non-group PFP (NG-PFP) mining algorithm that cancels the grouping model and reduces the data redundancy between sub-tasks. Moreover

we present the NG-PFP algorithm for task partition and parallel processing

and its performance in the Hadoop cluster environment is analyzed and discussed. Experimental results indicate that the non-group model shows obvious improvement in terms of computational efficiency and the space utilization rate.

关键词

Keywords

references

R Agrawal , , , R Srikant . . Fast algorithms for mining association rules in large databases . . Proc Int Conf on Very Large Data Bases , , 1994 . . p.487 - - 499 . . . .

RC Agarwal , , , CC Aggarwal , , , VVV Prasad . . A tree projection algorithm for generation of frequent item sets . . J Parall Distrib Comput , , 2002 . . 61 ( ( 3 ): ): 350 - - 371 . . DOI: 10.1006/jpdc.2000.1693 http://doi.org/10.1006/jpdc.2000.1693 . .

M Bauer , , , M Bruveris , , , N Charon , , , 等 . . A relaxed approach for curve matching with elastic metrics . . 2018 . . https://arxiv.gg363.site/abs/1803.10893 https://arxiv.gg363.site/abs/1803.10893 , , . .

L Berti-équille , , , H Harmouch , , , F Naumann , , , 等 . . Discovery of genuine functional dependencies from relational data with missing values . . Proc VLDB Endowm , , 2018 . . 11 ( ( 8 ): ): 880 - - 892 . . DOI: 10.14778/3204028.3204032 http://doi.org/10.14778/3204028.3204032 . .

L Caruccio , , , V Deufemia , , , G Polese . . On the discovery of relaxed functional dependencies . . Proc 20 th Int Database Engineering & Applications Symp , , 2016 . . p.53 - - 61 . . DOI: 10.1145/2938503.2938519 http://doi.org/10.1145/2938503.2938519 . .

L Caruccio , , , V Deufemia , , , G Polese . . Evolutionary mining of relaxed dependencies from big data collections . . Proc 7 th Int Conf on Web Intelligence, Mining and Semantics, Article 5 , , 2017 . . DOI: 10.1145/3102254.3102259 http://doi.org/10.1145/3102254.3102259 . .

L Caruccio , , , G Polese , , , G Tortora . . Dependency-based query/view synchronization upon schema evolutions . . Int Conf on Conceptual Modeling , , 2018 . . p.91 - - 105 . . DOI: 10.1007/978-3-030-01391-2_17 http://doi.org/10.1007/978-3-030-01391-2_17 . .

JC Chen , , , YG Chen , , , XY Du , , , 等 . . Big data challenge: a data management perspective . . Front Comput Sci , , 2013 . . 7 ( ( 2 ): ): 157 - - 164 . . DOI: 10.1007/s11704-013-3903-7 http://doi.org/10.1007/s11704-013-3903-7 . .

S Cong , , , J Han , , , D Padua . . Parallel mining of closed sequential patterns . . Proc 11 th ACM SIGKDD Int Conf on Knowledge Discovery in Data Mining , , 2005 . . p.562 - - 567 . . . .

LL Deng , , , YS Lou . . Improvement and research of FP-growth algorithm based on distributed spark . . Proc Int Conf on Cloud Computing and Big Data , , 2015 . . p.105 - - 108 . . DOI: 10.1109/CCBD.2015.15 http://doi.org/10.1109/CCBD.2015.15 . .

L di-Jorio , , , A Laurent , , , M Teisseire . . Mining frequent gradual itemsets from large databases . . Int Symp on Intelligent Data Analysis , , 2009 . . p.297 - - 308 . . DOI: 10.1007/978-3-642-03915-7_26 http://doi.org/10.1007/978-3-642-03915-7_26 . .

M El-Hajj , , , OR Zaïane . . Parallel bifold: large-scale parallel pattern mining with constraints . . Distrib Parall Datab , , 2006 . . 20 ( ( 3 ): ): 225 - - 243 . . DOI: 10.1007/s10619-006-0445-0 http://doi.org/10.1007/s10619-006-0445-0 . .

KS Ge , , , HY Su , , , DS Li , , , 等 . . Efficient parallel implementation of a density peaks clustering algorithm on graphics processing unit . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 7 ): ): 915 - - 927 . . DOI: 10.1631/FITEE.1601786 http://doi.org/10.1631/FITEE.1601786 . .

JW Han , , , J Pei , , , YW Yin . . Mining frequent patterns without candidate generation . . ACM SIGMOD Rec , , 2000 . . 29 ( ( 2 ): ): 1 - - 12 . . DOI: 10.1145/335191.335372 http://doi.org/10.1145/335191.335372 . .

Y Huhtala , , , J Kärkkäinen , , , P Porkka , , , 等 . . Tane: an efficient algorithm for discovering functional and approximate dependencies . . Comput J , , 1999 . . 42 ( ( 2 ): ): 100 - - 111 . . DOI: 10.1093/comjnl/42.2.100 http://doi.org/10.1093/comjnl/42.2.100 . .

S Kruse , , , F Naumann . . Efficient discovery of approximate dependencies . . Proc VLDB Endowm , , 2018 . . 11 ( ( 7 ): ): 759 - - 772 . . DOI: 10.14778/3192965.3192968 http://doi.org/10.14778/3192965.3192968 . .

HY Li , , , Y Wang , , , D Zhang , , , 等 . . PFP: parallel FP-growth for query recommendation . . Proc ACM Conf on Recommender Systems , , 2008 . . p.107 - - 114 . . DOI: 10.1145/1454008.1454027 http://doi.org/10.1145/1454008.1454027 . .

N Li , , , L Zeng , , , Q He , , , 等 . . Parallel implementation of Apriori algorithm based on MapReduce . . Proc. 13 th ACIS Int Conf on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing , , 2012 . . p.236 - - 241 . . DOI: 10.1109/SNPD.2012.31 http://doi.org/10.1109/SNPD.2012.31 . .

KW Lin , , , SH Chung . . A fast and resource efficient mining algorithm for discovering frequent patterns in distributed computing environments . . Fut Gener Comput Syst , , 2015 . . 52 49 - - 58 . . DOI: 10.1016/j.future.2015.05.009 http://doi.org/10.1016/j.future.2015.05.009 . .

MY Lin , , , PY Lee , , , SC Hsueh . . Apriori-based frequent itemset mining algorithms on MapReduce . . Proc 6 th Int Conf on Ubiquitous Information Management and Communication, Article 26 , , 2012 . . DOI: 10.1145/2184751.2184842 http://doi.org/10.1145/2184751.2184842 . .

JQ Liu , , , YS Wu , , , QF Zhou , , , 等 . . Parallel Eclat for opportunistic mining of frequent itemsets . . Int Conf on Database and Expert Systems Applications , , 2015 . . p.401 - - 415 . . DOI: 10.1007/978-3-319-22849-5_27 http://doi.org/10.1007/978-3-319-22849-5_27 . .

C Lucchese , , , S Orlando , , , R Perego , , , 等 . . WebDocs: a real-life huge transactional dataset . . Proc IEEE ICDM Workshop on Frequent Itemset Mining Implementations , , 2004 . . .

P Mandros , , , M Boley , , , J Vreeken . . Discovering reliable approximate functional dependencies . . Proc 23 rd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , , 2017 . . p.355 - - 363 . . DOI: 10.1145/3097983.3098062 http://doi.org/10.1145/3097983.3098062 . .

M Riondato , , , JA DeBrabant , , , R Fonseca , , , 等 . . PARMA: a parallel randomized algorithm for approximate association rules mining in MapReduce . . Proc 21 st ACM Int Conf on Information and Knowledge Management , , 2012 . . p.85 - - 94 . . DOI: 10.1145/2396761.2396776 http://doi.org/10.1145/2396761.2396776 . .

A Siddiqa , , , A Karim , , , A Gani . . Big data storage technologies: a survey . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 8 ): ): 1040 - - 1070 . . DOI: 10.1631/FITEE.1500441 http://doi.org/10.1631/FITEE.1500441 . .

R Srikant , , , R Agrawal . . Mining sequential patterns: generalizations and performance improvements . . Int Conf on Extending Database Technology , , 1996 . . p.1 - - 17 . . DOI: 10.1007/BFb0014140 http://doi.org/10.1007/BFb0014140 . .

F Wang , , , L Hu , , , J Zhou , , , 等 . . A survey from the perspective of evolutionary process in the Internet of Things . . Int J Distrib Sen Networks , , 2015 . . 11 ( ( 3 ): ): 462752 DOI: 10.1155/2015/462752 http://doi.org/10.1155/2015/462752 . .

J Wang , , , J Han . . BIDE: efficient mining of frequent closed sequences . . Proc 20 th Int Conf on Data Engineering , , 2004 . . p.79 - - 90 . . DOI: 10.1109/ICDE.2004.1319986 http://doi.org/10.1109/ICDE.2004.1319986 . .

D Xia , , , Y Zhou , , , Z Rong , , , 等 . . IPFP: an improved parallel FP-growth algorithm for frequent itemsets mining . . Proc 59 th ISI World Statistics Congress , , 2013 . . p.4034 - - 4039 . . . .

D Xia , , , Z Rong , , , Y Zhou . . A novel parallel algorithm for frequent itemsets mining in massive small files datasets . . ICIC Expr Lett Part B , , 2014 . . 5 ( ( 2 ): ): 459 - - 466 . . . .

Q Yang , , , FY Du , , , X Zhu , , , 等 . . Improved balanced parallel FP-growth with MapReduce . . Joint Int Conf on Artificial Intelligence and Computer Engineering and Int Conf on Network and Communication Security , , 2016 . . p.1 - - 5 . . DOI: 10.12783/dtcse/aice-ncs2016/5681 http://doi.org/10.12783/dtcse/aice-ncs2016/5681 . .

XY Yang , , , Z Liu , , , Y Fu . . MapReduce as a programming model for association rules algorithm on Hadoop . . Proc 3 rd Int Conf on Information Sciences and Interaction Sciences , , 2010 . . p.99 - - 102 . . DOI: 10.1109/ICICIS.2010.5534718 http://doi.org/10.1109/ICICIS.2010.5534718 . .

KM Yu , , , JY Zhou , , , WC Hsiao . . Load balancing approach parallel algorithm for frequent pattern mining . . Proc Int Conf on Parallel Computing Technologies , , 2007 . . p.623 - - 631 . . DOI: 10.1007/978-3-540-73940-1_63 http://doi.org/10.1007/978-3-540-73940-1_63 . .

MJ Zaki . . Scalable algorithms for association mining . . IEEE Trans Know Data Eng , , 2000 . . 12 ( ( 3 ): ): 372 - - 390 . . DOI: 10.1109/69.846291 http://doi.org/10.1109/69.846291 . .

MJ Zaki . . Parallel sequence mining on shared-memory machines . . J Parall Distrib Comput , , 2001a . . 61 ( ( 3 ): ): 401 - - 426 . . . .

MJ Zaki . . SPADE: an efficient algorithm for mining frequent sequences . . Mach Learn , , 2001b . . 42 ( ( 1-2 ): ): 31 - - 60 . . DOI: 10.1023/A:1007652502315 http://doi.org/10.1023/A:1007652502315 . .

XL Zhang , , , F Breitinger , , , I Baggili . . Rapid Android parser for investigating DEX files (RAPID) . . Dig Investig , , 2016 . . 17 28 - - 39 . . DOI: 10.1016/j.diin.2016.03.002 http://doi.org/10.1016/j.diin.2016.03.002 . .

XL Zhang , , , I Baggili , , , F Breitinger . . Breaking into the vault: privacy, security and forensic analysis of Android vault applications . . Comput Secur , , 2017 . . 70 516 - - 531 . . DOI: 10.1016/j.cose.2017.07.011 http://doi.org/10.1016/j.cose.2017.07.011 . .

ZG Zhang , , , GL Ji , , , MM Tang . . MREclat: an algorithm for parallel mining frequent itemsets . . Proc Int Conf on Advanced Cloud and Big Data , , 2013 . . p.177 - - 180 . . DOI: 10.1109/CBD.2013.22 http://doi.org/10.1109/CBD.2013.22 . .

YX Zhao , , , WX Zhang , , , DS Li , , , 等 . . Pegasus: a distributed and load-balancing fingerprint identification system . . Front Inform Technol Electron Eng , , 2016 . . 17 ( ( 8 ): ): 766 - - 780 . . DOI: 10.1631/FITEE.1500487 http://doi.org/10.1631/FITEE.1500487 . .

XF Zheng , , , S Wang . . Study on the method of road transport management information data mining based on pruning Eclat algorithm and MapReduce . . Proc Soc Behav Sci , , 2014 . . 138 757 - - 766 . . DOI: 10.1016/j.sbspro.2014.07.254 http://doi.org/10.1016/j.sbspro.2014.07.254 . .

L Zhou , , , ZY Zhong , , , J Chang , , , 等 . . Balanced parallel FP-growth with MapReduce . . Proc. IEEE Youth Conf on Information, Computing and Telecommunications , , 2010 . . p.243 - - 246 . . DOI: 10.1109/YCICT.2010.5713090 http://doi.org/10.1109/YCICT.2010.5713090 . .

YT Zhuang , , , F Wu , , , C Chen , , , 等 . . Challenges and opportunities: from big data to knowledge in AI 2.0 . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 1 ): ): 3 - - 14 . . DOI: 10.1631/FITEE.1601883 http://doi.org/10.1631/FITEE.1601883 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

An efficient parallel and distributed solution to nonconvex penalized linear SVMs

Networking and communication challenges for post-exascale systems

Meeting deadlines for approximation processing in MapReduce environments

Challenges and opportunities: from big data to knowledge in AI 2.0