基于Petri網模型的泛化度計算方法

，

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

過程挖掘[1-5]的目標是通過挖掘算法從給定的事件日志中挖掘出擬合、泛化、精確、簡潔的過程模型。由于現有的挖掘算法存在眾多缺陷，挖掘出的過程模型可能會與真實日志之間存在偏差。一致性檢驗用于檢測模型與日志之間是否存在偏差，主要度量標準有擬合度、精確度、泛化度、簡潔度。泛化度用于度量模型泛化日志行為的程度，即未來日志行為符合模型的程度，是過程挖掘中防止模型過擬合的一種度量標準。計算泛化度的主要困難是需要度量未知的日志行為，因此現有的計算泛化度的算法相對于其他度量標準來說并不多。

過程樹算法[6]根據過程模型構建過程樹，將事件日志在過程樹上重演，根據樹中結點被訪問頻率計算泛化度。該算法的主要缺點是需要先根據過程模型構建過程樹，時間復雜度比較高。基于校準的算法[7-8]將每個事件作為一個獨立的事件，計算事件屬于每個狀態的概率，根據狀態的被訪問次數及狀態發生的活動數計算泛化度。該算法依賴于貝葉斯假設[9]，要求每個狀態可能發生的活動數量是未知的，并且服從多項式分布，而通常情況下每個狀態只有有限個可以發生的活動。該算法沒有給出狀態的精確定義，并且事件日志規模較大時對每一個事件進行計算會非常耗時。反校準算法[10]通過計算最大反校準距離與最大反校準的恢復距離之間的歐幾里得距離來計算泛化度,為了降低時間復雜度該算法對最大反校準的長度進行限制，導致測量結果不準確，并且相對于其他算法該算法的時間復雜度仍然很高。

本研究針對基于校準[11]的泛化度算法[7-8]依賴于概率分布和時間復雜度高的缺點，提出一種類似于精確度自動機[7]的泛化度自動機算法,將Petri網模型中的標識作為狀態，并且借鑒過程樹算法[6]中的泛化度計算方法而不依賴于貝葉斯假設。

1 基本概念

過程模型的表示方法有多種，如Petri網[12-13]、變遷系統、工作流網、BPMN、YAWL等。Petri網圖形表示直觀簡單并且可以與其他表示方法互相轉換，因此本研究采用Petri網表示方法。下面介紹本研究所用到的基本概念：

定義1(Petri網)[14]設A為活動的集合，關于A的Petri網是一個元組N=(P,T,F,α,M,m0,mf)，其中P是庫所集合,T是變遷集合,且P∩T=?，F=(P×T)∪(T×P)是有向弧集合,M是標識集合,m0是初始標識，mf為結束標識，α:T→A是一個將變遷映射到活動的函數。

標識M表示庫所含有token的情況，例如M(p)=k表示庫所p含有token的數量為k。設變遷t∈T，則·t是t的前集，即含有有向弧指向t的庫所集合。t·是t的后集，即從t發出的有向弧所指向的庫所的集合。當·t中每一個庫所至少有一個token時，t可以引發。t引發后·t中每一個庫所減少一個token，t·中每一個庫所增加一個token。

如果存在一個變遷引發序列σ=t1t2…tn使標識從M轉變到M′，即M[σ>M′，則稱標識M′是從M可達的。如果m0[σ>mf,則σ為完整變遷引發序列。

定義2(事件日志)[1]事件日志L是跡的多重集，跡σ∈L是一個有限活動序列，σ=<σ1,σ2,…σ|σ|>，σi表示跡σ在第i位置的活動。

定義3(校準)[7]設A為活動的集合，σ∈A*是關于活動A的跡，關于活動A的Petri網N=(P,T,F,α,M,m0,mf)，跡σ與模型N的校準移動序列γ∈(A?×T?)*(?表示沒有與之對應的活動)。π1(γ)是序列在活動集合A上的投影，π2(γ)是序列在變遷集T上的投影。

對任意 (a,t)∈γ，校準可分為三種情況：當a∈A且t=?時，日志移動；當a=?且t∈T時，模型移動；當a∈A且t∈T時，同步移動。

代價函數是校準中偏差(日志移動、模型移動)的代價總和，最優校準是代價函數值最小的校準，最優校準可能不止一個。

2 過程模型泛化度

2.1 個人貸款流程

個人貸款流程是電子商務領域的典型應用，具有很強的流程性，是過程挖掘領域的典型實例。圖1中的Petri網模型描述的是簡化的個人貸款流程,該模型是從2012年BPI挑戰[15]提供的日志中選取的部分事件日志通過挖掘算法和手工創建得到的。貸款用戶首先需要登記貸款信息(register)，然后分成兩個并行執行的過程，分析人員為用戶提供與其申請相匹配的貸款產品(offers)，審核人員審查用戶申請(validate)。如果用戶是新用戶，可能需要另外一個分析人員對用戶的需求進行分析并提供更加合理的產品(extra offering)。同時風險分析人員對申請進行風險分析(risk analysis)。貸款經理根據風險分析及審核的結果做出是否同意貸款的決定(decide)。如果用戶對申請結果不滿意可以提出申訴(objection)，并重新申請(re-register),否則貸款過程結束并記錄(archive)。

圖1 個人貸款流程Petri網模型

IDTraceFrequency1abcefi3562abecdbcfi1743abcefghebcfi534aebcfi295abecdbcfghebcfi136aecfi17abecbcfi1

表1是從圖1 Petri網模型對應的事件日志中截取的7條跡組成的事件日志，其中第一列是日志中跡的編號，第二列是跡，第三列是跡出現的頻率。為了簡單起見，變遷t1,t2,t3,t4,t5,t6,t7,t8,t9對應的活動分別用字母a,b,c,d,e,f,g,h,i表示。

2.2 泛化度自動機

通常一個過程模型不應該只允許日志中的行為，否則這個模型是過擬合的[1](overfitting)。泛化度用于度量模型泛化日志行為的程度。計算泛化度的主要困難是需要考慮未知的行為，而日志中的行為是模型行為的真實反映，可以根據日志中已有的行為預測未知行為能否執行。

對擬合度很低的日志和模型進行泛化度計算是毫無意義的，為了不受擬合度的影響，用完全擬合的事件日志計算泛化度。將事件日志與Petri網模型校準得到校準序列，再將校準序列投影到變遷集可以得到完全擬合的事件日志。

過程樹算法[6]根據過程樹結點的被訪問次數計算泛化度，一個樹結點被訪問的次數越多，則越能確定這個結點是正確的。如果過程樹中有些結點很少被訪問到，則泛化度會比較低。借鑒這個思想，將完全擬合的事件日志在Petri網模型上重演，根據標識狀態變化情況構建泛化度自動機，并記錄狀態的被訪問次數及狀態發生的活動集合。狀態的被訪問次數與狀態發生的活動數之比越高則狀態越可靠，下次再訪問該狀態而不引發新活動的可能性越大，則泛化度越高。假設狀態S被訪問n次，發生的活動數是w,如果n很大w很小，則下次再訪問S時引發新活動的可能性很小。如果n和w差不多大，則下次再訪問S時很可能會引發新活動。下面給出泛化度自動機和泛化度的定義：

定義4(泛化度自動機) 泛化度自動機是一個元組GA=(S,SE,AT,NT,T,s0),其中S?M是標識狀態集合，M是Petri網的可達標識集合，SE?S×T×S是狀態間的帶標簽的有向邊集合，AT是狀態被訪問次數集合，NT是每個狀態發生的活動集合的集合，T是Petri網的變遷集合，s0=m0是初始狀態。

定義5(泛化度) 設N=(P,T,F,α,M,m0,mf)是關于活動集合A的Petri網，L是關于活動集合A的事件日志，α(L)是完全擬合的事件日志，GA=(S,SE,AT,NT,T,s0)是將α(L)在N上重演得到的泛化度自動機，則泛化度為：

(1)

對泛化度自動機中的每一個狀態Si∈S，ATi表示狀態Si的被訪問次數，NTi表示跡在Petri網模型重演時統計的在狀態Si所發生的活動集合。為了防止出現分母為0的情況，當NTi?NT時令|NTi|=1。這是合理的，因為Si∈S和NTi?NT兩個條件同時滿足的狀態只有泛化度自動機中的最后一個狀態(mf)，而每一個完全擬合的跡都會經過最后一個狀態，即當日志中的跡足夠多時公式中第二個求和項會接近于0。

算法1構建泛化度自動機

輸入：事件日志L，Petri網模型N

輸出：泛化度自動機

步驟：

1．S←{s0},SE←?,AT←?,NT←?;

2．α(L)←alignment(L,N) ;

3．for allσ∈α(L) do

4． for alle∈σdo

5． if(si[e>sj) then

6． if(sj?S) then

7．S←(S∪ {sj});

8．ATj←1;

9．AT←(AT∪{ATj});

10． elseATj←(ATj+1) ;

11． end if；

12． end if；

13． if(NTi?NT) then

14．NTi←{e};

15．NT←(NT∪{NTi});

16． elseNTi←(NTi∪{e});

17． end if；

18． if((si,e,sj)?SE) then

19．SE←(SE∪{(si,e,sj)});

20． end if；

21． end；

22．end；

23．GA←(S,SE,AT,NT,T,s0) ;

24．returnGA;

如果日志中有m條軌跡，平均每條軌跡有n個事件，則泛化度自動機算法時間復雜度為O(mn)，如果Petri網中共有s個狀態則基于校準算法的時間復雜度為O(smn)。過程樹算法需要根據過程模型構建過程樹，遍歷過程樹，時間復雜度也高于泛化度自動機算法。

表2 跡的校準序列

下面對圖1 Petri網模型N和表1事件日志計算泛化度。首先將事件日志與Petri模型校準，再將校準序列投影到變遷集得到完全擬合的事件日志α(L)。表2是跡的一個最優校準，其中第5列是模型移動，是擬合后的跡。將α(L)在N上重演根據標識狀態變化情況得到泛化度自動機。

圖2是根據圖1 Petri網和表1事件日志得到的泛化度自動機，圖中S0-S9是狀態，狀態右上角的兩個數字分別是狀態被訪問次數和狀態發生的活動數。例如狀態S1被訪問693次，發生的活動數是2 (t2和t5)。根據泛化度計算公式 (1)，泛化度為：Generation(N,L)=0.941 2,用過程樹算法[6]得到的泛化度為0.948 7，基于校準的算法[7]得到的泛化度為0.950 3。

圖2 泛化度自動機

3 仿真實驗

下面通過仿真實驗來評價本文所提出的泛化度自動機算法，實驗在開源軟件ProM6[16]上進行。試驗將泛化度自動機算法與其他經典算法作對比，以驗證其正確性與實用性。

表3 事件日志信息

表3是從圖1所示的個人貸款模型N所對應的事件日志中截取的6段事件日志的基本信息。每個事件日志含有500條跡(#Traces)，但是日志中的不同跡數(#Traces′)、事件數(#Events)、跡的長度(Length)不同，并且遞增。隨著事件日志更全面地覆蓋模型的標識狀態，狀態的可信度增加，泛化度也會增加。通過本實驗可以驗證算法是否具有正確性和實用性。

圖3是對不同事件日志測量泛化度的結果。4種算法的泛化度值都呈遞增趨勢，過程樹算法(gt)[6]、基于校準的算法(ga)[7]、泛化度自動機算法(gs)得到的泛化度值相近，而反校準算法(gc)[10]因為對最大反校準的長度進行了限制，得到的值偏低。

圖4是計算泛化度所用的時間。過程樹算法(gt)需要校準和構建過程樹所用時間多于基于校準的算法(ga)和泛化度自動機算法(gs)。雖然本研究所提出的算法也需要校準，但是沒有對日志中的每個事件單獨處理，因此所用時間少于基于校準的算法(ga)。反校準算法(gc)為了得到最大反校準需要遍歷整個模型，用時最多。

圖3 同一模型不同事件日志泛化度

圖4 計算時間

通過仿真實驗可以得出本研究所提出的泛化度算法可以得到與基于校準的算法和過程樹算法相似的結果，而用時少于這兩種算法。

4 結論

針對基于校準的泛化度算法的缺點，提出一種泛化度自動機算法。將事件日志與過程模型校準得到完全擬合的事件日志，將完全擬合的事件日志在Petri網模型上重演，根據標識狀態變化情況構建泛化度自動機。根據泛化度自動機中狀態被訪問次數及狀態發生的活動數計算泛化度。通過實例介紹了泛化度的計算方法及過程。該算法相對于其他經典算法最大的特點是表示直觀簡單，不依賴于概率分布并且時間復雜度低。仿真實驗驗證了算法的正確性及實用性。通過本文所提出的算法可以得到模型的泛化度，如何利用所得到的泛化度去改進模型，避免模型過擬合是本研究以后的工作目標。

[1]AALST W V D.Process mining:Discovery,conformance and enhancement of business processes[M].Berlin:Springer,Publishing Company,2011:191-213.

[2]AALST W V D,ADRIANSYAH A,MEDEIROS A K A D,et al.Process mining manifesto[C]// International Conference on Business Process Management.Springer,Berlin,Heidelberg,2011:169-194.

[3]李洪霞,杜玉越.業務過程管理研究現狀與關鍵技術[J].山東科技大學學報(自然科學版),2015,34(1):22-28.

LI Hongxia,DU Yuyue.A survey of research issues and key technology for business process management[J].Journal of Shandong University of Science and Technology(Natural Science),2015,34(1):22-28.

[4]魯法明,曾慶田,段華,等.一種并行化的啟發式流程挖掘算法[J].軟件學報,2015,26(3):533-549.

LU Faming,ZENG Qingtian,DUAN Hua,et al.Parallelized heuristic process mining algorithm[J].Journal of Software,2015,26(3):533-549.

[5]祁宏達,杜玉越,劉偉.一種基于可達標識的過程模型修復方法[J].山東科技大學學報(自然科學版),2017,36(1):118-124.

QI Hongda,DU Yuyue,LIU Wei.Process model repairing method based on reachable markings[J].Journal of Shandong University of Science and Technology(Natural Science),2017,36(1):118-124.

[6]BUIJS J C A M,DONGEN B F V,AALST W M P V D.On the role of fitness,precision,generalization and simplicity in process discovery[J].Springer Berlin Heidelberg,2012,7565(3) :305-322.

[7]ADRIANSYAH A.Aligning observed and modeled behavior[D].Eindhoven:Eindhoven University of Technology，2014:129-166.

[8]AALST W M P V D,ADRIANSYAH A,DONGEN B V.Replaying history on process models for conformance checking and performance analysis[J].Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery.2012,2(2):182-192.

[9]BOENDER C G E.A bayesian analysis of the number of cells of a multinomial distribution[J].The Statistician,1983,32(1/2):240-248.

[10]DONGEN B F V,CARMONA J,CHATAIN T.A unified approach for measuring precision and generalization based on anti-alignments[M].Berlin:Springer International Publishing，2016.

[11]王路,杜玉越.一種基于校準的模型問題域識別方法[J].山東科技大學學報(自然科學版),2015,34(1):42-46.

WANG Lu,DU Yuyue.An alignment-based identifying method of the problem areas within process models[J].Journal of Shandong University of Science and Technology(Natural Science),2015,34(1):42-46.

[12]DU Y Y,QI L,ZHOU M C.Analysis and application of logical Petri nets to E-commerce systems[J].IEEE Transactions on Systems Man & Cybernetics Systems,2014,44(4):468-481.

[13]DU Y Y,NING Y.Property analysis of logic Petri nets by marking reachability graphs[J].Frontiers of Computer Science,2014,8(4):684-692.

[14]吳哲輝.Petri網導論[M].北京：機械工業出版社，2006.

[15]DONGEN B F V.BPI challenge 2012.Dataset[DB].http://dx.doi.org/10.4121/uuid:3926db30-f712-4394-aebc-75976070e91f.

[16]MEDEIROS A K A D,WEIJTERS A J M M,Aalst W M PVD.Genetic process mining:An experimental evaluation[J].Data Mining and Knowledge Discovery.2007,14(2):245-304.