基于混合型事件日志的模型合規(guī)性檢驗(yàn)方法?

尚慶民 宋 巍

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

作為過(guò)程挖掘領(lǐng)域一項(xiàng)不可忽視的技術(shù)，合規(guī)性檢驗(yàn)旨在分析發(fā)現(xiàn)的過(guò)程模型所捕獲行為和事件日志所描述行為的差異性［1～2］。合規(guī)性檢驗(yàn)的輸入為事件日志及其對(duì)應(yīng)的過(guò)程模型，其中事件日志是事件序列的集合，并且是過(guò)程發(fā)現(xiàn)技術(shù)的輸入［3］?，F(xiàn)實(shí)中大部分事件在執(zhí)行過(guò)程會(huì)持續(xù)一段時(shí)間，即區(qū)間事件，因此該事件的開(kāi)始和結(jié)束信息都會(huì)被系統(tǒng)記錄在事件日志中［4～5］，然而，瞬時(shí)完成事件的開(kāi)始和結(jié)束會(huì)被合并記錄成一個(gè)點(diǎn)事件。因此，現(xiàn)實(shí)中的事件日志大部分是包含點(diǎn)事件和區(qū)間事件的混合型事件日志。

現(xiàn)有過(guò)程挖掘合規(guī)性檢驗(yàn)方法不能直接應(yīng)用到混合型事件日志。Cook 等最早提出通過(guò)比較事件日志和過(guò)程模型分別生成的事件流進(jìn)行合規(guī)性檢驗(yàn)的方法，為后來(lái)的合規(guī)性檢驗(yàn)技術(shù)發(fā)展奠定了基礎(chǔ)［6］。隨后的十幾年里，很多學(xué)者提出不同方法從不同方面進(jìn)行合規(guī)性檢驗(yàn)［7～8］?，F(xiàn)有研究主要從擬合度、精確度和簡(jiǎn)潔度幾個(gè)方面分析過(guò)程模型與事件日志的合規(guī)性。然而現(xiàn)有方法都是針對(duì)只包含點(diǎn)事件的事件日志進(jìn)行分析［9～12］，當(dāng)這些方法應(yīng)用到混合型事件日志時(shí)，由于區(qū)間事件的開(kāi)始事件和結(jié)束事件在事件日志重放過(guò)程中重復(fù)出現(xiàn)，導(dǎo)致合規(guī)性檢驗(yàn)結(jié)果不夠準(zhǔn)確。

針對(duì)現(xiàn)有技術(shù)的不足，本文提出一種針對(duì)混合型事件日志及其對(duì)應(yīng)的過(guò)程模型進(jìn)行合規(guī)性檢驗(yàn)的方法，從擬合度、精確度和簡(jiǎn)潔度三個(gè)方面衡量模型與事件日志的合規(guī)性。通過(guò)對(duì)事件日志重放計(jì)算令牌變化以計(jì)算擬合度，通過(guò)比較事件日志和過(guò)程模型分別包含的事件關(guān)系計(jì)算精確度，通過(guò)比較事件日志和過(guò)程模型分別包含的變遷數(shù)量計(jì)算簡(jiǎn)潔度，最后整合三個(gè)指標(biāo)，計(jì)算出合規(guī)性檢驗(yàn)結(jié)果值F1。我們實(shí)現(xiàn)原型工具HCC 并通過(guò)案例分析驗(yàn)證本文方法的有效性。

2 相關(guān)概念

2.1 過(guò)程模型

Petri 網(wǎng)是支持并發(fā)語(yǔ)義的建模語(yǔ)言，由庫(kù)所、變遷和令牌等基本元素組成。 其形式化定義如下。

定義1（Petri網(wǎng)）Petri網(wǎng)是一個(gè)三元組PN=（P，T，F(xiàn)）：

·P是庫(kù)所有限集合；

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

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

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

2.2 事件日志

信息系統(tǒng)的業(yè)務(wù)過(guò)程PN 包含多個(gè)活動(dòng)，這些活動(dòng)的生命周期有三類(lèi)，對(duì)于區(qū)間活動(dòng)，其開(kāi)始和結(jié)束通常會(huì)被記錄成兩個(gè)有不同生命周期的事件，對(duì)于瞬時(shí)完成的活動(dòng)，開(kāi)始和完成通常會(huì)合并記錄成一個(gè)點(diǎn)事件。業(yè)務(wù)過(guò)程PN 可執(zhí)行多次，每次執(zhí)行產(chǎn)生一條事件序列，多條事件序列組合構(gòu)成該系統(tǒng)的事件日志。假設(shè)業(yè)務(wù)活動(dòng)集合為T(mén)，T*表示基于T的所有可能發(fā)生的事件序列集合。

定義2（事件序列）業(yè)務(wù)過(guò)程PN=（P，T，F(xiàn)）的一條事件序列σ∈T*用一組符號(hào)t1t2… tn表示，其中ti=x（1 ≤i ≤n）表示事件ti為瞬時(shí)活動(dòng)x（x∈T），ti=ys（ye）表示事件ti為區(qū)間活動(dòng)y（y∈T）的開(kāi)始事件（完成事件）。

定義3（事件日志）業(yè)務(wù)過(guò)程PN=（P，T，F(xiàn)）對(duì)應(yīng)的事件日志L是事件序列的多重集，即L∈（T*）*，本文所用日志是以xes格式描述的事件日志［14］。

圖1 業(yè)務(wù)過(guò)程PN

圖1 所示是一個(gè)業(yè)務(wù)過(guò)程PN，黑色填充的變遷表示區(qū)間事件，無(wú)填充的表示瞬時(shí)事件，又稱為點(diǎn)事件。表1 是該業(yè)務(wù)過(guò)程的一個(gè)事件日志L，該事件日志包含幾條事件序列，每條事件序列記錄了業(yè)務(wù)過(guò)程執(zhí)行的事件順序，其中由于σ5存在事件移位導(dǎo)致L與PN不完全相符。

表1 事件日志

2.3 過(guò)程挖掘的合規(guī)性檢驗(yàn)

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

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

表2 符號(hào)對(duì)應(yīng)表

3 基于混合型事件日志的模型合規(guī)性檢驗(yàn)方法

3.1 擬合度計(jì)算

在混合型事件日志中，每個(gè)區(qū)間事件在事件序列中對(duì)應(yīng)一個(gè)開(kāi)始事件和一個(gè)結(jié)束事件，進(jìn)行日志重放的過(guò)程中，由于模型中并發(fā)的存在，需考慮所有并發(fā)的結(jié)束事件都完成之后才能使能后續(xù)的事件，這使得傳統(tǒng)日志重放算法不能直接應(yīng)用于混合型事件日志。

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

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

算法1：日志重放算法

輸入：事件日志L，過(guò)程模型P。輸出：擬合度結(jié)果f。

用n 表示事件日志L 包含的事件序列的條數(shù)，m 表示每條事件序列包含的事件的平均值，用k 表示模型P 中每個(gè)變遷對(duì)應(yīng)前驅(qū)庫(kù)所及后繼庫(kù)所的平均值，用h 表示模型中每個(gè)庫(kù)所對(duì)應(yīng)的后繼變遷的平均值，則算法1 在最壞情況下的時(shí)間復(fù)雜度為O（m×n×h×k2），相對(duì)于m 和n 來(lái)說(shuō)，h 和k 的值是非常小的。

3.2 精確度計(jì)算

在混合型事件日志中，對(duì)于區(qū)間事件t，對(duì)應(yīng)一個(gè)開(kāi)始事件和一個(gè)結(jié)束事件，對(duì)于兩個(gè)并發(fā)事件t1和t2，其可能發(fā)生的事件序列如表3所示，對(duì)于點(diǎn)事件t3和t4，其并發(fā)事件序列只有兩種｛t3，t4，t4，t3｝，由于區(qū)間事件的開(kāi)始和結(jié)束事件的同時(shí)存在，使得精確度計(jì)算比只針對(duì)包含點(diǎn)事件日志的合規(guī)性檢驗(yàn)更復(fù)雜，傳統(tǒng)的合規(guī)性檢驗(yàn)算法不能準(zhǔn)確計(jì)算混合型事件日志的精確度。本文提出的精確度衡量方法，通過(guò)比較事件日志的事件關(guān)系和過(guò)程模型的事件關(guān)系來(lái)計(jì)算。

在過(guò)程模型和事件日志中，活動(dòng)的發(fā)生遵循一定的規(guī)則，他們?cè)谶^(guò)程模型和事件日志中的關(guān)系都可以分別通過(guò)某種方式獲取。在計(jì)算精確度時(shí)，過(guò)程模型中的描述的行為比事件日志中記錄的行為可能要多，以基于事件日志的關(guān)系為基準(zhǔn)。用PL表示事件日志包含的并發(fā)和因果關(guān)系集合，PM 表示過(guò)程模型包含的并發(fā)和因果關(guān)系集合，合規(guī)性檢驗(yàn)的精確度計(jì)算表達(dá)式如式（2）所示。

表3 并發(fā)事件序列集合

日志中對(duì)并發(fā)關(guān)系和因果關(guān)系的判斷如下：

1）直接優(yōu)先關(guān)系（>）。當(dāng)事件序列內(nèi)兩個(gè)事件ti和tj同時(shí)滿足以下五個(gè)條件：（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）相交關(guān)系（|）。當(dāng)事件序列內(nèi)幾個(gè)事件ti，tj，tp，tq滿足以下條件中任意一個(gè)：（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）因果關(guān)系（→）。對(duì)于事件x 和y，若x>y，y≯x，且非x|y，則x→y；

4）并發(fā)關(guān)系（||）。對(duì)于事件x和y，若x|y，或x>y且y>x，則x||y。

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

算法2：模型并發(fā)和因果關(guān)系判斷算法

輸入：過(guò)程模型PN。

輸出：PN包含的并發(fā)關(guān)系Cc，因果關(guān)系Cs。

3.3 簡(jiǎn)潔度計(jì)算

本文比較過(guò)程模型中事件的數(shù)量和事件日志中包含的不同事件的數(shù)量來(lái)計(jì)算模型的簡(jiǎn)潔度，用LT 表示事件日志中不同的事件集合，用MT 表示過(guò)程模型中的所有事件的集合，MT"表示去重后過(guò)程模型中的事件集合，令ST=LT∩MT"表示LT 和MT"的相同變遷的個(gè)數(shù)，簡(jiǎn)潔度的計(jì)算表達(dá)式如式（3）所示。

即

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

算法3：簡(jiǎn)潔度計(jì)算

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

輸出：簡(jiǎn)潔度結(jié)果s。

3.4 合規(guī)性檢驗(yàn)結(jié)果綜合計(jì)算

為各個(gè)指標(biāo)設(shè)置權(quán)重，求出最終的合規(guī)性檢驗(yàn)結(jié)果。設(shè)擬合度f(wàn)、精確度p、簡(jiǎn)潔度s的權(quán)重分別為a，b，c，計(jì)算表達(dá)式如式（4）所示。

4 工具

4.1 實(shí)現(xiàn)

為評(píng)估本文方法的有效性，我們?cè)贓clipse 集成開(kāi)發(fā)環(huán)境中使用Java語(yǔ)言實(shí)現(xiàn)原型工具HCC，工具的總體架構(gòu)如圖2所示。主要包含模塊有：

1）輸入解析模塊。工具的輸入是xes 格式描述的事件日志文件和pnml 格式的Petri 網(wǎng)模型，對(duì)于事件日志的解析是借助第三方類(lèi)庫(kù)dom4j 將其解析為事件序列的數(shù)據(jù)結(jié)構(gòu)，對(duì)于過(guò)程模型的解析是將過(guò)程模型包含的變遷、庫(kù)所及其對(duì)應(yīng)的關(guān)系解析為模型的數(shù)據(jù)結(jié)構(gòu)。

2）合規(guī)性指標(biāo)計(jì)算模塊。對(duì)事件日志基于過(guò)程模型進(jìn)行重放，記錄重放過(guò)程產(chǎn)生、缺失、剩余及消耗的令牌數(shù)，根據(jù)式（1）計(jì)算出合規(guī)性檢驗(yàn)的擬合度；分別整合事件日志和過(guò)程模型對(duì)應(yīng)的事件關(guān)系集合，根據(jù)式（2）計(jì)算出合規(guī)性檢驗(yàn)的精確度；分別統(tǒng)計(jì)過(guò)程模型缺少和重復(fù)的事件數(shù)量，以及過(guò)程模型和事件日志分別包含的事件總數(shù)，根據(jù)式（4）計(jì)算出合規(guī)性檢驗(yàn)的簡(jiǎn)潔度。

3）合規(guī)性檢驗(yàn)結(jié)果計(jì)算及視圖模塊。給計(jì)算出的擬合度、精確度和簡(jiǎn)潔度設(shè)置不同權(quán)重，計(jì)算出合規(guī)性檢驗(yàn)的最終結(jié)果并輸出到控制臺(tái)中。

圖2 HCC總體架構(gòu)

4.3 案例分析

由于缺乏準(zhǔn)確的指標(biāo)衡量各合規(guī)性檢驗(yàn)方法的準(zhǔn)確性，因此我們進(jìn)行案例分析，通過(guò)對(duì)圖1 所示過(guò)程模型及表1 的事件日志進(jìn)行合規(guī)性檢驗(yàn)來(lái)衡量本文所提方法的有效性。圖3 可視化地展示了該案例的運(yùn)行結(jié)果。下面將對(duì)本文所提方法應(yīng)用于該案例進(jìn)行合規(guī)性校驗(yàn)過(guò)程進(jìn)行詳細(xì)分析。

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

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

根據(jù)算法3 計(jì)算模型與事件日志合規(guī)性檢驗(yàn)的簡(jiǎn)潔度，事件日志包含的事件集合為｛t1，t2，t3，t4，t5，t6，t7，t8｝，模型包含的事件集合與其一致，可以求得合規(guī)性檢驗(yàn)的簡(jiǎn)潔度為1。

最后，將擬合度f(wàn)、精確度p、簡(jiǎn)潔度s 的權(quán)重都設(shè)置為1，可得合規(guī)性檢驗(yàn)結(jié)果F1 如圖3 所示。通過(guò)該案例分析可得，本文所提的方法可以對(duì)混合型事件日志及對(duì)應(yīng)過(guò)程模型有效地進(jìn)行合規(guī)性分析，即使在過(guò)程模型與事件日志不完全相符的情況下，也能夠?qū)弦?guī)性進(jìn)行適度的衡量。

我們將該實(shí)例運(yùn)行在Inter（R）3.40GHz 處理器，8GB 內(nèi)存的Windows10 系統(tǒng)的臺(tái)式機(jī)上。為了有效判斷算法效率，我們將表1 所示的事件日志擴(kuò)大十倍進(jìn)行計(jì)算，經(jīng)過(guò)100 次計(jì)算，統(tǒng)計(jì)得到合規(guī)性檢驗(yàn)耗時(shí)104ms，表現(xiàn)了算法具有較高的效率。

圖3 基于混合型事件日志的模型合規(guī)性檢驗(yàn)工具HCC

5 結(jié)語(yǔ)

本文提出一種針對(duì)混合型事件日志及其對(duì)應(yīng)的過(guò)程模型進(jìn)行合規(guī)性檢驗(yàn)的方法，通過(guò)三個(gè)評(píng)價(jià)指標(biāo)綜合評(píng)判日志和模型的合規(guī)性。該方法可直接應(yīng)用于包含點(diǎn)事件和區(qū)間事件的混合型事件日志，同時(shí)又適用于只包含點(diǎn)事件和只包含區(qū)間事件的事件日志，我們將該算法實(shí)現(xiàn)在原型工具“HCC”中，并通過(guò)案例分析闡明了算法的有效性。