方賢文,楊慧慧,邵叱風(fēng)

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

流程挖掘是一門介于計(jì)算智能和數(shù)據(jù)挖掘以及過程建模和分析之間的新興研究學(xué)科，流程挖掘的起點(diǎn)是事件日志，所有流程挖掘技術(shù)都假設(shè)有可能順序地記錄事件，使每個(gè)事件指向一個(gè)活動(dòng)，并與特定的案例(即流程實(shí)例)相關(guān)。流程挖掘主要包括三個(gè)領(lǐng)域：流程發(fā)現(xiàn)、一致性檢查和流程增強(qiáng)。最近新興的模型修復(fù)領(lǐng)域，也算是流程增強(qiáng)的一種。本文的研究側(cè)重于一致性檢查與模型修復(fù)。

一致性檢查是將現(xiàn)有流程模型與同一流程的事件日志進(jìn)行比較。一致性檢查可以用來檢查記錄在日志中的事實(shí)是否符合模型。文獻(xiàn)[5]中針對(duì)聲明性模型提出了一種新的一致性檢查方法，文中采用了基于對(duì)齊的方法，以便能夠處理聲明式模型固有的靈活性帶來的巨大搜索空間。文獻(xiàn)[6]中提出了一種檢驗(yàn)序列圖與狀態(tài)圖一致性的方法。在比較過程模型和事件日志有不同的質(zhì)量維度，例如適應(yīng)度、簡單性、精度和泛化。而在本文中，我們關(guān)注于適應(yīng)度:一個(gè)具有良好適應(yīng)性的模型允許在事件日志中看到的大多數(shù)行為。如果日志中的所有軌跡都能被模型從頭到尾重復(fù)播放，那么模型就具有完美的適用性。

模型修復(fù)主要針對(duì)事件日志與原始模型不符合的部分進(jìn)行修復(fù)，最大程度地與原始模型保持相似。文獻(xiàn)[9]將一致性檢查的信息用于模型修復(fù)，識(shí)別流程模型中已刪除活動(dòng)的結(jié)構(gòu)、附加活動(dòng)和鄰接活動(dòng)之間的關(guān)系以及流程模型中的不一致子流程，基于文中所提出的技術(shù)實(shí)現(xiàn)模型修復(fù)。文獻(xiàn)[10]使用一個(gè)現(xiàn)有的一致性檢查器，將日志分解為不匹配子跡的幾個(gè)子日志，并對(duì)每個(gè)子日志派生出一個(gè)子流程，最后將其添加到原始模型的適當(dāng)位置，從而達(dá)到修復(fù)一個(gè)流程模型的目的。文獻(xiàn)[11]主要致力于一種模型分解修復(fù)工具，分解后的模型修復(fù)是模型增強(qiáng)的一種方法。模型修復(fù)可以使得事件日志與流程模型有較高的適合度甚至完美適合度，因此，越來越多的學(xué)者致力于研究模型修復(fù)。

在已有的方法中最為經(jīng)典的修復(fù)方法之一是插入-跳過活動(dòng)修復(fù)法，此方法對(duì)于單個(gè)日志移動(dòng)來說比較容易理解和使用。但是，在大多數(shù)情況下會(huì)見到連續(xù)的日志移動(dòng)，那么在同一個(gè)位置單個(gè)的插入多個(gè)活動(dòng)事件，會(huì)構(gòu)成模型的繁瑣。因此，在已有的子流程修復(fù)算法的基礎(chǔ)上，本文針對(duì)含有連續(xù)日志移動(dòng)的流程模型修復(fù)問題，提供了一種用于輔助模型修復(fù)的有效尋找日志移動(dòng)可修復(fù)的庫所集的算法。從成本對(duì)齊的角度出發(fā)，根據(jù)檢測到的日志移動(dòng)部分借助于該算法可有效實(shí)現(xiàn)模型修復(fù)。

1 基本概念

定義1

(變遷發(fā)生規(guī)則)一個(gè)網(wǎng)系統(tǒng)是一個(gè)標(biāo)識(shí)網(wǎng)∑=(

P

,

T

;

F

,

M

)，并具有下面的變遷規(guī)則(1)對(duì)于變遷

t

∈

T

，如果?

p

∈

P

∶

p

∈

t

→

M

(

p

)≥1則說變遷

t

在標(biāo)識(shí)

M

有發(fā)生權(quán)，記為

M

[

t

>。(2)若

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

(跡，事件日志)設(shè)Φ是一組活動(dòng)名稱集合，若

α

∈Φ是一個(gè)活動(dòng)序列，則稱

α

是一條跡。若

L

∈

B

(Φ)是跡的有限非空的多重集，則稱

L

是一個(gè)事件日志。

定義3

(對(duì)齊)設(shè)

N

=(

P

,

T

,

F

,

α

,

m

,

m

)是一個(gè)Petri網(wǎng)，設(shè)

α

=

a

a

…

a

是一條跡，

α

到流程模型

N

之間的對(duì)齊

γ

=(

a

,

t

)(

a

,

t

)…(

a

,

t

)是滿足下列條件的移動(dòng)序列：(1)對(duì)齊

γ

的第一行(

a

,

a

,…,

a

)是事件日志中的一條跡；(2)對(duì)齊

γ

的第二行(

t

,

t

,…,

t

)是Petri網(wǎng)流程模型N中的一組變遷發(fā)生序列；(3)對(duì)于所有的

i

=1, 2, …,

k

, 如果

t

≠?,

α

(

t

)≠

τ

,且

a

≠?，那么

α

(

t

)=

a

。

這里的移動(dòng)對(duì)滿足以下條件：

(1)如果

a

=?∧

t

≠?，則稱為模型移動(dòng)；(2)如果

a

≠?∧

t

=?，則稱為日志移動(dòng)；(3)如果

a

≠?∧

t

≠?，則稱為同步移動(dòng)；

定義4

(最優(yōu)對(duì)齊)給定一條跡

α

和Petri網(wǎng)流程模型

N

， 對(duì)于

α

和

N

之間所有的對(duì)齊

χ

, ?

γ

∈

χ

,對(duì)?

γ

′∈

χ

,都有

c

(

γ

)≤

c

(

γ

′)。則稱

γ

是

α

和

N

之間的最優(yōu)對(duì)齊。

定義6

(行為輪廓)設(shè)(

N

,

M

)是一個(gè)網(wǎng)系統(tǒng)，初始標(biāo)識(shí)為

M

，對(duì)任給的變遷對(duì)(

x

,

y

)∈

T

×

T

滿足以下關(guān)系：(1)若

x

>

y

且

y

≯

x

， 則稱為嚴(yán)格序關(guān)系， 記作

x

→

y

；(2)若

x

≯

y

且

y

≯

x

，則稱為排他關(guān)系，記作

x

+

y

；(3)若

x

>

y

且

y

>

x

， 則稱為交叉序關(guān)系， 記作

x

‖

y

；(4)所有關(guān)系的集合稱為網(wǎng)系統(tǒng)的行為輪廓，記作

BP

={→,+,‖}。

2 物流派送流程模型的一致性檢查

隨著國民經(jīng)濟(jì)的快速發(fā)展，社會(huì)物流需求也顯著增加，我國物流工程發(fā)展迅速。表1是從某物流公司派送包裹記錄中調(diào)取的部分事件日志，表2是各個(gè)字母所代表的活動(dòng)事件。

表1 記錄的事件日志

表2 各個(gè)字母所代表的活動(dòng)事件

圖1 基于Petri網(wǎng)的物流派送流程模型N

由表1提供的事件日志，得到合并后的跡及實(shí)例數(shù)為

α

=〈a,b,d,c,e,f,j,k,l〉，

α

=〈a,c,b,e,d,f,g,h,k,l〉，

α

=〈a,b,c,d,f,e,i,k,l〉，

α

=〈a,c,e,b,d,n,f,j,k,l〉，

α

=〈a,b,c,d,m,o,f,e,j,k,l〉，

α

=〈a,b,c,p,e,d,g,h,m,o,f,k,l〉，

α

=〈a,b,d,c,n,f,e,i,k,l〉。

3 流程模型修復(fù)分析

(1)尋找日志移動(dòng)的可修復(fù)庫所集

通過事件日志與流程模型的一致性檢查，可以看到跡

α

、

α

、

α

、

α

與流程模型之間存在偏差，偏差成本分別為1，2，3，1，因此，要想讓流程模型能夠重放所有的跡，必須要對(duì)流程模型進(jìn)行修復(fù)。根據(jù)跡與流程模型之間的最優(yōu)對(duì)齊，可以很明顯地看出需要修復(fù)的部分屬于日志移動(dòng)。對(duì)于單個(gè)日志移動(dòng)的修復(fù)，可以采用經(jīng)典的“插入和跳過活動(dòng)”的方法對(duì)模型進(jìn)行修復(fù)，然而有些日志移動(dòng)是連續(xù)出現(xiàn)的，此時(shí)可以根據(jù)文獻(xiàn)[13]中提到的基于子流程的修復(fù)算法進(jìn)行模型修復(fù)。

這種對(duì)單個(gè)日志移動(dòng)或者連續(xù)日志移動(dòng)進(jìn)行模型修復(fù)的方法，都是需要插入相應(yīng)的活動(dòng)事件。因此在修復(fù)之前，尋找最適合插入活動(dòng)事件的庫所也是一個(gè)關(guān)鍵環(huán)節(jié)。在選擇適合被插入的庫所方面，文獻(xiàn)[13]中有簡單描述，但并沒有給出具體形式的算法，因此，本文針對(duì)單個(gè)日志移動(dòng)或者連續(xù)日志移動(dòng)在進(jìn)行模型修復(fù)時(shí)如何選擇對(duì)應(yīng)庫所做了一個(gè)算法補(bǔ)充，算法如下

算法1：尋找日志移動(dòng)的可修復(fù)庫所集

輸入：日志中所有的最優(yōu)對(duì)齊

γ

,

γ

,…,

γ

；一個(gè)Petri網(wǎng)流程模型

N

輸出：日志移動(dòng)的可修復(fù)庫所集

P

Step1設(shè)

p

為初始庫所，

γ

[]為第

i

個(gè)對(duì)齊中第

j

個(gè)移動(dòng)對(duì)，

P

[]為第

i

個(gè)對(duì)齊中第

j

個(gè)移動(dòng)對(duì)所對(duì)應(yīng)的庫所，

m

為初始標(biāo)識(shí)。Step2如果

γ

[]是一個(gè)日志移動(dòng)，則

P

[]=(

p

)；否則，

m

[

π

(

γ

[])>

m

，在

m

狀態(tài)下有

m

(

p

)=…=

m

(

p

)=1，那么

P

[]=(

p

,…,

p

)

.

Step3當(dāng)2≤

j

≤|

γ

|時(shí)，如果

γ

[]是日志移動(dòng)，則

P

[]=

P

[-1]，若

γ

[],

γ

[+1],…,

γ

[+]是連續(xù)的日志移動(dòng)，則有

P

[]=

P

[+1]=…=

P

[+]

.

Step4當(dāng)2≤

j

≤|

γ

|時(shí)，如果

γ

[]不是日志移動(dòng)，則

m

[-1][

π

(

γ

[])>

m

，在

m

狀態(tài)下，

m

(

p

)=…=

m

(

p

)=1，則

P

[]=(

p

,…,

p

)，然后執(zhí)行Step5.Step5每一個(gè)對(duì)齊中，只保留日志移動(dòng)對(duì)中對(duì)應(yīng)的

P

[],然后刪除其余移動(dòng)對(duì)所對(duì)應(yīng)的庫所。Step6觀察所有保留的日志移動(dòng)對(duì)，如果不同對(duì)齊中有相同的日志移動(dòng)，即

γ

11=

γ

22=…=

γ

,其中1≤

it

≤

s

，1≤

jf

≤|

γ

|，那么若

P

[11]∩

P

[22]∩…∩

P

[]=

P

′≠?，則更新這些日志移動(dòng)的庫所表示為

P

,即

P

[11]=

P

[22]=…=

P

[]=

P

′；否則，若交集為空集，則無需變動(dòng)。然后執(zhí)行Step7.Step7整理保留下來的庫所集

P

[]，得到一個(gè)日志移動(dòng)的可修復(fù)庫所集

P

={

P

[]}算法結(jié)束。根據(jù)上述算法，尋找最優(yōu)對(duì)齊

γ

,

γ

,

γ

,

γ

中日志移動(dòng)所對(duì)應(yīng)的可用于修復(fù)的庫所集。首先輸入四個(gè)最優(yōu)對(duì)齊

γ

,

γ

,

γ

,

γ

和Petri網(wǎng)流程模型

N

，第一步交代了字母所代表的含義和初始狀態(tài)

m

(

p

)=1；第二步表示在一個(gè)最優(yōu)對(duì)齊中，第一個(gè)移動(dòng)對(duì)若是日志移動(dòng)，那么它所對(duì)應(yīng)的可修復(fù)庫所為

P

[]=(

p

)，否則按照正常的變遷發(fā)生規(guī)則依次觸發(fā)后面的活動(dòng)事件；第三步說明了出現(xiàn)連續(xù)日志的情況下，對(duì)應(yīng)可修復(fù)庫所是相同的；第四步表示在依次尋找最優(yōu)對(duì)齊中所有移動(dòng)對(duì)所對(duì)應(yīng)的庫所，對(duì)最優(yōu)對(duì)齊

γ

,

γ

,

γ

,

γ

的執(zhí)行結(jié)果為

γ

[1]=〈

a

,

a

〉,

P

[1]=(

p

,

p

);

γ

[1]=〈

c

,

c

〉,

P

[1]=(

p

,

p

);…;

γ

[1]=〈

d

,

d

〉,

P

[1]=(

p

,

p

);

γ

[1]=〈

n

,?〉,

P

[1]=

P

[1]=(

p

,

p

);…;

γ

[2]=〈

m

,?〉,

P

[2]=(

p

,

p

);

γ

[2]=〈

o

,?〉,

P

[2]=

P

[2]=(

p

,

p

);…;

γ

[3]=〈

p

,?〉,

P

[3]=(

p

,

p

);…;

γ

[3]=〈

m

,?〉,

P

[3]=(

p

,

p

);

γ

[3]=〈

o

,?〉,

P

[3]=

P

[3]=(

p

,

p

);…;

γ

[4]=〈

n

,?〉,

P

[4]=(

p

,

p

);…;

γ

[4]=〈

l

,

l

〉,

P

[4]=(

p

)；第五步是只保留了日志移動(dòng)對(duì)所對(duì)應(yīng)的庫所，此時(shí)的執(zhí)行結(jié)果為：

γ

[1]=〈

n

,?〉,

P

[1]=(

p

,

p

);

γ

[2]=〈

m

,?〉,

P

[2]=(

p

,

p

);

γ

[2]=〈

o

,?〉,

P

[2]=(

p

,

p

);

γ

[3]=〈

p

,?〉,

P

[3]=(

p

,

p

);

γ

[3]=〈

m

,?〉,

P

[3]=(

p

,

p

);

γ

[3]=〈

o

,?〉,

P

[3]=(

p

,

p

);

γ

[4]=〈

n

,?〉,

P

[4]=(

p

,

p

)；繼而執(zhí)行第六步，觀察所有保留的日志移動(dòng)對(duì)，如果不同對(duì)齊中有相同的日志移動(dòng)，則取它們對(duì)應(yīng)庫所的交集，若交集為空集，則無需變動(dòng)。此步驟執(zhí)行結(jié)果為：

P

[1]=

P

[4]=(

p

);

P

[2]=

P

[3]=(

p

);

P

[2]=

P

[3]=(

p

);

P

[3]=(

p

,

p

)；最后執(zhí)行第七步，整理保留下來的庫所集，得到一個(gè)日志移動(dòng)的可修復(fù)庫所集

P

={

P

[1]=

P

[4]=(

p

);

P

[2]=

P

[3]=(

p

);

P

[2]=

P

[3]=(

p

);

P

[3]=(

p

,

p

)}

.

(2)物流派送流程模型修復(fù)及驗(yàn)證分析

找到日志移動(dòng)的可修復(fù)庫所集，便可根據(jù)“插入和跳過活動(dòng)”的方法和基于子流程的修復(fù)算法對(duì)模型進(jìn)行修復(fù)。通過觀察，日志移動(dòng)〈

p

,?〉是單個(gè)日志移動(dòng)，且不同對(duì)齊中沒有與之相同的日志移動(dòng)，因此，修復(fù)模型時(shí)只需在庫所

p

或

p

上插入活動(dòng)事件

p

即可，修復(fù)結(jié)果如圖2所示。對(duì)于日志移動(dòng)〈

m

,?〉，〈

o

,?〉是連續(xù)的日志移動(dòng)，而且不同對(duì)齊中有相同的日志移動(dòng)，對(duì)應(yīng)庫所交集為

p

，這與日志移動(dòng)〈

n

,?〉所對(duì)應(yīng)庫所一致，因此，同時(shí)在同一個(gè)庫所上插入三個(gè)活動(dòng)事件，需要考慮這三個(gè)事件是否具有某種行為關(guān)系，通過分析日志可知，活動(dòng)事件

m

,

o

的每次執(zhí)行都是同時(shí)出現(xiàn)且具有一定的順序關(guān)系，而且并沒有與活動(dòng)事件

n

同時(shí)出現(xiàn)過，因此，判斷活動(dòng)事件

m

,

o

是嚴(yán)格序關(guān)系，且與活動(dòng)事件

n

是排他序關(guān)系。因此通過它們之間的行為輪廓關(guān)系，構(gòu)建一個(gè)子流程，如圖3所示，然后將子流程按照基于子流程的模型修復(fù)算法，插入到模型中的

p

上。故最終修復(fù)模型如圖4所示。

圖2 插入活動(dòng)事件p的修復(fù)模型N1 圖3 根據(jù)行為輪廓關(guān)系構(gòu)建的子流程

圖4 最終修復(fù)模型N′

為了驗(yàn)證修復(fù)模型的合理性，計(jì)算了修復(fù)模型與日志的適合度。其中適合度公式如下

fitness(

L

,

M

)=

(1)

c

(

γ

)+

c

(

γ

)+

c

(

γ

)=0，因此fitness(

L

,

M

)=1-0=1。從而說明了事件日志與修復(fù)模型完全擬合。

4 結(jié)論

本文主要基于Petri網(wǎng)構(gòu)建了一個(gè)物流派送的流程模型，并對(duì)事件日志與流程模型進(jìn)行了一致性檢查及模型修復(fù)分析。首先，本文根據(jù)給定事件日志構(gòu)建一個(gè)流程模型。其次，主要基于成本對(duì)齊的方法，根據(jù)其成本大小判斷事件日志與流程模型之間的偏差大小。在對(duì)偏差部分進(jìn)行模型修復(fù)過程中，本文給出了尋找日志移動(dòng)的可修復(fù)庫所集的算法，該算法有助于實(shí)現(xiàn)模型修復(fù)。最后，根據(jù)基于子流程的模型修復(fù)方法以及行為輪廓關(guān)系對(duì)模型進(jìn)行修復(fù)，使得流程模型能夠完全重放事件日志，并最大可能地與原始模型相似。通過計(jì)算得到日志與模型間的適合度為1，從而也說明修復(fù)模型具有合理性。

未來工作中，將致力于在修復(fù)模型適合度為1的情況下盡可能提高其精確度，并使得修復(fù)模型具有普遍適用性。