大数据模式挖掘的并行分布式技术研究及应用

沙特国王大学学报基于大数据的并行分布式模式挖掘Sunil Kumar，Krishna Kumar Mohbey印度阿杰梅尔拉贾斯坦邦中央大学计算机科学系阿提奇莱因福奥文章历史记录：收到2019年2019年8月20日修订2019年9月13日接受在线预订2019年保留字：大数据管理系统不确定数据挖掘A B S T R A C T模式挖掘是数据挖掘的一项基本技术，旨在发现数据集中有趣的相关性模式挖掘有几种变体，如频繁项集挖掘、序列挖掘和高效用项集挖掘。高效用项集挖掘是一个新兴的数据科学任务，旨在提取基于领域目标的知识。模式的效用显示了它的有效性或好处，可以根据用户优先级和特定领域的理解来计算。序列模式挖掘（SPM）的问题是很多研究和扩展在各个方向。序列模式挖掘枚举序列数据集合中的序列模式。不确定事务数据集上的频繁模式挖掘是近年来的研究热点近年来，基于Apache Hadoop和Spark框架的大数据项集挖掘受到了广泛关注。本文旨在对大数据领域中模式挖掘的不同方法进行广泛的概述。首先，我们研究了模式挖掘方法和相关技术（如Apache Hadoop，Apache Spark，并行和分布式处理）所涉及的问题。然后，我们研究了并行，分布式和可扩展的模式挖掘的主要发展，在大数据的角度分析它们，并确定在设计算法的困难。我们特别研究了四种项目集挖掘，即，并行频繁项集挖掘、高效用项集挖掘、序列模式挖掘和不确定数据中的频繁项集挖掘。本文最后讨论了开放的问题和机会。它还为进一步加强现有方法提供了方向©2019作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍挖掘有用的模式在许多实际应用中具有重要意义。（Chen等人，1996; Anastasiu 等 人 ， 2014;Aggarwal 等 人 ， 2009; Tsai 等 人（2013）。在过去的几十年里，人们研究了各种模式挖掘方法，如频繁模式挖掘（FPM）、序列模式挖掘（SPM）和高效用项集挖掘（HUIM）。这些都是重要的和基本的采矿方法，满足现实世界的需求，在许多领域。获得的模式可以用于市场篮子分析，决策辅助，交叉营销和销售，目录设计，医疗等。频繁项集挖掘是沙特国王大学负责同行审查制作和主办：Elsevier电 子 邮 件 地 址 ： gmail.com （ S.Kumar ） ， kmohbey@gmail.com（K.K.Mohbey）在许多实际应用中是相当有益的（Aggarwal等人，2009; Agrawal等人， 1993）然而，该方法具有某些局限性（Uno等人，2004;Shen等人，2002），考虑到不考虑采购数量的事实，具有明显效用和重要性的项目被认为是等同的。为了解决这种对数据集的限制，已经开发了高效用项集挖掘方法来检测数据集中的高效用项集（Lin等人，2011; Lin等人，2015; Liu和Qu，2012; Liu等人， 2005年）。效用挖掘的目标是发现具有高效用的模式，其中模式的效用以基于所使用的在我们的日常生活中，序列以有序的项目列表的形式到处都是例如DNA序列、Web访问日志等。序列模式挖掘（SPM）从事件序列或时间序列项中检测和分析统计上显著的子序列 SPM具有广泛的应用范围，包括购物篮分析（Agrawal和Srikant，1995）、Web挖掘（Boggan和Pressel，2007）、生物信息学（Ayres等人， 2002年）等。模式挖掘通常是但在许多现实生活中的系统中，数据可能充满不确定性（Wang等人，2 0 1 0 ; Calders等人， 2010年）。https://doi.org/10.1016/j.jksuci.2019.09.0061319-1578/©2019作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com1640S. 库马尔Mohbey/ Journal of King Saud University不确定性是由于采样误差、固有的不准确测量、过时的源、网络带宽限制和延迟以及有限的硬件能力造成的。不确定性可以用存在概率来描述。近年来，从不确定数据中提取数据已经成为令人兴奋的研究问题（Tong等人，2012;Chui等人，2007年）。模式挖掘（即模式挖掘、HUIM和SPM）在过去的两个世纪里在各个领域得到了广泛的研究和成功的应用。在大数据背景下，并行和分布式数据挖掘在近几十年来获得了极大的关注，以满足对大规模和高效率计算的需求（Wang等人，2010;Tsai等人，2015; Apiletti等人，2015），包括并行频繁模式挖掘（Salah等人，2017;Zaki，2001）PSPM（Leung等人，2013;Uno等人，2004; Fournier-Viger等人， 2017）等等。大数据可以在不同的来源中找到，如点击流、电子商务应用程序、购物记录、银行交易、社交网络、网络服务、生物科学、联网设 备 和 传 感 器 。 这 导 致 了 数 据 处 理 范 式 的 转 变 （ Masih 和Tanwani，2014）。传统的数据处理方法无法及时、经济有效地处理和分析大数据。近年来，为了提高数据挖掘技术的效率，已经进行了大量的工作，例如基于中心的算法的并行化数据量和分布式数据站点的指数级增长提高了对分布式知识挖掘的需求。 分布式数据挖掘方法已用于各种分布式计算范例，例如对等点，网格，集群和云环境（Chang，2018;Jeon等人，2018年）。多处理器上的并行算法和网络算法的并行实现有几种并行编程框架。OpensMP和MPI（Mpi，1994）用于并行化分布式和共享存储。网格允许访问远程资源和数据的分布式存储位置，进行大规模数据处理。网格可以为分布式数据挖掘应用提供有效的计算辅助。集群作为一个处理资源运行，并与高速网络连接集群是完美的问题，需要执行类似的要求，在数据挖掘。2004年，Google推出了Map Reduce。 在并行和分布式系统MapReduce（Bendechache等人， 2018）已成为大规模挖矿最常见的平台。MapReduce可用于CPU、GPU、GRID和多核设备上的云。许多其他大规模数据处理系统也被开发出来，以提高水平可扩展性，简化API。Spark（Djenouri等人，2019）提供交互式和迭代计算。代替map/reduce，Dryad（Masek等人，2015）提供了对通信和用户定义任务的良好控制。 在大数据应用中，NoSQL（不仅仅是SQL）数据库，如Cassandra（Espejo等人， 2009）和MongoDB（Cano和Ventura，2014）提供了可扩展性，无模式和一致性。对于数据处理，要么只使用SQL语言，要么使用Hive等执行引擎（Li et al.， 2013）或从诸如执行单元和像Dremel（Cano等人，2015年）。流数据处理和机器学习（ML）问题等特定领域的问题已经扩展到大型ML系统，因为可扩展性和效率是瓶颈之一以图形为 中 心 的GraphLab （ Cano 等 人 ， 2011 ） 和 ML 中 心 Petuum（Benatia等人，2016）是代表性的ML系统。S4（Chiu等人，2011）和Storm（Athanasopoulos等人， 2011）提供流/实时数据处 理 ， 例 如 ， 搜 索 引 擎 查 询 ， 社 交 网 络 分 析 和 Twitter 推 文（Chang，2018）。介绍了对基本MapReduce的扩展，包括不同的数据流支持，数据访问优化，因为MapReduce可能无法有效地进行数 据 解 析 ， 自 动 参 数 调 整 扩 展， 因 为有 几 个 参 数 必 须 转 换 为MapReduce和通信优化。此外，Dryad、Nephele/PACT和Spark是其他流行的批处理系统，它们使用MapReduce的概念进行一般处理，但具有强大的数据流和灵活的编程模型（Zhang等人， 2016年）。Dryad是微软提出的一种Scope、DryadLINQ、Apache Tez和Apache Hama是使用Dryad作为执行引擎的其他项目。Spark是一个集群计算框架，提供迭代的并行处理（Gonzalez-Lopez et al.，2018年）。 Spark的目标是统一，开发用于各种应用的系统，具有用于数据流执行、图形处理、机器学习等的单独库。实时应用，例如查询处理和社交网络（Zhang et al.，2016年），要求具有高带宽的可扩展流处理系统最近，GPU已经转向主要使用技术来加速整体执行。它们提供了大量的并行性，以处理大规模数据（Cano，2018）。该模型提供了数据级并行性，可以有效地处理数百万个线程，从而允许算法扩展到大量数据。GPUMapReduce将计算机节点添加到系统中，并在其上分配负载由于深度学习算法的高性能，它吸引了大量的研究。深度学习模型在处理大规模模型和大数据集时内存效率很差，这个约束可以通过在GPU和MapReduce上实现深度学习云计算可以利用虚拟资源进行高计算量和高数据敏感性的评估各种MapReduce知识挖掘算法已经在虚拟化云资源上实现（Chang，2017; Sharma等人， 2019年）。最近，分布式GraphLab和pipsCloud（Wang等人， 2018）框架，以有效地支持云计算中的许多重要的知识挖掘算法。GrphLab是一个图形扩展，具有故障恢复能力，并减少了网络的拥塞（Stuart和Owens，2011）。pipsCloud使用云服务实现大规模遥感数据处理在本文中，我们调查的最新进展，在解决的困难，开发分布式和并行技术挖掘模式。在第2节中，我们将介绍模式挖掘问题及其专业化。然后，我们在第3节中描述了大数据处理范式，包括分布式和并行处理。在第4节中，解释了用于方法比较的各种标准。在第5节中，我们调查现有的并行和分布式模式挖掘方法。第6节结束了关于挑战和研究机会的讨论。第7节讨论了前景广阔的未来方向。最后，第8节得出了一些关于大数据中高效用模式挖掘领域的最新技术和进一步机会的结论。2. 模式挖掘方法本节介绍了各种模式挖掘方法，包括XML、HUIM、不确定挖掘和SPM。它还包括用于模式挖掘方法的数据库。2.1. 频繁项集挖掘数据挖掘的主要目标是基于频率从巨大的数据集中探索数据和发现特征，即，如果一个事件或若干现象在记录中经常发生，则根据S. 库马尔Mohbey/ Journal of King Saud University1641.- 是 的- 是 的ΣXð Þ ð Þ ð Þ ××ð Þþð Þþð ÞQp顾客用更正式的术语来说，让我成为一组项目。数据集D包括{ti，. . ，tn}记录。每个事务tq2D由一个项目集合组成（即，tq I），其由事务标识符（tid）识别。事务性数据集实例，表1和表2中显示了4个事务，其中包含项集的计算支持。频繁项集挖掘的目标是发现高支持度的项集。一个项集是一个有限项的集合，使得X≠ I。项集的支持描述如下。定义1（（支持）：）。在事务数据库D中，项目集X的支持度被称为sup（X），定义为D中包含X的事务与D中所有事务的比率例如，在表2中，项集a，c>的支持度为2。表4效用表。表3数据集。T-ID项目：数量T1（i1， 1）;（i3， 3）;（i4， 4）T2（i2， 1）;（i3， 1）;（i4， 2）T3（i1， 2）;（i2， 2）;（i5， 3）T4（i3， 2）;（i5， 2）T5（i1， 1）;（i3， 2）;（i4， 1）T6（i1， 3）;（i3， 1）;（i4， 3）;（i5， 4）T7（i2， 1）;（i3， 4）;（i5， 1）T8（i2， 3）;（i4， 4）定义2（（Frequent itemset）：）。如果sup（X）不低于用户（即，e. sup（X）≥minsup）。2.2. 高效用项集挖掘效用的基本含义（姚和汉密尔顿，2006）是一个项目对用户的重要性或盈利性或兴趣。模式的效用描述了它的相关性或好处，可以根据用户优先级和特定领域的知识，在数量、价格、收益或其他事实方面进行估计。实用程序可以是内部或外部的。内部效用确定根据在交易中收集的信息，例如所售物品的价格/数量。外部实用程序显示用户首选项。HUIM被广泛用于决策过程中，以纳入用户的选择。例如一个人可能热衷于发现所有高弯曲的交易T-ID i1 i2 i3 i4i5利润6 2 10 1 5表5衍生效用。项目集实用程序（i3）130（i5）50（i1 i3）（i3 i5）105（i1 i3 i5）98定义4.（（itemset的效用）：）。项目集X在事务（Tp）中的效用联合X;TpXi2X^XTU。iq;Tp2在交易数据库中的efit，而另一个可能对发现具有总销售额的实质性增量的所有项目集感兴趣。表3显示了包含8个实例的数据集的示例。有关的利润载于表4。衍生效用如表5所示。定义3.（（效用）：）。交易中物品i q的效用被定义为U。i q; T p≠0，其中Q. iq;Tp是交易中iq的数量Tp.U i q;T p1/4Q i q;T p ×P iq1也就是说，Ui3;T1=10×3= 30。表1事务数据集。TID交易1a c d2a b c d3b d e4阿得埃表2支持itemset。项集支持项集支持{a}3{e}个2{二}2{a，c}2{c}2{b，c}1{d}4{c，d}2也就是说，U i1i4;T1=U i1;T1+ U i4;T1=（1 6）+（4 1）= 10。定义5.（数据库中项目集X的UXXTp2D^XTpU。X;Tp1000也就是说，U（i5）=Ui5;T3Ui5;T4Ui5;T6Ui5;T7=（3× 5）+（2× 5）+（4× 5）+（1× 5）= 50定义6.（（Transaction Utility）：）. 一个交易的效用被定义为Tp中发生项目的效用的增加。T U。TpXi2TpU。i;Tp100也就是说，TUT4=Ui3;T3Ui5;T3=（2× 10）+（2× 5）= 30。定义7.（（总效用）：）。事务的数据集D的总效用被表示为ToU（D），并被定义为transacti onutilityT U. 所有事务的TP由数据库t组成。联系我们你在我身边Ti2D即ToU星期六星期七星期八星期六= 40 + 14 + 31 + 30 + 27 + 51 + 47 + 10 = 250定义8.（（相对效用）：）。数据集D中项目集X的相对效用表示为RU（X），并定义为效用UX与数据库ToU（D）的总效用之比。RUXUX=ToUD6也就是说，RUi1i3=Ui1i3=ToUD= 90/250 = 0.361642S. 库马尔Mohbey/ Journal of King Saud Universityð Þ × ××≤≤ð Þ ð Þþð Þþð Þ12pTp2D^XT pP1 31定义9. （高实用Item set）：）. 如果 项集 具有效用超过用户指定的最小效用阈值为高效用ExpSu pXXnP. X;T9项目集（HUI）。注意，对于项集的效用，向下闭包属性不成立。{i5}实用程序很小，但它的{i3 i5}超集是一个很大的实用程序。因此，HUI挖掘搜索空间不能被有效地修剪。为了有效地平滑搜索区域，提出了交易加权利用率（TWU）的概念（Leung和Jiang，2014定义10.（（总加权利用率）：）。项集X的TWU被定义为与项集X的每个事务的TU之和。 TWUXXTUT7也就是说，ExpSup i1i3;T1=（0.71.0)+（1.00.8)+（1.00.8)=2.3概率数据库中的模式X被称为是频繁的，当且仅当ExpSup（X）大于minsup，其中minsup是用户定义的最小支持阈值。2.4.序列模式挖掘序列模式挖掘的问题可以通过序列数据库D来定义，并且用确定元素顺序的每个序列中的每个项目的时间戳来注释序列e = 称为序列e2 =如果它有l个整数j 1，j 2，. 其中，16j1j2<<.. . =<（1，3），（1，2，3），（2）>有三个项集，长度为|e|= 2 + 3+ 1 = 6。 序列e1=（1，3），（1，2，3），（1，2，3），（2），（2，3）>支持e，或者换句话说，e是e1的子序列。3. 大数据范式大数据挖掘解决了两个关键问题。一个挑战是数据生成速度超过机器在如此庞大的数据中。并行处理是定义12.（（预期支持）：）。项目集X的期望支持度ExpSup（X）是数据库中所有事务上X的存在概率之和。一些项集的预期支持度如表7所示。表6不确定的事务处理数据集。T-ID交易T1（i1，0.7）;（i3，1.0）;（i4，0.3）T2（i1，1.0）;（i2，0.5）;（i3，0.8）;（i4，0.5）T3（i2，0.5）;（i5，0.6）;T4（i1， 1.0）;（i2， 0.7）;（i3， 0.8）T5（i2，0.5）;（i5，0.9）表7期待支持。项目集ExpSup（i1）2.7（i2）2.2（i3）2.6（i3 i4）0.7（i1 i2 i3）0.96解决这些问题的关键技术。这是因为它允许算法使用多个处理单元，并且还为计算耗时的应用程序提供了快速工作的可能性。并行计算是性能改进的关键（Wu等人， 2013年）的报告。即使数据集可以适应您的内存，也可能有中间数据（如候选模式或用于频繁模式挖掘的数据结构）无法适应内存。并行范例一般是公共存储器的分布式硬件或软件系统因此，可以分布或共享并行技术。算法的有效设计是并行处理中的一个挑战，因为它必须处理诸如并行计算的存储器可扩展性、工作划分和负载平衡等特定问题其他挑战是最小化同步和通信成本，找到良好的数据布局和数据分解方法，以及最小化I/O开销。分布式系统是一组独立的计算组件，对于其用户来说是一个一致的系统（Sagiroglu和Sinanc，2013）。分布式系统有两个方面：（1）自治计算组件和（2）作为中间件的单个系统。分布式系统具有一定的显著特征，包括：实时性、多进程、多线程同时执行和资源共享。有几种不同的分布式系统，如网格、P2P系统、云计算系统、自组织网络和社交网络在线系统。虽然有重大进展，S. 库马尔Mohbey/ Journal of King Saud University1643分布式系统在异构性、安全性、服务质量、可扩展性、故障处理、并发性、透明性和开放性等方面还存在一些技术难点分布式挖掘的精度或有效性依赖于信息的划分、任务的规划和整体的综合，因此很难预测。并行挖掘比分布式挖掘更能保证分布式挖掘和并行挖掘都可以加速模式挖掘过程。但它们有一些不同之处。近年来，一些并行或分布式数据挖掘平台和技术被进一步设计，以实现高性能的数据挖掘。3.1 多核计算：多核处理器中的同一芯片上有多个处理多核处理器是标准计算的高级转变，提供了新的高性能计算（HPC）和并行处理。该处理器促进多核计算，并且不同于超标量处理器（Dolbeau等人， 2007年）。它们在比指令级更高的程度上操作多线程和并行性，并在很大程度上支持主流计算。3.2 网格计算：网格计算被设计为提供对有价值的和受限的资源（诸如具有高性能的并行计算机）的快速和有效的访问（Ernemann等人，2002年）。它使用多个分布式计算机资源的集合来实现一个共同的目标。每个网格节点完成不同的任务/应用程序。这个概念与以前的Meta计算方法类似，后者的目标是计算资源，而网格计算的范围更广，可以访问本地不可用的资源。3.3 图形处理单元（GPU）：最近，可编程图形处理单元的性能发展迅速。GPU具有强大的计算并行能力。先进的GPU可以等同于一个小型计算机集群的能力。GPU对于具有高度并行工作负载的数据是有效的，其中相同的计算被呈现在存储在网格状结构中的大量数据上GPU计算涉及CPU的计算机和内存以及设备（GPU的内存和计算机）。GPU具有大型并行多核架构，可以运行数百万个块线程。块之间的通信依赖于高带宽共享内存。每个块线程通过一个小延迟的共享内存与其他线程通信GPU计算和软件不再需要熟悉图形，因此GPU加速算法可以设计为以非常并行的方式表达算法最近的趋势是允许在图形处理单元上进行通用计算GPU是高度优化的计算机图形协处理器.最近，一些基于GPU已经设计了诸如图像处理以及CPU和GPU上的多核并行图形探索的工具（Zhang等人， 2010年）。3.4 Hadoop和MapReduce：对分布式算法的需求体现在信息量的增长在过去的十年中，MapReduce（Borthakur，2007）和分布式平台Apache Hadoop（Dean和Ghemawat，2008）经常被用来帮助设计和执行这些算法。Hadoop是一个用于分布式处理大数据的开源框架。Hadoop使用MapReduce编程模型在机器集群中编写和分发应用程序Hadoop的两个组成部分是HDFS和MapReduce编程模型。MapReduce首先，MapReduce将数据划分为具有一些副本的相等大小的块，并自动将块均匀分布到分布式文件系统，以便用户免于位置和数据分布任务。第二，MapReduce重新执行失败的作业，而不重新执行其他分配，第三，MapReduce通过将较慢或繁忙节点的未完成作业重新分配给异构集群中的空闲节点，提高了完整的输出。MapReduce的实现包括两个主要阶段：map和reduce。映射阶段对输入数据使用映射函数，并在处理它们之后产生许多键值对约简阶段每次考虑单个键，并通过与该键相关的值迭代以产生最终结果它们都同步工作，以处理一组键值对。数据文件被统一划分为不相交的部分，并存储在Hadoop分布式文件系统（HDFS）中。具有输入件的工作器通常被分配映射函数以减少必要的输入传输。MapReduce使用数据局部性特性将数据与处理节点配置在一起，以便快速访问数据因此，没有任何共享架构可以消除程序中考虑失败的负担架构本身检测或减少不成功的映射，并将其分配给另一个节点。图1显示了Hadoop MapReduce的架构。3.5 Spark：Apache Spark（Zaharia等人，（2012）成为大数据分析最流行的分布式框架，由于其对数据集的分布式抽象，其性能优于Hadoop。基于MapReduce的Hadoop程序不适合迭代操作，因为每次迭代都需要读取新的磁盘。在处理大量数据集时，这一特性至关重要。这个问题也是Spark发展的原因。与Hadoop的MapReduce基于磁盘的计算相反Fig. 1. MapReduce的架构1644S. 库马尔Mohbey/ Journal of King Saud University在每次迭代时提供中间数据的内存处理，并允许用户持久化数据以及应用于大型集群的新抽象分布式内存模型，用于Spark编程模型中使用的内存计算，称为弹性分布式数据集（RDD）。Spark提供了一个非常可扩展的基于DAG的数据流，以去除指定的MapReduce两阶段流模型。RDD是不可变的数据集集合，它提供了一系列内置函数来将一个RDD转换为另一个RDD。Spark将RDD的内容缓存在工作节点上，这使得数据的重用更加快速。代替复制，RDD可以基于沿袭数据实现容错。Spark将跟踪足够的信息来重建RDD如果一个节点发生故障。图2解释了spark框架的操作模型。4. 分析标准在总结并行和分布式方法时，考虑了以下关键因素：分裂类型，通信开销，负载平衡，数据表示和阶段数。(i) 搜索空间划分的类型：将问题划分为子问题所采用的策略对方法有重要影响。数据分区方法将问题划分为类似的子任务，对单独的数据分割执行相同的操作每个子任务在整个搜索空间上操作，但在输入数据子集上操作。最后，将每个子任务产生的局部结果数据划分方法期望每个映射器的主存储器应该包含候选k-项集。因此，它不能在密集数据集上扩展大的候选集。另一方面，搜索空间划分方法从输入数据库构造投影数据库每个投影数据集包括用于提取项集子集的最终结果是每个投影数据集的结果的组合。(ii) 不同的数据表示：在并行和分布式挖掘方面，数据表示起着至关重要的作用。它会影响挖掘过程、速度、可伸缩性和数据库扫描次数。根据需求和开发需要，可以采用不同的方式存储数据。水平布局是按行存储和访问信息的传统方式。第二个是垂直布局，这是一种具体的存储方式数据垂直作为键/值对，可以通过列访问。(iii) 通信开销：通信开销在并行分布式算法中至关重要，因为如果传输大量信息，其网络很通信开销主要与映射器发送到归约器的结果有关。因此，减少传输开销成为算法发展的一个重要(iv) 负载平衡：对于并行和分布式应用程序的设计，负载平衡是至关重要的，可以提高分布式系统的有效性和性能，并允许负载迁移以有效使用资源。资源共享是工作站机群上分布式系统负载平衡在集群节点之间划分作业，以便快速完成任务。不同的任务划分方式对负载平衡有很大的影响。一个好的任务分配到每个处理节点将减少不平衡。5. 模式挖掘的并行分布式方法在本节中，我们首先介绍了并行和分布式频繁项集挖掘的现有发展。然后介绍了并行项集挖掘的一些扩展，即，并行顺序模式挖掘，并行高效用项集挖掘和并行挖掘算法的不确定数据，在大数据的背景5.1. 频繁模式挖掘本小节介绍了可用的实现，描述了分布式和并行处理中发现大型数据集中频繁项集的最新解决方案Pfp（Li等人， 2008）：FP-Growth对MapReduce的适应。PFP包裹计算在整个集群的方式，挖掘任务可以在不同的机器上独立处理这导致机器之间的依赖性和传输成本的降低。挖掘任务由三个MapReduce任务组成该算法是为了发现top-k项集而开发的，适用于Web数据挖掘。它可以实现近似线性的加速比，并具有处理计算机故障的能力具有不同大小和特征的独立FP-树对运行时间和负载分布有重大影响，因为它们处理具有不同复杂性的子问题。图二. Spark框架的工作模型。S. 库马尔Mohbey/ Journal of King Saud University1645PFP算法不能处理小的最小阈值，并且当至少一组投影事务不适合机器的存储器时，它失败。当计划的事务显著重叠时，通信开销可能非常高，因为在这种情况下，数据的重叠被发送到网络在几次。SPFP（Deng and Lou，2015）是在Spark框架上实现FP-growth的一个简单实现。它包括MLlib中的机器学习算法库。GPU-FPM（Zhou等人，2010年）：它是一个使用OpenCL库实现的，以加快挖掘过程。开发了一种紧凑的数据结构，将整个数据库存储在GPU中，以符合GPU内存限制和访问延迟。结果表明，考虑阈值1900和块大小10，GPU-FPM在数据集T4011001 OOK的16倍线程下加速14.857倍。由于所有的模式验证过程都由GPU完成，GPU占用了CPU和GPU的大部分计算时间，GPU-FPM通过扩展线程大大减少了计算时间。此外，即使在最坏的情况下，GPU也使用了89%的执行时间。GPU-FPM有效地利用了GPU的计算资源。GPU-TreeProjection（Teodoro等人，2010）：树投影算法的GPU-TreeProjection多核存储器共享和基于GPU的并行化版本（Agarwal等人，2001），并设计了一个GPU版本的算法。一个新颖的紧凑和简单的 表 示 为 GPU 设 计 的 交 易 数 据 集 。 经 过 全 面 优 化 后 ， GPUTreeProjection在CPU共享内存环境中的规模和加速比接近线性。GPU版本比标准CPU版本快173倍，而传统方法无法提供可扩展性。对于CPU和GPU性能，实验结果的最大标准偏差与CPU版本相比，基于GPU的树投影非常有效，并且可以随着支持的下降而扩展。在GTX 470和GTX 260 GPU上实现的最高加速比分别是顺序算法的173倍和95倍。GPApriori（GPU并行Apriori算法）（Zhang等人，2011）：垂直事务列表的位集表示，利用基于trie的候选集和垂直数据布局。它使用优化的细粒度并行支持GPU执行计数过程。事务数据库表示为“静态位集”内存结构。 这种数据结构改进了标准Apriori实现中传统的垂直数据布局方法。这种图形处理器是使用Nvidia特斯拉T10的实施和作为COM 的几个国家的最先进的并行计算算法的CPU demon-strates高达100倍的加速。GPApriori总是优于基于CPU的Apriori实现。GPU版本相对于最先进的Apriori单线程算法加速了一到SPC、FPC和DPC（Lin等人， 2012）：这些算法是为了提高Apriori算法在MapReduce平台上的加速比和可扩展性而开发的。所提出的算法的目的是在整个地图减少作业的节点的最佳使用，并在集群之间的工作负载的平均分配单次计数（SPC）是Apriori使用MapReduce的转换固定通道组合计数（FPC）旨在通过应用生成和测试任务的三个映射缩减阶段来削减调度调用的数量。它只需要一个单一的阶段，通过加入SPC中的各个阶段的候选人来计算支持因此，与SPC相比，FPC需要更少数量的映射缩减作业。虽然当合并后产生大量候选集时，候选集可能会在合并过程中使工人过载，但由于严格固定的合并计数，也无法修剪候选集。因此，提出了动态通道组合计数（DPC）算法，该算法动态地组合不同通道的候选集，以平衡连接通道内的工作负载这确保了对每个节点的优化利用。DPC需要使用较少数量的映射缩减作业并最大化修剪的候选集。该算法利用前一阶段的运行时间来调整候选集的阈值DPC是最快的，更可扩展的算法中提出的而且，DPC的速度比SPC快8倍当最小支持度小于0.2时，FPC和DPC都优于SPC。DPC与FPC相比工作得更好，因为它可能会产生太多的假阳性候选。MRApriori（Yahya等人，2012年）：MapReduce算法，需要两个阶段来生成k-频繁项集。在第一阶段中，输入数据被分发到映射器节点，每个映射在单独的数据库上应用映射Reduce将map在第二阶段，文件信息被附加到前一阶段的输出，包含所有的本地频繁项集。该阶段中的映射计算部分k-频繁项集的每个项在单独数据库中的频率Reduce产生键/值对，键包含全局频繁模式，值包含整个数据库中的频率计数。MRApriori算法性能良好。但是，它会产生大量的部分频繁项集，导致每个节点的执行时间更长即使使用MapReduce此外，由于候选集的组合爆炸，MRApriori在每次作业中都需要扫描磁盘 数 据 。 IMRApriori （ Farzanyar and Cercone ， 2013 ） ， 在MRApriori映射缩减阶段应用有效的修剪策略来减少部分频繁项集生成，该算法使用了INS项目集的概念。在MRApriori中，随着最小支持度的降低，每个数据集中会产生大量的部分频繁项集，从而需要更多的执行时间。在IMRApriori中，全局不频繁项集在阶段1期间被修剪，因此，它在执行时间方面比MRApriori更有效Dist-Eclat和Biglavin（Moens等人， 2013年：MapReduce用于挖掘k-频繁项集的方法; Dist-Eclat是Eclat的改进（Zaki等人，1997年），鉴于使用Apache Hadoop的分布式计算平台的改进的执行时间。该方法在机器间均匀分配搜索空间，对每个分区的数据库分别挖掘项目集，将局部结果拼接在一起生成全局频繁项目集。然而，需要重复局部频繁模式组合和计数的过程来修剪全局非频繁项集，这使得其效率低下。这种算法无法处理大量数据。BigData挖掘是一种混合技术，它解决了在挖掘子树时需要完整数据库生成k-频繁项集和通信开销的问题该算法首先利用Apriori算法生成k-频繁项集，然后利用Eclat算法提取频繁模式。k-FI是逐层计算的，每当候选集超过内存限制时，候选集可以跨映射器分布以进行进一步计算。负载平衡和通信成本通过前缀长度参数k来解决 Dist-Eclat和Biglash的表现都优于PFP（Li等人， 2008年）。然而，Dist-Eclat的执行速度是最好的，Biglash能够挖掘大量数据集。对于所有考虑的minsup值，DistEclat 最 快 。 如 果 大 于 0.1% ， BigCast 的 速 度 就 和DistEclatDistEclat在处理大型数据集时往往会耗尽内存，因为它必须将所有频繁项tidlist保存在主内存中。Bigarette不能同时执行6个以上的任务。P-MINE（Baralis等人， 2013年）：P-MINE推出了 一款 基于磁盘的一种基于多核处理器1646S. 库马尔Mohbey/ Journal of King Saud Universitysors. P-Mine是应用VLDBMine开发的持久化数据结构。VLDBMine数据结构建立在HY-Tree数据结构的基础上，可在磁盘上提供完整和无损的数据表示。此外，它利用项目索引和二级结构来逼近特定挖掘任务所需的HY-Tree部分P-Mine使用预取策略来改善数据传输成本，并利用多处理器，从而使其在执行时间和处理大数据方面使用8个核心，最大总加速比为5.5。新进化方法学（Cano等人，2013年），用于评估GPU上的关联规则。使用GPU和CUDA编程模型，可以并行地大量提取所制定的规则，从而减少计算所需的时间。它得益于内核的同时执行和信息的异步传输，这提高了模型的有效性。该实现中的关联规则挖掘独立于不同规则的评估，因为存在没有内在的依赖。因此，可以同时计算规则。先行词的覆盖方法也是完全独立的，这是一个案例规则的结果。因此，判例的范围和每项规则的后果也可以同时计算。用于生成关联规则的GPU模型包括用于覆盖、约简和适应度计算的3个内核。将该模型的计算时间与单线程、多线程和图形处理系统的实现进行比较