劉 聰, 張帥鵬, 李會玲, 何 華, 曾慶田

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

0 引言

過程挖掘[1-3]旨在從事件日志中提取有關(guān)業(yè)務(wù)過程的有效信息,從而發(fā)現(xiàn)、監(jiān)控和改進(jìn)實(shí)際過程。過程挖掘主要包括過程發(fā)現(xiàn)、合規(guī)性檢查、過程增強(qiáng)與改進(jìn)3方面,其中過程發(fā)現(xiàn)是最具挑戰(zhàn)性的過程挖掘任務(wù)之一,它允許在不使用任何先驗(yàn)信息的情況下從事件日志中發(fā)現(xiàn)過程模型。在過去20年中,學(xué)者們已經(jīng)提出各種過程發(fā)現(xiàn)方法,如Alpha Miner[4],Heuristic Miner[5],Inductive Miner[6]等。

然而,大多數(shù)過程發(fā)現(xiàn)方法只關(guān)注單個(gè)機(jī)器上的模型發(fā)現(xiàn)。實(shí)際上,由于I/O和內(nèi)存等硬件的限制,隨著當(dāng)前信息系統(tǒng)中可用數(shù)據(jù)的增長,大部分過程發(fā)現(xiàn)方法都不再適用于單個(gè)機(jī)器處理整個(gè)大規(guī)模數(shù)據(jù)集,大規(guī)模事件日志對這些發(fā)現(xiàn)方法的性能提出了新的挑戰(zhàn)?，F(xiàn)有大多數(shù)過程發(fā)現(xiàn)方法不能正確挖掘大規(guī)模事件日志中的信息,導(dǎo)致過程發(fā)現(xiàn)算法效率低下。例如,已有過程發(fā)現(xiàn)方法在處理大規(guī)模事件日志時(shí),容易產(chǎn)生高度難以理解的意大利面模型[7];VAN DER AALST教授與其團(tuán)隊(duì)在過程挖掘宣言[8]中曾以ASML光刻機(jī)系統(tǒng)產(chǎn)生的海量數(shù)據(jù)為例,說明現(xiàn)有過程挖掘方法難以處理大規(guī)模事件日志,并將處理大規(guī)模復(fù)雜事件日志問題作為過程挖掘的重要挑戰(zhàn)之一。

對于大規(guī)模事件日志,一個(gè)有效的處理方法是用MapReduce重新實(shí)現(xiàn)一些過程發(fā)現(xiàn)方法,使其可擴(kuò)展到大規(guī)模事件日志數(shù)據(jù)集。EVERMANN[9]重寫了Alpha Miner和Heuristic Miner的MapReduce實(shí)現(xiàn)過程。然而,重寫實(shí)現(xiàn)的過程非常耗時(shí),需要開發(fā)人員深入了解底層發(fā)現(xiàn)方法。另外,重新實(shí)現(xiàn)技術(shù)為特定方法定制,并不適用于其他挖掘算法,例如文獻(xiàn)[9]中的方法無法適用于近年來提出的Inductive Miner。另一方面,重新實(shí)現(xiàn)技術(shù)并未降低事件日志的規(guī)模,過程發(fā)現(xiàn)的效率未得到實(shí)質(zhì)性改變。

事件日志采樣技術(shù)不是重新實(shí)現(xiàn)現(xiàn)有的發(fā)現(xiàn)方法,而是提供了一種提高發(fā)現(xiàn)效率的替代方法。通過采樣技術(shù)得到的樣本日志是原始日志的代表性子集,按照“一次采樣,多次使用”的原則,可將得到的樣本日志保留下來,以便用于后續(xù)的過程發(fā)現(xiàn)、合規(guī)性檢查、過程增強(qiáng)與改進(jìn)等,避免每次使用原始日志時(shí)出現(xiàn)效率低等問題,從而極大提高工作效率。

前期工作[10-11]中,筆者在PageRank算法的基礎(chǔ)上實(shí)現(xiàn)了一個(gè)基于圖排序的LogRank事件日志采樣技術(shù),其以任意事件日志為輸入來獲取樣本日志,因?yàn)闃颖救罩颈仍既罩拘〉枚?所以處理效率也更高。雖然該采樣技術(shù)有助于提高過程發(fā)現(xiàn)效率,但是在處理大規(guī)模事件日志時(shí)采樣算法本身非常耗時(shí)。于是LIU等[12]提出一種基于軌跡相似度計(jì)算的LogRank+事件日志采樣技術(shù),與基于LogRank的事件日志采樣技術(shù)相比,該方法在確保采樣質(zhì)量的前提下縮短了采樣時(shí)間,提高了采樣效率。然而,當(dāng)前已有采樣算法在處理一些大規(guī)模事件日志時(shí)仍需花費(fèi)大量時(shí)間才能完成采樣,采樣時(shí)間還需進(jìn)一步提升。

鑒于此,本文提出一種新的基于排序的事件日志采樣方法LogRank++。首先計(jì)算事件日志中的活動(dòng)和直接跟隨活動(dòng)關(guān)系的重要性,然后計(jì)算每條軌跡的重要性,最后根據(jù)重要性值進(jìn)行排序,選擇最重要的軌跡組成樣本日志。另外,從采樣質(zhì)量和采樣效率兩方面考慮,從過程發(fā)現(xiàn)的角度與已有采樣技術(shù)對比,說明所提采樣技術(shù)的高效性。

1 基礎(chǔ)知識

本章首先介紹在采樣技術(shù)中使用的基本術(shù)語。

假設(shè)S是一個(gè)集合,?表示空集,|S|表示集合S中的元素個(gè)數(shù),B(S)表示集合S所有多集的集合。

f:X→Y是一個(gè)函數(shù),其中dom(f)為其定義域,cod(f)={f(x)|x∈dom(f)}為其值域。定義在集合S上長度為n的序列(sequence)是一個(gè)函數(shù)σ:{1,2,…,n}→S。若σ(1)=a1,σ(2)=a2,σ(3)=a3,…,σ(n)=an,則σ=。|σ|表示序列σ的長度,包括空序列|<>|=0。S*表示定義在集合S上所有任意長度有限序列的集合。

例如,L=[2,4,,3,]是一個(gè)事件日志,該日志包含11條軌跡,共有5個(gè)軌跡變體和5個(gè)活動(dòng),L()=2。

事件日志可被視為軌跡的多重集合,因?yàn)榭赡苡卸鄠€(gè)過程實(shí)例(或案例)具有相同的軌跡,每個(gè)軌跡描述了特定實(shí)例(或案例)的生命周期。過程發(fā)現(xiàn)以事件日志為輸入,返回一個(gè)過程模型。

定義2過程發(fā)現(xiàn)[11]。設(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)語言、事件驅(qū)動(dòng)過程鏈(Event-driven Process Chain,EPC)等表示的過程模型。無論過程模型采用什么表示方法,輸入事件日志中的每個(gè)軌跡都對應(yīng)于發(fā)現(xiàn)的過程模型中的一個(gè)可能的執(zhí)行序列。然而已有過程發(fā)現(xiàn)方法不能有效挖掘出大規(guī)模事件日志中的信息,有必要對事件日志進(jìn)行采樣處理。

定義3事件日志采樣[12]。事件日志采樣技術(shù)指將一個(gè)事件日志L∈B(A*)映射到另一個(gè)事件日志L′∈B(A*)的函數(shù),其中L′?L,L為原始事件日志,L′是L的一個(gè)采樣日志。

根據(jù)定義3,事件日志采樣技術(shù)將原始事件日志作為輸入,并返回原始事件日志的一個(gè)子集。

2 研究問題和方法概述

本章首先提出兩個(gè)將要解決的研究問題,即獲取樣本日志的高效方法和評估樣本日志是否具有代表性。然后,概述了本文提出的解決方案,系統(tǒng)闡述了本文的主要方法思想。

2.1 研究問題

本文需要解決的問題如下:

(1)如何找到一種高效的方法來獲取一個(gè)樣本日志,使該樣本日志足以代表原始事件日志中的所有(或大多數(shù))軌跡行為。

(2)從過程挖掘的角度如何衡量一個(gè)樣本日志相對于原始日志具有代表性。

本文對問題(1)的解答將提供一種將大規(guī)模事件日志采樣為相對較小的樣本日志的采樣方法,用于高效地發(fā)現(xiàn)過程模型;問題(2)的答案用于評估樣本日志相對于原始事件日志的質(zhì)量。

2.2 方法概述

圖1所示為本文方法架構(gòu)圖,包括以下兩個(gè)階段:

階段1事件日志采樣。

本文提出一種基于LogRank++的事件日志采樣方法,將原始事件日志和用戶輸入的采樣率作為輸入,根據(jù)軌跡的重要性將日志中的軌跡排序,獲取一組最重要的軌跡組成樣本日志作為輸出。樣本日志本質(zhì)上是原始事件日志的子集。

階段2采樣技術(shù)的高效性評估。

給定一種事件日志采樣技術(shù),可以從以下兩個(gè)角度評估高效性。

(1)采樣質(zhì)量 為了量化樣本日志的質(zhì)量,首先從樣本日志中發(fā)現(xiàn)一個(gè)過程模型,發(fā)現(xiàn)的模型應(yīng)該保證100%樣本日志擬合度;然后通過測量原始日志和該過程模型之間的擬合度值來量化樣本日志的質(zhì)量。

(2)采樣效率 采樣效率可以通過獲取樣本日志所花費(fèi)的時(shí)間來量化,采樣技術(shù)花費(fèi)的時(shí)間越少,采樣效率越高。

3 基于LogRank++的業(yè)務(wù)過程事件日志采樣

本章首先給出一個(gè)示例事件日志,用于介紹后續(xù)采樣方法,然后詳細(xì)介紹基于LogRank++的業(yè)務(wù)過程事件日志采樣方法,最后通過量化所獲樣本日志的質(zhì)量和采樣效率兩方面來評估采樣技術(shù)的高效性,借助該評估方法對真實(shí)事件日志進(jìn)行實(shí)驗(yàn)質(zhì)量評估。

3.1 事件日志示例

3.2 基于LogRank++的業(yè)務(wù)過程事件日志采樣方法

事件日志采樣技術(shù)旨在選擇一個(gè)原始事件日志的代表性子集,以便更高效地進(jìn)行分析。在一個(gè)事件日志中,如果一條軌跡包含整個(gè)事件日志的更多信息(或行為),則該軌跡比其他軌跡更重要,這里的信息(或行為)指活動(dòng)、直接跟隨活動(dòng)關(guān)系等。因此,一條軌跡的重要性可以通過其活動(dòng)重要性和直接跟隨活動(dòng)關(guān)系重要性來量化?；谶@一思想,提出一種基于排序的業(yè)務(wù)過程事件日志采樣技術(shù),記作LogRank++,通過計(jì)算軌跡的重要性值對軌跡進(jìn)行排序,然后選擇重要程度最高的軌跡構(gòu)造樣本日志。

為了度量軌跡重要性,首先要獲得事件日志中包含的軌跡變體σ及其頻次L(σ),在示例日志LC中包含的變體及其頻次如表1所示;然后,統(tǒng)計(jì)原始事件日志中的活動(dòng)數(shù)和直接跟隨活動(dòng)關(guān)系數(shù)量。

表1 事件日志LC中的變體及其頻次

定義4直接跟隨活動(dòng)關(guān)系。令a和b是事件日志L中的一條軌跡σ的兩個(gè)活動(dòng),如果活動(dòng)b緊緊跟隨在活動(dòng)a之后,則稱在軌跡σ中從a到b存在直接跟隨活動(dòng)關(guān)系,記作。

例如,在示例日志LC中,有7個(gè)活動(dòng)a,b,c,d,e,f,g,直接跟隨活動(dòng)關(guān)系有,,,,,,,,,,,,,14個(gè)。

(1)計(jì)算事件日志的活動(dòng)重要性和直接跟隨活動(dòng)關(guān)系重要性。

事件日志L中活動(dòng)a的活動(dòng)重要性

(1)

直接跟隨活動(dòng)關(guān)系的直接跟隨活動(dòng)關(guān)系重要性

(2)

表2 事件日志LC中的活動(dòng)重要性

表3 事件日志LC中的直接跟隨活動(dòng)關(guān)系重要性

(2)計(jì)算事件日志中每條軌跡的平均活動(dòng)重要性和平均直接跟隨活動(dòng)關(guān)系重要性。

軌跡σ的平均活動(dòng)重要性

(3)

軌跡σ的平均直接跟隨活動(dòng)關(guān)系重要性

(4)

(3)計(jì)算事件日志L中軌跡σ的軌跡重要性

(5)

至此得到LC的所有重要性信息,包括每條軌跡的平均活動(dòng)重要性、平均直接跟隨活動(dòng)關(guān)系重要性和軌跡重要性,具體數(shù)值如表4所示。

根據(jù)軌跡重要性對事件日志LC中的軌跡進(jìn)行降序排列,得到σ3,σ1,σ6,σ2,σ8,σ5,σ4,σ7,根據(jù)選定的采樣率(默認(rèn)為0.3)和原始事件日志的大小確定最終樣本日志的大小,即20×0.3=6,最終所得的樣本日志LC′=[,,,,,]。值得注意的是,如果采樣大小大于軌跡變體數(shù),則首先選擇全部軌跡變體,然后將剩下的軌跡按照重要性值降序依次選擇,直到滿足指定采校大小,將全部軌跡變體和選擇到的剩余軌跡組合得到最終的樣本日志。

綜上所述,給定一個(gè)事件日志和一個(gè)采樣率,基于LogRank++的業(yè)務(wù)過程采樣過程如下:

(1)獲取事件日志中的軌跡變體及其頻次。

(2)獲取事件日志的活動(dòng)數(shù)和直接跟隨活動(dòng)關(guān)系數(shù)量。

(3)用式(1)和式(2)分別計(jì)算事件日志的活動(dòng)重要性和直接跟隨活動(dòng)關(guān)系重要性。

(4)用式(3)和式(4)分別計(jì)算事件日志中每條軌跡的平均活動(dòng)重要性和平均直接跟隨活動(dòng)關(guān)系重要性。

(5)用式(5)計(jì)算事件日志中每條軌跡的重要性,并根據(jù)軌跡重要性對軌跡排序。

(6)根據(jù)特定的采樣率選擇前N條軌跡組成樣本日志。

3.3 采樣技術(shù)的高效性評估

給定一個(gè)大規(guī)模事件日志,通過日志采樣技術(shù)獲得一個(gè)更小規(guī)模的樣本日志。由于與其他事件日志采樣技術(shù)相比,本文所提事件日志采樣技術(shù)是否更高效尚不清楚,本節(jié)通過量化獲得的樣本日志的質(zhì)量和采樣效率兩方面綜合評估采樣技術(shù)的高效性。

通過LogRank++日志采樣技術(shù)得到原始事件日志的一個(gè)代表性子集作為樣本日志,然而樣本日志通常不完整,可能導(dǎo)致模型過擬合(或欠擬合)。采樣的目標(biāo)是在不犧牲(太多)模型質(zhì)量的情況下提高過程發(fā)現(xiàn)的效率,而衡量采樣技術(shù)獲得的樣本日志是否具有代表性,通常是將從樣本日志中發(fā)現(xiàn)的過程模型與原始日志作合規(guī)性檢查來評估其過程模型質(zhì)量,為此量化原始事件日志與從樣本日志中發(fā)現(xiàn)的過程模型的擬合度。BUIJS等[13]認(rèn)為,擬合度量化了從原始日志得到的過程模型,能夠準(zhǔn)確再現(xiàn)日志中記錄軌跡的程度,其基本原理是,如果從樣本日志中發(fā)現(xiàn)的模型可以重演原始事件日志中的所有(或大部分)軌跡,則樣本日志對過程發(fā)現(xiàn)來說是高質(zhì)量的。

上述思想可行最關(guān)鍵的因素是保證從樣本日志中發(fā)現(xiàn)的模型可以完全代表樣本日志中的行為,即100%擬合,其基本原理在于,如果從樣本日志中發(fā)現(xiàn)的模型不能覆蓋樣本日志中所有可能的行為,則針對該模型重演原始事件日志沒有任何意義。因此,應(yīng)該選擇一種能夠保證100%擬合度的過程發(fā)現(xiàn)方法,即確保過程模型能夠重演樣本日志中的所有軌跡。

LEEMANS等[6]提出的IM(inductive miner)算法是一種可以保證發(fā)現(xiàn)的模型對輸入日志有100%擬合度的典型方法。該算法采用分而治之的思想,將發(fā)現(xiàn)一個(gè)日志L的過程模型問題分解為發(fā)現(xiàn)通過拆分日志L得到n個(gè)子日志的n個(gè)子過程模型問題,具體如下:①選擇最適合日志L的切分運(yùn)算(順序、并發(fā)、循環(huán)、排他);②將日志L中的活動(dòng)通過切分運(yùn)算劃分為不相交的集合;③用這些集合將日志L拆分為子日志L1,L2,…,Ln。通過上述步驟遞歸挖掘這些子日志L1,L2,…,Ln,直到子日志只包含一個(gè)活動(dòng)。因此,本文選擇IM算法發(fā)現(xiàn)過程模型。

采樣技術(shù)的高效性在很大程度上取決于采樣效率,考慮到即使獲得高質(zhì)量的樣本日志,用戶也不愿意選擇需要花費(fèi)數(shù)小時(shí)才能完成的采樣技術(shù),本文的采樣效率通過獲取樣本日志所花費(fèi)的時(shí)間來量化,一般來說,采樣技術(shù)花費(fèi)的時(shí)間越少,采樣效率越高。

4 實(shí)現(xiàn)工具與實(shí)驗(yàn)評估

本章首先介紹了基于LogRank++的事件日志采樣方法的工具實(shí)現(xiàn),然后對第2章中提出的問題進(jìn)行了解答,最后結(jié)合6個(gè)事件日志,從擬合度指標(biāo)評估采樣質(zhì)量,從采樣花費(fèi)時(shí)間衡量采樣效率,分別對比了LogRank,LogRank+,LogRank++方法的采樣質(zhì)量和采樣效率,有力地說明了基于LogRank++的事件日志采樣技術(shù)的高效性。

4.1 基于LogRank++日志采樣方法的支持工具

開源過程挖掘工具平臺ProM 6為過程挖掘提供了一個(gè)完全可插拔的實(shí)驗(yàn)環(huán)境,其通過添加插件進(jìn)行擴(kuò)展,目前包括1 600多個(gè)插件,該工具和所有插件都是開源的,詳見http://www.promtools.org/prom6/。

基于LogRank++的事件日志采樣技術(shù)已作為插件(稱為LogRank++-based Event Log Sampling,詳見https://svn.win.tue.nl/repos/prom/Packages/SoftwareProcessMining/)在開源過程挖掘工具平臺ProM 6中實(shí)現(xiàn)。該工具的快照如圖2和圖3所示,其輸入為一個(gè)事件日志和一個(gè)采樣率,輸出為返回的一個(gè)樣本日志。應(yīng)該注意的是,以下實(shí)驗(yàn)中的所有示例日志均由該插件生成。

4.2 實(shí)驗(yàn)評估

本節(jié)使用9個(gè)事件日志(3個(gè)仿真日志和6個(gè)真實(shí)日志,鏈接地址為https://github.com/Brain515/ProcessMiningDatasets/tree/main/LogRankPlusplus)對所提基于LogRank++的業(yè)務(wù)過程事件日志采樣方法進(jìn)行實(shí)驗(yàn)評估,表5所示為這些事件日志的部分主要統(tǒng)計(jì)數(shù)據(jù)。

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

(1)Synthetic 1～Synthetic 3數(shù)據(jù)集 Synthetic1數(shù)據(jù)集由論文評審過程模型生成,每一條軌跡都描述了評審論文的過程,Synthetic2和Synthetic3數(shù)據(jù)集是由構(gòu)造模型生成的仿真日志。

(2)Sepsis 數(shù)據(jù)集 該數(shù)據(jù)集包含來自醫(yī)院的膿毒癥病例事件,每一條軌跡代表一個(gè)膿毒癥患者的治療過程。

(3)BPI2011數(shù)據(jù)集 該數(shù)據(jù)集來自荷蘭一家學(xué)術(shù)醫(yī)院的婦科,每一條軌跡代表一個(gè)病人進(jìn)行的醫(yī)療活動(dòng)過程。

(4)BPI2012數(shù)據(jù)集 該數(shù)據(jù)集源自荷蘭一家金融機(jī)構(gòu)的個(gè)人貸款申請過程,每一條軌跡描述了不同客戶申請個(gè)人貸款的過程。

(5)BPI2015_1數(shù)據(jù)集 該數(shù)據(jù)集源自荷蘭城市市政當(dāng)局提供的本地企業(yè)所有建筑許可證的申請過程,期限約為4年,本數(shù)據(jù)集選取其中一部分進(jìn)行處理。

(6)WABO數(shù)據(jù)集 該數(shù)據(jù)集源自荷蘭科學(xué)研究組織中編號為638.001.211執(zhí)行的CoSeLoG項(xiàng)目,記錄了荷蘭城市的城市建筑許可證申請過程。

(7)Final數(shù)據(jù)集 該數(shù)據(jù)集來自意大利軟件公司服務(wù)臺的票務(wù)管理過程。

下面根據(jù)第2章中定義的兩個(gè)研究問題給出實(shí)驗(yàn)結(jié)果。

(1)找到一種高效的方法來獲取一個(gè)樣本日志,使該樣本日志足以代表原始事件日志中的所有(或大多數(shù))軌跡行為。

針對該問題,提出基于LogRank++的日志采樣技術(shù)來進(jìn)行高效的事件日志采樣。該方法首先獲取事件日志的活動(dòng)數(shù)和直接跟隨活動(dòng)關(guān)系數(shù),通過計(jì)算活動(dòng)的重要性和直接跟隨活動(dòng)關(guān)系的重要性得出每條軌跡的重要性,然后根據(jù)軌跡重要性將事件日志中的軌跡降序排列,最后結(jié)合設(shè)置的采樣率和原始事件日志大小選擇前N條軌跡組成樣本日志(N為采樣率與原始事件日志乘積向下取整的結(jié)果)。在之后的實(shí)驗(yàn)中,用基于LogRank++的事件日志采樣插件為每個(gè)實(shí)驗(yàn)日志生成一組不同采樣率的樣本日志(從5%～30%,增量為5%)。

(2)從過程挖掘的角度衡量一個(gè)樣本日志相對于原始日志具有代表性。

針對該問題,從以下方面衡量采樣技術(shù)的高效性:①量化樣本日志的質(zhì)量,本文采用擬合度[14]評估指標(biāo);②量化給定采樣方法的采樣效率。綜合這兩方面思想,在以下實(shí)驗(yàn)中將本文方法與基于LogRank的采樣方法、基于LogRank+的采樣方法的采樣質(zhì)量和采樣效率進(jìn)行對比。

4.2.1 采樣技術(shù)的可行性評估

下面對問題(1)展開詳細(xì)研究。首先對比未采樣的原始日志和采樣后的樣本日志應(yīng)用過程發(fā)現(xiàn)算法(此處為IM算法)的時(shí)間,來說明采樣技術(shù)的有效性,實(shí)驗(yàn)設(shè)置默認(rèn)采樣率為30%,得到的實(shí)驗(yàn)結(jié)果如表6所示。

表6 過程發(fā)現(xiàn)時(shí)間對比 ms

從表6可見,將采樣后的樣本日志進(jìn)行過程發(fā)現(xiàn)的時(shí)間均小于原始日志的過程發(fā)現(xiàn)時(shí)間,說明該采樣技術(shù)提高了過程發(fā)現(xiàn)的效率。值得注意的是,采樣時(shí)間和樣本日志的過程發(fā)現(xiàn)時(shí)間多于原始日志的過程發(fā)現(xiàn)時(shí)間,這是由采樣時(shí)間過長導(dǎo)致的,并不能說明采樣技術(shù)無效。相反,按照“一次采樣,多次使用”的原則,通過采樣技術(shù)得到的樣本日志能夠代替原始日志進(jìn)行后續(xù)過程挖掘相關(guān)工作分析,如一致性檢查、過程增強(qiáng)、預(yù)測性監(jiān)控等,不必每次都要分析原始日志,提高了工作效率。

其次,統(tǒng)計(jì)不同采樣率下樣本日志的詳細(xì)信息,包括軌跡數(shù)、事件數(shù)、活動(dòng)數(shù)和軌跡變體數(shù)量,實(shí)驗(yàn)結(jié)果如表7～表10所示,可見:①樣本日志的大小隨采樣率的降低而急劇減小;②隨著采樣率的降低,事件日志的活動(dòng)數(shù)或軌跡變體數(shù)略有減小或保持大致穩(wěn)定,即大多數(shù)的代表性信息都包含在樣本日志中。由此,進(jìn)一步驗(yàn)證了本文采樣方法的可行性。

表8 不同樣本日志的事件數(shù)

表9 不同樣本日志的活動(dòng)數(shù)

表10 不同樣本日志的軌跡變體數(shù)

4.2.2 采樣技術(shù)的高效性評估

下面對問題(2)展開詳細(xì)研究。為了對比樣本日志的質(zhì)量,量化從樣本日志中發(fā)現(xiàn)的過程模型相對于原始事件日志的擬合度。首先采用IM算法為樣本日志發(fā)現(xiàn)過程模型,然后針對該模型重演其原始日志獲得擬合度值,擬合度值越大,樣本質(zhì)量越高?；谶@一思想,對上述6個(gè)實(shí)驗(yàn)日志進(jìn)行擬合度指標(biāo)的質(zhì)量評估,圖4所示為基于LogRank++的采樣方法與基于LogRank的采樣方法、基于LogRank+的采樣方法進(jìn)行對比實(shí)驗(yàn)得到的擬合度值。

圖4的3種日志采樣技術(shù)顯示,隨著事件日志的減小,樣本日志的質(zhì)量逐漸降低,采樣率區(qū)間在20%～30%之間時(shí),其質(zhì)量下降相對較慢,可以保持在一個(gè)適當(dāng)?shù)闹狄陨?但在個(gè)別樣本日志中樣本質(zhì)量會在某一個(gè)采樣點(diǎn)出現(xiàn)較大波動(dòng),例如在BPI2011日志中,選擇采樣率由20%～15%時(shí)日志的擬合度值下降較快。因此采樣率的選擇至關(guān)重要,采樣率過大會導(dǎo)致采樣花費(fèi)時(shí)間長,采樣率過小則會降低樣本日志的質(zhì)量。實(shí)驗(yàn)結(jié)果表明,采樣率一般選擇在20%以上時(shí),樣本日志的質(zhì)量可以得到保證。

采樣效率通過計(jì)算采樣技術(shù)獲取樣本日志的時(shí)間來量化。一般來說,采樣技術(shù)花費(fèi)的時(shí)間越少,采樣效率越高。在圖5中,通過輸入9個(gè)實(shí)驗(yàn)日志和不同采樣率,展示了基于LogRank的事件日志采樣技術(shù)(用A1表示)、基于LogRank+的事件日志采樣技術(shù)(用A2表示)和基于LogRank++的事件日志采樣技術(shù)(用A3表示)的執(zhí)行時(shí)間,間接地比較了采樣效率。將給定采樣率的每個(gè)實(shí)驗(yàn)日志運(yùn)行插件5次,其平均值在圖中突出顯示。

以Synthetic1數(shù)據(jù)集、Synthetic3數(shù)據(jù)集、Sepsis數(shù)據(jù)集為例,采樣率范圍為30%～20%的樣本日志的擬合度值僅從1降至0.9,即原始日志中的主流行為保留在樣本日志中。另外,基于LogRank++的采樣技術(shù)、基于LogRank的采樣技術(shù)和基于LogRank+的采樣技術(shù)的樣本日志的質(zhì)量相近,不同的是,基于LogRank++的采樣技術(shù)的采樣時(shí)間遠(yuǎn)少于圖5所示的基于LogRank的采樣技術(shù),也少于基于LogRank+的采樣技術(shù)。以Sepsis日志為例,與基于LogRank的采樣技術(shù)相比,基于LogRank++的采樣技術(shù)(30%采樣率)的采樣時(shí)間從27 195 ms減少到449 ms,降低了98.3%;與基于LogRank+的采樣技術(shù)相比,基于LogRank++的采樣技術(shù)的采樣時(shí)間從1 676 ms減少到449 ms,降低了73.2%,但樣本日志的質(zhì)量卻相近;對于BPI2011日志,與基于LogRank的技術(shù)相比,基于LogRank++的采樣技術(shù)(30%采樣率)的采樣時(shí)間從大約2 790 000 ms減少到10 000 ms(節(jié)省大約45 min);與基于LogRank+的技術(shù)相比,基于LogRank++的采樣技術(shù)的30%采樣時(shí)間從大約73 000 ms減少到10 000 ms(節(jié)省約1 min),而其質(zhì)量基本相同(0.99 vs 0.90 vs 0.99)。因此,可以得出結(jié)論,基于LogRank++的采樣技術(shù)提供了一種高效的解決方案,能在提高采樣效率的同時(shí)確保樣本日志高質(zhì)量;另外,事件日志的規(guī)模越大,采樣技術(shù)的采樣效率越高。

5 結(jié)束語

為了提高采樣效率,本文提出一種基于排序的業(yè)務(wù)過程事件日志采樣技術(shù)LogRank++,并通過量化采樣效率和樣本日志的質(zhì)量來評估所提采樣技術(shù)的高效性,所提方法已經(jīng)作為插件在開源過程挖掘工具平臺ProM6中實(shí)現(xiàn)。通過9個(gè)實(shí)驗(yàn)日志的實(shí)驗(yàn)表明,相比已有采樣方法,所提采樣方法在保證樣本日志質(zhì)量的同時(shí)能夠大幅提高日志采樣效率。

本文提出的日志采樣技術(shù)為處理大規(guī)模事件日志提供了一種更高效的解決方案,但在實(shí)驗(yàn)過程中發(fā)現(xiàn),已有采樣技術(shù)均需用戶輸入采樣率,采樣率的選擇至關(guān)重要。從以上實(shí)驗(yàn)表明,無法直接明確一個(gè)采樣點(diǎn)能有效權(quán)衡樣本日志質(zhì)量和日志采樣效率。下一步工作將分析采樣率的設(shè)置對采樣技術(shù)的影響,給出一種有效的采樣率選擇方法,以兼顧日志質(zhì)量和采樣效率。

除此之外,在本文工作的基礎(chǔ)上,未來還可以從如下3方面繼續(xù)深入研究:①將基于LogRank++的業(yè)務(wù)過程事件日志采樣方法部署在分布式系統(tǒng)上[15],處理特大規(guī)模的事件日志;②將基于LogRank++的業(yè)務(wù)過程事件日志采樣方法應(yīng)用到專業(yè)領(lǐng)域(如醫(yī)療、物流、制造業(yè)等)的事件日志;③除了用于過程發(fā)現(xiàn)之外,將采樣技術(shù)用于支持一致性檢查[16]、預(yù)測性監(jiān)控[17]、軟件過程挖掘[18-20]和跨組織過程挖掘[21-23]。