基于Spark的改进关联规则算法研究-AET-电子技术应用

基于Spark的改进关联规则算法研究

2017年电子技术应用第6期

叶璐，董增寿

太原科技大学电子信息工程学院，山西太原030024

摘要：针对关联规则Apriori算法在信息爆炸时代面对海量数据时，其计算周期大、算法效率低等问题，将数据以特定的数据结构进行存储，降低数据遍历次数；在连接操作前进行剪枝操作，并且改变剪枝操作的判定条件；同时将改进算法IApriori与基于内存的大数据并行计算处理框架Apache Spark相结合，提出了一种基于Spark的Apriori改进算法(Spark+IAprior)。实验结果表明，Spark+IApriori算法在集群伸缩性和加速比方面都优于Apriori算法。

关键词： 关联规则 Apriori MapReduce Hadoop Spark

中图分类号：TP391
文献标识码：A
DOI：10.16157/j.issn.0258-7998.2017.06.032
中文引用格式：叶璐，董增寿. 基于Spark的改进关联规则算法研究[J].电子技术应用，2017，43(6)：126-129.
英文引用格式：Ye Lu，Dong Zengshou. An improved algorithm of association rules based on the Spark[J].Application of Electronic Technique，2017，43(6)：126-129.

An improved algorithm of association rules based on the Spark

Ye Lu，Dong Zengshou

School of Electronic Information Engineering，Taiyuan of Science and Technology，Taiyuan 030024，China

Abstract：Association rules Apriori algorithm have problems with large calculation cycle and low algorithm efficiency faced with huge amounts of data in the era of information explosion, data in a specific storage on the data structure to reduce the data on the number of times past, pruning operation before the items self-joins and changing the terms of judgment have been adopted in the paper, and the algorithm combined with Spark computing framework, an improved algorithm based on the Spark(Spark+IApriori) can be put forward. Experimental results show that the Spark+IApriori algorithm has a good data scalability and speed ratio than Apriori.

Key words :association rules；Apriori；MapReduce；Hadoop；Spark

0 引言

Apriori算法是关联规则(Association rule mining)中最为经典的，随着互联网的发展，已经渐渐不能满足需求。Google在2004年提出了MapReduce框架，然后基于MapReduce的Hadoop应运而生。LI N等提出了一个并行频繁项集挖掘算法（PApriori）^[1]，其中Map操作计算候选项集，Reduce操作统计频繁项集，但其需要反复执行Map操作和Reduce操作；Guo Jian等人提出了一种CMR-Apriori^[2]算法，通过编码和MapReduce对算法进行处理，但是Hadoop需要将中间结果保存到HDFS，也不支持迭代操作。UC Berkeley AMP实验室提出了一种Spark计算框架，Spark是一个基于内存的并行计算框架，它可以大大提高实时数据处理，确保集群的高容错性和在大数据环境下高可伸缩性^[3]。Qiu Hongjian等提出了一种基于Spark RDD框架的频繁项集挖掘(YAFIM)算法^[4]，实验表明Spark的性能远远高于MapReduce框架，但对于候选项集过多时效果也不是很理想；RATHEE S等人提出了一个通过一代代消除候选项从而改进数据集性能的R-Apriori算法^[5]，相较于YAFIM算法，R-Apriori更加具有优越性；Gui Feng在分析了FP-Growth算法的基础上，提出了DPBM算法^[6]，通过引入全球修剪技术极大减少候选项目集。

1 Apriori算法

Apriori算法使用了一个简单的数据结构，执行过程是明确的，但当事务的维度大、最小支持很小时，执行效率将下降。Apriori算法问题总结如下：

(1)每次生成高维项集时需要扫描事务数据库，当事务数据库巨大时，会导致I/O的负担重，计算周期大和算法效率低。

(2)由频繁项集产生候选项集的过程中都需要进行连接和剪枝操作，时间复杂度很高，算法的效率低。

(3)算法会产生大量候选项集，直接导致计算包含大量冗余，使算法效率较低。

2 基于Spark框架的改进Apriori算法

2.1 Apriori算法改进

对于上节提到的问题(1)，改进策略是数据以特定的数据结构存储从而减少扫描数据库次数，本文用图1的存储结构。

通过使用此种数据结构，可以避免重复扫描数据库，大大降低了时间复杂度。当统计候选集的支持度时，只需要将支持度作为Key值，然后将相应下标元素的数组做“与”操作，最后统计非零的数量即为候选集的支持度。

2.2 Spark+IApriori算法

Spark本身是一个计算框架，要计算数据时，一般是从外部文件系统读取数据， Spark本身擅长内存迭代，尤其是基于工作集的内存迭代，会非常高效。如果有分布式大数据仓库，数据仓库会有很多人使用，有些人可能使用同样的作业，而执行同样操作，在Hadoop中就需要重复的计算，而在Spark中，如果发现曾经有人完成了同样的数据、同样的计算，另外有人要和数据仓库进行交互时，直接复用工作集的结果即可，可以极大地提高运算速率。Spark相比Hadoop的MapReduce的优势在于，基于MapReduce的计算引擎通常会将中间结果输出到磁盘中，进行存储和容错。Spark将执行模型抽象为有向无环图执行计划DAG，无须将stage中间结果输出到HDFS中。同时，Spark在数据格式、内存布局、执行策略以及任何调度开销上都有很好的优势。

在上节的基础上，将改进算法IApriori与基于内存的大数据并行计算处理框架Apache Spark相结合，提出了一种基于Spark并行计算处理框架的Apriori改进算法(Spark+IAprior)，算法流程图如图2。算法主要分为两步：(1)产生本地频繁项集；(2)产生全局频繁项集。

3 实验

3.1 环境搭建

由于Spark的服务部署比较繁琐，需要手工编辑配置非常多的文件以及下载依赖包等，本实验采用cloudera manager以GUI的方式管理CDH集群，提供向导式的安装步骤。

(1)实验环境：

处理器：Intel（R）Pentium（R）CPU 3.20 GHz；

安装内存RAM：16 GB；

系统类型：64位操作系统；

(2)环境搭建过程：

①本地Yum软件源安装Cloudera Manager 5：首先需要关闭关闭防火墙、selinux，修改/etc/selinux/config文件，然后安装Apache httpd web服务器，下载CM资源包cm5.0.2-centos6.tar.gz，同时发布CM资源文件，移动解压后的cm文件夹到Web目录，并设置权限，安装postgresql，修改客户端配置，使其可以找到资源文件，下载CM5安装文件cloudera-manager-installer.bin，安装CM5，给cloudera-manager-installer.bin 添加可执行权限，登录CM管理页面，使用用户名和密码都为admin登录http://localhost:7180/界面，如图3。

②CDH5上安装Hive、HBase、Impala、Spark等服务：下载RPM-GPG-KEY-cloudera(这是对rpm包进行校验的文件)，所有的服务器上安装CentOS-6.5-x86_64，并关闭防火墙、selinux、保持时间一致。保持所有的root用户密码一致。一个 Hadoop集群中的节点最少为3台，本测试环境的节点为5台保存到Web服务器的/var/www/html/redhat/cdh目录，cm.worker.com上安装PostgreSQL，图4～图6为Hive、HBase、Impala、Spark的安装和配置图。

3.2 实验结果

实验数据选自网站http://fimi.ua.ac.be/data/，Frequent Itemset Mining Dataset Repository，主要选取其中的T10I4D100K以及Accidents这两个数据库进行测试。

算法有效性测试：在保证数据集的支持度和节点数一致的前提下，将Spark+IApriori算法分别与基于MapReduce框架下Apriori算法（MapReduce+Apriori）与基于Spark框架下的Apriori算法（Spark+Apriori）进行对比，同时寻找数据集拷贝数和算法运行时间的关系。本文根据不同数据库设置了不同的支持度，集群采用了5个节点，其中一个作为Master节点，其余4个作为Slave节点，实验对比结果如图7、图8。从图7、图8可以看出，随着数据拷贝数的增大，也就是随着数据量不断增大，MapReduce+Apriori算法的运行时间几乎直线上升，数据量越大，其处理速度急速下降。这是因为基于MapReduce 计算框架的Hadoop需要将中间结果保存到HDFS，并且MapReduce是分步对数据进行处理的，从图7、图8中可以很明显地看出，Spark框架下的算法运行速度优于Hadoop计算框架，这是因为Spark会在内存中接近“实时”的时间完成所有数据分析，Spark的批处理速度比MapReduce快近10倍。同时从图7、图8也可以看出，基于Spark框架下，改进Apriori算法的运行效率也高于Apriori算法，证明Spark+IApriori算法是有效的。

为了消除单一实验中偶然误差的影响，本文主要从下面两个方面对Spark+IApriori算法进行评估性能：

（1）集群的可伸缩性：在数据集的支持度和数据量一定的前提下，寻找数据集节点与算法运行时间的关系；为了测试集群的可伸缩性，本文同样根据不同数据库设置了不同的支持度，图9、图10反映了不同数据集节点与算法运行时间的关系。对于不同数据集，其算法运行时间以及下降趋势也是不同的，这是因为对于不同的数据集，数据的横纵向维度、局部频繁项集大小以及设置的最小支持度minsup都会有差异。

（2）集群的加速比：算法在单节点和多节点上运行时间的比值：

其中，t₁表示算法在单节点上的运行时间，t_i表示作业在n个节点下的运行时间。

在本实验中，为了测试Spark+IApriori算法的加速比，在保持实验其他参数一致的情况小，通过改变节点数来测试加速比，实验结果如图11、图12。加速比无法呈线性的主要原因是集群间的通信时间消耗。

综上所述，Spark+IApriori算法优于基于MapReduce框架下Hadoop平台的Apriori算法；同时在Spark 平台下，Spark+IApriori算法在数据伸缩性和加速比方面都优于Spark框架下的Apriori算法。

4 结语

本文在介绍关联规则的概念以及分析Apriori算法的基础上，发现Apriori算法存在数据量巨大时计算周期大、修剪操作计算复杂度高、产生大量不必要的候选项集等问题，为解决这些问题，对算法在数据结构以及剪枝操作进行了改进，然后结合Spark计算框架，提出了Spark+IApriori算法。实验验证了Spark+IApriori算法的有效性以及在集群伸缩性和加速比方面的优势。

参考文献

[1] LI N，ZENG L，HE Q.Parallel implementation of Apriori algorithm based on MapReduce[C].2012 13th ACM International Conference on Software Engineering, Artificial Intelligence，Networking and Parallel & Distributed Computing，IEEE Computer Society.Kyoto，Japan，2012：236-241.

[2] Guo Jian.Research on improved Apriori algorithm based on coding and MapReduce[C].2013 10th Web Information System and Application Conference(WISA 2013)，IEEE Computer Society.Yangzhou，Jiangsu，China，2013：294-299.

[3] Gao Yanjie.Data processing with Spark technology，application and performance optimization[M].China Machine Press，2014.

[4] Qiu Hongjian，Gu Rong，Yuan Chunfeng.YAFIM：A parallel frequent item set mining algorithm with Spark[C].2014 IEEE 28th International Parallel & Distributed Processing Symposium Workshops，IEEE Computer Society.Phoenix，AZ，United states，2014：1664-1671.

[5] RATHEE S，KAUL M，KASHYAP A.R-apriori：An efficient Apriori based algorithm on Spark[C].PIKM 2015-Proceedings of the 8th Ph.D.Workshop in Information and Knowledge Management.Melbourne，VIC，Australia，2015：27-34.

[6] GUI F，MA Y，ZHANG F，et al.A distributed frequent item set mining algorithm based on Spark[C].Proceedings of the 2015 IEEE 19th International Conference on Computer Supported Cooperative Work in Design.Calabria，Italy，2015：271-275.

作者信息:

叶璐，董增寿

（太原科技大学电子信息工程学院，山西太原030024）

原创声明：此内容为AET网站原创，未经授权禁止转载。

相关内容