事件日志的批量跡與過程模型的多視角對齊方法

摘 要：在業務過程發現的一致性檢測中，現有事件日志與過程模型的多視角對齊方法一次只能獲得一條跡與過程模型的最優對齊；并且最優對齊求解中的啟發函數計算復雜，以致最優對齊的計算效率較低。為此，提出一種基于跡最小編輯距離的、事件日志的批量跡與過程模型的多視角對齊方法。首先選取事件日志中的多條跡組成批量跡，使用過程挖掘算法得到批量跡的日志模型；進而獲取日志模型與過程模型的乘積模型及其變遷系統，即為批量跡的搜索空間；然后設計基于Petri網變遷序列集合與剩余跡的最小編輯距離的啟發函數來加快A^*算法；最后設計可調節數據和資源視角所占權重的多視角代價函數，在乘積模型的變遷系統上提出批量跡中每條跡與過程模型的多視角最優對齊方法。仿真實驗結果表明，相比已有工作，在計算批量跡與過程模型間的多視角對齊時，所提方法占用更少的內存空間和使用更少的運行時間。該方法提高了最優對齊的啟發函數計算速度，可以一次獲得批量跡的所有最優對齊，進而提高了事件日志與過程模型的多視角對齊效率。

關鍵詞：過程模型； 一致性檢測； 多視角； 批量跡； 最優對齊

中圖分類號：TP311

文獻標志碼：A

文章編號：1001-3695（2023）07-019-2045-08

doi：10.19734/j.issn.1001-3695.2022.12.0788

Multi-perspective alignment between batch traces of event log and process model

Sun Jinyong¹， Deng Wenwei¹， Xu Qian¹， Sun Zhigang^2?

（1.Guangxi Key Laboratory of Trusted Software， Guilin University of Electronic Technology， Guilin Guangxi 541004， China; 2.School of Computer Science amp; Engineering， Guangxi Normal University， Guilin Guangxi 541004， China）

Abstract：In the consistency detection of business process discovery research， existing methods of multi-perspective alignment between event logs and process models can only obtain the optimal alignment of one trace with the process model at a time. Meanwhile the computation of heuristic function in obtaining the optimal alignment is complex， leading to low computation efficiency. To solve above problems， the paper proposed a multi-perspective alignment between batch traces of event log and process model based on trace minimum edit distance. Firstly， the study selected multiple traces in the event log to form batch traces， and used a process mining algorithm to obtain the log model of the batch traces. Then it obtained the product model of log model and process model and their transition system， which was the search space of batch traces. Then it designed a heuristic function based on the minimum edit distance between Petri net transition’s sequence set and the remaining traces to speed up the A^* algorithm. Finally， the study designed a multi-perspective cost function that could adjust the weight of data and resource perspectives， and proposed a method of multi-perspective optimal alignment between each trace in the batch traces and the process model with the transition system of the product model. Compared with existing work， the simulation results show the proposed method takes up less memory space and uses less running time. This method improves the computation speed of heuristic function for optimal alignment， and obtains all optimal alignments of batch traces at one time， thus improves the efficiency of multi-perspective alignment between event logs and process models.

Key words：process model; conformance checking; multi-perspective; batch traces; optimal alignment

0 引言

在大數據時代背景下，現代企業和組織的業務過程越來越復雜，這給業務過程管理帶來了挑戰。現代企業和組織從業務處理日志中提取業務過程模型的需求逐漸增加。目前，業務過程挖掘在企業和組織的業務過程管理中正發揮著越來越重要的作用^［1，2］。業務過程挖掘關注發現新業務過程，分析和改進己發布的業務過程，是近年來的研究熱點^［3］。業務過程挖掘主要包括過程發現、一致性檢測、過程改進這三種應用類型^［4］。其中，一致性檢測是將觀測到的業務過程行為與發布的業務過程模型進行比對，找出兩者之間的差異和共性，以判斷觀測到的業務過程行為是否合規或與發布的業務過程模型是否一致，并發現存在的問題。

一致性檢測方法能夠確定出事件日志與業務過程模型的偏差，而偏差的定位可以由事件日志與業務過程模型之間的、與字符序列比對類似的比對方法實現。例如，圖1中的業務過程模型P₁表示某銀行的一個簡化的貸款過程，其中活動A為“接受貸款申請”，B為“審查資格”，C為“反饋審查合格”，D為“反饋審查不合格”，E為“發放貸款資金”，F為“記錄日志”。假設在處理某個貸款申請的過程中，發生了事件序列{A， B， E， F}，那這個處理過程是否合規就可以通過一致性檢測來判斷。一致性檢測方法可以得到{A， B， E， F}與過程模型P₁的比對結果，如圖2所示。可以看出事件序列{A， B， E， F}不合規，原因是缺失了活動C。在實際的業務過程中，活動還可能附帶數據和資源信息，因此一致性檢測不能僅關注業務過程的控制流，也要關注數據流和資源信息。

Rozinat等人^［5］提出一種基于托肯重演的一致性檢測方法。該方法在Petri網中重演事件日志的跡，記錄丟失和剩余的令牌數，用以計算事件日志與過程模型的擬合度，但不能準確定位導致不一致性的偏差^［6］。為此，Adriansyah等人^［7］提出對齊方法來發現事件日志與過程模型間的偏差，偏差的檢測可以轉換為事件日志中的事件序列與過程模型重演生成的活動序列之間的比對問題，可以準確定位偏差出現的活動或位置。所有對齊中偏差最少的對齊被稱為最優對齊。此后，對齊方法迅速成為一致性檢測的標準技術^［8］，其對齊結果可用于模型修復^［9］、決策挖掘^［10］、精確度檢查^［11］等。Adriansyah^［12］提出一種計算跡與過程模型間的最優對齊方法，但一次只能獲得一條跡與過程模型的最優對齊。由于業務過程的事件日志包含多條跡，這就需要反復多次構造搜索空間進行求解，以致效率低而且時間和空間復雜度高。田銀花等人^［13］提出一種基于Petri網模型的批量跡與過程模型對齊方法，構造一次搜索空間可以獲取多條跡與過程模型的最優對齊，提高了事件日志中跡與過程模型之間的一致性檢測效率。以上對齊方法主要關注了業務過程的控制流，只能檢查控制流視角的一致性，并不能檢測數據和資源視角的一致性。

De Leoni等人^［14］從控制流、數據和資源這三個視角進行跡與過程模型的對齊，先進行控制流視角對齊，再考慮數據和資源視角的對齊。該方法主要關注控制流視角，因而可能會將控制流視角的偏差診斷為數據和資源視角的偏差，導致錯誤的判斷。為此，Mannhardt等人^［15］提出一種同時考慮控制流、數據和資源視角的對齊方法，為控制流、數據和資源視角設置相同的權重，從而獲得更準確的對齊。該方法不能根據業務過程的需要為數據和資源視角分配不同的權重，因此求得的最優對齊不符合業務過程模型的需求。Zhang等人^［16］使用模糊集合來評估數據視角偏差的嚴重程度，對數據視角偏差進行更細粒度的評估，提高了對數據視角偏差的分析能力。現有多視角對齊方法只能一次獲得一條跡與過程模型的最優對齊，并且最優對齊求解過程中的啟發函數計算復雜，以致最優對齊的計算效率較低且時間和空間復雜度高。

針對多視角對齊存在的問題，本文同時從多視角和批量對齊兩個方面出發，研究跡與過程模型間的對齊問題，提出了一種多視角的批量跡對齊方法，通過構造一次批量跡與過程模型的搜索空間來實現批量跡與過程模型的多視角對齊，以提高最優對齊的計算效率。首先，使用基于區域的迭代挖掘算法^［17］獲取事件日志中批量跡的活動序列對應的日志模型，接著獲取日志模型與過程模型的乘積模型，以及乘積模型對應的變遷系統。然后，改造A^*算法，提出一種變遷序列集合與剩余跡的最小編輯距離方法，用于A^*算法中啟發函數的計算，可提高啟發函數的計算速度。最后，在該變遷系統基礎上，針對不同的業務過程需要，本文使用自定義多視角代價函數，提出了批量跡中每條跡與過程模型的多視角最優對齊的計算方法。與現有多視角對齊方法相比，本文多視角的批量跡對齊方法可以在同一個批量跡的搜索空間中獲取批量跡的多視角最優對齊，降低了搜索過程中占用的內存空間，也提高了計算多視角最優對齊的速度。

本文的主要貢獻如下：a）提出一種可調節數據和資源視角所占權重的多視角代價函數;b）設計基于變遷序列集合與剩余跡的最小編輯距離的啟發函數，以此來加快A^*算法的計算;c）提出一種計算批量跡中每條跡與過程模型的多視角最優對齊方法;d）理論證明了本文方法的正確性，實驗驗證了本文方法占用更少的內存空間和使用更少的運行時間，效率更高。

1 預備知識

1.1 基本概念

標簽Petri網是工作流網^［18］的抽象表達形式，具有強大的表達能力，非常適用于業務過程建模。故本文選用標簽Petri網來建模業務過程，研究基于Petri網的事件日志與過程模型的多視角對齊方法。為方便表述，在不產生混淆的情況下，下文中提到的Petri網均指標簽Petri網。

2 批量跡與過程模型的多視角對齊方法

本文提出的批量跡與過程模型的多視角對齊方法（multi-perspective alignment between batch traces and process model，MABP）的流程如圖3所示。該方法可分為構造搜索空間和獲取多視角最優對齊兩個步驟。

首先，使用挖掘算法獲取事件日志中批量跡的活動序列的日志模型；接著獲取日志模型與過程模型的乘積模型及其變遷系統；然后，使用多視角代價函數，在乘積模型的變遷系統上求解批量跡中每條跡與過程模型的多視角最優對齊。

記業務過程的事件日志為L，事件日志的批量跡日志為L₁，現有的過程模型為N₂。首先，使用基于區域的迭代挖掘算法^［17］挖掘L₁的所有跡的活動序列日志模型，記為N₁。該挖掘算法可以保證從L₁中得到完全擬合跡的日志模型，即N₁能夠重演L₁中的任意一條跡。然后，根據定義8計算得到N₁和N₂的乘積模型N₃。最后，根據定義2獲得N₃的變遷系統S₃，S₃即為L₁中所有跡與過程模型N₂的搜索空間。現有的多視角對齊方法每次求解一條跡的最優對齊都要構造一次搜索空間，本文方法構造一次搜索空間就可以實現批量跡（即多條跡）與過程模型的多視角對齊，從而減少了搜索空間所占用的內存空間。

2.1 現有多視角對齊方法的改進策略

本文考慮同時從控制流、數據和資源這三個視角進行跡與過程模型的對齊。針對現有的多視角對齊方法中多視角代價函數^{［15，16］}和啟發函數^{［23，24］}的不足，本文提出兩種改進策略：策略1提出可調節數據和資源視角所占權重的多視角代價函數，策略2提出基于跡最小編輯距離的啟發函數。

對于策略1，由于定義5的標準多視角代價函數^［15］為數據和資源視角分配了相同權重，不能根據過程模型的實際業務需求為兩者分配不同的權重，所以有時獲得的最優對齊不符合過程模型的一致性檢測需求。鑒于此，本文提出了一個新的多視角代價函數，如定義9所示。

定義9 自定義多視角代價函數。多視角代價函數c（b）可以表示為移動分配代價值，其中b=（a，t）是跡與過程模型對齊中的一個任意移動。

根據定義9所示的代價函數，跡與過程模型之間對齊的代價值（即所有移動的代價之和）最小的對齊，即為最優對齊。

計算跡與過程模型的最優對齊可以建模為在有向圖中搜索代價最小路徑的問題^［25］。一般的思路為：首先根據定義9，為變遷系統的邊加上權值，構成加權有向圖。然后，在加權有向圖的基礎上，使用A^*算法可以較快地找出初始標識節點v₀∈S到結束標識節點的代價最小路徑。每個標識節點v的搜索代價由評價函數f（v）=g（v）+h（v）確定，其中：g：S→R⁺是從初始標識節點v₀到標識節點v的最短路徑代價；h：S→R⁺是從標識節點v到結束標識節點最短路徑的估計代價，也稱為啟發函數。如果啟發函數h（v）估計代價總是小于等于真實代價，A^*算法可以保證找到總體代價最小的路徑。

對于策略2，啟發函數h（v）的定義可以采用不同的策略。文獻［24］利用了Petri網標記方程的策略，文獻［25］利用生成BPMN模型的可能狀態空間策略。文獻［23，24］的啟發函數h（v）值的計算需要求解整數線性規劃方程，具有指數級的時間復雜度。鑒于此，本文先給出Petri網標識節點的變遷序列集合的定義，然后使用變遷序列集合與剩余跡（即跡與過程模型對齊時，跡中剩余的待對齊活動序列）等術語來定義啟發函數。

定義10 Petri網標識節點的變遷序列集合。設N=（P，T，F，α，m_i，m_f）是一個Petri網，S=R（m_i）表示從初始標識m_i可達的所有標識節點集合。對任意的標識節點m_k∈S，定義m_k的變遷序列集合為Σ_mk，Σ_mk表示從m_k到結束標識m_f的所有變遷序列組成的集合。

對于帶有循環結構的Petri網，標識節點到結束標識節點存在無限多個變遷序列。為了使變遷序列集合中的變遷序列有限，本文給出如下定理。

定理1 變遷序列長度小于等于2×max+min的Petri網標識節點的變遷序列集合必定包含跡與過程模型的最優對齊所對應的所有變遷序列。其中，max表示日志中跡的最大長度，min表示過程模型生成變遷序列的最小長度。

證明 使用反證法。假定存在跡σ與過程模型的最優對齊所對應的所有變遷序列中存在長度大于2×max+min的變遷序列u，則跡σ與變遷序列u的最優對齊，非同步移動的次數大于2×max+min-|σ|。跡σ與過程模型最優對齊的最壞情況為跡σ中的活動全部為日志移動和過程模型生成最短的變遷序列且變遷全部為模型移動，非同步移動次數為|σ|+min。因為跡σ的長度小于等于max，則跡σ與變遷序列u的最優對齊的非同步移動次數大于|σ|+min，不可能為跡σ與過程模型的最優對齊，所以假設不成立。因此，變遷序列長度小于等于2×max+min的Petri網標識節點的變遷序列集合必定包含跡與過程模型的最優對齊所對應的所有變遷序列。

本文采用基于Petri網標識節點的變遷序列集合與剩余跡最小編輯距離的策略來定義啟發函數h（v）。具體思路如下：首先根據定義10獲得過程模型標識節點的變遷序列集合，其變遷序列長度均小于等于2×max+min;然后，在變遷系統上進行最優對齊時，計算當前跡剩余的活動序列與過程模型對應標識節點變遷序列集合中每條變遷序列的編輯距離^［22］，并選出最小值作為當前啟發函數h（v）的取值。

本文方法與文獻［25，26］可以得到相同的h（v）值。經分析，本文方法的時間復雜度為O（nlk），其中，n表示過程模型對應的標識節點的變遷序列集合中變遷序列的個數，l表示變遷序列集合中變遷序列的平均長度，k表示跡剩余的活動序列長度。其時間復雜度是多項式級的，相比文獻［25，26］的指數級時間復雜度，本文方法降低了計算啟發函數h（v）的時間復雜度。

2.2 獲取多視角最優對齊

獲取最優對齊的主要思路是針對批量跡中的某條跡，從乘積模型變遷系統的初始標識節點開始，依據標識節點的評價函數f（v）的最小原則向前搜索，直到當前標識節點屬于結束標識節點集，搜索結束。在當前標識節點所記錄的移動序列中，對其第1行中的活動所對應的事件屬性和第2行中的變遷的約束變量進行賦值，即為該跡與過程模型的多視角最優對齊。跡與過程模型的移動序列的形式如圖4所示，其中第1行為活動序列〈a₁，a₂，a₄，a_n〉，第2行為變遷序列〈t₁，t₃，t₄，t_m〉。

2.2.1 過程模型變遷的約束變量處理方法

基于定義9的自定義多視角代價函數，在乘積模型的變遷系統上搜索批量跡與過程模型的多視角最優對齊時，標識節點所記錄的移動序列就是批量跡中每條跡與過程模型的控制流視角的前綴對齊。這需要計算移動序列的第2行元素對應變遷的約束變量值，使得移動序列的代價值最小。為了解決這個問題，本文對文獻［14］中變遷的約束變量值處理方法進行改進，提出根據過程模型的不同業務需求，可以給數據和資源約束設置不同的權重。處理方法可以分為如下兩步：a）將移動序列第2行元素對應變遷中的數據約束變量記為d₁，…，d_n，將資源約束變量記為r₁，…，r_m；b）根據過程模型中變遷的數據約束和資源約束，分別為數據約束變量和資源約束變量確定約束條件t₁（d₁），…，t_n（d_n），t_n+1（r₁），…，t_n+m（r_m），則求解移動序列的代價值最小問題可以建模為

其中：w₁、w₂分別為所有數據約束變量、資源約束變量的權重系數，分別來自定義9中的w₁、w₂;f_i（d_i）表示第i個數據約束變量的布爾約束，f_n+j（r_j）表示第j個資源約束變量的布爾約束，其中，i=1，2，…，n，j=1，2，…，m。例如，對于f_n（d_n），如果數據約束變量d_n與跡中對應活動的屬性值相同，則f_n（d_n）=0，否則f_n（d_n）=1。式（3）所示的移動序列代價值最小問題本質上即為一個混合整數線性規劃問題（mixed integer linear programming，MILP）。

2.2.2 多視角最優對齊算法

本文為多視角最優對齊方法MABP設計了實現算法，稱之為MABP算法。下面給出MABP算法的偽代碼，變量和函數的定義分別如表1、2所示。

算法1 多視角對齊算法MABP

輸入：批量跡的日志L;多視角代價函數c（）;過程模型N的標識節點的變遷序列集合;乘積模型的變遷系統S_l×p。

輸出：批量跡中每條跡與過程模型之間多視角的最優對齊optAlign。

foreach all σ_i∈L do

selNodeSet←?; canNodeSet←{srnode}; mv_seq（srnode）←?;

while canNodeSet ≠? do

curnode←curnode∈canNodeSet minimizing f（curnode）;

//從候選節點集中選取當前標識節點

if curnode∈tgtNodeSet then //返回當前跡的多視角最優對齊

optAlign=align（mv_seq（curnode））;

return optAlign;

else

selNodeSet←selNodeSet∪{curnode}; canNodeSet ←canNodeSet－{curnode};

foreach all sucnode∈sucNodeSet（curnode） do

//遍歷當前標識節點的后繼標識節點

if（π₁（mv_seq（curnode）amp;mv（curnode， sucnode））_↓A）∈pre（σ_i） then

if sucnodeselNodeSet then

t=h（sucnode）; mv=mv_seq（curnode）amp;mv（curnode，sucnode）; a=cmin_seq（mv）;

if sucnode∈canNodeSet then

if g（sucnode）gt;a then

g（sucnode）=a;f（sucnode）=a+t; mv_seq（sucnode）=mv;

else

canNodeSet←canNodeSet∪{sucnode}; g（sucnode）=a;

f（sucnode）= a+t; mv_seq（sucnode）=mv;

在算法MABP中，第2行用于初始化已選標識節點集、候選標識節點集、初始節點的移動序列;第5～7行，在當前標識節點屬于結束標識節點集時，返回當前跡的多視角最優對齊optAlign;第8～19行對當前標識節點的后繼標識節點進行處理。本文的候選標記節點集canNodeSet使用優先隊列存儲，并按照標識節點的評價函數f（v）降序排序。這樣可以在O（1）的時間內從canNodeSet中選出當前標識節點，從而加快查找當前標識節點的速度。

2.3 多視角對齊方法MABP的實例

本節使用實例展示MABP方法的執行過程。給定如圖5所示過程模型N_p，變遷的數據和資源約束如表3所示。其中，數據的約束變量為Amount，資源的約束變量為E_a、E_b、E_c，N_p是一個合理的工作流網^［18］。在圖5中將標簽為a、b、c的變遷分別標記為t₁、t₂、t₃。

1）從事件日志中挖掘日志模型

給定事件日志L如表4所示，針對L中所有跡的活動序列，使用基于區域的迭代挖掘算法^［17］，可以得到如圖6所示的工作流網N_l，N_l即為日志模型。

2）獲取日志模型和過程模型的乘積模型

計算日志模型N_l和過程模型N_p的乘積模型N_l×p，如圖7所示。

3）獲取乘積模型的變遷系統

乘積模型N_l×p的變遷系統S_l×p如圖8所示。其中，標識節點代表乘積模型的可達標識，無起點箭頭指向的標識節點特指乘積模型的初始標識，灰色標識節點指乘積模型的結束標識。各有向邊的標注為乘積模型的可達標識之間的觸發變遷。

現在以跡σ=〈（a，{R=Sue，A=900}），（c，{E=Pete}）〉和圖8的變遷系統S_l×p為例，展示算法MABP的執行過程。使用定義9的自定義多視角代價函數，為了計算方便，設置定義9中的權重系數w₁=1.0、w₂=1.0。在S_l×p的搜索過程中存儲標識節點和連接順序，如圖9所示，圖中每個搜索標識節點的詳細信息如表5所示。

算法MABP的執行過程如下：

a）首先，確定變遷系統S_l×p的初始標識為［p₁，p′₁］，對應的移動序列為〈〉。生成一個查找標識節點記為v₁，該標識節點放入canNodeSet集合中。v₁的移動序列為〈〉，其代價值g（v₁）=0。標識節點v₁對應過程模型N_p的標識節點的變遷序列集合為{〈a，c〉，〈b，c〉}，跡σ剩余的活動序列為〈a，c〉，可得h（v₁）=0，f（v₁）=g（v₁）+h（v₁）=0。

b）將canNodeSet中的標識節點v₁作為當前標識節點，同時將v₁從canNodeSet中移除。v₁的標識［p₁，p′₁］在變遷系統中有4個出邊，對應生成的后繼標識節點v₂、v₃、v₄、v₅，將它們放入canNodeSet中。其中，v₂經由變遷（t′₁，gt;gt;）到達。（t′₁，gt;gt;）為日志移動，代價值為1，對應的移動為（a，gt;gt;）。因此v₂的移動序列為〈〉∪〈（a，gt;gt;）〉=〈（a，gt;gt;）〉，其代價值g（v₂）=0+1=1。標識節點v₂對應過程模型N_p的標識節點的變遷序列集合為{〈a，c〉，〈b，c〉}，跡σ剩余的活動序列為〈c〉，可得h（v₂）=1，f（v₂）=g（v₂）+h（v₂）=2。同理，可以求得v₃、v₄、v₅的移動序列和g（）、h（）、f（）的值。

c）此時，canNodeSet中標識節點排列順序為v₃、v₂、v₄、v₅。根據算法MABP，取出canNodeSet中的隊首標識節點v₃作為當前標識節點，同時將v₃從canNodeSet中移除。v₃的標識［p₂，p′₂］在變遷系統中有4個出邊，其中邊（［p₂，p′₂］，（t′₂，gt;gt;），［p₂，p′₃］）指向的后繼標識對應的移動序列為〈（a，t₁），（b，gt;gt;）〉，其第1行在活動集的投影得到的序列為〈a，b〉。〈a，b〉不是跡σ的前綴，因此該標識節點不予考慮。根據標識［p₂，p′₂］的出邊，生成3個后繼標識節點v₆、v₇、v₈，并放入canNodeSet。

d）獲取多視角最優對齊結果。由c）中可得，候選標識節點節點集canNodeSet中標識節點排列順序為v₆、v₂、v₄、v₅、v₇、v₈。根據算法MABP，取出canNodeSet中的隊首標識節點v₆作為當前標識節點，同時將v₆從canNodeSet中移除。該標識節點的標識［p₃，p′₃］為變遷系統S_l×p的結束標識，說明此時已找到最優對齊。圖10展示了v₆標識節點對應的移動序列，其第2行元素對應變遷的約束變量的求解，得到跡σ與過程模型N_p的多視角最優對齊為〈（a{Sue，900}，t₁{Sue，1000}），（c{Pete}，t₃{Pete}）〉，代價值為1。

圖9中的v₆標識節點的移動序列〈（a，t₁），（c，t₃）〉對應的控制流視角的對齊如圖10（a）所示。首先為過程模型N_p中的變遷t₁，t₃的約束變量標記為R₁，A₁，E₁，如圖10（b）所示。然后根據變遷t₁，t₃的數據和資源約束，為約束變量設置約束，對齊過程中過程模型N_p對應變遷t₁，t₃的約束變量值求解轉換為混合整數線性規劃問題求解最小偏差，如圖10（c）所示。目標函數是v₆標識節點的移動序列的最小代價值，即布爾變量值的總和。

2.4 多視角對齊方法MABP的正確性分析

假設事件日志L₁=〈σ₁，σ₂，σ₃，…，σ_n〉，根據L₁中跡對應的活動序列，采用基于區域理論的迭代挖掘算法^［17］得到日志模型記做N₁=（P₁，T₁，F₁，α₁，m_i，1，m_f，1），過程模型N₂=（P₂，T₂，α₂，m_i，2，m_f，2），兩者的乘積模型為N₃=（P₃，T₃，F₃，α₃，m_i，3，m_f，3），記乘積模型的變遷系統為S₃。為了方便表述，對S₃變遷上的標記做如下修改：設原標記為（x，y），若x≠gt;gt;，則原標記更改為（α₁（x），y）。在S₃中，從初始標識節點到結束標識節點的所有變遷序列組成的集合記為Λ。Γ_L1，N₂表示日志L₁與過程模型N₂之間所有對齊的集合。Γ_L1，N₂，c表示日志L₁與過程模型N₂之間的、基于定義9的自定義多視角代價函數的所有最優對齊的集合。

定理2表明了事件日志中的任意一條跡與過程模型之間的對齊，都可以在乘積模型對應的變遷系統中找到一個從初始標識節點到結束標識節點的變遷序列與之對應。

推理1 給定\"σ∈L₁，MABP算法的計算結果是align（σ）∈Γ_L1，N₂，c。

根據定理2，Λ中包含了任一條跡σ與N₂之間的所有對齊。其中肯定包含了L₁中所有跡與N₂的最優對齊。MABP算法是在改進A^*算法的基礎上得到的，在搜索過程中計算標識節點的移動序列和代價值。MABP算法既能保證當前搜索標識節點的移動序列的第1行在活動集的投影是跡σ的前綴，又能保證搜索結束時標識節點的代價值最小。因此MABP算法能查找到L₁中σ與N₂之間的最優對齊。

3 實驗結果與分析

3.1 數據集和實驗設置

本文使用軟件PLG2.0^［26］生成索賠申請過程模型^［27］的事件日志，來構造本文的實驗數據集。索賠申請過程的Petri網模型N_s與數據和資源約束分別如圖11、表6所示。首先用戶提出索賠申請（register request）。當索賠申請金額小于1 000元時進行粗略檢查（examine casually），大于或等于1 000元時進行仔細檢查（examine thoroughly），與此同時進行檢票（check ticket）；對索賠申請進行決定（decide）。公司支付賠償（pay compensation）或者拒絕請求（reject request）或者需要更多的檢查（reinitiate request）。

模型N_s雖然簡單，但包含了工作流網的順序結構、選擇結構、并發結構和循環結構四種基本結構。因此，使用模型N_s及其跡來檢驗本文方法的正確性有代表意義，可以說明本文方法的健壯性和適應性。

本文使用PLG2.0根據模型N_s生成實驗所用事件日志。這些事件日志的命名規則為Logx-y，x為跡的數量，y表示為該事件日志中跡的平均長度，共12個事件日志。生成事件日志的相關信息如表7所示。

為了模擬真實業務過程實例的異常發生情況，本文分別在表7中的每個事件日志中選取0%、10%、30%和50%的案例，通過隨機刪除和增加事件、或修改事件屬性的方式在每條跡中人工地插入3～10個噪聲。0%表示不插入噪聲。為每個事件日志均生成包含四個不同噪聲比例的事件日志，例如為事件日志Log10-5生成對應噪聲事件日志為Log10-5-0.0、Log10-5-0.1、Log10-5-0.3、Log10-5-0.5。其中噪聲事件日志名中最后的小數代表噪聲比例，共生成48個事件日志。取每種噪聲比例的事件日志各做10次實驗，統計其計算時間和生成搜索空間標識節點數的平均值。

本文實驗使用定義9的多視角代價函數對對齊中出現的偏差進行度量。通過對索賠申請過程的Petri網模型N_s及其數據和資源約束進行分析可以發現，用戶更加注重索賠的金額而不關心實際的事務處理者。在模型N_s與其跡的對齊中，相比于資源視角，應該為數據視角分配更大的權重，因此暫設定義9中的權重系數w₁=3.0、w₂=1.0。在實際應用中，可以先由領域專家確定w₁、w₂的大致范圍，再用網格搜索法確定最優的w₁、w₂數值。

本文的實驗環境如下：操作系統Windows 11，處理器9th Gen Intel^? Core i5-9500@3.00 GHz；內存8 GB；在軟件環境PyCharm 2018.1.4中配置Python 3.6。

3.2 實驗結果分析

3.2.1 自定義多視角代價函數的有效性分析

為了分析不同多視角代價函數對多視角最優對齊計算的影響，本文使用事件日志Log20-11-0.5開展實驗。分別在定義5的標準多視角代價函數和定義9的自定義多視角代價函數上，使用MABP算法計算Log20-11-0.5中每條跡與過程模型的多視角最優對齊。記錄所有跡的最優對齊中數據視角偏差和資源視角偏差的次數，即事件的數據屬性和過程模型的數據約束變量值不同的次數，結果如表8所示。

從表8可以看出，使用定義9的多視角代價函數進行最優對齊會產生更少的數據偏差，獲得的最優對齊更符合過程模型N_s的實際業務需求。這是因為通過使用定義9的多視角代價函數，可以根據過程模型N_s的實際業務需求給數據視角分配更高權重，進而使得最優對齊中有更少的數據偏差，更加符合過程模型N_s的業務需求。

3.2.2 多視角對齊算法MABP的空間效率分析

本實驗在事件日志Log10-y和Log20-y對應的噪聲事件日志上（其中y∈［5，8，11，14，17，21］），比較MA1^［15］、MA2^［16］和MABP算法在計算事件日志中每條跡與過程模型的多視角最優對齊時，記錄生成搜索空間的標識節點數，以此來確定算法的空間開銷，實驗結果如圖12所示。其中橫坐標軸代表事件日志中跡的平均長度，縱坐標軸代表生成搜索空間的標識節點數。

從圖12可以發現，隨著事件日志中跡平均長度的增加，所生成的搜索空間內標識節點的數量會不斷增加并且MA1^［15］和MA2算法^［16］與MABP算法生成搜索空間的標識節點數的比值越來越大。這是因為當跡的長度增加時，可能會出現更多的循環，MA1^［15］和MA2算法^［16］會為相同的標識建立多個搜索標識節點，而MABP算法對一個標識只建立一個搜索標識節點。由于無論事件日志包含多少條跡，MABP算法只需建立一次搜索空間；而MA1^［15］和MA2算法^［16］建立搜索空間的次數與跡的數目是相同的。即當事件日志中跡的數量為10時，需建立10個搜索空間，而當跡的數量為20時，需建立20個搜索空間。相比之下，MABP算法節約了大量的存儲空間。

3.2.3 多視角對齊算法MABP的時間效率分析

本實驗在事件日志Log10-y和Log20-y對應的噪聲事件日志上（其中y∈［5，8，11，14，17，21］），比較MA1^［15］、MA2^［16］和MABP算法在獲取事件日志中所有跡的多視角最優對齊時的運算時間，實驗結果如圖13所示。

從圖13可以看出，當事件日志中跡的平均長度增加時，無論是MA1^［15］、MA2算法^［16］還是MABP算法計算所有跡與過程模型的多視角最優對齊所花費的時間均有一定增加。原因是當跡長度增加時，對齊操作需要進行更多的匹配，從而導致計算多視角最優對齊的時間增加。從圖13可得，MABP算法更優。這是因為MA1^［15］和MA2算法^［16］會為一個標識節點建立多個搜索標識節點，而MABP算法為一個標識節點只建立一個搜索標識節點，所以MABP算法的對齊操作需要數量更少的匹配，運行時間更少。在獲取多視角最優對齊時，MA1算法^［15］使用Petri網標記方程的策略^［24］設計啟發函數，MA2算法^［16］使用生成BPMN模型的可能狀態空間的策略^［25］設計啟發函數，其時間復雜度都是指數級。MABP算法使用Petri網標識節點的變遷序列集合與剩余跡最小編輯距離的策略設計啟發函數（見2.1節的策略2），其時間復雜度是多項式級，從而減少了啟發函數的計算時間。

由以上實驗可以得出，計算事件日志的批量跡與過程模型的多視角對齊時，相比MA1^［15］、MA2算法^［16］，MABP算法的確生成了更少的搜索標識節點（即占有更少的內存）并使用更少的計算時間，進而提高了多視角最優對齊的計算效率。

4 結束語

一致性檢測在過程挖掘中發揮著越來越重要的作用，對齊是一致性檢測中最先進和應用最廣泛的方法。但是，現有的多視角對齊方法只能一次獲得一條跡和過程模型的多視角最優對齊。業務過程的事件日志中包含多條跡，這就需要反復多次地構造搜索空間進行求解，以致時間和空間復雜度高、效率低。本文提出一種基于事件日志的批量跡與過程模型的多視角對齊方法。先使用挖掘算法獲取事件日志中批量跡活動序列的日志模型，接著獲取日志模型與過程模型的乘積模型及其變遷系統。改造A^*算法，采用基于Petri網標識節點的變遷序列集合與剩余跡最小編輯距離的策略來設計啟發函數，降低了計算啟發函數的時間復雜度。在乘積模型的變遷系統基礎上，針對不同的業務過程需求，使用自定義的多視角代價函數，本文方法構造一次搜索空間即可求得批量跡與過程模型的多視角最優對齊。仿真實驗結果表明，相比于MA1、MA2算法，MABP算法的運行時間更少、空間占用率更低，說明MABP算法提高了多視角最優對齊的計算效率。

本文方法實現了事件日志的批量跡與過程模型間的多視角對齊，由于每條跡與過程模型間的對齊過程是獨立的，所以在處理復雜業務過程模型的多視角對齊時用時較多。在未來研究中，將設計批量跡與過程模型的多視角對齊的并行算法，以進一步提高多視角對齊的速度。本文方法可以應用于現代企業和組織的業務過程模型的修復與增強，以進一步提高其業務過程模型的質量。目前將本文方法應用于現代企業和組織的業務過程管理系統的難點是：這些系統生成的日志形式多樣，如何對這些系統日志文件進行預處理，將其轉換成標準的事件序列形式。

參考文獻：

[1]Leno V， Polyvyanyy A， Dumas M， et al. Robotic process mining： vision and challenges［J］.Business amp; Information Systems Engineering，2021，63（3）：301-314.

［2]Van Der Aalst W M P. Process mining： a 360 degree overview［M］//Van Der Aalst W M P， Carmona J. Process Mining Handbook. Lecture Notes in Business Information Processing.Cham：Springer，2022：3-34.

［3]Sani M F， Gonzalez J J G， Van Zelst S J， et al. Conformance che-cking approximation using simulation［C］//Proc of the 2nd International Conference on Process Mining.Piscataway，NJ：IEEE Press，2020：105-112.

［4]Fani S M， Van Zelst S J， Van Der Aalst W M P. Conformance checking approximation using subset selection and edit distance［M］//Dustdar S， Yu E， Salinesi C， et al. Advanced Information Systems Engineering.Cham：Springer，2020：234-251.

［5]Rozinat A， Van Der Aalst W M P. Conformance checking of processes based on monitoring real behavior［J］.Information Systems，2008，33（1）：64-95.

［6]Adriansyah A， Van Dongen B F， Van Der Aalst W M P. Towards robust conformance checking［M］//Muehlen M， Su Jianwen. Business Process Management Workshops.Berlin：Springer，2010：122-133.

［7]Adriansyah A， Munoz-Gama J， Carmona J， et al. Alignment based precision checking［M］//La Rosa M， Soffer P. Business Process Management Workshops.Berlin：Springer，2012：137-149.

［8]Van Zelst S J， Bolt A， Hassani M， et al. Online conformance che-cking： relating event streams to process models using prefix-alignments［J］.International Journal of Data Science and Analytics，2019，8（3）：269-284.

［9]Fahland D， Van Der Aalst W M P. Model repair—aligning process models to reality［J］.Information Systems，2015，47：220-243.

［10]De Leoni M， Van Der Aalst W M P. Data-aware process mining： discovering decisions in processes using alignments［C］//Proc of the 28th Annual ACM Symposium on Applied Computing.New York：ACM Press，2013：1454-1461.

［11]De Leoni M， Maggi F M， Van Der Aalst W M P. An alignment-based framework to check the conformance of declarative process models and to preprocess event-log data［J］.Information Systems，2015，47：258-277.

［12]Adriansyah A. Aligning observed and modeled behavior［D］.Eindhoven：Eindhoven University of Technology，2014.

［13]田銀花，杜玉越，韓咚，等.基于Petri網的批量跡與過程模型校準［J］.計算機學報，2018，41（3）：611-627.（Tian Yinhua， Du Yuyue， Han Dong， et al. Alignments between batch traces and process models based on Petri nets［J］.Chinese Journal of Computers，2018，41（3）：611-627.）

［14]De Leoni M， Van Der Aalst W M P. Aligning event logs and process models for multi-perspective conformance checking： an approach based on integer linear programming［C］//Proc of the 11th International Conference on Business Process Management.Berlin：Springer，2013：113-129.

［15]Mannhardt F， Leoni M， Reijers H A， et al. Balanced multi-perspective checking of process conformance［J］.Computing，2016，98（4）：407-437.

［16]Zhang Sicui， Genga L， Yan Hui， et al. Towards multi-perspective conformance checking with fuzzy sets［J］.International Journal of Interactive Multimedia and Artificial Intelligence，2021，6（5）：134-141.

［17]Van Dongen B F，Busi N，Pinna G M，et al. An iterative algorithm for applying the theory of regions in process mining［C］//Proc of Workshop on Formal Approaches to Business Processes and Web Services.Siedlce，Polen：Publishing House of University of Podlasie，2007：36-55.

［18]林闖，田立勤，魏丫丫.工作流系統模型的性能等價分析［J］.軟件學報，2002，13（8）：1472-1480.（Lin Chuang， Tian Liqin， Wei Yaya. Performance equivalent analysis of workflow systems［J］.Journal of Software，2002，13（8）：1472-1480.）

［19]田銀花，杜玉越，韓咚，等.基于Petri網的事件日志與過程模型對齊方法［J］.計算機集成制造系統，2019，25（4）：809-829.（Tian Yinhua， Du Yuyue， Han Dong， et al. Alignments between batch traces and process models based on Petri nets［J］.Computer Integrated Manufacturing System，2019，25（4）：809-829.）

［20]韓咚，田銀花，杜玉越，等.基于Petri網可達圖的業務對齊方法［J］.計算機集成制造系統，2020，26（6）：1589-1606.（Han Dong， Tian Yinhua， Du Yuyue， et al. Business alignments based on reachable graphs of Petri nets［J］.Computer Integrated Manufacturing System，2020，26（6）：1589-1606.）

［21]Adriansyah A， Van Dongen B F， Van Der Aalst W M P. Confor-mance checking using cost-based fitness analysis［C］//Proc of the 15th International Enterprise Distributed Object Computing Conference.Piscataway，NJ：IEEE Press，2011：55-64.

［22]Sani F M， Zelst S J， Van Der Aalst W M P. Conformance checking approximation using subset selection and edit distance［M］//Dustdar S， Yu E， Salinesi C， et al. Advanced Information Systems Enginee-ring.Cham：Springer，2020：234-248.

［23]Van Der Aalst W， Adriansyah A， Van Dongen B. Replaying history on process models for conformance checking and performance analysis［J］.Wiley Interdisciplinary Reviews：Data Mining and Know-ledge Discovery，2012，2（2）：182-192.

［24]Yan Hui， Van Gorp P， Kaymak U， et al. Aligning event logs to task-time matrix clinical pathways in BPMN for variance analysis［J］.IEEE Journal of Biomedical and Health Informatics，2017，22（2）：311-317.

［25]Dechter R， Pearl J. Generalized best-first search strategies and the optimality of A^*［J］.Journal of the ACM，1985，32（3）：505-536.

［26]Burattin A， Sperduti A. PLG： a framework for the generation of business process models and their execution logs［M］//Muehlen M， Su Jianwen. Business Process Management Workshops.Berlin：Springer，2010：214-219.

［27]Van Der Aalst W. Process mining： data science in action［M］.Berlin：Springer，2016：74-82.