基于行为轮廓和逻辑Petri网的模型修复方法.pdf

2023 08 10计算机应用,Journal of Computer Applications2023,43(8):2527-2536ISSN 10019081CODEN JYIIDUhttp：/基于行为轮廓和逻辑Petri网的模型修复方法张昊宇1，王丽丽1，2*（1.安徽理工大学 数学与大数据学院，安徽 淮南 232001；2.安徽省煤矿安全大数据分析与预警技术工程实验室（安徽理工大学），安徽 淮南 232001）（通信作者电子邮箱）摘要：现实中的业务流程不断发生变化，需要对初始的业务流程模型进行修复以更好地表示实际业务流程。模型修复的关键步骤是分析现实日志和模型间的偏差，目前寻找偏差的方法主要采用对齐重演技术，未从行为的角度定量分析抽象的结构。因此，提出了一种通过行为轮廓分析日志和模型偏差的方法，并在此基础上进一步给出了基于逻辑Petri网的模型修复方法。首先，基于行为轮廓计算日志和模型间的服从度以识别偏差迹；然后，在偏差迹中依据偏差三元组集从偏差活动中选择逻辑变迁；最后，基于逻辑变迁设置逻辑函数，并通过添加新的分支或重构新的结构来修复原模型。对修复模型的适应度和精确度进行了验证，仿真实验结果表明，在尽可能保持修复模型与原始模型相似的基础上，相较于Fahland方法与Goldratt方法，所提修复方法在适应度都为1的情况下，得到的修复模型具有更高的精确度。关键词：行为轮廓；业务流程；逻辑Petri网；过程挖掘；模型修复中图分类号：TP301.1 文献标志码：AModel repair method based on behavioral profile and logical Petri netsZHANG Haoyu1，WANG Lili1，2*（1.School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan Anhui 232001，China；2.Anhui Province Engineering Laboratory for Big Data Analysis and Early Warning Technology of Coal Mine Safety（Anhui University of Science and Technology），Huainan Anhui 232001，China）Abstract:In the circumstance of the real business process changing constantly，the original business process model needs to be repaired to better represent the real business process.The key step of model repair is to analyze the deviation between the real log and the model.However，the current methods to find the deviation mainly use the alignment repetition technique，and do not quantitatively analyze the abstract structure from the perspective of behavior.Therefore，a method of analyzing deviation between log and model by behavioral profile was proposed，and based on the above，a model repair method was further proposed on the basis of logical Petri nets.Firstly，based on the behavioral profile，the compliance between the log and the model was calculated to identify the deviation trace.Secondly，the logic transitions were selected from deviant activities through the deviant triple set in the deviation trace.Finally，the logic function was set based on the logic transitions，and the original model was repaired by adding new branches or reconstructing new structures.The fitness and precision of the repair models were verified.Simulation results show that when the all finesses are 1，the repair model obtained by the proposed repair method has higher precision compared with Fahland method and Goldratt method，on the basis of maintaining the similarity between the repair model and original model as much as possible.Key words:behavioral profile;business process;logical Petri net;process mining;model repair0 引言 近年来，随着互联网技术的发展，业务流程管理和在线事件流监控的方法得到进一步扩展，企业和各大组织均使用信息系统来检测分析业务流程。大量的事件日志在信息系统的执行过程中产生，为过程挖掘技术提供了基础，从而提取有价值的信息，用于进行过程发现、一致性检测和过程增强1。过程发现技术从事件日志中自动构造过程模型（例如Petri网或业 务 流 程 建 模 标 注（Business Process Modeling Notation，BPMN）模型）2；一致性检测用于分析事件日志与过程模型之间存在的偏差；过程增强利用事件日志对原始模型增添或改进3-6，模型修复是过程增强中的一项技术，通过事件日志对过程模型进行修复，使修复后的模型具有更理想的适应度和精确度7。现有的一致性检测中有很多不同的方式，如早期可能会导致不稳定或模糊结果的“token-replay”方法8，后来出现并逐渐成为主流一致性检验技术的“对齐”方法9，以及为了迎合不断增加的数据流而出现的在线一致性检测技术，它基于前缀对齐联系事件流与过程模型，从而进行过程监控10。国内外学者也提出许多检测算法：Schuster等11使用前缀对齐在文章编号：1001-9081（2023）08-2527-10DOI：10.11772/j.issn.1001-9081.2022070980收稿日期：20220707；修回日期：20221212；录用日期：20221213。基金项目：国家自然科学基金资助项目（61572035）；安徽省高校优秀人才支持计划项目（gxyqZD2020020）；安徽省重点研究与开发计划项目（2022a05020005）。作者简介：张昊宇（1998），男，安徽合肥人，硕士研究生，主要研究方向：Petri网、模型修复；王丽丽（1982），女，安徽安庆人，副教授，博士，主要研究方向：Petri网、可信计算。第 43 卷计算机应用增量状态空间中进行一致性检测的计算，能够在保证最优性的同时，使事件流上前缀对齐的计算可以在具有不同目标状态的扩展搜索空间上从先前的结果继续；Sani等12提出一种使用上下界的一致性检测新方法，不考虑过程模型和事件日志中可用迹之间的精确对齐，只考虑过程模型中可能行为的一个子集，并通过它来使用编辑距离函数逼近一致性值。过程增强使用事件日志进一步扩展或改进模型13。例如信息系统中所产生的事件日志可以通过过程挖掘技术发现和改进业务流程模型14，但随着业务流程的扩展，现实中很多情况下挖掘的过程模型并不能完美地重放事件日志，导致挖掘的原始模型失去价值，造成资源的浪费15。此时采用模型增强中的模型修复技术可以修复原模型，能够正确地表述实际的业务流程16-19。模型修复是一种过程挖掘的新方式，通过输入事件日志和过程模型找出模型中与日志不匹配的部分进行修复，修复后的模型可以正确重放事件日志，并尽可能保留原始模型特点20-21。例如，模块化方法22基于扩展对齐，对过程模型进行分块，将劣子模型进行修复并与优子模型结合对原模型进行修复。Fahland方法23基于最优对齐寻找日志和模型间存在的偏差，使用一致性检测将给定的流程模型与日志中的迹对齐，然后把日志分解为多个子日志。对于每个子日志，发现一个可以重放子日志的循环或是子流程，使用添加沉默变迁或从日志中提取子过程将其以自环形式嵌入原模型中的方式修复模型。Polyvyanyy方法24研究模型修复过程中如何减少资源损耗的问题，并提出了不同的替代方法加快修复速度，使得对齐计算的数量显著减少的同时仍可以接近最佳的模型修复。Knapsack方法25通过将单个活动以自循环的方式插入原始模型中修复。Goldratt方法26采用与Knapsack方法不同的约束函数处理资源损耗，但修复方式均为向模型中添加了一个自循环或沉默变迁。这些方式通过增加子进程或子模块的方式提高了适应度，但同时也增加了模型的复杂度和冗余。本文使用基于行为轮廓的服从度检测存在偏差的迹27，通过逻辑Petri网建模修复原模型，基于行为的服从度反馈信息能更直观和快速地反映存在问题活动间的关系，逻辑 Petri 网相较于普通Petri网添加了逻辑控制变迁，提高了修复模型的简洁度并能够正确描述活动间的逻辑关系28-29。1 动机例子 下面给出一个过程模型和一组事件日志如图1和表1所示，其中代表事件日志中的可执行迹，ao代表业务流程中的 可 执 行 活 动，例 如1代 表 一 条 活 动 序 列 为a，b，c，d，e，j，k，l，o。当将实际事件日志重演于过程模型时，在选择和顺序结构中会存在偏差问题，如1、2和3中活动a发生之后，分别选择模型PM（Petri Model）的两个不同分支，在模型中能正确重演；但4在发生了活动a和活动f后，并没有发生f的直接后继活动g，而是选择另一个选择分支上的活动c和活动d继续执行。此时不难发现对于这种选择结构，当将日志重放于模型时存在选择偏差，本文将此类偏差称为选择结构中的路径选择偏差问题。同理对于5和6除了发生活动k所在选择分支中的所有活动之外，还发生了另一个选择分支上的活动n，显然与模型的可执行迹存在偏差，进一步分析发现，活动l与活动n在行为上存在并发关系，因此在本文将此类偏差称为选择结构中的并发执行偏差问题。对于7、8和9在活动a发生后，活动f与活动g的执行顺序并没有严格按照顺序的关系发生，但它们都仍在一条迹中执行，对于这种并发结构，本文将此类偏差称为顺序结构中存在活动并发执行的问题。综上，日志在模型中重演时：1）由 4 可知，日志和模型在选择结构中存在路径选择偏差的问题；2）由 5，6 可知，日志和模型在选择结构中存在活动并发执行的问题；3）由 7，8，9 可知，日志和模型在顺序结构中存在活动并发执行的问题。因此图1中所示的过程模型PM并不能正确反映表1中事件日志Log所描述的业务流程，本文需要通过模型修复技术，在保持与原模型尽可能相似的前提下，修复原模型以更好地描述现实日志。目前的模型修复方法大多通过添加自环和沉默变迁修复模型，较少关注到活动间的行为逻辑关系。本文采用文献26 所给出的Goldratt方法利用表1中的事件日志修复图1所示的过程模型PM，得到如图2所示的修复后模型PM。图2Goldratt方法修复后模型PMFig.2Repair model PM by Goldratt method对于图2所示的修复模型，通过10组事件日志集分析模型质量，实验结果如图3所示。从图3可以看出，Goldratt方法修复后的模型虽然适应度达到了1，但因为在并发和循环结表1实际事件日志Tab.1Real event log迹12345活动a，b，c，d，e，j，k，l，o a，b，d，c，e，j，m，n，o a，f，g，h，i，j，k，l，o a，f，c，d，i，j，k，l，o a，b，c，d，e，j，k，n，l，o迹6789活动a，b，c，d，e，j，m，l，n，oa，f，h，i，j，k，l，o a，g，i，j，k，l，o a，g，f，h，i，j，k，l，o 图1Petri网模型PMFig.1Petri net model PM2528第 8 期张昊宇等：基于行为轮廓和逻辑Petri网的模型修复方法构中添加了自环和沉默变迁，导致模型产生了大量额外的可执行迹，使得模型的简洁度和精确度都有所下降，并且不能描述活动间的行为逻辑关系。针对上述问题，本文提出了基于行为轮廓和逻辑Petri网的模型修复方法。从活动间的行为关系角度出发，首先通过分析活动间的行为轮廓关系提供偏差反馈；然后通过反馈的偏差三元组信息选择不同类型的逻辑变迁；最后开展模型修复方法研究。并通过实验验证了本文方法在保证模型能够正确重放实际事件日志的前提下，提高了模型的精确度并使得修复后的模型尽可能与原模型相似。2 基础概念 本文使用Petri网对业务流程进行建模，Petri网是用于描述分布式系统的一种模型，它既能描述系统的结构，又能模拟系统的运行，描述系统结构的部分称为网，它可以通过对业务模型的优化和配置约束的添加来满足用户的使用需求28。定义12 流程模型。设=(A，ai，a0，C，F，T)为一个六元组的流程模型，其中：1）T为一个非空的活动变迁节点集，C为控制流的节点集，A和C互不相交；2）ai A为一个最初的活动变迁，a0 A为一个最终的活动变迁；3）F (A a0)C (A a)C为流关系；4）T：C and，or，xor 为流程模型控制流的类型。定义 22 行为轮廓。设一个网系统(N，M0)，其中N=(P，T，F)初始标识是M0。对于任意给定的变迁(t1，t2)(T T)，满足以下关系：若t1 t2，且t2 t1，则称为严格序关系，记作t1 t2；若t1 t2，且t2 t1，则称为排他序关系，记作t1+t2；若t1 t2，且t2 t1，则称为交叉序关系，记作t1|t2；若t1 t2，且t2 t1，则 称 为 严 格 逆 序 关 系，记 作t1-1t2。将以上几种关系构成网N的行为轮廓，记为BP=，-1，+，。定义31 可达性。已知Petri网PN=(P，T；F，M)，如果存在t T，使M t M，则称M为从M直接可达的。如果存在变迁序列t1，t2，tk和标识序列M1，M2，Mk使得：M t1 M1 t2 M2 Mk-1 tk Mk则称Mk为从M可达的，从M可达的一切标识的集合记为R(M)。定 义 41 变 迁 发 生 规 则。一 个 四 元 组PN=(P，T；F，M0)称为Petri网，并具有下面的变迁发生规则：1）变 迁t T具 有 发 生 权，当 且 仅 当 对P t：M(P)1，记作M t。2）在标识M下能使得变迁t经发生后，得到一个新的标识M，记作M t M，则有：M(p)=M(p)+1，P t-tM(p)-1，P t-tM(p)，其他定义53 迹与事件日志。设A是所有活动的集合。若活动序列 A*，A*表示集合A上有限序列的集合，则称是一条迹。若L B(A*)是迹的一个多重集，称L为一个事件日志。定义61 一个工作流网是合理的当且仅当：1）对于任意的标识，都存在一个发生序列M，使得初始库所可以通过M到达终止库所。2）通过一个初始标识发生而发生的中间标识，如果此时的终止库所里至少有一个token，该状态就是终止状态。终止时，该工作流网终止库所中有且仅有一个标识，并且整个工作流程只有唯一的一个标识。3）无死锁，即该Petri网是活的。逻辑Petri网是Petri网的一种扩展形式，可以在保留Petri网功能的基础上，通过活动间的业务逻辑关系对路径进行约束，构造输入输出的逻辑表达式限制变迁的输入输出，保证了模型的拟合度和精确度。定义74 LPN=(P，T；F，I，O，M)是一个逻辑Petri网，当且仅当：1）P是一个有限库所集。2）T=TI TO TD是一个有限变迁集，若t TI TO，则t t=。a）TD表示Petri网中的变迁集；b）TI表示逻辑输入变迁集，对t TI，t的输入集t受逻辑表达式fI(t)的约束；c）TO表示逻辑输出变迁集，对t TO，t的输入集t受逻辑表达式fO(t)的约束。3）F (P T)(T P)是一个有限弧集。4）I表示逻辑输入变迁到逻辑输出变迁的映射，对t TI，有I(t)=fI(t)。5）O表示逻辑输出变迁到逻辑输入变迁的映射，对t TO，有O(t)=fO(t)。6）映射M：P 0，1是一个标识函数，对p P，M(p)表示p中含有的token数。7）变迁触发规则：a）对t TD，变迁引发规则与传统Petri网一致。b）对t TI，若fI(t)|M=.T.，则逻辑输入变迁t可引发，记 作M t M，且 对 于p t，M(p)=0；对p tt，M(p)=M(p)；对p t，M(p)=1。c）对t TO，若fO(t)|M=.T.，则逻辑输出变迁t可引发，记 作M t M，且 对 于p t，M(p)=0；对p tt，M(p)=M(p)；对p t，M(p)满足fO(t)|M的约束。8）对t TI和p1，p2t，t的逻辑输入函数为：a）I(t)=p1 p2表示当且仅当M(p1)=1且M(p2)=0，或M(p2)=1且M(p1)=0时，有M t；b）I(t)=p1 p2表示当且仅当M(p1)=1且M(p2)=1时有M t；c）I(t)=p1 p2表示当且仅当M(p1)=1或M(p2)=1时有M t；9）对t TI和p1，p2 t，t的逻辑输出函数为：a）O(t)=p1 p2表 示 当M t 时，有M(p1)=1且图3Goldratt方法修复模型的适应度与精确度Fig.3Fitness and precision of Goldratt method for repairing model2529第 43 卷计算机应用M(p2)=0，或M(p2)=1且M(p1)=0；b）O(t)=p1 p2表 示 当M t 时，有M(p1)=1且M(p2)=1；c）O(t)=p1 p2表 示 当M t 时，有M(p1)=1或M(p2)=1；令集合SL中包含LPN中所有完全触发序列。如图4所示为一个简单的逻辑Petri网，图内变迁a为一个逻辑输入变迁，变迁c是逻辑输出变迁。I(a)=p1p2是变迁a的逻辑输入函数，表示若需要变迁a可以发生，只有两种情况：仅p1中token；仅p2中有token。O(c)=p5(p6 p7)是变迁c的逻辑输出函数，它表示变迁c发生后，p5、p6和p7中至少有一个token，且p5不能和p6、p7同时存在token。定义827 行为轮廓服从度。设c=(n1，n2，nm)是一个案例，P=(A，ai，a0，C，F，T)是一个过程模型，其中Ac A：1）PCc是行为轮廓一致的案例集合，PCc(Ac Ac)包含（x，y）所 有 的 活 动 对，其 中 c 的 行 为 关 系 包 含 在 P 中，R (BP -1P)，R (BC -1c)使得(xRy xRy)S(R，R)。2）c 对 P 的模型相对行为轮廓服从度（Model-relative Behavioural-profile Compliance，MBCc）：MBCc=|PCc|Ac|23）c对 P的约束相对行为轮廓服从度（Constraint-relative Behavioural-profile Compliance，CBCc）：CBCc=1，|c=(Ac Ac)|PCc|c|Ac Ac|c|2，其他定义927 因果行为轮廓。设P=(A，ai，a0，C，F，T)是一个过程模型：1）(x，y)(A A)是一对共现关系P，对于所有的可执行序列=n1，n2，nm，在p中有ni=x(1 i m)就意味着有一个j i，i+1，m，例如nj=y。2）B+P=BP P是P的因果行为轮廓。定义1027 服从度违反三元组。设c=n1，n2，nm是过程模型P=(A，ai，a0，C，F，T)的一个案例，B+P是关于P的因果行为轮廓，PCc是行为约束案例对的集合，EAc是预期案例活动的集合：服从度违反三元组的集合Vc(A A B+P)，定义Vc(A A B+P)|x EAc x y x y y Ac，(x，y)PCi3 基于行为轮廓服从度的模型修复方法 本章针对现实日志中不产生新活动的情况下，分别对选择结构和顺序结构中出现的异常行为开展研究，介绍了服从度检测的基本概念并对初始模型进行修复。3.1选择结构中的模型修复3.1.1选择结构中分支跳转的模型修复对于业务流程中，选择结构中的路径选择偏差问题，图5为原模型PM问题1所对应子结构的BPMN模型图，Petri网模型M1如图6所示。实际事件日志Log1=1，2，3，其中1=a，f，g，h，i，j；2=a，b，c，d，e，j；3=a，f，c，d，i，j。同 理 于问题1，实际事件的流程与原模型存在偏差，变迁活动f与变迁活动c、d在模型中互为排他关系，但它们同时在事件日志Log1的2中执行。使用服从度结果判断事件日志中存在问题的迹，从服从度反馈得到的三元组信息中筛选出所需要的变迁活动，这些活动在日志的迹中实际发生，依据行为轮廓关系找到迹中与原模型存在偏差关系的活动，使用逻辑Petri网修复原Petri网模型。由定义8可以得到Log1的服从度结果如表2所示，根据结果可知4的活动间行为轮廓关系存在异常。上述两种服从度值的范围都在01：数值为0表示为完全不符合的行为轮廓关系；数值为1表示为完全符合的行为轮廓关系。对于表2中Log1的服从度结果，1和3表示为完全触发序列集中的一种，为完全符合的行为轮廓关系；4所显示的活动顺序并不能成功地在图6中完全触发，迹中出现的活 动 违 反 了 模 型 中 的 互 斥 关 系，例 如f+c，f+d，d+i和i+c，量化这些违规的活动相较于所考虑的活动数，可以得到模型相对行为轮廓服从度值：MBCc=28/36=0.78。忽略对交叉顺序c和d的约束，就得到了这种情况下的约束相对行为轮廓服从度：CBCc=26/34=0.76。由定义9和定义10可以得到事件日志Log1的4中存在问题的节点以及行为轮廓关系如下所示：（a，b，），(f，h，），(c，b，），(c，e，），(d，b，），(d，e，），(i，g，），(f，c，+)，(f，d，+)，(c，f，+)，(c，i，+)，(d，f，+)，(d，i，+)，(i，c，+)，(i，d，+)，(i，h，-1)，(f，g，)，(j，e，-1)，(g，h，)，(h，g，-1)算法1生成选择后的服从度违反三元组集，定义为偏差图4逻辑Petri网示例图Fig.4Example diagram of logical Petri net图5BPMN模型Fig.5BPMN model图6Petri网模型M1Fig.6Petri net model M1表2Log1的服从度结果Tab.2Compliance results of Log1迹1=a，b，c，d，e，j3=a，f，g，h，i，j4=a，f，c，d，i，jCBC1.001.000.76MBC1.001.000.782530第 8 期张昊宇等：基于行为轮廓和逻辑Petri网的模型修复方法三元组集，具体执行步骤如下：第1）行初始化服从度违反三元组集Vc和筛选后的偏差三元组集Vc；第2）行定义了服从度违反三元组的集合，三元组中的元素分别为迹中的活动和模型中活动间的行为轮廓关系；第3）4）行遍历了事件日志中的迹和迹中的活动；第5）6）行中遍历出的活动若存在Vc中，则将包含此活动Vc中的三元组添加到Vc中，得到筛选后的偏差三元组集。算法1 偏差三元组集的生成算法。输入 事件日志L，过程模型PM；输出 偏差三元组集Vc。1）Vc=，Vc=2）Vc(A A B+P)|x EAc x y x y y Ac，(x，y)PCi3）for（i=1，i L；i+，i|L|）do4）for（j=1；j+；j|EAi|）do5）if EAi j Vc|(x，y，R)，x=EAi j y=EAi j，(x，y)PCi then6）Vc=Vc Vc j 7）else8）continue9）end for10）end for11）return Vc例如前文中4的不合规反馈，为算法1第2）行Vc集，运行算法1后得到的Vc=（a，b，），（f，h，），（c，b，），（d，b，），（d，e，），（i，g，），（f，c，+），（f，d，+），（c，f，+），（c，i，+），（d，f，+），（d，i，+），（i，c，+），（i，d，+），（i，h，-1），（j，e，-1）。算法2在使用算法1筛选得到偏差三元组集后，通过排他与顺序的行为轮廓关系判断输出和输入逻辑函数，并通过增加活动间的选择分支修复原模型。具体执行步骤如下：第1）行初始化修复模型；第2）行调用选择算法得到偏差三元组集Vc；第3）行选择Vc集中存在排他序关系的活动对；第4）23）行基于选择路径上活动间行为轮廓关系考虑，通过筛选三元组中的活动更新P、T、F、O和M；第24）27）行寻找偏差活动设置逻辑输入变迁修复模型。算法2 选择关系中跳转分支的模型修复算法。输入 事件日志L，过程模型PM；输出 基于逻辑Petri网的修复模型LPN=(P，T；F，I，O，M)。1）LPN=2）调用算法1得到选择后的偏差三元组集Vc3）for(x，y，+)Vc do4）if(z y1，y2，y3，yn)and(z+y1，y2，y3，yn)and(y1)=(y2)=(yn)then5）P=P P6）T=T T7）F=F(x y1)(x y2)()x yn8）if(x，z，)Vc then9）O=O O(x)=z(y1 y2 yn)10）else if(x，z，)Vc and (z1)=(z2)=(zn)，then11）O=O O(x)=(z1 z2 zn)(y1 y2 yn)12）else13）O=O O(x)=z(y1 y2 yn)14）M y M15）else if(z y1，y2，yn)and(z+y1，y2，yn)and(y1=y2=yn)then16）P=P P17）T=T T18）F=F(x y1)(x y2)(x yn)19）if(x，z，)Vc and (z1)=(z2)=(zn)then20）O=O O(x)=(z1 z2 zn)y21）else if(x，z，)Vc and z1=z2=zn then22）O=O O(x)=z y23）M y M24）if（y+x1，x2，xn)and(x1=x2=xn)，then25）F=F(x y)26）I=I I(x)=y x27）M y M28）end29）end for30）return LPN对于实际事件日志Log1，算法1得到Log1的Vc集后，采用算法2筛选出存在排他关系的偏差活动f、c、d和i。变迁活动f与变迁活动c、b均存在排他关系，迹中存在f与g的严格序关系，确认无其他选择路径和并发关系，将f作为逻辑输出变迁，得到活动f的后集p6和活动c与d的前集p3和p4，将逻辑输出函数设置为O(f)=p6(p3 p4)，并增加变迁f到p3和p4的弧；c和d均与i存在排他关系，且c=d=p5，将变迁i作为逻辑输入变迁，找到 i 的前集p8，设置逻辑输入函数为 I(i)=p5p8，并添加p5到i的弧。修复后的模型如图7所示，解决了问题1选择结构中分支跳转的问题，能够正确地描述事件日志中的行为关系。3.1.2选择结构中嵌套并发的模型修复随着实际业务流程的更新和扩展，在原模型中为排他关系的活动，在实际的事件日志中可能并发发生。本节使用基于服从度反馈的三元组信息，通过动态地选择存在偏差的活动，在活动集中找到关键活动设为逻辑变迁，用于解决选择结构中的并发执行偏差问题。实际事件日志Log2=1，2，5，6，其中1=j，k，l，o；2=j，m，n，o；5=j，k，n，l，o；6=j，m，l，n，o，原 模型 M2的 Petri 网 模 型 如 图 8 所 示。变 迁 活 动 k，l，n 和 m，l，n 在模型中为排他序的行为关系，但在实际事件日志中它们可以并发进行。图8Petri网模型M2Fig.8Petri net model M2事件日志Log2的服从度结果如表3所示，根据结果判断存在异常行为轮廓关系的迹。图7M1的修复模型Fig.7Repair model of M12531第 43 卷计算机应用由表3的服从度结果可知，Log2中的5和6存在行为偏差。表4给出了5和6的服从度不合规反馈信息。算法3基于算法1选择得到的偏差三元组集，通过排他序的行为轮廓关系判别输出逻辑函数，使用在活动间添加弧的方式修复原模型。具体执行步骤如下：第1）行初始化修复模型；第2）行调用选择算法得到偏差三元组集Vc；第3）行选择Vc集中存在排他序关系的活动对；第4）9）行通过筛选并发关系的活动进行模型修复，基于三元组中的活动更新P、T、F、O和M。算法3 选择路径中嵌套并发的模型修复算法。输入 事件日志L，过程模型PM；输出 基于逻辑Petri网的修复模型LPN=(P，T；F，I，O，M)。1）LPN=2）调用算法1得到选择后的偏差三元组集Vc3）for(x，y，+)Vc do4）if x+y1，y2，y3，yn then5）P=P P6）T=T T7）F=F(x y1)(x y2)()x yn8）O=O O(x)=x(y1 y2 yn)9）M y M10）else11）continue12）end for13）return LPN对于事件日志Log2，算法1找到Vc集后，采用算法3得到存在排他关系的偏差活动k、l和m、n，选择逻辑输出变迁k和m，变迁活动n的前集p12和活动k的后集p11，将逻辑输出函数定义为O(k)=p11 p12，增加k到p12的弧；找到l的前集p11，m的后集p12，将逻辑输出函数设为O(m)=p12 p11，添加 m到p11的弧。修复后的模型如图9所示，解决了问题2模型中为排他行为关系的活动也能在选择结构中并发发生的问题，能够正确地重放事件日志。3.2顺序结构中嵌套交叉序的模型修复在不断更新的信息系统中可能存在以下问题：某些活动在业务流程模型中互为严格序关系，但在实际的事件日志中它们可能会以交叉序的关系执行。原模型M3的Petri网模型如图10所示，实际事件日志Log3=3，7，8，9，其中3=a，f，g，h，i；7=a，f，h，i；8=a，g，i；9=a，g，f，h，i。同理于问题3，原模型中变迁活动f和g为严格序关系，但在实际事件日志当中可以并发进行。当采用行为轮廓关系对事件日志进行检测时，迹中这些缺失的活动并不会影响其他活动的行为轮廓关系，也不会改变3.1节中所计算的服从度。由表5中所示Log3的服从度结果可知在部分活动缺失的情况下，仅基于行为轮廓的服从度结果并不能正确反映出迹中存在的偏差。因此引入共现服从度（MCC）的概念，如定义11所示。定义11 共现服从度27。设c=(n1，n2，nm)是一个案例，P=(A，ai，a0，C，F，T)是一个过程模型，其中Ac A：1）EAc是预期案例活动的集合，EAc A包含案例中的所有 活 动 或 预 期 案 例 中 的 所 有 活 动，EAc=Ac a A|b，d Aca p d b P a (b=d b p d。2）预期案例活动对的集合EPc(A A)：EPc=(EAcEAc)idAc。3）c 对 P 的 模 型 相 对 共 现 服 从 度（Model-relative Co-occurrence Compliance，简称为MCCc）：MCCc=|EAc AcidAc|P+|EPc|P|EPc|共现服从度基于迹的期望路径，显示期望路径中的活动，通 过 潜 在 共 现 约 束 的 数 量 来 标 准 化 行 为。例 如7=a，f，h，i，gh的严格序关系并没有被满足，h活动的出现证明了 g 活动必须发生的事实，由此可以得出共现服从度MCC7=16 20=0.8。表6给出了Log3中部分不合规迹的MCC结果。由表5和表6所示的服从度结果可知，7、8和9存在行为偏差，表7给出了79的不合规反馈信息。算法4基于算法1选择得到的偏差三元组集，通过严格序与顺序的行为轮廓关系选择输出和输入的逻辑函数，通过增加活动间的选择分支或增加新的行为结构修复原模型。具体表3Log2的服从度结果Tab.3Compliance results of Log2迹1=j，k，l，o 2=j，m，n，o CBC1.001.00MBC1.001.00迹5=j，k，n，l，o 6=j，m，l，n，oCBC0.830.83MBC0.840.84表45和6的不合规反馈Tab.45 and 6 non-conformance feedback迹5=j，k，n，l，o6=j，m，l，n，o服从度违反三元组（j，m，），（n，m，），（l，n，+），（n，l，+），（k，n，+），（n，k，+）（j，k，），（l，k，），（m，l，+），（l，m，+），（l，n，+），（n，l，+）图9M2的修复模型Fig.9Repair model of M2图10Petri网模型M3Fig.10Petri net model M3表5Log3的服从度结果Tab.5Compliance results of Log3迹3=a，f，g，h，i7=a，f，h，i 8=a，g，i 9=a，g，f，h，iCBC1.001.001.000.84MBC1.001.001.000.84表6Log3中部分不合规迹的MCC结果Tab.6MCC results of some non-conformance traces in Log3迹7=a，f，h，i8=a，g，i MCC0.800.802532第 8 期张昊宇等：基于行为轮廓和逻辑Petri网的模型修复方法执行步骤如下：第1）行初始化修复模型；第2）行调用选择算法得到偏差三元组集Vc；第3）行选择Vc集中活动x对应多个y活动时存在排他序和顺序行为轮廓关系的服从度违反三元组；第4）14）行基于第3）行筛选后的三元组，在原模型中通过增加新的库所和分支的方式嵌套并发关系进行模型修复，基于三元组中的活动更新LPN；第15）19）行使用增加循环的方式在原模型中嵌套交叉非并发的结构关系进行模型修复，基于三元组中的活动更新LPN。算法4 顺序结构中嵌套交叉序的模型修复算法。输入 事件日志L，过程模型PM。输出 基于逻辑Petri网的修复模型LPN=(P，T；F，I，O，M)。1）LPN=2）调用算法1得到选择后的偏差三元组集Vc3）for(x，y，or)Vc(|y 1)do4）P=Pn P5）F=F(x y1)(x y2)()x yn(x Pn)(Pn y)-(x y)6）T=T T7）O=O O(x)=y1 y2 yn8）if(y，x，-1)Vc9）O=O O(x)=x1 x2 xn 10）end for11）for(x，y，)Vc(|x|=|y=1)do12）F=F(x y)13）I=I I(y)=x y14）e