基于擬間接依賴的流程挖掘優(yōu)化分析

曹 蕊，方賢文，王麗麗

CAO Rui,FANG Xianwen,WANG Lili

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

College of Mathematics and Big Data,Anhui University of Science and Technology,Huainan,Anhui 232001,China

1 引言

隨著信息技術(shù)的快速發(fā)展，業(yè)務(wù)流程管理占據(jù)著舉足輕重的作用。業(yè)務(wù)流程挖掘優(yōu)化作為業(yè)務(wù)流程管理的核心內(nèi)容之一，對(duì)流程挖掘優(yōu)化方面進(jìn)行深入的研究顯得至關(guān)重要。因此，先以行為輪廓為基礎(chǔ)，得到初始模型，然后通過(guò)執(zhí)行日志，運(yùn)用基于整數(shù)線性規(guī)劃算法的約束條件集找出具有擬間接依賴關(guān)系的變遷對(duì)并對(duì)初始模型進(jìn)行調(diào)整，最后，挖掘出符合需求的業(yè)務(wù)流程模型。

目前，關(guān)于流程挖掘的研究已做了相當(dāng)多的工作。文獻(xiàn)[1]研究了流程發(fā)現(xiàn)技術(shù)的應(yīng)用從場(chǎng)景中去發(fā)現(xiàn)各個(gè)成分的內(nèi)部行為。在事件日志的基礎(chǔ)上，提出了一種方法：（1）導(dǎo)出特征間的信息流，（2）確認(rèn)特征的內(nèi)部行為，（3）發(fā)現(xiàn)模塊內(nèi)的特征的順序。對(duì)于每一個(gè)模塊，使用該方法得到一個(gè)合理的工作流模型。文獻(xiàn)[2]中的流程發(fā)現(xiàn)旨在從給定事件日志中更好地獲取描述流程模型的行為，然而不頻繁行為的存在影響獲取模型的精確性。通過(guò)Inductive Miner，利用切操作過(guò)濾不頻繁行為，挖掘得到合理的流程模型。把該方法和現(xiàn)有的挖掘方法在質(zhì)量和性能方面作對(duì)比，說(shuō)明該方法的有效性。文獻(xiàn)[3]中描述從不完備的事件日志中發(fā)現(xiàn)流程模型結(jié)構(gòu)，分析不完備日志對(duì)過(guò)程發(fā)現(xiàn)的影響，引入概率行為關(guān)系，利用這些關(guān)系處理不完備日志，給出一個(gè)基于這些概率關(guān)系的算法，用作重新發(fā)現(xiàn)流程模型語(yǔ)言。文獻(xiàn)[4]考慮在間接繼承的基礎(chǔ)上，把日志作為輸入，利用矩陣表示日志的可達(dá)到關(guān)系，順序、排他、循環(huán)、平行，把日志分離成子日志，不斷迭代，自動(dòng)發(fā)現(xiàn)流程模型塊結(jié)構(gòu)。文獻(xiàn)[5]提出了一種基于定位事件日志的通用的過(guò)程發(fā)現(xiàn)方法。該方法已在ProM和實(shí)驗(yàn)結(jié)果表明，位置信息確實(shí)有助于提高發(fā)現(xiàn)模型的質(zhì)量。文獻(xiàn)[6]提出了一種通用的流程挖掘框架預(yù)測(cè)、關(guān)聯(lián)和聚集基于事件日志的動(dòng)態(tài)行為。文獻(xiàn)[7]提出了一種可構(gòu)成的方法，從事件日志中發(fā)現(xiàn)塊結(jié)構(gòu)的流程模型。文獻(xiàn)[8]提出了基于不同程度信息進(jìn)行隊(duì)列挖掘。文獻(xiàn)[9]利用整數(shù)線性規(guī)劃的方法挖掘業(yè)務(wù)流程模型。

考慮事件間的擬間接依賴關(guān)系能有效提高業(yè)務(wù)流程挖掘的效果，但目前相關(guān)研究比較少，文獻(xiàn)[10]開(kāi)展了相關(guān)研究，給出了一個(gè)基于擬間接依賴關(guān)系的挖掘方法，但是在查找其行為方面具有一定的難度，基于此，本文提出了基于擬間接依賴的流程挖掘優(yōu)化分析的新方法。該方法以Petri網(wǎng)的行為輪廓理論為基礎(chǔ)，建立初始模型。通過(guò)基于整數(shù)線性規(guī)劃的約束條件找出具有擬間接依賴的變遷（事件）對(duì)，并對(duì)初始模型進(jìn)行調(diào)整。最后挖掘出符合需求的業(yè)務(wù)流程模型。

2 基本概念

這一部分給出本文所需要的基本概念，首先給出Petri網(wǎng)的形式化定義。

定義1[11]（Petri網(wǎng)）一個(gè)Petri網(wǎng)PN=(P,T,F)是一個(gè)三元組，滿足以下條件：

（1）P是有限庫(kù)所集，T是有限變遷集。

（3）F=(P×T)?(T×P）表示PN 的流關(guān)系。

在Petri網(wǎng)PN中存在一種弱序關(guān)系，即包含T×T所有的變遷對(duì)(x,y)中存在一個(gè)發(fā)生序列δ=t1t2…tn，當(dāng)i∈{1,2,…,n-1}時(shí)，i＜j≤n有ti=x且tj=y,x?y，依據(jù)這種弱序關(guān)系定義了行為輪廓。

定義2[12]（Petri網(wǎng)的行為輪廓）PN=(P,T,F)是一個(gè)Petri網(wǎng)，對(duì)任意的變遷對(duì)(x,y)∈(T×T)，滿足下列關(guān)系之一：

則以上幾種行為關(guān)系構(gòu)成Petri網(wǎng)的行為輪廓。

定義3[13]（事件日志）T是任務(wù)集，σ∈T*是一個(gè)執(zhí)行集，L∈Ρ(T*)是一個(gè)事件日志。Ρ(T?)是T?的冪集，L?T*。

定義4[14]（前綴閉包）設(shè)L=[＜ABC…XYZ＞1002,＜ACB…YXZ＞1262,…,＜ABC…ZXY＞1232]是事件日志，A,B,C,…,Y,Z均是事件即任務(wù)，則L的前綴閉包是={ε,＜A＞,＜AB＞,＜AC＞,＜ABC＞,＜ACB＞,…,＜ABC…XYZ＞,＜ACB…YXZ＞,…,＜ABC…ZXY＞}，其中，ε是空序列。

3 基于擬間接依賴的流程挖掘優(yōu)化分析方法

3.1 事件間擬間接依賴關(guān)系

任何一個(gè)業(yè)務(wù)流程模型的兩個(gè)事件間都存在兩種因果依賴關(guān)系：直接依賴關(guān)系和間接依賴關(guān)系。如果僅僅考慮事件之間的直接因果關(guān)系，不能夠準(zhǔn)確地從事件日志中挖出業(yè)務(wù)流程來(lái)滿足組織或者企業(yè)的需求，因此，還需要查找出事件之間的間接依賴關(guān)系。事件之間擬間接依賴關(guān)系的概念如定義5所示。

定義5（擬間接依賴關(guān)系）T是事件集（任務(wù)集），L∈Ρ(T*)是事件日志，Lˉ是事件日志L的前綴閉包，設(shè)t1,t2∈T是T中的兩個(gè)事件（Petri網(wǎng)模型的兩個(gè)變遷），t1,t2之間具有擬間接依賴關(guān)系，記作t1∝t2，當(dāng)且僅當(dāng)不等式組，n∈{1,2,3,…}成立。

其中，對(duì)于L的前綴閉包Lˉ中的每一條執(zhí)行的事件日志，xi(t1),yi(t2)的值可能不同，當(dāng)t1發(fā)生時(shí)，xi(t1)是兩個(gè)事件（變遷對(duì)）之間的庫(kù)所的輸入弧數(shù)目，當(dāng)t2發(fā)生時(shí)，yi(t2)是兩個(gè)事件（變遷對(duì)）之間的庫(kù)所的輸出弧的數(shù)目，i∈{1,2,…,n}，n∈{1,2,3,…}。

從事件之間擬間接依賴關(guān)系的定義可知，t1∝t2，稱t1與t2滿足擬間接依賴關(guān)系，即t2對(duì)于t1有依賴關(guān)系，通俗地說(shuō)，t2是否發(fā)生取決于t1。由此可知，t1與t2之間存在著一個(gè)庫(kù)所，使t1與t2之間形成另一條通路，這個(gè)庫(kù)所的存在保證了t1與t2之間的擬間接依賴關(guān)系。具體的擬間接依賴關(guān)系可以參考圖1，圖中的變遷對(duì)A與C之間存在庫(kù)所p1，B與D之間存在庫(kù)所p2，A與C之間以及B與D之間均具有擬間接依賴關(guān)系。

圖1 擬間接依賴關(guān)系的Petri網(wǎng)模型

3.2 基于擬間接依賴的流程挖掘優(yōu)化分析算法

對(duì)于基于整數(shù)線性規(guī)劃流程發(fā)現(xiàn)算法的基本約束體，由于每條執(zhí)行日志不同，則一個(gè)庫(kù)所前后變遷t1,t2發(fā)生的 xi(t1)，yi(t2）的值不同，i∈{1,2,…,n}，n∈{1,2,3,…}，則對(duì)應(yīng)的線性不等式 xi(t1)+yi(t2)≥0(i∈{1,2,…,n}，n∈{1,2,3,…})也不一樣。若每個(gè)線性不等式的右邊部分大于等于零即不等式組成立，則該庫(kù)所可以添加到流程模型中的這兩個(gè)變遷t1,t2之間且t1,t2具有擬間接依賴性關(guān)系，這樣就挖掘出了兩個(gè)變遷的擬間接依賴關(guān)系（文中的事件集以Petri網(wǎng)的變遷集為例）。

Petri網(wǎng)的業(yè)務(wù)流程模型的變遷間除了具有直接依賴關(guān)系外，還往往具有間接依賴關(guān)系。如果僅僅從記錄事件日志中挖掘出只含有直接依賴關(guān)系的流程模型，該模型并不能有效地?cái)M合日志中的行為。因此，挖掘含有擬間接依賴關(guān)系的業(yè)務(wù)流程模型具有重要的意義。

有關(guān)業(yè)務(wù)流程挖掘的研究已做了相當(dāng)多的工作。其中，α算法能夠從事件日志中挖掘出合理的模型，但是，當(dāng)涉及到挖掘特殊的流程模式（例如擬間接依賴關(guān)系）時(shí)，它具有很大的局限性。基于此，提出了基于整數(shù)線性規(guī)劃流程發(fā)現(xiàn)算法的基本約束條件集找出流程模型中的具有擬間接依賴關(guān)系的變遷對(duì)，并且接受該變遷對(duì)間的庫(kù)所，最終挖掘出流程模型中的擬間接依賴關(guān)系。

本文提出的基于擬間接依賴的流程挖掘優(yōu)化分析的算法是以事件日志的行為輪廓關(guān)系為基礎(chǔ)，首先分析事件日志的行為輪廓，根據(jù)行為輪廓關(guān)系建立初始模型。然后找出具有擬間接依賴的變遷對(duì)，并在執(zhí)行具有擬間接依賴的變遷對(duì)的日志下，建立基于整數(shù)線性規(guī)劃流程發(fā)現(xiàn)算法的基本約束表，通過(guò)不等式的成立來(lái)驗(yàn)證具有擬間接依賴的變遷對(duì)之間的庫(kù)所的存在性。最后，得出符合需要的業(yè)務(wù)流程模型。具體的算法如算法1所示。

算法1基于擬間接依賴的流程挖掘優(yōu)化

輸入：事件日志

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

步驟1處理所有提取到的事件日志L，按照實(shí)例數(shù)從大到小排列日志，例如 {τ1,τ2,…,τn}，n∈{1,2,3,…}，τ1,τ2,…,τn∈L 。

步驟2根據(jù)定義，遍歷每個(gè)事件日志，計(jì)算出事件日志的行為輪廓關(guān)系即各個(gè)變遷對(duì)t1,t2（其中t1,t2∈L）的行為輪廓關(guān)系，得出行為輪廓關(guān)系表（這里僅給出主要的關(guān)系，即→，+，‖），然后建立初始Petri網(wǎng)模型M0。

步驟3在初始模型M0的基礎(chǔ)上，找出預(yù)擬間接依賴關(guān)系的變遷對(duì)t1,t2，t1是該庫(kù)所前變遷，t2是該庫(kù)所后變遷，然后執(zhí)行含有此變遷對(duì)的跡，得到執(zhí)行日志，建立執(zhí)行日志表格。

步驟4對(duì)于由步驟3得到的執(zhí)行日志，求出其前綴閉包Lˉ，即執(zhí)行日志的子日志集。根據(jù)子日志集，找出基于整數(shù)線性規(guī)劃的流程發(fā)現(xiàn)算法的基本約束條件體C1,C2,…,Cn，其中n∈{1,2,3,…}。計(jì)算預(yù)擬間接依賴關(guān)系的變遷對(duì)間的庫(kù)所的輸入弧和輸出弧的數(shù)目（分別記為x(t1)，y(t2)其中，t1是該庫(kù)所前變遷，t2是該庫(kù)所后變遷）。然后建立約束體表格，轉(zhuǎn)入步驟5。

步驟5根據(jù)步驟4中的約束體表格，可知對(duì)于不同的執(zhí)行的日志，計(jì)算得到的x(t1)，y(t2)可能不同。為此，對(duì)于每一條日志，得到不同的約束條件Ci,i∈{1,2,…,n}，n∈{1,2,3,…}，變遷對(duì)之間的庫(kù)所的輸入弧和輸出弧的數(shù)目分別記作 xi(t1),yi(t2),i∈{1,2,…,n}，n∈{1,2,3,…}。然后計(jì)算不等式組若不等式組成立，則該庫(kù)所被該模型接受，且與該庫(kù)所直接連著的變遷對(duì)具有擬間接依賴關(guān)系。否則，該庫(kù)所被拒絕。執(zhí)行步驟6。

步驟6步驟5中得到的被接受的庫(kù)所則保留在該模型中。即挖掘出符合需求的模型，最后，輸出最終符合需求的Petri網(wǎng)優(yōu)化模型M1。

4 實(shí)例分析

為了驗(yàn)證上述算法的可行性，給出簡(jiǎn)單的實(shí)例，即衣服購(gòu)買業(yè)務(wù)流程。記錄的事件日志包括以下事件，分別用大寫(xiě)英文字母表示，其中，（A）顧客存包、（B）進(jìn)入商場(chǎng)、（C）挑選衣服、（D）完成挑選、（E）新顧客選擇支付方式、（F）老顧客選擇支付方式、（H）刷 VIP卡、（I）銀行卡支付、（J）走出商場(chǎng)。具體的事件日志如表1所示。

表1 事件日志L

首先將事件軌跡按照實(shí)例數(shù)從大到小排列，結(jié)果為 ：{ABCDEGIJ（2017），ABCDKCDFGHJ（2015），ACBDKCDKCDFGHJ（2013），ACBDFGHJ（2000），ABCDKCDKCDEGIJ（1997），ABCDKCDKCDKCJ（256），ACBDJ（157）}，依次記為 τ1，τ2，τ3，τ4，τ5，τ6，τ7。根據(jù)這些日志的行為輪廓關(guān)系，建立行為輪廓關(guān)系表，如表2所示。

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

根據(jù)事件日志的行為輪廓關(guān)系，可以得到衣服購(gòu)買的初始Petri網(wǎng)模型M0，如圖2所示。

圖2 初始模型M0

從初始模型M0中可以發(fā)現(xiàn)變遷對(duì)F和H，E和I具有預(yù)擬間接依賴關(guān)系，執(zhí)行含有該變遷對(duì)的序列，可以得到執(zhí)行日志，見(jiàn)表3。

表3 執(zhí)行日志

表4 約束體表

圖3 具有擬間接依賴關(guān)系的優(yōu)化模型M1

對(duì)于上述實(shí)例，如果用α算法可以從事件日志中挖掘出合理的初始模型M0，但變遷對(duì)F和H以及變遷對(duì)E和I的擬間接依賴關(guān)系被忽視。而通過(guò)基于整數(shù)線性規(guī)劃流程發(fā)現(xiàn)算法的基本約束條件集可以找出F和H以及E和I的擬間接依賴關(guān)系，從而得到符合需求的業(yè)務(wù)流程模型。

5 結(jié)束語(yǔ)

本文在現(xiàn)有研究的基礎(chǔ)上，給出了基于擬間接依賴的流程挖掘優(yōu)化分析方法。在事件日志下，找出各個(gè)任務(wù)即事件的行為輪廓關(guān)系，建立初始模型。通過(guò)基于整數(shù)線性規(guī)劃流程發(fā)現(xiàn)算法的基本約束條件找到被初始模型接受的庫(kù)所，則該庫(kù)所前后兩個(gè)變遷具有擬間接依賴關(guān)系，該庫(kù)所保留在初始模型中，得到了滿足需求的具有擬間接依賴關(guān)系的業(yè)務(wù)流程模型。

未來(lái)關(guān)于過(guò)程挖掘的研究還有很多工作去做。例如，在基于整數(shù)線性規(guī)劃的約束體下，從包含數(shù)量眾多的事件的日志中挖掘滿足需求的業(yè)務(wù)流程模型。

參考文獻(xiàn)：

[1]Van Der Werf J M E M，Kaats E.Discovery of functional architectures from event logs[C]//International Workshop on Petri Nets and Software Engineering，2015：227-243.

[2]Leemans S J J，F(xiàn)ahland D，Van Der Aalst W M P.Discovering block-structured process models from event logs containing infrequent behaviour[C]//International Conference on Business Process Management.[S.l.]：Springer International Publishing，2013：66-78.

[3]Leemans S J J，F(xiàn)ahland D，Van Der Aalst W M P.Discovering block-structured process models from incomplete event logs[M]//Application and Theory of Petri Nets and Concurrency.[S.l.]：Springer International Publishing，2014：91-110.

[4]Boushaba S，Kabbaj M I，Bakkoury Z.Process discovery：Automated approach for block discovery[C]//2014 International Conference on Evaluation of Novel Approaches to Software Engineering（ENASE），2014：1-8.

[5]Van Der Aalst W M P，Kalenkova A，Rubin V，et al.Process discovery using localized events[C]//International Conference on Applications and Theory of Petri Nets and Concurrency.[S.l.]：Springer International Publishing，2015：287-308.

[6]De Leoni M，Van Der Aalst W M P，Dees M.A general process mining framework for correlating，predicting and clustering dynamic behavior based on event logs[J].Information Systems，2016，56：235-257.

[7]Leemans S J J，F(xiàn)ahland D，Van Der Aalst W M P.Discovering block-structured process models from event logs-a constructive approach[C]//International Conference on Applications and Theory of Petri Nets and Concurrency.Berlin Heidelberg：Springer，2013：311-329.

[8]Senderovich A，Leemans S J J，Harel S，et al.Discovering queues from event logs with varying levels of information[C]//International Conference on Business Process Management.[S.l.]：Springer International Publishing，2015：154-166.

[9]Van Der Werf J M E M，Van Dongen B F，Hurkens C A J，et al.Process discovery using integer linear programming[J].Fundamenta Informaticae，2009，94（3/4）：387-412.

[10]化佩，方賢文，劉祥偉.基于擬間接依賴的過(guò)程模型挖掘方法[J].計(jì)算機(jī)科學(xué)，2016，43（11）：94-97.

[11]Smirnov S，Weidlich M，Mendling J.Business process model abstraction based on behavioral profiles[C]//8th International Conference on Service-oriented Computing，San Francisco，December 7-10，2010.Berlin Heidelberg：Springer，2010，6470：1-16.

[12]Weidlich M，Polyvyanyy A，Desai N，et al.Process compliance measurement based on behavioral profiles[J].Advanced Information Systems Engineering，2010，6051：499-514.

[13]Van Der Aalst W，Weijters T，Maruster L.Workflow mining：Discovering process models from event logs[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（9）：1128-1142.

[14]Van Zelst S J，Van Dongen B F，Van Der Aalst W M P.Filter techniques for region-based process discovery，Technical Report 15-4[R].BPM Center.org，2015.