祁宏達(dá)，杜玉越，劉 偉

(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

一種基于可達(dá)標(biāo)識(shí)的過程模型修復(fù)方法

祁宏達(dá)，杜玉越，劉 偉

(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

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

校準(zhǔn)；模型修復(fù)；擴(kuò)展校準(zhǔn)；修復(fù)算法

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

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

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

作為一種新的過程挖掘的應(yīng)用技術(shù)，模型修復(fù)技術(shù)屬于過程增強(qiáng)這一范疇[4]。模型修復(fù)以事件日志和過程模型作為輸入，如果存在事件日志中的跡不能夠在過程模型中重演，則需要對(duì)過程模型進(jìn)行修改。修改后的模型要盡量與原始模式相似，即不改變?cè)寄Ｐ偷幕窘Y(jié)構(gòu)。

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

1 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

1) π1(γ)↓A=σ，即校準(zhǔn)中所有的第一元素對(duì)應(yīng)一條跡；

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

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

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

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

2 擴(kuò)展校準(zhǔn)

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

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

1)γ是一個(gè)跡σ和模型PN之間的校準(zhǔn)；

2)mi[π2(π1(β)↓γ) ↓T>mf，即擴(kuò)展移動(dòng)隊(duì)列在模型中的移動(dòng)發(fā)生后，最終會(huì)到達(dá)終止標(biāo)識(shí)；

Bσ,PN是跡σ和模型PN之間所有擴(kuò)展校準(zhǔn)的集合。需要指出的是，當(dāng)前動(dòng)作的可達(dá)標(biāo)識(shí)與前一動(dòng)作的可達(dá)標(biāo)識(shí)相同，為iffπ2(π1(β)↓γ)↓T= ?。

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

圖1 Petri網(wǎng)PN1

圖2 跡σ1的擴(kuò)展校準(zhǔn)

對(duì)于(d,d,m2)，可達(dá)標(biāo)識(shí)m2:m2(p2) =m2(p5)=1,m2(p1)=m2(p3)=m2(p4)=m2(p6)=0。

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

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

對(duì)于圖2中的兩個(gè)擴(kuò)展校準(zhǔn)β1和β2，可能性代價(jià)值lc(β1)=2,lc(β2)=2，顯然，β1，β2均是是跡σ1的最優(yōu)擴(kuò)展校準(zhǔn)。

3 偏差修復(fù)方法

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

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

圖3 跡σ2的擴(kuò)展校準(zhǔn)

圖4 Fahland的方法修復(fù)后的模型

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

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

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

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

圖5 RMR方法修復(fù)后的模型

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

算法1指定庫(kù)所處日志動(dòng)作收集

輸出：變遷序列集合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；

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

算法2利用子日志修復(fù)過程模型

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

輸出：修復(fù)后的過程模型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′

通過這兩個(gè)算法，能夠收集指定庫(kù)所處出現(xiàn)的日志動(dòng)作，實(shí)現(xiàn)在指定庫(kù)所處對(duì)過程模型進(jìn)行修復(fù)。

4 實(shí)驗(yàn)

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

4.1 修復(fù)過程模型

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

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

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

對(duì)不同的庫(kù)所，按照算法1進(jìn)行變遷序列集合的收集，得到表2。

表1 3組事件日志

表2 各個(gè)位置處的變遷序列集合

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

圖7 Fahland的方法修復(fù)后的模型

圖8 RMR方法修復(fù)后的模型

4.2 模型評(píng)估

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

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

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

圖9 擬合度的變化

圖10 精確度的變化

5 總結(jié)

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

[1]曾慶田.流程挖掘的研究現(xiàn)狀和問題綜述[J].系統(tǒng)仿真學(xué)報(bào),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.

(責(zé)任編輯：傅 游)

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

國(guó)家自然科學(xué)基金項(xiàng)目(61170078,61472228); 泰山學(xué)者建設(shè)工程項(xiàng)目；山東省自然科學(xué)基金項(xiàng)目(ZR2014FM0 09)；山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金項(xiàng)目(BS2015DX010)

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

TP311

A

1672-3767(2017)01-0118-07