基于混合型事件日志的模型合規性檢驗方法?

尚慶民 宋 巍

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

作為過程挖掘領域一項不可忽視的技術，合規性檢驗旨在分析發現的過程模型所捕獲行為和事件日志所描述行為的差異性［1～2］。合規性檢驗的輸入為事件日志及其對應的過程模型，其中事件日志是事件序列的集合，并且是過程發現技術的輸入［3］?，F實中大部分事件在執行過程會持續一段時間，即區間事件，因此該事件的開始和結束信息都會被系統記錄在事件日志中［4～5］，然而，瞬時完成事件的開始和結束會被合并記錄成一個點事件。因此，現實中的事件日志大部分是包含點事件和區間事件的混合型事件日志。

現有過程挖掘合規性檢驗方法不能直接應用到混合型事件日志。Cook 等最早提出通過比較事件日志和過程模型分別生成的事件流進行合規性檢驗的方法，為后來的合規性檢驗技術發展奠定了基礎［6］。隨后的十幾年里，很多學者提出不同方法從不同方面進行合規性檢驗［7～8］。現有研究主要從擬合度、精確度和簡潔度幾個方面分析過程模型與事件日志的合規性。然而現有方法都是針對只包含點事件的事件日志進行分析［9～12］，當這些方法應用到混合型事件日志時，由于區間事件的開始事件和結束事件在事件日志重放過程中重復出現，導致合規性檢驗結果不夠準確。

針對現有技術的不足，本文提出一種針對混合型事件日志及其對應的過程模型進行合規性檢驗的方法，從擬合度、精確度和簡潔度三個方面衡量模型與事件日志的合規性。通過對事件日志重放計算令牌變化以計算擬合度，通過比較事件日志和過程模型分別包含的事件關系計算精確度，通過比較事件日志和過程模型分別包含的變遷數量計算簡潔度，最后整合三個指標，計算出合規性檢驗結果值F1。我們實現原型工具HCC 并通過案例分析驗證本文方法的有效性。

2 相關概念

2.1 過程模型

Petri 網是支持并發語義的建模語言，由庫所、變遷和令牌等基本元素組成。 其形式化定義如下。

定義1（Petri網）Petri網是一個三元組PN=（P，T，F）：

·P是庫所有限集合；

·T是變遷有限集合，并且滿足P∩T=?；

·F ?（P×T）∪（T×P）是被稱為流關系的有向弧的有限集合。

對于任一節點z∈P∪T，·z=｛y|＜y，z>∈F｝，并且z·=｛y|＜z，y>∈F｝。Petri網引入令牌表示當前狀態，如果變遷t能夠消耗每個·t庫所的一個令牌，并且在每個t·中產生一個新的令牌，則表示變遷t 在當前狀態下是使能的。Petri 網可用來表示業務過程模型，其中變遷表示活動，庫所和邊表示活動間的控制流關系。本文與現有多數過程挖掘工作［13～14］一致，采用Petri 網表示業務過程模型，所用過程模型擁有唯一源庫所Pi∈P（·Pi=?）和唯一終止庫所Po∈P（Po·=?），每一個庫所和變遷都在從Pi到Po的路徑上。

2.2 事件日志

信息系統的業務過程PN 包含多個活動，這些活動的生命周期有三類，對于區間活動，其開始和結束通常會被記錄成兩個有不同生命周期的事件，對于瞬時完成的活動，開始和完成通常會合并記錄成一個點事件。業務過程PN 可執行多次，每次執行產生一條事件序列，多條事件序列組合構成該系統的事件日志。假設業務活動集合為T，T*表示基于T的所有可能發生的事件序列集合。

定義2（事件序列）業務過程PN=（P，T，F）的一條事件序列σ∈T*用一組符號t1t2… tn表示，其中ti=x（1 ≤i ≤n）表示事件ti為瞬時活動x（x∈T），ti=ys（ye）表示事件ti為區間活動y（y∈T）的開始事件（完成事件）。

定義3（事件日志）業務過程PN=（P，T，F）對應的事件日志L是事件序列的多重集，即L∈（T*）*，本文所用日志是以xes格式描述的事件日志［14］。

圖1 業務過程PN

圖1 所示是一個業務過程PN，黑色填充的變遷表示區間事件，無填充的表示瞬時事件，又稱為點事件。表1 是該業務過程的一個事件日志L，該事件日志包含幾條事件序列，每條事件序列記錄了業務過程執行的事件順序，其中由于σ5存在事件移位導致L與PN不完全相符。

表1 事件日志

2.3 過程挖掘的合規性檢驗

合規性檢驗，又稱為合規性分析，是檢測事件日志與對應的過程模型之間的匹配的程度，并用一定的指標去量化［7］。本文的合規性檢驗方法用三個指標量化，即擬合度、精確度、和簡潔度。其中擬合度是指事件日志的序列在過程模型中重現的程度，重現程度越高，則擬合度越高；精確度是指過程模型是否描述了日志包含的事件序列之外的行為，描述的事件日志之外行為越多，則精確度越低；簡潔度是指模型應該足夠簡潔，不能包含事件日志之外的多余事件［14～16］。

表2列舉了本文的符號、算法中的單詞及其含義。

表2 符號對應表

3 基于混合型事件日志的模型合規性檢驗方法

3.1 擬合度計算

在混合型事件日志中，每個區間事件在事件序列中對應一個開始事件和一個結束事件，進行日志重放的過程中，由于模型中并發的存在，需考慮所有并發的結束事件都完成之后才能使能后續的事件，這使得傳統日志重放算法不能直接應用于混合型事件日志。

本文與經典算法［17］采用相同思想，基于令牌計算合規性檢驗的擬合度，對日志中的事件序列基于模型進行重放。首先在初始庫所生成一個令牌，之后執行該庫所之后的事件，消耗庫所中的令牌，當該事件執行完成后，該事件之后的庫所才能產生令牌，與經典算法不同的是，若事件為區間事件，則應在其compete事件執行完成之后才生成令牌。在事件日志重放過程中，若序列中要執行的事件之前的庫所缺乏令牌，則人為添加并記錄，統計出重放過程令牌情況及次數，然后計算擬合度。事件日志包含的事件序列數量用k 表示，重放過程中生成的令牌數用p 表示，缺失的令牌數用m 表示，剩余的令牌數用r 表示，自然消耗的令牌數用c 表示，擬合度的計算表達式如式（1）所示。

算法1 旨在計算事件日志與過程模型的擬合度，第1～2 行是對事件日志中每條序列的起始庫所生成一個令牌，第3～25 行是事件日志重放的過程，其中第4～8 行是對區間事件的開始事件重放，判斷前驅庫所是否有token，沒有則人為添加，m 加1，之后消耗c加1，前驅庫所令牌數置零，第9～25行是對點事件和區間事件的結束事件進行重放，重放結束后右側庫所產生令牌，第19～25 行是對后繼事件是否為不可見事件的判斷，若為不可見事件則不需要重放，第26～29 行是當前序列重放完成計算剩余令牌數量，第30～31行是計算擬合度并返回結果。

算法1：日志重放算法

輸入：事件日志L，過程模型P。輸出：擬合度結果f。

用n 表示事件日志L 包含的事件序列的條數，m 表示每條事件序列包含的事件的平均值，用k 表示模型P 中每個變遷對應前驅庫所及后繼庫所的平均值，用h 表示模型中每個庫所對應的后繼變遷的平均值，則算法1 在最壞情況下的時間復雜度為O（m×n×h×k2），相對于m 和n 來說，h 和k 的值是非常小的。

3.2 精確度計算

在混合型事件日志中，對于區間事件t，對應一個開始事件和一個結束事件，對于兩個并發事件t1和t2，其可能發生的事件序列如表3所示，對于點事件t3和t4，其并發事件序列只有兩種｛t3，t4，t4，t3｝，由于區間事件的開始和結束事件的同時存在，使得精確度計算比只針對包含點事件日志的合規性檢驗更復雜，傳統的合規性檢驗算法不能準確計算混合型事件日志的精確度。本文提出的精確度衡量方法，通過比較事件日志的事件關系和過程模型的事件關系來計算。

在過程模型和事件日志中，活動的發生遵循一定的規則，他們在過程模型和事件日志中的關系都可以分別通過某種方式獲取。在計算精確度時，過程模型中的描述的行為比事件日志中記錄的行為可能要多，以基于事件日志的關系為基準。用PL表示事件日志包含的并發和因果關系集合，PM 表示過程模型包含的并發和因果關系集合，合規性檢驗的精確度計算表達式如式（2）所示。

表3 并發事件序列集合

日志中對并發關系和因果關系的判斷如下：

1）直接優先關系（>）。當事件序列內兩個事件ti和tj同時滿足以下五個條件：（1）ti=x 或ti=xe；（2）tj=y 或tj=ys；（3）不存在p，i＜p＜j，tp=z；（4）不存在k，i＜k＜j，ti=zs；（5）不存在p，i＜l＜j，tl=ze；則x>y；

2）相交關系（|）。當事件序列內幾個事件ti，tj，tp，tq滿足以下條件中任意一個：（1）ti=xs，tj=xe，tp=ys，tq=ye，且p＜i＜q 或i＜p＜j；（2）ti=ys，tj=ye，tp=x，且i＜k＜j，則x|y，y|x；

3）因果關系（→）。對于事件x 和y，若x>y，y≯x，且非x|y，則x→y；

4）并發關系（||）。對于事件x和y，若x|y，或x>y且y>x，則x||y。

算法2旨在挖掘過程模型中的因果關系和并發關系。第1 行對集合進行初始化，第2～3 行是遍歷模型中的邊，第4～6 行是求過程模型中的因果關系，第7～20 行是求過程模型中的并發關系，第21行，返回過程模型的因果關系和并發關系集合。用m 表示過程模型PN 中包含的弧的個數，用n 表示并發事件關系的數量，則算法2 在最壞情況下的時間復雜度為O（m2×n2）。

算法2：模型并發和因果關系判斷算法

輸入：過程模型PN。

輸出：PN包含的并發關系Cc，因果關系Cs。

3.3 簡潔度計算

本文比較過程模型中事件的數量和事件日志中包含的不同事件的數量來計算模型的簡潔度，用LT 表示事件日志中不同的事件集合，用MT 表示過程模型中的所有事件的集合，MT"表示去重后過程模型中的事件集合，令ST=LT∩MT"表示LT 和MT"的相同變遷的個數，簡潔度的計算表達式如式（3）所示。

即

算法3旨在計算混合型事件日志合規性檢驗的簡潔度。第1 行對集合進行初始化，第2～4 行是遍歷過程模型的事件集合和事件日志的事件集合，找到相同的事件則添加到集合ST中，第6行是計算結果，第7 行返回合規性檢驗的簡潔度。用m 表示LT 中變遷個數，用n 表示MT"中變遷個數，則算法3在最壞情況下的時間復雜度為O（m×n）。

算法3：簡潔度計算

輸入：混合型事件日志變遷集合LT，過程模型變遷集合MT"。

輸出：簡潔度結果s。

3.4 合規性檢驗結果綜合計算

為各個指標設置權重，求出最終的合規性檢驗結果。設擬合度f、精確度p、簡潔度s的權重分別為a，b，c，計算表達式如式（4）所示。

4 工具

4.1 實現

為評估本文方法的有效性，我們在Eclipse 集成開發環境中使用Java語言實現原型工具HCC，工具的總體架構如圖2所示。主要包含模塊有：

1）輸入解析模塊。工具的輸入是xes 格式描述的事件日志文件和pnml 格式的Petri 網模型，對于事件日志的解析是借助第三方類庫dom4j 將其解析為事件序列的數據結構，對于過程模型的解析是將過程模型包含的變遷、庫所及其對應的關系解析為模型的數據結構。

2）合規性指標計算模塊。對事件日志基于過程模型進行重放，記錄重放過程產生、缺失、剩余及消耗的令牌數，根據式（1）計算出合規性檢驗的擬合度；分別整合事件日志和過程模型對應的事件關系集合，根據式（2）計算出合規性檢驗的精確度；分別統計過程模型缺少和重復的事件數量，以及過程模型和事件日志分別包含的事件總數，根據式（4）計算出合規性檢驗的簡潔度。

3）合規性檢驗結果計算及視圖模塊。給計算出的擬合度、精確度和簡潔度設置不同權重，計算出合規性檢驗的最終結果并輸出到控制臺中。

圖2 HCC總體架構

4.3 案例分析

由于缺乏準確的指標衡量各合規性檢驗方法的準確性，因此我們進行案例分析，通過對圖1 所示過程模型及表1 的事件日志進行合規性檢驗來衡量本文所提方法的有效性。圖3 可視化地展示了該案例的運行結果。下面將對本文所提方法應用于該案例進行合規性校驗過程進行詳細分析。

首先進行擬合度分析，根據算法1，對表1所示事件日志中的事件序列σ1進行重放，在庫所Pi中生成一個令牌，生成令牌數p加1，接著讀入點事件t1，判斷其前驅庫所Pi有令牌，則執行t1，Pi令牌個數置零，消耗令牌數c 加1，并在其后繼庫所p1生成令牌，p 加1；讀入事件t2s，其前驅庫所p1有令牌，則執行t2，p1令牌數置零，c 加1，令t（t2）=1，表示t2正在執行；讀入事件t2e，判斷t（t2）=1，則執行t2e，令t（t2）=0，表示t2執行完成，并在其后繼庫所p2生成令牌，p 加1；后續事件執行與其一致，需注意的是事件t4和t5的complete事件都完成后，庫所p5和p6才會有令牌，t6才能執行，否則需人為添加令牌；對σ1持續重放直到t8執行完成，可得該序列重放過程中不需要認為添加或刪除令牌。對表1 中剩余序列進行重放，事件日志重放完成后得到擬合度結果如圖3 所示。需要注意的是，σ5由于存在事件移位，重放時需人為添加并消除令牌，若將此事件序列中的區間事件只保留開始或結束事件，則現有的合規性檢驗方法可應用于此事件序列，而由于部分開始或結束事件的舍棄，可能導致現有方法無法檢測出該事件序列不能完整重放，從而無法得出正確的擬合度結果。

擬合度計算完成后，計算事件日志與模型的精確度，根據3.2中的定義，可以求得事件日志包含的因果 關 系 有｛t1→t2，t2→t3，t2→t7，t3→t4，t3→t5，t4→t6，t5→t6，t6→t8，t7→t8｝，并發關系有｛t4|| t5，t6|| t8｝；根據算法2 求得模型的因果關系有｛t1→t2，t2→t3，t2→t7，t3→t4，t3→t5，t4→t6，t5→t6，t6→t8，t7→t8｝，并發關系有｛t4||t5｝，根據式（2），可以求出合規性檢驗的精確度為1。

根據算法3 計算模型與事件日志合規性檢驗的簡潔度，事件日志包含的事件集合為｛t1，t2，t3，t4，t5，t6，t7，t8｝，模型包含的事件集合與其一致，可以求得合規性檢驗的簡潔度為1。

最后，將擬合度f、精確度p、簡潔度s 的權重都設置為1，可得合規性檢驗結果F1 如圖3 所示。通過該案例分析可得，本文所提的方法可以對混合型事件日志及對應過程模型有效地進行合規性分析，即使在過程模型與事件日志不完全相符的情況下，也能夠對合規性進行適度的衡量。

我們將該實例運行在Inter（R）3.40GHz 處理器，8GB 內存的Windows10 系統的臺式機上。為了有效判斷算法效率，我們將表1 所示的事件日志擴大十倍進行計算，經過100 次計算，統計得到合規性檢驗耗時104ms，表現了算法具有較高的效率。

圖3 基于混合型事件日志的模型合規性檢驗工具HCC

5 結語

本文提出一種針對混合型事件日志及其對應的過程模型進行合規性檢驗的方法，通過三個評價指標綜合評判日志和模型的合規性。該方法可直接應用于包含點事件和區間事件的混合型事件日志，同時又適用于只包含點事件和只包含區間事件的事件日志，我們將該算法實現在原型工具“HCC”中，并通過案例分析闡明了算法的有效性。