一種基于邏輯Petri網(wǎng)的過(guò)程挖掘方法

杜玉越,朱鴻儒,王 路,劉 偉

(山東科技大學(xué)山東省智慧礦山信息技術(shù)重點(diǎn)省級(jí)實(shí)驗(yàn)室，山東青島 266590)

?

一種基于邏輯Petri網(wǎng)的過(guò)程挖掘方法

杜玉越,朱鴻儒,王 路,劉 偉

(山東科技大學(xué)山東省智慧礦山信息技術(shù)重點(diǎn)省級(jí)實(shí)驗(yàn)室，山東青島 266590)

邏輯Petri網(wǎng)是抑制弧Petri網(wǎng)和高級(jí)Petri網(wǎng)的抽象和擴(kuò)展,可在過(guò)程挖掘中簡(jiǎn)潔準(zhǔn)確的表示活動(dòng)之間復(fù)雜的業(yè)務(wù)邏輯關(guān)系.本文在傳統(tǒng)Petri網(wǎng)挖掘方法的基礎(chǔ)上,為了進(jìn)一步提高復(fù)雜系統(tǒng)挖掘模型的簡(jiǎn)潔度和擬合度,尤其是對(duì)并行活動(dòng)間存在復(fù)雜與或關(guān)系的系統(tǒng),提出了一種基于邏輯Petri網(wǎng)的過(guò)程挖掘方法,并給出了邏輯Petri網(wǎng)中邏輯變遷的挖掘算法.它可以充分挖掘活動(dòng)之間的業(yè)務(wù)邏輯,并且業(yè)務(wù)邏輯可用邏輯表達(dá)式表示.通過(guò)與相應(yīng)Petri網(wǎng)模型的實(shí)例比較分析,例證了本文方法的正確性和有效性,且邏輯Petri網(wǎng)模型更加適合日志行為.

過(guò)程挖掘;Petri網(wǎng);邏輯Petri網(wǎng);邏輯變遷;挖掘算法

1 引言

過(guò)程挖掘通過(guò)挖掘?qū)嶋H的日志信息,發(fā)現(xiàn)并改進(jìn)現(xiàn)實(shí)的模型[1],主要包括過(guò)程發(fā)掘、一致性檢測(cè)和過(guò)程改進(jìn).在過(guò)程挖掘研究中,由于Petri網(wǎng)[2]描述和分析并發(fā)事件的優(yōu)越性,許多研究都以Petri網(wǎng)作為描述過(guò)程的工具.α算法[3]是根據(jù)活動(dòng)的順序關(guān)系進(jìn)行過(guò)程挖掘,當(dāng)模型中不包括重復(fù)活動(dòng)、不可見(jiàn)變遷以及特定結(jié)構(gòu)式時(shí),能挖掘得到系統(tǒng)的正確模型.由于α算法不能有效挖掘包括重復(fù)活動(dòng)、不可見(jiàn)變遷和特定結(jié)構(gòu)的系統(tǒng)模型,出現(xiàn)了α算法的多種擴(kuò)展.針對(duì)α算法不能挖掘不可見(jiàn)變遷問(wèn)題,文獻(xiàn)[4]提出了可以有效挖掘不可見(jiàn)變遷的alpha#算法.針對(duì)α算法無(wú)法判定非自由選擇結(jié)構(gòu)問(wèn)題,文獻(xiàn)[5]提出了相應(yīng)的過(guò)程挖掘方法.除α算法外,還有基于區(qū)域的過(guò)程挖掘算法[6,7].文獻(xiàn)[6]從日志挖掘低等級(jí)的變遷系統(tǒng),通過(guò)變遷系統(tǒng)得到模型,從而克服了α算法的一些局限性.為了進(jìn)行多角度挖掘,出現(xiàn)了基于顏色Petri網(wǎng)CPN(Color Petri Net )的過(guò)程挖掘算法[7,8],并通過(guò)對(duì)Petri網(wǎng)進(jìn)行拓展以考慮時(shí)間和成本對(duì)工作流決策的影響.這些方法通常以Petri網(wǎng)[9,10]為描述工具,但當(dāng)并行活動(dòng)之間的邏輯關(guān)系更加復(fù)雜時(shí)(如存在復(fù)雜的與或關(guān)系),僅使用Petri網(wǎng)不足以對(duì)其進(jìn)行簡(jiǎn)潔地描述,且得到的模型不能充分反映日志信息.圖1和圖2是由相同旅游預(yù)訂日志L1={σ1=t1t2t5,σ2=t1t2t4t5,σ3=t1t4t2t5,σ4=t1t4t2t3t5,σ5=t1t2t4t3t5,σ6=t1t2t3t4t5,σ7=t1t3t5}得到的Petri網(wǎng)模型,其中圖1是使用α算法挖掘得到的Petri網(wǎng)模型,圖2是由文獻(xiàn)[7] 給出的先得到C-net后轉(zhuǎn)化得到的Petri網(wǎng)模型.t1代表開(kāi)始預(yù)訂,t2代表預(yù)訂機(jī)票,t3代表預(yù)訂車(chē)票,t4代表預(yù)訂旅館,t5代表完成預(yù)定.黑方框代表不可見(jiàn)變遷,即在日志中沒(méi)有對(duì)應(yīng)的事件.預(yù)訂機(jī)票(t2)和預(yù)訂賓館(t4)之間業(yè)務(wù)邏輯關(guān)系為:(1)預(yù)定機(jī)票t2可以單獨(dú)發(fā)生;(2)在t2和t4同時(shí)發(fā)生時(shí)它們的關(guān)系是并行的.傳統(tǒng)挖掘方法可能認(rèn)為t2和t4是并行的,但忽視了t2可以單獨(dú)發(fā)生的情況.此外,由圖2知,在挖掘得到的Petri網(wǎng)模型中,需要添加大量的不可見(jiàn)變遷.

針對(duì)上述問(wèn)題,有些學(xué)者提出先挖掘得到C-net模型,再將其轉(zhuǎn)化成等價(jià)的Petri網(wǎng)模型,并使得到的模型比原有方法得到的模型更準(zhǔn)確.為了得到更為簡(jiǎn)潔和更高擬合度的Petri網(wǎng)模型,本文采用另一種方法,在α算法挖掘結(jié)果的基礎(chǔ)上,利用任務(wù)發(fā)生的頻次關(guān)系得到活動(dòng)之間的與或關(guān)系,通過(guò)活動(dòng)之間的關(guān)系推導(dǎo)得到邏輯Petri網(wǎng)中的邏輯表達(dá)式,從而對(duì)挖掘模型進(jìn)行約束,使得挖掘結(jié)果更加簡(jiǎn)潔、貼合日志,進(jìn)而得到邏輯Petri網(wǎng)模型[11,12,13].同時(shí),最后得到的邏輯Petri模型,也可以有效解決由α算法表示偏好(representational bias)引起的死鎖問(wèn)題.

2 基本概念

本節(jié)介紹邏輯真值與邏輯Petri網(wǎng)的相關(guān)概念.在邏輯Petri網(wǎng)中,通過(guò)邏輯表達(dá)式約束網(wǎng)中邏輯變遷的引發(fā).為了討論邏輯表達(dá)式的值,首先需要引入Petri網(wǎng)和邏輯真值的概念.

定義1 (Petri網(wǎng))四元組PN=(P,T;F,M)稱為一個(gè)Petri網(wǎng)PN,其中P是一個(gè)有限庫(kù)所集,T是一個(gè)有限變遷集,F?(P×T)∪(T×P)是一個(gè)有限弧集,M:P→N稱為網(wǎng)PN的一個(gè)標(biāo)識(shí).

有關(guān)Petri網(wǎng)更詳細(xì)的定義請(qǐng)參見(jiàn)文獻(xiàn)[2,9,10].

定義2 (邏輯真值)設(shè)f為庫(kù)所集合P的邏輯表達(dá)式,M為P的標(biāo)識(shí)向量,對(duì)?p∈P,記p|M為在M下p的邏輯真值,記f|M為邏輯表達(dá)式f在M下的邏輯真值,f(p1,p2,…,pn)|M=f(p1|M,p2|M,…,pn|M) 其中p|M的值定義如下:

在定義2中,.T./.F.為邏輯值為真/假.下面給出邏輯Petri網(wǎng)的概念.

定義3 (邏輯Petri網(wǎng))一個(gè)邏輯Petri網(wǎng)定義為一個(gè)六元組LPN=(P,T;F,I,O,M),其中

(1)P是一個(gè)有限庫(kù)所集.

(2)T=TD∪TI∪TO是一個(gè)有限變遷集,T∩P=?.若t∈TI∩TO,則·t∩t·=?.

(a)TD表示Petri網(wǎng)中的變遷集;

(b)TI表示邏輯輸入變遷集,對(duì)?t∈TI,t的輸入庫(kù)所·t受邏輯表達(dá)式fI(t)的限制;

(c)TO表示邏輯輸出變遷集,對(duì)?t∈TO,t的輸出庫(kù)所t·受邏輯表達(dá)式fO(t)的限制;

(3)F=(P×T)∪(T×P)是一個(gè)有限弧集;

(4)I是由邏輯輸入變遷到邏輯輸入函數(shù)的映射,對(duì)于?t∈TI,I(t)=fI(t);

(5)O是由邏輯輸出變遷到邏輯輸出函數(shù)的映射,對(duì)于?t∈TO,O(t)=fO(t);

(6)M:P→Z0是Petri網(wǎng)的表示函數(shù),Z0={0,1,2……};

(7)變遷引發(fā)規(guī)則:

(a)對(duì)?t∈TD,變遷引發(fā)規(guī)則與傳統(tǒng)Petri網(wǎng)一致.即設(shè)M[t>M′,M′(p)定義如下:

(b)?t∈TI,若fI(t)|M=.T.,則邏輯輸入變遷t可引發(fā),記做M[t>M′,且對(duì)?p∈·t,M′(p)=0;對(duì)?pt·∪·t,M′(p)=M(p);對(duì)?p∈t·,M′(p)=1;

(c)對(duì)?t∈TO,若?p∈·t,M(p)=1,則邏輯輸出變遷t可引發(fā),且對(duì)?p∈·t,M′(p)=0;對(duì)?p∈t·,需滿足fO(t)|M′=.T.;對(duì)?pt·∪·t,M′(p)=M(p).

圖3給出了一個(gè)邏輯Petri網(wǎng)的例子.t1為邏輯輸入變遷,I(t1)=(p1?p2)∧p3是t1的邏輯輸入函數(shù),(p1?p2)表示t1觸發(fā)時(shí),p1和p2中不能同時(shí)存在托肯.(p1?p2)∧p3表示t1在如下兩種情況下滿足觸發(fā)條件:(1)p1和p3中存在托肯;(2)p2和p3中存在托肯.t2為經(jīng)典Petri網(wǎng)的變遷,觸發(fā)規(guī)則與經(jīng)典Petri相同.t3為邏輯輸出變遷,其邏輯輸出函數(shù)O(t3)=p7∨p8表示t3引發(fā)后會(huì)有三種情況:(1)p7和p8中有托肯;(2)p7中有托肯;(3)p8中有托肯.

3 邏輯變遷的挖掘方法

本節(jié)給出邏輯變遷挖掘算法的相關(guān)定義以及算法描述.挖掘算法主要實(shí)現(xiàn)單個(gè)邏輯變遷的挖掘.由于邏輯輸入變遷和邏輯輸出變遷的相關(guān)結(jié)論可以通過(guò)逆網(wǎng)進(jìn)行轉(zhuǎn)化,因此本文僅給出挖掘邏輯輸入變遷的挖掘方法.不同挖掘方法得到的Petri網(wǎng)模型可能不同,故將其轉(zhuǎn)化為邏輯Petri網(wǎng)的方法也有所區(qū)別.因此,本文研究在α算法得到的Petri網(wǎng)模型基礎(chǔ)上,通過(guò)進(jìn)一步日志挖掘得到邏輯Petri網(wǎng)的方法.首先引入日志和跡的概念.

定義4 (跡,日志)PN=(P,T;F,M)為一個(gè)Petri網(wǎng),日志L?T*,跡σ∈L.這里對(duì)于?t?T,?σ∈L,滿足t∈&(σ),即L中記錄了網(wǎng)中所有可以被記錄的活動(dòng).用&(σ)表示由跡σ中所有活動(dòng)構(gòu)成的集合.

在挖掘到的Petri網(wǎng)模型中,若把變遷t轉(zhuǎn)換為邏輯輸入變遷,需要基于日志信息挖掘t與前面相鄰變遷之間的邏輯關(guān)系.因此,下面引入前序變遷集的概念.

定義5 (前序變遷集)設(shè)PN=(P,T;F,M)為一個(gè)由日志L得到的Petri網(wǎng),tk∈T,tk的前序變遷集定義為T(mén)bef|tk={t|p∈·tk∧t∈·p}.

定義6 (變遷邏輯關(guān)系)設(shè)PN=(P,T;F,M)為一個(gè)由日志L得到的Petri網(wǎng),tk∈T,tk的前序變遷集為T(mén)bef|tk.L′為L(zhǎng)在Tbef|tk投影得到的日志,σ為日志的一條跡,對(duì)T1,T2?Tbef|tk,(a>L′b)|σ表示在σ上活動(dòng)a和b的關(guān)系為a>L′b.令A(yù)={σ|σ∈L′∧(a>L′b)|σ,a∈T1,b∈T2},B={σ|σ∈L′∧(b>L′a)|σ,a∈T1,b∈T2},C={σ|σ∈L′∧(a∈&(σ))},D={σ|σ∈L′∧(b∈&(σ))}.令k1=|A|/min{|C|,|D|},k2=|B|/min{|C|,|D|}.給定常數(shù)m和n用于度量變遷的并發(fā)程度,且0

在定義6中,a→b或b←a表示b依賴于a,∨表示或關(guān)系,∧表示與關(guān)系.k1和k2是介于0到1之間的數(shù),用于描述變遷a和b的依賴關(guān)系.當(dāng)k1接近于0時(shí),表示在L′中極少出現(xiàn)a>L′b.當(dāng)k1接近于1時(shí),表示L′中a和b的關(guān)系為a→b.m和n是用于度量a和b的并發(fā)程度的數(shù)值.當(dāng)lr(a,b)=a?b時(shí),日志L′中極少出現(xiàn)a>L′b或b>L′a,即k1和k2都接近0.因此,這里記為k1+k2n.當(dāng)k1+k2>n時(shí),還存在k1很大而k2很小的情況,即a→b.a∧b與a→b區(qū)別在于a∧b滿足條件min{k1,k2}>m.這里m和n的值是在分析問(wèn)題時(shí),由用戶自定義的數(shù)值.

定義6給出了前序變遷集中變遷的四種邏輯關(guān)系.在此基礎(chǔ)上,可以進(jìn)一步將前序變遷集中變遷的邏輯關(guān)系反映到其后繼庫(kù)所上,使庫(kù)所的邏輯關(guān)系與變遷的邏輯關(guān)系保持一致.

定義7 (庫(kù)所邏輯關(guān)系)設(shè)PN=(P,T;F,M)為一個(gè)由日志L得到的Petri網(wǎng),t∈T,Tbef|t為t的前序變遷集.a,b∈Tbef|t,Pa={p|p∈a·∩·t},Pb={p|p∈b·∩·t},Pa-b=Pa-Pb,Pb-a=Pb-Pa.庫(kù)所邏輯關(guān)系pl(lr(a,b))定義為:

(1)若lr(a,b)=a∧b,則pl(lr(a,b))=f(Pa)∧f(Pb)=·T·即t觸發(fā)時(shí),在Tbef|t中a和b都觸發(fā);

(2)若lr(a,b)=a?b,則pl(lr(a,b))=(f(Pa)∧┐f(Pb-a))∨(f(Pb)∧┐f(Pa-b))=.T.,即t觸發(fā)時(shí),在Tbef|t中a和b只有一個(gè)能觸發(fā);

(3)若lr(a,b)=a∨b,則pl(lr(a,b))=f(Pa)∨f(Pb)=.T.,即t觸發(fā)時(shí),在Tbef|t中需要a或b觸發(fā);

(4)若lr(a,b)=a→b,pl(lr(a,b))=(f(Pa)∧┐f(Pb))∨(f(Pb)∨┐f(Pa))=.T.,即t觸發(fā)時(shí),只有Pa或Pb中存在托肯.

在定義7中,當(dāng)a?b時(shí),Pa∩Pb≠?,此時(shí)討論的集合為Pa-b和Pb-a.日志L4={abc,ac}由α算法挖掘的Petri網(wǎng)模型如圖4所示.但是,在該模型中,不能反映日志中的a→t.這個(gè)問(wèn)題可在相應(yīng)的邏輯Petri網(wǎng)中解決,且其優(yōu)化后的邏輯Petri網(wǎng)模型如圖5所示,其中I(t)=(f(Pa)∧┐(f(Pb)∨((f(Pb)∧┐f(Pa)).下面的定理1將證明若?c∈Tbef|t,c≠a,則lr(c,b)≠c→b.即在Tbef|t中,只有a會(huì)與b存在依賴關(guān)系的情況下.Pa和Pb的邏輯關(guān)系pl(lr(a,b))=(f(Pa)∧┐f(Pb))∨(f(Pb)∧┐f(Pa)),即在處理a→b時(shí),應(yīng)將其視為a?b.

定理1 設(shè)LPN=(P,T;F,I,O,M)為一個(gè)由日志L得到的Petri網(wǎng),t∈T,Tbef|t為t的前序變遷集,L′是L在Tbef|t上的投影,a,b∈Tbef|t且a,bTO.若a→b,且M[t>,則Pa與Pb的邏輯關(guān)系滿足(f(Pa)∧┐f(Pb)∨(f(Pb)∧┐f(Pa))=.T..

證明:先考慮不引入不可見(jiàn)變遷的情況,且Pa∈·b.采用反證法,令Pa·b,由a,b∈Tbef|t,a→b,則?M[a>M′,(f(Pa)|M′)∧┐f(·b)|M′)=.T..令M′[b>M″,有(f(Pa)|M″)∧┐f(Pb)|M″)=.T..若t觸發(fā),則表達(dá)式應(yīng)為(f(Pa)|M″)∧┐f(Pb)|M″),且原日志中不存在跡,這與原有日志矛盾.因此,Pa∈·b.

因?yàn)镻a∈·b,故?M,M[b>,f(Pb)|M=.T.,f(Pa)|M=.F.,且f(Pb)|M∧┐f(Pa)|M=.T..由a∈Ti|t1,故對(duì)?M[a>M′,M′[t>,有f(Pb)|M′=.F.,f(Pa)|M′=.T.,且f(Pa)|M′∧┐f(Pb)|M′=.T..因此,邏輯輸入變遷t的邏輯輸入函數(shù)應(yīng)為(f(Pa)∧┐f(Pb))∨(f(Pb)∧┐f(Pa)).[證畢]

由定理1,當(dāng)a→b時(shí),Pa和Pb的行為與a?b相同.故在下面處理a→b時(shí),可把它作為a?b處理.從邏輯變遷的邏輯輸入函數(shù)可知,兩者是等價(jià)的.

定義7描述了邏輯輸入變遷的前序庫(kù)所邏輯與其前序變遷集中變遷邏輯之間的關(guān)系.由定義7和定理1,根據(jù)日志可得到邏輯變遷的邏輯輸入表達(dá)式,再將邏輯關(guān)系轉(zhuǎn)化成邏輯變遷的邏輯輸入函數(shù),可得到邏輯輸入表達(dá)式I(t).為了得到邏輯變遷的邏輯輸入函數(shù),需要引入邏輯前序矩陣的概念.

定義8 (邏輯前序矩陣)PN=(P,T;F,M)是由日志L得到的Petri網(wǎng),t1∈T,Tbef|t為t的邏輯前序變遷集.t的邏輯前序矩陣定義為(AI|t)[n][n](n=|Tbef|t|).設(shè)i,j∈[0,n),當(dāng)i≠j時(shí),(AI|t1)[i][j]=lr(i,j),反之,(AI|t1)[i][j]=?.

由定義8,邏輯前序矩陣可表達(dá)前序變遷集中任意兩個(gè)變遷的邏輯關(guān)系.對(duì)于給定的前序變遷集中的任意個(gè)變遷,通過(guò)邏輯前序矩陣可以得到這些變遷之間的邏輯關(guān)系.下面給出前序邏輯表達(dá)式的概念.

定義9 (前序變遷表達(dá)式)PN=(P,T;F,M)是由日志L得到的Petri網(wǎng),t∈T,Tbef|t為t的邏輯前序變遷集,t的邏輯前序矩陣為(AI|t).對(duì)?T′?Tbef|t,λ(T′,AI|t1)稱為由AI|t得到的關(guān)于T′的前序變遷表達(dá)式.

基于邏輯前序矩陣挖掘前序變遷集中變遷的邏輯關(guān)系時(shí),要考慮?和∧,以及?和∨是否滿足分配律.如a,b,c∈Tbef|t1,lr(a,b)=a∧b,lr(a,c)=a∧c,lr(b,c)=b?c,若先挖掘得到?,可得到表達(dá)式f1=a∧(b?c);若先挖掘得到∧,可得到表達(dá)式f2=(a∧b)?(a∧c).但是,下面將證明這兩種順序是等價(jià)的,即∧對(duì)?滿足分配率.這里證明plf1(lr(a,lr(b,c)))=plf2(lr(a,c),lr(a,b)),其中plf1(lr(a,b))表示在變遷表達(dá)式f1下得到的庫(kù)所邏輯表達(dá)式.

定理2 設(shè)PN=(P,T;F,M)為一個(gè)由日志L得到的Petri網(wǎng),t∈T,Tbef|t為t的前序輸入變遷集,a,b,c∈Tbef|t.若lr(a,b)=a∧b,lr(a,c)=a∧c,且lr(b,c)=b?c,則對(duì)于邏輯表達(dá)式f1=a∧(b?c)與f2=(a∧b)?(a∧c),有plf1(lr(a,lr(b,c)))=plf2(lr(a,c),lr(a,b)).

證明:由定義6,左邊=plf1(lr(a,lr(b,c)))=f(pa)∧f(pb,c)=f(pa)∧((f(Pc)∧┐f(Pb-c))∨(f(Pb)∧┐f(Pc-b)))=((f(pa)∧f(Pc)∧┐f(Pb-c))∨(f(pa)∧f(Pb)∧┐f(Pc-b)).右邊=plf2(lr(a,c),lr(a,b))=(f(pa,c)∧┐f(p(a,b)-(a,c))∨(f(pa,b)∧┐f(p(a,c)-(a,b)))=((f(pa)∧f(Pc)∧┐f(Pb-c))∨(f(pa)∧f(Pb)∧┐f(Pc-b))=plf1(lr(a,lr(b,c))).

因此,左邊=右邊,即原等式成立.[證畢]

類似的還可以得到?對(duì)∧也滿足分配率,即?和∧都滿足分配率.同樣可以推出?和∨也滿足分配率.在Petri網(wǎng)中給出一個(gè)變遷t的邏輯前序矩陣AI|t,根據(jù)定理2,下面將給出前序變遷集中變遷邏輯關(guān)系的挖掘算法.

定義10 (邏輯輸入函數(shù))設(shè)LPN=(P,T;F,I,O,M)是由日志L得到的邏輯Petri網(wǎng),t∈T,Tbef|t為t的邏輯前序變遷集,λ為由矩陣AI|t得到的邏輯表達(dá)式.t的邏輯輸入函數(shù)定義為fI(t)=pl(λ).

定義10給出了邏輯表達(dá)式與邏輯輸入函數(shù)的關(guān)系,下面的算法1將實(shí)現(xiàn)由前序變遷矩陣挖掘出前序變遷集中變遷的邏輯關(guān)系.

在算法1中,為了處理‘→’與‘∧’,下面分別給出相應(yīng)的轉(zhuǎn)換規(guī)則.

規(guī)則1 (a→b的轉(zhuǎn)換規(guī)則)LPN=(P,T;F,I,O,M)為一個(gè)由日志L得到的邏輯Petri網(wǎng),t∈T,Tbef|t1為t的前序輸入變遷集.a,b∈Tbef|t,若a→b且aTO,根據(jù)定理1,使a·∩·b=pa,即合并a·∩·b與pa.在AI|t中把lr(a,b)置為?.若a∈TO,則只在AI|t中將lr(a,b)置為?.

對(duì)于規(guī)則1,雖然在邏輯輸出變遷中也可以得到類似規(guī)則,但變遷a和b在相鄰的邏輯輸入變遷和邏輯輸出變遷之間時(shí),可能會(huì)導(dǎo)致同樣的結(jié)構(gòu)被處理兩次.為了避免這個(gè)問(wèn)題,規(guī)定同一個(gè)a→b結(jié)構(gòu)只能被處理一次,且在其他變遷中記a→b為a?b.

規(guī)則2 (a?b的轉(zhuǎn)換規(guī)則)LPN=(P,T;F,I,O,M)為一個(gè)由日志L得到的邏輯Petri網(wǎng),t∈T,Tbef|t為t的輸入變遷集.a,b∈Tbef|t且a,bTO.pl(a?b)=(f(pa)∧┐f(pb-a))∨(f(pb)∧┐f(pa-b)),其中

(1)當(dāng)pa∩pb=?時(shí),pl(a?b)=f(pa)?f(pb);

(2)當(dāng)pb=pa時(shí),pl(a?b)=f(pa)∨f(pb)=f(pa);

(3)當(dāng)pb≠pa和pb-pa=?,即pl(a?b)=f(pa)∨(f(pb)∧f(pa-b))時(shí),F=F-a×(pa∩pb),pa=pa-pb,且pl(a?b)=(f(pa)∧┐f(pb))∨(f(pb)∧┐f(pa));

規(guī)則2給出了化簡(jiǎn)邏輯Petri網(wǎng)模型和邏輯表達(dá)式的方法.如在圖1中,pl(t1,t4)=(f(pt1)∧┐f(pt4-t1))∧(f(pt4)∧┐f(pt1-t4)).因?yàn)閜t1-t4=?,故F=F-a×(pt1∩pt4),pt4=pt4-pt1=p2,且pl(t1,t4)=p1?p2.這樣就能利用引入的邏輯表達(dá)式簡(jiǎn)化邏輯Petri網(wǎng)模型.將挖掘得到的模型轉(zhuǎn)化成它的逆網(wǎng),可以得到邏輯輸出變遷的類似定義.

在執(zhí)行算法1時(shí),利用規(guī)則1和規(guī)則2可以改善原有挖掘結(jié)果.在處理t1?t2中第三種情況時(shí),將出現(xiàn)庫(kù)所的消減.算法1沒(méi)有考慮(的優(yōu)化順序,這會(huì)影響最終得到的邏輯Petri網(wǎng)的挖掘效果.圖6是由L4={〈t1,t3,t5,t7〉2,〈t1,t5,t3,t7〉3,〈t2,t4,t6,t7〉2,〈t2,t6,t4,t7〉4}挖掘得到的Petri網(wǎng).若將t7視為邏輯輸入變遷,圖7給出了其邏輯前序矩陣.使用算法1,首先尋找AI|t7中為?的元素,有λ1=t3?t4,λ2=t3?t6,λ3=t4?t5,且λ4=t5?t6.根據(jù)t3∧t5,得λ1=λ1∧λ3=t4?(t3∧t5),λ2=λ2∧λ4=t6?(t3∧t5).由t4∧t6,得λ1=λ1∧λ2=(t3∧t5)?(t4∧t6).此時(shí),得到如圖8所示的邏輯Petri網(wǎng)模型,且根據(jù)t3∧t5得λ1=λ1∧λ4=(t3?t4)∧(t5?t6).λ2=λ2∧λ3=(t3?t6)∧(t4?t5).λ1=λ1∧λ2=(t3?t4)∧(t5?t6)∧(t3?t6)∧(t4?t5)=(t3∧t5)?(t4∧t6).因此,得到如圖9所示的邏輯Petri網(wǎng)模型.

圖8和圖9的前序變遷表達(dá)式相同,但最后的邏輯輸入表達(dá)式以及邏輯Petri網(wǎng)模型不同.圖8中出現(xiàn)了一次規(guī)則2中的第(4)種情況,而圖9中出現(xiàn)了兩次這種情況.由于第(4)種情況涉及到庫(kù)所的消減,因此,圖9的庫(kù)所和弧比圖8的都更少.為了使得到的邏輯Petri網(wǎng)模型盡量簡(jiǎn)潔,在處理?時(shí),采用貪心算法.優(yōu)先處理出度較多的變遷,且在處理時(shí)優(yōu)處理規(guī)則2中的第(4)種情況.因此,可以得到改進(jìn)后的算法2.

由算法2,可以確定前序變遷集中變遷之間的邏輯關(guān)系.在圖1中,{t2,t3,t4}通過(guò)算法2可以得到(t2∧t4)?(t3∧t4),代表跡σ∈{t1t2t3t4t5,t1t4t2t3t5,t1t2t4t3t5}.但此時(shí)無(wú)法表示t2與t3單獨(dú)發(fā)生的情況.為了解決這個(gè)問(wèn)題,算法3將日志在前序變遷集上進(jìn)行投影.將投影后長(zhǎng)度相同的跡分為一組,并將每組中的變遷用算法2得到其邏輯關(guān)系.這樣就可以得到能反映日志的前序變遷表達(dá)式,進(jìn)而計(jì)算相應(yīng)的邏輯輸入函數(shù).

本節(jié)給出了一種單個(gè)邏輯輸入變遷的挖掘方法.在此基礎(chǔ)上,按優(yōu)化所有路由選擇變遷得到的邏輯Petri網(wǎng)模型,比原有Petri網(wǎng)模型能更充分反映日志中的信息.而優(yōu)化的順序不同會(huì)引起最終結(jié)果的不同,這會(huì)在下面的例子中給與展示.

4 實(shí)例分析

本節(jié)給出第3節(jié)挖掘方法的實(shí)例分析,從而展示以邏輯Petri網(wǎng)挖掘模型比Petri網(wǎng)挖掘模型更符合日志行為.以某三甲醫(yī)院實(shí)際就診日志為例,給出其邏輯Petri網(wǎng)挖掘模型與相應(yīng)Petri網(wǎng)挖掘模型的比較分析,其中Petri網(wǎng)模型是由啟發(fā)式(Heuristic)算法得到的模型轉(zhuǎn)化而來(lái)的.

例1 本例中的日志和圖1中的日志軌跡相同,L1={σ1=t1t2t5,σ2=t1t2t4t5,σ3=t1t4t2t5,σ4=t1t4t2t3t5,σ5=t1t2t4t3t5,σ6=t1t2t3t4t5,σ7=t1t3t5}.首先將t5轉(zhuǎn)換為邏輯輸入變遷:由模型可知Ti|t5={t2,t3,t4},由定義6,可得到日志并發(fā)度k(t2,t3)=0.6,k(t3,t2)=0,k(t2,t4)=0.25,k(t4,t2)=0.25,k(t3,t4)=0.25,k(t4,t3)=0.25.取m=0.3,n=0.5,則lr(t2,t3)=t2→t3,lr(t2,t4)=t2∧t4,lr(t3,t4)=t3∧t4.

構(gòu)建邏輯前序矩陣AI|t5如下:

根據(jù)上述三個(gè)邏輯前序矩陣,依次得到λ1=t1?t2,λ2=t2∧t4,λ3=t2∧t4,λ4=(t2?t3)∧t4,且λ=(t2?t3)∨(t2∧t4)∨((t2?t3)∧t4).根據(jù)相應(yīng)轉(zhuǎn)換規(guī)則,合并pt2與·t3得到圖10中的邏輯Petri網(wǎng).根據(jù)定義7,I(t5)=pl(λ)=(p3?p4)∨(p3∧p5)∨(p3?p4)∧p5)=(p3?p4)∨((p3?p4)∧p5).將t3轉(zhuǎn)化為邏輯輸入變遷時(shí),由于t3的前序變遷集為{t1,t2},且lr(t1,t2)=t1→t2,則合并pt1與·t2后,有I(t3)=p1?p3.處理t1時(shí),由于t2→t3在處理t5時(shí)已被處理,記lr(t2,t3)=t2?t3,得O(t1)=p1∨(p1∧p2).

若處理變遷t1t2t5,可以得到圖11中的邏輯Petri網(wǎng)模型.在圖11中,O(t1)=(p1?p3)∨((p1?p3)∧p2),O(t2)=p3?p4,I(t5)=p4∨(p4∧p5).圖11中的模型可正確反映原日志中的模型.依次處理變遷t3t1t5和t3t5t1可以得到和圖10相同的邏輯Petri網(wǎng),依次處理t2t1t5和t2t5t1可以得到和圖11相同的邏輯Petri網(wǎng)模型.對(duì)比圖1和圖10,日志L1在圖1中只有σ4,σ5,σ6重演,而日志L1在圖11中的跡均可以被重演.因此,挖掘得到的邏輯Petri網(wǎng)模型相比原Petri網(wǎng)模型,能更加充分的反映日志中的信息.對(duì)比圖2和圖10,兩者均可以重演日志L1中的跡,但通過(guò)比較比較庫(kù)所和變遷的數(shù)目可以發(fā)現(xiàn)圖10中的模型更為簡(jiǎn)潔.

例2:圖12給定某三甲醫(yī)院門(mén)診服務(wù)和檢查的部分流程.圖13為圖12中t11代表的子流程,包括6520條跡,以及九個(gè)事件:掛號(hào)、PET-CT、普通CT、胸部增強(qiáng)CT、生化全套、血沉、血?dú)夥治?、血常?guī)和診斷,在將其進(jìn)行格式轉(zhuǎn)化成為XES文件后,基于該日志,在ProM6.5下用ProM中啟發(fā)式算法挖掘得到的Petri網(wǎng)模型,如圖13所示,其中黑方框表示不可見(jiàn)變遷.可見(jiàn)變遷中左邊第一列變遷名為“掛號(hào)”,第二列從上到下變遷名分別為“PET-CT”、“胸部增強(qiáng)CT”和“普通CT”,第三列從上到下變遷名分別為“生化全套”、“血沉”、“血?dú)夥治觥焙汀把Ｒ?guī)”,第四列變遷名為“診斷”.在ProM上使用α算法挖掘得到的Petri網(wǎng),如圖14所示.在圖14的基礎(chǔ)上,利用本文方法進(jìn)一步挖掘日志信息,得到的邏輯Petri網(wǎng)如圖15所示,其中“掛號(hào)”為邏輯輸出變遷,且其邏輯輸出表達(dá)式為Oregister=p1?p3.“診斷”為邏輯輸入變遷,且其邏輯輸入表達(dá)式為Idiagnose=p3?p4(p6.表1對(duì)由Heuristic-net得到的Petri網(wǎng)、α算法挖掘

得到的Petri網(wǎng)、C-net網(wǎng)及相應(yīng)的邏輯Petri網(wǎng)的性能指標(biāo),進(jìn)行了比較分析.由表1可知,圖13和圖15的擬合度(Fitness)比圖14中的模型要好,圖14和圖15比圖13的模型規(guī)模更小,且主要體現(xiàn)在庫(kù)所的規(guī)模以及不可見(jiàn)變遷的數(shù)量上.從泛化度(Generalization)以及精確度(precision)[14]上比較,圖15的模型比圖13的好.

在時(shí)間消耗上,α算法和啟發(fā)式算法挖掘Heuristic網(wǎng)挖掘效率最快,這是因?yàn)樗鼈冊(cè)诖笠?guī)模日志上沒(méi)有重復(fù)的操作,如表1所示.本文方法需要在α算法的基礎(chǔ)上,還需通過(guò)日志得到定義6中相應(yīng)的頻次關(guān)系.因此,本文方法在時(shí)間上的花費(fèi)會(huì)比前兩種算法要高.圖16為通過(guò)啟發(fā)式算法挖掘得到C-net后,在ProM下得到的BPMN模型(可轉(zhuǎn)化為與圖15等價(jià)的邏輯Petri網(wǎng)).挖掘C-net需要多次遍歷日志[1],如對(duì)于圖1中的變遷t1,本文方法需要確定{t2,t3},{t3,t4}和{t2,t4}三組變遷之前的頻次關(guān)系,而挖掘它的C-net需確定所有可能的綁定關(guān)系,即{t1,t2},{t1,t3},{t1,t4},{t1,{t2,t3}},{t1,{t3,t4}),{t1,{t2,t3}},{t1,{t2,t4}},{t1,{t2,t3,t4}}.由表1知,C-net的平均時(shí)間比本文邏輯Petri網(wǎng)花費(fèi)時(shí)間更多.C-net中沒(méi)有庫(kù)所和變遷的概念.

表1 例2中四種模型的比較

庫(kù)所變遷擬合度泛化度精確度平均時(shí)間消耗(s)Heuristic-net18540.96350.80210.85110.6795Petri網(wǎng)890.78790.83500.81250.5683C-net0.97680.90660.93327.8626邏輯Petri網(wǎng)790.99980.93780.93633.5039

5 總結(jié)

本文針對(duì)復(fù)雜系統(tǒng)的過(guò)程挖掘問(wèn)題,特別是對(duì)于系統(tǒng)中在并行活動(dòng)之間存在復(fù)雜與或關(guān)系的過(guò)程挖掘,將邏輯Petri網(wǎng)應(yīng)用到過(guò)程發(fā)掘中,在原有α算法的基礎(chǔ)上,考慮事件的頻次,提出了一種邏輯變遷的挖掘方法.挖掘得到的邏輯Petri網(wǎng)模型能夠正確描述活動(dòng)之間復(fù)雜的業(yè)務(wù)邏輯關(guān)系.本文方法可以作為α及其拓展方法的補(bǔ)充,即在原有方法需要更加深入的挖掘日志信息時(shí),可將邏輯Petri作為工具進(jìn)行更深入的挖掘.因此,本文方法的效率會(huì)低于一般的α算法或擴(kuò)展的α算法,比如alpha#算法[4].算法效率的提高及批量日志的自動(dòng)挖掘與比較,將作為下一步的研究?jī)?nèi)容.

[1]Van der Aalst W.Process Mining:Discovery,Conformance and Enhancement of Business Processes[M].Berlin Heidelberg:Springer,2011.1-30.

[2]杜玉越,薛潔,李彥成.基于服務(wù)簇的服務(wù)組合替換與分析[J].電子學(xué)報(bào),2014,42(11):2231-2238.

Du Yuyue,Xue Jie,Li Yancheng.Substitution and analysis of service composition based on service clusters[J].Acta Electronica Sinica,2014,42(11):2231-2238.(in Chinese)

[3]Van der Aalst W,et al.Workflow mining:discovering process models from event logs[J].Knowledge and Data Engineering,IEEE Transactions on,2004,16(9):1128-1142.

[4]Wen L,Wang J,van der Aalst W M P,et al.Mining process models with prime invisible tasks[J].Data & Knowledge Engineering,2010,69(10):999-1021.

[5]Wen L,van der Aalst W M P,Wang J,et al.Mining process models with non-free-choice constructs[J].Data Mining and Knowledge Discovery,2007,15(2):145-180.

[6]Van der Aalst W,et al.Process mining:a two-step approach to balance between underfitting and overfitting[J].Software & Systems Modeling,2010,9(1):87-111.

[7]Busi N,Pinna G,van der Aalst W.An Iterative Algorithm for Applying the Theory of Regions in Process Mining[M].Beta,Research School for Operations Management and Logistics,2007.16-38.

[8]Rozinat A,Mans R S,Song M,et al.Discovering colored Petri nets from event logs[J].International Journal on Software Tools for Technology Transfer,2008,10(1):57-74.

[9]Du Y Y,Jiang C J.On the design and temporal Petri net verification of grid commerce architecture[J].Chinese Journal of Electronics,2008,17(2):247-251.

[10]梅曉勇,李師賢,等.一種支持組合事務(wù)的執(zhí)行語(yǔ)義分析方法[J].電子學(xué)報(bào),2012,40(7):1386-1396.

Mei Xiaoyong,Li Shixian,et al.An execution semantic analysis method for composition transaction[J].Acta Electronica Sinica,2012,40(7):1386-1396.(in Chinese)

[11]Du Y Y,Qi L,Zhou M C.Analysis and application of logical Petri nets to e-Commerce systems [J].Systems,Man,and Cybernetics:Systems,IEEE Transactions on,2014,44(4):468-481.

[12]Du Y Y,Jiang C J,Zhou M C.A Petri Net-based model for verification of obligations and accountability in cooperative systems[J].IEEE Transactions on Systems,Man,and Cybernetics--Part A:Systems and Humans,2009,39(2):299-308.

[13]Du Y Y,Ning Y H,Qi L.Reachability analysis of logic Petri nets using incidence matrix[J].Enterprise Information Systems,2014,8(6):630-647.

[14]Van der Aalst W,Adriansyah A,van Dongen B.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.

杜玉越 男,1960年生于山東聊城.博士,教授,博士生導(dǎo)師.研究方向?yàn)檫^(guò)程挖掘、工作流技術(shù)、Petri網(wǎng)應(yīng)用等.

E-mail:yydu001@163.com

朱鴻儒 男,1991年生于山東淄博.碩士研究生.研究方向?yàn)檫^(guò)程挖掘、工作流、Petri網(wǎng).

Email:zhr20122013@163.com

A Method of Process Mining Based on Logic Petri Nets

DU Yu-yue,ZHU Hong-ru,WANG Lu,LIU Wei

(KeyLaboratoryforWisdomMineInformationTechnologyofShandongProvince,ShandongUniversityofScienceandTechnology,Qingdao,Shandong266590,China)

Logic Petri nets are the abstraction and extension of the Petri nets with inhibitor arcs and high level Petri nets,and can describe the Business Logic among activities concisely and accurately in process mining.To further improve the simplicity and fitness of the mining models of complex systems,especially the systems with the complex AND-OR relation in parallel activities,a method of process mining is proposed based on Logic Petri nets to improve Petri net models in this paper.An algorithm of mining logic transitions is presented to transform the business logic among activities in event logs into logic expressions adequately.Experiment results illustrate that the mining logic Petri nets can represent the event logs more properly and succinctly than the corresponding Petri nets.

process mining;Petri net;logic Petri net;logic transition;mining algorithm

2015-06-08;

2015-12-28;責(zé)任編輯：藍(lán)紅杰

國(guó)家自然科學(xué)基金(No.61170078，No.61472228);山東省泰山學(xué)者建設(shè)工程專項(xiàng)經(jīng)費(fèi)；山東省自然科學(xué)基金(No.ZR2014FM009);青島市科技計(jì)劃基礎(chǔ)研究項(xiàng)目(No.13-1-4-116-jch);山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金(No.BS2015DX010)

TP311

A

0372-2112 (2016)11-2742-10

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.025