王倩倩， 王麗麗

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

0 引言

流程挖掘是一種從實(shí)際業(yè)務(wù)執(zhí)行日志中發(fā)現(xiàn)結(jié)構(gòu)化流程信息的過程[1].流程挖掘技術(shù)能夠從現(xiàn)代信息系統(tǒng)普遍產(chǎn)生的事件日志中抽取信息，通過建立清晰的流程模型，保證構(gòu)建的流程模型與實(shí)際的流程執(zhí)行過程保持一致，從而監(jiān)測和改進(jìn)原過程模型[2].目前，過程發(fā)現(xiàn)技術(shù)面臨的主要問題是事件日志往往不能包含一個(gè)業(yè)務(wù)流程模型的所有信息(如不完整日志)，從而導(dǎo)致所挖掘的流程模型與實(shí)際業(yè)務(wù)流程不一致.文獻(xiàn)[3]給出了流程模型與事件日志一致性程度的3種度量維度(合適度、精度、泛化)，但是這3種度量維度不能明確表達(dá)活動(dòng)之間的因果關(guān)系和并行關(guān)系.文獻(xiàn)[4]提出了一種從日志的活動(dòng)發(fā)生順序來推斷業(yè)務(wù)流程模型的算法，但該方法只能發(fā)現(xiàn)簡單的業(yè)務(wù)流程模型.M.Rovani等[5]和高立哲等[6]基于流程挖掘ProM平臺(tái)和事件日志，挖掘醫(yī)療業(yè)務(wù)流程，但該方法仍不適合結(jié)構(gòu)復(fù)雜的流程模型.針對以上問題，M.Weidlich等[7]以Petri網(wǎng)行為輪廓作為基線來計(jì)算新的服從指標(biāo)，該方法通過有效計(jì)算行為輪廓，避免了基于狀態(tài)空間指標(biāo)的性能問題，從而能夠清晰表達(dá)活動(dòng)之間復(fù)雜的業(yè)務(wù)流程關(guān)系.本文受文獻(xiàn)[7]的啟發(fā)，提出一種基于Petri網(wǎng)行為輪廓的網(wǎng)上購物流程挖掘方法，并結(jié)合實(shí)例驗(yàn)證本文方法的有效性.

1 基本概念

定義1[8](流程模型) 一個(gè)網(wǎng)P=(A,ai,a0,C,F,T)稱作流程模型，滿足以下條件：

1)A是活動(dòng)節(jié)點(diǎn),A≠?；C是控制節(jié)點(diǎn)，C≠?.

2)ai,a0∈A，ai是起始活動(dòng)，a0是結(jié)束活動(dòng).

3)F?((A{a0})∪C)×((A{ai})∪C)是流關(guān)系.

4)T:C{and,or,xor}是關(guān)于控制節(jié)點(diǎn)類型的函數(shù).

定義2[9](流程模型的弱序關(guān)系) 若P=(A,ai,a0,C,F,T)為一個(gè)流程模型，εP是執(zhí)行序列的集合，弱序關(guān)系?P?(A×A)包含所有(x,y)， 存在一個(gè)執(zhí)行序列σ=n1,…,nm，σ∈εP，?i,j∈{1,…,m-1}且j

定義3[9](流程模型的行為輪廓) 若P=(A,ai,a0,C,F,T)為一個(gè)流程模型，?(x,y)∈(A×A)滿足下面關(guān)系：

1)若x?Py且y?/Px， 則稱x和y之間為嚴(yán)格序關(guān)系，記作x→Py；

2)若x?/Py且y?/Px， 則稱x和y之間為排他性關(guān)系，記作x+Py；

3)若x?Py且y?Px， 則稱x和y之間為交叉序關(guān)系，記作x‖Py.

定義4[7](執(zhí)行序列，事件日志) 若Petri網(wǎng)P=(A,ai,a0,C,F,T)為一個(gè)流程模型，σP為P的一個(gè)發(fā)生序列σP∈{ai}·A*·{a0}， 事件日志L是執(zhí)行序列σP的集合.

定義5[9](流程模型的因果行為輪廓) 若P=(A,ai,a0,C,F,T)為一個(gè)流程模型，則：

1)共現(xiàn)關(guān)系?P，?(x,y)∈(A×A)滿足?σ=n1,…,nm，σ∈εP,ni=x,nj=y，?i,j∈{1,…,m}， 且i≠j.

定義6[7](日志的行為輪廓) 若LP=n1,…,nm是流程模型P=(A,ai,a0,C,F,T)的一個(gè)日志，對于?(x,y)∈(AL×AL)滿足：

1)若x?Ly且y?/Lx， 則稱x和y之間為嚴(yán)格序關(guān)系，記作x→Ly；

2)若x?Ly且y?Lx， 則稱x和y之間為交叉序關(guān)系，記作x‖Ly.

稱所有關(guān)系的集合為日志的行為輪廓，記作BL={→L,‖L}.

定義8[7](包容謂詞) 給定兩個(gè)行為關(guān)系R,R′∈{→,→-1,+,‖}， 當(dāng)R=R′和R=‖， (R∈{→,→-1}∧R′=+)中有一個(gè)成立時(shí)，則稱R和R′滿足包容謂詞關(guān)系，記作S(R,R′).

2 基于行為輪廓的網(wǎng)上購物挖掘算法

本文提出的基于Petri網(wǎng)行為輪廓的網(wǎng)上購物流程挖掘算法，首先通過分析事件日志的活動(dòng)關(guān)系確定行為輪廓關(guān)系，以此挖掘出一個(gè)初始的流程模型；然后測量流程模型與事件日志的服從程度，并將其與標(biāo)準(zhǔn)的服從程度值進(jìn)行對比，以此來判斷該流程模型是否需要進(jìn)一步優(yōu)化.

基于Petri網(wǎng)行為輪廓的網(wǎng)上購物流程挖掘算法的步驟如下：

輸入：事件日志，服從性閾值

輸出：網(wǎng)上購物Petri網(wǎng)模型

步驟1 對事件日志L={n1,n2,…,ni},i=1,2,…,k進(jìn)行預(yù)處理，按照發(fā)生頻數(shù)f(x)大小進(jìn)行排序.

步驟2 選擇發(fā)生頻數(shù)f(x)>M的幾條日志序列(M為經(jīng)驗(yàn)閾值)，然后根據(jù)日志序列中活動(dòng)間行為輪廓的弱序關(guān)系構(gòu)造序列活動(dòng)關(guān)系表.

步驟3 根據(jù)活動(dòng)關(guān)系表構(gòu)造活動(dòng)間行為輪廓表，然后利用行為輪廓表建立初始Petri網(wǎng)模型.

步驟4 根據(jù)行為輪廓計(jì)算事件日志與初始模型的服從性.以α為服從性的標(biāo)準(zhǔn)值，若服從性高于α， 則輸出模型；反之，返回到步驟2進(jìn)行模型優(yōu)化，且令步驟2中的M=M-N, 其中N為每次減小的步長.

步驟5 重復(fù)步驟4， 當(dāng)服從性大于α或M-N<0， 輸出模型.

3 實(shí)例分析

系統(tǒng)中發(fā)生的事件被記錄在日志中，它對理解系統(tǒng)的活動(dòng)至關(guān)重要，特別是在用戶交互較少的應(yīng)用程序中.由于事件日志包含事件的屬性較多，本文僅抽取事件中的活動(dòng)序列來挖掘網(wǎng)上購物流程.

本文以某app網(wǎng)上購物系統(tǒng)記錄的事件日志為例進(jìn)行挖掘.網(wǎng)上購物業(yè)務(wù)流程信息系統(tǒng)中日志處理后所包含的活動(dòng)P={A,B,C,D,E,F,G,H,I,J,K,L,Y}， 其中〈A,B,C,E,F,Y,G,I,L〉為事件日志中的一個(gè)發(fā)生序列.以下是該app處理過后的一個(gè)事件日志：

Φ=[〈A,B,C,E,F,Y,G,I,L〉80,〈A,B,C,E,F,Y,G,H,J,K,L〉56,〈A,B,D,E,F,Y,G,H,J,K,L〉33,〈A,B,C,E,F,Y,G,H,J,K,L〉20,〈A,B,C,E,Y,F,G,I,L〉63,〈A,B,D,E,Y,F,G,I,L〉43,〈A,B,D,E,G,I,L〉49]，

其中A,B,C,D,E,F,G,H,I,J,K,L,Y分別表示登錄、購買商品、在線支付、到付、下單、接單、發(fā)貨、因質(zhì)量拒貨、收貨、理賠、取消訂單、交易結(jié)束、略過.這個(gè)事件日志中包含7個(gè)不同的發(fā)生序列，每個(gè)序列發(fā)生的次數(shù)不同，序列的上標(biāo)表示發(fā)生次數(shù),例如〈A,B,C,E,F,Y,G,I,L〉80表示序列〈A,B,C,E,F,Y,G,I,L〉發(fā)生了80次.

下面利用本文提出的流程挖掘算法，對上述app給出的網(wǎng)上購物事件日志進(jìn)行挖掘，以此驗(yàn)證本文提出算法的可行性.

1)將所有的日志序列按照發(fā)生序列及發(fā)生次數(shù)進(jìn)行排序：{ABCEFYGIL(80)，ABCEYFGIL(63)，ABCEFYGHJKL(56)，ABDEGIL(49)，ABDEYFGIL(43)，ABDEFYGHJKL(33)，ABCEFYGHJKL(20)}.

當(dāng)經(jīng)驗(yàn)閾值M=45時(shí)，選擇發(fā)生次數(shù)大于等于45的序列建立活動(dòng)關(guān)系表，并計(jì)算各活動(dòng)間行為關(guān)系的個(gè)數(shù).表1為根據(jù)日志中活動(dòng)的行為輪廓建立的活動(dòng)關(guān)系表.

表1 活動(dòng)關(guān)系表

2)根據(jù)行為輪廓的定義，找出活動(dòng)間的行為關(guān)系，結(jié)果如表2所示.

表2 活動(dòng)間的輪廓關(guān)系表

3)根據(jù)表2列出的行為關(guān)系，結(jié)合Petri網(wǎng)的基礎(chǔ)結(jié)構(gòu)，構(gòu)造出初始模型Model_1，如圖1所示.

圖1 初始模型

4)計(jì)算服從程度.依據(jù)定義計(jì)算模型與日志之間的服從性，得εcLP=0.673.取α=0.95作為服從性的標(biāo)準(zhǔn)值[7]，因εcLP=0.673<0.95， 因此需要進(jìn)行優(yōu)化.重新選擇發(fā)生頻數(shù)M(M?M-N)， 其中取N=10.優(yōu)化后的模型如圖2所示.

5)計(jì)算優(yōu)化模型Model_2與日志的服從性，得εcLP=0.981. 該值表明，模型與事件日志具有較高的服從程度，符合要求，輸出模型.

4 結(jié)論

本文給出的基于Petri網(wǎng)行為輪廓的網(wǎng)上購物流程挖掘方法，不僅能夠清晰地表達(dá)活動(dòng)之間復(fù)雜的業(yè)務(wù)流程關(guān)系,而且能夠提高網(wǎng)上購物流程模型的運(yùn)行效率，具有一定的應(yīng)用價(jià)值.在流程挖掘過程中，本文僅對出現(xiàn)在執(zhí)行日志中的活動(dòng)進(jìn)行了研究，但在實(shí)際執(zhí)行過程中有些活動(dòng)可能被隱藏或者被堵塞，即存在隱藏變遷和阻塞變遷等問題，因此今后將探討隱藏變遷和阻塞變遷的問題，以提高本文方法的有效性.