祁宏達，杜玉越，劉 偉

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

一種基于可達標識的過程模型修復方法

祁宏達，杜玉越，劉 偉

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

模型修復是一種基于模型增強的過程挖掘的應用技術(shù)，現(xiàn)有的模型修復方法大多是以擬合度為主要指標，對于其他維度，諸如精確度，考慮較少?；诖耍疚脑噲D綜合考慮多個維度，來對過程模型進行修復。校準能夠?qū)κ录罩具M行重演，發(fā)現(xiàn)各類偏差，即日志動作和模型動作，卻無法確定偏差在Petri網(wǎng)中出現(xiàn)的位置。因此，基于Petri網(wǎng)的可達標識，提出了擴展校準的概念，這樣便能確定偏差的位置。進一步地，針對擴展校準中出現(xiàn)的日志動作提出了RMR(Reachable Marking Repaining)算法進行修復。最后，通過實驗證明修復算法在擬合度和精確度上均有較好的表現(xiàn)。

校準；模型修復；擴展校準；修復算法

過程挖掘是從實際執(zhí)行集合中提取出結(jié)構(gòu)化過程描述的方法[1]。過程挖掘技術(shù)一共有三類應用:過程發(fā)現(xiàn)(process discovery)、一致性檢測(conformance checking)和過程增強(process enhancement)。

評價過程模型 “好壞”的標準有擬合度(fitness)、精確度(precision)、簡化度(simplicity)和泛化度(generalization)[2]，其中擬合度是評價過程模型最為重要的指標。模型的擬合度意味著日志中的跡(trace)在模型中重演的能力。高精確度代表著模型只會重演事件日志中的跡。

在一致性檢測和過程增強技術(shù)方面，目前最大的挑戰(zhàn)是在過程模型上進行重演，發(fā)現(xiàn)事件日志中觀察到的行為的最優(yōu)路徑。文獻[3]提出了基于事件日志的校準方法，為模型修復奠定了基礎(chǔ)。

作為一種新的過程挖掘的應用技術(shù)，模型修復技術(shù)屬于過程增強這一范疇[4]。模型修復以事件日志和過程模型作為輸入，如果存在事件日志中的跡不能夠在過程模型中重演，則需要對過程模型進行修改。修改后的模型要盡量與原始模式相似，即不改變原始模型的基本結(jié)構(gòu)。

目前，已有一些運用編輯距離矩陣(edit distance matrices)來發(fā)現(xiàn)改進模型的[5-7]方法，雖與修復模型的目標一致，但并不屬于模型修復技術(shù)?；谀Ｐ秃腿罩镜钠顏磉M行模型修復的方法并不多，文獻[4]提出了一種模型修復方法，利用校準發(fā)現(xiàn)模型和日志的偏差，進而對模型進行修復。但是，這種方法主要關(guān)注擬合度這一維度，對于其他維度(如精確度)未考慮。在這一背景下，本文綜合考慮多個維度指標來修復過程模型。

1 基本概念

這一節(jié)中對事件日志、Petri網(wǎng)[8-9]和校準[3]等基本概念進行了描述。首先介紹跡和事件日志這一概念。

定義1(跡，事件日志) 設(shè)A∈A是活動集，跡σ∈A*是活動隊列。而事件日志L則是跡的多重集合，即L∈IB(A*)。

Petri網(wǎng)是一個包含庫所(place)和變遷(transition)的有向二分圖。

定義2(Petri網(wǎng)[8-9]) 四元組PN=(P,T;F,M)稱為一個Petri網(wǎng)PN，當且僅當

1)N=(P,T;F)為一個網(wǎng)，其中P是一個有限庫所集，T是一個有限變遷集，F(xiàn)?(P×T)∪(T×P)是一個有限弧集；

2)M:P→N稱為網(wǎng)PN的一個標識，其中mi為初始標識，mf為終止標識；

3)PN具有下面的變遷發(fā)生規(guī)則：

①對于變遷t∈T，如果?p∈·t:M(p)≥1，則稱變遷t在標識M下使能，記為M[t>；

②若M[t>，則在標識M下，變遷t可以發(fā)生，從標識M引發(fā)變遷t得到一個新的標識M′，記為M[t>M′，且對?p∈P，

在定義2中，·t表示t的輸入集，t·表示t的輸出集。

以一個過程模型作為參考，活動在執(zhí)行過程沒有偏離模型，意味著在當前狀態(tài)下活動是被模型所允許的。也就是說，給定一個無任何偏差的事件日志，活動是完全按照模型的順序來執(zhí)行的。文獻[3]提出了校準這一概念，用以比較事件日志中的活動與模型上的活動。對于校準來說，每一個實例都要對應一個校準。

定義3(校準[3]) 設(shè)A∈A，σ∈A*，PN=(P,T;F,M)。二元組(a,t)∈A?XT?{(?,?)}是一個移動。校準γ是跡σ和模型PN之間的移動隊列(a,t)*，且滿足：

1) π1(γ)↓A=σ，即校準中所有的第一元素對應一條跡；

Γσ,PN是跡σ和模型PN之間所有校準的集合。其中π1(γ)↓A代表校準中第一個元素，π2(γ)↓T代表校準中第二個元素。

對于一個移動(a,t)，可能是一個:①同步動作iffa≠? andt≠?，② 模型動作iffa=? andt≠?，③日志動作iffa≠? andt=?。

給定一個跡和一個Petri網(wǎng)，可能會存在多個校準。在實際過程中，偏差的可能性會隨著活動的不同和人為制定的不同而產(chǎn)生不同的影響。為了能夠產(chǎn)生最有可能的校準，需要對每一個移動賦予一個可能性代價函數(shù)lc(a,t)。在本文中，對于日志動作和模型動作，lc(a,t) = 1，對于同步動作，lc(a,t) = 0。根據(jù)制定的可能性代價函數(shù)，能夠找到可能性代價值最低的校準，這種校準被稱為最優(yōu)校準。

校準和最優(yōu)校準能夠?qū)⑹录罩竞瓦^程模型關(guān)聯(lián)起來，并且最優(yōu)校準能夠處理過程模型中的不可見變遷、復雜的控制流和循環(huán)等。當偏差出現(xiàn)時，校準能夠展示出偏差所在的位置，并且為進一步的研究提供診斷信息。

2 擴展校準

過程模型修復屬于過程增強的具體應用，其思想是利用實際過程中產(chǎn)生的事件日志擴展和改進一個已經(jīng)存在的過程模型。校準能夠?qū)κ录罩具M行重演，發(fā)現(xiàn)各類偏差，即日志動作和模型動作，卻無法確定偏差在Petri網(wǎng)中出現(xiàn)的位置。因此，本文引入了可達標識對校準進行擴展，來確定偏差出現(xiàn)的位置，其定義如下。

定義5(擴展校準) 設(shè)A∈A，σ∈A*，PN=(P,T;F,M)，γ是一個跡σ和模型PN之間的校準。β∈(γ×M)*是跡σ和模型PN之間的擴展校準，當且僅當：

1)γ是一個跡σ和模型PN之間的校準；

2)mi[π2(π1(β)↓γ) ↓T>mf，即擴展移動隊列在模型中的移動發(fā)生后，最終會到達終止標識；

Bσ,PN是跡σ和模型PN之間所有擴展校準的集合。需要指出的是，當前動作的可達標識與前一動作的可達標識相同，為iffπ2(π1(β)↓γ)↓T= ?。

以圖1所示的Petri網(wǎng)PN1為例，假設(shè)存在一條跡σ1= ，擴展校準如圖2所示。

圖1 Petri網(wǎng)PN1

圖2 跡σ1的擴展校準

對于(d,d,m2)，可達標識m2:m2(p2) =m2(p5)=1,m2(p1)=m2(p3)=m2(p4)=m2(p6)=0。

類似于最優(yōu)校準，最優(yōu)擴展校準定義如下：

定義6(最優(yōu)擴展校準) 設(shè)A∈A，σ∈A*，PN=(P,T;F,M)，γ是一個跡σ和模型PN之間的校準。擴展校準β∈(γ×M)*是一個最優(yōu)擴展校準當且僅當γ是一個最優(yōu)校準。

對于圖2中的兩個擴展校準β1和β2，可能性代價值lc(β1)=2,lc(β2)=2，顯然，β1，β2均是是跡σ1的最優(yōu)擴展校準。

3 偏差修復方法

實際上，現(xiàn)有過程模型往往是通過過程挖掘算法或者手動建立的。存在著這樣一種情形：一開始的事件日志與過程模型完全符合，但隨著一些原過程模型中無法重演的跡出現(xiàn)在事件日志中，導致原模型不再符合真實情況。因此，需要對過程模型進行修復。

對于最優(yōu)擴展校準來說，存在兩類基本的偏差類型：日志動作和模型動作。本文主要針對日志動作修復方法進行改進。日志動作的出現(xiàn)，說明事件日志中出現(xiàn)了過程模型中不存在的活動。Fahland的方法利用校準發(fā)現(xiàn)模型和日志之間的偏差，收集出不擬合的子日志，利用現(xiàn)有挖掘算法對不擬合的子日志進行挖掘，將挖掘出的子過程作為自環(huán)，添加到原模型的合適位置。自環(huán)的出現(xiàn)，使得這一子過程可以多次重復發(fā)生，即模型中允許無限序列的出現(xiàn)。然而在實際過程中，這種情況基本不會出現(xiàn)，導致了修復后過程模型的精確度不高。

圖3 跡σ2的擴展校準

圖4 Fahland的方法修復后的模型

以Petri網(wǎng)PN1為例，假設(shè)存在變遷σ2=〈a,x,y,c,d,e〉，最優(yōu)擴展校準如圖3所示。

β3存在兩個連續(xù)的日志動作(x,?,m2)和(y,?,m3)。其中兩個動作可達標識完全相同，即m2=m3且m3(p2) =m3(p4) = 1。根據(jù)其可達標識，Petri網(wǎng)PN1在庫所p2和p4處有托肯。Fahland的方法對于添加子環(huán)的位置并未做出約束，位置可以是p2和p4任意一個，在此選取p2位置，修復后的模型如圖4所示。

由于在p2處添加了一個自環(huán)，修復后的模型允許這一自環(huán)無限重復發(fā)生，即存在一個無限序列σ3=〈a,x,y,…〉。在實際的事件日志中，σ3顯然不會出現(xiàn)。這就導致模型允許的可能的發(fā)生序列多于實際的事件日志，因而模型的精確度不高。

為了避免自環(huán)的出現(xiàn)，本文提出了RMR修復方法，將這一子過程插入到原模型中。由于是插入到原模型中，導致這一子過程必然會發(fā)生，而實際的日志中這一子過程可以不發(fā)生。因此，需要對子過程添加一個不可見變遷，分別與初始庫所和終止庫所相連。同樣以σ2為例，選取p2位置，修復后的模型如圖5所示。

圖5 RMR方法修復后的模型

算法1實現(xiàn)了對指定庫所處的日志動作的收集。其思想是依次對每一條擴展校準進行遍歷，當發(fā)現(xiàn)指定庫所是日志動作時，進行保存。遍歷完所有的最優(yōu)擴展校準后將會得到一個變遷序列集合。

算法1指定庫所處日志動作收集

輸出：變遷序列集合TS

步驟：

2. {While(j<βi，length)do

3. {if(mj(p)=1 and π2(π1(βi[j]))↓γ↓T=?)then

4.TI←TI∪π1(π1(βi[j]))↓γ↓A；}

5. if((TI≠?)then

6.TS←TS∪TI；

7.TI←?；}

8.returnTS；

在收集到所有指定庫所處的日志動作后，可以通過現(xiàn)有挖掘算法來挖掘過程模型，之后將這一子過程添加到指定的庫所處。目前，國內(nèi)外的很多學者都致力于研究過程挖掘算法。比如，基于活動順序關(guān)系產(chǎn)生的α算法[10]以及其衍生算法[11-12]，基于語義技術(shù)提出的區(qū)域挖掘[13]和ILP挖掘[14]等等。本文所使用的過程挖掘算法是歸納挖掘[15]。算法2主要思想是通過挖掘算法挖掘出變遷序列集合對應的子過程，這一子過程需要添加一個不可見變遷，并將這一子過程插入到指定的庫所處。

算法2利用子日志修復過程模型

輸入：原過程模型PN，子日志SL，指定庫所p

輸出：修復后的過程模型PN′

步驟：

1.PN1←InductiveMiner(SL)

2.T1←T1∪{τ}

3.F1←F1({(m1i,τ),(τ,m1f)}

4.PN′←PN

5. for ?t∈·pdo

6. {F′ ←F′∪{(t,m1i)}{(t,p)};

7. for ?t∈p·do

8. {F′←F′∪{(m1f,t)}{(p/t)};

9.P′←P′ {p}

10.P′←P′∪P1，T′←T′∪T1，F(xiàn)′←F′∪F1

11. returnPN′

通過這兩個算法，能夠收集指定庫所處出現(xiàn)的日志動作，實現(xiàn)在指定庫所處對過程模型進行修復。

4 實驗

本文中所有的仿真實驗均在ProM 6.0中進行，所有的數(shù)據(jù)均來自于青島某醫(yī)院胸外科。

4.1 修復過程模型

以某醫(yī)院胸外科的業(yè)務流程為例，通過在原有事件日志的基礎(chǔ)上進行挖掘建模，得到圖6的Petri網(wǎng)模型。主要活動過程描述如下：首先，病人通過兩種方式預約：分診臺預約(reserve at triage station)和電話預約(reserve by phone)。隨后，進行預約登記(booking)和取得預約號(get reservation number)。病人也可以不進行預約直接就診(consult without reservation)，但需要進行掛號(registration)。對于預約的病人和掛號的病人，醫(yī)院進行排號(arranging)和順序叫號(call number by order)，病人依照順序找醫(yī)生問診(inquiry)。醫(yī)生通過問診來確定是否進行影像檢查和臨床檢驗。影像檢查一共有三種類型：普通CT(common ct)、PET-CT和胸部增強(chest enhanced scan)。臨床檢驗有4種類型：血沉(ESR)、生化全套(Biochemical full set)、血氣分析(blood gas analysis)和血常規(guī)(blood routine)。之后，醫(yī)生根據(jù)檢查結(jié)果進行診斷(diagnosis)。若病人病情無礙，則可離開醫(yī)院(leave)。若病人病情嚴重，則需要住院治療(hospitalization)。

圖6 某醫(yī)院胸外科的Petri網(wǎng)模型

選取了3組事件日志用以修復過程模型。表1展示了3組事件日志中跡的總數(shù)與長度、事件總數(shù)、活動總數(shù)和跡中出現(xiàn)的偏差總數(shù)。

對不同的庫所，按照算法1進行變遷序列集合的收集，得到表2。

表1 3組事件日志

表2 各個位置處的變遷序列集合

按Fahland的方法對過程模型進行修復，修復后的模型如圖7所示。本文中將這一子過程進行修改，插入到原模型中，修復后的模型如圖8所示。

圖7 Fahland的方法修復后的模型

圖8 RMR方法修復后的模型

4.2 模型評估

下面對修復后的過程模型進行評價。針對各個一致性指標，本文分別采用了不同數(shù)量級的事件日志，對RMR方法和Fahland方法進行了比較。圖9和圖10分別展示了不同數(shù)量級下擬合度和精確度的變化。

通過圖9發(fā)現(xiàn)，在不同的數(shù)量級下，兩種方法均有較高的擬合度，且兩種方法并未出現(xiàn)隨著數(shù)據(jù)增加而波動的情形。這說明事件日志中的跡大部分都能夠在兩個模型中重演。

通過圖10發(fā)現(xiàn)，對于精確度來說，本文的RMR方法能夠保持一個較高的數(shù)值，而Fahland方法的精確度較低。對于不同數(shù)量級的事件日志，這一情形相似。

圖9 擬合度的變化

圖10 精確度的變化

5 總結(jié)

本文首先在校準中加入了Petri網(wǎng)的可達標識，提出了擴展校準的概念，并通過擴展校準來識別可能出現(xiàn)的各類擴展動作。最優(yōu)擴展校準則能為各類偏差的修復提供支持。通過對日志動作進行分析，本文提出RMR算法對這類偏差進行修復。通過某醫(yī)院胸外科的事件日志對這一方法進行仿真實驗發(fā)現(xiàn)，這一方法相較于Fahland的方法，在擬合度和精確度方面均有著較好的表現(xiàn)。本文僅僅是對基本偏差進行了修復，對于一些高級偏差并未給出相應的修復方法，這也是下一步研究的重點。

[1]曾慶田.流程挖掘的研究現(xiàn)狀和問題綜述[J].系統(tǒng)仿真學報,2007,19(1):276-278.

[2]VAN DERr AALST W M P.Process Mining:Discovery,Conformance and Enhancement of Business Processes[M].Berlin:Springer-Verlag,2011:9-25.

[3]ADRIANSYAH A,MUNOZ-GAMA J,CARMONA J,et al.Alignment based precision checking[C]//Business Process Management Workshops.Berlin Heidelberg:Springer,2013:137-149.

[4]FAHLAND Dirk,W M P VAN DER AALST. Model repair - aligning process models to reality[J].Information Systems,2015,47:220-243.

[5]GAMBINI M,LA ROSA M,MIGLIORINI S,et al.Automated error correction of business process models[C]//International Conference on Business Process Management.Berlin Heidelberg:Springer,2011:148-165.

[6]LI C,REICHERT M,WOMBACHER A.Discovering reference models by mining process variants using a heuristic approach[C]//International Conference on Business Process Management.Berlin Heidelberg:Springer,2009:344-362.

[7]LOHMANN N.Correcting deadlocking service choreographies using a simulation-based graph edit distance[C]//International Conference on Business Process Management.Berlin Heidelberg:Springer,2008:132-147.

[8]YUYUE D,LIANG Q， MENGCHU.Analysis and application of logical Petri nets to E-commerce systems[J].IEEE Transactions on Systems,Man,and Cybernetics Systems,2014,44(4):468-481.

[9]DU Y Y,LIANG Q,ZHOU M C.A vector matching method for analyzing logic Petri nets[J].Enterprise Information Systems,Sep.2011,5(4):449-468.

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

[11]WEN L,WANG J,SUN J.Mining invisible tasks from event logs[M]//Advances in Data and Web Management.Berlin Heidelberg:Springer,2007:358-365.

[12]WEN L,VAN DER AALST W M P,WANG J,et al.Mining process models with non-free-choice constructs[J].Data Mining and Knowledge Discovery,2007,15(2):145-180.

[13]BERGENTHUM R,DESEL J,MAUSER S.Synthesis of Petri nets from term based representations of infinite partial languages[J].Fundamenta Informaticae,2009,95(1):187-217.

[14]VAN DERWERF J M E M,VAN DONGEN B F,HURKENS C A J,et al.Process discovery using integer linear programming[J].Fundamenta Informaticae,2009,94(3/4):387-412.

[15]LEEMANS S J J,FAHLAND D,VAN DER AALST W M P.Discovering block-structured process models from event logs-a constructive approach[C]//International Conference on Applications and Theory of Petri Nets and Concurrency.Berlin Heidelberg:Springer,2013:311-329.

(責任編輯：傅 游)

Process Model Repairing Method Based on Reachable Markings

QI Hongda,DU Yuyue,LIU Wei

(College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266590,China)

Model repairing is a new application of process mining based on model enhancement. The existing methods of model repairing concentrate on degree of fitting,and give little consideration to other dimensions such as precision. In this background,this paper attempts to repair the process model by considering the multiple dimensions. Although alignments can replay event logs in process models and find deviations,i.e.,move on log and move on model,they are unable to confirm the locations of deviations in Petri nets. Thus,extended alignments were proposed based on reachable markings in Petri nets to confirm the locations of deviations. A new algorithm were proposed for repairing the move on log in the extended alignments. Finally,experiments were conducted to prove the better performance of the proposed method in fitting,precision and time.

alignment; model repair; Petri Net; repairing algorithm

2016-06-15

國家自然科學基金項目(61170078,61472228); 泰山學者建設(shè)工程項目；山東省自然科學基金項目(ZR2014FM0 09)；山東省優(yōu)秀中青年科學家科研獎勵基金項目(BS2015DX010)

祁宏達(1993—)，男，山東臨沂人，碩士研究生，主要從事過程挖掘和Petri網(wǎng)方面的研究. 杜玉越(1960—)，男，山東聊城人，教授，博士生導師，CCF高級會員，主要從事軟件工程、形式化技術(shù)和Petri網(wǎng)方面的研究.E-mail:yydu001@163.com 劉 偉(1977—)，男，山東青島人，副教授，博士，CCF會員，主要從事Petri網(wǎng)、工作流、Web服務的研究.

TP311

A

1672-3767(2017)01-0118-07