基于Petri網行為輪廓的網上購物流程挖掘方法

王倩倩， 王麗麗

( 安徽理工大學 數學與大數據學院， 安徽 淮南 232001 )

0 引言

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

1 基本概念

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

1)A是活動節(jié)點,A≠?；C是控制節(jié)點，C≠?.

2)ai,a0∈A，ai是起始活動，a0是結束活動.

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

4)T:C{and,or,xor}是關于控制節(jié)點類型的函數.

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

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

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

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

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

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

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

1)共現關系?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)的一個日志，對于?(x,y)∈(AL×AL)滿足：

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

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

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

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

2 基于行為輪廓的網上購物挖掘算法

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

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

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

輸出：網上購物Petri網模型

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

步驟2 選擇發(fā)生頻數f(x)>M的幾條日志序列(M為經驗閾值)，然后根據日志序列中活動間行為輪廓的弱序關系構造序列活動關系表.

步驟3 根據活動關系表構造活動間行為輪廓表，然后利用行為輪廓表建立初始Petri網模型.

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

步驟5 重復步驟4， 當服從性大于α或M-N<0， 輸出模型.

3 實例分析

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

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

Φ=[〈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ā)貨、因質量拒貨、收貨、理賠、取消訂單、交易結束、略過.這個事件日志中包含7個不同的發(fā)生序列，每個序列發(fā)生的次數不同，序列的上標表示發(fā)生次數,例如〈A,B,C,E,F,Y,G,I,L〉80表示序列〈A,B,C,E,F,Y,G,I,L〉發(fā)生了80次.

下面利用本文提出的流程挖掘算法，對上述app給出的網上購物事件日志進行挖掘，以此驗證本文提出算法的可行性.

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

當經驗閾值M=45時，選擇發(fā)生次數大于等于45的序列建立活動關系表，并計算各活動間行為關系的個數.表1為根據日志中活動的行為輪廓建立的活動關系表.

表1 活動關系表

2)根據行為輪廓的定義，找出活動間的行為關系，結果如表2所示.

表2 活動間的輪廓關系表

3)根據表2列出的行為關系，結合Petri網的基礎結構，構造出初始模型Model_1，如圖1所示.

圖1 初始模型

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

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

4 結論

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