• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 论文 • 上一篇    下一篇

一种基于Spark框架的并行FP-Growth挖掘算法

张稳,罗可   

  1. (长沙理工大学计算机与通信工程学院,湖南 长沙 410114)
  • 收稿日期:2015-12-11 修回日期:2016-03-31 出版日期:2017-08-25 发布日期:2017-08-25
  • 基金资助:

    国家自然科学基金(71371065,11671125);湖南省科技计划项目(2013SK3146)

A parallel FP-Growth mining algorithm
based on Spark framework

ZHANG Wen,LUO Ke   

  1. (School of Computer & Communication Engineering,
    Changsha University of Science & Technology,Changsha 410114,China)
  • Received:2015-12-11 Revised:2016-03-31 Online:2017-08-25 Published:2017-08-25

摘要:

Apriori和FP-Growth算法是频繁模式挖掘中的经典算法,由于Apriori存在更多缺陷,因此FP-Growth是单机计算环境下比较高效的算法。然而,对于非并行计算在大数据时代遇到的瓶颈,提出一种基于事务中项间联通权重矩阵的负载平衡并行频繁模式增长算法CWBPFP。算法在Spark框架上实现并行计算,数据分组时利用负载均衡策略,存入分组的数据是相应频繁项的编码。每个工作节点将分组数据中每一个事物中项的联通信息存入一个下三角联通权重矩阵中,使用被约束子树来加快每个工作节点挖掘频繁模式时创建条件FP-tree的速度,再用联通权重矩阵避免每次挖掘分组中频繁模式时对条件模式基的第一次扫描。由于联通权重矩阵和被约束子树的结合应用于每一个工作节点的FP-tree挖掘过程,因此提升了并行挖掘FP-tree性能。通过实验表明,所提出的并行算法对大的数据有较高性能和可扩展性。
 

关键词: 数据挖掘, 关联规则, FP-Growth, 大数据, 并行计算, Spark

Abstract:

The Apriori and FP-Growth are classical algorithms in frequent pattern mining. Since the Apriori has more flaws, the FP-Growth is a more efficient algorithm in stand-alone computing environment. Aiming at the bottlenecks of non-parallel computing in the era of big data, we propose a balanced parallel frequent pattern (BPFT) growth algorithm based on the connect-weight (CW) matrix of items in each transaction, called CWBPFP, which achieves parallel computing based on Spark framework. We use the load balance strategy to group data, and the corresponding code of each frequent item is stored in the relevant group during grouping. The connect information of items in each transaction of each grouped data is stored into a lower triangular connect-weight matrix by each working node. We use the restricted sub-tree to accelerate the speed of producing conditional FP-tree, and employ the connect-weight matrix to avoid the first scanning for the conditional patterns during mining frequent patterns of grouped data. The performance of the parallel mining FP-tree is improved due to the combination of the CW matrix and the restricted sub-tree applied to FP-tree mining process of each node. Experiments show that the CWBPFP has high performance and scalability on big data sets.

Key words: data mining, association rule, FP-Growth, big data, parallel computing, Spark