于先波 張志豪

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

關鍵詞： 過程挖掘;非自由選擇結構;邏輯Petri網(wǎng);偏差;模型修復

中圖分類號： TP3 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.01.048

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

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

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

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

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

4 ?模擬實驗

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

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

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

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

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

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

5 ?結論

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

參考文獻

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