于先波 張志豪

摘 ?要： 業(yè)務(wù)過程通常在信息系統(tǒng)中實(shí)現(xiàn)之前由過程模型描述和驗(yàn)證。過程模型可以描述系統(tǒng)的特性，并通過向系統(tǒng)設(shè)計(jì)者提供反饋的功能來驗(yàn)證系統(tǒng)的正確性。當(dāng)系統(tǒng)生成的事件日志中的活動(dòng)與過程模型中的活動(dòng)存在偏差時(shí)，需修復(fù)現(xiàn)有模型。對(duì)于含非自由選擇結(jié)構(gòu)的模型，盡管事件日志中的活動(dòng)可以由現(xiàn)有的修復(fù)方法而得到重放，但修復(fù)后的模型往往會(huì)與原模型在結(jié)構(gòu)上有很大的不同，此外，還會(huì)導(dǎo)致模型精確度不高且模型結(jié)構(gòu)復(fù)雜。因此本文提出一種基于邏輯Petri網(wǎng)新的模型修復(fù)方法。首先給出了變遷對(duì)和后繼關(guān)系的概念，構(gòu)造出后繼關(guān)系矩陣。接著通過遍歷變遷對(duì)來確定模型需要修復(fù)的位置。最后通過實(shí)驗(yàn)驗(yàn)證方法的正確性和可行性。

關(guān)鍵詞： 過程挖掘;非自由選擇結(jié)構(gòu);邏輯Petri網(wǎng);偏差;模型修復(fù)

中圖分類號(hào)： TP3 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.01.048

本文著錄格式：于先波，張志豪. 邏輯Petri網(wǎng)非自由選擇結(jié)構(gòu)模型修復(fù)方法[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 ?引言

過程挖掘從事件日志中提取過程相關(guān)信息，以發(fā)現(xiàn)、監(jiān)控、和改進(jìn)實(shí)際業(yè)務(wù)過程[1-2]。過程挖掘技術(shù)主要有三個(gè)方面：過程發(fā)現(xiàn)、一致性檢查和過程增強(qiáng)。過程發(fā)現(xiàn)[3]是從事件日志生成過程模型：一致性檢查[5]是將過程模型與其事件日志進(jìn)行比較，并在過程模型上重放事件日志以檢查其一致性：過程增強(qiáng)[6]是使用實(shí)際流程生成的事件日志來擴(kuò)展或改進(jìn)過程模型。

過程模型的質(zhì)量的評(píng)價(jià)指標(biāo)[11]主要考慮以下四個(gè)維度：擬合度、精確度、簡潔度、泛化度。擬合度是指事件日志可以在過程模型上重播的能力。精確度要求過程模型只能重放在事件日志中有的活動(dòng)。簡潔度要求模型結(jié)構(gòu)盡可能簡單。泛化度意味著模型不僅可以重放事件日志中的行為，而且還允許將來發(fā)生新的行為。

模型修復(fù)技術(shù)保留過程模型中可以重放事件日志的部分，目的是對(duì)現(xiàn)有模型進(jìn)行優(yōu)化[12]計(jì)算?，F(xiàn)有的修復(fù)模型方法都無法從數(shù)據(jù)庫[13]中找到相應(yīng)的原始模型，因此不能很好的修復(fù)模型。文獻(xiàn)[4]闡述了圖像處理[14]、校準(zhǔn)、托肯重演、足跡對(duì)比、視頻檢測[15]等已有的一致性檢測方法。例如，F(xiàn)ahland和Aalst[7]提出的方法首先根據(jù)事件日志與過程模型之間的校準(zhǔn)關(guān)系，找出最大的日志移動(dòng)序列。在同一位置發(fā)生的每一個(gè)最大日志移動(dòng)序列都是一個(gè)不適合的子跡，這些位于同一位置的子跡構(gòu)成了不適合的子日志，然后發(fā)現(xiàn)一個(gè)循環(huán)，可以重放子日志，或者可以發(fā)現(xiàn)相應(yīng)的子過程，將其作為一個(gè)自循環(huán)添加到原始模型中。對(duì)于以最佳校準(zhǔn)方式移動(dòng)模型，我們可以向原始模型添加不可見的變遷。

邏輯Petri網(wǎng)[8]是對(duì)Petri網(wǎng)的擴(kuò)展，是一種高級(jí)網(wǎng)。與傳統(tǒng)的Petri[9]網(wǎng)模型相比具有簡單性。變遷的輸入和輸出受到某些邏輯函數(shù)的限制。它可以描述變遷之間的邏輯關(guān)系，很好地描述實(shí)時(shí)協(xié)同系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)。本文基于邏輯Petri網(wǎng)提出了一種新的修復(fù)方法來針對(duì)含有非自由選擇結(jié)構(gòu)模型。

4 ?模擬實(shí)驗(yàn)

Fahland的修復(fù)方法是通過過程挖掘工具ProM6.6實(shí)現(xiàn)的，它可以從http：//www.promtools.org/ prom6.6/獲得，因?yàn)榛谶壿婸etri網(wǎng)的修復(fù)方法也沒有實(shí)驗(yàn)工具，因此，本文的修復(fù)方法采用手工畫出。實(shí)驗(yàn)所有數(shù)據(jù)見已發(fā)送的名為“數(shù)據(jù)”的壓縮包。

實(shí)驗(yàn)中使用的模型和事件日志來自青島某醫(yī)院。以醫(yī)院骨科業(yè)務(wù)流程模型為例，原模型如下圖4所示。

我們共實(shí)驗(yàn)了10組事件日志，事件日志中的跡數(shù)從122到1029不等。我們對(duì)事件日志進(jìn)行預(yù)處理，并刪除嚴(yán)重偏離實(shí)際過程的事件日志，事件日志的詳細(xì)信息，如事件數(shù)、活動(dòng)數(shù)和跡的長度。

本文提出的模型修復(fù)方法如圖5所示，與原模型相比增添了一個(gè)庫所和三個(gè)邏輯函數(shù)，而用Fahland方法修復(fù)后的模型如圖6所示，與原模型相比添加三個(gè)不可見變遷，以及多個(gè)弧關(guān)系，導(dǎo)致結(jié)構(gòu)發(fā)生了很大變化，而且復(fù)雜度高。

擬合度表示過程模型可以在多大程度上重現(xiàn)事件日志中記錄的跡。擬合度的值范圍是0到1。注意，擬合度值越高表明效果越好。兩種方法擬合度表現(xiàn)上效果都很好，即擬合度的值均為1。

圖7顯示了兩種方法在10組日志的基礎(chǔ)上進(jìn)行模型修復(fù)后的精確度值的比較，其中橫坐標(biāo)表示10組日志，縱坐標(biāo)表示精確度值?；谶壿婸etri網(wǎng)是根據(jù)文獻(xiàn)來計(jì)算的精確度值。從圖7中可以看出，本文提出的方法在不同數(shù)量的日志中都能夠維持一個(gè)較高水平的精確度值，而使用Fahland方法修復(fù)后的模型得到精確度值要比我們的方法低。

5 ?結(jié)論

本文提出了一種基于邏輯Petri網(wǎng)的非自由選擇結(jié)構(gòu)模型修復(fù)方法。首先從事件日志中計(jì)算出變遷對(duì)，然后根據(jù)變遷對(duì)的后繼關(guān)系得到后繼關(guān)系矩陣。通過遍歷最佳對(duì)準(zhǔn)以及遍歷這些變遷對(duì)，并在后繼關(guān)系矩陣中得到反常變遷對(duì)，進(jìn)而可以確定待修復(fù)的位置，最后基于邏輯Petri網(wǎng)挖掘算法引發(fā)條件[10]增加邏輯輸入輸出函數(shù)，進(jìn)而對(duì)原模型進(jìn)行修復(fù)。本文主要是在保證高擬合度的同時(shí)，提高了模型的精確度和簡潔度。然而，本文只修復(fù)了非自由選擇結(jié)構(gòu)。在未來，我們將關(guān)注其他更復(fù)雜結(jié)構(gòu)的過程模型。此外，未來工作將研究其他一致性度量，如泛化度。

參考文獻(xiàn)

[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.