用于流程發(fā)現(xiàn)的局部日志采樣方法

倪 可，俞東進+，孫笑笑，胡 華

(1.杭州電子科技大學 計算機學院，浙江 杭州 310018；2.杭州師范大學，浙江 杭州 311121)

0 引言

流程挖掘旨在從企業(yè)組織的信息管理系統(tǒng)中提取業(yè)務流程相關見解，其核心理念為發(fā)現(xiàn)、監(jiān)測和改進真實的業(yè)務流程[1]。流程發(fā)現(xiàn)是流程挖掘的一個分支領域，其主要任務是從事件日志中構(gòu)建流程模型，達到更好地理解和分析業(yè)務流程的目的。

事件日志是提取流程模型的基礎。近年來，隨著物聯(lián)網(wǎng)、大數(shù)據(jù)等技術(shù)的快速發(fā)展，企業(yè)有了更多獲取和存儲事件日志的手段，使事件日志的規(guī)模呈幾何級別增長?，F(xiàn)有的流程發(fā)現(xiàn)算法，如Alpha挖掘算法[2]、啟發(fā)式流程挖掘算法[3]、歸納算法[4]等，將完整的事件日志作為輸入構(gòu)建相應的流程模型，然而這些流程挖掘算法往往有多個可調(diào)整的參數(shù)，從而使流程發(fā)現(xiàn)成為一個漫長的探索性過程，尤其在將其應用于大規(guī)模事件日志時，可能需要較長的處理時間，導致流程發(fā)現(xiàn)效率低下。

為了應對大規(guī)模的事件日志，常采用分而治之的思想，將流程發(fā)現(xiàn)問題分解為若干個規(guī)模較小的子問題[5]；另一種做法則是利用分布式計算提高流程發(fā)現(xiàn)的效率，例如EVERMANN[6]在MapReduce平臺上復現(xiàn)并擴展了Alpha挖掘算法和啟發(fā)式流程挖掘算法，使這兩種著名的流程挖掘算法得以擴展應用到大規(guī)模、分布式存儲數(shù)據(jù)集上。

除了改進現(xiàn)有挖掘算法，對完整的事件日志進行采樣則是一種從根本上提高流程發(fā)現(xiàn)效率的方法[7]。這種做法的依據(jù)是，事件日志中存在大量相似或重復的行為，只有一小部分日志記錄了導致流程模型發(fā)生變動的“新信息”。因此，將大規(guī)模的事件日志通過采樣縮減到可快速處理的大小是一種十分有效的方式。

綜上所述，本文的研究目標是從完整的事件日志中得到一個規(guī)模較小且信息損失較少的日志子集(文中稱為采樣日志)用于流程發(fā)現(xiàn)，主要解決3個問題：①從完整事件日志中提取控制流信息；②衡量采樣日志的質(zhì)量；③在事件日志存在大量重復軌跡的情況下避免遍歷重復軌跡。

因此，本文提出一種適用于流程發(fā)現(xiàn)的、基于軌跡信息增量的局部日志采樣方法，該方法從控制流和特征屬性兩個角度對軌跡所包含的信息進行量化，通過比較一條軌跡和已采樣日志之間的信息差異來判斷該軌跡是否記錄了新的流程行為。特別地，由于現(xiàn)有的日志采樣方法大都需要對完整的事件日志進行至少一次遍歷，為了進一步提高采樣速度，本文基于統(tǒng)計理論確定了最小連續(xù)遍歷樣本數(shù)，并提出二進制指數(shù)跳躍算法來處理相似軌跡聚集問題，其核心思想是避免完整掃描事件日志，即對局部日志進行采樣。

1 相關工作

作為流程發(fā)現(xiàn)算法的輸入，事件日志的質(zhì)量也會影響流程發(fā)現(xiàn)的性能和結(jié)果，因此事件日志預處理逐漸得到研究人員的關注。為了發(fā)現(xiàn)更高質(zhì)量的流程模型，一種做法是在應用流程發(fā)現(xiàn)算法之前對事件日志進行分析處理，以刪除或修改事件日志中的離群值行為[8-10]；另一種做法是直接在流程發(fā)現(xiàn)算法中內(nèi)置噪聲過濾機制，如Split Miner[11]，ILP Miner[12]等。上述過濾技術(shù)專注于從事件日志中刪除不頻繁或異常行為，然而過濾低頻率行為對事件日志總體數(shù)量的影響很小，對于大規(guī)模事件日志，流程發(fā)現(xiàn)所需的處理時間仍然很長。

為了提高流程發(fā)現(xiàn)算法的運行速度，一種有效的做法是對大規(guī)模事件日志進行抽樣，這種方法既可以減少業(yè)務流程實例的數(shù)量，又可以增加事件日志的機密性[13]。CARMONA等[14]建議基于軌跡的Parikh向量來檢測事件日志中的行為，然而這種采樣技術(shù)不能用于流程發(fā)現(xiàn)，因為Parikh向量并不存儲對發(fā)現(xiàn)流程模型至關重要的活動序列。為了簡化流程發(fā)現(xiàn)算法在大規(guī)模數(shù)據(jù)集上的應用，BERTI[15]提出一種針對啟發(fā)式流程挖掘算法(heuristic miner)[3]的統(tǒng)計抽樣技術(shù)；LIU等[16]提出一種基于圖的事件日志抽樣排序模型LogRank，該模型基于Google的PageRank[17]，對事件日志中的軌跡進行了重要性排名。對于抽樣方法效用的評價，SANI等[18]比較了多種偏置抽樣方法在不同數(shù)據(jù)集上的表現(xiàn)，發(fā)現(xiàn)與隨機抽樣相比，采用偏置抽樣可以大大加快流程發(fā)現(xiàn)技術(shù)的速度。

2 預備知識

定義1日志、軌跡、事件。事件e指流程執(zhí)行過程中發(fā)生的活動，包括活動名稱和時間戳等特征屬性。所有事件的集合表示為ε，即e∈ε。事件的有序執(zhí)行構(gòu)成一個序列σ=e1,…,en，稱為軌跡，其中ei表示軌跡中第i個發(fā)生的事件。事件日志L={σ1,…,σm}是所有軌跡的集合。

表1所示為一個事件日志的示例。其中，每一條軌跡表示一個流程實例執(zhí)行的完整過程，每個事件表示流程實例中發(fā)生的活動。需要說明的是，事件的特征屬性除了活動名稱和時間戳，可能還有資源、執(zhí)行者等其他屬性，本文只考慮事件的活動名稱和時間戳特征屬性。

表1 事件日志示例

定義2直接跟隨關系。設σ=e1,e2,…,en∈L,則稱ei+1直接跟隨于ei，記為ei?ei+1。為了簡化表達，通常用事件的活動名稱屬性代指事件。

以表1中的事件日志為例，記σ1=A,B,C，稱B直接跟隨于A，C直接跟隨于B，以此類推。

定義3信息增量。設采樣日志為L′，L′是完整事件日志L的子集。若一條軌跡σ含有采樣日志集合L′中未包含的信息，則認為該軌跡是一條帶有新信息的軌跡，用γ(L′,σ)=1表示；反之，γ(L′,σ)=0。

在逐條遍歷事件日志中的軌跡時，采用抽象函數(shù)Ψ提取軌跡中的信息。

定義4控制流(Control Flow)抽象函數(shù)。給定一條軌跡σ，定義控制流抽象函數(shù)

ΨCF(σ)(Aσ,?(σ),estart(σ),eend(σ))。

(1)

式中Aσ為軌跡σ中出現(xiàn)的活動集合；?(σ)為軌跡σ中事件的直接跟隨關系集合；estart(σ)和eend(σ)分別為該軌跡的開始/結(jié)束事件。

(2)

以表1中的兩條軌跡σ1=A,B,C和σ2=A,B為例，假設采樣日志L′中只有σ1一條軌跡，根據(jù)式(1)和式(2)可得而ΨCF(σ2)=({A,B},{A?B},{A},{B})，將σ2加入L′會在中增加新的結(jié)束事件，因此認為σ2是一條帶有新信息的軌跡，即γ(L′,σ2)=1。

軌跡的特征信息不同于事件的特征信息，除了軌跡ID外，軌跡的其他特征屬性一般不會在事件日志中顯式地表示，而是通過計算獲得，如軌跡中事件的數(shù)量、軌跡的持續(xù)時間等。僅關注事件日志的控制流信息所能得到的軌跡數(shù)量有限，因此本文額外使用軌跡的兩個特征(軌跡長度和軌跡持續(xù)時間)來減少信息損失。

定義5軌跡/日志長度。軌跡長度指軌跡中發(fā)生的事件數(shù)量，記為Len(σ)。對于日志L，Len(L)表示日志L中所有軌跡長度的集合。

對于軌跡σ∈L-L′，如果Len(σ)?Len(L′)，則認為軌跡σ是一條帶有新信息的軌跡，并記γ(L′,σ)=1。

為了進一步發(fā)現(xiàn)流程實例之間的差異，本文用軌跡持續(xù)時間來擴充軌跡信息。

定義6軌跡持續(xù)時間。軌跡持續(xù)時間指一個流程實例從開始執(zhí)行到結(jié)束經(jīng)過的時間，計算公式為

T(σ)=eend(σ).timestamp-estart(σ).timestamp。

(3)

軌跡的持續(xù)時間通常是一個細粒度的數(shù)值，從該屬性角度看可以認為幾乎每一條軌跡都引入了新信息。為了減少時間信息帶來的差異，本文用距離函數(shù)d和松弛系數(shù)λ來判斷向L′中加入一條軌跡是否會引入新的信息。σ∈L-L′與L′之間的軌跡持續(xù)時間距離

(4)

式中n為L′中軌跡的數(shù)量。只有當d(L′,σ)大于設定的松弛系數(shù)λ時，才認為該條軌跡引入了新的時間信息。

3 基于軌跡信息增量的日志采樣

3.1 總體框架

本文提出的基于軌跡信息增量的日志采樣方法的總體流程如圖1所示。該方法將完整事件日志作為輸入，首先根據(jù)統(tǒng)計推斷計算出最小連續(xù)遍歷樣本數(shù)量Nmin，然后根據(jù)控制流和軌跡特征判斷每一條軌跡是否帶有新的信息，并將其加入采樣日志。在連續(xù)遍歷Nmin條沒有新信息的軌跡后，采用二進制指數(shù)跳躍算法計算下一次掃描的位置，直到遍歷到事件日志的末尾。

下面詳細介紹最小連續(xù)遍歷樣本數(shù)量的計算方法以及二進制指數(shù)跳躍算法的流程。

3.2 確定最小連續(xù)遍歷樣本數(shù)量

本文的研究目的為快速從大規(guī)模事件日志中采樣出一個高效用的日志子集，其核心思想是避免完整掃描事件日志，即在未知事件日志中軌跡行為分布的情況下進行局部采樣。

基于上述動機，本文基于統(tǒng)計原理作出以下假設：假設L中的每一條軌跡均為獨立同分布，從L中選取n條軌跡樣本，定義p=pi為軌跡σi帶有新信息的概率，即對所有軌跡而言，帶有新信息的概率pi均相同；對于一條軌跡σi，γ(L′,σi)只有1(帶有新信息)或0(不帶有新信息)兩種取值。在此假設之下，可以認為n條樣本軌跡中含有新信息的軌跡數(shù)量x符合二項分布，即x～B(n,p)，在事件日志數(shù)量足夠大的情況下，二項分布近似于正態(tài)分布。

樣本量對于獲得準確的、具有統(tǒng)計意義的結(jié)果非常重要，本文基于Cochran公式[19]計算這一理想樣本量。給定置信水平α、概率約束δ和誤差幅度e，最小連續(xù)遍歷樣本數(shù)量

(5)

式中：z對應于置信水平1-α(單邊假設檢驗)的標準化正態(tài)隨機變量；δ為在L-L′中發(fā)現(xiàn)帶有新信息的軌跡的概率。誤差幅度一般取5%。

例如，當α=0.01且δ=0.05時，由式(5)可得Nmin≥126，即當在日志L中連續(xù)遍歷了126條不帶有新信息的軌跡之后，可以認為在剩余日志中發(fā)現(xiàn)帶有新信息軌跡的概率小于0.05，其置信水平為0.99。

3.3 二進制指數(shù)跳躍算法

上述內(nèi)容從統(tǒng)計理論層面證明，在原始事件日志中掃描了一定數(shù)量不帶有新信息的軌跡后，可以認為在后續(xù)日志中出現(xiàn)帶有新信息的軌跡的概率很小。然而，在真實的事件日志中，相似的流程行為(即無信息增量的軌跡)可能會在一段時間內(nèi)大量出現(xiàn)，將其稱為相似軌跡聚集現(xiàn)象。如果掃描了Nmin條相似軌跡之后就停止采樣，則可能無法在后續(xù)事件日志中發(fā)現(xiàn)新的軌跡，從而出現(xiàn)信息損失。

為了避免相似軌跡聚集導致的信息損失，本文提出二進制指數(shù)跳躍算法，在連續(xù)掃描Nmin條沒有信息增量的相似軌跡后，重新計算下一次掃描的間隔，從而跳過一部分不帶有新信息的軌跡，以保證在后續(xù)事件日志中發(fā)現(xiàn)新軌跡，同時提高預處理的速度。

若在原始事件日志中連續(xù)遍歷了Nmin條不帶有新信息的軌跡，則認為此處發(fā)生相似軌跡聚集，此時從離散的整數(shù)集合[1,2,…,2k]中隨機取出一個數(shù)作為下一次掃描前需要跳過的軌跡數(shù)，其中參數(shù)k的計算公式為

k=min(發(fā)生軌跡聚集的次數(shù),8)。

(6)

掃描的間隔與發(fā)生軌跡聚集的次數(shù)有關。當k≤8時，參數(shù)k等于發(fā)生軌跡聚集的次數(shù)，從[1,2k]中隨機選取一個整數(shù)作為要跳過的軌跡數(shù)量；當k>8時，從[1,28]中隨機選取一個整數(shù)。一旦掃描到一條帶有新信息的軌跡時，即將k恢復為默認值1，并重新開始相似軌跡的計數(shù)。

二進制指數(shù)跳躍算法提供了一個應對相似軌跡聚集現(xiàn)象的方法。在剛開始出現(xiàn)軌跡聚集時，該算法會以一個相對較小的跳躍間隔決定下一條軌跡的索引；而當相似軌跡聚集頻繁出現(xiàn)時，掃描間隔將會以指數(shù)級增加，以快速檢測出下一條帶有新信息的軌跡。二進制指數(shù)跳躍算法有助于提高在完整事件日志中發(fā)現(xiàn)新軌跡的效率，同時避免完整遍歷事件日志導致處理時間過長的問題。

3.4 基于軌跡信息增量的日志采樣算法

基于上述理論，本文提出基于軌跡信息增量的日志采樣算法，該算法首先根據(jù)控制流和軌跡特征屬性判斷原始事件日志L中的軌跡是否帶有新的信息，并將其加入采樣日志L′,然后根據(jù)相似軌跡聚集的情況決定是否需要采用二進制指數(shù)跳躍算法跳過軌跡。算法1描述了基于軌跡信息增量的日志采樣過程。

算法1基于軌跡信息增量的日志采樣算法。

輸入：事件日志L、置信水平α、概率約束δ、誤差幅度e、松弛系數(shù)λ。

輸出：采樣日志L′。

1: L′←?

2: count←0 //記錄重復軌跡的數(shù)量

3: i←0 //軌跡的索引

4: k←1 //記錄發(fā)生相似軌跡聚集的次數(shù)

5: N←(z2*δ*(1-δ))/(e2) //按式(5)計算最小連續(xù)遍歷樣本數(shù)量

6: WHILE i

7: σ←從L中取出一條軌跡

8: γ(L′,σ)←calculate γ(L′,σ) with bound of λ //根據(jù)控制流和特征屬性計算軌跡是否帶有新信息

9: IF γ(L′,σ)=1 THEN

10: count←0

11: k←1

12: ELSE

13: count←count+1

14: IF count>N THEN

15: k←k+1

16: END IF

17: END IF

18: L′←{σ}∪L′ //將軌跡加入采樣日志

19: IF count>N THEN //采用二進制指數(shù)跳躍算法確定需要跳過的軌跡數(shù)量

20: k←min(k,8)

21: i←i+random(1,2k)

22: ELSE

23: i←i+1

24: END IF

25:END WHILE

26:RETURN L′

算法1將原始事件日志L、置信水平α、概率約束δ、誤差幅度e和松弛系數(shù)λ作為輸入，在初始化后(第1～4行)，根據(jù)式(5)計算出最小連續(xù)遍歷樣本數(shù)量Nmin(第5行)；然后順序遍歷事件日志，根據(jù)式(1)～式(4)計算并判斷每條軌跡是否帶有新的信息(第7～8行)；若當前軌跡帶有新的信息，則重置計數(shù)器count和參數(shù)k，并將該軌跡加入采樣日志(第9～18行)；若連續(xù)掃描了Nmin條沒有新信息的軌跡，則采用二進制指數(shù)跳躍算法計算下一次掃描的軌跡索引，直到遍歷到事件日志的末尾(第19～24行)。

毫無疑問，采用二進制指數(shù)跳躍算法在提高預處理速度的同時會引入一定信息損失，然而這種情況對日志采樣的影響未必是負面的。因為事件日志本身就存在一些低頻率的流程行為，這些行為使發(fā)現(xiàn)的流程模型變得復雜而難以分析，所以目前許多流程發(fā)現(xiàn)算法都采用噪聲過濾機制或單獨的預處理步驟事先過濾掉事件日志中的低頻行為。由于在二進制指數(shù)跳躍算法執(zhí)行過程中跳過的軌跡大概率是事件日志中發(fā)生頻率較低的軌跡，所帶來的信息損失可以看作為噪聲處理步驟的一部分，其對流程模型的發(fā)現(xiàn)有積極的作用，這部分內(nèi)容將在第5章通過適應度(fitness)實驗詳細論證。

4 實驗設計

4.1 實驗環(huán)境與參數(shù)設置

本文實驗采用Python語言編寫(Python的版本為3.6.5)，采用PM4PY庫對事件日志進行統(tǒng)計分析。實驗環(huán)境配置如下：操作系統(tǒng)為Windows 10專業(yè)版64位；處理器為Intel(R) Core(TM) i7-6500U (2.50 GHz)；內(nèi)存為12.0 GB。

本文采用歸納算法Inductive Miner的一種變體——IMi(inductive miner infrequent)作為流程發(fā)現(xiàn)算法。IMi算法根據(jù)事件的直接跟隨關系將日志轉(zhuǎn)化為直接跟隨圖，并基于事件發(fā)生的頻率處理日志中的不頻繁行為(噪聲)，使其可以適用于真實的事件日志。本實驗用默認值0.2作為IMi算法的噪聲閾值。在對事件日志采樣時，設置α=0.01，δ=0.05，松弛系數(shù)λ是實驗中的一個可控變量，所有實驗均取10次實驗運行結(jié)果的平均值作為最終結(jié)果。

4.2 實驗數(shù)據(jù)

本文選擇在4個公開的真實事件日志數(shù)據(jù)集上驗證日志采樣算法的有效性。所有數(shù)據(jù)集均來自4TU Centre for Research Data (https://data.4tu.nl/)，數(shù)據(jù)集的詳細信息如表2所示。

表2 真實事件日志的詳細信息

4.3 評價指標

本文從3個方面評價日志采樣算法的性能：

(1)軌跡數(shù)量、直接跟隨關系數(shù)量和變體數(shù)量 通過比較采樣日志的大小，即采樣日志中包含的軌跡數(shù)量，來衡量采樣的有效性。除軌跡數(shù)量外，本實驗還將研究采樣日志中保留的事件直接跟隨關系和變體的數(shù)量。

(2)效率 效率分為采樣時間和挖掘時間兩部分。采樣時間指對原始事件日志進行預處理的時間，挖掘時間指從采樣日志中發(fā)現(xiàn)流程模型的時間。將采樣時間和挖掘時間擬合得到效率的值，效率(ms)=采樣時間(ms)+挖掘時間(ms)，然后與從完整事件日志中挖掘出流程模型的時間進行比較。

(3)適應度 用于評估流程模型捕獲了多少事件日志中的行為，當適應度取值為1時，表示流程模型可以完美地描述日志中存在的所有行為。實驗首先從采樣日志中挖掘出流程模型，然后采用基于標記重放的一致性檢查方法[20]在流程模型上重放原始的事件日志，從而計算出流程模型的適應度。

5 實驗結(jié)果

實驗1探究日志采樣的有效性，圖2所示為不同λ值對采樣日志中軌跡數(shù)量的影響，作為參考值，λ=0時采樣日志中的軌跡數(shù)量與原始事件日志中的相同?？梢娫?個數(shù)據(jù)集上，隨著松弛系數(shù)λ的增加，軌跡數(shù)量均呈現(xiàn)下降趨勢，并在λ值較大時趨于平穩(wěn)。值得注意的是，在λ=20時，所有數(shù)據(jù)集的軌跡數(shù)量都下降到了原始數(shù)量的40%左右，說明在真實事件日志中，大部分軌跡(60%左右)在持續(xù)時間上的差異比較小(小于20)，因此軌跡數(shù)量會在λ為0～20這一階段大幅下降。圖2證明本文采樣方法可以有效減小事件日志的規(guī)模。

減小事件日志規(guī)模可以有效提高流程發(fā)現(xiàn)的效率，圖3所示為在4個數(shù)據(jù)集上進行采樣和流程挖掘的時間。隨著松弛系數(shù)λ值的增加，采樣的日志規(guī)模越小，流程挖掘的總體效率越高，說明IMi挖掘算法的執(zhí)行時間和事件日志規(guī)模成正比，通過采樣減小事件日志的規(guī)模是提高效率最有效的手段。本文采樣方法使IMi算法的挖掘速度在4個數(shù)據(jù)集上均有不同程度的提高，表3所示為λ=150時IMi算法在完整日志和采樣日志上挖掘的效率差異。除此之外，圖3還單獨標出了進行日志采樣花費的時間，這一時間相對于采用IMi算法進行流程發(fā)現(xiàn)的時間可以忽略不計，證明本文的采樣算法十分高效。

表3 IMi算法的挖掘效率(λ=150) ms

圖4所示為采用IMi算法從完整/局部采樣日志中挖掘出的流程模型的適應度差異。因為IMi算法自身帶有噪聲過濾機制，所以在4個數(shù)據(jù)集上，從完整事件日志中挖掘出的流程模型的適應度均未達到1，但都在0.95以上，而從采樣日志中挖掘出的流程模型在4個數(shù)據(jù)集上的適應度也都達到和完整日志相近的水平，證明大規(guī)模事件日志中的確存在大量重復的軌跡，使用完整日志的一小部分就可以發(fā)現(xiàn)較高質(zhì)量的流程模型，而且采樣日志中高頻行為的比例與完整日志中相似。特別地，圖4顯示二進制指數(shù)跳躍算法造成的信息損失對流程模型適應度的影響不同。在BPIC_2013數(shù)據(jù)集上，從采樣日志中挖掘出的流程模型比從完整事件日志中挖掘出的流程模型的適應度低，說明二進制指數(shù)跳躍算法跳過了一些帶有新信息且發(fā)生頻率較高的軌跡，可能因為本文設置的掃描跳躍間隔對于小規(guī)模數(shù)據(jù)集范圍過大。而流程模型在數(shù)據(jù)集BPIC_2012和數(shù)據(jù)集HB上的適應度略高于從完整事件日志中挖掘出的流程模型，原因是采用基于信息增量的采樣方法捕獲且放大了原始事件日志中的低頻行為，這些行為包含額外的控制流信息，從而使流程模型能更完美地匹配事件日志。在RTF數(shù)據(jù)集上，兩個流程模型的適應度幾乎相同，證明二進制指數(shù)跳躍算法帶來的信息損失與IMi的噪聲過濾機制類似，即跳過的軌跡為原始事件日志中的低頻率軌跡。

實驗2對不同的采樣策略性能進行比較。實驗采用基于軌跡頻率的采樣方法，并將隨機采樣方法作為對照，其中基于軌跡頻率的采樣方法選取事件日志中發(fā)生頻率最高的軌跡加入采樣日志，隨機采樣方法則隨機地從事件日志中抽取軌跡。為了保證實驗的公平性，在所有數(shù)據(jù)集上都將采樣率控制在30%左右(采樣率=采樣日志的大小/完整日志的大小)。

直接跟隨關系是體現(xiàn)控制流信息最關鍵的因素，采樣日志能在多大程度上保留直接跟隨關系決定了流程模型的最終結(jié)構(gòu)。圖5a所示為基于不同采樣策略得到的采樣日志中保留的直接跟隨關系的數(shù)量。該結(jié)果表明，本文采樣方法能夠保留原始日志中88%以上的直接跟隨關系，特別在BPIC_2013數(shù)據(jù)集上，采樣日志保留了所有的直接跟隨關系。圖5b所示為不同采樣日志中保留的變體數(shù)量之間的差異。變體是一組共享相同控制流信息的軌跡，即軌跡中活動出現(xiàn)的順序相同，不同變體之間的直接跟隨關系可能相同，因此并不是每一個新的變體都會在流程模型中提供新的信息。以BPIC_2012數(shù)據(jù)集為例，采樣日志僅保留了1 422種流程變體(總共有4 366種流程變體)，而這些變體涵蓋了96%的直接跟隨關系(120/125)，即本文采樣算法雖然過濾掉了大部分直接跟隨關系重復的變體，大大減少了事件日志的規(guī)模，但是仍然能從日志中挖掘出高質(zhì)量的流程模型。除此之外，圖5中基于軌跡頻率的采樣方法得到的直接跟隨關系和變體數(shù)量都很少，這是由于相同控制流的軌跡在事件日志中大量重復出現(xiàn)導致的；而隨機采樣方法雖然可以發(fā)現(xiàn)更多的控制流信息，但是仍然少于本文的采樣方法。

最后從采樣時間上比較不同策略的性能，如圖6所示。在3種采樣方法中，速度最快的是隨機采樣，原因是該方法無需進行額外計算。本文方法僅次于隨機采樣，證明采用二進制指數(shù)跳躍算法避免對完整日志進行掃描可以有效提高采樣效率。

6 結(jié)束語

本文提出一種基于軌跡信息增量的日志采樣方法，首先從事件日志中抽象出控制流信息和特征屬性信息，用于比較軌跡攜帶的信息量；然后采用二進制指數(shù)跳躍算法避免遍歷重復或相似軌跡，達到提高預處理效率的目的。在4個真實事件日志上的實驗表明，本文采樣方法可以快速有效地將大規(guī)模的事件日志采樣到一個可管理的大小，能夠保證從采樣日志中挖掘出的流程模型的質(zhì)量。未來將比較各種采樣策略的有效性，并在發(fā)生流程概念漂移的情況下對新版本的流程日志進行區(qū)分和采樣。