通过对Spark大数据平台以及Eclat算法的深入分析，提出了基于Spark的Eclat算法（即SPEclat）。针对串行算法在处理大规模数据时出现的不足，该方法在多方面进行改进：为减少候选项集支持度计数带来的损耗，改变了数据的存储方式；将数据按前缀进行分组，并划分到不同的计算节点，压缩数据的搜索空间，实现并行化计算。最终将算法结合Spark云计算平台的优势加以实现。实验表明该算法可在处理海量数据集时高效运行，并且在面对数据量大规模增长的情况下具备良好的可扩展性。
20 计算机应用研究 第36卷 Bitset求与操作常数时间即可完成,所以频繁项集产生的消耗验表明两种算法得到的结果一致。 是非常少的。数据划分的伪代码如算法2所示。 3.1加速比测试 算法2按前缀划分数据 Rcad L(2)from RDD 为了验证 SPEclat算法是否具有可扩展性以及处理大数据 map( Items, BitSet 的能力,拟人工生成大小为10GB、20GB、30(,项目数为80 get the profix p from items 的三个不同大小的数据集,用于以下实验。 t(p,( Items, BitSet)) 加速比指同一仁务在单处坦器和多处埋器系统中运行消 ReduceBykey(p, ( Items, BitSet)) 耗时问的比率,是一种用来衡量并行化性能的一个有效指标。 gel all C frun ileitis 因此,为了考察算法的并行化性能,应用以上数据进行算法的 Eclat(Cn) 加速比性能实验。实验对三个数据集分别在468个节点上 out( frequent Itemset with profix p) 运行算法,实验结果如图2所示。为了对比明显,加入了线性 加速比结果。从图2可以看出,对于同一数据集,该算法运行 在各节点上使用 SPEclat算法并行挖摒频繁集,需瑟迭代的加速比会随着节点数的增加而增加。由于节点数的增加,使 地以 Imap/reduce任务来实现,其中mφ()方法实现数据的划得节点间的通信、数据传递所消耗的时间逐渐增加,所以增加 分, reduce阶段实现改进后的 Eclat算法。在mpcr与 reducer趋势接近线性,但是与线性加速比有一定差距,而且随着节点 之间需要重写 parlon过程,以确保属于同一分组的前缀所对数的增加差距也越大。对比不同数据集的加速比,当数据量越 应的列被划分到同一个计算节点中。 大时,加速比会越接近线性加速比,原因在于面对数据量更大 2.3第三阶段 的数据集,数据计算所消耗的吋间占总耗时的比例相比于小的 本阶段将在各个计算节点中针对具有相同前缀的项集并数据集要更多。实验表明, SPEclat算法具有一定的可扩展性 行地以自底向上的形式进行迭代,用频繁k项集产生频繁(k+3.2数据的可扩展性测试 1)项集。即在母个节点中,对分配到该节点的项集进行自连 通过比较 SPeclat与 MEPlat算法在不同数据集上的运算 接,产生候选k项集,之后进行支持度计数。 效率,验证 SPEclat算法的数据可扩展性。5Plat是 Eclat算 因为在22节数据已经被转换为( ItemSet,,tset)形式,所法在Sma上的实现,而 MREclat是Ect算法基于 MapReduce 以求候选项集支持度时,可使用在同一节点的两个自连接的频的经典实现,其运行效率较其他同类算法更为优越,所以运用 繁项集的 Bitset求与來对侯选项集的进行计数。在求与之后 这两种算法进行对比,以验证 SPEclat的数据可扩展性。 得到包含该候选项集的事务序列。该过程中利用 Bitset求与 使用3.1节实验中人工生成的数据集,对 SPeclat与MRE 的快速运算代替集合之间的求交运算,能节省大量时间。之后cla算法进行了对比实验,以评估算法的运行效率。实验结果 对生成的 Bissel进行计数,判断计数值是否大于最小支持度。如图3所示。其中x轴代表人工数据的数据量,y轴则表示程 若大于,则将候选项集和对应BSct组成的键值对存入F序执行所用的时间。支持度为5%,节点数设置为8个。 当中。算法3是第三阶段所采用算法的伪代码。 算法3生成频繁k+1项集 Rcad L(/)from RDD for each l, in L(k) 一线性加速比 ch (: in L(h) —10GB效据量 20GB数据量 lierse=(2[1],12L2],1[3],…,12[k-1],[k,l[k]) 30CB数据量 数据集大小GB Bitset =l. BitSet, BitSet 节点数 人工数砉集: min sup=5 图2加速比测试 图3人工数据测试实验 L(K+1)+=(ItemSet, BitSet) 实验的统计结果表明, SPeclat较 MREclat算法而言,在性 之后,对生成的频繁(k+Ⅰ)项集进行再划分,迭代式地调能上取得了显著地提高,并且随着数据量的增长,性能的提升 用 SPeclat算法挖掘频繁项集,直到没有更多的频繁项产生。不断增加,且 SPEclat算法的性能具有明品优势。 2.4时间复杂度分析 为了进一步验证算法的数据可扩展性,对 SPEca与 需要对些值进行假设,以数学公式的形式表示算法的时 Trelat算法分别进行了多组对比实验。使用公共测试数据 集TI0H4D100K、 Pumsb star和 chess以保证实验的客观性。为 间复杂度。假设原数据集中事务个数为T,计算节点数为N,4了确保实验结果的正确性图中的值为算法运行10次的平均值。 代表频繁一项集的个数。原算法的时间复杂度为0(2、Tx 在测量算法可扩展性的过程中,将节点数调为8个,并 a2)。而对原算法进行改进后的SPE算法的时间复杂度为分别将测试数据复制为原数据集人小的234.56倍,通过多 次实验测量两种并行算法的数据可扩展性。实验结果如图4 °(n× 所示。其中x轴代表副木数据的复制次数,y轴则表小程序执 行所花费的时间。从图中可以看到,对于不断增长的数据量 3相关实验与分析 Marechal算法执行所消耗的时间近似于直线式增长,而 SPEclal 实验室的分布式计算平台由九台计算机搭建而成,其中主算法的运算时间增长较为缓慢,堪本上保持水平;同时 节点配置为门73770处理器,4CB内存,TB硬盘。计算节点算法所消耗的时间远少于 MrEclal,完成计算任务的速率是 配置为奔腾2140处里器;1C内存,250c硬盘。5mk集 MREclat算法速率的20倍左右。 群的环境参数如下所示: Ubuntu14.04; Hadoop version2.4.0; 其原因是 SPEclat算法采用基于内存的计算方式,可将数 park version I.6.l。 据集在内存中快速地进行多次迭代,省去人量LO操作。同 为了验证 SPEclat算法的正确性,在T1OH4D100K、Pmsb 时,在对候选项集进行支持度计数时,通过对数据存储结构的 dr和ches数据集上与 MREclat的处理结果进行了对比,实改变,实现了利用Bise求与的快速运算代替集合之间求交运 第1期 冯兴杰,等:基于 Spark的并行 Eclat算法 21 算,优化了攴持度计数的计算方式,提升了运算效率,且相较于 large databases[ C]//Proc of International Conference on Very Large MREclat算法, SPEclat算法性能的提升会随着数据量的增加而 Data Bases. San Francisco: Morgan Kaufmann Publishers Inc 变得愈发明显。 1994:487-499 [3 Zaki MJ, Parthasarathy S, Ogihara M, el al. Parallel alyuril hIs fe discovery of association rules J]. Data Mining and Knowledge 长600 Discovery,1997,1(4):343-373 [4] Zaki M Scalable algorithms for association mining]. IEEE Trans 200 on Knowledge Data Engineering, 2000, 12(3): 372-390 0 [5 Dean J, Ghemawat S. MapReduce: simplified data processing on 12 复制数据集次数 复制数据集次数 large clusters[ C]//Proc of the 6th Conference on Symposium on Op (aT1ol4D100K: min sup-025% (b)Pumsb star: min sup-0.65%0 erating Systems Design Implementation. Berkeley: USENIX Asso- Pecial claton,2004:107-113 MREcat [6]李伟卫,赵航,张阳,等。基于 MapReduce的海量数据挖掘技术 600 研究[J计算机工程与应用,2013,49(20):112-117.( Li Wei wei, Zhao Ilang, Zhang Yang, et al. Research on massive data 200 mining based on Map Reduce[ J]. Computer Engineering and Ap plications,2013,49(20):112-117.) 复制数据集次数 (c)Chess: min sup35% [冂]章志刚,吉报林,唐梦梦.并行挖掘频繁项日集新算法- 图4数据可扩展性测试 MREclat[ J 1.计算机应用,2014,34(8):2175-2178.( Zhang Zhigang, Ji Cenlin, Tang Mengmeng. MREclat: new algorithm for par- 3.3节点的可扩展性测试 allel mining frequent itemsets[J]. Journal of Computer Applica 在验证 SPEclat算法的节点可扩展性时,分别使用公共测 Lions,2014,34(8):2175-2178 [8 Qiu Hongjian, Gu Rong, Yuan Chunfeng, et aL. YAFIM: a parallel 试数据集T10l4D100K、 Pumsh star和 chess进行实验,并凋整 frequent ile msel miring algorithm with Spark[C]//Pre of IEEE. In- 集群节点数为46、8个,保持数据集的大小不变,分别记录 lermalional Parallel Disl ribuled Processing SymmposilIn Workshops SPEclat算法执行所消耗的时间。实验结果如图5所示。其中 Washington DC: IEEE Computer Society, 2014: 1664-1671 X轴代表集群中节点的个数,Y轴代表所花费的时间。分析图[9] Deng lingling, Lou yuansheng. Improvement and research of Fl 5可知,随着集群中节点数的增加, SPEclat算法的耗时呈近似 growth algorithm based on distributed Spark[ C]//Proc of Internati 线性依次递减,结果表明该算法具有良好的节点可扩展性。 nal Conference on Cloud Computing and Big Data. Washington D 26 IEEE Computer Society, 2015: 105-108 → SPEclat SPEclat [10 Yang Shaosong, Xu Guoyan, Wang Zhijian, et al. The parallel im- 80 20 proved Apriori algorithm research based on Spark[cl//Proc of the 9th Internatior onference on Frontier of Computer Science and 70 Technology. Piscataway, NJ IEEE Press, 2015: 354-359 节点数 节点数 [11 Wang Shuang, Wu Peng, Till Tao, et al. P-WLPA algorithm research (aT1014D100K: min sup (b)Pumsb star: min sup=0.65% n parallel framework Spark[ C//Proc of Information Technology and · SPeclat Artificial Intelligence Conference. Piscataway N: IEEE Press 2014 [12]曹博,倪寔成,李淋淋,等.基于 Spark的并行频繁模式挖据箅 210 法J].计算机工栏与应用, 0 Jiancheng, Li Linlin, et al. Parallel frequence pattern mining algo 节点数 rithm based on Spark[ J]. Computer Engineering and Applica- (e)Chess: min sup=35% tons,2016,52(20):86-91.) 图5节点可扩展性测试 [13]陈明洁.分布式频繁项集挖掘算法[J].计算机应用与软件 2015, 32(10): 63-66.( Chen Mingjie. a distributed frequent itemset 4结束语 mining algorithm[J]. Computer Applications and Software, 2015 32(10):63-66.) 本文提出了基于 Spark的 Eclat频繁项集挖掘算法SE-[14]赵焱德.基于 SPARK的浄量数捃颎繁模式挖掘算法硏究[D」 clat针对信息化时代产生的海量数据,木文将原冇串行 eclat 哈尔滨:哈尔滨工业大学,2016.( Zhao yanda. Research on frc 算法进行了改进,并依托 Spark平台将其实现并行化,充分利 quant pattcrn mining algorithm for massive data based on SPARK 用 Spark平台基于内存、利于迭代式计算的特性,完成了算法 I]. Harbin: Harbin Institute of Technology 2016. 在挖掘海量数据时性能上的突破,解决了其并行化所遇到的[15]郭进伟,皮建勇,基于 Mapreduce的sON算法实现[J.宀算机 J F, 2014(sl): 100-102.( Guo Jinwei, Pi Jianyong. Implementa- 如数据的划分、生成频繁项集时产生人量的交叉计算等问题。 tion of SoN algorithm based on MapReduce J] Journal of Compu 最终利用人造数据以及公共数据集加以实验,证明针对该算法 ter Applications, 2014(sl ): 100-102.) 的改进是行之冇效的,且随着数据量的不断増长,算法的性能[I6马可,李玲娟,孙杜靖。分布式并行仁数据流频繁模式挖掘算決 会有更加显著的提高。 J].计算机技术与发展,2016,26(7):75-79.(MaKe,li Lingjuan, Sun Dujing. Distributed parallel algorithm of mining fre- 参考文献 quent pattern on data stream[ 1]. Computer Technology and de [Ⅰ』韩家炜,堪博,装健,等.数据挖掘:概念与抆术[Ⅵ].范明,等 velopment,2016,26(7):75-79.) 译2版北京:机械工些出版社,2007:147-154.(H灬 n1 Jiawei,[Iη]唐颖峰,陈世平,一种基于后缀项表的并行闭频繁项集挖据算法 Kamber M, Pei Jian, et al. Data mining: comcepts and techniques [J].计算机应用研究,2014,31(2):373-377.( Tang yingfeng, LM. Fan Ming, el (l, Iranslaled. 2nd ed. Beijing: China Machine Chen Shiping. Parallel closed frequent itemset mining algorithm with ss,2007:147-154.) postfix-table[ J]. Application Research of Computers, 2014, 31 [2 Agrawal R, Srikant R. Fast algorithms for mining association rules in (2):373-377.)