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

曹 蕊，方賢文，王麗麗

CAO Rui,FANG Xianwen,WANG Lili

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

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

1 引言

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

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

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

2 基本概念

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

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

（1）P是有限庫所集，T是有限變遷集。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：事件日志

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

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

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

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

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

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

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

4 實例分析

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

表1 事件日志L

首先將事件軌跡按照實例數(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)系，可以得到衣服購買的初始Petri網(wǎng)模型M0，如圖2所示。

圖2 初始模型M0

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

表3 執(zhí)行日志

表4 約束體表

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

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

5 結(jié)束語

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

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

參考文獻：

[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]化佩，方賢文，劉祥偉.基于擬間接依賴的過程模型挖掘方法[J].計算機科學，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.