基于spark的pfpgrowth并行算法优化实现

《基于spark的pfpgrowth并行算法优化实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于Spark的PFPGrowth并行算法优化实现　　基于Spark的PFPGroation(T)和Action(A)。T操作的输入类型是RDD，输出类型也是RDD;A操作的输入类型是RDD，输出类型是一个值或者一个数组。由于对RDD的操作是惰性的，T操作只是表明该操作被请求，而没有对具体的数据进行操作，只有出现了一个A操作以后，数据的读写请求才能真实的在集群上触发。这样的好处就是可以减少T操作的所要存储的中间数据。根据这个特性在编写程序的过程中就需要减少A操作的频率。文献[10]就是在Spark平台实现了频繁项挖掘Apriori算法的并行化，其实验结果也说明了在S

2、park平台上实现并行化算法具有很高的效率。　　1.2FP?Growth算法介绍　　FP?Growth算法将整个数据库的事务进行压缩，该算法不会产生候选项集，采用一种频繁项集增长的方式来进行数据挖掘。该算法从逻辑上可以分为两个部分：第一部分是建树的过程，即把数据库转化为一棵FP?Tree，第二部分就是挖掘的过程，即递归的挖掘这棵FP?Tree，具体的步骤如下所述：　　1.2.1建树　　(1)第一次扫描整个数据库，计算出所有项所出现的次数，找出满足支持度计数的项，并把这些项按支持度计数降序排列，这就是频繁?1项集，记为L。　　(2)第二次扫描数据库，并在每条事务中的项

3、中先删除不满足支持度计数的项，以L中的顺序为大小规则进行降序排列记为d_list。　　(3)建立一个根节点为null的树。　　(4)建立一个表存储节点的信息记为Tab，包括两个属性(项，一个指向节点的指针)。　　(5)将d_list中的每条处理好的事务依次插入这棵树中，构建出该树的一条路径，在插入的过程中，同时用Tab的指针指向对应项的节点。并将每个节点的计数增加1。　　1.2.2挖掘　　(1)从Tab表的尾部的项开始向上遍历FP?Tree，每次遍历得到该项的条件模式基，再根据第一部分将其条件模式基转化为一棵新的FP?Tree以及一个存储表，项与项的计数记为后缀模式

4、。　　(2)如果这棵新的FP?Tree为单分支的结构，就对路径上的项进行组合，并与后缀模式相结合;如果不是单分支的结构就跳转到步骤(1)并合并后缀模式，直到挖掘到根节点(null)。　　FP?Growth算法具体过程如图1所示。　　2IPFP?Growth算法的并行化实现　　2.1IPFP?Growth算法在Spark上的实现　　本文的IPFP?Growth算法建立在PFP?Growth算法的基础之上，采用Scala语言编写，IPFP?Growth算法在Spark上的并行实现整个过程分为4个步骤：　　(1)读取原始数据库将其按频繁?1项集顺序递减排列;　　(2)根据

5、文件大小确定分组个数，按照分组规则将其分为若干组;[1][2][3]>　　(3)对每个组分别进行频繁项挖掘;　　(4)将每个组的结果进行合并。　　算法的整体逻辑图如图2所示。由于原始数据是存储在HDFS中的，超出一个Block大小文件将自动被切分为许多Block，原始分区数s等于文件的总大小/每个Block块的大小+1。　　第(1)步中，先从HDFS获取数据库信息转化为初始RDD，利用RDD的faltMap操作将原本的每条事务合并成一个List集合并通过cache操作保存在内存中以便后期的重用，这样只需要对HDFS上的数据进行一次访问，而原PFP?Gro)进行map

6、操作，转化为键值对的形式，接着用reduceByKey操作来进行词频统计，并按从大到小的顺序进行排序，根据支持度计数剔除不满足的项，得到频繁?1项集。根据频繁?1项集的数目，对cache过的数据进行HashPatition操作，重新分为P个分区(p≥s)，目的是为了增加并行的粒度，采用键值对映射的方式来反映出频繁项之间的大小关系，以此大小关系作为排序规则，用map操作作用在List集合中的每条事务上，同时剔除不满足支持计数的项。　　第(2)步中，首先将每条事务进行最小划分，以图1第一条事务为例，{a，b，c，e}经过第(1)步的处理变为{b，a，c}，其中划分给c组

7、的序列为{b，a，c}，发送给a组的序列为{b，a}，发送给b组的序列为{b}，以这种最小划分的方式来对List中的每一条事务进行划分。明显可以看出三个不同组的挖掘所用的开销是不同的，接下来对每一个小组的挖掘开销进行估计，按照均衡分组的规则再进一步合并，确保每一组挖掘的开销基本相同，最后将所有的分组用Hash的方法放在均衡放在每个patition中，保证每个patition中的组数相同。　　第(3)步中，采用mapPartitions操作分别对每个分区中的的序列采用2.1节中所描述的FP?Gro>t时，各个组的计算量必然不一致，此时并行计算的时间取决于最长