PDF
研究文章|开放获取
思源静, ”基于集合的微分进化算法基于引导当地自动化过程的探索发现”,复杂性, 卷。2020年, 文章的ID4240584, 19 页面, 2020年。 https://doi.org/10.1155/2020/4240584
基于集合的微分进化算法基于引导当地自动化过程的探索发现
文摘
进化算法是一种有效的方法来解决过程发现问题,旨在从事件日志我的流程模型是符合实际的业务流程。然而,当前的进化算法,如GeneticMiner ETM ProDiGen,收敛缓慢而艰难,因为他们采用遗传交叉和变异具有很强的随机性。本文提出一种混合进化算法的自动化过程发现,它包含一个基于集合的微分进化算法和引导地方探索。这项工作有三大创新。首先,提出了一种混合进化策略,采用微分进化算法的搜索解空间和快速近似最优解首先,然后一个特定的地方勘探方法加入帮助算法跳过局部最优。其次,提出了两个新的基于集合的微分进化操作符,可以有效地执行在因果矩阵微分变异和交叉。第三,一个细粒度的评估技术的目的是为每个节点分配分数,在流程模型中,这是用来指导当地的探索和提高算法的效率。实验进行了68种不同的事件日志,包括22个人工事件日志,44嘈杂的事件日志,和两个真正的事件日志。此外,该算法与三种流行的算法过程的发现。实验结果表明,该算法可以实现良好的性能,其收敛速度快。
1。介绍
基于流程的信息系统(π),包括工作流管理系统(管理系统),客户关系管理(CRM)、企业资源规划(ERP),已成为现代企业的基本的基础设施。π可以大大提高企业的运作效率。除此之外,它将记录业务流程的信息,如名称的活动,活动时间发生,生命周期的活动,形成事件日志。换成标准,由IEEE出版于2016年,提供了一个统一的、可扩展的语言标准化事件日志的内容和格式。流程挖掘技术可以用来发现换成事件日志的过程模型。希望尽可能一致的开采过程模型与实际业务流程。获得的过程模型可以用来改善企业业务流程、提高生产效率,优化产品。例如,ASML使用过程发现技术来优化晶片扫描仪在光刻机的生产。SAP ERP系统的使用过程中发现的技术帮助用户设计业务流程,分析业务的瓶颈和资源计划。飞利浦收集世界各地的事件日志的医疗设备来分析客户的习惯。 By this way, they can optimize their medical products and shorten the time of product development.
一般来说,有三个主要任务过程中挖掘,包括过程发现,一致性检查和过程改进(1]。过程发现的目标是获得一个流程模型,这与实际业务流程尽可能一致。大多数研究都专注于挖掘二进制关系事件日志的任何两个活动的控制流。除此之外,它还可以发现事件日志中包含来自其他领域的知识,如组织,时间,资源,等等。一致性检查用来测量偏差的开采过程从一个真正的业务流程重现事件日志挖掘过程模型。这种技术可以用于诊断的流程模型以及分析业务瓶颈。过程增强关注更改或扩展之前的流程模型。例如,通过使用事件日志时间戳,可以增强模型分析瓶颈,估计剩余时间,并发现分层流程模型。在本文中,我只关注过程发现技术从控制流的角度。
ɑ的算法,提出了van der阿尔斯特et al .,通常被看作一个里程碑过程挖掘的领域(2]。工作流模型,佩特里网,可以有效地找到因果关系,平行关系,和选择事件日志的任何两个活动之间的关系。之后,一些变异的ɑ算法被提出,就像[ɑ+算法3]和[ɑ+ +算法4]。然而,有许多在ɑ系列算法的缺陷,如抗噪声能力,alignment-based健身和精度。为了解决这些问题,提出了一些更高效的算法,如独立矿工(5和归纳矿工6,7]。前者提出了最近范Zelst et al .,基于整数线性规划。后者提出了Leemans et al。他们都显示良好的性能在处理小事件日志。
进化算法是一种有效的方法来解决这个问题的过程挖掘。de Medeiros et al。8)首先采用遗传算法(GA)在采矿过程,称为GeneticMiner。通过定义适应度函数和遗传算子(即好。,crossover and mutation), the GeneticMiner can find a process model, which is consistent with the real process. Cheng et al. [9,10)表明,GeneticMiner从事件日志不能有效地发现平行结构;因此,他们提出了一个混合动力技术,基于集成GeneticMiner,微分进化粒子群优化和改善流程挖掘的结果。Vazquez-Barreiros et al。11]提出了一个算法,名叫ProDiGen,这提高了GeneticMiner通过引入分层适应度函数找到完整,精确,和最小的结构流程模型。Buijs et al。12- - - - - -14)采用进化树显示过程模型,并提出了一个alignment-based技术指导GA的突变。然而,它是难以忍受的嵌入在变异操作alignment-based本地搜索,因为它太耗费时间了。在一般情况下,遗传算法的优点包括抗噪音的好,它可以处理过程中的关键问题的主要部分矿业通过一个统一的框架,如无形的任务,non-free-choice结构,任务重复的名字。然而,当前的基于遗传算法的收敛速度太慢了,因为他们采用随机搜索。
本文提出了一种混合进化过程挖掘算法,名叫德民。创新我们的工作包括三个部分:(1)提出了一种混合进化策略在这工作。在我们的方法中,德民首先接近最优的流程模型,基于集合的DE算法;当检测到早产,引导当地勘探方法在进化过程中会加入帮助算法跳过局部最优。(2)两个基于集合的运营商,即。,a set-based mutation operator and a set-based crossover operator, are designed for differential evolution of causal matrix.(3)提出了一种细粒度的评价方法指导地方探索分数分配给流程模型中的所有节点的候选人。这种方法不仅可以帮助人口避免早产,还提高德民的效率。
本文的其余部分组织如下。第二节介绍了过程挖掘的基本知识,如佩特里网和因果矩阵,以及DE算法。第三节详细解释了该算法。实验以及实验结果给出了分析第四节。最后,第五节给出的结论。
2。预赛
2.1。过程挖掘
过程挖掘的问题,流程模型通常被建模为一个地方/净(缩写为过渡P/T净),这是经典的佩特里网的变体。的定义P/T下面给出。
定义1。(P/T净)[2]。一个P/T网络是一个元组
,在哪里是一组有限的地方,是一个有限集的转换,
,和
是一组有限的有向弧。
让
是一个P/T网。的元素被称为节点。一个节点是另一个节点的输入节点如果
。同样,一个节点是另一个节点的输出节点如果
。此外,一个象征表示节点的所有输入节点
;也就是说,
。同样的,表示所有的输出节点
。基于P/T净,一个正式的定义工作流净(缩写为Wf-Net)。
定义2。(Wf-Net) [2]。让 是一个P/T净,是一个新鲜的标识符不是吗 。 是一个Wf-Net如果(1) 包含一个输入的地方这样(2) 包含一个输出的地方这样(3) 是强连通图1显示了一个过程模型,它是由一个Wf-Net表示。圆圈表示的地方,广场表示转换。转换Wf-Net代表活动(也称为任务)在真实的业务流程。黑点在初始位置代表一个令牌。启用一个过渡被解雇如果所有输入的地方包含令牌。“火”这个词意味着一个活动准备执行。如果一个过渡火灾、令牌在其输入的地方删除;与此同时,令牌是放在其输出的地方。例如,如果过渡”一个”解雇,令牌在“开始”将被删除,这个地方“P1”和“P2”分别会得到一个令牌。在那之后,三个转变”B”、“C”和“D”会启用。请注意,“P1”只有一个令牌;换句话说,尽管两种转换(或称。”B”和“C启用了”),只有一个可以被解雇。因此,可能的序列之间”一个”和“E”包括{B,D},{C,D},{D,B},{D,C}。
给定一个声音Wf-Net ,我们说是一个事件跟踪和是一个事件日志,包括跟踪。把上面的流程模型作为一个例子,它可以诱发很多事件的痕迹,就像ABDEG, ACDEH ADBEFCDG等等。
第一个问题需要解决在基于进化学的过程挖掘是染色体的编码。不幸的是,很难直接雇佣佩特里网络进化。de Medeiros提出了因果矩阵来表示流程模型,已应用于许多进化过程挖掘算法,如ProDiGen和GeneticMiner。因果矩阵的定义如下所示。
定义3。(因果矩阵)8]。一个因果矩阵是一个元组 ,在哪里(1) 一组有限的活动吗(2) 是因果关系(3) 是输入条件函数(4) 是输出条件函数因为我们通常需要比较因果矩阵所呈现的过程模型与其他模型中提出的网,一个映射的方法P/T净的因果矩阵是必需的。定义4显示了转换方法P/T净因果矩阵。
定义4。(映射P/T净因果矩阵)(8]。让 是一个P/T网。的映射是一个元组 ,在哪里(1) (2) (3) 这样 (4) 这样 解释的映射过程中,我们把流程模型图1一个因果矩阵,如表所示1。把活动”E“作为一个例子,它有两个输入的地方“P3”和“P4。“此外,输入转换”P3“转换”B”和“C过渡”,输入“P4“过渡”D”,因此, 。应该注意的是,这些活动在同一的子集或者加入关系,和这些不同的子集有一个和连接关系。相反,活动在同一的子集有和这些不同的子集或分裂的关系和关系。除此之外,说明活动的输入是空的展示活动的输出是空的。
|
||||||||||||||||||||||||||||||||||||
2.2。微分进化算法
微分进化算法(DE),首先由Das等人1995年提出,是一个随机的方法,模拟生物进化个体适应环境的保存通过反复迭代(15]。与其他进化算法相比,DE算法有一些优点,比如更好的全局搜索能力,收敛速度快,强鲁棒性。
德的主要步骤包括变异、交叉评价和选择,这是类似于遗传算法。德开始人口,其中包含N随机生成的个体(也称为染色体)。个人用一个向量表示 ,在哪里我表示i个人,G表示当前一代和D表示向量的维数。一步的突变,生成一个捐赠向量 为i个人(称为目标向量)。首先选择三个不同的向量 , ,和从人口。指数是相互排斥的整数随机选择的范围(1,N]。然后,任意两个的差异这三个向量(即,和 )由一个标量扩展因素呢 ,然后按比例缩小的区别是添加到最后一个向量 ;最终获得捐赠向量。这样的过程可以由以下公式表示:
提高潜在的多样性的人口,交叉操作进场后生成捐赠者向量。捐赠者矢量交流其组件与目标向量在这种操作形成了试验向量 。有两个受欢迎的方式交叉DE,指数的交叉(或两点模)和二项交叉(或制服)。本文就介绍了后者,在公式(2),交叉率和Cr是一个随机的数字。的条件保证至少有一个元素的捐赠者向量将被选中。获得试验向量将评估一个预定义的适应度函数。如果试验向量的适应性高于健身目标向量,DE算法将取代试验目标向量的向量;否则,它使目标向量:
3所示。德民:混合进化算法过程的发现
3.1。德民框架
遗传过程挖掘算法,包括GeneticMiner [8],ProDiGen [11),和ETM (12),遭受的问题都需要成百上千的代收敛到一个解决方案。这个问题背后的原因是遗传算子采用完全随机的方法,没有利用日志和错误的信息挖掘模型的解析中痕迹。ProDiGen解决这个问题在一个简单的方法选择一个错误解析活动交叉跨越的一步。但是它并不能显著提高收敛的速度,因为交叉的过程也是随机的。ETM雇佣当地探索alignment-based技术来加速收敛。然而,总运行时间也是不可接受的,因为对齐算法耗时太长。
在这一节中,我将介绍自动化的过程发现的混合进化算法,称为德民。德民的主要步骤如图所示2。从图可以看出,德民与传统进化算法的主要区别是,它需要选择特定的进化策略的循环。一步V是一个基于集合DE算法(缩写为德或DE算法),负责快速近似最优解。然而,通常DE算法陷入局部最优。克服过早收敛,我使用六步,这是一个引导当地探索算法。当地探索算法可以利用错误信息在日志的解析和帮助德民快速跳过局部最优。
德民是在算法的伪代码1。算法跳过循环当一代的数量高于一个预定义的阈值maxGenerations或者是timesNotChange高于maxNotChange。的变量timesNotChange记录多久人口并没有被取代。在循环,两个统计数据,也就是说,meanFitness和devFitness,用于检测算法是否出现过早收敛。前者是指健身的人群,而后者是偏差的健身价值。如果meanFitness和devFitness低于预定义阈值曼氏金融和DF,与此同时,我认为该算法还为时过早。除了两个数据,一个随机数兰德用于条件。这背后的原因是,地方探索算法的全局搜索能力低于DE算法。有时,当地的探索可能会使一个人向前移动,但它可能不会引起重大变化在两个统计数据。因此,该算法将随机选择一个策略如果它落入局部最优。接下来,我将详细介绍这些步骤。
|
3.2。种群初始化
德民中使用的种群初始化方法遵循的启发式方法8),这是基于之间的因果关系的活动。除此之外,有两个变化在我们的方法中,叫做基因库和禁忌列表,可以提高德民的性能。
基因库是一组染色体(即。,个人s), including the individuals that are in current population and the individuals that have been eliminated during the evolution. To reduce the cost of memory space, the individuals in gene bank will be serialized; in other words, they will be converted to a simple format. For example, 将被转换成一个字符串”我(E)= [[B,C]、[D]]。“如果算法生成一个单独的基因银行,个人将被丢弃,没有计算它的健身价值。
禁忌列表保持一组历史操作的地方探索。在德民,一个重要的步骤,引导当地的探索,是用来搜索指定节点。当地的探索需要随机选择的三个操作,添加一个弧,删除一个弧,或重新分配一个节点。执行这些操作,无论他们是有用或无用的,禁止再次被选中。每一个节点都有禁忌列表,这些列表将开始时初始化为空。
3.3。适应度函数
一般来说,两个指标评估流程模型时,应该考虑完整性和精度(16]。完整性量化的能力发现过程模型,它可以准确地解析痕迹记录在事件日志中。一个自然的方式来定义一个完整性度量是正确解析痕迹的数量除以总数量的痕迹。然而,这样的定义太粗,因为它不能正确显示有多少部分个体当个人不正确解析痕迹。考虑两个流程模型:一种是完全不正确的流程模型,和其他的只是错过弧形;上述方法不能区分两个人因为他们不能正确解析日志。因此,我采用部分完整性(8],它考虑了正确解析活动以及令牌的数量,这是在解析缺失或不消耗。我使用了符号”Cf”来表示完整性度量。
发现流程模型可能不合适,即使它变得完整。例如,一朵花模型可以解析任意事件日志,但它是无用的。精度是用来量化的分数所允许的行为模式,这不是在事件日志中看到。然而,很难给出一个适当的精度的定义,因为它必须检测所有的额外的行为,即。在模型中,可能的路径而不是在日志中。在[4),精度的定义 除以 ,在哪里 启用活动当一个日志的数量吗解析的模型 。分母是一个函数返回的最大数量的活动人群中启用。很容易发现,每个单独的精度取决于人口的其余部分。在这个工作中,我认为另一个精确的定义提出了(11)(见公式(3))。很容易发现更多的活动使流程模型,精度越低的流程模型是:
一般,我需要分配加权系数结合加权和的两个指标(17]。然而,很难将这两个指标在一个适当的方式,因为使用精度不是标准化的。因此,分层的方法来定义适应度函数在这工作。因为完整性是更重要的比精度评估发现流程模型时,我首先比较两个流程模型的完整性;如果他们的完整性是平等的,然后比较他们的精度。通过这种方式,当所有人都等于1的完整性,个人有更好的精度会赢。很容易注意到分层适应度函数可以很容易地扩展到其他指标,如结构复杂性和泛化。
3.4。微分进化算法
DE算法包含一个循环通过所有个人的人口。为每个单独的(称为目标个人),它首先生成一个捐赠个人基于三个随机选择的个体(突变操作),然后它结合了目标个人和捐赠个人去试验个人(交叉操作)。必须强调,由于获得的捐赠/试验个人可能不一致,他们两人应该修理之前将下一个步骤。然后,试验个人将评估如果不是基因库。如果的健身价值试验个人高于健身的目标个人,目标个人将取而代之试验个体;与此同时,试验个人将被添加到基因库。可以看出,DE算法有三个关键的步骤,变异、交叉和修复。接下来,三个步骤的细节将被解释的。
3.4.1。突变
当前基于集合的进化算法通常采用脆集代表候选人的解决方案(这被称为个体或染色体在GA)。例如,陈等人。18)提出了一种基于集合的粒子群优化算法的候选解决方案由一组顺序对。然而,因果矩阵是一种更复杂的元素我(活动),O(活动)脆集等 。因此,传统的基于集合的变异算子不能直接用于这项工作。在Ou-Yang的方法9,10),变异算子随机选择从三个个人成分,然后用它们来更新目标个人获得捐赠个人。该方法的优点是,一些好的原料(例如,平行结构)可以直接移植到目标的个体,可以改善GeneticMiner的搜索能力。然而,Ou-Yang的方法不能直接用于这项工作,因为该算法完全基于DE算法。换句话说,它需要更灵活的变异算子。
本节介绍两个新运营商,使该算法执行微分因果矩阵上的突变。以下两个运营商给出的定义。
定义5。两组之间(-操作符)。给定一个因果矩阵 和两套 。相对补的在被定义为
定义6。两组之间(+操作符)。给定一个因果矩阵
和两套
。然后,被定义为
在哪里代表一个广义联合经营意味着它删除元素从
。很容易发现+操作符将保持元素
。这种考虑是背后的原因在公式(4),事实上,结果从公式(3)(又名两组的差异)。通过这种方式,它可以极大地改变的结构和提高潜力试验个体的多样性。
图3给一个说明的例子。鉴于三组代表三个不同的输入集的活动D,
,
,和
。的突变的定义(见公式(1)),它需要首先计算的差异和然后添加的区别
。基于定义5和6,我们可以得到
然后
。注意,比例因子不是用于突变。
(一)
(b)
(c)
(d)
(e)
3.4.2。交叉
交叉的目的是将捐赠的个人和个体生成一个审判个人目标。审判个人会代替目标个人如果健身高于个人目标。有两种流行的交叉方法,指数和二项式。我在这工作采用后者。二项算子的伪代码如下所示。“Cr”被称为交叉率。二项式交叉活动的每一个节点上执行时随机生成的数字0和1之间的“兰德”小于或等于“Cr”(算法2)。“r”是一个随机选择的索引,确保审判个人可以得到至少一个组件从捐赠者的个人。
|
3.4.3。修复
众所周知,个人获得了进化算法的迭代过程总是不一致。例如,它可以得到个人的审判 ,但不包含活动”E”。除此之外,输入的“开始”活动以及“的输出端”活动可能不是空的。因此,需要进行修复操作个人捐赠者的个人以及审判。在遗传过程中挖掘算法,如GeneticMiner ProDiGen,修复操作简单,因为交叉以及变异上执行一个指定的点。修复操作这项工作要复杂得多,因为变异和交叉操作在所有节点上执行一个因果网。换句话说,它需要修复所有节点在一个因果矩阵。介绍的算法修复之前,我首先给一致性的定义一个因果矩阵。
定义7。(因果矩阵的一致性)。让 是一个因果矩阵,我们说它是一致的(1) ,在“开始”开始活动(2) ,“结束”活动结束吗(3)为 , ,在哪里(4)为 , ,在哪里中给出了修复算法的伪代码3。步骤1 - 6节点负责修复“开始”和“结束”节点。首先让和是空的。然后,它将生成一个新的输入(输出)( )如果他们是空的。从步骤7 - 19,算法经过因果矩阵中的所有节点和维修和 ,分别。有两个选择修复操作。输入的修复一个例子;如果输出的不包含 ,它可能随机添加来或删除从 。通过这种方式,我们将最终获得一个一致的个体。
|
3.5。指导地方探索
虽然进化算法,包括GA算法和DE算法,有较强的全局搜索能力,它们都存在着过早收敛的问题。在[14),van Eck等人提出了一个基于对齐的勘探方法。方法,算法是用来找到最优调配流程模型和事件跟踪。
通过这种方式,它可以在流程模型中发现异常区域。然而,alignment-based当地探索有两个缺点。首先,它只能定位异常区域而不是一个节点,这太粗,指导勘探。其次,尽管这项技术可以加快收敛GA算法的执行时间算法是这么长时间,使总执行时间无法忍受。
提出了一种有效而简单的方法指导地方探索,它可以帮助德民跳过局部最优和全球最佳前进。方法是基于口令日志回放,也用于评估过程模型(也称为因果矩阵)的这项工作。原算法对因果矩阵解析日志仅记录三种类型的信息,这是“allParsedActivities”、“allMissingTokens”和“allExtraTokensLeftBehind”。allParsedActivities表示活动正确解析,总数allMissingTokens表示丢失令牌的数量在所有事件的痕迹,和allExtraTokensLeftBehind表示数量的令牌不消耗后解析。在我们的方法中,除了这些,它需要记录的节点解析错误发生,包括令牌小姐在解析或解析后留下的记号。通过这种方式,它可以实现细粒度对所有节点的评价。
很容易发现,该方法有几个优点。首先,它可以准确定位异常节点和提高当地勘探的效率。其次,该方法的时间复杂度远低于extracomputation alignment-based方法,因为它不需要。节点的评价可以完成个人的评价。下面的公式给出了细粒度的评价,在其中代表的分数和代表的分数 :
的伪代码引导当地探索算法所示4。第二步采用轮盘赌为当地的勘探策略,随机选择一个节点。节点较低分数有很大的概率被选中。步骤3随机选择一个方向探索,即。“输入”和“输出。”步骤4-28随机选择一个变异操作,包括随机添加一个弧节点,节点随机删除一个弧,并随机分配的结构节点。一个例子给出的说明再分配操作 ,它可能会 或 后再分配。在算法中,禁忌列表用于记录当地的历史探索。有些操作是无用的(又名不能让个人前进)记录禁忌列表。通过这种方式,它可以提高当地勘探的效率。
|
4所示。实验
在这一节中,我给出了实验和分析。实验的重点是两个方面。第一是评估是否DE算法和引导地方勘探效率,加快算法的收敛速度。第二个是评估算法的性能(又名德民)。接下来,实验中使用的事件日志将被介绍。
4.1。事件日志
在实验中,66事件日志用于评估算法。事件日志可以分为三组。第一组包含从[22人工事件日志,8,19),可以从下载https://svn.win.tue.nl/repos/prom/DataSets/GeneticMinerLogs/。事件日志的描述如表所示2。生成这些日志的过程模型包括不同的结构,如顺序、选择、并行性、循环,和看不见的任务。这些过程模型,表示为佩特里网和启发式网,可以发现在19]。在事件日志,痕迹与相同事件序列分组在一起。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
第二组,用于评估的德民的抗噪能力,包含44事件日志。这些事件日志生成基于事件日志的第一组,分别含有5%和10%的噪音。噪音的产生三种不同类型的操作,包括随机事件添加到跟踪、随机删除一个事件从一个跟踪和随机交换两个相邻事件跟踪。将噪音,原始无噪声的日志被随机选中的痕迹,然后运用三种噪声类型和每一个1/3的概率相等。
第三组包括两个真正的事件日志,都是下载的https://data.4tu.nl/repository/collection: event_logs。第一个事件日志被命名为“BPI2013cp”记录了过程信息从沃尔沃问题管理系统。它包括1487年以及6660年事件痕迹。第二个事件日志被命名为“败血症”记录的事件败血症病例医院ERP系统。它包括1050年以及15214年事件痕迹。
4.2。收敛速度和运行时间
本节介绍了实验的评价DE算法的效率以及引导当地的勘探方法。
本节评估是否DE算法和引导地方探索有效加快算法的收敛速度。四种不同的策略被认为是在这个实验中,DE算法没有地方勘探(DE)表示,DE算法与随机的地方勘探(表示为德+随机搜索),DE算法与当地指导勘探(表示为德+引导搜索),和GA。应该解释说,(1)中使用的随机搜索第二个策略是GeneticMiner基因突变,和(2)第三个策略是德民提出了工作,和(3)GA算法遵循框架在此工作,但使用GeneticMiner的遗传算子。三个指标用于实验的完整性、精密,一代(即。迭代次数)。避免造成实验结果误差随机性,每个算法运行10倍,平均每个指标的价值以及它的计算标准偏差。
事件日志的第一组是用于评估。实验的计算机配备了2.5 GHz CPU和8 GB内存。参数设置如表所示3。应该解释说,人口规模是活动的数量乘以1∼2。“曼氏金融”的参数设置为0.7,因为当地的探索并不希望参与搜索过早。参数“DF”设置为0.2用于检测的过早收敛。事实上,这些参数的微小变化,例如,MF设置为0.6∼0.8和DF将0.1∼0.2,不会影响算法的性能,包括挖掘结果的质量和收敛速度。
|
||||||||||||||||||||||
实验结果如表所示4。出于完整性的考虑,可以看出四个算法(从左到右表31日)总是实现完整性1.00事件日志,10事件日志,20事件日志,分别和12事件日志。结果表明,“纯”DE算法不能实现最好的模型;选择。,我t always falls into local optimum. Then, for precision, the “DE” algorithm achieves the best precision on just one event log. Except that, the “DE + Random Search” and the “GA” achieve the best precision on 2 event logs, and the “DE + Guided Search” achieves the best precision on 14 event logs stably. From the two metrics, it can be seen that the “DE + Guided Search” plays much better than other three strategies. For generation, it requires to exclude the “DE” algorithm because it always suffers from premature convergence. Among the remaining algorithms, it is obvious that the “DE + Guided Search” has the fastest convergence speed and the “GA” has the slowest convergence.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
为了说明德民的时间复杂度,”德+引导搜索”的运行时间也记录,如图所示4。从图可以看出,最小运行时间大约是3秒(“a6nfc”)和最大运行时间是大约80秒(“bn3”)。这证明了时间德民的性能。
(一)
(b)
(c)
(d)
基于上述结果,可以得出一些结论。(1)“DE”算法陷入局部最优。(2)“德+随机搜索”和“遗传算法”可以发现过程模型质量相似,但前者比后者有更快的收敛速度。注意,两个算法使用随机搜索(即。基因突变)。所不同的是,“德+随机搜索”雇佣了DE算法。它证明了DE算法可以快速近似最优解,加快收敛速度。(3)实验结果的基础上“德+随机搜索”和“德+引导搜索,”可以看出,后者比前者达到更好的结果。这解释说,引导当地探索有效帮助DE算法忽略了局部最优,提高德民的搜索能力。
4.3。性能人工事件日志
4.3.1。设置
本节比较了德民三个流行的过程挖掘算法的性能。通过实验,我想评价的性能以及在德民的抗噪能力。选择的过程挖掘算法进行比较,包括启发式矿工(HM) [20.),独立矿工(5),和ETM矿工12]。在这些算法中,英国是一个流行的工具挖掘过程,输出一个启发式网络挖掘的结果,以及独立矿工ETM是两个最先进的矿业领域的算法过程。6.9毕业舞会是最受欢迎的过程挖掘平台是用于实验21]。三个算法的参数设置为默认值。因为独立矿工和ETM输出净和流程树中挖掘结果,分别获得的模型必须被转换成因果矩阵基础上定义4。通过这种方式,四个算法可以通过一个统一的评估方法。特别,如果输出模型包含无形的转换(例如,ETM),它将被转换成因果矩阵。
中定义的四个指标(8,19)被用来评估算法的实验。精度指标包括行为(Bp)、行为回忆(Br),结构精密(Sp)、召回和结构(Sr)。Bp和Br是基于事件的解析日志的挖掘模型和原始模型。前检测多少行为所允许的开采模型不是由原模型。后者相反的检测。此外,英国石油公司和Br的值越接近1.0,相似性越高原始和挖掘模型。Sp和Sr指标是基于因果关系的挖掘和原始模型,前者检测多少因果关系挖掘模型不是在原始模型中,相反,后者检测。不同于英国石油公司和Br, Sp和Sr测量结构的相似性的观点。当原始模型的连接没有出现在开采模型,将值小于1,,同样的,当开采模型连接,不出现在原始模型中,Sp值低于1.0。
4.3.2。无噪声的事件日志
首先,实验进行22无噪声的事件日志。表中列出的结果5在每个日志,最好的结果是斜体。的结果,很容易发现德民的性能略优于其他三种算法。(即德民达到最优解决方案。,four metrics are equal to 1) on 18 event logs. The HM, ILP Miner, and ETM achieve the optimal solutions on 16 event logs, 14 event logs, and 5 event logs, respectively. To compare the four algorithms more intuitively, a combinatorial metric, called averagef分数,设计,如下所示:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
结果如图所示5。从图中,很容易发现德民只输给了其他算法四个事件日志,这是“a5,”“a7,”和“a6nfc, h6p18。“除此之外,德民获得最好的结果在其余18事件日志。此外,平均f分数通过德民在其余4事件日志是超过0.9。它表明,德民具有良好的性能。后,深入分析。
有四个事件日志,德民无法达到最好的效果,这是“a5,”“h618,”和“a7, h6p36。”的挖掘结果重复最常在图所示6。在图中,已经被红色标记错误的部分。此外,虚线表示失踪的弧(a.k.。在原始模型而不是由德民),发现和实线表示不正确的连接(又名结构性错误)。
(一)
(b)
(c)
(d)
在图6(一),可以看出开采模型缺乏一个周期<E,E>。在原始模型中,有两个周期节点”E”。这一现象背后的原因是微分突变的运营商提出了工作(定义5和6)将删除此类结构在演变。假设S1 = {{E},{E},{B,C}}和S2 = {{E},{B}},然后S1-S2 = {{B,C}};换句话说,两个子集{E}将从S1 -操作。此外,假设S1 = {{E},{E},{B,C}}和S2 = {{E},{B,C}};很容易发现,两组将获得相同的完整性价值,但S1的精度值低于S2(启用前有更多的活动)。换句话说,S1将取代S2在进化。同样,这种现象也出现在事件日志“h6p18。”
接下来,在开采模型输入的节点集“a7,D”{{2,4},{3、7、8}},这是{{2},{3、7},{4 7 8}}在原始模型。这背后的原因不正确也差变异操作。很容易发现,去除两组交叉的部分算法是一个高概率的事件。假设两个集合S1 ={3、7}和S2 = {4 7 8}, S1 + S2 ={{3、7},{8}}的定义6。可以看出,两个集合的交集。从上面的分析,可以发现,该方法不能实现最好的结果在某些罕见的情况下(例如,两个圆在同一节点和现有的冗余的结构)。然而,从另一个角度来看,这表明该方法更喜欢较低的模型结构的复杂性。
“h6p36”四个算法发现相同的模型如图6 (d)。挖掘模型缺乏两个弧< KB, NB >和< KA, NA >,它存在于原始模型(启发式净)19]。通过分析,我发现原来的启发式网络是不正确的。CPN模型的“h6p36”,可以看出,该模型就有两个并行路径入手分别“卡”和“KB,”。然而,给启发式网络有两个弧,即。,
4.3.3。嘈杂的事件日志
接下来,实验进行了22日事件日志以5%的噪音。实验结果如表所示6。HM的性能将显著下降。噪音还会影响其他两种算法,但其性能下降小于HM算法。此外,ETM也可以发现最优流程模型”paral5”,没有达到最好的效果。同样,平均f分数的四个算法计算(见图7)。从图可以看出,德民的性能略有降低,达到最好的结果13日事件日志。此外,平均f德民的得分在0.8和1.0之间。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
之后,实验进行事件日志以10%的噪音。实验结果表中列出7,平均f分数的四个算法如图8。从表中,我们可以看到德民达到最好的结果14日事件日志,和其他三个算法(从左到右)达到最好的模型2,7,分别和4事件日志。ETM发现我们可以看到最优模型a7和a8,“含有10%的噪音,但它确实没有找到最优模型在相同的日志,有5%的噪音。这是因为两个日志是独立的;即。,the inserted noise may be totally different. Through careful comparison of Figures7和8,它可以发现德民的表现不显著降低,保持在一个稳定的水平。两组实验的基础上与噪声事件日志,可以得出一个结论,德民具有良好的抗噪能力。然而,我们应该注意到德民不能发现所有事件日志上的最优解与噪音。这一现象表明,德民还不能避免噪音干扰。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4.4。表现真实的事件日志
本节展示德民的性能在两个真正的事件日志,即。、“BPI2013cp”和“脓毒症。“在实验中,一个“开始”活动以及“结束”事件被添加到每个跟踪运行时间。它确保每个路径节点具有相同的“开始”和“结束”节点。消除进化的随机性,德民是执行在每个事件日志的10倍。进化的过程在两个事件日志数据所示9和10,分别。纵坐标表示完整性度量,横坐标表示后代的数量,这是比例从1到100。在这里,我只记录完整性价值因为它是单调的。相反,精度值可能会有极大的完整性的变化值。从这两个数字,可以看到在两个事件日志德民收敛快。
此外,三个指标用来评估德民的效率,这是alignment-based健身(22),alignment-based精度(23),的总和f分数(24]。计算结果,包括平均值和标准差,表中列出8。而给出的结果(24),很容易发现德民的结果略低于ETM的结果“败血症”,和德民比获得的结果的结果获得的ETM“BPI2013cp”。这证明德民可以发挥真正的事件日志。
|
||||||||||||||||||||||||
5。结论
本文提出了一种新的过程挖掘算法,名叫德民。该算法是基于混合进化策略,它包含一个基于集合的算法和引导当地探索算法。与此同时,一些技术用来提高德民的效率,比如基因库,禁忌列表和稠度修复。评价性能,68事件日志被用于实验。根据实验结果可以得出一些结论:(1)通过比较四种不同的策略(即。,德,德+随机搜索,德+引导搜索,和遗传算法),the “DE + Guided Search” outperforms the rest strategies and it can achieve the best quality solution as well as the fastest convergence speed. Moreover, the results prove that the DE algorithm can rapidly approximate the optimal solution, but it always suffers from premature convergence. The guided local exploration can help the DE algorithm skip out the local optimum and improve the efficiency of the proposed algorithm.(2)通过比较性能的过程挖掘算法(即德民三个受欢迎。,嗯,独立矿工,和ETM)on 22 noise-free event logs and 44 noisy event logs, it shows that the DEMiner can achieve the best result on most of the event logs. Furthermore, based on the experimental results on 2 real event logs, it can be concluded that the DEMiner can work well on real-world events logs. This proves the effectiveness and the efficiency of the proposed algorithm.
然而,我们可以看到德民没有成功地发现最优的流程模型从任何一个44的事件日志。这演示了德民的缺点。除此之外,很难发现一些罕见的德民结构,如两个圆上一个节点。这是对我们未来的工作。
数据可用性
事件日志用于支持本研究的结果都包含在这篇文章中,可以下载https://svn.win.tue.nl/repos/prom/DataSets/GeneticMinerLogs/。可以找到相应的过程模型(19]。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是支持的科技项目局乐山(批准号18 jzd117)、乐山师范大学科学研究基金(批准号ZZ201822),中国四川省教育部重点项目(批准号18 za0239)和关键网络自然语言处理实验室的项目四川省教育部门(没有。INLP201903)。
引用
- w·m·p·范德阿尔斯特过程挖掘:数据科学行动斯普林格出版社,柏林,德国,第二版,2016年版。
- w·范德阿尔斯特、t . Weijters和l . Maruster”工作流挖掘:从事件日志发现过程模型,”IEEE工程知识和数据,16卷,不。9日,第1142 - 1128页,2004年。视图:出版商的网站|谷歌学术搜索
- a . Medeiros b .幅w·m·p·范德阿尔斯特et al .,“无处不在的移动系统的过程挖掘:概述和具体算法,”程序无处不在的移动信息和协作系统里加,页156 - 170年,拉脱维亚,2004年6月。视图:谷歌学术搜索
- l .温w·m·p·范德阿尔斯特j . Wang和j .太阳”与non-free-choice结构挖掘过程模型”,数据挖掘和知识发现,15卷,不。2、145 - 180年,2007页。视图:出版商的网站|谷歌学术搜索
- s . j . van Zelst b·f·凡·通根于w·m·p·范德阿尔斯特和h . m . w . Verbeek“发现工作流使用整数线性规划网,”计算,卷100,不。5,529 - 556年,2018页。视图:出版商的网站|谷歌学术搜索
- 美国j。j Leemans、d . Fahland和w·m·p·范德阿尔斯特”发现对流程模型从包含罕见的行为,事件日志”学报2013年的业务流程管理研讨会,第78 - 66页,北京,中国,2013年8月。视图:谷歌学术搜索
- 美国j。j Leemans、d . Fahland和w·m·p·范德阿尔斯特“可伸缩过程发现和一致性检查”软件和系统建模,17卷,不。2、599 - 631年,2018页。视图:出版商的网站|谷歌学术搜索
- a . k . a . de Medeiros a·j·m·m·Weijters和w·m·p·范德阿尔斯特“遗传过程挖掘:一个实验评估,”数据挖掘和知识发现,14卷,不。2、245 - 304年,2007页。视图:出版商的网站|谷歌学术搜索
- 周宏儒。程、c . Ou-Yang和研究。胡安,”一个混合方法来提取业务流程模型与健身和精度高,“工业和生产工程杂志》上,32卷,不。6,351 - 359年,2015页。视图:出版商的网站|谷歌学术搜索
- c . Ou-Yang周宏儒。程,研究。胡安。”一个集成的采矿方法,发现业务流程模型与平行结构:对健康改善,”国际期刊的生产研究,53卷,不。13日,3888 - 3916年,2014页。视图:出版商的网站|谷歌学术搜索
- b Vazquez-Barreiros、m . Mucientes和m .喇嘛”ProDiGen:矿业完整,准确和最小的结构与遗传算法流程模型,”信息科学卷,294年,第333 - 315页,2015年。视图:出版商的网站|谷歌学术搜索
- j . c . A . m . Buijs b·f·凡·通根于和w·m·p·范德阿尔斯特“遗传算法用于发现流程树,”《IEEE国会进化计算布里斯班,澳大利亚,页1 - 8,2012年6月。视图:出版商的网站|谷歌学术搜索
- j . c . a . m . Buijs b·f·凡·通根于w·m·p·范德阿尔斯特et al .,“健身的作用,精度、概括和简化过程中发现,”《移动会议有意义的网络系统,页305 - 322,罗马,意大利,2012年9月。视图:谷歌学术搜索
- m . l . van Eck j . c . a . m . Buijs和b·f·凡·通根于“遗传过程挖掘:流程模型alignment-based突变,”业务流程管理研讨会施普林格,页291 - 303年,可汗,瑞士,2014。视图:谷歌学术搜索
- s Das和p . n . Suganthan微分进化:最新的一项调查,”IEEE进化计算,15卷,不。1,4-31,2011页。视图:出版商的网站|谷歌学术搜索
- w·范德阿尔斯特,a . Adriansyah和b·凡·通根于“历史重演在流程模型一致性检查和性能分析,“威利跨学科评论:数据挖掘和知识发现,卷2,不。2、182 - 192年,2012页。视图:出版商的网站|谷歌学术搜索
- 黄许,陈x, x h . l .道,“一个multistrategy-based多目标微分进化化学过程的最优控制,”复杂性卷,2018篇文章ID 2317860, 22页,2018年。视图:出版商的网站|谷歌学术搜索
- h·s·h·w·n·陈,j . Zhang涌et al .,”一个新颖的基于集合的粒子群优化方法离散优化问题,“IEEE进化计算,14卷,不。2、278 - 300年,2010页。视图:出版商的网站|谷歌学术搜索
- a·k·阿尔维斯de Medeiros“遗传过程挖掘,埃因霍温科技项目,埃因霍温,荷兰,2006年博士论文。视图:谷歌学术搜索
- a·j·m·m·Weijters和j·里贝罗,“灵活的启发式矿工(《男人帮》),”《IEEE研讨会上计算智能和数据挖掘,页310 - 317年,巴黎,法国,2011年4月。视图:出版商的网站|谷歌学术搜索
- b·凡·通根于a·k·阿尔维斯de Medeiros h . m . w . Verbeek et al .,“舞会框架:一个新时代的过程挖掘的工具支持,”学报》第26届国际会议应用程序和佩特里网的理论,页444 - 454,迈阿密,佛罗里达,美国,2005年6月。视图:谷歌学术搜索
- a . Adriansyah b·凡·通根于和w·m·p·范德阿尔斯特“一致性检查使用基于成本的适应性分析,”学报》第十五届IEEE国际企业分布式对象计算会议,55 - 64页,芬兰赫尔辛基,2011年8月。视图:出版商的网站|谷歌学术搜索
- a . Adriansyah j . Munoz-Gama j·卡蒙et al .,“基于对齐精度检查,”业务流程情报学报》国际研讨会爱沙尼亚塔林,页137 - 149,,2012年9月。视图:谷歌学术搜索
- a·奥古斯托·r·Conforti m·杜马斯et al .,“自动发现过程模型的事件日志:审查和基准,”IEEE工程知识和数据没有,卷。31日。4、686 - 705年,2019页。视图:出版商的网站|谷歌学术搜索
版权
版权©2020思源。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。
