面向日志完備性的事件日志采樣方法

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

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

0 引言

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

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

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

1 基礎(chǔ)知識(shí)

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

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

定義2流程發(fā)現(xiàn)。設(shè)UM是所有流程模型的集合，一個(gè)流程發(fā)現(xiàn)方法指從一個(gè)事件日志L∈B(A*)映射到一個(gè)流程模型pm∈UM的函數(shù)γ，即γ(L)=pm。一般來說，流程發(fā)現(xiàn)方法能夠?qū)⑹录罩巨D(zhuǎn)換為有標(biāo)記的Petri網(wǎng)、業(yè)務(wù)流程建模標(biāo)注(Business Process Modeling Notation，BPMN)、流程樹等表示的流程模型。無論流程模型采用什么表示方法，輸入事件日志中的每個(gè)軌跡都對(duì)應(yīng)發(fā)現(xiàn)的流程模型中的一個(gè)可能的執(zhí)行序列。

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

2 方法概述

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

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

為了實(shí)現(xiàn)這些研究目標(biāo)，圖1展示了所用方法的概述，包括以下兩個(gè)階段:

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

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

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

(2)階段2——采樣技術(shù)的有效性評(píng)估

為驗(yàn)證4種事件日志采樣方法的有效性，提出兩種評(píng)估方法：

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

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

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

本章首先給出4種事件日志采樣方法的具體思路，其次介紹兩種實(shí)驗(yàn)評(píng)估方法。下面給出一個(gè)示例日志(表示為L)，用于介紹面向事件日志完備性的采樣方法。該日志包括5條軌跡，共有5個(gè)變體和6個(gè)事件，記σ(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的軌跡的初始點(diǎn)集合StartSet、結(jié)束點(diǎn)集合EndSet、日志直接跟隨關(guān)系集合dfrSetLog和軌跡直接跟隨關(guān)系集合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 完全遍歷采樣法

完全遍歷采樣法的思路如下：從原始事件日志第一條軌跡開始依次遍歷，若軌跡的直接跟隨關(guān)系集合與日志直接跟隨關(guān)系集合有交集，且滿足軌跡的開始點(diǎn)與開始點(diǎn)集合有交集或軌跡的結(jié)束點(diǎn)與結(jié)束點(diǎn)集合有交集，則將該條軌跡加入樣本日志，并刪除以下3部分：①日志直接跟隨關(guān)系集合與新軌跡的直接跟隨關(guān)系集合的交集；②開始點(diǎn)集合與新軌跡開始點(diǎn)的交集；③結(jié)束點(diǎn)集合與新軌跡結(jié)束點(diǎn)的交集。直到日志直接跟隨關(guān)系集合、開始點(diǎn)集合、結(jié)束點(diǎn)集合均為空，停止軌跡遍歷。完全遍歷采樣法的偽代碼如算法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(算法結(jié)束)

3.1.2 集合覆蓋采樣法

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

算法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(算法結(jié)束)

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

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

根據(jù)定義4，基于軌跡長度的采樣方法思想如下：首先統(tǒng)計(jì)原始事件日志中每條軌跡的長度，將軌跡和其對(duì)應(yīng)的長度存儲(chǔ)到一個(gè)集合中；然后按照軌跡長度降序排列，從最長的軌跡開始依次向下遍歷，篩選樣本日志軌跡的方法與完全遍歷采樣法相同?；谲壽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(算法結(jié)束)

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

根據(jù)定義5，基于軌跡頻次的采樣方法思想如下：從原始事件日志的第1條軌跡開始，依次統(tǒng)計(jì)每條軌跡出現(xiàn)的次數(shù)，同時(shí)將軌跡和其對(duì)應(yīng)的頻次存儲(chǔ)到一個(gè)集合中；統(tǒng)計(jì)完成后進(jìn)行去重操作，只保留相同軌跡的頻次最大值；最后按照軌跡頻次降序排列，從頻次最大的軌跡開始依次向下遍歷，篩選樣本日志軌跡的方法與完全遍歷采樣法相同。基于軌跡頻次的采樣方法偽代碼如算法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(算法結(jié)束)

3.2 采樣方法的有效性評(píng)估

為了系統(tǒng)地評(píng)估4種采樣方法得到的樣本日志相比原始日志的質(zhì)量，同時(shí)與之前的采樣方法進(jìn)行比較，本文采用模型質(zhì)量評(píng)估和時(shí)間性能分析兩種評(píng)估方法。

3.2.1 模型質(zhì)量評(píng)估

為了評(píng)估模型質(zhì)量，先引入直接跟隨活動(dòng)關(guān)系集合和樣本日志完備性定義：

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

因?yàn)橛邢驁D可分別對(duì)比樣本日志和原始日志對(duì)應(yīng)的直接跟隨圖、邊集(即直接跟隨活動(dòng)關(guān)系集合)和頂點(diǎn)集(即活動(dòng)集合)，所以模型質(zhì)量評(píng)估實(shí)驗(yàn)通過比較原始日志和樣本日志的有向圖是否相同，來間接驗(yàn)證樣本日志相比原始日志的質(zhì)量，從而判斷采樣方法是否保證了樣本日志的完備性。進(jìn)而，為了量化事件日志采樣方法所得樣本日志的質(zhì)量，將樣本日志采用Inductive Miner方法發(fā)現(xiàn)一個(gè)流程模型，與原始日志進(jìn)行一致性檢查，通過擬合度指標(biāo)來量化原始日志中軌跡可以被樣本模型從頭到尾重演的比例。

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

3.2.2 時(shí)間性能分析

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

4 工具實(shí)現(xiàn)

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

在驗(yàn)證面向日志完備性的4種事件日志采樣方法的模型質(zhì)量評(píng)估實(shí)驗(yàn)中，采用圖5所示的在ProM平臺(tái)中實(shí)現(xiàn)的Compare two event log dfg sampling Plugin插件與原始日志和樣本日志的邊集(即直接跟隨活動(dòng)關(guān)系集合)、頂點(diǎn)集(即活動(dòng)集合)進(jìn)行比較，該插件以原始事件日志和樣本日志為輸入，直接輸出比較結(jié)果。

5 實(shí)驗(yàn)評(píng)估

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

5.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

(3)Production數(shù)據(jù)集 該數(shù)據(jù)集包括生產(chǎn)流程中的流程數(shù)據(jù)，每條軌跡包括案例、活動(dòng)、資源、時(shí)間戳和更多數(shù)據(jù)字段的數(shù)據(jù)。

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

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

表1 實(shí)驗(yàn)日志概述

續(xù)表1

5.2 模型質(zhì)量評(píng)估結(jié)果

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

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

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

5.3 時(shí)間性能分析結(jié)果

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

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

實(shí)驗(yàn)得到如下3個(gè)結(jié)論：

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

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

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

6 結(jié)束語

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

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