蘇 軒，劉 聰+，張帥鵬，曾慶田，李彩虹

(1.山東理工大學 計算機科學與技術學院，山東 淄博 255000；2.山東科技大學 計算機科學與工程學院，山東 青島 266590)

0 引言

流程挖掘[1-3]是連接數據科學和業(yè)務流程管理領域的新穎學科，其目的是從事件日志中提取業(yè)務流程的有效信息，發(fā)現、監(jiān)控和改進真實的業(yè)務流程[4]。人們對流程挖掘日益增長的興趣主要有兩個驅動因素：①越來越多被記錄下來的事件提供了流程歷史的詳細信息；②需要在競爭激烈且瞬息萬變的環(huán)境中改進和支持業(yè)務流程。流程挖掘還包括流程預測[5-6]和業(yè)務流程自動化[7]等子領域，流程發(fā)現是最具挑戰(zhàn)性的流程挖掘任務之一，其可以在不使用任何先驗信息的情況下從事件日志中發(fā)現流程模型，近年來受到了外界的廣泛關注。在過去的20年中，國內外學者已經提出各種流程發(fā)現方法，如Alpha Miner[8]，Heuristics Miner[9]，Inductive Miner[10]，Tsinghua-Alpha[11]，Split Miner[12]等，然而由于I/O和內存等硬件限制，大多數發(fā)現方法不再適用于使用一臺機器處理整個大型數據集的模型發(fā)現。若依靠當前的分布式平臺重新實現現有的流程發(fā)現算法，如著名的MapReduce框架[13-14]，則流程將非常耗時，而且這些方法不具有普適化，需要開發(fā)人員對底層發(fā)現方法有廣泛的了解，因此迫切需要一種新方法來解決這些問題。

事件日志采樣技術為上述問題提供了一種可行性方案，其將原始事件日志作為輸入，返回一個樣本日志。事件日志采樣技術不是要求重新實現現有發(fā)現方法，而是希望能夠提供一種提高發(fā)現效率的替代方法。目前已經提出許多事件日志采樣技術，以LogRank日志采樣技術[15-16]為例，該技術實現了一個基于圖的排序算法，所得樣本日志比原始日志小得多，處理效率也更高。在此基礎上提出的一種基于軌跡相似度的事件日志采樣技術LogRank+[17]，雖然能夠確保采樣質量，縮短采樣時間，提高采樣效率，但是其性能仍然不能滿足實際應用的需求，例如得到的模型質量不夠理想，而且隨著原始日志規(guī)模的增大，原始日志采樣時間與樣本日志挖掘時間之和與原始日志挖掘時間之間的差異愈發(fā)明顯。

受傳統集合覆蓋等相關問題的啟發(fā)，借助傳統算法如動態(tài)規(guī)劃、貪心算法、排序算法等，本文提出面向日志完備性的事件日志采樣方法，包括完全遍歷采樣法(BF-Sampling)、集合覆蓋采樣法(SC-Sampling)、基于軌跡長度的采樣方法(TL-Sampling)和基于軌跡頻次的采樣方法(TF-Sampling)4種，該方法保留了原始日志更多的信息，能夠更有效地支持日志采樣，而且與已有采樣方法相比，4種采樣方法可以得到更簡單、更高質量的流程模型。為了驗證這種保證日志完備性的事件日志采樣方法的可行性與高效性，從模型質量評估和時間性能分析兩方面進行實驗，比較4種采樣方法得到的樣本日志與原始日志的質量，最終說明本文所提4種新的采樣方法可以在保證模型挖掘質量的前提下，大幅提高模型挖掘效率，具備可行性與高效性。

1 基礎知識

本章介紹后期研究4種事件日志采樣方法和兩種實驗評估方法需要用到的基本知識。假設S為一個集合，?表示空集，B(S)為集合S所有多集的集合;f：X→Y是一個函數，其中dom(f)為其定義域，cod(f)={f(x)|x∈dom(f)}為函數的值域;在集合S上長度為n的序列為一個函數σ{1,2,…,n}→S。若σ(1)=a1,σ(2)=a2,…,σ(n)=an，則σ=a1,a2,…,an；S*為定義在集合S上所有任意長度有限序列的集合。

定義1事件、軌跡、事件日志。給定A是一個活動的集合，一個軌跡σ∈A*是一系列的活動。對于1≤i≤|σ|，σ(i)表示軌跡σ中的第i個事件，L∈B(A*)是一個事件日志。一個事件日志記錄了某個潛在業(yè)務流程的執(zhí)行情況，該業(yè)務流程對應的業(yè)務流程模型即為流程挖掘的任務目標，因此并未在事件日志的定義中顯式地出現。業(yè)務流程實例的執(zhí)行情況由相應的軌跡表示，軌跡中的事件記錄在事件日志中。

定義2流程發(fā)現。設UM是所有流程模型的集合，一個流程發(fā)現方法指從一個事件日志L∈B(A*)映射到一個流程模型pm∈UM的函數γ，即γ(L)=pm。一般來說，流程發(fā)現方法能夠將事件日志轉換為有標記的Petri網、業(yè)務流程建模標注(Business Process Modeling Notation，BPMN)、流程樹等表示的流程模型。無論流程模型采用什么表示方法，輸入事件日志中的每個軌跡都對應發(fā)現的流程模型中的一個可能的執(zhí)行序列。

定義3直接跟隨活動關系。假設事件日志L中的一條軌跡為a,b,c,e,f，則a，b，c，e，f是σ的5個活動，如果活動b緊緊跟隨在活動a之后，則稱在軌跡σ中從a到b存在直接跟隨活動關系，記作a,b。因此軌跡σ的直接跟隨活動關系有4對，分別為a,b，b,c，c,e，e,f。

2 方法概述

本章提出兩個研究目標：①尋找一種事件日志采樣方法，使樣本日志不僅具有足夠的代表性，還能覆蓋原始事件日志中的所有行為，而且相比已有采樣方法更加高效；②分別從時間性能分析和模型質量評估兩方面衡量樣本日志相對于原始事件日志的質量。

目標①的解決方案提供了一種方法，即相比已有事件日志采樣方法，將大規(guī)模事件日志更快更準確地采樣為較小的樣本日志，以便更高效地進行分析；目標②的答案用于驗證事件日志采樣方法的有效性和評估樣本日志的質量，以證明事件日志采樣方法的可行性。

為了實現這些研究目標，圖1展示了所用方法的概述，包括以下兩個階段:

(1)階段1——事件日志采樣

事件日志采樣技術將一個事件日志L∈B(A*)映射到另一個事件日志L′∈B(A*)中，其中L′?L，L為原始事件日志，L′為L的一個樣本日志，與原始事件日志L相比，L′小得多，而且可以準確地代表L。

本文提出的面向日志完備性的4種事件日志采樣方法分別為完全遍歷采樣法、集合覆蓋采樣法、基于軌跡長度的采樣方法、基于軌跡頻次的采樣方法。

(2)階段2——采樣技術的有效性評估

為驗證4種事件日志采樣方法的有效性，提出兩種評估方法：

1)模型質量評估 首先通過比較原始日志和樣本日志的有向圖是否相同，間接地說明樣本日志中的行為與原始事件日志中的代表性行為是否相同，若比較結果相同，則將原始日志與從樣本日志中挖掘的模型進行擬合度計算[19]，擬合度值為1表示樣本模型可以重新生成原始日志中的所有軌跡，低擬合度表明原始日志中的大部分行為不能被樣本模型重演。此外，通過準確度[20]指標量化樣本日志相對于原始日志的質量，準確度值為1表示樣本模型生成的所有軌跡都包含在原始日志中，低精確度則表明樣本模型允許原始日志外更多的行為。最后，通過擬合度和準確度的調和平均值F-measure[18]來評價模型的優(yōu)劣。

2)時間性能分析 首先計算原始日志采樣時間與樣本日志挖掘時間之和，再將其與原始日志挖掘時間進行比較，原始日志采樣時間與樣本日志挖掘時間之和越短，采樣效率越高，事件日志采樣方法越高效。

3 業(yè)務流程事件日志采樣

本章首先給出4種事件日志采樣方法的具體思路，其次介紹兩種實驗評估方法。下面給出一個示例日志(表示為L)，用于介紹面向事件日志完備性的采樣方法。該日志包括5條軌跡，共有5個變體和6個事件，記σ(1)=a,d,e，σ(2)=a,b,c,e，σ(3)=b,c,e,f，σ(4)=b,d,f，σ(5)=c,d，L=[a,d,e,a,b,c,e,b,c,e,f,b,d,f,c,d]。示例日志L的軌跡的初始點集合StartSet、結束點集合EndSet、日志直接跟隨關系集合dfrSetLog和軌跡直接跟隨關系集合traceIDToDFRSet分別為：

StartSet=[a,b,c]；

EndSet=[e,f,d]；

dfrSetLog=[a,d,d,e,a,b,b,c,

traceIDToDFRSet=[{a,d,d,e},{a,b,

3.1 日志完備性采樣方法

3.1.1 完全遍歷采樣法

完全遍歷采樣法的思路如下：從原始事件日志第一條軌跡開始依次遍歷，若軌跡的直接跟隨關系集合與日志直接跟隨關系集合有交集，且滿足軌跡的開始點與開始點集合有交集或軌跡的結束點與結束點集合有交集，則將該條軌跡加入樣本日志，并刪除以下3部分：①日志直接跟隨關系集合與新軌跡的直接跟隨關系集合的交集；②開始點集合與新軌跡開始點的交集；③結束點集合與新軌跡結束點的交集。直到日志直接跟隨關系集合、開始點集合、結束點集合均為空，停止軌跡遍歷。完全遍歷采樣法的偽代碼如算法1所示。

算法1完全遍歷采樣法。

輸入:原始日志。

輸出:樣本日志。

1： Initialization(算法開始)

2： N∈ |L|

3： For i∈1 To N Step 1

4： StartSet1 {σ(0)}

5： EndSet1 {σ(|σ |-1)}

6： If(dfrSetLog∩traceIDToDFRSet !=?)∨(StartSet1 ∩StartSet !=?)∨(EndSet1 ∩ EndSet !=?) Then

7： SampleLog L(i)

8： dfrSetLog dfrSetLog-(dfrSetLog∩traceIDToDFRSet)

9： StartSet StartSet-(StartSet1∩StartSet)

10： EndSet EndSet-(EndSet1∩EndSet)

11： Else break；

12：End(算法結束)

3.1.2 集合覆蓋采樣法

本文給出集合覆蓋采樣法的偽代碼，如算法2所示。集合覆蓋采樣法主要借助集合覆蓋問題的貪婪算法求解思想，具體思路如下：首先遍歷所有軌跡的直接跟隨活動關系，選擇一條覆蓋了最多未覆蓋直接跟隨活動關系的軌跡(即與日志直接跟隨活動關系集合擁有最大交集的軌跡)；然后將所選軌跡加入樣本日志，刪除其覆蓋的日志直接跟隨活動關系、開始點與開始點集合的交集、結束點與結束點集合的交集；最后重復前兩步，直到日志直接跟隨活動關系集合、開始點集合、結束點集合3個集合均為空集時結束遍歷。

算法2集合覆蓋采樣法。

輸入:原始日志。

輸出:樣本日志。

1：Initialization(算法開始)

2：N |L|

3：For i 1 To N Step 1

4： StartSet2 {σ(0)}

5： EndSet2 {σ(|σ|-1)}

6： If Max (dfrSetLog∩traceIDToDFRSet(i)) Then

7： SampleLog L(i)

8： dfrSetLog dfrSetLog-(dfrSetLog∩traceIDToDFRSet(i))

9： StartSet StartSet-(StartSet2∩StartSet)

10： EndSet EndSet-(EndSet2∩EndSet)

11： Else break；

12：End(算法結束)

3.1.3 基于軌跡長度的采樣方法

定義4軌跡長度。軌跡σ的長度記為|σ|。日志中的所有事件是全序的，即整個日志可以看作為一個事件序列，然而整個日志的長度通常并不是該序列的長度，而是日志中所包含的軌跡數，因為軌跡是一個相對完整的邏輯單位。假設一條軌跡σ=a,b,c,e,f，a，b，c，e，f是σ的5個事件，則稱L中σ的軌跡長度為5，即|σ|=5。日志L中第i條軌跡長度表示為|L(i)|。

根據定義4，基于軌跡長度的采樣方法思想如下：首先統計原始事件日志中每條軌跡的長度，將軌跡和其對應的長度存儲到一個集合中；然后按照軌跡長度降序排列，從最長的軌跡開始依次向下遍歷，篩選樣本日志軌跡的方法與完全遍歷采樣法相同?；谲壽E長度的采樣方法偽代碼如算法3所示。

算法3基于軌跡長度的采樣方法。

輸入:原始日志。

輸出:樣本日志。

1：Initialization(算法開始)

2：N |L|

3：For i 1 To N Step 1

4： TraceLength(i) |σ(i)|

6：For j MaxLength To MinLength Step 1

7： StartSet3 {σ(0)}

8： EndSet3 {σ(|σ|-1)}

9： If(dfrSetLog ∩ traceIDToDFRSet(j)!=?)∨(StartSet3∩StartSet!=?)∨(EndSet3∩EndSet!=?)Then

10： SampleLog L(i)

11： dfrSetLog dfrSetLog-(dfrSetLog∩traceIDToDFRSet(j))

12： StartSet StartSet-(StartSet3∩StartSet)

13： EndSet EndSet-(EndSet3∩EndSet)

14： Else break；

15：End(算法結束)

3.1.4 基于軌跡頻次的采樣方法

根據定義5，基于軌跡頻次的采樣方法思想如下：從原始事件日志的第1條軌跡開始，依次統計每條軌跡出現的次數，同時將軌跡和其對應的頻次存儲到一個集合中；統計完成后進行去重操作，只保留相同軌跡的頻次最大值；最后按照軌跡頻次降序排列，從頻次最大的軌跡開始依次向下遍歷，篩選樣本日志軌跡的方法與完全遍歷采樣法相同?；谲壽E頻次的采樣方法偽代碼如算法4所示。

算法4基于軌跡頻次的采樣方法。

輸入:原始日志。

輸出:樣本日志。

1：Initialization(算法開始)

2：N |L|

3：For i 1 To N Step 1

5：For i 1 To N Step 1

6： If TraceFrequency(i) HasNextSameTrace Then

7： TraceFrequency (TraceFrequency-TraceFrequency(i))

9：For j MaxFrequency To MinFrequency Step 1

10： StartSet4 {σ(0)}

11： EndSet4 {σ(|σ|-1)}

12： If(dfrSetLog∩traceIDToDFRSet(j)!=?)∨(StartSet4∩StartSet!=?)∨(EndSet4∩EndSet!=?)Then

13： SampleLog L(i)

14： dfrSetLog dfrSetLog-(dfrSetLog∩traceIDToDFRSet(j))

15： StartSet StartSet-(StartSet4∩StartSet)

16： EndSet EndSet-(EndSet4∩EndSet)

17： Else break；

18：End(算法結束)

3.2 采樣方法的有效性評估

為了系統地評估4種采樣方法得到的樣本日志相比原始日志的質量，同時與之前的采樣方法進行比較，本文采用模型質量評估和時間性能分析兩種評估方法。

3.2.1 模型質量評估

為了評估模型質量，先引入直接跟隨活動關系集合和樣本日志完備性定義：

圖2直觀地展示了定義7中樣本日志完備性的概念，圖中I.M表示對日志采用Inductive Miner流程發(fā)現方法，PN1=PN2表示原始日志Petri網和樣本日志Petri網在保證樣本日志完備性時需滿足的條件。

因為有向圖可分別對比樣本日志和原始日志對應的直接跟隨圖、邊集(即直接跟隨活動關系集合)和頂點集(即活動集合)，所以模型質量評估實驗通過比較原始日志和樣本日志的有向圖是否相同，來間接驗證樣本日志相比原始日志的質量，從而判斷采樣方法是否保證了樣本日志的完備性。進而，為了量化事件日志采樣方法所得樣本日志的質量，將樣本日志采用Inductive Miner方法發(fā)現一個流程模型，與原始日志進行一致性檢查，通過擬合度指標來量化原始日志中軌跡可以被樣本模型從頭到尾重演的比例。

最后，通過比較4種事件日志采樣方法針對同一業(yè)務流程事件日志得到的準確度指標和F-measure值，判斷其是否均有效可用。

3.2.2 時間性能分析

時間性能分析實驗通過比較原始日志挖掘時間和采樣挖掘時間(包括原始事件日志采樣時間、樣本日志挖掘時間)的大小來驗證4種事件日志采樣方法的采樣效率，若原始日志挖掘時間比采樣挖掘時間大，則證明采樣方法提高了采樣效率。另外，還對4種采樣方法進行相互比較，從而找出其中最快的采樣方法。

4 工具實現

在開源流程挖掘工具平臺ProM 6中為流程挖掘提供了一個完全可插拔的實驗環(huán)境，其可通過添加插件進行擴展，目前包括1 600多個插件，該工具和所有插件都是開源的。本文所提4種事件日志采樣技術已作為插件(稱為Business Process Event Log Sampling Plugin)在ProM中實現，該工具的快照如圖3和圖4所示，其以一個事件日志作為輸入，選擇采樣方法后輸出一個樣本日志。

在驗證面向日志完備性的4種事件日志采樣方法的模型質量評估實驗中，采用圖5所示的在ProM平臺中實現的Compare two event log dfg sampling Plugin插件與原始日志和樣本日志的邊集(即直接跟隨活動關系集合)、頂點集(即活動集合)進行比較，該插件以原始事件日志和樣本日志為輸入，直接輸出比較結果。

5 實驗評估

本章介紹對面向日志完備性的事件日志采樣方法進行實驗時使用的事件日志數據集，然后分析模型質量評估和時間性能評估兩個實驗的結果。本次實驗評估采用一臺2.70 GHz CPU、Windows 10專業(yè)版、Java SE 1.8.0_281(64位)和Python 3.7.6(64位)的筆記本電腦，并分配有12 GB RAM。

5.1 實驗數據集

實驗共使用9個公開事件日志數據集(https://figshare.com/articles/dataset/Event_Log_Sampling_Datasets/20354505)，分別對所提4種事件日志采樣方法進行實驗評估。表1所示為這些事件日志的部分主要統計數據，包括軌跡數、變體數、事件數、活動數，以及軌跡長度的一些信息。

(1)exercise數據集 該數據集是由論文評審流程模型生成的仿真日志，每條軌跡均詳細清晰地描述了評審論文的流程。

(2)training_log_1/3/8數據集 這3個數據集是人工訓練的用于2016年流程發(fā)現競賽(PDC 2016)的仿真日志，每條軌跡由事件所引用的流程模型活動的名稱和事件所屬案例的標識符兩個值組成。

(3)Production數據集 該數據集包括生產流程中的流程數據，每條軌跡包括案例、活動、資源、時間戳和更多數據字段的數據。

(4)BPIC_2012_A/O/W數據集 該數據集源自荷蘭一家金融機構的個人貸款申請流程，事件日志中表示的流程是全球融資組織中個人貸款或透支的申請流程，每條軌跡描述了不同客戶申請個人貸款的流程。

(5)CrossHospital數據集 該數據集包括醫(yī)院急診病人的治療流程數據，每條軌跡表示醫(yī)院里一位急癥患者的治療流程。

表1 實驗日志概述

續(xù)表1

5.2 模型質量評估結果

模型質量評估實驗得到的有向圖比較結果如圖6所示，示例日志采用BPIC_2012_W數據集，示例方法為完全遍歷采樣法，因為其他3種采樣方法與該方法結果相同，所以不再贅述。采用Python方式比較原始日志直接跟隨圖和樣本日志直接跟隨圖，得到的比較結果相同，表明從樣本日志中發(fā)現的流程模型可有效替代從原始日志中發(fā)現的流程模型。通過對9個公開事件日志數據集進行實驗，并比較返回的結果可知，原始事件日志與樣本日志的邊集和頂點集均相同，證明了4種事件日志采樣方法能夠保證日志的完備性。

首先根據原始事件日志和4種事件日志采樣方法對應的樣本日志得到的Petri網[2]進行擬合度測量，測出的擬合度均為1(如圖7)，證明4種事件日志采樣方法能夠保證從樣本日志中發(fā)現的模型可以完全代表原始日志中的行為，即100%擬合，有力地證明了所提采樣方法能夠保證日志采樣質量。

測得的準確度如圖8所示。通過柱狀圖可以發(fā)現，對于同一業(yè)務流程事件日志，即使選擇的采樣方法不同，得到的準確度值也完全相同，證明4種事件日志采樣方法相互之間的結果沒有偏差，均可在保證日志完備性的前提下進行采樣。最后根據準確度和擬合度計算出的F-measure值如圖9所示，可見雖然不同業(yè)務流程事件日志的F-measure值不同，但是相同事件日志使用不同采樣方法得到的結果完全相同，進一步印證了4種事件日志采樣方法的可行性與高效性，是符合預期的。

5.3 時間性能分析結果

實驗共測量并記錄了3種類型的時間:①原始日志挖掘時間；②使用4種采樣方法的采樣時間；③樣本日志挖掘時間。由于每次實驗時電腦內部環(huán)境可能存在差異，且每次測出的時間與上次相比不可能完全相同，為了保證實驗結果的準確性，對9個事件日志應用4種采樣方法的3個時間分別測量5次取平均值，最后將4種采樣方法各自的采樣時間與樣本日志挖掘時間求和，再與原始日志挖掘時間比較。

時間性能分析結果如圖10所示，圖中縱坐標為實驗使用的采樣方法，分別為本文所提的4種采樣方法和未使用采樣方法(Non-Sampling)。

實驗得到如下3個結論：

(1)將樣本日志與原始日志比較，當日志規(guī)模較大時，樣本日志挖掘時間遠小于原始日志挖掘時間，證明使用樣本日志替代原始日志進行相應操作可以極大提高操作效率。

(2)執(zhí)行時間和質量通常會隨日志規(guī)模的減小而縮減，不同的是，執(zhí)行時間隨日志規(guī)模的減小而急劇縮短，事件日志的規(guī)模越大，原始日志采樣時間與樣本日志挖掘時間之和小于原始日志挖掘時間越多。因此，在實際應用時，可以考慮根據具體需求在發(fā)現效率和樣本日志質量之間尋找平衡點，通過選擇合適的采樣方法對原始日志進行處理，從而優(yōu)化流程挖掘流程，加快操作速度，提高準確度。

(3)通過比較4種采樣方法的結果可見，隨著原始事件日志規(guī)模的增大，雖然4種采樣方法得到的樣本日志挖掘時間相差無幾，但是采樣時間之間的差異呈遞增趨勢。相比其他3種采樣方法，在保證樣本日志質量的前提下，基于軌跡長度的采樣方法的采樣時間最短。

6 結束語

給定一個大規(guī)模事件日志，為了高效地從中選擇能夠保證日志完備性的代表性樣本日志，本文提出完全遍歷采樣法、集合覆蓋采樣法、基于軌跡長度的采樣方法和基于軌跡頻次的采樣方法4種事件日志采樣方法，并從時間性能分析和模型質量評估兩方面評估樣本日志相對原始日志的質量。所提4種采樣方法已作為插件在開源流程挖掘工具平臺ProM6中實現。在9個公開事件日志數據集上的實驗結果表明，相比已有采樣方法，所提4種采樣方法不僅能夠大幅提高日志采樣效率，還能保證模型的完整性。

未來將從3個方面進行深入研究：①本文在探討4種事件日志采樣方法的有效性時只針對普通事件日志，未來將研究包含生命周期信息的事件日志采樣方法;②在分布式系統[22]上部署4種事件日志采樣方法，以便處理現實生活中其他信息系統收集的超大規(guī)模事件日志;③將本文所提事件日志采樣方法應用于面向特定領域的事件日志，如教育、醫(yī)療、金融、制造業(yè)等。