论文研究-基于Spark的并行关联规则挖掘算法研究综述.pdf

所需积分/C币:11 2019-09-07 15:19:10 968KB .PDF
收藏 收藏
举报

关联规则挖掘是数据挖掘的一个重要分支,但随着数据的快速增长,传统关联规则挖掘算法不能很好地适应大数据的要求,需要在分布式、并行计算的平台上寻找突破。Spark是专门为大数据处理而设计的一个适合迭代运算的并行计算模型,相比MapReduce具有更高效、充分利用内存、更适合迭代计算和交互式处理的优点。对已有的基于Spark的并行关联规则挖掘算法进行了分类和综述,并总结了各自的优缺点和适用范围,为下一步的研究提供参考。
刘莉萍,等:基于 Spark的并行关联规则挖掘算法研究综述 2019,55(9)3 Hadoop mapReduce的通用并行框架。相较于 MarE flatMap(.getTransaction()) duce计算框架, Spark具有对数据的处理速度更快、攴持 (Input File)+(Transactions 数据査询功能、支持流式计算模式、支持丰富的数据源 flatMap(. getltems( )) 种类、支持多种语言和可用性较强等优。图1所示 为 Spark的并行任务原理图,由图可看出群集资源由集 Items 群管理器管理,每一个 worker节点包含job,job里面同 Map(it (Item 时对多个Task进行并行计算。 Item Worker node reduce By Key(+) Executor cache Item count Driver Program 第一阶段 Spark Conex Cluster Manager Itemset Count flatMap(. get Candidateltemset()) Executor Cache Candidatc-sct Collect(). buildIlash Tree( TaskTask 图1 Spark并行原理 弹性分布数据集RDD( Resilient distributed dataset Transactions 是Spak的核心,RDD在进行迭代操作时将中间结果存 储在分布式内存中,这样在下一步的数据处理中直接从 内存当中进行提取,减少了大量的1O操作,因此使迭代 map( itemset=>(itemset, 1)) 式算法运行效率得到很大提升。 c <itemset,1> 32并行 Apriori算法 reduce ByKey(+ <Itemset, Count Qu等人在2014年提出了一种经典的基于 Spark 第二阶段 RDD计算模型的并行 Apriori算法: YAFIM。该算法是 图2 YAFIM算法的RDD谱系图 第一个将 Apriori算法移植到 Spark平台实规并行化计 K valu 算的,该算法主要工作分为两个阶段,第一个阶段将数 据集从HDFS加载到 Spark rdd并找出所有频繁1项 集;第二个阶段迭代使用颊繁k项集来生成蜘繁 (k+1)项集,在这个过程中使用了哈希树来存储数据 集。这两个阶段在RDD上进行的操作如图2所示。 1 Y∧FM算法设计思想简单且易于实现,但存在两个明 显缺点:(1)需要多次启动map和 reduce任务进行计数, 图3SAP算法的数据结构 会产生大量的IO消耗:(2)会产生大量的候选项集占(2)使用隆过滤器( Bloom filter代替哈希树Bom 川存储空间,当数据集很大时,会影响算法效率。 Filter数据结构用来存储和检索单项集,比哈希树其有 Yang等人在2015年提出了SIAP算法,通过对更快的速率,因此,当单项集的数目很人时,R- Apriori算 apriori算法所使用的数据结构进行改进,避免了对数据法在时间和空间复杂度上均优于YAM,且R- Apriori 库的重复扫描,在第二阶段提出了一种新的预修剪概作为核心函数的扩展性好。第三阶段是迭代地进行 念,减少了频繁项集产生的数量,从而提升了算法效频繁k项集牛成频繁(k+1)项集过程。其不足是布隆 率。该算法改进之后的数据结构如图3所示。但该算过滤器的误差率,随着数据集的增大而增高,这在·定 法在事务数据维度过高时,存储数据的矩阵会是一个稀程度上会影响算法效率。文献[29所提出的基士 Spark 疏矩阵,就会造成大量的空间浪费现象。 的I- Apriori的改进算法与R- apro算法相似,也是通过 Rathee等人提出了一种新的改进算法R- Apriori,改进布隆过滤器,消除候选集生成,减少数据库扫描次 该算法是在 YAFIM算法基础上进行改进,大大减少了第数对算法进行收进,但算法仍存在额外1O负载的缺点。 二阶段产生候选项集的时间和空间复杂度。R- Apriori Luo等人在2016年提出了一种稀疏布尔矩阵分 算法分为三个阶段第一个阶段获取频繁1项集。第二布式频繁挖掘算法FISM,将事务作为知阵的刎,项集作 个阶段进行了以下改进:(1)去除生成候选集的步骤;为矩阵的行,从而得到一个稀疏布尔矩阵,从矩阵中很 2019,55(9) Computer Engineering and4 pplications计算机工程与应用 睿易得到项集的支持度,之后只需对所有项集进行¨与”来压缩搜索空间,使算法的效率得到提升,该算法所需 运算即可通过频繁廴项集产生频繁〔k+1)项集。虽然节点数随着缴据集的增大而増多,这样对运行环境的硬 FISM算法减少了1O消耗,只需对数据库进行次扫件要求过十苛刻。 描但当项集的数量巨大时项集之间的与”运算量也33并行 FP-growth算法 变得十分大。同样引入矩阵对算法进行改进的还有 FP-growth算法只箭扫描两次数据库,不产生候选 Nu等人提出的 AMRDD算法,通过引入矩阵概念减项集,将所有事务的频繁项集存储在上P-te上,再对树 少扫描事务数据库的次数,同时该算法还应用局部剪枝进行遍历得到频繁项集。Fang等人在2016年提出了 和全局剪枝方法缩减生成候选频繁项集的数量来提升种基于 Spark的女进 FP-growth并行算法IPP 算法效率。Iu等人提出的基于Sprk的 Apriori改进 growth,实现了将改进的PFP- growth算法移植到 算法( Spark+ aPriori)也是通过类似的方法,对数据的 Spark计算模型上进行分布式计算。该算法主要分为4 存储结构进行优化来进步提升算法的效率其算法流个步骤,第一步从HDFS获取原始信息并转化为RDD 程图如图4所示。文献3的DMA的算法和文献4并通过基于 Spark l的系列算子计算获得频繁项集的 38的改进算法,都是通过转换存情结构、消除候进集的递减排序;第二步根据获取文件的大小确定分组个数 产生来提升效率,但也都存在稀疏矩阵、计算量大占用按照均衡分组的规则将其分为岩干组第二步分别对每 内存的问题。 个组进行频繁项集挖掘;第四步将每个组得到的结果合 并得到最终结果。图5展小了 IPFP-growth算法的实现 开始) 步骤,但由于没有改变数据的存储结构,在迭代过程中 事务数据库 会产生大量条件FP-Tree存储在内存中,内存开销将随 数据増加而增大。 block1 block2 block3 map Par apparition appArition 本地频繁项集本地频繁项集|本地频繁项集 HDFS CResulthHDESE 仝局候选项集 选项集传送给每个节点 统计全局支持度 步第二步第三步第四步 全局频繁项集 图5 IPFP-growth算法步骤 Zhang等人提出了·种基于事务屮项间联通权重 图4 Spark+ aPriori算法流程图 矩阵的负载平衡并行颎繁模式増长算法 CWBPFP,该算 法通过融合联通权重矩阵和被约束子树的方法应用到 Krishan等人提出一种使用垂直数据集格式来减 Spark每一个工作节点的FP-tree挖掘过程,从而提升了 少扫描数据库的时间和产生候选集数量的算法 HFIM, FP-growth算法的性能但是该算法没有充分考虑到均 垂直数据的格式是 item/itemset列装后跟其事务ID,垂衡分组的问题,存在空间和时间浪费现象 直数据集提供的优点是不需要在莓次迭代屮扫描整个 焦润海等人叫提出了一种针对高维数据样本的改 数据集。垂直数据集携带足够的信息以生成可能的候进频繁项集挖掘算法SMHl,该算法通过结合DMHA算 选集并计算其支持度计数。在垂直数据的每个记录中 法的双向搜索策略和 Spark分布式框架的并行化思想, ID被按升序排列,这使得支持度计算更容易。可以通对深度路径搜索和长度优先检验进行改进,提高了高维 过简单地交叉(k-1)项集的TID来计算对k候选项集数据挖掘的效率。SMHl算法主要解决了DMHA算法 的支持度,但同时会造成计算量过大和占用内存过多的中存在的三个问题:第一个是当数据量较大时,采用划 问题。 分投影,形成并行分区侯选子集,这种投影能够避免不 王青等人在2016年提出了一种基丁 Spark的优同节点之间的数据通信,也减少了分区中子记录的重复 化算法 SP-Apriori,该算法在挖掘过程中利用频数表示率,诚少∫内存占用。第一个问题就是对于高维数据在 支持度,利用组合策略得到总的规则类别来获取各项集形成最大频繁候选项集吋,采用生成由频繁1项集组成 Ky,再利用 Apriori算法的先验性质去掉多余项集Kky的频繁项树,再对每个分区的频繁项树进行深度路径递 刘莉萍,等:基于 Spark的并行关联规则挖掘算法研究综述 2019,55(9) 归搜索,得到分区最大频繁候选项集。第三个问题是循 环中超集检验是在最大频繁侯选项集直接操作,采用先 分细,,分组2,,分组3 前缀序号后长度的方法,进行升序排序,然后自上而下、 由短及长进行超集检验,最后剩余侯选集就是最大频繁 /FP-Trec模/ 项集该算法山于需要重复检验,时间复杂度和冗余度 较高。 计算量 邵梁等人提了一种 FP-growth垂直频繁项集挖 掘算法,简称FP-ⅤFIM算法,该算法使用了数据集垂直 LL 布局的概念,诚少了每次迭代过程扫描数据集的时间 项在F-List中的位置 并且垂直数据可通过交又(k工个项集的TID就可以 未优化分组策略 计算k候选项集的支持度。算法主要分为两个步骤:步 骤1主要通过 Spark的fame0和mm0等函数在垂直 LI 分组2 分组3 数据格式上生成频繁1项集,步骤2是通过迭代方式生 成频繁k项集,这个过程使用了Spak的广播变量与执 行者共享,减少了IO消耗和憾盘空间,图6为 FP-VFIM 算法的基本流程。 算遠 步骤1 读取数据) 步骤2 计算项集的支持度 nm数1成项」「生成N基数的潜在候选项集 项在F-List中的位置 优化后分组策略 mm最生成项[获锝k-1基数的所有子柴」 图7分纠优化策略小意图 繁模式树中加入了链头表,在F-tre中进行迭代挖掘 构建垂直项集 将子集中相同事务存储到列表 common 时所产生的内存也随之增大,是下一步需要研究的问 FP-Growth算法筛选频紫 min sup和列表 common的长度 题。 Gassama等人提出的S-FPG算法通过改变数据结 项集 比较 构形式和减少迭代生成频繁项集的数量在 Spark平台上 获得垂直布局频繁1项集生成N基数的潜在候选项集 实现并行计算,但仍然没有减少对内存的需求。 Zhang 图6FPⅤIM算法流程 等人四提出的算法 DFIMA通过一种基于矩阵的修剪方 法,减少候选集的产生,结合 Spark平台实现并行运算 顾军华等人甽在2018年提出了一种新的并行但该算法没有对数据存储格式进行深入研究。陆可等 上( Growth算法BFPG,该算法基 J Spark平台,通过对人通过对 FP-growth算法的支持度计数和分组进行优 频繁模式树规模大小和分区计算量的F-Lit分组策暗化来提升挖掘效率,由丁迭代计算的运行结果都保在 进行改进,将负载总和均分到每个分区,再通过创建列内存中,无法满足海量数据的需求 表PLs对数据集划分策略进行优化,达到减少扫描数34并行 Eclat算法 据库的次薮来降低时间复杂度。频繁项集的并行挖掘 Apriori算法秈FP- growth算法处理的事务数据格式 时间取决于最后一个分区的完成时间,因此在进行分组 是水平格式,而 Eclat算法不一样,是垂直格式的。冯兴 时要尽量使每个分区完成的时间相等,BFPG算法对杰等人叫提出来一种基于 Spark的并行Eca算法即 于分组的优化策略采用了两个衡量公式Can=sPca,通过变数据存储方式,并将数据按前缀进行 lg(L(lmyF-lal)和S= iie.supx(emnx+1)/2,从分组划分到不同的计算节点,压缩数据的搜索空间,实 FP-Tre的横向和纵向维度来综合考虑时间复杂度和空现并行化计算。该算法主要分为三个阶段来完成并行 间复杂度,图7为分组策略优化的示意图。 计算,第一个阶段读取数据并保存,获取频繁1项集。 石陆魁等人‘提出的RPP算法改进思想与BFPG传统的 Eclat算法将事务以( Itemset, Tinsel)形式储, 算法类似在均侮分组和降低时间复杂度两个方面来对但当数据集庞大时, TidSet的求交集操作会耗费大量时 算法进行改进。不同的是RP算法是基于PP间,因此该算法将数据以( tem set, BitSet)的方式存储, Growth算法的基础上加入了均衡分组优化算法和对链支持度的计数变为 Bitset求与运算,避免了大数据量的 头表结构算法进行了优化并加入张哈希表达到快速计算。第二阶段迭代式地对得到的频繁项集按前缀进 访问元素地址,从而降低∫时间复杂度,但也由于在频行划分,分发到不同的计算节点。第三阶段将每个计算 6 2019,55(9) Computer Engineering and4 pplications计算机工程与应用 节点中具有相同前缓的项集,以自底向上的形式并行地 进行迭代,用频繁k项集产生频繁(k+1)项集,最后 度为(2b+c) 2=O(6+)1),而 APriori算 将得到的频繁(k+1)项集进行再划分,迭代调用SP法的空间复杂度总和为在布隆过滤器中存储频繁单项 clat算法挖掘频繁顼集,直到不再产生频繁项为止。但集所占的空间,以看出比YAFM算法的空间复杂度要 该算法在则分到不同计算节点时投有均衡则分会造成)低很多。同样的对ABS算法进行分析得到总的时间复 内存占用的现象。 杂度为((+ 7x2(81),空间复杂度为,可以 35并行算法的效率分析对比 M ? 35.1并行算法时间和空间复杂度分析 看出lABS算法的时间复杂度秈空间复杂度均比 并行计算模型主要是解决关联挖掘算法迭代过程 YAFIM的要低。I- Apriori算法的时间复杂度总和为 有典型代表性的算法的效进行分析科比较为后线少 的时间复杂度租空间复杂度过高的问题,通过对以上具 O(+X/M2),空间复杂度总和为 法改进提供参考在Spak计算框架中 Reduce F中行 O(f)。 输入输出的时间与传统关联挖掘算法的输入输出时间 对于并行FP- Growth算法,设含有的项集数量为 是一样的,在 mapper中,需要进行分析假没是事务k,最大事务中含有的项的数量为m。FVFM算法步 个数,M是mp任务的个数,“为每个事务的平均数骤1的时间复杂度为扫描事务数据库一次并访问每个 量,f为频繁1项集的个数,是在哈希树中搜索一个项以构建垂直布局所需的时间,所有k个项均会经历 FP- Growth步骤,所以该过程最坏情况下的复杂度为 元素的时间,是在布隆过滤器中搜索一个元素的时 O(Xm+k),步骤2是一个选代过程,在第次迭代过程 间。对于 Apriori算法,第二步迭代的总时间为生成候 中扫描频繁项集中的所有事务并创建项列表,再从项 选集的时间、存储候选集的时间和映射器所用时间的总 和,其中生成候选集的时间为连接的时间和剪枝的时间 列表中生成潜在的候选集,进一步访问每个候选集并 创建(-1)的子集列表,所需最大时间复杂度为OF 的总和。对于 YAFIM算法,生成候选集的时间为 (-1).2/(-1)3/(/-1) 1x7X0),中F为频繁项集的事务数量,v为 ,在哈希树中存储候选 share data中项集的数量,c为 share data中项集TID的 最大计数, FP-VFIN算法的总时间复杂度为这两个步骤 集的时间为20(),映射器所川时间为的时间复杂度之和。其空间复杂度为OFxm+2+ Xx(g-1=OM2),所以YAM的时间复++0×。对于 SPEclat算法,虽然数据格式为垂直 2 l) g2|。对于R- Apriori算法来说 样的方法, SPEclat算法时间复杂度为三个阶段时间 总的时间一你储频繁1项集到布降过滤器的时间+枝复杂度的总和为O+-M“6) 的时间+生成项集对的时间,即:+个x lg(g 352算法总体介析对比 关联规则挖掘算法的改进主要是对原始数据集格 O(+x4g)。YAM算法的时间复杂度减去R式算法使用的数据结构挖据过程中产生候选项集的 数量以及挖掘过程扫描数据库的次数等方面进行优 Apriori算法的时间复杂度等于Oz(-1g2 化。以上各类并行算法之间的比较见表1,结合上一节 由此可以看出 R-Apriori算法的时间复杂度要比YAEM中对各类并行算法的时间复杂度和空间复杂度的分析, 算法的时间复杂度低。再看两者的空间复杂度,同样在并行 Apriori算法中,除 R-Apriori算法在挖掘过程不 Reduce对于算法的输入输出是·样的,主要是 mapper产生候选集其他算法均会产生候选集,且 R-Apriori算 占用的空间不一样, Apriori算法的空间复杂度主要是存法的时间复杂度和空间复杂度也优于其他并行 Apriori 储侯选项集和建立存储侯选项集的数据结构所占用的算法,由此可以得到减少生成候选集的数量一定程度上 空间的总和,设b和c分别为存储一对候选集和单个项可以提高关联规则挖掘算法效率。SIAP算法和HFIM 集所占的空间。 YAFIMA算法中储侯选项集的空间算法使用了水平和垂直两种数据格式,在生成频繁1项 集的阶段减少了算法的时间复杂度和空间复杂度,由于 为∽≈O(),创建哈看树的空间复杂度为在生成关联规则的时候没有减少生成侯选项集的数量 bf(f-1)of(-1) 因此算法整体复杂度比R- Apriori算法高,但比 YAFIM O(b+c)/),所以总的空间复算法要低。在使用的数据结构方面 R-Apriori算法使用 刘莉萍,等:基于 Spark的并行关联规则挖掘算法研究综述 2019,55(9) 表1各类并行算法的比较 变体类型 算法名称数据格式使用的数据结构是否产生候选集扫描数据库次数 YAFIM 水平 哈希树 SIAP 水平、垂 布尔矩阵 R-Apriori 水平 布隆过滤器 ISM 水平 布尔矩阵 并行Apo算法 AMRDD 水平 布尔矩阵 水平 布尔矩阵 HFIM 水平、垂直 无 水平 分布矩阵 DPBM 水平 在尔矩阵 IPF 水平 哈希树 CWBPFP 水平 FP-trc SMFI 水平 树 并行 FP-Growth算法 FP-VFIM垂直水平 BFPG ●水平 FP-tree 是是否是是是是是是否否是是是是是是 ≤ RPFP 水平哈希表、FP-trcc S-FPG 水平 222 FP-tree 并行Fc SPEclat 垂直 分布矩阵 ≥3 的是布隆过滤器, SIAP FISM、 AMRDD、 Spark+^ prior、4总结与展望 SP-Apriori、DPBM等算法使用的是矩阵,YAFM使用的 随着数据量的增长,关联规则传统挖掘算法已经无 是哈希树,HFIM使用的原始数据结构,同等情况下,使法满足要求,需要可以并行、分布运算的关联规则挖掘 用了特殊数据结构的算法在生成频繁k项集阶段比没算法来解决。 Spark是专门为解决大数据的计算问题而 有使用特殊数据结构的算法在时间和空间复杂度上均有设计的,适合迭代运算并被广泛运用到关联规则挖掘领 明显优势,在使用了特殊数据结构的算法中,R- Apriori域。本文所研究的频繁模式挖掘算法主要通过以下几 算法使用的布隆过滤器比其他算法使用的布尔矩阵更种方法进行改进:(1)改变数据结构加快频繁项集搜索 有优势,是因为布隆过滤器可以表示全集,而其他任何速度;(2)减少候选项集的数量;(3)优化均衡分组,实现 数据结构都不能,所以在时间和空间方面更具有优势。计算负载均衡;(4)减少1O通信量和存储占用。 使用特姝数据结构的算法在扫描数据库次数方面都少 本文研究的算法都是经典关联规则算法向 Spark平 于k次,甚至只需扫描一次数据库,明显减少了内仵占台进行∫迁移,但随着数据量的扩展,产生的关联规则 用和扌描数据库的时间。在并行 FP-Growth算法中,由也随之增多,因此在未来的研究工作重点可能主要在以 于IP- Growth算法本身只需扫描数据库两次,因此算法下方闻: 效率均比 Apriori算法好。IFP- growth和 CWBPFP算 (1)Spak平台是基丁内存的运算,没有大量的O 法不产生倏选集,在迭代计算时优于其他同类算法,消耗,但由于现实中的数据集日益增大,其增长的速度 SMFI和RPFP算法使用了特殊数据结构,使算法在迭代远远超过内存容量的发展速度,而关联规则挖掘的过程 的挖掘频繁模式阶段具有更高的效率。 FP-VFIM算法并不是一步计算就可以得到结果,需要在原始数据集中 是唯一使用了垂直数据格式的算法,在查找频繁项集过不断地搜索并计算得出关联规则,在挖掘过程中需要的 程比同类算法更具有优势 内存比原始数据更大,当达到内存最大时并行计算就会 并行关联规则算法在Spak平台的实现使用的是H现数据丢失和需要重复搜索的问题。囚此,解决数据 基于key- value的存储系统,其查询速度快、存放数据量大小与计算机内存大小之间的关系是未来的研究方向 大、支持高并发,但不能进行复杂的条件查询。因此,之·。对原始数据进行压缩处理可以有效解决,因此数 关联规则挖掘算法使用的数据结构存储对挖掘效率的据压缩技术是未来硏究的热点方向。 影响非常重要,当事务的数量越来越庞大时,垂直数据 (2)信息时代新数据每时每刻都在增加,因此关联 格式更能显示出优势。生成侯选集的数量主要占用内规则挖掘算法所得到的结果也要史新,因此,算法的方 存,会影响算法空间复杂度扫描数据库次数会影响算法也要随着数据的更新有所改进。并行关联规则的挖 法时间复杂度。因此在改进算法时需要允分同时考虑掘计算主要在内存上进行,若每当有新数据加入时需要 这几个因素,结合现实数据结构特点,找到最优的解决重新开始计算则会造成很大的内存损失,因此设计处理 新旧数据之间变化问题的高性能新算法,是未来亟需攻 2019,55(9) Computer Engineering and4 pplications计算机工程与应用 克的难关之 synthesis framework for applying parallelizing compiler (3)算法的设计仍然是关联规则挖挺最重要的部 transformations(CI/nternational Conterence on 分,分布式运行算法如何达到最优需要考虑各个节点的 Design, 2003 运行情况,无论在时间或者空间复杂度上如何将算法改13 Pan Yanyan. a study and analysis of DHP algorithm 为最优或者局部最优算法是一直需要研究的方向。此 for association rules[]Journal of Foshan Universit 外,除了基本模式的挖掘算法研究,多层和多维模式的 2012(2) 挖掘算法也需要在并行化平台实现,结构模式、空间模 [14] Dai X, Gretsch R Quasi-synchronous sampling algorithm 式、图像、视颎、多媒体和网络模式等数据类型的关联挖 and its applications[].IEFF Transactions on Instrumen tation and Measurement, 1994, 43(2): 204-209 掘均是下一步需要研究的内容 [15 Vyawhare R, Mandape PImplementation of dic using association rule mining algorithm[]. International Journal 参考文献: of Engineering Sciences Research Technology, 2015 [J Witten I HData miningLMJ. Bcijing: China Machine Press 4(3) [16 Laszlo M, Mukherjee S Minimum spanning tree parti [2 Han J, Kamber M Data mining: concepts -and techniques[M/ tioning algorithm for microaggregation[J]IEEE Transac Data mining concepts models mcthods algorithms tions on Knowledge Data Engineering, 2005, 17(7): 2nd Ed.San Francisco, CA, USA: Morgan Kaufmann Pub 902911 fishers Inc. 2005 [7 Rashedi E, Nezamabadi-Pour H, Saryazdi SGSA: a [31 Zhang C, Zhang SAssociation rule mining[MViAssociation gravitational search algorithm[M][SL ]: Elsevier Science ule mining [S1: Springer, 2002: 193-203 inc,2009. Toivonen H Apriori algorithm[ ] Encyclopedia of Machine [18 Trelftz C. Santamaria -Galvis A, Cruz R Parallelizing an Learning, 2011: 39-40 algorithm to find the maximal clique on interval graphs 5 Vo B, Le B.A novel classilication algorithm based on graphical processing units[ C] /2014 IEEE Interna on association rules mining[M]/Knowledge acquisition Lional Conference on ElecTro/Information Technology approaches, algorithms and applications, Berlin Heidelberg (FIT),2014 Springer, 2009 [19]Tomita L, Seki T An efficient branch-and-bound algo [6 Chakaravarthy V T, Pandit v, Sabharwal Y Analysis of rithIn for linding a maximum clique[C]//Proc Interna- sainpling techniques for associalion rule mining[C]/ Inter tional Conference on Discrete mathematics theoretical national Conference on Database Theory (ICDT 2009) Computer Science, 2003 St Petersburg, Russia, March 23-25, 2009: 276-283 20] Trieu T A, Kunieda Y An improvement for dEclat algo [7 Han J, Pei J, Yin Y Mining frequent patterns without rithm[c/International Conference on Ubiquitous Infor candidate generation[C]pRoceedings of the 2000 ACM Imation Managenent Connunication, 2012 SIGMOD International Conference on Management of[21]孟晨,曹宗雁,王龙,等基于 Charm++运行环境的异构计算 Data,2000:1-12 应用容错研究「计算机工程与应用,2016,52(13):1-7 [8] Niu X 7. She K Mining maximal frequent item scts with [22] Janez Konc E A.An improved branch and bound algo improved algorithm of FPMAX[J]. Computer Science rithm for the maximum clique problem[J]. Match Com 2013.40(12):223-228 mun in Mathematical in Computer Chemistry, 2007 [9] Song Changxin. Research on the improved eclat data 58(3):569-590. mining algorithn[J]. Microcomputer Inlormation, 2008(24) 3 Barnes .High integrity software, the SPARK approach [10 Ye x, Wei F, Jiang F,et al. An optimization to CHARM to safety and security M . Boston, MA, USA: Addison algorithm for mining frequent closed itemsets[C]/IlED Wesley Longnan Publishing Co, Inc, 2003 International Conference on Computer and Information[24]吴信东,嵇圣硙 Mapreduce与 Spark用于大数据分析之 Technology; Ubiquitous Computing and Communications 比较软件学报,2018,29(6):1770-1791 Dependable, Autonomic and Secure Computing: Perva- [25] Joy R, Sherly KKParallel frequent itemset mining sive Intelligence and Computing, 2015: 226-235 spark RDD framework for discasc prediction(C./ [Il Taylor R C. An overview of the Hadoop/ Mapreduce International Conference on circuit, 2016 HBase framework and its current applications in bioin- [26] Qiu H, Gu R, Yuan C, et aL. YAFIM: a parallel frequent formatics[J]. Bmc Bioinformatics, 2010, 11(S12): itemset mining algorithm with Spark[C1//Parallel [12] Gupta S, Dutt N, Gupta R, et al.SPARK: a high-level Dislributed Processing SyMposium Workshops, 2014 刘莉萍,等:基于 Spark的并行关联规则挖掘算法研究综述 2019,55(9) [27] Yang S, Xu G, Wang Z, et al. The parallel improved problem as an example[C]/International Conference on Apriori algorithm research based on Spark[C]/Ninth Advances in Computing, 2016 International Conference on Frontier of Computer 391 Krishan K S, Dharavath R. HFIM: a Spark-based hybrid Science Technology, 2015 frequent iteMset mining algorithIn for big data process [28 Rathee S, Kaul M, Kashyap AR Apriori: an efficient ing[]Journal of Supercomputing, 2017, 73: 1-17 Apriori based algorithm on Spark[C] /Workshop on PH山D[40]王青,谭良,杨显华基于 Spark的Apo并行算法优化 Workshop in Information Knowledge Management 实现[郑州人学学报(理学版),2016,48(4):60-64 [41 Fang Xiang, Zhang Gongxuan. Optimization of parallel 129 Li Qingpeng. Zhang Longjun, Geng Xinyuan. l-Apriori: an FP-Growth algorithm based on Spark J Moden Elec improved Apriori algorithm based on Spark platform[] tronics Technique, 2016(8) Science Technology Engineering, 2017(27) [42] Li l, Wang Y, Zhang D, et al. Pfp: parallel fp-growth [30] Luo Y. Yang,Z, Shi H, et al. a distributed fr Cor query recommendation[C]/ACM Co unlerence on rec itemsets mining algorithm using sparse Boolean matrix ommender Systems, 2008 107-114 on Spark[C]/Asia-Pacific Web Conference. 2016 43 Zhang Wen, Luo Ke. A parallel FP-Growth mining algo- [31]Niu H, Lu H, Liu Z The improvement and research of onSparkframework[j].computerEngi- Apriori algorithm based on Spark J]Journal of north- nccring Sciencc, 2017(8 east Normal University, 2016(1 [44]焦润海,张谦,陈超基于 Spark改进的最大频繁项集挖掘 [32] Lu Y, Dong 7cngshou An improved algorithm of asso 算法[]计算机工程与设计,2017,38(7):1839-1843 iation rules based on the Spark[J] Application of Elec-[45]邵梁,何星舟,尚俊娜.基于 Spark框架的 FP-Growth大数 tronic Technique, 2017(6) 据频繁项集挖掘算法[J.计算机应用硏究,2018,35(10) [33 Song Wenlin, Xu Huimin. Improvement of DMfIa algo- 2932-2935 rithrn based on mining of maximal frequent iteIn sequence[46]顾军华,武君艳,许馨匀,等.基于Spak的并行 FP-Growth sets[J]. Computer Engineering Design, 2007(7) 算法优化及实现[]计算机应用,2018,38(11):3069- [34 Feng F, Cho J, Pedrycz W, et al. Soft set based association 3074 rule mining[ J]. Knowledge- Based Systems,2016,11:[47]石陆魁,张欣,师胜利基于 Spark的FP( Growth算法的并 268-282 行与优化[门计算机工程与应用,2018,5413):52-58 [35]王雯,赵衎衎,李翠平,等 Spark平台下的短文本特征48] Gassama d, Camara h, Ndiaye S.s-hPG: a parallel 扩展与分类研究[计算机科学与探索,2017,11(5): version of FP-Growth algorithm under Apache Spark [C/ 732-741 IEEE International Conference on Cloud Computing [36 Dharavath R, Raj S QuanLitative analysis of frequent Big Dala Analysis, 2017. itemsets using Apriori algorithm on apache spark [49 7.hang F, Liu M, Gui F, et al. a distributed frequent framework[C]//Proceedings of the International Confer- Itemset mining algorithm using spark for big data ana ence on Computational Intelligence in Data Mining lytics[J]. Cluster Computing, 2015, 18(4): 1493-1501 2017:261-272 「50陆可,桂伟,江雨燕,等.基于 Spark并行 FP-Growth [37]曹博,倪建成,李淋淋,等.基」 Spark的并行頻繁模式挖 算法优化与实现[J计算机应用与软件,2017,34(9) 掘算法[计算机工程与应用,2016,52(20):86-91 273-278 [38] Rathee s, Kashyap A Exploiting apache Flink’ s iteration[51]冯兴杰,潘轩.基于 Spark的并行 Eclat算法[.计算机应 capabilities for distributed Apriori: community detection 用研究,2019(1).

...展开详情
试读 9P 论文研究-基于Spark的并行关联规则挖掘算法研究综述.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于Spark的并行关联规则挖掘算法研究综述.pdf 11积分/C币 立即下载
    1/9
    论文研究-基于Spark的并行关联规则挖掘算法研究综述.pdf第1页
    论文研究-基于Spark的并行关联规则挖掘算法研究综述.pdf第2页
    论文研究-基于Spark的并行关联规则挖掘算法研究综述.pdf第3页

    试读已结束,剩余6页未读...

    11积分/C币 立即下载 >