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

唐婧芝，劉祥偉，王麗麗

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

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

唐婧芝，劉祥偉，王麗麗

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

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

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

1 引言

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

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

基于以上背景，本文通過電影票預(yù)售訂單處理這一實(shí)例得到幾組事件日志，利用過程挖掘技術(shù)從幾組描述相似業(yè)務(wù)流程的日志中發(fā)現(xiàn)流程樹,合并相同結(jié)點(diǎn)和有向邊，然后對結(jié)點(diǎn)上的操作符進(jìn)行可配置的合并得到一個(gè)可配置的流程樹。

2 動(dòng)機(jī)例子

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

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分別是三個(gè)業(yè)務(wù)流程模型執(zhí)行過程中隨機(jī)產(chǎn)生的事件日志，通過過程挖掘技術(shù)可以得到各自的源模型。為了研究這三個(gè)相似的業(yè)務(wù)流程，通常需要合并流程模型。但是一般的合并方法計(jì)算量大且復(fù)雜性高，所以結(jié)合配置信息進(jìn)行合并得到可配置的流程模型是本文的研究重點(diǎn)。

3 基礎(chǔ)知識及相關(guān)概念

定義1[1](流程模型Petri網(wǎng)) 一個(gè)流程模型Petri網(wǎng)PN=(P,T,F,C)是一個(gè)四元組，滿足以下條件：(1)P是有限庫所集，T是有限變遷集；(2)P≠?,T≠?且P∩T=?；(3)F=(P×T)∪(T×P)表示PN的流關(guān)系且(P∪T,F)是強(qiáng)連通圖；(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}是流程網(wǎng)的結(jié)構(gòu)類型。

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

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

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

首先利用過程挖掘技術(shù)從事件日志中發(fā)現(xiàn)流程樹，然后根據(jù)結(jié)點(diǎn)和有向邊合并流程樹，最后對結(jié)點(diǎn)上的操作符進(jìn)行可配置的合并得到一個(gè)可配置的流程模型。

4.1 挖掘流程樹

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

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

表1 事件日志L1中的跟隨關(guān)系

圖1 關(guān)于事件日志L1構(gòu)建流程樹的框架圖

我們把b,c塊結(jié)構(gòu)和e,g塊結(jié)構(gòu)看作整體后再次計(jì)算日志L1中的跟隨關(guān)系(表2)。

表2 事件日志L1中的跟隨關(guān)系

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

圖2 在圖1基礎(chǔ)上進(jìn)一步得到流程圖的框架圖

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

圖3 基于事件日志L1發(fā)現(xiàn)的流程樹T1

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

圖4 基于事件日志L2，L3發(fā)現(xiàn)的流程樹T2，T3

4.2 構(gòu)建可配置的流程樹

進(jìn)行合并流程樹時(shí),不僅合并相同的結(jié)點(diǎn)和有向邊，同時(shí)對結(jié)點(diǎn)上的操作符進(jìn)行可配置的合并。流程樹中結(jié)點(diǎn)操作符包括嚴(yán)格序(→)、排他序(×)、并發(fā)序(∧)、異或序(∨)。比如可配置的∨可以配置給→，×，∧，∨，即當(dāng)這些結(jié)點(diǎn)上的操作符進(jìn)行合并時(shí)可以合并成∨C。詳細(xì)內(nèi)容見表3。

表3 流程樹中結(jié)點(diǎn)操作符的合并法則

算法1：合并流程樹

輸入：流程樹T1，T2，T3

步驟一：觀察需要進(jìn)行合并的流程樹的結(jié)構(gòu)，根據(jù)相似性找到各自匹配的塊結(jié)構(gòu)，轉(zhuǎn)到步驟二；

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

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

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

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

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

通過步驟一，根據(jù)流程樹分支結(jié)構(gòu)的相似性劃分出對應(yīng)的塊結(jié)構(gòu)，然后合并結(jié)點(diǎn)和操作符。因此在圖5中用不同的線框標(biāo)出了三個(gè)流程樹中對應(yīng)的子流程樹。下面就如何具體合并使用過程圖來說明。

圖5 流程樹T1，T2，T3

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

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

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

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

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

圖8 可配置的流程樹

5 總結(jié)與展望

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

[1]蔣昌俊.Petri網(wǎng)的行為理論及其應(yīng)用[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

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

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

TP391.9

A

2095-7602(2017)02-0028-07