LogRank++:一種高效的業務過程事件日志采樣方法

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

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

0 引言

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

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

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

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

前期工作[10-11]中,筆者在PageRank算法的基礎上實現了一個基于圖排序的LogRank事件日志采樣技術,其以任意事件日志為輸入來獲取樣本日志,因為樣本日志比原始日志小得多,所以處理效率也更高。雖然該采樣技術有助于提高過程發現效率,但是在處理大規模事件日志時采樣算法本身非常耗時。于是LIU等[12]提出一種基于軌跡相似度計算的LogRank+事件日志采樣技術,與基于LogRank的事件日志采樣技術相比,該方法在確保采樣質量的前提下縮短了采樣時間,提高了采樣效率。然而,當前已有采樣算法在處理一些大規模事件日志時仍需花費大量時間才能完成采樣,采樣時間還需進一步提升。

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

1 基礎知識

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

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

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

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

事件日志可被視為軌跡的多重集合,因為可能有多個過程實例(或案例)具有相同的軌跡,每個軌跡描述了特定實例(或案例)的生命周期。過程發現以事件日志為輸入,返回一個過程模型。

定義2過程發現[11]。設UM是所有過程模型的集合,一個過程發現方法指從一個事件日志L∈B(A*)映射到一個過程模型pm∈UM的函數γ,即γ(L)=pm。

一般來說,過程發現方法能夠將事件日志轉換成由標記的Petri網、業務流程建模標注(Business Process Modeling Notation,BPMN)語言、事件驅動過程鏈(Event-driven Process Chain,EPC)等表示的過程模型。無論過程模型采用什么表示方法,輸入事件日志中的每個軌跡都對應于發現的過程模型中的一個可能的執行序列。然而已有過程發現方法不能有效挖掘出大規模事件日志中的信息,有必要對事件日志進行采樣處理。

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

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

2 研究問題和方法概述

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

2.1 研究問題

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

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

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

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

2.2 方法概述

圖1所示為本文方法架構圖,包括以下兩個階段:

階段1事件日志采樣。

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

階段2采樣技術的高效性評估。

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

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

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

3 基于LogRank++的業務過程事件日志采樣

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

3.1 事件日志示例

3.2 基于LogRank++的業務過程事件日志采樣方法

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

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

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

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

例如,在示例日志LC中,有7個活動a,b,c,d,e,f,g,直接跟隨活動關系有,,,,,,,,,,,,,14個。

(1)計算事件日志的活動重要性和直接跟隨活動關系重要性。

事件日志L中活動a的活動重要性

(1)

直接跟隨活動關系的直接跟隨活動關系重要性

(2)

表2 事件日志LC中的活動重要性

表3 事件日志LC中的直接跟隨活動關系重要性

(2)計算事件日志中每條軌跡的平均活動重要性和平均直接跟隨活動關系重要性。

軌跡σ的平均活動重要性

(3)

軌跡σ的平均直接跟隨活動關系重要性

(4)

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

(5)

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

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

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

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

(2)獲取事件日志的活動數和直接跟隨活動關系數量。

(3)用式(1)和式(2)分別計算事件日志的活動重要性和直接跟隨活動關系重要性。

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

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

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

3.3 采樣技術的高效性評估

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

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

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

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

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

4 實現工具與實驗評估

本章首先介紹了基于LogRank++的事件日志采樣方法的工具實現,然后對第2章中提出的問題進行了解答,最后結合6個事件日志,從擬合度指標評估采樣質量,從采樣花費時間衡量采樣效率,分別對比了LogRank,LogRank+,LogRank++方法的采樣質量和采樣效率,有力地說明了基于LogRank++的事件日志采樣技術的高效性。

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

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

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

4.2 實驗評估

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

表5 實驗日志概述

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

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

(3)BPI2011數據集 該數據集來自荷蘭一家學術醫院的婦科,每一條軌跡代表一個病人進行的醫療活動過程。

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

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

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

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

下面根據第2章中定義的兩個研究問題給出實驗結果。

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

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

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

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

4.2.1 采樣技術的可行性評估

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

表6 過程發現時間對比 ms

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

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

表8 不同樣本日志的事件數

表9 不同樣本日志的活動數

表10 不同樣本日志的軌跡變體數

4.2.2 采樣技術的高效性評估

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

圖4的3種日志采樣技術顯示,隨著事件日志的減小,樣本日志的質量逐漸降低,采樣率區間在20%～30%之間時,其質量下降相對較慢,可以保持在一個適當的值以上,但在個別樣本日志中樣本質量會在某一個采樣點出現較大波動,例如在BPI2011日志中,選擇采樣率由20%～15%時日志的擬合度值下降較快。因此采樣率的選擇至關重要,采樣率過大會導致采樣花費時間長,采樣率過小則會降低樣本日志的質量。實驗結果表明,采樣率一般選擇在20%以上時,樣本日志的質量可以得到保證。

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

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

5 結束語

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

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

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