《电子技术应用》

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

2017年电子技术应用第6期 作者:叶 璐,董增寿
2017/7/20 11:49:00

叶  璐,董增寿

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


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

    关键词: 关联规则;Apriori;MapReduceHadoop;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.

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的存储结构。

jsj3-t1.gif

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

jsj3-gs1-4.gif

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)产生全局频繁项集。

jsj3-t2.gif

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。

jsj3-t3.gif

    ②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的安装和配置图。

jsj3-t4.gif

jsj3-t5.gif

jsj3-t6.gif

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算法是有效的。

jsj3-t7.gif

jsj3-t8.gif

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

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

jsj3-t9.gif

jsj3-t10.gif

    (2)集群的加速比:算法在单节点和多节点上运行时间的比值:

    jsj3-gs5.gif

其中,t1表示算法在单节点上的运行时间,ti表示作业在n个节点下的运行时间。

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

jsj3-t11.gif

jsj3-t12.gif

    综上所述,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.

继续阅读>>