基于事件日志的可配置流程樹合并方法

唐婧芝，劉祥偉，王麗麗

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

基于事件日志的可配置流程樹合并方法

唐婧芝，劉祥偉，王麗麗

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

為了滿足企業復雜多變的應用需求，通過結合配置信息建立可配置的流程模型已成為新的趨勢。目前對于建模工作的研究主要集中于利用事件日志挖掘一個特定的流程模型，對于挖掘包含一類特征的多個流程模型具有局限性。本文提出了基于事件日志發現流程樹，然后根據結點和有向邊合并流程樹，最后對結點上的操作符進行可配置的合并得到一個可配置的流程模型。

過程挖掘；可配置流程模型；流程樹

1 引言

計算機技術的發展使業務流程被廣泛應用在不同企業，為了研究多個企業間的相似業務流程，合并流程模型得到一個綜合的可配置流程模型成為了一種新的發展趨勢。目前關于合并業務流程的一些方法被提出，但是由于沒有結合配置信息,使得合并后的模型異常復雜和冗余,且計算量較大[1]。

在過程挖掘方面，W.M.P.van der Aals[2]指出過程挖掘技術可以作為業務流程變化分析以及檢測的工具。Xumin Liu[3]和Yiping Wen[4]提出了從事件日志中發現流程模型的方法，但是發現流程模型不包含配置信息。Amin Vahedian Khezerlou[5]和Christopher Shultis[6]提出了發現流程樹的新算法，介紹了流程樹可以用來分析業務流程。M.Weidlich[7]詳細介紹了行為輪廓關系，將其應用到流程樹中結點處的操作符可以合并流程樹。Huang rui[8]和Peter C.M.[9]給出了流程模型的合并方法。Wil M.P.[10]介紹了可配置的流程模型，闡述了可配置流程模型的構建和優點。Wil van der Aalst[11]提出了評估模型的四個指標，即合理性、精確度、一般化和簡單性。J.C.A.M. Buijs[12]提出把合理性作為判斷模型好壞最重要的標準。

基于以上背景，本文通過電影票預售訂單處理這一實例得到幾組事件日志，利用過程挖掘技術從幾組描述相似業務流程的日志中發現流程樹,合并相同結點和有向邊，然后對結點上的操作符進行可配置的合并得到一個可配置的流程樹。

2 動機例子

這里給出了三組相似業務流程執行過程中產生的事件日志。針對網上預售電影票這一事件，顧客必須先要從網上填寫申請表并提交給系統要求購買預售的電影票，所以系統就有相應地處理流程。以下給出的事件日志都是系統自動獲取的，其中重要符號如下：a代表系統處理訂單，b代表檢查信用卡信息，c代表查詢電影票余票，d代表記錄個人信息，e代表接收訂單，f代表拒絕訂單，g代表更新余票數量，h代表完成，i代表核實VIP卡信息，j代表查詢VIP卡余額，k代表確認訂單。

L1={(a,b,c,d,e,g,h)23,(a,c,b,d,e,g,h)28,(a,b,c,e,g,h)29,(a,b,c,d,f,h)34,(a,c,b,f,h)17,(a,c,b,e,g,h)19,(a,b,c,f,h)15,(a,c,b,d,f,h)30,(a,b,c,g,e,h)35}.

L2={(a,i,j,c,e,h)25,(a,i,j,c,f,h)33}.

L3={(a,b,c,e)20,(a,b,c,f)27}.

L1，L2，L3分別是三個業務流程模型執行過程中隨機產生的事件日志，通過過程挖掘技術可以得到各自的源模型。為了研究這三個相似的業務流程，通常需要合并流程模型。但是一般的合并方法計算量大且復雜性高，所以結合配置信息進行合并得到可配置的流程模型是本文的研究重點。

3 基礎知識及相關概念

定義1[1](流程模型Petri網) 一個流程模型Petri網PN=(P,T,F,C)是一個四元組，滿足以下條件：(1)P是有限庫所集，T是有限變遷集；(2)P≠?,T≠?且P∩T=?；(3)F=(P×T)∪(T×P)表示PN的流關系且(P∪T,F)是強連通圖；(4)dom(F)∪cod(F)=P∪T，其中dom(F)={x∈P∪T|?y∈P∪T,(x,y)∈F}；cod(F)={x∈P∪T|?y∈P∪T,(y,x)∈F}。

(5)C={and,xor,or}是流程網的結構類型。

定義3[3](事件日志，跡) 跡指活動發生的序列，如跡(a,b,c)指活動a最先發生，其次發生b，最后發生c；事件日志指包含多個跡的集合。

定義4[5](流程樹) 流程樹是一個不含圓的有向連接圖，第一層結點稱為樹根，以下各層結點均為上層結點對應的孩子。每個結點要么是分支結點，要么是葉子結點，分支結點處都有一個操作符，包括嚴格序(→)，排他序(×)，并發序(∧)，異或序(∨)，葉子結點則代表單個活動變遷。

4 基于事件日志挖掘可配置的流程樹

首先利用過程挖掘技術從事件日志中發現流程樹，然后根據結點和有向邊合并流程樹，最后對結點上的操作符進行可配置的合并得到一個可配置的流程模型。

4.1 挖掘流程樹

針對業務流程中任務的發生順序，可以用一個表格(表1)來表示跡中的跟隨關系。表格中只有1和0，其中數字1表示跡中b在a的后面，即b跟隨a，反之則用0表示。

從表1中的∑1可知，a?b=c?d?e=g?f?h，可推出在業務流程模型中a是開始變遷，h是結束變遷。其中，b和c可作為一個塊結構，e和g作為一個塊結構，并且b,c塊結構在e,g塊結構的前面。變遷d在b,c塊結構之后，同時在e,g塊結構之前。此時暫時得到一個構建流程樹的框架圖(圖1)。

表1 事件日志L1中的跟隨關系

圖1 關于事件日志L1構建流程樹的框架圖

我們把b,c塊結構和e,g塊結構看作整體后再次計算日志L1中的跟隨關系(表2)。

表2 事件日志L1中的跟隨關系

從表2中的∑2可知，a?bc?d?eg=f?h，所以e,g和f在一個塊結構中。由此可進一步得到流程樹的構建圖(圖2)。

圖2 在圖1基礎上進一步得到流程圖的框架圖

通過分析日志L1中跡的發生順序可知b與c是并發關系，e與g是并發關系，塊結構b,c與f是排他結構。并且從跡abcdegh，abcegh，acbdegh，acbegh中還可以發現d與一個沉默變遷τ是排他關系(沉默變遷τ在流程樹中沒有實際意義，只是控制流結構的需要)，因此最終可以得到關于日志L1的流程樹，如圖3所示。

圖3 基于事件日志L1發現的流程樹T1

同理可得關于事件日志L2，L3的流程樹，如圖4所示。

圖4 基于事件日志L2，L3發現的流程樹T2，T3

4.2 構建可配置的流程樹

進行合并流程樹時,不僅合并相同的結點和有向邊，同時對結點上的操作符進行可配置的合并。流程樹中結點操作符包括嚴格序(→)、排他序(×)、并發序(∧)、異或序(∨)。比如可配置的∨可以配置給→，×，∧，∨，即當這些結點上的操作符進行合并時可以合并成∨C。詳細內容見表3。

表3 流程樹中結點操作符的合并法則

算法1：合并流程樹

輸入：流程樹T1，T2，T3

步驟一：觀察需要進行合并的流程樹的結構，根據相似性找到各自匹配的塊結構，轉到步驟二；

步驟二：在匹配的塊結構中取任意一組結點ti，tj，1≤ij≤k，及其在輸入模型中的結點操作符關系?(ti,tj)，?′(ti,tj)，?″(ti,tj)，轉步驟三；

步驟三：如果?(ti,tj)=?′(ti,tj)=?″(ti,tj)≠?，則轉到步驟五，否則轉到步驟四；

步驟四：如果?(ti,tj)≠?′(ti,tj)≠?″(ti,tj)≠?，則按照表3中的合并法則先進行合并?(ti,tj)和?′(ti,tj)得到?1,2(ti,tj)，再與?″(ti,tj)進行合并。如果?(ti,tj)=φ∧?′(ti,tj)≠φ∧?″(ti,tj)≠?，則合并?′(ti,tj)和?″(ti,tj)，并且引入沉默變遷τ添加到合并后的結點處，用排他序(×C)連接。如果?(ti,tj)=φ∧?′(ti,tj)=φ∧?″(ti,tj)≠?，則將?″(ti,tj)繼續保留在合并后的流程樹中，轉到步驟五；

步驟五：如果?(ti,tj)={→}，則?(ti,ti)={←}，否則?(ti,tj)=?(tj,ti)；

步驟六：通過以上步驟得到了可配置的流程樹。

通過步驟一，根據流程樹分支結構的相似性劃分出對應的塊結構，然后合并結點和操作符。因此在圖5中用不同的線框標出了三個流程樹中對應的子流程樹。下面就如何具體合并使用過程圖來說明。

圖5 流程樹T1，T2，T3

首先用過程圖分析圖5中實線框里子流程樹的合并過程。

圖6 合并S1T1，S1T2，S1T3的過程圖

根據步驟三和步驟四，在圖6中可以發現實線框里子流程樹的結點和有向邊相同，但是操作符不同，因此可以根據控制流結構合并結點和有向邊，再根據表3將并發序(∧)和嚴格序(→)合并成異或序(∨C)。S1T1中沒有與虛線框對應的子流程樹，所以引入了沉默結點τ用來與k作為排他序操作符的分支結點。此時還觀察到S1T2中未合并的流程樹分支不屬于三個子流程樹的共有部分，因此繼續保留在合并后的流程樹中，且它的結點操作符嚴格關系(→)不需要進行配置，但是仍然需要添加排他關系(×C)來連接前面已經合并后的b,c分支，最終得到帶配置信息的子流程樹。因為圖5中短虛線框里的流程樹分支S2T1在流程樹T2，T3中沒有與它對應的部分，所以繼續保留在合并后的流程樹中。下面進行合并圖5中長虛線框里的子流程樹，如圖7所示。

圖7 合并S3T1，S3T2，S3T3的過程圖

根據步驟二和步驟五，將圖7中實線框里子流程樹的結點、有向邊和操作符直接進行合并。通過步驟三和步驟四可以發現在S3T1中結點g和e是并發序(∧)，而結點e在S3T2和S3T3中與上層結點操作符關系都是排他序(×)，因此引入了沉默結點τ，使用操作符排他序(×C)連接結點g和τ，同理合并流程樹中的結點h，最終得到了一個可配置的流程模型，如圖8所示。

圖8 可配置的流程樹

5 總結與展望

本文提出了通過從幾組描述相似業務流程的事件日志中發現流程樹來建立可配置的流程模型。因此在工作流網的基礎上合并流程樹的結點、有向邊和結點上的操作符，得到可配置的流程樹。但是實際生活中企業活動的多樣化和復雜性使得許多問題有待進一步的研究。例如，在模型構建時如何找到一種算法能自動選擇結點進行配置，如果結合了數據、資源或者時間限制時又該如何進行可配置流程模型的構建。

[1]蔣昌俊.Petri網的行為理論及其應用[M].北京:高等教育出版社,2003:19-28.

[2]W.M.P.van der Aalst,J.Munoz-Gama,J.Garmona.Hierarchical conformance checking of process models based on event logs[J].Computer Science,2013,7927:291-310.

[3]Xumin Liu,Chen Ding.Learningworkflow models from event logs using co-clustering [J].International Journal of Web Services Research(IJWSR),2013(3):42-59.

[4]Yiping Wen,Zhigang Chen,Jianxun Liu,et al.Mining batch processing workflow models from event logs[J]. Concurrency Computation Practice Experience,2013(13):1928-1942.

[5]Amin Vahedian Khezerlou,Somayeh Alizadeh.A new model for discovering process trees from event logs[J].Applied Intelligence,2014(3):725-735.

[6]Christopher Shultis.The process of discovery:interpreting child of tree[J].Contemporary Music Review,2014(5-6):570-579.

[7]M.Weidlich,J.Mendling,M.Weske.Efficient consistency measurement based on behavioural profiles of process models[J].IEEE Transaction on Software Engineering,2011(3):410-429.

[8]Huangrui,Zhang Shusheng,Bai xiaoliang,et al.An effective numerical control machining process reuse approach by merging feature similarity assessment and data mining for computer-aided manufacturing models[J].Proceedings of the Institution of Mechanical Engineers,2015,2297:64-77.

[9]Peter C.M.Molenaar,JohnR.Nesselroade.Merging the idiographic filter with dynamic factor analysis to model process[J].Applied Developmental Science,2012(4):210-219.

[10]Wil M.P.Aalst,Niels Lohmann,Marcello La Rosa.Ensuring correctness during process configuration via partner synthesis[J].Information Systems,2012(6):574-592.

[11]Wil van der Aalst,Arya Adriansyah,Boudewijn van Dongen.Replaying history on process models for conformance checking and performance analysis[J].WIREs Data Mining Knowledge Discovery,2012(2):182-192.

[12]J.C.A.M. Buijs,B.F.van Dongen,W.M.P.van der Aalst.On the role of fitness,precision,generalization and simplicity in process discovery[J].Springer Berlin Heidelberg,2012(3):305-322.

Configuration Process Tree Merging Method Based on Event Log

TANG Jing-zhi, LIU Xiang-wei, WANG Li-li

(College of Science, Anhui University of Science and Technology,Huainan Anhui 232001,China)

In order to meet the complex and ever-changing application requirements of the enterprise, the new trend is established by combining the configuration information. At present, the research of modeling work is mainly focused on the use of event log mining for a specific process model, which has limitations for mining multiple process models that contain a class of features. In this paper, the process tree is discovered based on event log, and then merge the process tree according to the node and the directed edge. At last, the operators on the node can be configurable merged to obtain a configurable process model.

process mining; configurable process model; process tree

2016-09-07

國家自然科學基金項目“基于Petri網行為輪廓的業務流程交互下變化域傳播機理及控制方法研究”(61572035)；國家自然科學基金項目“基于Petri網的網絡化軟件行為可信性分析方法研究”(61272153)；國家自然科學基金項目“基于行為Petri網的業務系統變化域分析方法及應用研究”(61402011)；安徽省自然科學基金項目“面向可信管理的業務系統變化域分析方法研究”(1508085MF111)；安徽省自然科學基金項目“部分可觀系統故障診斷的Petri網理論及在行為變化診斷中的應用”(1608085QF149)。

唐婧芝(1990- )，女，碩士研究生，從事Petri網研究。

TP391.9

A

2095-7602(2017)02-0028-07