基于依賴關(guān)系的數(shù)據(jù)流Petri網(wǎng)一致性分析

錢 陳 婧

(1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院,安徽 淮南 232001;2.安徽省煤礦安全大數(shù)據(jù)分析與預(yù)警技術(shù)工程實驗室,安徽 淮南232001)

在業(yè)務(wù)流程管理中,對業(yè)務(wù)流程進行一致性分析在保證系統(tǒng)的可信度上有著重要的作用,它既可以用來識別偏離的執(zhí)行信息并提供相應(yīng)的診斷信息,也可以用來評估流程模型的質(zhì)量[1].一致性分析通過將現(xiàn)有的流程模型與來自該流程模型的事件日志作比較,檢驗記錄在日志中的現(xiàn)實的流程是否與流程模型相一致.

已有的關(guān)于一致性方面的研究在純控制流已經(jīng)進行了深入的研究[2],但忽略了在控制流之外的其他方面,例如操作流程的數(shù)據(jù)對象、活動資源、活動生命周期等,這可能導(dǎo)致誤導(dǎo)性的一致性診斷.文獻[3]介紹了一種在考慮數(shù)據(jù)、資源和時間等視角的同時協(xié)調(diào)事件日志和模型的方法,通過構(gòu)建一個ILP(Integer Linear Programming)問題,融合考慮其他視角獲得最佳對齊,以量化一致性和分析模型與現(xiàn)實之間的差異.這種方式的缺點是首先考慮控制流,無法平衡數(shù)據(jù)與控制流之間的成本,因此返回的對齊可能不是最優(yōu)的.對此,文獻[4]提出一種新的平衡考慮多視角的算法,同時考慮控制流與數(shù)據(jù)屬性,基于可定制的代價函數(shù)來平衡不同角度的偏差,有助于避免傳統(tǒng)的單視角或分階段方法產(chǎn)生的誤導(dǎo)結(jié)果.文獻[5]提出利用活動依賴進行數(shù)據(jù)感知過程一致性檢查,采用基于過程分解和跡重放的啟發(fā)式方法來確定參考跡,使得日志與模型的一致性程度變?yōu)閮蓚€跡之間的一致性程度,識別由活動依賴偏差引起的一致性下降.文獻[6]提出一種基于Petri網(wǎng)的事件日志與流程模型之間快速對齊的RapidAlign方法,根據(jù)移動類型計算代價值最終生成一個最優(yōu)對齊圖.文獻[7]展示了如何將在純控制流設(shè)置中研究的基于 SAT 的編碼提升到數(shù)據(jù)感知案例中,使用 SMT 作為底層形式和算法框架;并引入了一種基于屬性保留聚類的預(yù)處理技術(shù),以加快一致性檢查輸出的計算速度.

在業(yè)務(wù)流程分析中,決策模型與表示法(DMN)是幫助流程建模以及實現(xiàn)一致性檢查的一種重要方法.文獻[8]為決策模型以及流程和決策的集成提供了形式化的定義,同時提供了一個包含整個流程的決策模型,而不是只關(guān)注局部決策點.文獻[9]提出了DMN決策表的形式化語義和決策表上分析任務(wù)的形式化定義,并基于定義提出一個基于構(gòu)成決策表的規(guī)則的幾何解釋大決策表分析和重構(gòu)方法.文獻[10]將重點放在數(shù)據(jù)視角,探討了在BPMN過程中建模并用于決策的數(shù)據(jù)如何以及在多大程度上可以在相應(yīng)的DMN決策模型中表示,并確定一組可以捕獲BPMN流程中可能表示的數(shù)據(jù)的模式,用于派生得到一個與流程一致的決策模型.

融合控制流與數(shù)據(jù)流來分析業(yè)務(wù)流程的一致性已經(jīng)成為現(xiàn)代研究發(fā)展的新趨勢.本文將重點放在業(yè)務(wù)流程的數(shù)據(jù)決策上,從業(yè)務(wù)流程執(zhí)行的決策邏輯出發(fā),對生活中常見的業(yè)務(wù)流程模型分析根據(jù)實際情況尋找決策點,建立其帶有DMN決策表的BPMN模型;通過將其轉(zhuǎn)換為數(shù)據(jù)流Petri網(wǎng)給出它正式的執(zhí)行語義;最后提出一個基于依賴關(guān)系的一致性分析算法,計算模型與事件日志的一致性,驗證本文提出的方法的合理性.

1 基本概念

本文以數(shù)據(jù)流Petri網(wǎng)為研究基礎(chǔ),以Petri網(wǎng)模型與事件日志間的一致性檢查為研究重點,下面給出貫穿全文的一些基本背景概念.

定義1[11](流程模型Petri網(wǎng))三元組N=(P,T,F)稱為一個流程模型的Petri網(wǎng),須滿足以下條件:

a) 有限庫所集P≠φ,有限變遷集T≠φ;

b)P∩T=φ,P∪T≠φ;

c)F?(P×T)∪(T×P);

d) dom(F)∪cod(F);

其中:

dom(F)={x∈P∪T|?y∈P∪T:(x,y∈F)}

cod(F)={x∈P∪T|?y∈P∪T:(y,x∈F)}

如上,P和T為網(wǎng)N的兩個基本元素,在圖中分別用圓圈和矩形來表示.

定義2[12](數(shù)據(jù)流Petri網(wǎng))一個數(shù)據(jù)流Petri網(wǎng)DPN=(P,T,F,V,αI,guard)是一個六元組,包含在流程模型Petri網(wǎng)N=(P,T,F)以外的描述,滿足以下條件:

a)V是活動的有限集;

b)αI為變量賦初始值;

c)guard為網(wǎng)中每個變遷分配一個守衛(wèi),有g(shù)uard(v)α=true,表示對于變量v的賦值α滿足守衛(wèi).

不同于控制流Petri網(wǎng),數(shù)據(jù)流Petri網(wǎng)包含對業(yè)務(wù)流程數(shù)據(jù)信息的描述,即元組中的guard實現(xiàn)了對業(yè)務(wù)流程中數(shù)據(jù)信息的有效約束.

2 動機案例

本節(jié)利用一個常見的銀行貸款的實例來研究提出的基于活動依賴關(guān)系的一致性檢查方法.在常見的銀行貸款業(yè)務(wù)流程中,客戶首先發(fā)出貸款申請,銀行對提交申請的客戶進行信譽評估,綜合其職業(yè)、工資等各項信息以確定是否符合銀行規(guī)定的開放貸款的條件,若符合即可開放貸款,不符合則駁回申請.

圖1是一個用BPMN語言描述的業(yè)務(wù)流程.銀行評估可對客戶開放貸款后,為客戶辦理貸款,并為客戶提供相應(yīng)的辦理通道,不符合開放貸款條件的客戶則直接反饋拒絕申請.僅考慮這一業(yè)務(wù)流程建立的控制流模型,計算模型與事件日志是否一致,可以得到較高的一致性值,但本文在考慮現(xiàn)實的數(shù)據(jù)信息后并非如此.銀行對客戶信譽評估通常分為幾個等級,不同信譽等級的客戶享有不同的貸款額度上限,據(jù)此,對原有模型進行調(diào)整,解決上述問題,如圖2所示.然而,模型的復(fù)雜度顯而易見,因此,本文引入決策表的概念,將信譽評估任務(wù)鏈接到DMN決策表,該決策表將在應(yīng)當(dāng)做出決策時執(zhí)行,其結(jié)果幫助決定BPMN流程的下一步執(zhí)行.

圖1 銀行貸款業(yè)務(wù)流程

圖2 信譽評估BPMN流程

3 基于依賴關(guān)系的數(shù)據(jù)流Petri網(wǎng)一致性分析

3.1 引入DMN決策表建模準(zhǔn)則

圖2流程模型解決了根據(jù)客戶信譽等級以及客戶申請貸款額度決定執(zhí)行結(jié)果的問題,但也同時增加了模型的復(fù)雜度.為簡單、高效解決銀行貸款業(yè)務(wù)流程中業(yè)務(wù)執(zhí)行的決策邏輯問題,本文引入了DMN標(biāo)準(zhǔn)中的決策邏輯的概念來優(yōu)化原有的流程模型.通過在模型中對需要決策的活動添加DMN決策表構(gòu)建模型的決策邏輯,并將決策模型轉(zhuǎn)換為相應(yīng)的數(shù)據(jù)流Petri網(wǎng)模型DPN,它有效擴展了帶有數(shù)據(jù)屬性的Petri網(wǎng).

定義4[14](DMN決策表)一個DMN標(biāo)準(zhǔn)的決策表DT=(name,I,O,Def,H)是一個五元組,其中:

1)name是決策表名稱;

2)I為輸入,關(guān)聯(lián)一個類型和一組輸入值;

3)O為輸出,關(guān)聯(lián)一個類型和一組輸出值;

4)Def是一個默認賦值函數(shù),將一些輸出屬性映射到相應(yīng)的默認值;

5)H是決策表的命中策略,指定決策表的結(jié)果.

圖3為將“信譽評估”鏈接到DMN決策表中,由決策表做出相應(yīng)決策,決定流程的下一步執(zhí)行.客戶信譽等級和進行貸款申請的額度作為輸入,匹配列出的7條規(guī)則,命中得到相應(yīng)的輸出結(jié)果為同意貸款申請還是拒絕申請.后續(xù)將引入DMN決策表得到的BPMN模型編碼為數(shù)據(jù)流Petri網(wǎng),實現(xiàn)一致性分析的目標(biāo).

圖3 貸款信譽評估決策表示例

3.2 基于活動依賴關(guān)系的一致性檢查規(guī)則

本節(jié)提出了基于依賴關(guān)系的一致性分析算法,在算法1中,通過給定的事件日志和數(shù)據(jù)流Petri網(wǎng)模型計算出在納入數(shù)據(jù)約束后,利用活動間的依賴關(guān)系得到的日志與模型的一致性度.算法為業(yè)務(wù)活動及其攜帶數(shù)據(jù)分配代價值,據(jù)此計算對齊時所需代價值.

首先,本文提出的一致性檢查方法要求對流程模型和事件日志進行對齊,以顯示事件如何在模型中重放,下面給出與對齊相關(guān)的概念.

定義5 (依賴關(guān)系)設(shè)活動的有限集A={a1,a2,…,an},若從活動ai至活動aj間存在一條有向路徑,則稱活動aj依賴于活動ai,記為,相反,若兩個活動間沒有任何依賴關(guān)系,則稱兩個活動是相互獨立的.例如在上述提到的銀行貸款業(yè)務(wù)流程中,活動B,C,D,E皆依賴于活動A,活動A中攜帶的數(shù)據(jù)信息決定了下一步應(yīng)當(dāng)執(zhí)行哪個活動.

定義6 (對齊)設(shè)一個Petri網(wǎng)N=(P,T,F,V,α,guard),σ∈L是一條跡,將日志中事件的依賴關(guān)系與模型中活動間依賴關(guān)系相對應(yīng),形成事件日志與流程模型之間的對齊γ=(R(σ),R(N)).其中,跡中所有事件的依賴關(guān)系集為R(σ)={,,…},R(N)={,,…}則表示模型中活動的所有依賴關(guān)系集.

假定模型中將發(fā)生的變遷為t1,其映射的活動為A,在對齊的過程中,從模型中觀察到的直接依賴關(guān)系,即觀察到依賴于活動A的活動B,在跡中并沒有觀察到這樣的依賴關(guān)系,此時就可以得到一個模型移動;反之從跡中觀察到的依賴關(guān)系在模型中并不能實現(xiàn),即認為觀察到一個日志移動;如果能夠在模型和日志中觀察到同樣的依賴關(guān)系,但跡中事件攜帶的數(shù)據(jù)信息不能匹配模型的守衛(wèi),其移動也認為不合理.

對于基于依賴關(guān)系的對齊的定義如下:

1)若(a,b)∈(E×E)且(t1,t2)∈(T×T)或a=?(b=?)且t1=τ(t2=τ),記為同步移動MS;

2)若(a,b)∈(E×E)且t1=?(t2=?),記為日志移動ML;

3)若(t1,t2)∈(T×T)且a=?(b=?),記為模型移動MN;

4)否則記為非法移動.其中?表示無移動.

定義7 (最優(yōu)對齊)[15]給定跡和Petri網(wǎng)模型,可能存在著多種對齊,使用代價函數(shù)為事件與活動的上述每種移動分配代價值,根據(jù)給定的代價函數(shù),找到代價值κ(γ)最低的對齊即為所需的最優(yōu)對齊.對于一個最優(yōu)對齊γ,有κ(γ)≤κ(γ′),即最優(yōu)對齊的代價值小于等于任意一個對齊γ′.

考慮活動的重要性和數(shù)據(jù)對活動的影響,定義的代價函數(shù)如下:

(1)

其中:val(e)表示日志中事件e的屬性所對應(yīng)的數(shù)據(jù)值,act(e)表示日志中事件所代表的活動名稱,|num(attr)|則表示事件或活動所包含的具有數(shù)據(jù)值的屬性個數(shù),|num(attr)|dif則表示具有的不同的數(shù)據(jù)值的個數(shù).

定義8 (一致性度)設(shè)模型N和跡σ=,對齊γO為模型與日志的最優(yōu)對齊,γR為參考對齊,即考慮最壞情況所得到的對齊,得到模型與日志對齊的一致性度為:

(2)

通過上述定義和公式,給出基于依賴關(guān)系的一致性度的計算如算法1所述.

Algorithm 1 Fitness level based on dependencies

Input:DPN=(P,T,F,V,α1,guard),

σ=

Output:F(σ,N)

1R(σ)←{},R(N)←{} // initialize the aggregate of dependencies

2 For eachei∈σdo

3R(σ)←GetEventDep(ei)//get the dependencies of eventei

4 End for

5 For eachti∈DPNdo

6R(N)←GetEventDep(ti) //get the dependencies of activitytiin the model

7 End for

8 For eachri∈R(σ) do

9 For eachrj(N)∈R(N) do

10κ(γOi)←argminγ∈(ri(σ),ri(N))κ(γ) //get the minimum cost value of each alignment

11κ(γRi)←argmaxγ∈(ri(σ),ri(N))κ(γ) // get the maximum cost value of each alignment

12 End for

15 End for

17 ReturnF(σ,N)

算法1描述了使用給定代價函數(shù)計算模型與日志的一致性的方法,算法主要分為三部分,首先,行2～7遍歷給定的日志跡,獲得其依賴關(guān)系存儲在集合中R(σ),同時,依據(jù)控制流結(jié)構(gòu)遍歷模型,獲得其中存在的依賴關(guān)系,存儲在集合R(N)中;接著,行8～12將獲得的依賴關(guān)系對齊,計算每個對齊所需代價值,并分別保存最小和最大代價值;行13、14計算最優(yōu)對齊和參考對齊總代價值;最后,行16根據(jù)定義8的公式計算得到一致性度.

4 實例分析

本節(jié)以上述銀行貸款流程為例,驗證本文提出方法的有效性.針對流程模型中存在的兩個決策點構(gòu)建決策表,得到的模型如圖4所示.模型中添加了兩個決策表,分別為“信譽評估”決策表和“辦理通道”決策表,前者用來根據(jù)客戶的信譽等級和貸款金額決定申請結(jié)果,后者則為可實行貸款申請的用戶分配業(yè)務(wù)辦理通道.

圖4 帶決策表的銀行貸款流程

為驗證本文提出的一致性檢查方法,將給定的事件日志與構(gòu)建的數(shù)據(jù)流Petri網(wǎng)模型對齊,并將計算得到的一致性度和事件日志與初始模型對齊得到的一致性度進行比較,說明本文方法所構(gòu)建的模型能夠更有效挖掘事件日志中存在的異常問題,幫助提高業(yè)務(wù)流程的合理性.圖5即為根據(jù)圖4流程模型得到的數(shù)據(jù)流Petri網(wǎng)模型.

圖5 銀行貸款數(shù)據(jù)流Petri網(wǎng)

給出銀行貸款業(yè)務(wù)中的不完整事件日志,以其中的一條跡σ1為例,σ1=<(A,{amount=296000}),(B,{grade=B,amount=296000}),F,G,(H,{rank=0,channel=common}),J>,分析其與流程模型的一致性.

對于得到的圖5數(shù)據(jù)流Petri網(wǎng)模型M1,首先分別提取出跡與模型的依賴關(guān)系集R(σ1)和R(M1),其依賴關(guān)系如下:

1)跡中事件依賴關(guān)系集

R(σ1)={<(A,{amount=296000}),

(B,{grade=B,amount=296000})>,

<(B,{grade=B,amount=296000}),F>,

,

,

<(H,{rank=0,channel=common}),J>}

2)模型中活動依賴關(guān)系集

R(M1)={<(A,{amount>0}),

(B,{(grade=A)∧(amount∈(0,30])})>,

<(A,{amount>0}),

(C,{(grade=B)∧(amount∈(0,20])})>,

<(A,{amount>0}),

(D,{(grade=C)∧(amount∈(0,10])})>,

<(A,{amount>0}),

(E,{amount=undef})>,

<(B,{(grade=A)∧(amount∈(0,30])}),F>,

<(C,{(grade=B)∧(amount∈(0,20])}),F>,

<(D,{(grade=C)∧(amount∈(0,10])}),F>,

(E,{amount=undef}),F>,

,

,

,

,

,

<(H,{rank=0,channel=common}),G>,

<(I,{rank=1,channel=VIP}),G>,

,

,

<(I,{rank=1,channel=VIP}),J>}

根據(jù)上述得到的依賴關(guān)系進行對齊,計算最小的代價值獲得最優(yōu)對齊,計算模型與給定跡的一致性度如表1所示.

表1 跡σ1與模型M1對齊示例

對于給出的代價函數(shù),表1所示對齊即為找到的最優(yōu)對齊,因為日志與模型間不存在代價值更小的對齊,因此,其最優(yōu)對齊代價值為κ(γO)=2,計算得到的數(shù)據(jù)流模型與事件日志的一致性度:

計算在未加入數(shù)據(jù)信息的情況下,初始模型M0與它的一致性度,可以看到,在不考慮數(shù)據(jù)元素時,給定的日志跡可以在模型中完全重放,不存在不一致的行為,因此獲得的一致性度F(σ1,M0)=1.但在本文提出的方法中,一致性度僅為0.82,顯然,在實際貸款流程中,跡σ1存在著不合理性,客戶所申請的貸款金額高于其信譽等級所能獲得的最高貸款額度,這種不合理性在不考慮數(shù)據(jù)信息時無法被模型篩選出來.同時,與文獻[3]將控制流優(yōu)先考慮不同,本文提出的計算方法同時著眼于數(shù)據(jù)流與控制流,所提出的代價函數(shù)也相應(yīng)地考慮了數(shù)據(jù)信息對流程執(zhí)行的影響,實現(xiàn)了控制流和數(shù)據(jù)流之間的有效融合,因此,本文提出的方法更具合理性.

至此可以得出結(jié)論,在不考慮數(shù)據(jù)因素的情況下,業(yè)務(wù)流程模型與事件日志具有良好的一致性,能夠在模型中有效重放事件日志,但在考慮了貸款額度與客戶信譽等級這種與實際情況更相近的數(shù)據(jù)環(huán)境下,數(shù)據(jù)流模型與事件日志的一致性大大下降,這有利于檢測流程執(zhí)行中存在的與實際執(zhí)行間的偏差問題,幫助后期對事件日志進行檢測、修復(fù)或?qū)δＰ瓦M一步優(yōu)化以提高一致性.

5 結(jié) 語

本文提出一種基于活動依賴關(guān)系的數(shù)據(jù)流模型與事件日志的一致性檢查方法,該方法將流程中涉及的數(shù)據(jù)信息考慮在內(nèi),采用給定的代價函數(shù)計算模型與跡的一致性度,從而評估業(yè)務(wù)流程的合理性.同時,該方法通過查找模型中存在的決策點并對其添加決策表來構(gòu)建合理且盡可能貼合實際系統(tǒng)的流程模型,為一致性分析鋪平道路.此方法不僅能在控制流角度分析流程的一致性,還進一步從數(shù)據(jù)視角加強對業(yè)務(wù)流程合理性的判斷.關(guān)于數(shù)據(jù)流模型一致性檢查的研究有很多,未來的工作中,將尋求更合理的代價函數(shù)及對齊方法進行一致性檢查,同時,根據(jù)修復(fù)后的事件日志及相關(guān)領(lǐng)域知識挖掘更為合理且符合實際的高一致性模型也是今后研究的重點.