基于行为轮廓和逻辑Petri网的模型修复方法.pdf
《基于行为轮廓和逻辑Petri网的模型修复方法.pdf》由会员分享,可在线阅读,更多相关《基于行为轮廓和逻辑Petri网的模型修复方法.pdf(10页珍藏版)》请在咨信网上搜索。
1、2023 08 10计算机应用,Journal of Computer Applications2023,43(8):2527-2536ISSN 10019081CODEN JYIIDUhttp:/基于行为轮廓和逻辑Petri网的模型修复方法张昊宇1,王丽丽1,2*(1.安徽理工大学 数学与大数据学院,安徽 淮南 232001;2.安徽省煤矿安全大数据分析与预警技术工程实验室(安徽理工大学),安徽 淮南 232001)(通信作者电子邮箱)摘要:现实中的业务流程不断发生变化,需要对初始的业务流程模型进行修复以更好地表示实际业务流程。模型修复的关键步骤是分析现实日志和模型间的偏差,目前寻找偏差的方
2、法主要采用对齐重演技术,未从行为的角度定量分析抽象的结构。因此,提出了一种通过行为轮廓分析日志和模型偏差的方法,并在此基础上进一步给出了基于逻辑Petri网的模型修复方法。首先,基于行为轮廓计算日志和模型间的服从度以识别偏差迹;然后,在偏差迹中依据偏差三元组集从偏差活动中选择逻辑变迁;最后,基于逻辑变迁设置逻辑函数,并通过添加新的分支或重构新的结构来修复原模型。对修复模型的适应度和精确度进行了验证,仿真实验结果表明,在尽可能保持修复模型与原始模型相似的基础上,相较于Fahland方法与Goldratt方法,所提修复方法在适应度都为1的情况下,得到的修复模型具有更高的精确度。关键词:行为轮廓;业
3、务流程;逻辑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
4、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 busines
5、s 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
6、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
7、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
8、.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
9、repair model and original model as much as possible.Key words:behavioral profile;business process;logical Petri net;process mining;model repair0 引言 近年来,随着互联网技术的发展,业务流程管理和在线事件流监控的方法得到进一步扩展,企业和各大组织均使用信息系统来检测分析业务流程。大量的事件日志在信息系统的执行过程中产生,为过程挖掘技术提供了基础,从而提取有价值的信息,用于进行过程发现、一致性检测和过程增强1。过程发现技术从事件日志中自动构造过程模型(例
10、如Petri网或业 务 流 程 建 模 标 注(Business Process Modeling Notation,BPMN)模型)2;一致性检测用于分析事件日志与过程模型之间存在的偏差;过程增强利用事件日志对原始模型增添或改进3-6,模型修复是过程增强中的一项技术,通过事件日志对过程模型进行修复,使修复后的模型具有更理想的适应度和精确度7。现有的一致性检测中有很多不同的方式,如早期可能会导致不稳定或模糊结果的“token-replay”方法8,后来出现并逐渐成为主流一致性检验技术的“对齐”方法9,以及为了迎合不断增加的数据流而出现的在线一致性检测技术,它基于前缀对齐联系事件流与过程模型,从
11、而进行过程监控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
12、),女,安徽安庆人,副教授,博士,主要研究方向:Petri网、可信计算。第 43 卷计算机应用增量状态空间中进行一致性检测的计算,能够在保证最优性的同时,使事件流上前缀对齐的计算可以在具有不同目标状态的扩展搜索空间上从先前的结果继续;Sani等12提出一种使用上下界的一致性检测新方法,不考虑过程模型和事件日志中可用迹之间的精确对齐,只考虑过程模型中可能行为的一个子集,并通过它来使用编辑距离函数逼近一致性值。过程增强使用事件日志进一步扩展或改进模型13。例如信息系统中所产生的事件日志可以通过过程挖掘技术发现和改进业务流程模型14,但随着业务流程的扩展,现实中很多情况下挖掘的过程模型并不能完美地重
13、放事件日志,导致挖掘的原始模型失去价值,造成资源的浪费15。此时采用模型增强中的模型修复技术可以修复原模型,能够正确地表述实际的业务流程16-19。模型修复是一种过程挖掘的新方式,通过输入事件日志和过程模型找出模型中与日志不匹配的部分进行修复,修复后的模型可以正确重放事件日志,并尽可能保留原始模型特点20-21。例如,模块化方法22基于扩展对齐,对过程模型进行分块,将劣子模型进行修复并与优子模型结合对原模型进行修复。Fahland方法23基于最优对齐寻找日志和模型间存在的偏差,使用一致性检测将给定的流程模型与日志中的迹对齐,然后把日志分解为多个子日志。对于每个子日志,发现一个可以重放子日志的循
14、环或是子流程,使用添加沉默变迁或从日志中提取子过程将其以自环形式嵌入原模型中的方式修复模型。Polyvyanyy方法24研究模型修复过程中如何减少资源损耗的问题,并提出了不同的替代方法加快修复速度,使得对齐计算的数量显著减少的同时仍可以接近最佳的模型修复。Knapsack方法25通过将单个活动以自循环的方式插入原始模型中修复。Goldratt方法26采用与Knapsack方法不同的约束函数处理资源损耗,但修复方式均为向模型中添加了一个自循环或沉默变迁。这些方式通过增加子进程或子模块的方式提高了适应度,但同时也增加了模型的复杂度和冗余。本文使用基于行为轮廓的服从度检测存在偏差的迹27,通过逻辑P
15、etri网建模修复原模型,基于行为的服从度反馈信息能更直观和快速地反映存在问题活动间的关系,逻辑 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)的两个不同分支,在模型中能
16、正确重演;但4在发生了活动a和活动f后,并没有发生f的直接后继活动g,而是选择另一个选择分支上的活动c和活动d继续执行。此时不难发现对于这种选择结构,当将日志重放于模型时存在选择偏差,本文将此类偏差称为选择结构中的路径选择偏差问题。同理对于5和6除了发生活动k所在选择分支中的所有活动之外,还发生了另一个选择分支上的活动n,显然与模型的可执行迹存在偏差,进一步分析发现,活动l与活动n在行为上存在并发关系,因此在本文将此类偏差称为选择结构中的并发执行偏差问题。对于7、8和9在活动a发生后,活动f与活动g的执行顺序并没有严格按照顺序的关系发生,但它们都仍在一条迹中执行,对于这种并发结构,本文将此类偏
17、差称为顺序结构中存在活动并发执行的问题。综上,日志在模型中重演时:1)由 4 可知,日志和模型在选择结构中存在路径选择偏差的问题;2)由 5,6 可知,日志和模型在选择结构中存在活动并发执行的问题;3)由 7,8,9 可知,日志和模型在顺序结构中存在活动并发执行的问题。因此图1中所示的过程模型PM并不能正确反映表1中事件日志Log所描述的业务流程,本文需要通过模型修复技术,在保持与原模型尽可能相似的前提下,修复原模型以更好地描述现实日志。目前的模型修复方法大多通过添加自环和沉默变迁修复模型,较少关注到活动间的行为逻辑关系。本文采用文献26 所给出的Goldratt方法利用表1中的事件日志修复图
18、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活
19、动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网的模型修复方法。从活动间的行为关系角度出发,首先通过分析活动间的行为轮廓关系提供偏差反馈;然后通过反馈的偏差三元组信息选择不同类型的逻辑变
20、迁;最后开展模型修复方法研究。并通过实验验证了本文方法在保证模型能够正确重放实际事件日志的前提下,提高了模型的精确度并使得修复后的模型尽可能与原模型相似。2 基础概念 本文使用Petri网对业务流程进行建模,Petri网是用于描述分布式系统的一种模型,它既能描述系统的结构,又能模拟系统的运行,描述系统结构的部分称为网,它可以通过对业务模型的优化和配置约束的添加来满足用户的使用需求28。定义12 流程模型。设=(A,ai,a0,C,F,T)为一个六元组的流程模型,其中:1)T为一个非空的活动变迁节点集,C为控制流的节点集,A和C互不相交;2)ai A为一个最初的活动变迁,a0 A为一个最终的活动
21、变迁;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 可达性。
22、已知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)
23、-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
24、网功能的基础上,通过活动间的业务逻辑关系对路径进行约束,构造输入输出的逻辑表达式限制变迁的输入输出,保证了模型的拟合度和精确度。定义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
25、,有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)满
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 行为 轮廓 逻辑 Petri 模型 修复 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。