針對(duì)多并發(fā)三角形二度循環(huán)結(jié)構(gòu)的過(guò)程模型挖掘方法

孫慧明 杜玉越

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

關(guān)鍵詞：過(guò)程挖掘;并發(fā)結(jié)構(gòu);三角形二度循環(huán);過(guò)程模型;Petri網(wǎng)

中圖分類號(hào)： TP311

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

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

在得到模型后，一般采用擬合度、精確度、簡(jiǎn)化度和泛化度這四個(gè)標(biāo)準(zhǔn)評(píng)價(jià)過(guò)程模型。擬合度表示日志中的跡在模型中重演的能力;精確度表示模型重演日志的能力;簡(jiǎn)化度表示模型的復(fù)雜程度;泛化度表示模型允許未來(lái)行為的能力。擬合度和精確度是判斷過(guò)程模型最重要的兩個(gè)標(biāo)準(zhǔn)。

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

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

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

2 過(guò)程模型挖掘算法

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

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

3 仿真實(shí)驗(yàn)

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

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

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

3.1 挖掘模型分析

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

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

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

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

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

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

3.2 精確度和擬合度分析

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn) （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)的擴(kuò)展Alpha算法[J]. 計(jì)算機(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] 祁宏達(dá)，杜玉越，劉偉.一種基于可達(dá)標(biāo)識(shí)的過(guò)程模型修復(fù)方法[J]. 山東科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 明利，李彤，秦江龍，等.面向軟件即服務(wù)的負(fù)載均衡策略建模與分析[J].計(jì)算機(jī)應(yīng)用，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.