逻辑Petri网非自由选择结构模型修复方法

来源:用户上传      作者:

　　摘  要： 业务过程通常在信息系统中实现之前由过程模型描述和验证。过程模型可以描述系统的特性，并通过向系统设计者提供反馈的功能来验证系统的正确性。当系统生成的事件日志中的活动与过程模型中的活动存在偏差时，需修复现有模型。对于含非自由选择结构的模型，尽管事件日志中的活动可以由现有的修复方法而得到重放，但修复后的模型往往会与原模型在结构上有很大的不同，此外，还会导致模型精确度不高且模型结构复杂。因此本文提出一种基于逻辑Petri网新的模型修复方法。首先给出了变迁对和后继关系的概念，构造出后继关系矩阵。接着通过遍历变迁对来确定模型需要修复的位置。最后通过实验验证方法的正确性和可行性。
　　关键词： 过程挖掘;非自由选择结构;逻辑Petri网;偏差;模型修复
　　中图分类号： TP3    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.01.048
　　本文著录格式：于先波，张志豪. 逻辑Petri网非自由选择结构模型修复方法[J]. 软件，2020，41（01）：220225+249
　　【Abstract】： Business processes are usually described and validated by process models before they are implemented  in information systems. The process model can describe the characteristics of the system and verify the correctness of the system by providing feedback to the system designer. When the activities in the event log generated by the system deviate from those in the process model， the existing model needs to be repaired. For models with non-free choice structure， although event logs can be replayed by existing repair methods， the repaired model is often very different from the original model in structure，In addition，it will lead to low precision and complex structure of the model.Therefore， a new model repair method based on logical Petri net is proposed in this paper. Firstly， the concept of transition pair and succession relation is given， and the succession relation matrix is constructed. Then the location of the model to be repaired is determined by traversing the transition pairs. Finally， the correctness and feasibility of the method are verified by experiments.
　　【Key words】： Process mining; Non-free-choice structure; Logic petri net; Deviation; Model repair
　　0  引言
　　过程挖掘从事件日志中提取过程相关信息，以发现、监控、和改进实际业务过程[1-2]。过程挖掘技术主要有三个方面：过程发现、一致性检查和过程增强。过程发现[3]是从事件日志生成过程模型：一致性检查[5]是将过程模型与其事件日志进行比较，并在过程模型上重放事件日志以检查其一致性：过程增强[6]是使用实际流程生成的事件日志来扩展或改进过程模型。
　　过程模型的质量的评价指标[11]主要考虑以下四个维度：拟合度、精确度、简洁度、泛化度。拟合度是指事件日志可以在过程模型上重播的能力。精确度要求过程模型只能重放在事件日志中有的活动。简洁度要求模型结构尽可能简单。泛化度意味着模型不仅可以重放事件日志中的行为，而且还允许将来发生新的行为。
　　模型修复技术保留过程模型中可以重放事件日志的部分，目的是对现有模型进行优化[12]计算。现有的修复模型方法都无法从数据库[13]中找到相应的原始模型，因此不能很好的修复模型。文献[4]阐述了图像处理[14]、校准、托肯重演、足迹对比、视频检测[15]等已有的一致性检测方法。例如，Fahland和Aalst[7]提出的方法首先根據事件日志与过程模型之间的校准关系，找出最大的日志移动序列。在同一位置发生的每一个最大日志移动序列都是一个不适合的子迹，这些位于同一位置的子迹构成了不适合的子日志，然后发现一个循环，可以重放子日志，或者可以发现相应的子过程，将其作为一个自循环添加到原始模型中。对于以最佳校准方式移动模型，我们可以向原始模型添加不可见的变迁。
　　逻辑Petri网[8]是对Petri网的扩展，是一种高级网。与传统的Petri[9]网模型相比具有简单性。变迁的输入和输出受到某些逻辑函数的限制。它可以描述变迁之间的逻辑关系，很好地描述实时协同系统的网络结构。本文基于逻辑Petri网提出了一种新的修复方法来针对含有非自由选择结构模型。 　　4  模擬实验
　　Fahland的修复方法是通过过程挖掘工具ProM6.6实现的，它可以从http：//www.promtools.org/ prom6.6/获得，因为基于逻辑Petri网的修复方法也没有实验工具，因此，本文的修复方法采用手工画出。实验所有数据见已发送的名为“数据”的压缩包。
　　实验中使用的模型和事件日志来自青岛某医院。以医院骨科业务流程模型为例，原模型如下图4所示。
　　我们共实验了10组事件日志，事件日志中的迹数从122到1029不等。我们对事件日志进行预处理，并删除严重偏离实际过程的事件日志，事件日志的详细信息，如事件数、活动数和迹的长度。
　　本文提出的模型修复方法如图5所示，与原模型相比增添了一个库所和三个逻辑函数，而用Fahland方法修复后的模型如图6所示，与原模型相比添加三个不可见变迁，以及多个弧关系，导致结构发生了很大变化，而且复杂度高。
　　拟合度表示过程模型可以在多大程度上重现事件日志中记录的迹。拟合度的值范围是0到1。注意，拟合度值越高表明效果越好。两种方法拟合度表现上效果都很好，即拟合度的值均为1。
　　图7显示了两种方法在10组日志的基础上进行模型修复后的精确度值的比较，其中横坐标表示10组日志，纵坐标表示精确度值。基于逻辑Petri网是根据文献来计算的精确度值。从图7中可以看出，本文提出的方法在不同数量的日志中都能够维持一个较高水平的精确度值，而使用Fahland方法修复后的模型得到精确度值要比我们的方法低。
　　5  结论
　　本文提出了一种基于逻辑Petri网的非自由选择结构模型修复方法。首先从事件日志中计算出变迁对，然后根据变迁对的后继关系得到后继关系矩阵。通过遍历最佳对准以及遍历这些变迁对，并在后继关系矩阵中得到反常变迁对，进而可以确定待修复的位置，最后基于逻辑Petri网挖掘算法引发条件[10]增加逻辑输入输出函数，进而对原模型进行修复。本文主要是在保证高拟合度的同时，提高了模型的精确度和简洁度。然而，本文只修复了非自由选择结构。在未来，我们将关注其他更复杂结构的过程模型。此外，未来工作将研究其他一致性度量，如泛化度。
　　参考文献
　　[1] W. M. P. van der Aalst， Process Mining： Discovery， Conformance and Enhancement of Business Processes Berlin， Germany： Springer， 2011， pp. 1-10.
　　[2] D. You， S， Wang. Dai， W. Wu， and Y. Jia， “An approach for enumerating minimal siphones in a subclass of Petri nets， ”IEEE Access， vol. 6. pp. 4255-4265， 2018.
　　[1] S. J. J. Leemans， D. Fahland， and W. M. P. van der Aalst， “Discovering block-structured process models from event logs-A constructive appproach， ”in Application and Theory of Petri Nets and Concurrency. Berlin， Germany： Springer， 2013， pp. 311-329.
　　[2] VAN DER AALST W M P. M Process mining： discovry conformance and enhancement of business process[M]. Berlin Germany： Springer-Verlag， 2011： 64-162.
　　[3] A. Rozinat and W. M. P. van der Aalst， “Conformance checking of processes based on monitoring real behavior， ”Inform. Syst. ， vol. 33， no. 1， pp. 64-95 Mar. 2008.
　　[4] W. M. P. van der Aalst， M. H. Schonenberg， and M. Song， “Time prediction based on process mining， ”Inf Syst. ， vol. 36， no. 2， pp. 450-475， Apr. 2011.
　　[5] D. Fahland W. M. P. van der Aalst， “Model repair-Aligning process models to reality， ”Inf. Syst. ， vol. 47， no. 1， pp. 220-243， 2015.
　　[6] Y. Y. Du， H. R. Zhu， and L. Wang， “An approach of process mining based on logical Petri nets， ”IEEE Access， vol. 6. pp. 29926-29939， 2018.
　　[7] LIN Chuang， YANG Hongkun， SHAN Zhiguang. The application of Petri net in bioinformatics[J]. Chinese Journal of Computers， 2007， 30（11）： 1889-1900（in Chinese）.
　　[8] Y. Du. H. R. Zhu， L. Wang， and W. Liu， “A method of process mining based on logical， ”Acta Electron. Sinica， vol. 44， no. 11， pp. 2743-2751， 2016.
　　[9] Weng Xiumu. A general software quality evaluation index system[J]. Software， 2015， 36（3）. 59-63.
　　[10] Zuo Dapeng， Xu Wei. Optimization strategy of small file processing based on Hadoop[J]. Software， 2015， 36（2）. 107-111.
　　[11] Zhang Tianzhen. Evaluation and research of shopping website construction based on database[J]. Software， 2015， 36（3）. 75-82.
　　[12] Cao Yan， Chen Wei， Xu Sen. research and Simulation of image denoising method[J]. Software， 2015， 36（4）. 33-36.
　　[13] Zhou Feng， Xue Yingying， Li Qianmu. Overview of video monitoring and coding technology[J]. Software， 2015， 36（4）. 84-92.
转载注明来源:https://www.xzbu.com/8/view-15121473.htm