基于Petri網的模型偏差域識別與模型修正

杜玉越　孫亞男　劉　偉

(山東科技大學山東省智慧礦山信息技術重點省級實驗室　山東青島　266590)

?

基于Petri網的模型偏差域識別與模型修正

杜玉越孫亞男劉偉

(山東科技大學山東省智慧礦山信息技術重點省級實驗室山東青島266590)

(yydu001@163.com)

過程挖掘技術能夠通過事件日志建立過程模型，一致性檢測技術能夠發現過程模型和觀察行為間的偏差.然而，現有的過程挖掘技術著重于發現偏差，不易于修正偏差.因此，利用一致性檢測技術和工作流網模型的動態特性，提出一種基于Petri網的模型偏差域識別方法和模型修正技術(靜態模型修正和動態模型修正).通過跟蹤token流向，有效地識別模型偏差域，并對其進行修正，特別是能夠正確修正具有循環結構、選擇結構的復雜實際流程.最后，通過與其他方法的對比實驗和分析，驗證了本文方法的有效性和正確性.

一致性檢測；模型修正；偏差域；工作流網；token

隨著傳統生產流程理論、業務流程再造理論、工作流技術和管理技術的發展，業務過程管理在各企業和組織中都得到了相應的應用.但是，隨著企業和組織業務的增長、企業和組織之間合作程度的加強以及企業外部環境的變化，企業已有業務過程難以與企業和組織的發展相適應.因此，增強企業業務過程以提高企業和組織的競爭能力勢在必行.

過程挖掘通過從現代信息系統普遍可見的事件日志中提取知識，發現、監測和改進實際過程.過程挖掘主要包括3個部分：過程發現[1-6]、一致性檢測[7-8]和過程增強.

過程發現是從事件日志出發，構造出可以描述事件日志的模型.一致性檢測是指對發現的過程模型與事件日志比較，即將每條跡在模型中進行“重演”，分析模型行為與日志行為的一致性程度，是評價模型質量的重要標準.現有的一致性檢測方法有令牌重演、足跡對比、校準等.一致性檢測的目的是進行過程改善.有的研究以偏差檢測為基礎，對過程模型進行修正或擴展，如根據觀察到的行為與模型行為之間的偏差，提出常見的偏差模式，并給出能夠識別每一種偏差模式的Petri網片斷，或通過子過程擴展模型，使之和觀察到的行為有較高的擬合度.有的研究對不合理過程模型進行糾錯，從結構距離[9]、行為距離[10]和方案弊端[11]3個維度考慮，用模擬退火算法使之最小化，進而達到修正模型的目的.

現有模型偏差識別方法不能很好地識別存在偏差的模型區域，例如，利用校準識別偏差只能模糊地判斷可能存在偏差的區域，不能準確識別出每一個存在偏差的區域，所以修正結果也不理想.為使現有工作流網模型符合實際流程，根據實際流程產生的日志對工作流網模型修正.修正的前提是發現模型與實際流程間的偏差，對偏差區域修正.產生偏差最根本的原因是應該發生的活動沒有在模型中觸發，或者不應該發生的活動卻在模型中觸發了.在工作流網模型中，觸發模型變遷的因素是token，故token是一個網系統動態特性的直觀體現.因此，本文研究如何準確識別偏差和簡單有效地修正模型，基于工作流網中token的動態性，在一致性檢測(重演)的基礎上，提出一種基于token的模型偏差域識別方法和基于token的模型修正技術，提高了修正結果的擬合度和簡潔度.

1　有關概念

本節簡要介紹Petri網[12-16]、工作流網[17-19]、合理性[20]等的基本定義及有關符號表示.Petri網可用于分布式并發系統的建模與分析，并能夠直觀地將流程運行展現出來.它既能描述系統的結構又能模擬系統的運行.+表示一個正整數集合.

定義1. 多重集.S是一個集合，集合S上的多重集D是一個映射D：S→+.B(S)表示集合S上的所有多重集的集合.

例如，D=[a3,b,c2]是集合S上的一個多重集，其中a,b,c∈S，D(a)=3,D(b)=1,D(c)=2.

[1],σ

[2],…,σ[n]是一個序列，表示尖括號內元素的列表.A是一個集合，A*表示A上有限序列的集合.

|σ|=n表示σ的長度.對于?a∈A，σ(a)代表σ中a元素的個數，例如，σ(a)=|{σ[i]=a，1≤i≤|σ|}|.

定義3. 跡、事件日志. 設A是所有活動的集合，A?A.若活動序列σ∈A*，則稱σ是一條跡.若?L∈B(A*)是跡的一個多重集，稱L為一個事件日志.用&(σ)表示由跡σ中所有活動構成的集合.

例如，活動集合A={a,b,c,d}，σ=b,c,a,d即為一條跡，&(σ)={b,c,a,d}.

定義4. 前集、后集. 設N=(P,T;F)為一個網.其中，P為有限庫所的集合，T為有限變遷的集合，F是網N的流關系集合.對于x∈P∪T，記

?x={y|y∈P∪T∧(y,x)∈F}，

x?={y|y∈P∪T∧(x,y)∈F}，

稱?x為x的前集或輸入集，x?為x的后集或輸出集，稱?x∪x?為元素x的外延.

定義5. Petri網. 四元組Σ=(P,T;F,M)稱為一個Petri網，當且僅當

1)N=(P,T;F)為一個網；

2)M:P→+，M稱為網N的一個標識；

3) 變遷發生規則:

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

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

從M可達的一切標識的集合記為R(M)，約定M∈R(M).

下面給出工作流網(workflow net)的概念.

定義6. 工作流網.Petri網Σ=(P,T;F,M)稱為一個工作流網，當且僅當

1) 存在一個開始庫所i∈P，并且?i=?；

2) 存在一個結束庫所o∈P，并且o?=?;

3) 對于?x∈P∪T，x均位于從i到o的一條路徑上.

工作流網也記作WFN=(P,T;F,M,i,o).

在Petri網中，token可用來表示任務的前置和后置條件.因此，本文使用token代表工作流過程中的資源.

定義7. 子網. 網N=(P,T;F)，如果

1)P′∈P，T′∈T；

2)F′=((P′×T′)∪(T′×P′))∩F;

則稱N′=(P′,T′;F′)為網N的一個子網.

定義8. 死變遷.Σ=(P,T;F,M)是一個Petri網，t∈T,M0為初始標識，若?M∈R(M0)：M[t>，則稱變遷t為死變遷.

定義9. 合理性(Soundness).WFN=(P,T;F,M,i,o)是一個工作流網，i為開始庫所，o為結束庫所.WFN是合理的當且僅當

1) 對從i可達的任意標識M，存在變遷序列可到達終止標識；

2) 開始狀態可達終止狀態，終止標識是滿足o中至少包含一個token的標識；

3) 不存在死變遷.

2　模型偏差域識別

現實中流程不是既定不變的，流程往往會隨著實際情況的改變而變化，以便更好地適應不斷改變的環境.因此，需要根據實際流程產生的日志，對原有模型進行監測，判斷原有模型是否存在與實際流程不相符之處，如果存在，就要進行模型修正.本節提出一種模型偏差域識別方法，基于強制重演技術確定模型中存在偏差的區域.下面先介紹強制重演.

2.1強制重演

在工作流網中，利用token描述系統的行為，能夠有效實時地反映系統的動態變化，而且通過事件日志重演，能夠發現模型存在的偏差.

事件日志的重演[12-13]是指以一個事件日志和一個過程模型作為輸入，事件日志在過程模型上重新被執行一遍，記為Replay(Model,L).若跡與模型完全擬合，意味著跡會完全按照模型執行動作序列發生；若跡與模型不完全擬合，則當重演至跡與模型不符的動作時，將停止重演.然而，有些跡可能只有部分動作與模型不符，重演停止后無法再對后面的跡進行分析.為了使重演不終止，利用token的變化找到重演停止的原因，繼而發現模型與日志不相符的區域，下面提出強制重演的定義.

定義10. 強制重演. 事件日志在工作流網上重演時，若跡與事件日志不完全擬合，則跳過模型上與事件日志不匹配或不存在的變遷繼續重演.這種重演稱為事件日志的強制重演，記為Force_Replay(WFN,L)，其中WFN為工作流網，L為事件日志.

定義11. 日志活動與模型變遷的映射. 對于?σ∈L，若活動a∈&(σ)，并且在模型中存在變遷t與活動a對應，則稱Map(a,t)是一個日志活動與模型變遷的映射.

由于強制重演的引入，必須改變工作流網的引發規則，才能實施強制重演.

定義12. 強制重演中WFN引發規則. 在強制重演Force_Replay(WFN,L)中，規定開始環境給開始庫所一個token，其余庫所token數為0，強制重演結束后，環境再消耗結束庫所里的一個token.工作流網WFN=(P,T;F,M,i,o)變遷引發規則：

1) 跡σ對應變遷發生序列σt=t1,t2,…,tn，變遷t1在初始標識下引發，其余變遷t∈{t2,t3,…,tn}均可在前一變遷引發后得到的標識M下使能，即M[t>.

2) 若M[t>，從標識M引發變遷t得到一個新的標識M′(記為M[t>M′)，對?p∈P，

強制重演在模型中按照跡對應的變遷發生序列強制依次引發變遷，使得工作流網中變遷的使能引發規則改變.強制重演記錄變遷引發后，相應庫所p可能缺失token(M(p)<0)或者剩余token(M(p)>0)，token的變化反映了強制重演中變遷的引發過程.強制重演結束后，若M(p)<0，表示強制重演過程中庫所p缺失token，且一定有變遷在不滿足通常使能條件下執行；若M(p)>0，表示強制重演過程中庫所p有剩余的token，且一定有變遷在通常使能條件下沒有被執行.因此，通過結束標識中token數量，能夠清楚地判定找到現有模型與實際流程存在偏差的區域.下面給出強制重演算法.

算法1. 強制重演算法.

輸入：工作流網WFN=(P,T;F,M,i,o)、事件日志L∈B(σ*)；

輸出：標識M.

Step1.TL←?；*TL為日志活動對應模型變遷集，初始化TL*

Step2.M(i)=1,M(P-{i})=0；*初始狀態環境給開始庫所一個token，其余庫所token數量為0*

Step3. FOR EACHσ∈LDO*對日志中的每條跡進行以下操作*

Step3.1. FOR (aj∈σ;j=1;j++) DO*對跡中的每個活動依次進行以下操作*

Step3.1.1.Map(aj,tj)；*將活動映射為模型中的變遷*

Step3.1.2.TL←TL∪{tj}；*更新集合TL*

Step3.2. FOR (tj∈TL,j=1;j++) DO*對集合TL中的元素依次進行以下操作*

Step3.2.1. FOR EACHp∈PDO

Step3.2.1.1. IFp∈?t∈t?THENM(p)←M(p)-1；

Step3.2.1.2. IFp∈t?-?tTHENM(p)←M(p)+1；

Step3.2.1.3. ELSEM(p)←M(p)；

Step3.3.M(o)←M(o)-1；*最終環境消耗結束庫所中的一個token*

Step4. RETURNM.*返回結束標識*

2.2模型偏差域識別方法

實際流程發生變化，要么變換活動的先后順序，要么原有的活動代價太高不去執行，要么添加一個新的活動增加流程效率.因此，本文針對日志原有的活動順序改變或者有部分活動未被執行的情況展開模型偏差域識別方法進行介紹.

將token理解為系統消耗資源(系統資源分為消耗資源和非消耗資源，如工具等)，跡的重演可以理解為一種消耗資源使用行為.在一個正確有效的工作流網系統，消耗資源使用行為發生以后，系統中的消耗資源應該完全被消耗掉，不應該有剩余(剩余代表消耗資源浪費)，也不應該有缺失(消耗資源缺失代表前期工作準備不足).所以，跡在一個正確的工作流網上重演后，各個庫所中token數量應為0.不存在未使能卻引發的變遷，也不存在使能卻未引發的變遷.而當重演后，某些庫所中重演數量不為0時，那么該工作流網系統必定存在與實際流程不相符的區域.

定義13. 模型偏差域. 設WFN=(P,T;F,M,i,o)是一個工作流網，WFN′=(P′,T′;F′,M′,i,o)是挖掘事件日志L得到的工作流網，若F中存在與F′中元素不匹配的元素(p,t)或(t,p)，記為不匹配流關系，模型偏差域是由不匹配流關系組成的最小子網，用2端庫所表示，記為(pn,pm).

根據定義13，模型偏差域是指原有模型與實際流程相比存在偏差的區域.利用提出的強制重演，得到結束標識M，根據M所記錄的token數量判定模型偏差域.剩余token的庫所與缺失token的庫所之間存在與實際流程不相符的行為.為了方便模型修正，在判定模型偏差域時，應當遵循偏差域越集中約好，模型偏差域越小越好.

符號#(A)表示集合A中元素的個數.Mend為結束標識.

定理1. 設WFN=(P,T;F,M,i,o)是一個工作流網，L是事件日志，對于σ∈L，?a∈σ，若?Map(a,t)，則∑#(?t)=∑#(t?)當且僅當強制重演結束后，對?p∈P，∑Mend(p)=0.

證明. 充分性.根據強制重演算法，開始環境會產生1個token到開始庫所，最終環境還要從結束庫所中消耗1個token，兩者相互抵消.∑#(?t)是所有變遷前集元素的數量，變遷引發需要消耗前集的token，∑#(?t)也就代表所有變遷消耗token的數量.∑#(t?)是所有變遷后集元素的數量，同樣變遷引發會向后集中產生token，∑#(?t)也就代表所有變遷產生token的數量.因為，∑#(?t)=∑#(t?)，變遷引發消耗的token和產生的token又相互抵消，即∑Mend(p)=0.

必要性.由于∑M(p)=0，可得沒有變遷引發token為0，或者引發變遷消耗token的數量等于產生token的數量.所以，∑#(?t)=∑#(t?).

證畢.

在模型偏差域識別過程中，定理1驗證模型偏差域2端庫所的個數.例如，結束標識和為0，則所有的模型偏差域2端庫所個數相等，如果不為0，則存在2端庫所個數不相等的偏差域.

定理2. 跡是完全擬合的當且僅當強制重演結束后，對?p∈P，Mend(p)=0.

證明. 充分性.因為跡是擬合的，所以所有變遷都是滿足使能的條件下觸發，因此不存在缺失token的庫所，也不存在使能卻不觸發的變遷，因此也不存在含有token的庫所，所以強制重演結束后，對?p∈P，Mend(p)=0.

必要性.強制重演結束后，對?p∈P，Mend(p)=0，所以既沒有缺失token也沒有剩余token，因此跡是完全擬合的.

證畢.

定理2用來判定重演跡的擬合性，從而判定工作流網模型是否存在偏差，同時驗證偏差域的準確性.例如，結束標識中若存在庫所中的token不為0，則表示該工作流網模型存在偏差.

下面給出基于token的模型偏差域的識別算法.

算法2. 基于token的模型偏差域識別算法.

輸入：工作流網WFN=(P,T;F,M,i,o)、事件日志L∈B(σ*)；

輸出：模型偏差域(pn,pm).

Step1. 調用算法1強制重演算法；

Step2. IF(M(p)<0) RETURNt；*強制重演中，M(p)←M(p)-1后就開始判斷，判斷前不進行強制重演的后續行為*

Step3.pm←?t；

Step4.pn←順著流關系向前尋找含有token的庫所(規定開始庫所的前一個庫所是結束庫所)；

Step5. IF(pn不存在) THEN*如果沿著流關系沒有找到含有token的庫所，就返回上一次出現負數token的標識M，重新執行t*

Step5.1.M←上一次出現負數token的標識M；

Step5.2. RETURN上一次出現負數token的模型偏差域(A,B)；

Step5.3.pn←A；

Step5.4.pm←B∩pm；

Step5.5. RETURN(pn,pm)；

Step5.6.M(pm)←M(pm)+1；

Step5.7.M(pn)←M(pn)-1；*更新M的值，繼續強制重演的后續行為*

Step6. ELSE RETURN(pn,pm)；

Step7.M(pm)←M(pm)+1；

Step8.M(pn)←M(pn)-1.*更新M的值，繼續強制重演的后續行為*

算法2調用算法1，出現含有負數token的庫所時，以該庫所為起點沿著流關系向前尋找含有token的庫所，是為了在后續的修復工作中盡量使用簡單結構修正模型，向前尋找含有token的庫所能保證優先發現順序結構等簡單結構修正模型.如果尋找到開始庫所還是沒發現含有token的庫所，則按照規定開始庫所的前一個庫所是結束庫所，繼續尋找含有token的庫所.

例1. 工作流網模型WFN1如圖1所示，日志L={a,c,c,e,d}.在WFN1上，對σ=a,c,c,e,d進行模型偏差域識別.表1給出了強制重演時庫所token變化情況.

Fig. 1　Workflow net model WFN1.圖1　工作流網模型WFN1

TraceM(p1)M(p2)M(p3)M(p4)M(p5)M(p6)ModelDeviationDomainstart100000a011000c001100c0-11200(p4,p2)001100e0021-10(p3,p5)001100d0010-11(p3,p5)000001end000000

由表1，初始狀態環境為開始庫所p1產生1個token，其余庫所里的token數量為0，M[1,0,0,0,0,0].重演σ=a,c,c,e,d，首先觸發變遷a，p1∈?a-a?，M(p1)=M(p1)-1；p2∈a?-?a，p3∈a?-?a，M(p2)=M(p2)+1，M(p3)=M(p3)+1；其余庫所token不變，更新M[0,1,1,0,0,0].然后觸發c，p2∈?c-c?，M(p2)=M(p2)-1；p4∈c?-?c，M(p4)=M(p4)+1；其余庫所token不變，更新M[0,0,1,1,0,0].觸發c，p2∈?c-c?，M(p2)=M(p2)-1<0，因為M(p4)=1>0，所以偏差域(p4,p2)，更新M(p2)=M(p2)+1=0，M(p4)=M(p4)-1=0，由于只執行了觸發c時前集庫所里的token數量減1，繼續執行后集庫所里token數量加1，p4∈c?-?c，M(p4)=M(p4)+1=1，M[0,0,1,1,0,0].觸發e，p5∈?e-e?，M(p5)=M(p5)-1<0，因為M(p3)=1>0，所以偏差域(p3,p5)，更新M(p5)=M(p5)+1=0，M(p3)=M(p3)-1=0，由于只執行了觸發e時前集庫所里的token數量減1，繼續執行后集庫所里的token數量加1，p3∈e?-?e，M(p3)=M(p3)+1=1，M[0,0,1,1,0,0].觸發d，p4∈?d-d?，M(p4)=M(p4)-1，p5∈?d-d?，M(p5)=M(p5)-1<0，因為M(p3)=1>0，所以偏差域(p3,p5)，更新M(p5)=M(p5)+1=0，M(p3)=M(p3)-1=0，由于只執行了觸發d時前集庫所里的token數量減1，繼續執行后集庫所的token數量加1，p6∈d?-?d，M(p6)=M(p6)+1=1，M[0,0,0,0,0,1].根據算法最終結束庫所標識M(o)-1，得到結束標識M[0,0,0,0,0,0].偏差域識別后，根據定理2跡與模型是擬合的，因此識別的偏差域是正確的.

模型偏差域的發現是為了模型修正.例1的模型偏差域為(p4,p2)和(p3,p5).庫所p2缺失一個token，庫所p4剩余1個token，也就是說變遷c在沒有使能的情況下被強制執行了.所以，模型中(p4,p2)區域存在偏差，區域(p4,p2)為一個偏差域.區域(p3,p5)被發現2次，一次是由于e未使能卻強制執行，另一次是由于b使能但未執行，所以模型中(p3,p5)區域存在偏差，區域(p3,p5)為一個偏差域.最終得到偏差域為(p4,p2)和(p3,p5)，如圖2所示:

Fig. 2　Deviation domains of WFN1.圖2　WFN1偏差區域

下面給出一個更復雜的模型偏差域識別示例.

例2. 工作流網模型WFN2如圖3所示，日志L={a,b,c,d,b,c,b,c,d}.根據算法2，庫所token變化如表2所示.

Fig. 3　Workflow net model WFN2.圖3　工作流網模型WFN2

TraceM(p1)M(p2)M(p3)M(p4)M(p5)M(p6)M(p7)ModelDeviationDomainstart1000000a0110000b0101000c0001100d00010-10(p4,p6)0000001b00-11001(p7,p3)0001000c0-101100b00-11001backtobc0-1-11101(p7,(p2,p5))0001100

Continued (Table 2)

表2中token的變化原理同表1，這里不再贅述,不同的地方是虛線框里的部分，由于第2次觸發c時，庫所p2中token為負數，而觸發變遷c之前，其后集庫所p5也沒有token，所以沿著流關系向前尋找含有token的庫所.p1，p7，p5中都沒有token，返回上一次出現負數token的操作，也就是觸發b后的標識[0,0,-1,1,0,0,1].此時，重新觸發c，庫所p2，p3中token數均為負數.把(p2,p3)看成一個整體，而p5和p4中沒有同時含有token，所以沿著流關系向前尋找含有token的庫所，p7中含有token，且偏差域為(p7,(p2,p3)).最后，得到模型的偏差域為(p4,p6)，(p7,(p2,p3))，(p4,p3)，(p5,p2)，(p4,p6).根據定理1，由于強制重演結束標識和不為0，所以存在2端庫所數量不相等的偏差域.根據定理2，識別的偏差域是正確的.模型WFN2偏差區域如圖4所示:

Fig. 4　Deviation domains of e.g.2.圖4　例2偏差區域

3　基于token的模型修正

修正與實際流程相差不大的模型有很重要的意義，小規模的修正比重新挖掘要簡單方便省時，而且有利于企業更好地管理業務流程.本文所涉及的模型修正有3種：單個分支上的活動循環(新日志中增加了部分舊活動的執行次數)、部分活動跳過(新日志中沒有執行某些活動)和復雜結構體循環(新日志中增加了循環執行的多個活動).對于其他情況，例如增加了大規模的新活動、原有活動執行順序大部分改變等，其修正的代價要比重新挖掘的代價大得多，一般沒有修正的意義了.強制重演時環境給予工作流網模型1個token，新日志在修正后的模型上重演，最后環境再消耗1個token，此時的工作流網模型理應不含token.本節基于工作流網中token的缺失與剩余，給出一種模型修正的方法，利用不可見變遷改變token的流向，達到修正模型的目的.

3.1靜態模型修正

第2節已經介紹了模型偏差域的識別方法，找到原始模型與實際流程的偏差區域，下一步就要對原始模型修正，使之更加接近實際流程.

模型偏差域識別算法中已經確定了偏差區域，靜態模型修正就是將偏差域2端庫所，用不可見變遷連接起來，流關系是從偏差域2端中含有token的庫所到缺少token的庫所.

下面給出靜態模型修正的算法，τ表示不可見變遷.

算法3. 靜態模型修正算法.

輸入：工作流網WFN=(P,T;F,M,i,o)、事件日志L∈B(σ*)；

輸出：修正后的工作流網WFN′=(P′,T′;F′,M,i,o).

Step1. 調用算法2得到模型的所有偏差域(pn,pm)；

Step2.T′←T∪τ；

Step3.P′←P；

Step4.F′←F∪(pn,τ)∪(τ,pm)；

Step5. RETURNWFN′=(P′,T′;F′,M,i,o).

例3. 對圖1中的工作流網模型WFN1，日志L={a,c,c,e,d}，跡σ=a,c,c,e,d的模型修正結果如圖5所示:

Fig. 5　Repaired model of WFN1.圖5　WFN1的修正模型

由圖5可知，當第3個活動c觸發時，庫所p2中缺少1個token，在p2和p4之間添加1個不可見變遷τ1，使token從p4流向p2，這樣就可以解決p2中缺少token的問題，使活動c使能.活動e觸發時，庫所p5缺少1個token，在p5和p3之間添加1個不可見變遷τ2，使token從p3流向p5，這樣就可以解決p5中缺少token的問題，使活動e使能.觸發活動d時，庫所p5缺少1個token.添加了從庫所p3到庫所p5的不可見變遷和流關系后，通過此不可見變遷庫所p5可以獲得token，使d使能.

例4. 對于圖3中的工作流網模型WFN2，日志L={a,b,c,d,b,c,b,c,d}，根據識別的模型偏差域，可以修正模型，且修正結果如圖6所示：

Fig. 6　Repaired model of WFN2.圖6　WFN2修正模型

WFN2修正是一個相對復雜的修正例子，涉及到了復雜結構體循環修正和循環結構內部修正.一共增加了4個不可見變遷，第1次觸發d時，庫所p6中缺少1個token，在p4和p6之間添加1個不可見變遷τ4，使token從p4流向p6，使變遷d使能.變遷b和c是并發的，第2次觸發b和c時，2個庫所同時都缺少1個token，在p7與p2和p3之間添加1個不可見變遷τ1，使token從p7流向p2和p3，使并發變遷b和c都使能.第3次觸發b時，庫所p3中缺少1個token，在p4和p3之間添加1個不可見變遷τ3，使token從p4流向p3，使變遷b使能.第3次觸發c時，庫所p2缺少1個token，在p5和p2之間添加1個token，使token從p5流向p2，使變遷c使能.最后觸發d，庫所p6缺少1個token.在p4和p6之間有1個不可見變遷，token可以從p4流向p6，使d使能.由此可得到如圖6所示的WFN2的模型修正圖.

3.2動態模型修正

靜態模型修正依賴于識別出來的模型偏差域，模型偏差域識別算法只有在偏差域識別出來時才考慮，后續的識別過程中如果直接或間接涉及到該偏差域時，算法都默認該偏差域是不存在的，這就會導致偏差重復識別并且忽略偏差對整體的影響.因此對于復雜結構修正(例如WFN2的修正)，靜態模型修正無法整體把握模型的偏差，會使修正結果復雜條理不清晰.針對復雜結構修復，提出一種動態模型修正方法，使修正結果更加簡單清晰.

動態模型修正在進行模型偏差域識別的過程中，一旦識別出偏差域立即修正模型，并更新原有模型，在新模型的基礎上繼續進行強制重演直到結束.下面給出動態模型修正算法，τ表示不可見變遷.

算法4. 動態模型修正算法.

輸入：工作流網WFN=(P,T;F,M,i,o)、事件日志L∈B(σ*)；

輸出：修正后的工作流網WFN′=(P′,T′;F′,M,i,o).

Step1.S←?；*S用來存放以pm為標記的偏差域(pn,pm)，若pm為多個庫所，則分別以每一個庫所為標記存放在S中*

Step2. 調用基于token的模型偏差域識別算法(算法2)；

Step3. IF (there is (pn,pm)) THEN

Step3.1. IF (pm未在S中出現) THEN

Step3.1.1.S←〈pm,(pn,pm)〉∪S；

Step3.1.2.T′←T∪τ；

Step3.1.3.F′←F∪(pn,τ)∪(τ,pm)；

Step3.1.4.P′←P；

Step3.1.5. RETURNWFN′=(P′,T′;F′,M,i,o)；

Step3.2. ELSE

Step3.2.1. 在S中以pm為索引得到；*此處為之前識別過的偏差域可能與pn相同也可能不同*

返回算法2對庫所內出現負數token的操作；

Step3.2.3. RETURNWFN′←WFN.

例5. 運用動態模型修正算法重新修正圖3中的工作流網模型WFN2，L={a,b,c,d,b,c,b,c,d}，修正結果如圖7所示：

Fig. 7　Dynamically repaired model of WFN2.圖7　WFN2動態修正模型

Fig. 8　The process model for diagnosing and performing surgery on patients with colonopathy.圖8　結腸病患者就診流程模型

與靜態模型修正不同的是：第3次觸發b時，返回模型偏差域(p4,p3)進行判斷，由于標記p3在S中出現，因此之前的工作已經將此偏差修正，不必對(p4,p3)區域修正.得到S中以p3為標記的元素p3,(p7,(p2,p3))，繼續判斷庫所p7中是否有token，結果在第3次觸發d之前庫所p7中是沒有token的，因此順著流關系尋找存在token的庫所，發現偏差域((p5,p6),p7)，只有p5中有token，p6中沒有，然后再順著流關系向前尋找含有token的庫所，發現偏差域(p4,p6)，而標記p6在S中出現，因此不用修正偏差域(p4,p6)，只需修正偏差域((p5,p6),p7).

對比圖6和圖7，動態模型修正的修正結果只添加了3個不可見變遷和8條流關系就完成和修正，而靜態模型修正的修正結果卻添加了4個不可見變遷和9條流關系.隨著模型和日志的復雜程度增加，這種修正結果的對比會更加明顯.可見，動態模型修正方法對于復雜結構的修正更為簡單準確，而且結構清晰.

4　仿真實驗

本文提出的模型修正技術已經在過程挖掘工具ProM6中實現.本節將對提出的技術進行仿真實驗與比較分析，進一步驗證本文方法的正確性和有效性.

4.1實驗模型與數據

實驗所使用的過程模型和事件日志來源于某三甲醫院.圖8展示了結腸病患者的診斷和手術過程.此過程開始于患者訪問就診部門(變遷v)，結束訪問后去做結腸鏡檢查(cs)，檢查完畢后直接去手術門診(vs)或者讓腸胃病主任查看檢查結果(vg)或者沒有結腸疾病(w)離開結腸門診(g).如果患者有結腸疾病，需去結腸護理門診(n)制定一系列診斷檢查計劃.主要有化驗檢測(l)，CT掃描(c)，核磁共振(m)和X射線掃描(x).做完這些檢查后，患者需要再次去就診部門(vp)制定治療計劃.然后，患者再次去結腸護理門診(n)準備手術過程.依次進行確認手術(o)，術前評估(p)，同時進行心電圖(e)和化驗檢測(l)，且到膳食部門制定相應的飲食計劃(vt).同外科醫生商議(vm)后，患者住院(a)并進行手術(s)以及化驗檢測(l).最后，患者病愈出院(d).其工作流網模型如圖8所示.

Table 3　Detailed Information of Logs表3　詳細日志信息

4.2基于子跡的模型修正實驗

本文以基于子跡的模型修正技術為代表[21]進行實驗對比與分析,該技術是普通修正技術的改進，其主要思想是，通過校準找到模型的偏差區域，對于模型動作通過添加不可見變遷跳過執行，將相鄰的日志動作作為子日志，通過子日志挖掘子模型，將子模型添加到原模型中.這種修正方法耗時長，涉及的算法過多，既要利用合適的校準找到偏差區域，又要利用模型挖掘算法挖掘子模型，因此與本文所提模型修正技術相比過于復雜.

Fig. 9　Repaired result of Fig.8 according to 2 by subprocess-based model repair.圖9　基于2對圖8的修正——基于子跡的模型修正

LogSubprocess-BasedRepairAdd|P|Add|T|Add|τ|Add|F|Similarity-DistanceFitnessRunTime∕sL'1131715750.48280.53540L'2161717770.46860.47344L'3101115550.55170.63130L'4142015710.48280.59938L'5182014850.44980.34147

4.3基于token的模型修正驗證實驗

4.3.1靜態模型修正

Fig. 10　Repaired result of Fig.8 according to 2 by static model repair.圖10　基于2對圖8的修正——靜態模型修正

LogAdd|P|Add|T|Add|τ|Add|F|Similarity-DistanceFitnessRunTime∕msL'10510380.67880.92199L'20014310.71340.919104L'30010250.76190.99735L'40312330.70.93852L'50613400.65490.907130

4.3.2動態模型修正

表6展示了動態修正結果，增加0個庫所、13個不可見變遷、30條流關系、增加9個循環結構和4個選擇結構.修正模型與原始模型的相似距離0.722 6，與日志的擬合度高達0.969.

Fig. 11　Repaired result of Fig.8 according to 2 by dynamic model repair.圖11　基于2對圖8的修正——動態模型修正

LogAdd|P|Add|T|Add|τ|Add|F|Similarity-DistanceFitnessRunTime∕msL'1049340.70440.985399L'20013300.72260.969426L'30010250.76190.997300L'40010280.74670.991358L'50311300.71790.963455

4.43種模型修正技術對比分析

本節對3種修正方法進行擬合度和時間復雜度方面的對比分析.

4.4.1擬合度

Fig. 12　Fitness of different model repair techniques.圖12　不同修正技術的擬合度

Fig. 13　Changing curves of fitness.圖13　擬合度變化曲線

4.4.2時間復雜度

Fig. 14　Run time of different model repair techniques.圖14　不同修正技術所需時間

Fig. 15　Changing curves of run time.圖15　時間變化曲線

5　相關工作

現有的一致性檢測技術主要目的是衡量擬合度，例如模型可以重演多少日志以及盡可能多地發現模型偏差[22].除了擬合度，還有其他度量標準[18](精確度、泛化度和簡潔度)衡量模型質量.將模型和日志作為輸入的迭代過程發現技術，主要有2種基本技術類型.1)從日志L中發現過程模型NL，然后合并N和NL成新模型N[23].2)提取日志L中事件間的關系RL和模型N中活動間的關系RN，將2種關系合并得到R′.通過R′就可以得到修改的過程模型N′.R′是RN被RL取代的關系[24].這2類技術都會產生一個復雜的模型.為了解決這個問題，一個新的模型修正技術基于子跡的模型修正技術[21]被提出.雖然該技術解決迭代過程發現技術的缺點，但是同樣使用過程發現技術，不同的是跡的規模變小了.因此，時間復雜度是不變的，且修正得到的結果同樣很復雜.另一種模型修正方法是強制修正模型與原始模型之間的相似度，將相似度形式化為編輯距離[25].基于編輯距離，多種模型修正技術被提出，例如原始模型的最優相似健全模型[26].但是這些方法都不考慮現實行為.還有一些技術利用執行時間調整模型.

已有修正技術可能會存在時間復雜度高、修正結果擬合度低或者修正結果相對復雜的情況.針對這些情況本文提出了基于token的模型偏差域識別方法和基于token的模型修正技術，從另一個角度分析網行為，更加細致準確地完成模型修正，并且修正結果簡單擬合度高.

6　結　　論

本文根據一致檢測技術中的重演提出強制重演，主要使用擬合度和時間復雜度衡量模型修正的質量.對于與模型不擬合的跡重演不能順利進行，而強制重演遇到不能觸發的活動時，用標識記錄token的變化情況，并繼續重演.根據強制重演記錄的標識，可以很容易地找到缺失token的庫所和剩余token的庫所.以token為線索，從微觀的角度分析網系統的偏差，又在強制重演的基礎上提出一種基于Petri網的模型偏差域識別方法以及模型修正技術.通過控制token流向，有效地實現了模型修正,該模型修正方法修正結果擬合度高.該技術使得系統資源合理利用，利用系統多余資源使缺少觸發條件的變遷得以觸發,該技術還可以從根本上發現模型偏差并對其做出修正.

通過與其他方法的對比實驗和分析，驗證了本文方法的有效性和正確性.下一步工作將考慮其他一致性度量標準和改進的一致性檢測方法[27]，例如泛化度和精確度.同時，對于日志的適用不僅局限于活動的執行順序，還要考慮諸如時間戳和活動屬性等信息.

[1]Medeiros A K A, Weijters A, van der Aalst W M P. Genetic process mining: An experimental evaluation [J]. Data Mining and Knowledge Discovery, 2007, 14(2): 245-304

[2]van der Aalst W M P, Weijters A, Maruster L. Workflow mining: Discovering process model form event logs [J]. IEEE Trans on Knowledge and Data Engineering, 2004, 16(9): 1128-1142

[3]Goedertier S, Martens D, Vanthienen J, et al. Robust process discovery with artificial negative events [J]. Journal of Machine Learning Research, 2009, 10: 1305-1340

[4]Medeiros A, Weijters A, van der Aalst W M P. Genetic process mining: An experimental evaluation [J]. Data Mining and Knowledge Discovery, 2007, 14(2): 245-304

[5]Wang Jianmin, Wen Lijie. Mining process knowledge from log data [J]. Communications of CCF, 2012, 8(6): 63-68 (in Chinese)

(王建民, 聞立杰. 從日志數據中挖掘過程知識[J].中國計算機學會通訊, 2012, 8(6): 63-68)

[6]van der Werf J, van Dongen B, Hurkens C, et al. Process discovery using integer linear programming [J]. Fundamenta Informaticae, 2010, 94: 387-412

[7]van der Aalst W M P, Adriansyah A, van Dongen B. Replaying history on process models for conformance checking and performance analysis [J]. WIREs Data Mining and Knowledge Discovery, 2012, 2(2): 182-192

[8]Rozinat A, van der Aalst W M P. Conformance checking of processes based on monitoring real behavior [J]. Information Systems, 2008, 33(1): 64-95

[9]Banerjee A. Structural distance and evolutionary relationship of networks[J]. Biosystems, 2012, 107(3): 186-196

[10]Cao Yongzhi, Wang Huaiqing, Sun Sherry Xiaoyun, et al. A behavioral distance for fuzzy-transition systems[J]. IEEE Trans on Fuzzy Systems, 2013, 21(4): 735-747

[11]Alpaydin E. Introduction to Machine Learing[M]. Cambridge, MA: MIT Press, 2010

[12]Murata T. Petri nets: Properties, analysis and applications [J]. Proceedings of the IEEE, 1989, 77(4): 541-580

[13]van der Aalst W M P. Process Mining: Discovery, Conformance and Enhancement of Business Processes[M]. Berlin: Springer, 2011

[14]Du Yuyue, Jiang Changjun, Zhou Mengchu. A Petri net-based model for verfication of obligations and accountability in cooperative systems [J]. IEEE Trans on Systems, Man, and Cybernetics—Part A: Systems and Humans, 2009, 39(2): 299-308

[15]Du Yuyue, Jiang Changjun, Zhou Mengchu. A Petri nets based correctness analysis of internet stock trading systems [J]. IEEE Trans on System, Man and Cybernetics-Part C: Applications and Reviews, 2008, 38(1): 93-99

[16]Lin Chuang, Yang Hongkun, Shan Zhiguang. Application of Petri nets to bioinformatics [J]. Chinese Journal of Computers, 2007, 30(11): 1889-1900 (in Chinese)

(林闖, 楊宏坤, 單志廣. Petri網在生物信息學中的應用[J]. 計算機學報, 2007, 30(11): 1889-1900)

[17]Sun H C, Du Yuyue. Soundness analysis of inter-organizational workflows [J]. Information Technology Journal, 2008, 7(8): 1194-1199

[18]Du Yuyue, Jiang Changjun. Modeling real-time cooperative systems with workflow nets [J]. Chinese Journal of Computers, 2004, 27(4): 471-481 (in Chinese)

(杜玉越, 蔣昌俊. 基于工作流網的實時協同系統模擬技術[J]. 計算機學報, 2004, 27(4): 471-481)

[19]Lin Chuang, Tian Liqin, Wei Yaya. Performance equivalent analysis of workflow systems [J]. Journal of Software, 2002, 13(8): 1472-1480 (in Chinese)

(林闖, 田立勤, 魏丫丫. 工作流系統模型的性能等價分析[J]. 軟件學報, 2002, 13(8): 1472-1480)

[20]van der Aalst W M P, van Hee K M, ter Hofstede A H M, et al. Soundness of workflow nets: Classification, decidability and analysis [J]. Formal Aspects of Computing, 2011, 23(3): 333-363

[21]Fahland D, van der Aalst W M P. Model repair: Aligning process models to reality [J]. Information Systems, 2015, 47: 220-243

[22]Rozinat A, van der Aalst W M P. Conformance checking of processes based on monitoring real behavior [J]. Information Systems, 2008, 33(1): 64-95

[23]Kindler E, Rubin V, Sch¨afer W. Incremental workflow mining based on document versioning information[G] //LNCS 3840: Proc of Int Software Process Workshop. Berlin: Springer, 2005: 287-301

[24]Li Jie, Wen Lijie, Wang Jianmin. Process model storage mechanism based on Petri net edit distance [J]. Computer Integrated Manufacturing Systems, 2013, 19(8): 1832-1841 (in Chinese)

(李婕, 聞立杰, 王建民. 基于Petri網編輯距離相似性的過程模型存儲機制[J]. 計算機集成制造系統, 2013, 19(8): 1832-1841)

[25]Lohmann N. Correcting deadlocking service choreographies using a simulation-based graph edit distance[G] //LNCS 5240: Proc of the 6th Int Conf on BPM. Berlin: Springer, 2008: 132-147

[26]Gambini M, Rosa M L, Migliorini S, et al. Automated error correction of business process models[G] //LNCS 6896: Proc of the 9th Int Conf on BPM. Berlin: Springer, 2011: 148-165

[27]Tian Yinhua, Du Yuyue. A grouping algorithm of optimal alignments [J]. Journal of Shandong University of Science and Technology : Natural Science, 2015, 34(1): 29-34 (in Chinese)

(田銀花, 杜玉越. 一種最優校準的分組算法[J]. 山東科技大學學報: 自然科學版, 2015, 34(1): 29-34)

Du Yuyue, born in 1960. Professor and PhD supervisor at Shandong University of Science and Technology. Senior member of China Computer Federation. His research interests include work flows, business process mining and Petri nets, etc.

Sun Yanan, born in 1991. Master candidate at Shandong University of Science and Technology. Her research interests include big data, process mining and Petri net, etc.

Liu Wei, born in 1977. Associate professor at Shandong University of Science and Technology. His research interests include Petri net and service computing (yanchunchun9896@163.com).

Petri Nets Based Recognition of Model Deviation Domains and Model Repair

Du Yuyue, Sun Ya’nan, and Liu Wei

(KeyLaboratoryforWisdomMineInformationTechnologyofShandongProvince,ShandongUniversityofScienceandTechnology,Qingdao,Shandong266590)

Process mining techniques can be used to discover process models from event logs. Event logs and process model can be contrasted by conformance checking techniques. And conformance checking techniques can be used to detect the deviations between observed behaviors and process model. However, existing techniques of process mining concern with discovering these deviations, but not support to repair the process model easily and make the process model more related to the real process. So in this paper we propose a token-based identification method of model deviation domains and a token-based technique of model repair (static model repair and dynamic model repair) through techniques of conformance checking and dynamic behaviors of workflow net. Model deviation domains can be identified effectively though the flow direction of token. We can repair process model according to model deviation domains. And we also can repair the real complex process accurately which has the structures of complicated circulation and choice. In this paper, the effectiveness and the correctness of techniques are illustrated through contrast experiment and analysis with other techniques.

conformance checking; model repair; deviation domains; workflow net; token

2016-03-01；

2016-05-30

國家自然科學基金項目(61170078,61472228)；泰山學者建設工程專項；山東省自然科學基金項目(ZR2014FM009)；山東省優秀中青年科學家科研獎勵基金項目(BS2015DX010)

孫亞男(ynsun1006@163.com)

TP301.6

This work was supported by the National Natural Science Foundation of China (61170078,61472228), the Taishan Scholar Construction Project of Shandong Province, the Natural Science Foundation of Shandong Province (ZR2014FM009), and the Promotive Research Fund for Young and Middle-aged Scientists of Shandong Province (BS2015DX010).