基于擬間接依賴的流程挖掘優化分析

曹 蕊，方賢文，王麗麗

CAO Rui,FANG Xianwen,WANG Lili

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

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

1 引言

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

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

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

2 基本概念

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

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

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

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

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

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

則以上幾種行為關系構成Petri網的行為輪廓。

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

定義4[14]（前綴閉包）設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 基于擬間接依賴的流程挖掘優化分析方法

3.1 事件間擬間接依賴關系

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

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

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

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

圖1 擬間接依賴關系的Petri網模型

3.2 基于擬間接依賴的流程挖掘優化分析算法

對于基于整數線性規劃流程發現算法的基本約束體，由于每條執行日志不同，則一個庫所前后變遷t1,t2發生的 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具有擬間接依賴性關系，這樣就挖掘出了兩個變遷的擬間接依賴關系（文中的事件集以Petri網的變遷集為例）。

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

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

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

算法1基于擬間接依賴的流程挖掘優化

輸入：事件日志

輸出：Petri網模型

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

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

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

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

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

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

4 實例分析

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

表1 事件日志L

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

表2 行為輪廓關系表

根據事件日志的行為輪廓關系，可以得到衣服購買的初始Petri網模型M0，如圖2所示。

圖2 初始模型M0

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

表3 執行日志

表4 約束體表

圖3 具有擬間接依賴關系的優化模型M1

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

5 結束語

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

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

參考文獻：

[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，Fahland 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，Fahland 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，Fahland 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.