基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為挖掘與優(yōu)化分析

郝惠晶，方賢文，方 娜，許 健

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

0 引言

在實際應(yīng)用中，從信息系統(tǒng)中提取的事件日志不可避免地包含低頻行為，這些低頻行為由于發(fā)生頻數(shù)較低往往被作為無序事件、記錄錯誤、異常行為或者噪音而被刪除。然而,有些低頻行為雖然出現(xiàn)頻率較低，但是對流程管理也很重要，不能直接過濾，例如，飛機的逃逸系統(tǒng)、保險公司的欺詐性索賠，由此可見，低頻行為的挖掘具有重要意義。

目前，針對低頻行為的挖掘已經(jīng)成為學(xué)者專家研究的熱門課題，并有了一定的研究成果。文獻[1]提出一個從日志中移除低頻行為的自動技術(shù)，該技術(shù)自動識別所有的行為并移除低頻行為。文獻[2]中提出了區(qū)分噪音與流程的規(guī)則行為的噪音過濾方法。文獻[3-4]提出在過程發(fā)現(xiàn)中處理包含噪音的事件日志是一個重大挑戰(zhàn)。文獻[5]提出一種利用數(shù)據(jù)屬性來區(qū)分低頻路徑和隨機噪聲的啟發(fā)式挖掘算法(Data-aware Heuristic Miner, DHM)。文獻[6]提出了增廣因果網(wǎng)，它能用于一致性檢測，也能在有噪音和真實日志的復(fù)雜和低結(jié)構(gòu)化過程中得到例證。文獻[7]提出一種新的基于頻率的流程挖掘方法來過濾噪音。文獻[8]提出一種Inductive Miner-infrequent技術(shù)，該技術(shù)選擇切操作來拆分日志，并過濾低頻行為，且該技術(shù)已在ProM中實施。文獻[9]提出WoMine-i算法，是一種在已經(jīng)發(fā)現(xiàn)的過程模型中不僅能搜索不常見的行為模式，還能發(fā)現(xiàn)具有最常見控制結(jié)構(gòu)模式的算法，該結(jié)構(gòu)允許執(zhí)行的子進程能夠發(fā)現(xiàn)少于預(yù)期的或不常見的錯誤行為。文獻[10]提出一種最大模式挖掘(Maximal Pattern Mining, MPM)的新技術(shù)，用于從事件日志中發(fā)現(xiàn)過程模型，該技術(shù)在召回、精度、F-測量、運行效率等方面表現(xiàn)良好，并進而基于頻率提出了噪音過濾的方法。

本文以模塊間的通訊行為輪廓為基礎(chǔ)，通過預(yù)處理事件日志挖掘初始流程模型，用帶切關(guān)系的直接流圖與初始模型進行匹配，發(fā)現(xiàn)低頻行為。考慮事件日志間的行為屬性，基于日志與模型的行為緊密度區(qū)分有效低頻日志和噪音日志，過濾噪音。并通過不同模塊間的通訊特征挖出模塊網(wǎng)和特征網(wǎng)，將模塊網(wǎng)和特征網(wǎng)進行交互通訊，得到一個優(yōu)化的業(yè)務(wù)流程通訊模型。

1 基本概念

定義1[11]通訊行為輪廓。設(shè)L?T*是事件日志，L?T×T是相應(yīng)的通訊后繼關(guān)系。通訊行為輪廓是一個3元數(shù)組(→C,‖C,+C)Com，它由以下關(guān)系組成：

(1)嚴(yán)格通訊關(guān)系A(chǔ)→CB，當(dāng)且僅當(dāng)ALB，BLA；

(2)交叉通訊關(guān)系A(chǔ)‖CB，當(dāng)且僅當(dāng)ALB，BLA；

(3)排它通訊關(guān)系A(chǔ)+CB，當(dāng)且僅當(dāng)ALB，BLA；

(4)逆嚴(yán)格通訊關(guān)系A(chǔ)←CB，當(dāng)且僅當(dāng)ALB，BLA。

定義2[12]流程樹切(日志)。設(shè)Li(i=1,2,…,n)為流程模型CP=(S,T,F,c)對應(yīng)的事件日志，S(T)為關(guān)于變遷T的跡，L∈S(T)，c∈S∪T，若變遷?x,y∈c:((x,y?F+)∧(y,x?F+))，其中F+為流關(guān)系F的傳遞閉包，則c為流程樹切，對于任意一個活動(x,y)∈Li×Li，存在日志序列δ=t1t2…tn，其中i,j∈{1,2,…,n}，i

(1)x?y，當(dāng)且僅當(dāng)?δ∈L?ti=x，tj=y；

(2)x→y，當(dāng)且僅當(dāng)x?y,yx；

(3)xy，當(dāng)且僅當(dāng)xy,yx；

(4)x‖y，當(dāng)且僅當(dāng)x?y,y?x；

(5)xy，當(dāng)且僅當(dāng)?δ∈L,?x,y∈T?(x∈δ,y?δ)∨(y∈δ,x?δ)。

其中：x?y表示活動對間的弱序關(guān)系，x→y表示活動對間的因果關(guān)系，xy表示活動對間無關(guān)系，x‖y表示活動對間平行交叉關(guān)系，xy表示活動對間的互斥關(guān)系。

事件日志L：[a,b,c,a,b,e,f50,(a,b,f,e)100,d,e,f100,d,f,e100]，將日志L劃分為一些子日志：L1=[a,b,c,a,b50,a,b100,d200]，L2=[e,f150,f,e200]，L3=[a,b,c,a,b50,a,b100]。

圖1中虛線為切，圖1a日志L1是關(guān)于弱序流程樹切圖；圖1b日志L2是關(guān)于互斥流程樹切圖；圖1c日志L3是關(guān)于交叉流程樹切圖；圖1d日志L4是關(guān)于循環(huán)流程樹切圖。

定義4[14]日志距離向量。設(shè)一條事件日志T={t1,t2,…,tn}，其中?(t1,t2)∈T，?(pi,pi+1)∈ti的日志行為值為VT(pi,pi+1)，且VT(pi,pi+1)=1。日志的行為距離向量為：X={VT(p1,p2),VT(p2,p3),…,VT(pi,pi+1),…,VT(pj,pm)}={l1,l2,…li,…,lm}。類似地，可以定義模型的行為值為VM(pi,pi+1)=k。模型的行為距離向量定義為：X={VM(p1,p2),VM(p2,p3),…,VM(pi,pi+1),…,VM(pj,pm)}={k1,k2,…ki,…,km}。

其中：m表示變遷個數(shù)，且0

定義5[11]特征網(wǎng)。設(shè)L?T*是一個事件日志，A,F∈T是特征。設(shè)(→C,‖C,+C)Com相應(yīng)的通訊行為輪廓，特征網(wǎng)ΝF滿足以下條件：

(2)I={pA-F|A→F}；

(3)O={pF-A|F→A}；

2 基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為挖掘與優(yōu)化分析

一般情況下，從信息系統(tǒng)中獲取的事件日志往往包含低頻行為，這些行為通常被認(rèn)為是噪音而被直接刪除，而發(fā)現(xiàn)的業(yè)務(wù)流程模型因此會失去一些有用的規(guī)則行為。本文主要介紹了基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為挖掘與優(yōu)化分析的方法，并提出了相關(guān)的算法，通過基于帶切關(guān)系的直接流圖及行為緊密度對低頻行為進行挖掘與優(yōu)化，并通過分析模塊間的通訊特征，更好地優(yōu)化業(yè)務(wù)流程模型，從而更好地應(yīng)用于實際生活。

2.1 基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為的挖掘方法

在過程挖掘中，已有研究大多集中在發(fā)現(xiàn)頻繁行為，少有涉及低頻行為，且很少從行為關(guān)系角度考慮低頻行為。許多算法的提出基本是以事件日志記錄業(yè)務(wù)過程的完整行為為基礎(chǔ)，進而挖掘業(yè)務(wù)流程模型。但是事件日志中往往存在異常或者偏差，即噪音，噪音的存在會影響業(yè)務(wù)流程的結(jié)構(gòu)。運用流程樹切的行為關(guān)系匹配初始模型挖掘低頻行為，基于日志與模型的行為距離向量計算日志與模型的行為緊密度，根據(jù)緊密度閾值區(qū)分低頻行為和噪音，從而對低頻行為進行挖掘與優(yōu)化。下面首先給出行為緊密度的定義。

定義6[12]行為緊密度。給出事件日志T和流程模型M，則日志T與模型M的行為緊密度

其中，m表示日志中的活動行為關(guān)系數(shù)，ki為模型中與日志對應(yīng)變遷的最小行為距離，li為日志行為距離。

算法1基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為挖掘方法。

輸入：事件日志L={τ1,τ2,…,τn}，緊密度閾值θ；

輸出：低頻行為。

步驟1預(yù)處理給定的事件日志L={τ1,τ2,…,τn}，分析各個變遷對ti,tj之間的行為輪廓關(guān)系，按照實例數(shù)大小從大到小排列事件日志，找到頻數(shù)發(fā)生較高的日志序列，建立初始的Petri網(wǎng)流程模型M0，轉(zhuǎn)步驟2。

步驟2根據(jù)定義2，對給定的事件日志用流程樹切進行劃分，將事件日志中活動對的關(guān)系用帶切關(guān)系的直接流圖表示出來，將直接流圖的序列關(guān)系與初始流程模型M0的序列關(guān)系進行匹配，找出所有無匹配項的直接流圖的序列關(guān)系，即為該事件日志中所包含的低頻行為，轉(zhuǎn)步驟3。

步驟4根據(jù)定義6，求出日志與模型行為緊密度的值，根據(jù)給定的緊密度閾值θ，如果緊密度值ξ(Ti,M)≥θ，則該低頻日志為有效低頻日志，如果ξ(Ti,M)<θ，則該日志為噪音日志，轉(zhuǎn)步驟5。

步驟5過濾噪音日志，過濾掉該流程樹切的運算符和切口選擇，即過濾直接流圖和最終跟隨圖的低頻序列，算法結(jié)束。

2.2 基于通訊行為輪廓的低頻行為的優(yōu)化分析

由上述研究可知，挖掘發(fā)現(xiàn)的非頻繁的行為并不都是異常行為，有的可能是對系統(tǒng)有用的有效低頻，為了提高系統(tǒng)或企業(yè)的運行效率，應(yīng)將有效低頻保留下來。但已有關(guān)于低頻行為的研究主要是基于完整的流程模型，對通過不同模塊間通訊特征挖掘低頻行為的研究還很少。本節(jié)提出一個新的低頻行為的優(yōu)化算法，具體算法如下。

算法2基于通訊行為輪廓的低頻行為挖掘與優(yōu)化。

輸入：事件日志L={τ1,τ2,…,τn}，緊密度閾值θ;

輸出：優(yōu)化的業(yè)務(wù)流程模型。

步驟1根據(jù)算法1建立的初始Petri網(wǎng)流程模型M0，預(yù)處理其給定的事件日志L={τ1,τ2,…,τn}，n=1,2,3,…，轉(zhuǎn)步驟2。

步驟2將預(yù)處理后的事件日志L′={τ1,τ2,…,τm}(m

步驟3根據(jù)處理后的事件日志及通訊行為輪廓關(guān)系，將系統(tǒng)分解為不同的模塊，構(gòu)建相應(yīng)的模塊網(wǎng)M1,M2,…，轉(zhuǎn)步驟4。

步驟5將步驟4和步驟5挖掘得到的模塊網(wǎng)M1,M2,…和特征網(wǎng)MF進行進行融合，進而得到優(yōu)化的業(yè)務(wù)流程模型，算法結(jié)束。

3 實例分析及仿真實驗

3.1 實例分析

為驗證上述算法的可行性，以網(wǎng)絡(luò)訂購火車票為例，用戶首先需要注冊并登錄官網(wǎng)，登陸成功以后進入車票預(yù)訂界面，依次選擇乘車區(qū)間及日期，然后選擇車次進行車票預(yù)訂、付款、改簽或者退票等流程。下面給出一些基于網(wǎng)絡(luò)購票系統(tǒng)所記錄的事件日志(如表1)。其中：t11表示注冊，t12表示登錄，t13表示選擇乘車區(qū)間，t14表示選擇乘車日期，t15表示選擇車次，t16表示余票查詢，t17表示車票預(yù)訂，t18表示付款，t19表示訂票成功，t1，10表示改簽，t1，11表示取票，t1，12表示退票。t21表示登錄成功，t22表示登錄失敗，t23表示余票信息，t24表示余票充足，t25表示余票不足，t26表示返回車次選擇，t27表示重新登錄，t28表示付款信息，t29表示付款成功，t2，10表示待付款，t2，11表示付款時間超過30 min，t2，12表示交易關(guān)閉，t2，13表示付款時間在30 min以內(nèi)。

表1 網(wǎng)絡(luò)購票系統(tǒng)的事件日志

對表1給定的事件日志用流程樹切進行劃分，通過與圖2的初始流程模型進行匹配，可發(fā)現(xiàn)日志L9：t11t12t22t12t2,1214，L10：t11t12t21t13t14t15t16t23t1745，L11：t21t16t23t25t1，12t2,1226，L12：t24t17t18t28t2,1251，L13：t13t14t21t15t16t23t24t1,127與初始模型不匹配，而初始模型由頻數(shù)相對較高的日志構(gòu)建，因此視這些事件日志為低頻日志。然后，判斷低頻日志是有效低頻日志還是噪音日志，利用定義4計算低頻日志與模型的行為緊密度，日志L9的行為距離向量為X1=(1,1,1,1)，與初始模型M0對應(yīng)變遷的最小行為距離向量為日志L9與初始模型M0的行為緊密度為同理，日志L10與初始模型M0的行為緊密度為σ2≈0.959 4，日志L11與初始模型M0的行為緊密度為σ3≈0.650 8，日志L12與初始模型M0的行為緊密度為σ4≈0.866，日志L13與初始模型M0的行為緊密度為σ5≈0.699 9。引入行為緊密度閾值為0.8，當(dāng)日志與模型的行為緊密度大于閾值時，說明低頻日志符合模型的行為關(guān)系，視為有效低頻日志，應(yīng)當(dāng)保留；當(dāng)小于閾值時，說明低頻日志與模型的行為關(guān)系不符，視為噪音日志，應(yīng)當(dāng)過濾。

由上述行為緊密度值與閾值比較的結(jié)果可知，事件日志L9，L11和L13的行為緊密度小于閾值，視為噪音日志，其中L9：t11t12t22t12t2,1214劃分為一些子日志，分別為：[t11t12t22t121 034，t12t2,1214]，其中流弧t12t2,12是低頻的，觀察流程樹切的直接流圖，用啟發(fā)式過濾的方法過濾流弧t12t2,12，因此含有流弧t12t2,12的事件日志也應(yīng)當(dāng)過濾。同理，L11和L13通過過濾直接流圖的低頻序列，進而過濾含有此低頻序列的事件日志，而事件日志L10和L12為有效低頻日志，需保留在事件軌跡集中。

通過優(yōu)化事件軌跡集，根據(jù)日志之間的變遷對的關(guān)系，分析各個活動事件之間的行為關(guān)系，建立通訊行為輪廓表，如表2所示。基于域的方法與優(yōu)化事件軌跡集挖掘出兩個模塊網(wǎng)，如圖3所示，不同模塊之間存在交互行為，且事件之間的特征不僅能接受信息,還能傳遞信息，重構(gòu)事件之間的內(nèi)部行為，找出相應(yīng)的特征網(wǎng)，如圖4所示。分析可知，模塊網(wǎng)可反映模塊內(nèi)部行為，特征網(wǎng)可反映不同模塊之間的特征交互，故將模塊網(wǎng)與特征網(wǎng)融合可得到優(yōu)化的業(yè)務(wù)流程模型，如圖5所示。

表2 通訊行為輪廓關(guān)系

續(xù)表2

3.2 仿真分析

為驗證本文所提基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為的挖掘與優(yōu)化算法的有效性，將本文提出的基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為挖掘與優(yōu)化的新方法與文獻[8]提出的方法進行比較分析，對模型的一致性度(見文獻[15])和精確度(見文獻[16])進行比較。一致性度是指事件日志與業(yè)務(wù)流程行為相匹配的程度，而一個模型精確度高說明流程模型中無過多的行為。關(guān)于一致性度、精確度和運行時間的具體實驗結(jié)果如圖6a～圖6c所示。

分析圖6a可知，兩種算法的一致性度比較接近，且都接近1，說明本文的過濾算法和文獻[8]中基于切操作的過濾算法挖掘出的流程模型與日志行為之間具有很好的匹配度，但本文的過濾算法相較于文獻[8]的算法一致性度要高一些，說明本文的挖掘算法可基于事件日志挖掘出更有效的流程模型，且受日志的數(shù)量影響較小。

分析圖6b可知，本文的過濾方法相較于文獻[8]的過濾方法，精確度明顯要高，說明本文只過濾對系統(tǒng)造成影響的噪音序列；而文獻[8]的過濾方法將所有低頻行為和噪音全部過濾，因此過濾了很多活動，導(dǎo)致精確度明顯較低。

分析圖6c可知，兩種方法在挖掘流程模型的過程中，系統(tǒng)運行時間隨事件日志數(shù)量的增長而快速增加，且相同日志數(shù)下本文的過濾方法所需運行時間相較于文獻[8]的運行時間較長，但兩者整體運行時間相差不大，且對于挖掘流程模型沒有影響。

由以上分析可知，本文提出的方法在一致性度和精確度方面相較于以前的方法提高了很多，雖然運行時間稍微比之前方法較長，但本文的過濾方法只過濾掉噪音，保留了對系統(tǒng)有用的低頻行為，達到了優(yōu)化系統(tǒng)的目的。

4 結(jié)束語

本文在已有研究的基礎(chǔ)上，給出了基于Petri網(wǎng)的業(yè)務(wù)流程低頻行為挖掘與優(yōu)化的方法。首先基于流程樹切的基本流圖與初始模型進行匹配，不僅能區(qū)分頻繁行為和低頻行為，通過行為緊密度的知識還能區(qū)分有效低頻與噪音序列，從而過濾噪音日志，優(yōu)化事件軌跡集；然后分析了事件對之間的行為關(guān)系，建立了模塊網(wǎng)和特征網(wǎng)，從而解決了不同模塊間低頻行為的挖掘問題，融合了模塊網(wǎng)和特征網(wǎng)，可以得到一個優(yōu)化的業(yè)務(wù)流程模型，從而提升了企業(yè)或組織的運行效率。

本文所提方法是從行為關(guān)系的角度區(qū)分有效低頻行為和噪音行為，未來還要將行為屬性和數(shù)據(jù)屬性相結(jié)合來區(qū)分低頻行為，從而更好地過濾噪音，優(yōu)化系統(tǒng)。