孫慧明 杜玉越

摘 要：為了在不完備的日志中挖掘含有多并發(fā)的三角形二度循環(huán)結構的過程模型，在擴展Alpha算法的基礎上提出AlphaMatch算法。該算法可以在不包含重復行為序列的日志中，將兩個活動匹配成三角形二度循環(huán)，并挖掘出含有多并發(fā)三角形二度循環(huán)的過程模型。首先，根據活動數量關系將構成三角形二度循環(huán)的活動分為兩類;然后，再根據活動位置關系，使用三角形二度循環(huán)活動的首尾標記位置矩陣匹配這兩類活動，并且給出足跡矩陣顯示活動之間的關系;最后，在ProM平臺上進行了大量仿真實驗，從模型正確性、挖掘效率、擬合度和精確度四個角度驗證了算法能有效挖掘含有多并發(fā)的三角形二度循環(huán)的Petri網模型。

關鍵詞：過程挖掘;并發(fā)結構;三角形二度循環(huán);過程模型;Petri網

中圖分類號： TP311

文獻標志碼：A

文章編號：1001-9081（2019）03-0851-07

Abstract： To mine the process model including multi-concurrent 2-loops of triangles in incomplete logs， an AlphaMatch algorithm based on extended Alpha algorithm was proposed. Two activities in triangle structure could be correctly matched in 2-loops of triangles by AlphaMatch in the log without repeated activity sequence， thus the process model with multi-concurrent 2-loops of triangles could be mined. Firstly， the activities in 2-loops of triangles were divided into two categories according to the number of activities. Then， a matrix of head and tail position of the activities was constructed to match the two categories and a footprint matrix was constructed to show the relationship between activities. Finally， a large number of experiments were carried out on ProM platform from model correctness， mining efficiency， fitness and precison. Experimental results show that the Petri net model including multi-concurrent 2-loops of triangles can be mined efficiently by the proposed algorithm.

Key words： process mining; parallel structure; 2-loops of triangles; process model; Petri net

0 引言

隨著計算機、互聯網的發(fā)展，越來越多的企業(yè)采用信息系統(tǒng)處理業(yè)務，這些信息系統(tǒng)會產生大量的日志文件。過程挖掘作為一門新興學科，旨在從這些日志文件中提取有價值的過程相關信息。過程挖掘主要有過程發(fā)現（Process Discovery）、合規(guī)性檢查（Process Conformance）和過程改進（Process Enhancement）三個方面的應用。過程發(fā)現是過程挖掘中最富有挑戰(zhàn)性的任務之一[1]。通常，過程發(fā)現就是使用不包括任何先驗信息的事件日志生成模型的過程。過程模型主要有以下兩個方面的價值：1）有利于管理者了解業(yè)務流程，進行業(yè)務流程優(yōu)化，從而提高業(yè)務效率;2）利用過程模型和日志信息相結合可以發(fā)現當前業(yè)務流程中出現的不合規(guī)問題，從而推動工藝流程的改進。

在得到模型后，一般采用擬合度、精確度、簡化度和泛化度這四個標準評價過程模型。擬合度表示日志中的跡在模型中重演的能力;精確度表示模型重演日志的能力;簡化度表示模型的復雜程度;泛化度表示模型允許未來行為的能力。擬合度和精確度是判斷過程模型最重要的兩個標準。

針對過程發(fā)現中出現的問題，國內外學者提出了諸多過程發(fā)現的算法。文獻[2]提出的Alpha算法根據活動的次序判斷活動之間的關系，但是無法挖掘短循環(huán)（只含有一個活動或者兩個活動組成的循環(huán)）。文獻[3]提出的Alpha++算法解決了非自由選擇結構的問題。文獻[4]提出Alpha+算法來挖掘短循環(huán)，但是要求日志是完全完備的。然而，當日志只滿足局部完備性，Alpha及其擴展算法均不能挖掘出正確的模型。文獻[5]提出的啟發(fā)式過程挖掘算法根據依賴關系重演日志，在不完備的、有噪聲的日志處理上有很大優(yōu)勢，并且可以用于處理噪聲和不完備性，但是對于短循環(huán)處理能力一般。文獻[6]將遺傳算法思想用于過程挖掘，該方法有著良好的并行能力，日志處理速度快，但是當短循環(huán)隱藏在規(guī)模很大的模型中時，效率并不是很高。文獻[7]提出的整數線性規(guī)劃（Integer Linear Programming， ILP）算法在一定程度上能解決短循環(huán)挖掘問題，但是日志處理速度慢，效率低。文獻[8-9]提出基于區(qū)域的過程挖掘方法能夠表達更加復雜的控制流結構，并且能夠較好地平衡“過擬合”和“欠擬合”，但是當過程模型包含大量活動時，會出現“狀態(tài)空間爆炸”和無法處理噪聲的問題。文獻[10]提出的模糊挖掘方法在處理噪聲和不完備性上有很大優(yōu)勢，并且得到的過程模型較為簡潔。文獻[11]將二度循環(huán)劃分為三角形二度循環(huán)和菱形二度循環(huán)，并提出緊鄰度模型來挖掘二度短循環(huán)。緊鄰度模型在一定程度上能夠解決該問題。但是緊鄰度模型是依據相關性計算的概率模型，依賴于大量日志。當日志量比較少或者三角形二度循環(huán)中的活動緊鄰行為較少時，識別三角形二度循環(huán)存在一定局限性，即對于多個三角形二度循環(huán)并發(fā)時，匹配三角形二度循環(huán)中的活動很容易出現偏差。文獻[12]提出的Inductive Miner算法挖掘的模型有著較高的擬合度，但是挖掘含有三角形二度循環(huán)結構的日志時，挖掘的結果模型往往是過擬合的。當日志中不包含“abab……aba”行為序列時，即活動a先發(fā)生，b緊跟著發(fā)生，a緊跟b再次發(fā)生，b再次緊跟a發(fā)生，反復進行上述活動，最后以活動a結束。我們本文稱這種行為序列為三角形二度循環(huán)的循環(huán)顯式行為。針對上述情況，當前方法均不能有效挖掘出日志對應的正確過程模型。此外，三角形二度循環(huán)結構是一種重要的工業(yè)生產流程，廣泛出現在模具生產、零件加工、柔性制造、精密儀器生產、醫(yī)療器械生產、傳感器生產等諸多領域，通常代表著對某一高精度零件的多次調整和加工。挖掘含有該類結構的過程模型，對企業(yè)了解并改進精密零件的生產流程有著重要意義。綜上所述，在不包含三角形二度循環(huán)顯式行為的不完備日志中，挖掘過程模型是本文的研究重點。

針對多個并發(fā)的三角形二度循環(huán)，本文擴展Alpha算法，提出基于三角形二度循環(huán)活動首次和最后一次被標記位置的挖掘算法AlphaMatch，該算法只需要日志滿足局部完備性要求，并且不需要含三角形二度循環(huán)的顯式行為。通過大量仿真實驗，從模型正確性、挖掘效率、擬合度和精確度四個角度進行了對比分析，驗證了本文方法的有效性。

定義7 日志的完備性[16]。設a、b為日志中任意兩個活動，并且b可以直接跟在a后發(fā)生，稱滿足a >L b的行為在跡中至少出現一次的日志為局部完備性日志;稱滿足包含模型可能產生的所有活動序列的日志為完備性日志。

2 過程模型挖掘算法

本章以圖1中塑料澆筑模具生產過程模型為例，引出相關概念并詳細描述算法過程。圖1中字母代表活動含義如下：e：準備生產原料;k：制胚;a：測量模具上凹槽;b：打磨拋光上凹槽;c：測量模具下凹槽;d：打磨拋光下凹槽;j：拼接上下凹槽; f：塑料模具定型。

與經典的Alpha算法相比，AlphaMatch算法先將主體活動和回調活動進行分類;再將主體活動與回調活動進行匹配;最后返回正確的匹配二元組集合MTL。以L1為例，經過AlphaMatch算法挖掘并分析得到活動間的關系如表3所示。由表3可知，活動a與b，c與d均被匹配在一起，最后得出L1對應的模型如圖2所示，該模型與圖1一致。

3 仿真實驗

本文算法已經在ProM平臺[17]實現（包含詳細代碼的ProM工程以及實驗日志獲取網址為https：//pan.baidu.com/s/1b9Js_KhDXXEqqYdEV8QrLw）。實驗步驟如下：1）安裝必要的Java環(huán)境;2）通過上述鏈接下載該ProM工程;3）將工程添加進入Eclipse中;4）進入ProM平臺，導入日志;5）輸入AlphaMatch搜索該算法，選中并單擊該算法，即可挖掘日志對應的Petri網模型。

本文以圖3所示的滾珠軸承的生產過程模型為例，模型中變遷代表的活動含義如下：o：制胚;i：套圈退火;j：車削加工;k：熱處理;l：滾珠粗磨;m：滾珠清洗;n：保持器切削加工;e：準備半成品胚子;a：套圈細磨拋光;b：套圈測量;c：滾珠細磨拋光;d：滾珠測量;g：保持器細磨拋光;h：保持器測量;f：軸承安裝。通過以下步驟獲取不含有三角形二度循環(huán)顯式行為的局部完備日志：1）輸入如圖3所示含有三個并發(fā)的三角形二度循環(huán)的滾珠軸承生產的過程模型;2）運行ProM中的Perform a simple simulation of a （stochastic） Petri net插件得到原模型的初始日志;3）將步驟2）生成的所有初始日志中包含三角形二度循環(huán)顯式行為的跡刪除，得到實驗需要的不完備日志。本文進行實驗的日志屬性如表4所示，表中的4個日志均為缺乏循環(huán)顯式行為的不完備日志，并且日志中不包含重復序列。

實驗比較了AlphaMatch算法、Alpha+算法、ILP算法和IMF（Inductive Miner-inFrequent）算法[17]挖掘的結果。3.1節(jié)主要從模型正確性和挖掘效率上對比4種算法挖掘的模型，3.2節(jié)分別分析4個模型的擬合度和精確度。

3.1 挖掘模型分析

本節(jié)對比Alpha+算法、ILP算法、Inductive Miner-infrequent（IMF）算法以及AlphaMatch算法的挖掘結果。導入日志L2、L3、L4、L5。四種算法挖掘模型效率如圖4所示，由圖4可知Alpha+算法挖掘模型用時最少，Inductive Miner-infrequent（IMF）算法次之，兩種算法用時差別很小;ILP算法在4個算法中用時最長;本文算法比上述兩種算法用時多，但本文算法用時遠比ILP算法用時要少。

導入日志L2，Alpha+算法挖掘結果如圖5所示。由于日志不是完全完備的，所以Alpha+算法只挖掘出活動a、b、c、d、g、h之間的并發(fā)關系和活動的因果關系。此時Alpha+算法并沒有挖掘出3個回調活動與其他活動之間的關系，所以圖5的模型中存在3個獨立變遷，與原模型有很大差別，因此，該模型是不合理的。

圖6為ILP算法挖掘的模型，與Alpha+相比，該算法得到的模型不存在獨立變遷，并且該方法正確地挖掘出了活動間的關系，得到的模型與原模型一致。但是該算法挖掘速度較慢，效率較低，耗時最長。

圖7為Inductive Miner - infrequent（IMF）IMF算法挖掘的模型，該算法沒有進行活動的匹配，而是將回調活動和主體活動分成兩個部分，并且加入了大量不可見變遷，這導致模型結構相對比較復雜。除此之外，若先發(fā)生主體活動a，另外兩個主體活動還沒發(fā)生的情況下，3個回調活動中的任意一個都可以緊跟活動a發(fā)生。這種情況下產生的序列可能是原模型無法產生的，例如序列“aha”。因此，圖7中的模型是不合理的。

圖8為本文算法挖掘的模型。與Alpha+算法挖掘的模型相比，圖8所示的模型正確地把活動匹配在一起，并且沒有獨立變遷的存在;與ILP算法相比，本文算法挖掘模型用時較少，效率高;與Inductive Miner - infrequent（IMF）IMF算法挖掘的模型相比，圖8的模型不會產生原模型無法得到的序列，并且該模型與原模型一致。

綜上所述，從算法挖掘模型上看，本文算法挖掘的模型與原模型一致，與其他算法相比，有著較大優(yōu)勢。本節(jié)是從模型整體的角度進行對比分析，3.2節(jié)分別從擬合度和精確度角度，進一步對挖掘的模型進行分析。

3.2 精確度和擬合度分析

本節(jié)從擬合度和精確度的角度分析四種結果模型。導入由原模型生成的不同規(guī)模，不同完備性的日志L2、L3、L4、L5。4個日志中L5含有跡的數量最多，完備性最強。通過ProM平臺的Replay a Log on Petri Net for Conformance Analysis插件，輸入模型和日志，得出四種算法所挖掘模型的擬合度，統(tǒng)計結果如圖9所示。其中AlphaMatch算法、Inductive Miner - infrequent（IMF）IMF算法和ILP算法得到的擬合度一直都是1，擬合度要高于Alpha+算法。但是由于Inductive Miner - infrequent（IMF）IMF算法將主體活動和回調活動分成兩塊挖掘，導致模型還可能產生類似于“ada”“aha”等原模型不能產生的序列。因此，該模型是一種不合理的“過擬合”模型。由于上文中4個的日志都不是Alpha+算法所要求的完全完備日志，Alpha+算法無法得到回調活動間的關系，因此Alpha+算法得到模型的擬合度相對較低。

利用ProM中的Check Precision based on Align-ETConformance插件得到四種算法的精確度，統(tǒng)計結果如圖10所示。由于Alpha+算法挖掘的模型中出現3個獨立變遷，所以得到模型的精確度最低。由于Inductive Miner - infrequent（IMF）IMF算法挖掘的模型能產生大量原模型無法產生的活動序列，所以該算法得到模型的精確度也不高。由于ILP算法挖掘出的模型與原模型也一致，所以精確度與本文算法相同。但ILP算法挖掘出正確模型耗時最長。相比之下，本文算法挖掘用時較低，精確度更高。

綜上所述，本文算法在挖掘效率上優(yōu)于ILP算法，在所得到模型的擬合度上優(yōu)于Alpha+算法，在精確度上優(yōu)于Alpha+算法和Inductive Miner - infrequent（IMF）IMF算法。

4 結語

現有算法在挖掘多并發(fā)三角形二度循環(huán)時，挖掘的結果模型很容易與原模型出現偏差。本文提出一種能挖掘多并發(fā)三角形二度循環(huán)的新方法。首先依據三角形二度循環(huán)活動的數量特征將活動分為主體活動和回調活動;其次，依據活動首次和最后一次在跡中出現的位置，采用剪枝的思想，逆向將不正確的活動匹配刪除，從而得到正確的活動匹配;最后，將算法以插件形式在ProM平臺實現，經過大量實驗分析，驗證了本文算法能夠正確有效地挖掘多并發(fā)三角形二度循環(huán)，并且該方法得到的模型有著最高的精確度和擬合度。但是本文算法也有一定的局限性，沒有考慮重名活動等復雜情況的干擾，并且在挖掘效率上表現平庸，后續(xù)將對本文算法作出改進。

參考文獻 （References）

[1] van der AALST W M. Process Minging： Discovery， Conformance and Enhancement of Business Processes [M]. Berlin： Springer， 2014： 5-18.

[2] van der AALST W， WEIJTERS T， MARUSTER L. Workflow mining： discovering process models from event logs [J]. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（9）： 1128-1142.

[3] WEN L， van der AALST W M， WANG J， et al. Mining process models with non-free-choice constructs [J]. Data Mining and Knowledge Discovery， 2007， 15（2）： 145-180.

[4] de MEDEIROS A K A， van DONGEN B F， van der AALST W M. Process mining： extending the α-algorithm to mine short loops [R]. Eindhoven， Holland： Eindhoven University of Technology， 2004： 151-165.

[5] WEIJTERS A， van der AALST W， de MEDEIROS A A. Process mining with the heuristics miner-algorithm [R]. Eindhoven， Holland： Eindhoven University of Technology， 2006： 1-34.

[6] MEDEIROS A K A D， WEIJTERS A J M M， AALST W M P V D. Genetic process mining： an experimental evaluation [J]. Data Mining and Knowledge Discovery， 2007， 14（2）： 245-304.

[7] van der WERF J M E M， van DONGEN B F， HURKENS C A J， et al. Process discovery using integer linear programming [C]// Proceedings of the 2008 International Conference on Applications and Theory of Petri Nets， LNCS 5062. Berlin： Springer， 2008： 368-387.

[8] van DONGE B， BUSI N， PINNA G， et al. An iterative algorithm for applying the theory of regions in process mining [R]. Eindhoven， Holland： Eindhoven University of Technology， 2007： 36-55.

[9] BERGENTHUM R， DESEL J， LORENZ R， et al. Process mining based on regions of languages [C]// Proceedings of the 2007 International Conference on Business Process Management， LNCS 4714. Berlin： Springer， 2007： 375-383.

[10] GNTHER C W， van der AALST W M P. Fuzzy mining — adaptive process simplification based on multi-perspective metrics [C]// International Conference on Business Process Management. Springer-Verlag， 2007：328-343.

GNTHER C W， van der AALST W M P. Fuzzy mining — adaptive process simplification based on multi-perspective metrics [EB/OL]. [2018-06-16]. http：//citeseerx.ist.psu.edu/viewdoc/download;jsessionid=1628DBA2308A214245DDE19D04107610？doi=10.1.1.81.1207&rep=rep1&type=pdf.

[11] 林雷蕾，周華，代飛，等.一種挖掘二度循環(huán)的擴展Alpha算法[J]. 計算機集成制造系統(tǒng)，2018，24（3）：591-601. （LIN L L， ZHOU H， DAI F，et al. Extending α-algorithm to mine simplest 2-loops [J]. Computer Integrated Manufacturing Systems， 2018， 24（3）： 591-601.）

[12] WU B， FU Y. Generating inductive invariants for Petri nets [M]// Advances in Electrical Engineering and Automation， AINSC 139. Berlin： Springer， 2012： 259-266.

[13] 祁宏達，杜玉越，劉偉.一種基于可達標識的過程模型修復方法[J]. 山東科技大學學報（自然科學版），2017，36（1）：118-124.（QI H D， DU Y Y， LIU W. Process model repairing method based on reachable markings[J]. Journal of Shandong University of Science and Technology （Natural Science）， 2017， 36（1）： 118-124.）

[14] 明利，李彤，秦江龍，等.面向軟件即服務的負載均衡策略建模與分析[J].計算機應用，2017，37（1）：24-30.（MING L， LI T， QIN J L， et al. SaaS-oriented modeling and analysis of load balancing strategy [J]. Journal of Computer Applications， 2017， 37（1）： 24-30.）

[15] HE Z， DU Y， WANG L， et al. An alpha-FL algorithm for discovering free loop structures from incomplete event logs [J]. IEEE Access， 2018，6： 27885-27901.

[16] YANG H， WEN L， WANG J. An approach to evaluate the local completeness of an event log [C]// Proceedings of the 2012 IEEE 12th International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2012： 1164-1169.

[17] van DONGEN B F， de MEDEIROS A K A， VERBEEK H M W， et al. The ProM framework： a new era in process mining tool support [C]// Proceedings of the 2005 International Conference on Applications and Theory of Petri Nets， LNCS 3536. Berlin： Springer， 2005： 444-454.