沙特国王大学学报流程满足大数据需求：在大数据环境Reguieg HichamAl-Al-Benallal Mohamed AnisAlgeria，31000阿提奇莱因福奥文章历史记录：2020年12月14日收到2021年2月9日修订2021年2月18日接受2021年3月4日网上发售关键词：进程发现事件日志大数据ApacheSpark分布式计算A B S T R A C T流程挖掘是一种业务流程管理技术，用于从流程执行日志中提取值。流程发现算法，如alpha和启发式挖掘器，用于从事件日志自动发现/重建业务流程模型。然而，这些技术在处理大数据时的性能是有限的。为了解决这个问题，我们提出了一个分布式的实现，基于Spark框架，阿尔法和启发式算法，以支持高效的可扩展的过程发现的大过程数据。该方法包括分配CPU密集的阶段，如与这些算法相关的因果关系矩阵的建设实验结果表明，该算法的速度和规模的变化方面的数据大小和集群中的节点数。版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍流程挖掘是一门旨在自动发现、合规和改进业务流程的学科（Van der Aalst，2016）。具体来说，进程发现是进程挖掘领域中的一个事实上，它包括分析事件日志的存储库，以便推断再现业务流程行为的模型。实际上，这是一项计算上具有挑战性的任务，因为它包括在广泛且持续增加的日志存储库上探索事件之间的潜在关系的广阔空间。集中式进程发现在文献中得到了广泛的研究。作为进程发现算法的示例，我们引用了a- miner（alpha）（van der Aalst等人，2004）、灵活启发式Miner（FHM）（Weijters和Ribeiro，2011）、非线性规划（ ILP ） Miner （ van derWerf 等 人 ， 2009 ） 和 Inductive Miner（Leemans等人，2013年）。先前引用的算法能够从事件日志中生成流程模型。尽管如此，这些技术并不旨在支持不断增长的事件规模*通讯作者。电子邮件地址：hicham. univ-usto.dz（R. Hicham）。沙特国王大学负责同行审查制作和主办：Elsevier由大规模现代信息系统生成的日志（Sakr等人，2018; van derAalst，2013）。生成事件日志的速度、种类和数量通常被认为是流程挖掘解决方案的主要挑战。由于事件日志的分布性和大规模性，过程挖掘分析在大数据领域受到了学术界的广泛关注。在（Reguieg等人，2012; Reguieg等人，2015年），作者研究了MapReduce（Dean和Ghemawat，2008年），以支持分散事件日志中的事件相关性发现，即，以识别属于同一过程执行的事件。此外，MapReduce已被用于实现可缩放的a-miner和灵活的启发式Miner（Hernandez et al.，2015; Evermann，2016）。随着内存计算集群的出现（例如， Spark平台（Zaharia等人，2010）），MapReduce的局限性变得越来越明显，例如迭代处理的性能差（Shi等人，2015年）。因此，越来越多的研究工作和应用，即机器学 习 （ JayaLakshmi 和 Krishna Kishore ， 2018 ） 和 数 据 挖 掘（Kumar和Mohbey，2019）转向了Spark。Spark是一个快速、通用和可扩展的内存大数据计算引擎。它为大多数大数据问题提供了一站式解决方案。此外，委员会认为，它集成了批处理、实时流处理、交互式查询、图计算和机器学习。尽管它的好处，火花还没有被广泛研究，在该领域的过程采矿。考虑到它的优势以及大多数流程挖掘算法都是迭代的这一事实，研究Spark在这一研究领域的表现是有意义的。https://doi.org/10.1016/j.jksuci.2021.02.0081319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comR. Hicham和Benallal Mohamed Anis沙特国王大学学报8479●（）^在本文中，我们介绍了一个有效的可扩展的过程挖掘技术，包括分布式算法，以支持大事件日志的过程发现。依赖于众所周知的过程发 现 算 法 Alpha （ van der Aalst 等 人 ， 2004 ） 、 Alpha+（Medeiros，2004; Hung等人，2020）和Flexible Heuristic Miner（Weijters and Ribeiro，2011），我们研究了处理框架ApacheSpark，提出了一种快速和可扩展的进程发现算法。我们工作的主要贡献可归纳如下：1. 我们提出了一个分布式的替代方案，从a和alpha+矿工的大型事件日志中提取因果关系矩阵。2. 我们引入了一个并行计算的频率和依赖矩阵的灵活的启发式矿工。3. 通过性能测试，我们证明了我们提出的算法是有效的，并能很好地扩展到大型事件日志。本文的其余部分组织如下。第二部分介绍了我们的工作背景。第三节讨论了一些相关的工作。第4节介绍了我们的主要贡献，我们的方法的概念架构，并详细介绍了我们的算法的实现本研究期间进行的评价试验见第5节。最后，我们在第6节中总结并概述了未来的工作。表1事件日志的片段（摘自Van der Aalst，2016）。情况事件ID活动时间戳.. .1Eid1一ts-11Eid2Bts-21eID3Dts-31eID4ets-41eID5Hts-52eID6一TS-62eID7DTS-72eID8Cts-82. 预赛在本节中，我们总结了进程发现中的基本概念。2.1. 进程事件日志流程事件日志L（Van der Aalst，2016），简称为事件日志，可以被视为关系模式L（CaseID，Event id，Activity，Timestamp，resources，...）上的关系。. ），其中每行表示一个事件并引用一个活动（Activity-name属性）。此外，事件按时间戳排序，并按CaseID分组以形成流程执行实例（跟踪）。表1举例说明了一个紧凑的事件日志。此事件日志表示任何进程发现算法的最低要求输入将日志中的信息转换为流程模型。2.2. Petri网Petri网（Murata，1989）是一种用于描述系统的图形和数学模型。它允许对常规业务流程进行建模。Petri网是一种有向二部图。它由三种元素组成：由有向弧连接的过渡和地点。图1示出了Petri网表示的示例。2.3. 阿尔法算法所谓的α-算法（van der Aalst等人，2004）是能够从事件日志自动地推断出标记为Petri网的过程模型的基本过程发现算法的示例。该算法包括两个主要阶段：（i）建立足迹矩阵，（ii）构建过程模型。2.3.1. L的足迹第一步是提取每对活动（转换）之间的顺序关系，以便在矩阵中捕获事件日志的足迹。表2显示了表1中描述的事件日志的足迹。对于任何事件日志L，以下顺序关系之一适用于任何活动对定义1（a-算法的基于对数的排序关系））。 设L是一组活动T上的事件日志设a，b2 T.直接继承（a>Lb）它在日志中至少存在一个跟踪，其中a后跟b。● 因果关系（a-！b）（）（a>b^bb且b后面永远不会有a。a)，a之后是L● 平行关系（ajjLb）（）（（a>Lb）^（b>La））有时b如下-低A，有时A跟随B。Fig. 1.由阿尔法算法发现的Petri网模型对应于表2中描述的足迹矩阵。● 没有关系（a#Lb）（）（（a乘b或反之亦然。b)（b）La）a永远不会被跟踪L表2事件日志的足迹矩阵见表1。abcdefgh a#L！我！我！L#L#L#L#Lb← L#L#Lj jL！L←L#L#Lc← L#L#Lj jL！L←L#L#Ld←LjjLj jL#L！L←L#L#Le#L←L←L#L！我！我！Lf#L！我！我！L←L#L#L#Lg#L#L# L#L←L# L #L#L#Lh#L#L#L#L←L#L#L#LR. Hicham和Benallal Mohamed Anis沙特国王大学学报8480Ll>;->公司简介LL2-！2.3.2. 构建过程模型第二步对足迹应用a-算法，建立一个带标记的Petri网. a-算法如下进行：表3基于示例2中的事件日志的FHM的子集日志排序关系频率和依赖性度量。1. 确定以下各项的集合：(a) 所有不同的活动（例如，TL={a，b，c，d，e，f，g，h}）(b) 可能的初始活动（例如Ti={a}）（一）ja>Lbj= 5ja>Lcj = 15jb>Laj= 5jb>Lcj = 10jc>Lbj= 10jc>Ldj = 15je>Ldj= 5ja>Lej = 5(c) 可能的最后活动（例如To={g，h}）2. 计算X =（{A，B}）的可能集合，其中：(a) A中的所有元素（分别为B）都是独立的（即，a1;a22Aa1#La2和b1;b22Bb1#Lb2）。(b) 对于每个（a，b）（A，B），aL b(c) A和B不是空的。（例如： X = {({a}, {b}), ({a}, {c}), ({a}, {d}), ({b}, {e}), ({c}, {e}) .. .（{e}，{h})，（{a}，{b，c}）（{b，c}，{e}），（{e}，{f，g，h}），（{f}，{b，c}）... （{a，f}，{b，c}），（{a，f}，{d}）3. 从步骤2中，仅选择最大集合（例如，Y ={（{a，f}，{b，c}），JaLbj = 5jcLbj= 10Ja>Lbj= 15ja>Lcj= 15Ja>Ldj= 15jb>Laj= 5JB>Lcj= 15jb>Ldj= 15JC>Ldj= 15je>Ldj= 5（b）第（1）款ja）Lbj=0ja）Lcj=0.93ja）Lej=0.83jc）Ldj=0.93je）Ldj==10ja）2bj=0.83jc）2bj=0.9ja）bj=0.24ja）cj=0.58L LL l({a，f}，{d}），（{d}，{e}），（{b，c}，{e}），（{e}，{f，g，h}）}。ja）Ldj=0.65ja）Lej=-0.96L l4. 在Y中为每个集合创建一个位置，并添加一个初始和最终jb）Laj=-0.24ja）Lcj=0.24L l地5. 在地点和活动例1.从（Vander Aalst，2016）的表1中获取事件日志，a-算法将生成Petri网[35]中描述的过程模型，如图所示。1 .一、2.4. Alpha+算法在（Medeiros，2004; Hung等人，2020年，以A +的名义。这一步超越了alpha算法可以捕捉长度为1和2的短循环。Alpha+算法如下进行：1. 它标识所有单循环活动并将其放入单独的列表中。2. 它识别连接到一个循环活动的所有弧，即，在单循环活动之前和之后发生的活动。(e.g trace = aeed，arcs = {（a，e），（e，d）}）3. 它从原始事件日志中删除所有单循环活动4. 它将算法应用于已清理的事件日志。jb）Ldj=0.43jc）Ldj=0.43例如2. 让L被一个事件日志和L为{a;b;a;c;d5;a;c;b;c;d10;a;e;d5}。考虑事件日志L，基于日志的排序关系的频率矩阵如表3a所示。2.5.2.计算依赖性度量基于对数序关系，FHM计算表示对数序关系中活动的相对频率的依赖性度量此外，这些度量表示两个活动定义3. FHM算法依赖性测量。设T是一组活动，L是T上的事件日志。设a，b2T;jaj是a在L中出现的次数，ja>Lbj是a>Lb在L中出现的次数，（jaLbj和ja>Lbj相同），则：ja>Lbj-jb>Laj，如果a ba>bjjb>aj15. 最后，它将单循环活动及其弧重新连接到发现的模型。2.5. 灵活的启发式矿工a)Lb¼Lja>Lbj：ja>Lbj1L;ifa¼bð1Þa) 2b¼JaLbjjbLajð2Þ发现流程模型的另一种替代方法是灵活启发式矿工（FHM）（Weijters和Ribeiro，2011）。引入FHM通过消除被认为是异常行为的不频繁或罕见的执行跟踪来处理噪声事件日志FHM包括以下步骤：2.5.1. 对数序关系和频率矩阵的提取FHM定义了三种基于日志的排序关系：定义2. FHM算法基于日志的排序关系。设T是一组活动，L是T上的事件日志设a，b2T：● 直接继承：（一个>Lb）、 （）它存在一微量 Rt1;t2;t3;. ;t n在L中，其中a = t i且b = t i≠ 1，对于i{1，2，... . ，n-1}（也用于alpha算法）。● 长度为2的环：（aLb）（）9r¼ft1;t2;t3;. . ;tng2L其中，对于i 2 {1，2，.. . ，n-2}。● 间接演替：（a>Lb）（）9r1/2t1;t2;t3;. . 其中ti= a且t j= b且i Lbj-absjaj-jbj3ja jjbj1FHM算法使用这些基于频率的依赖性度量来定义依赖性图，该依赖性图可以被转换为Petri网。该算法将在该阶段通过要求特定频率阈值来考虑噪声，以确保依赖性的有效性。通常，这些阈值被设置为0.9，并且低于这些阈值的依赖性被消除。实施例3.考虑实施例2中的事件日志和表3a中的频率，表3b中呈现了所得到的依赖性度量。2.5.3.发现过程模型在这个阶段，算法识别每个活动的直接输入和输出，以构建足迹矩阵。然后这些R. Hicham和Benallal Mohamed Anis沙特国王大学学报8482包含直接关系依赖性的足迹矩阵被转换成依赖性图。之后，该算法通过添加循环、“and”和“or”运算符来扩展图最后，插入间接依赖关系，得到的图表示FHM算法发现的过程模型。2.6. Spark概述Apache Spark（Zaharia等人，2010）是一个开源的内存中分布式计算框架。它使用Hadoop（Hadoop，2020）基础设施组件，如Hadoop 分 布 式 文 件 系 统 （ HDFS ） 和 Yet Another ResourceNegotiator（Yarn）来管理大规模集群。Spark对于小型数据集具有亚秒级的延迟。具体来说，Spark比MapReduce（Dean和Ghemawat，2008）更适合大型数据集应用。由于其各种功能，Spark已被许多研究领域采用，例如机器学习（JayaLakshmi和Krishna Kishore，2018）和模式挖掘（Kumar和Mohbey，2019; Sundari和Subaji，2020），作为解决大数据问题的处理引擎。Spark围绕着RDD，RDD是弹性分布式数据集（Zaharia等人，2012年）。RDD是Spark的基本数据结构。它是弹性的、容错的、只读的和分布式的记录收集。每个RDD被划分为逻辑分区，这些分区可以在集群的不同节点上存储和计算。这些特性通过它们的局部性来提高性能。Spark支持RDD上的两种操作：transformations和actions。诸如map和flatMap之类的转换操作从现有的RDD创建新的RDD。诸如reduce之类的动作操作运行计算（例如，聚合），并将结果返回给驱动程序。与MapReduce类似，Spark计算基于函数式编程（Spark运行wordcount的示例见附录A.1）。3. 相关作品在单机上的进程发现已经在文献中被广泛算法，例如矿工（vander Aalst等人， 2004）、启发式（Weijters等人， 2006）和灵活的启 发 式 矿 工 （ Weijters 和 Ribeiro ， 2011 ） ， ILP 矿 工 （ vanderWerf等人， 2009）和感应采矿机（Leemans等人，2013）是能够从历史事件日志学习和发现过程模型的算法的示例。然而，这些技术变得无法跟上信息系统的发展，其中事件日志变得更大，分散在多个子系统中并且具有多种格式。随 着 分 布 式 数 据 处 理 框 架 的 出 现 MapReduce （ Dean 和Ghemawat，2008）和Spark（Zaharia等人，2010年），许多研究人员有兴趣将大数据研究领域和过程分析相结合。第一个将MapReduce与流程挖掘结合起来的研究是在（Reguieg等人，2012年）。提出了一种在事件日志分散、事件间关系缺失的系统中进行事件关联发现他们使用MapReduce来识别一组规则，这些规则指定如何将事件分组在一起以形成跟踪。 该技术已经在（Reguieg等人，2015; Cheng等人，2017）来发现复合规则。在事件与caseID不关联的情况下，此方法可被视为进程发现的预处理步骤。在过程发现的背景下，（Evermann，2016; Hernandez等人，2015）已经使用MapReduce来实现alpha算法和灵活的启发式矿工。一方面，进程发现技术是迭代计算，在MapReduce上实现alpha miner或灵活的启发式miner需要多个MapReduce作业。另一方面，MapReduce存储，读取和排序中间磁盘上的数据，这涉及磁盘上的更多I/O （Kalavri和Vlassov，2013）。因此，这可能会影响任何计算的全局性能。作者在（Cheng等人，2020），已经研究了Spark，以引入一种由基于过滤器的混合模型发现表示的技术。他们的方法旨在发现混合过程模型，即，正式和非正式模式的结合。并行进程发现也已研究使用高性能计算（HPC）。在（Sahu等人，2018），作者使用消息传递接口MPI实现了alpha miner的并行版本。他们的方法是基于alpha算法的任务并行性。在使用MPI时，集群节点之间的头级并行性和共享内存是两个主要的好处。然而，MPI具有差的可靠性，因为它不是容错的并且对于大数据处理环境没有公共运行时（Jha等人，2014年）。与使用线程级并行性的（MPI）作业不同，Spark作业用于遵循数据流模型（Chowdhury等人， 2014年）。Hadoop MapReduce和Apache Spark等大数据平台已被用作大多数大数据问题的一站式解决方案然而，在这些框架下运行的作业需要仔细的参数调整，以提高处理性能。此外，不良的参数整定可能导致性能不佳在（Cai等人，2019年），作者介绍了一个自适应框架，名为mrMoulder，用于自动调整新作业的参数。mrMoulder利用动态扩展的配置存储库，在短时间内为大数据作业推荐接近最佳的配置。在合理的时间内处理大量的数据，使用巨大的计算资源将增加能源消耗，从而导致温室气体排放和环境影响的增加。 作者在（Wu等人，2016b，a）处理这个问题，并分析绿色措施和大数据之间的关系。在相同的背景下，作者在（Wu等人，2018年）介绍了最新的解决方案，旨在找到可持续发展目标与信息和通信技术之间的相关性。4. 贡献在本节中，我们介绍了我们的方法的概念架构，并描述了基于Apache Spark框架（Zaharia等人， 2010年）。4.1. 概念架构图2示出了所提出的方法的概念架构的抽象。它分为以下几层：4.1.1. 数据源层第一层概述了事件数据源系统，如业务流程管理系统（BPMS）、生产系统和Web应用程序。这样的系统连续地生成广泛的过程信息项（事件）。4.1.2. 数据存储层然后将事件集成到数据存储中，以便进一步分析。由于事件数据是半结构化的，Hadoop分布式文件系统（HDFS）（Shvachko等人，2010）适合于存储这样的数据。4.1.3. 处理层实际上，这一层代表了架构的核心。它包括在Apache Spark处理引擎上运行的并行进程发现算法。处理引擎将存储的事件日志在HDFS中作为输入，然后应用所提出的算法之一R. Hicham和Benallal Mohamed Anis沙特国王大学学报8483图二. 提出的方法的概念架构。来扩展自动进程发现。这一层的并行算法是本文的主要贡献。4.1.4. 可视化层这一层提供了结果模型的图形表示。4.2. 并行进程发现算法我们工作的主要目标是提出一个可扩展的过程描述算法，以处理大事件日志。请注意，流程发现中的计算密集型任务是将事件日志转换为因果关系矩阵。这一步需要探索事件之间的对数顺序关系的大空间。4.2.1. SA算法第一个并行进程发现算法是算法4中描述的基于Spark的Alapha算法（SAlpha）。它依赖于阿尔法矿工（van der Aalst等人，2004年）。作为输入，SAlpha需要事件日志并产生足迹矩阵，然后将其转换为Petri过程模型。首先，将事件日志加载到HDFS中并作为RDD读取。这里，RDD在节点上进行分区，每个分区包含一组迹线（见图3（a）和（b））。然后，SAlpha继续如下所示提取初始和最终活动（算法1中的第1 - 3行）：在每个RDD分区上，我们在映射转换上应用用户定义的函数selectFirstAndLast，以选择每个跟踪中的第一个和最后一个活动（图1中的第1行，map1）。 3（a））。结果 将 被 缓 存 以 供 下 一 步 使 用 然 后 ， 我 们 使 用 selectFirst（selectLast respect）。提取所有初始活动（最终活动方面）。（第2行和第3行，图2和图3） 3（a））。接下来，应用一个独特的操作来消除冗余活动。之后，初始和最终活动使用收集动作返回到驱动程序。提取活动对上的因果关系（图3（b）中的第4-5行首先，我们提取直接继承关系（a>Lb）。因此，我们将每个跟踪解析为(key，值）对，其中A和B是活动，>表示直接跟随关系。这个阶段是在RDD的每次拆分时通过在flatMap变换上使用用户定义 的 函 数 extract_extension 并 行 完 成 的 然 后 ， 通 过 使 用reduceByKey动作，将具有相同键的所有值聚合在一起成为单个对（键，值列表）。在这里，每个分区上的合并对首先在本地合并，然后基于它们的键在集群节点上洗牌，然后再次在本地合并（见图2）。 3（b））。为●●R. Hicham和Benallal Mohamed Anis沙特国王大学学报8484）●）例如，对（AB，>）、（AB，>）和（AB，）将被简化为（AB，{<; >} ） 。 之 后 ， 在 （ 第 5 行 ） 中 ， 我 们 在 map 转 换 上 使 用compute_relation函数来计算全局关系（a-！Lb和ajjLb）的所有活动对例如，（AB，{<; >}）和（CD，{>}）将被转换为（AB，'jj'）和（CD，'-！'）.4.2.3. SFHM算法本小节讨论表示为SFHM的基于火花的灵活启发式挖掘器的实现（在图5中描绘）。SFHM依赖于灵活的启发式矿工（Weijters和Ribeiro，2011）。在这里，我们再次集中在基于日志的排序关系，以建立依赖性度量矩阵。生成足迹矩阵（第6 -8门控对将由程序驱动器收集以构造足迹（因果关系）矩阵。矩阵中的空单元格为因为，没有一个人，是主动的。ities（a#L b）.该矩阵反映了整个事件日志的抽象，并将其转换为Petri网。4.2.2. SAlphaplus算法第二种并行进程发现算法是基于Spark的Alapha plus算法，用（SAlpha+）表示。SAlpha+的实现与SAlpha算法非常相似。主要区别在于，SAlpha+有一个额外的预处理步骤，可以发现长度为1的短循环，并且它会考虑“ABA”和“BAB”模式算法2中描述了SAlpha+算法的实现细节。我们首先提取具有“xAAy”形式的模式的所有活动例如，跟踪 这个任务是通过使用getLoopTasksWithArcs函数在flatMap转换上并行完成的（图1中的第1行，flatMap 2）。 4）. 接下来，单循环活动及其后继/前驱弧存储在不同的RDD中（图2中的第2-3行，map6和map7）。 4）. 然后，我们需要为每个单循环活动创建一个之后，我们从事件日志中删除所有单循环活动这也是通过过滤每个分区中的跟踪并行完成的，并生成没有单循环活动的最后，我们可以在清理过的日志上应用SAlpha算法来生成足迹矩阵（第10行）。算法3描述了SFHM算法的实现。其程序如下：计算活动的频率（图5中的第1行，flatMap 1）：首先，我们计算每个活动在事件日志中的出现次数，如下所示：（1）使用map转换，遍历分区中的所有活动，并为每个活动分配值1，以生成（A，1）形式的对，然后（2）执行reduceByKey函数，将每个活动的所有值相加。例如，L = {abc，bc}将给出（a，1）（b，2）（c，2）。由于独特活动的数量非常少，因此将结果收集到程序驱动程序中。计算直接连续关系a>L b频率（第2行，图5中的flatMap 2）：与上一步类似，我们对每条迹进行遍历，并通过使用map变换以（AB，1）的形式产生对。然后，我们通过使用reduceByKey动作对所有值的数量求和。例如，L = {abc，bc}将给出（ab，1）（bc，2）。计算依赖度量（aL b）（第3-5行所有低于用户定义阈值的候选项都将被排除。●●●R. Hicham和Benallal Mohamed Anis沙特国王大学学报8485LLLL通过使用reduceByKey动作，我们计算每对Activity的频率。例如，L= {abcd，abef}将给出us（ab，2）（ac，1）（ad，1）.. . （ef，1）.所有的统计数据，然后收集，lect到节点主。然后应用公式3计算（a）l b）依赖性度量。修剪不满足阈值的候选5. 评价在本节中，性能和可扩展性的建议算法进行评估，通过实验研究。5.1. 实验框架图三. SAlpha算法的数据流。见图4。 SAlpha+：提取一个长度循环活动。图五. SFHM算法的数据流。● 计算（aLb）关系频率和依赖性度量（a）2b）（第7-10行，图3中的flatMap 3）。 5）：使用映射变换，我们遍历所有迹线，寻找像“ABA”这样的模式，并以（AB，1）的形式生成对。接下来，我们对reduceByKey动作中的所有值求和。例如L ={abacd，abacd，aede}将得到（ab，2）（ed，1）。之后，在程序驱动程序中，我们应用公式2来计算依赖性度量（a）2b），并消除不满足定义阈值的候选项。● 计算（a>Lb）关系频率和依赖性-势测度b）（图12-15中的flatMap 4行） 5）：最后一步，我们对轨迹进行重新排序，并生成所有可能的com-我们已经使用Spark上的Python实现了SAlpha、SAlpha +和SFHM算法（Zaharia等人， 2010年）。环境 我们在群集上进行了性能测试13个物理节点，一个主节点和12个从节点（工作节点）。节点使用1 Gb/s以太网CISCO 2960-X交换机连接。主节点具有Intel i7-3370 CPU，运行频率为3.4 GHz，具有8个内核，16 Gb RAM和100 Gb磁盘。每个从节点都有一个Intel I5-4460 CPU，运行频率为2.8 Ghz，有四个核心，8 Gb的RAM和80 Gb的可用空间磁盘。操作系统为Linux Ubuntu服务器版本18.04 LTS，软件堆栈包括Spark版本3.0.0、Hadoop 3.2.1、Scala版本2.12、Python版本3.7、Java JDK版本1.8.0_251和用于模型可视化的Graphviz版本2.40.1。请注意，我们的环境中使用的非虚拟化从属节点是等效的，几乎接近Amazon EC2实例中的集群实例a1.xlarge。因此，我们的方法可以很容易地部署在真正的云计算上（Armbrust等人，2009）环境。数据集。我们对补偿请求进行了实验测试1事件日志取自（Van derAalst，2016）。它包含8个不同的活动，6个跟踪，每个跟踪的最大事件数为13。为了评估算法的可扩展性和速度性能，该事件日志被综合复制，以评估算法的加速和扩展。表4显示的大小，跟踪数和事件数的复制文件。Setup. 为了更好地利用集群资源，我们将Spark配置如下：（i）slave worker使用6.7 Gb，4个CPU核心，（ii）主服务器不执行任何并行计算，也不存储数据，它只运行程序驱动程序和Hadoop/ Spark主守 护 进 程 （ Master ， NodeManager ， ResourceManger 和NameNode）。在所有测试中，存储事件日志并从HDFS读取事件日志（Shvachko等人， 2010），并将输出（发现的模型）以dot和png文件格式写入主磁盘。运行时间是从作业提交到作业完成的时间。最后，我们在一个由一个主节点和12个工作节点组成的集群上进行了实验5.2. 实验结果在本节中，我们报告了我们的实验结果。首先，我们提出了所发现的模型的质量措施。 然后，我们讨论了算法的运行时间和可扩展性的性能。5.3. 发现模型图图6说明了在补偿请求事件日志上执行我们的算法所获得的流程模型。测量活动的成对组合（AB，1）（例如，对于迹r=我们生成对（ab，1）（ac，1）（ad，1）（bc，1）（bd，1）（cd，1））。然后，第1页https://doi.org/10.17632/xct7k6w98k.1R. Hicham和Benallal Mohamed Anis沙特国王大学学报8486SFHMi¼2ti-1表4实验中使用的日志中的轨迹和事件的大小、数量的总结大小（Gb）病例数事件数量25,382,63037,678,164410,671,79274,702,544821,228,858148,602,0061642,342,996296,400,9723284,155,646589,089,52264167,183,6041,170,285,228128330,768,3522,094,866,224见图7。SAlpha、SAlpha+和SFHM算法在不同输入事件日志大小上的运行时间。见图6。使用所提出的算法从请求补偿表5对提出的算法进行一致性检验表6每个算法的平均梯度和估计的洗牌次数SAlpha SAlpha+ SFHM平均梯度0.19 0.24 0.21Shuffles 7 9 8处理最大数据集（128 Gb）的时间在30 min（TSAlpha128= 23.79 min，T128SAlpha = 29.82 minT128为对于所发现的模型的质量，我们使用了三个质量度量，（i）适合度：模型能够再现事件日志，（ii）精确度：所发现的模型应该是精确的并且只允许比在日志中看到的最小的新行为，（iii）概括：所发现的模型产生过程的未来行为的能力（对于关于一致性检查度量的更多细节，读者可以参考（Adriansyah等人，2015））。从表5中，我们注意到我们的算法可以发现与原始算法具有相同模型质量的模型。请注意，本文的主要目标是在大数据环境中扩展进程发现算法，而不影响质量指标，即适应度，精度和泛化保持稳定。5.4. 效率- 是的为了评估所提出的算法的运行时进化性能，我们使用不同大小的输入事件日志进行了作为第一个测试，我们已经使用我们集群的全部容量对补偿请求数据集执行了3个算法（即，48核、8~0GbRAM和1Gb/s以太网。作为输入日志大小，我们从2 Gb开始，相当于一个日志有5M个跟踪和超过37M个事件，然后我们在每一步将日志大小加倍，直到128 Gb（见表4）。x轴表示输入数据大小，y轴表示运行时间（分钟）。此外，我们应该记得，所提出的算法的发现的过程模型与原始算法Alpha发现的过程模型相同（van der Aalst等人，2004）和FHM（Weijters and Ribeiro，2011）。26.77分钟）。其次，我们确定了一个线性演化的运行时间的3个算法相对于所使用的事件日志大小。此外，虽然数据大小在每一步都乘以因子2，但是对于SAlpha、SAlpha+和SFHM算法，执行时间的平均增加因子分别为1.79、1.81和1.79。SAlpha、SAlpha+和SFHM算法的平均运行时间梯度分别为0.19、0.24和0.21这意味着在一分钟内，SAlpha、SAlpha+和SFHM算法处理大约5，4，5千兆字节的数据。图7中的另一个关键观察是算法执行时间之间的细微差异。我们观察到SAlpha比SAlpha+和SFHM更快。这主要是由于：1. SAlpha+在SAlpha算法上执行额外的步骤。它提取一个长度的循环活动，然后扫描整个事件日志以删除循环模式。这个任务深深地影响了算法的性能。2. SFHM算法计算三个依赖矩阵，而不是SAlpha算法中的一个足迹矩阵。影响算法性能的第二个因素是数据混洗的次数。混洗是一种昂贵的操作，因为它涉及分组、分区和在网络上的节点之间传输环形数据。它由RDD操作触发，例如collect（）、distinct（）、reduceByKey（）和groupByKey（）。 表6示出了在每个算法中进行的洗牌的估计数量。尽管如此，SAlpha+和SFHM算法能够发现比SAlpha算法更复杂的模型。图 7比较从执行SAlpha获得的结果，SAlpha+和SFHM算法。首先，我们观察到，所需的2平均增加可以计算为a=avg<$P6ti-ti-1）方法健身精度概括原始10.837300.83214提出10.837300.83214R. Hicham和Benallal Mohamed Anis沙特国王大学学报8487我图8.第八条。算法在64 Gb事件日志和不同群集配置上的运行时间和相对运行时间（加速）。见图9。 不同群集和事件日志配置上的运行时间（纵向扩展）。5.5. 扩展性我们进行了两个不同的测试，以验证我们的算法的加速和放大。在第一个测试中，我们固定了输入事件日志的大小，并改变了clus- ter中的节点数。在第二个测试中，我们用相同的因子改变了输入事件日志的大小和节点的数量5.5.1. 加快为了测量接近的速度。我们将算法应用于固定大小的输入事件日志，即64Gb（约11.70亿个事件），我们增加了工人数量，12工人主要地，可以看出，随着工作者数量的我们可以观察到，运行时间减少得更快，直到配置8个节点。然后，它慢慢减少我们假设原因是8个节点的集群中的内存量接近输入日志文件的大小，并且在配置10之后，集群能够处理内存中的所有工作负载310节点和12节点配置之间的运行时间改善微不足道，证明了这一点这个音符在图中很好地出现。第8（b）段。相对时间1/4时间ei;i2f1;2;3;4;5;6g每步增加2个节点理想的时间可以通过i其中i2f1;2;3;4;5;6g.图 8（a），我们将算 法 的运行时间绘 制 在一个时间1当我们将群集大小从2增加到3Spark的一个关键特性是内存计算。R. Hicham和Benallal Mohamed Anis沙特国王大学学报8488表7比较所提出的基于火花的算法与原始集中式算法的运行时间。方法病例数阿尔法Alpha+FHM原始2.65M177s185年代235s提出5.3M44s52s50年代改进X0.5X4x3.5x4.7图8（b）示出了与图8（a）中相同的结果，但是以“相对尺度”报告对
我的内容管理
展开
