盛夢君，方賢文，邵叱風

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

模型修復(fù)是一種新的過程挖掘技術(shù)，它將事件日志和流程模型作為輸入，通過對日志進行分析來發(fā)現(xiàn)流程模型中的偏差，進而對模型進行修復(fù)。目前，可以通過事件日志來研究系統(tǒng)的真實情況，運用過程挖掘技術(shù)得到流程模型。但是，由于挖掘出能夠確切描述現(xiàn)實生活的系統(tǒng)模型是困難的，且流程往往會在系統(tǒng)的生命周期中發(fā)生變化。因此，對于模型修復(fù)問題的研究具有重要意義。

關(guān)于模型修復(fù)國內(nèi)外學(xué)者已經(jīng)做了很多工作。過程挖掘技術(shù)一共有三類應(yīng)用：模型發(fā)現(xiàn)、一致性檢測和過程增強，模型修復(fù)屬于過程增強。評價過程模型的質(zhì)量有四個標準：擬合度、精確度、泛化度和簡化度。工作流網(wǎng)中適應(yīng)性感知控制流修復(fù)的方法通過事件日志將不符合要求和符合要求的跡分開，將不合格的跡分解為不合格的子日志，每個子日志都能在相應(yīng)的子流程工作流網(wǎng)中被發(fā)現(xiàn)，然后以這種方式將這些子流程添加到初始模型中，使得修復(fù)后的模型能夠成功重放給定的事件日志。這種方法還允許刪除不常使用的模型片段，令修復(fù)后的模型更簡單，但這種刪除方式略顯暴力，并不是簡化模型的最佳方法?；诖耍ㄟ^一種簡化模型結(jié)構(gòu)的方法，使得模型仍然可以重放日志中描述的大多數(shù)行為?，F(xiàn)有的模型修復(fù)方法大多側(cè)重于通過一致性檢驗找到事件日志與模型之間的偏差，但未側(cè)重修復(fù)偏差問題?；趯R的概念，建議改變運營分配成本，通過調(diào)查所有可能的修復(fù)空間，提出并評估了一組最優(yōu)修復(fù)算法，將Petri網(wǎng)的修復(fù)問題簡化為了優(yōu)化問題。通過考慮過程挖掘中應(yīng)用分而治之原則的問題，提出一個過程發(fā)現(xiàn)的模式，該修復(fù)方法也是利用分而治之的思想進行模塊化修復(fù)。通過分析事件日志來研究系統(tǒng)的真實情況，發(fā)現(xiàn)真實系統(tǒng)模型，工程師可以使用一致性檢驗技術(shù)來診斷觀察事件日志和流程模型之間的差異。但一味地提高修復(fù)后模型的適應(yīng)度或簡化度會讓修復(fù)成本大大提高，并且修復(fù)過程中事件日志遍歷的次數(shù)過大，與其修復(fù)模型不如重新通過事件日志挖掘新模型。因此，進一步降低修復(fù)成本，減少以往修復(fù)算法的迭代次數(shù)和遍歷事件日志的次數(shù)以及修復(fù)算法的時間復(fù)雜度是本文針對的問題。

針對上述問題，本文提出了基于行為輪廓的流程模型修復(fù)方法，運用模型分解及線性過濾的方法對模型進行修復(fù)，盡可能地保持初始模型結(jié)構(gòu)不改變、原模型可讀以及結(jié)構(gòu)良好的性能來進一步降低修復(fù)成本，降低修復(fù)算法的時間復(fù)雜度。此外，還給出了過濾模塊以及選擇模塊中相應(yīng)的算法，從而較好地提升了模型修復(fù)的有效性。

1 基礎(chǔ)知識

定義1(流程模型Petri網(wǎng))滿足以下條件的四元組

N

=(

P

,

T

,

F

,

C

)稱作一個流程模型Petri網(wǎng)：(1)

P

是有限非空庫所集，

T

是有限非空變遷集；(2)

P

∪

T

≠

φ

且

P

∩

T

=

φ

；(3)

F

?(

P

×

T

)∪(

T

×

P

)是

N

中的流關(guān)系，(

P

∪

T

,

F

)是強連通圖；(4)

dom

(

F

)∪

cod

(

F

)=

P

∪

T

，其中

dom

(

F

)={

x

∈

P

∪

T

|?

y

∈

P

∪

T

∶(

x

,

y

∈

F

)}

cod

(

F

)={

x

∈

P

∪

T

|?

y

∈

P

∪

T

∶(

y

,

x

∈

F

)}；(5)

C

={and,xor,or}是流程網(wǎng)的結(jié)構(gòu)類型。定義2(行為輪廓)設(shè)

P

=(

A

,

I

,

C

,

F

,

T

)是一個流程模型(

x

,

y

)∈((

N

∪

F

)×(

N

∪

F

))是滿足下列關(guān)系中的一個：(1)嚴格序關(guān)系→，如果

x

?

y

且

y

?

x

；(2)排他關(guān)系+，如果

x

?

y

且

y

?

x

；(3)交叉序關(guān)系‖，如果

x

?

y

且

y

?

x

。以上三種關(guān)系的集合是

P

=(

A

,

I

,

C

,

F

,

T

)的行為輪廓。定義3(流程模型)將流程模型設(shè)定為一個元組

M

=(

P

,

T

,

F

,

J

,

ε

,

σ

,

M

,

M

)，

P

是庫所集?

p

∈

P

；

T

是變遷集?

t

∈

T

；

F

是連接所有直接跟隨庫所與變遷之間的流關(guān)系，

F

?(

P

×

T

)(

T

×

P

)；

J

是排序的有限集合；

ε

是滿射函數(shù)，將每個變遷關(guān)聯(lián)到一個排序，

T

→

J

；

σ

是指定函數(shù)，將所有變遷映射到活動集或靜默變遷中，

T

→

A

∪{

τ

}，

σ

(

t

)=?(

e

)=

a

,?

a

∈

A

，

τ

∈

T

,

σ

(

τ

)?

A

；

M

是初始標識；

M

是終止標識。

圖1 流程模型工作流網(wǎng)示例

表1 圖1 示例中字母代表的活動事件

定義4(事件日志，跡)事件日志是一個數(shù)學(xué)模型，用于捕獲有關(guān)動態(tài)系統(tǒng)執(zhí)行的歷史信息。從形式上講，定義

Σ

是一組動作集，跡

l

∈

Σ

是一個動作序列，

L

∈

ΙΒΣ

)是一個事件日志即一組跡的多元集。其中每組跡都是將系統(tǒng)(即流程實例)的執(zhí)行描述為一系列觀察到的事件。因為可以存在多個具有相同跡的情況，如果跡的頻率不相關(guān)，將記錄日志稱為一組跡

L

={

l

,…,

l

}。定義5(工作流網(wǎng)的有效分解)設(shè)

N

∈

U

是一個帶標簽函數(shù)

l

的工作流網(wǎng)。

D

={

N

,

N

,…,

N

}?

U

是一個有效的分解，當且僅當：—任意1≤

i

≤

n

，

N

=(

P

,

T

,

F

,

l

)是一個Petri網(wǎng)，—任意1≤

i

≤

n

，

l

=

lΓ

，—任意1≤

i

<

j

≤

n

，則

P

∩

P

=0，

—

N

=∪1≤≤

N

D

(

N

)對任意網(wǎng)

N

是一個有效分解集。

2 本文方案

(1) 模塊化修復(fù)框架

本文考慮的修復(fù)問題：給定工作流網(wǎng)N和事件日志L，事件日志L不完全符合N，提出了一種基于模型分解及線性過濾的模塊化修復(fù)方法，構(gòu)造模型Nr(修復(fù)后模型)，讓Nr能夠重放L。主要思想是基于分而治之的原則篩選出需要修復(fù)的片段，修復(fù)方法由構(gòu)建的塊組成，每個塊執(zhí)行其中一個步驟，模塊化模型修復(fù)方法如圖2所示，構(gòu)建的塊分別為：①分解；②過濾；③選擇；④修復(fù)；⑤組合；⑥案例分析?；”硎緣K之間的數(shù)據(jù)傳輸。

圖2 模塊化修復(fù)框架

本文基于模塊化模型修復(fù)的一般方法如下：該方法的輸入是一組(

L

，

N

)，其中

L

是一組事件日志，

N

是一個不完全符合事件日志的初始模型。在分解塊中，使用極大分解算法將模型N分解成幾個片段，分解結(jié)果是唯一的。在過濾塊中，本文給出了一個包含在過濾塊中線性過濾算法，算法將這些模型片段即子模型的直鏈結(jié)構(gòu)進行過濾篩除，直鏈結(jié)構(gòu)不執(zhí)行下一步選擇過程，從而直接保留直鏈的原始模型片段，最后與修復(fù)后的模型片段組合。在選擇塊中，選擇算法將分解后的子模型的執(zhí)行序列與新增的兩條事件日志的跡運用行為輪廓相關(guān)知識進行比對，符合事件日志的跡即為優(yōu)子模型，反之為劣子模型。在修復(fù)塊中，將剩下的劣子模型與事件日志對比分析運用感應(yīng)挖掘算法進行修復(fù)。在組合塊中，將過濾掉的直鏈結(jié)構(gòu)、優(yōu)子模型和修復(fù)后的子模型進行組合，得到能夠重放事件日志修復(fù)后的模型。

(2)使用極大分解方法進行模塊化修復(fù)

本文提出的模塊化修復(fù)方法在每個構(gòu)建的塊中使用特定算法。其中分解塊中使用的極大分解方法是一個有效分解，極大分解是基于邊緣的劃分，其定義如下：每個變遷嚴格地位于單個片段中，具有唯一標簽的變遷被放置在片段的邊界上，在片段之間需要有因果關(guān)系的支持。因此，對于每個變遷，一個在初始網(wǎng)中具有唯一標簽的變遷將存在于兩個或者多個片段中，最后，拆分保存了網(wǎng)絡(luò)的初始標識。如果庫所在初始網(wǎng)中被標記了，那么它在片段中也是被標記的。在給定的系統(tǒng)網(wǎng)中，有且僅有一個極大分解，且分解結(jié)果是唯一的。極大分解網(wǎng)能夠很容易地通過融合有相同標簽的變遷組合回完整的網(wǎng)。

圖3 圖1中模型的極大分解

將文獻中提出的極大分解算法應(yīng)用到分解塊中，并在此基礎(chǔ)上開發(fā)了過濾塊和選擇塊的算法，其工作原理如下：如果網(wǎng)片段發(fā)現(xiàn)可見的變遷，可依據(jù)decompose、handlePlace、handlePlace recursively三個函數(shù)的工作原理調(diào)用以后對其進行分解。即decompose函數(shù)從初始網(wǎng)中任意庫所開始，當有庫所需要遍歷時調(diào)用handlePlace函數(shù)，調(diào)用handlePlace函數(shù)后，調(diào)用handlePlace recursively函數(shù)來遍歷此流程中庫所的前置節(jié)點和后繼節(jié)點。以初始網(wǎng)圖1中庫所p為例，調(diào)用后三個函數(shù)后它的前置節(jié)點為變遷A和變遷G，后繼節(jié)點為變遷B，因此分解后片段為圖3中SN2片段。

初始網(wǎng)圖1中完整流程模型分解后得到的全部子模型如圖3所示；過濾塊中運用線性過濾算法再將其進行過濾，若子模型中的庫所前、后集個數(shù)分別為1或0，則可直接過濾此直鏈結(jié)構(gòu)，直鏈結(jié)構(gòu)不執(zhí)行下一步選擇過程，過濾后的模型片段如圖4所示；過濾后選擇劣子模型進行修復(fù)，選擇塊中的選擇算法將過濾后模型片段的執(zhí)行序列與增加的事件日志運用Petri網(wǎng)中行為輪廓定義進行比對，符合的為優(yōu)子模型，反之為劣子模型。過濾算法及選擇算法如下：

輸入：ModelSet

ε

輸出：ModelSet

φ

ModelSet

ε

;ModelSet

φ

=Null;1)for each part model A in ModelSet

ε

;

2)pre set of place=prsp;

3)post set of place=posp;

4)if |prsp|=|posp|=1 || (|prsp |=1 and |posp|=0)|| (|posp |=1 and |prsp|=0)

5)part model A is null;

6)break;

7)else

8)Return (prsp X posp) of A

9)end if

10)

φ

.add(part model);

11)end for each

12)for each (

x

,

y

) in (prsp X posp)

13)for each Trace in New Log

14)if

x

in Trace and y not in pre of

x

;15)return (

x

,

y

) , part Model of (

x

,

y

)

16)end for each

17)end all

圖4 圖3過濾后模型片段

文獻[13]已有許多流程發(fā)現(xiàn)的算法，本文使用感應(yīng)挖掘保證模型發(fā)現(xiàn)的適應(yīng)性(零噪音閾值的不頻繁感應(yīng)挖掘)。它使用順序和回歸的感應(yīng)推理來構(gòu)建一個可以轉(zhuǎn)化為工作流網(wǎng)結(jié)構(gòu)的過程樹。

假設(shè)圖3中的模型中變遷C和E與其行為順序不完全一致，如果二者同時出現(xiàn)，則在事件日志的跡中E總是在C之前出現(xiàn)，根據(jù)行為輪廓，即E和C是嚴格序關(guān)系，記作E→C，也就是說事件日志包含跡和，沒有C在E之前出現(xiàn)的跡。應(yīng)用本文提出的選擇算法，如圖4所示，得到的片段SN4不完全適合日志，因此我們使用感應(yīng)挖掘算法發(fā)現(xiàn)了這個正確的工作流網(wǎng)片段SN4如圖5所示。

圖5 通過感應(yīng)挖掘發(fā)現(xiàn)此模型片段

在發(fā)現(xiàn)正確的模型片段并組合所有片段之后，得到了如圖6所示的網(wǎng)。這個模型與事件日志的跡和完全適應(yīng)。可以看到修復(fù)過的模型不是工作流網(wǎng)，它包含源位置的標識和初始標識中的初始庫所。網(wǎng)的最終標識包括在接收器和庫所中的兩個托肯，這個模型可以通過添加靜默的開始和結(jié)束變遷很容易地轉(zhuǎn)換成等效的工作流網(wǎng)。考慮到開始庫所和結(jié)束庫所限制模型的行為并可能產(chǎn)生死鎖，從而將它們刪除。但在模型運行中增加可能發(fā)生的變遷，會稍微降低模型的精度，避免這樣的問題最好不要在修復(fù)過程中更改片段邊界節(jié)點變遷，因此可以通過考慮更大的片段來完成修復(fù)。

圖6 變遷組合后的Petri網(wǎng)

3 案例分析

本節(jié)以上述退換貨系統(tǒng)為例計算修復(fù)前后模型的適合度來評估所提方法的可行性，并與Fahland修復(fù)方法進行對比實驗。

在給定事件日志L和模型M上進行實驗評估。如表2所示，事件日志L一共包含事件總數(shù)為：|

N

|=12 781，其運行次數(shù)依次為{58,87,230,270,198,205,109,26,100,12,49,210,180,33,101}。事件日志中總共有15條完整有效的執(zhí)行序列，大小分別為{6,7,10,11,12,15,16,14,13,15,14,13,10,8,7}，預(yù)定義模型上的所有發(fā)生序列大小依次為{7,7,10,10,12,15,16,14,12,15,15,12,10,7,7}。將日志與模型進行最優(yōu)校準，得到15組最優(yōu)校準。

表2 網(wǎng)購?fù)藫Q貨系統(tǒng)的事件日志

分析得到的15組最優(yōu)校準，這些校準中的不一致由偏差引起，偏差分為日志插入偏差和網(wǎng)

N

跳過偏差，如案例1即

n

=1中是日志插入偏差，

n

=2中是網(wǎng)

N

跳過偏差。因此，日志與初始模型之間的擬合度為

(1)

式中：

L

表示每組發(fā)生序列的發(fā)生次數(shù)即實例數(shù)，

n

表示校準的組數(shù)(本文有15組)，

C

表示每組校準的偏差成本，這里將所有偏差成本設(shè)為1，

M

表示日志發(fā)生序列，

M

表示模型中的發(fā)生序列，

ε

表示日志發(fā)生序列的元素個數(shù)，

δ

表示模型發(fā)生序列的元素個數(shù)，而日志與修復(fù)后模型之間的適合度為1，因此本文的修復(fù)方法具有可行性。根據(jù)本文所提算法的第12～17兩層嵌套循環(huán)可以看出，其算法的時間復(fù)雜度為

O

(

MN

)。運用Fahland方法對案例模型修復(fù)結(jié)果如圖7所示，與本文所提方法的對比實驗結(jié)果如表3所示。

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

表3 修復(fù)結(jié)果對比數(shù)據(jù)

4 結(jié)論

本文在已有研究的基礎(chǔ)上提出了一種基于模型分解和線性過濾的模塊化流程模型修復(fù)方法，通過線性過濾算法進一步有效降低了修復(fù)的成本和修復(fù)算法的時間復(fù)雜度,并且盡可能保持了初始模型結(jié)構(gòu)。首先將初始模型運用極大分解算法分解，其次使用過濾算法進行線性過濾，再使用選擇算法選擇劣子模型然后通過感應(yīng)挖掘重新發(fā)現(xiàn)模型片段，最后對模型片段進行組合得到修復(fù)后模型。

本文的方法可能略微降低了模型的精度，對于此問題，計劃提出更細微的分解技術(shù)以避免片段邊界節(jié)點的相關(guān)問題?；诜纸獾哪Ｐ托迯?fù)也會考慮到擬合度，精確度，泛化度和簡化度的組合度量，此外修復(fù)是基于模型，對模型分解的相關(guān)問題可能非常有幫助，這也是未來可以研究的方向之一。