基于日志聚類構造行為子集的近似一致性方法

收稿日期：2021-08-27；修回日期：2021-10-06

基金項目：國家自然科學基金資助項目（61572035，61402011）; 安徽省高校優(yōu)秀人才支持計劃資助項目（gxyqZD2020020）; 安徽省高校領軍骨干人才項目（2020-1-12）; 安徽省學術和技術帶頭人資助項目（2019H239）

作者簡介：王麗麗（1982-），女，安徽安慶人，副教授，碩導，博士研究生，主要研究方向為Petri網、業(yè)務流程挖掘等（64460112@qq.com）；向小陽（1997-），男，重慶萬州人，碩士研究生，主要研究方向為Petri網與過程挖掘；方賢文（1975-），男，河南信陽人，教授，博導，博士，主要研究方向為Petri網和可信軟件等.

摘 要：利用行為子集可以求得事件日志與過程模型之間的近似一致性度，但現有方法得到日志候選跡間的行為差異小，影響了行為子集的代表性而導致近似一致性度的準確度偏低。針對該問題，提出一種應用聚類技術預處理事件日志以構造行為子集的近似一致性方法。首先根據跡之間的Levenshtein編輯距離，將事件日志中具有較高行為相似性的跡聚類成若干個子日志；然后遍歷各子日志，采用簇內高頻和簇中心兩種方法選出子日志中的代表跡，形成候選跡集合；進一步利用最優(yōu)對齊技術構造出模型的行為子集，將其與完整的事件日志進行擬合度計算來得到近似一致性度及其上下界值。最后對現實事件日志進行仿真實驗，從準確度和時間效率兩方面驗證了該方法的優(yōu)越性。

關鍵詞：近似一致性度； 日志聚類； 編輯距離； 候選跡； 行為子集

中圖分類號：TP391.9"" 文獻標志碼：A

文章編號：1001-3695（2022）06-047-1872-07

doi：10.19734/j.issn.1001-3695.2021.08.0432

Approximate consistency method for constructing behavior subsets based on log clustering

Wang Lili， Xiang Xiaoyang， Fang Xianwen

（College of Mathematics amp; Big Data， Anhui University of Science amp; Technology， Huainan Anhui 232001， China）

Abstract：According to the behavior subset， it is able to obtain the approximate consistency between the event log and the process model. However， it obtains small behavior difference between the log candidate traces through the existing methods， which causes some influence on the representativeness of the behavior subset， thus leading to the low accuracy of the approximate consistency. In view of this problem， this paper proposed an approximate consistency method using clustering technology to preprocess event logs for the construction of behavior subsets. Firstly， it clustered the traces with high behavioral similarity in the event log into several sub-logs according to the Levenshtein editing distance between traces. Then， it traversed each sub log， which selected the representative traces in the sub logs by using the methods of high frequency in the cluster and cluster center to form a set of candidate traces. Furthermore， it took advantage of the optimal alignment technique to construct the behavior subset of the model， which calculated the degree of fit with the complete event log to get the approximate consistency and its upper and lower bounds. Finally， it carried out the simulation experiment of real event log， which verified the superio-rity of this method from two aspects of accuracy and time efficiency.

Key words：approximate consistency; log clustering; edit distance; candidate trace; behavior subset

0 引言

隨著信息技術的發(fā)展，信息系統日益成為企業(yè)組織實施和管理業(yè)務的重要載體，它記錄了企業(yè)內部業(yè)務過程的運作情況。過程挖掘以控制流、資源和組織結構等多個角度從信息系統中提取出控制結構或數據屬性等關鍵信息，從而實現對業(yè)務過程的發(fā)現、監(jiān)控及完善，它主要應用于過程發(fā)現、一致性檢查和過程改進三個方面［1，2］。在業(yè)務過程的實際運行中，受資源分配、組織協作、過程瓶頸等多方面的影響，信息系統所記錄的執(zhí)行過程難免與模型描述的行為不一致［3］。一致性檢查能夠反映過程模型與事件日志之間的符合情況，以分析預期行為與實際過程之間的共性和差異，進而實現對日志或者模型的修復、異常行為檢測、算法評估等應用［4］。

一致性檢查通常以事件日志和過程模型作為研究對象。在早期的研究中，Rozinat等人［5］提出了基于令牌（token）重演的方法，當事件軌跡在模型上重演時，依照變遷發(fā)生規(guī)則［1］記錄token在重演過程中的變化來判斷跡與模型的擬合情況。為了形式化表示一致性檢查的過程，后來在重演的基礎上派生出了業(yè)務對齊的方法。然而，最優(yōu)對齊的計算是一個具有較高時間復雜度的NP-hard問題［6］。隨著信息系統記錄的事件數據規(guī)模日益龐大，或者依據業(yè)務過程而建立的模型愈加復雜，基于對齊技術的傳統一致性檢查方法難以適用。然而在許多應用中，并不需要計算每個日志行為與過程模型間的精確對齊，通常只用求出它們的近似一致性度就足夠對業(yè)務過程及系統進行分析。

如何提升一致性檢查的效率是業(yè)務過程管理中的一個熱點研究問題。Munoz-Gama等人［7］利用分解技術將大的過程模型/事件日志劃分為相互獨立的子網/子日志，進而分而治之地計算子網與子日志間的一致性，最終評估整體的一致性。Schuster等人［8］提出一種對過程樹進行近似對齊的方法，根據過程樹的層次結構遞歸地將一個軌跡劃分為子軌跡，分別從子對齊中組合一個有效的對齊。Nolle等人［9］提出了一種基于遞歸神經網絡的深度對齊算法，該方法能在沒有提供參考模型的前提下實時監(jiān)測異常事件并實現自主校正，并且將深度學習思想運用在一致性檢查中，通過減小搜索空間來減少對齊的內存消耗。楊皓然等人［10］通過結合控制流和數據流兩方面，提出了一種基于概率和時間因素的Petri網業(yè)務流程一致性分析方法，利用行為兼容度算法來衡量業(yè)務流程的一致性程度。方賢文等人［11］通過分析控制流網和數據流網交互時的行為包含關系及其影響，進而計算控制流網、數據流網和融合網之間的緊密度，以實現對融合網的變化域和一致性的分析。Bauer等人［12］提出一種基于日志跡抽樣的增量計算近似一致性的方法，該方法能夠提高一致性檢查的速度并為近似值提供界限。為了處理規(guī)模龐大的事件日志，Cao等人［13］提出基于屬性驅動（數據流）的層次聚類方法，根據案例屬性分割成子日志，從句法、特征向量等方面度量跡間距離，并比較各子日志所生成的過程模型，結果得到質量更好的模型。

對齊計算是一致性檢查過程中最耗時的部分［6］。Fanisani等人［14］提出了使用隨機重演Petri網模擬、頻率、k-medoids等方法構造模型行為的子集（行為子集），以此代表完整的模型行為來計算與事件日志之間的近似一致性度，該方法能夠提升一致性檢查效率。然而，近似結果的質量很大程度上取決于構造的行為子集［15］，現有方法對活動序列之間的長度及句法（排列順序）差異要求不高，可能導致子集并不能理想地代表完整的模型行為，從而影響近似結果的準確度。本文在現有研究的基礎上，應用了基于編輯距離的層次聚類方法預處理事件日志，相較于k-medoids方法，分類效果不受人為設定聚類數k值的影響，并且能夠一次性聚類整個過程行為，再提出使用簇內高頻和簇中心的方法提取日志候選跡。通過計算候選跡與過程模型之間的最優(yōu)對齊得到相應的模型跡，這些模型跡組成了用于一致性檢查的行為子集。本文的研究框架如圖1所示。

1 基本概念

關于Petri網的基本定義可以參見文獻［16］，過程挖掘和計算機科學領域中常使用的基本數學概念可以參見文獻［17］，本章主要介紹與本文相關的核心概念。

定義1［6］ 標簽Petri網系統。設N=（P，T，F，λ，mi，mf）是活動集合A上的一個標簽Petri網系統，其中：P、T分別是有限的庫所、變遷集合，且P∩T=；F（P×T）∪（T×F）是流關系;λ：T→Aτ是變遷到活動標簽的映射函數；mi、mf分別是初始、終止標識。

下面給出一個申請貸款流程的標簽Petri網系統，如圖2所示。變遷A代表注冊申請，執(zhí)行該變遷后會在每個后繼庫所中產生一個托肯，以便于執(zhí)行后續(xù)變遷B（能力評估）、C（系統檢查）和D（調查信用度），由于變遷E（同意）和F（拒絕）具有公共前集庫所，故變遷E、F只能執(zhí)行其一，隨后執(zhí)行變遷G（發(fā)送決定）。

定義2［7］ 事件日志。設A是活動的集合，σ∈A是一條活動軌跡，稱L∈β（A）為一個事件日志，其中β（A）是跡的有限非空多重集。

定義3［17］ 移動。設A是活動的集合，T是變遷的集合，元組（a，t）稱為一個移動，且存在以下類別：a）a∈A，t=gt;gt;，則稱（a，t）為一個日志移動;b）若a=gt;gt;，t∈T，則稱（a，t）為一個模型移動;c）若a∈A，t∈T且λ（t）=b，滿足a=b或者a=gt;gt;，t=τ，則稱（a，t）為一個同步移動;d）否則為非法移動。其中，τ表示不可見變遷，gt;gt;（gt;gt;A∪T∪Λ且gt;gt;≠τ）表示“無移動”操作。

定義4［18］ 對齊。設A是活動的集合，σ∈A是一個活動序列，N=（P，T，F，λ）是一個標簽Petri網，σ與N之間的對齊γ∈（Agt;gt;×Tgt;gt;）是滿足如下條件的移動序列：a）π1（γ）↓A=σ，即γ的第一列元素在A上的投影（排除gt;gt;）;b）mi→π2（γ）↓Tmf，由初始標識mi到終止標識mf，可產生γ的第二列元素在T上投影（排除gt;gt;）的變遷序列。

通常一條跡會對應多組對齊，為了選出最優(yōu)的對齊，有必要引入標準代價函數δ：Agt;gt;×Tgt;gt;→R0來量化非同步移動導致的對齊偏差，δ分配給日志移動、模型移動和同步移動的代價值分別為1、1和0。

定義5［18］ 最優(yōu)對齊。設A是活動的集合，σ∈A是一個活動序列，N=（P，T，F，λ）是一個標簽Petri網，對齊γ的代價值為κδ（γ） = ∑|γ|i = 1δ（γ（i） ），σ與N之間的一個最優(yōu)對齊γopt滿足：γopt=arg minγ∈Γ（N，σ，mi，mf）κ（γ）。其中，Γ（N，σ，mi，mf）表示σ與N之間所有對齊的集合。例如在圖1中，γ1、γ2是跡σL=〈A，D，B，F，G〉關于模型N1的兩個對齊。κδ（γ1）=1是所有對齊中最小的代價值，故γ1是一個最優(yōu)對齊，序列σM=〈A，D，C，B，F，G〉是γ1所映射的模型跡。

定義6［12］ Levenshtein編輯距離函數。設σ1、σ2∈A為兩條序列，i∈［1，|σ1|］，j∈［1，|σ2|］，定義如下三種編輯操作：a）（σ1（i），σ2（j））表示活動σ1（i）與σ2（i）之間的替換操作;b）（σ1（i），gt;gt;）表示活動σ1（i）的刪除;c）（gt;gt;，σ2（i））表示活動σ2（i）的插入。

Levenshtein編輯距離函數d（σ1，σ2）→N表示序列相互轉換的最小編輯操作次數。例如，d（〈a，b〉，〈c，d〉）=2，其編輯操作為兩個替換操作（a，c）和（b，d）。

定義7［14］ 編輯距離代價函數。假設σ1、σ2∈A為兩條活動序列，編輯距離代價函數Δ（σ1，σ2）→N的編輯操作不包含替換操作，僅指活動在跡中的插入與刪除操作。

在對齊中，每個非同步移動都等同于一次編輯操作，故Δ與δ返回同樣的代價值，例如Δ（〈a，b〉，〈c，d〉）=κδ（γ）=4。

定義8［14］ 擬合度公式。為了度量非對齊偏差，采用式（1）將代價值轉換為歸一化的擬合度值：

fitness（σL，PM）=1－κ（γoptPM（σ））|σL|+minσM∈φf（|σM|）（1）

其中：|σL|+minσM∈φf（|σM|）表示對日志跡中每個活動的刪除和最短模型跡中每個活動的插入次數之和。在本文中，設σM、σL分別表示模型跡和日志跡；ΣM表示模型行為子集，由不包含τ的模型跡組成；ΣL表示由日志跡組成的候選跡集合。

2 動機例子

本文僅從控制流的角度考慮事件日志的活動序列，并以合成的事件日志來具體說明當前方法可能存在的問題。日志L包含了由16 300個事件形成的2 553條跡，共12種跡變體，具體如表1所示。

利用Prom中的IM（inductive miner）算法發(fā)現過程模型（圖3），經過多次的測試表明：當非頻繁閾值設定為0.07～0.16時，挖出的模型含有適量的不可見變遷和較高的擬合度值，故將此模型用于一致性檢查。

現有方法中，模擬法［15］是基于重演Petri網的原理得到的模型跡，不需要做任何的對齊計算，但是構造的行為子集可能因為偏離日志行為而導致近似結果不準確；k-medoids法需要人為地設定k值，并且分類效果會受此影響；頻率法是從事件日志中選出高頻率的跡作為候選跡。對于頻率法而言，假設行為子集的數目為3，則需要從日志中選出三條高頻率的跡作為候選跡：ΣL={〈A，B，C，D，F，E，G，H〉640，〈A，B，C，D，E，F，G，H〉456，〈A，B，C，D，E，G，F，H〉432}。由于這些候選跡能夠完全重演于過程模型，所以它們還構成基于最優(yōu)對齊所映射的模型跡，即行為子集ΣM=ΣL。然而，基于頻率法構造出的候選跡集合存在如下問題：

a）所選的三條候選跡在事件日志中均是最長的，而其余短跡未被考慮。例如日志跡〈A，H〉，與過程模型對齊的移動成本值為1，但是與行為子集的最小編輯距離代價值為Φ（〈A，H〉，ΣM）=6，導致計算出的近似一致性度偏大。

b）候選跡之間的句法相似程度高，構造出的行為子集差異不明顯、代表性不夠好。例如跡〈A，B，C，D，F，E，G，H〉與〈A，B，C，D，E，F，G，H〉之間只存在活動E和F發(fā)生順序的區(qū)別，由圖3模型可知，變遷E、F為交叉序關系，實際上并沒有順序執(zhí)行先后的要求，以此構成的行為子集并不能較好地代表模型行為。

針對上述可能存在的問題，本文提出基于日志聚類構造行為子集的近似一致性方法，應用基于編輯距離的層次聚類技術預處理事件日志，一次性聚類所有的過程行為，然后以簇內高頻或者簇中心的方法選擇日志候選跡。表2比較了使用頻率法和本文方法構造出的行為子集（計算過程由5.1節(jié)給出），由于本文方法考慮了跡之間的句法差異，構造的集合中既包括長度為3的短跡（〈A，B，H〉），同時也包括長度為8的長跡，最后計算得出Φ（〈A，H〉，ΣM）=1，有效降低了這類短跡的距離代價值，從而提高近似一致性度的準確度。

3 基于日志聚類構造行為子集的近似一致性方法

本章首先介紹跡間距離的度量方法以及簇間連接準則，根據日志跡之間的句法差異來定義跡間距離，采用層次聚類技術［13］對事件日志進行預處理，將原始的復雜事件日志分成具有相似行為特征的若干子日志；再提出簇內高頻和簇中心兩種方法構造行為子集的算法思路，并給出近似一致性度的計算方法。

3.1 聚類的相關準則

模型的行為子集將要代表所有的模型行為與事件日志進行一致性檢查，通過減少對齊計算的時間開銷來提高一致性檢查的效率。日志聚類是一個預處理階段，用于自下而上（凝聚）的層次聚類方法將最相似的類別進行合并，結果返回一個聚類樹。通過切割聚類樹將事件日志劃分為不同行為特征的子日志，該方法避免了人為設定聚類數k值而影響分類效果的可能。同時，采取層次聚類的方法便于比較不同數目的行為子集對近似結果準確度的影響。

依據Levenshtein編輯距離函數來計算跡間距離是一種基于語義聚類的常用方法，即根據兩個序列之間的編輯操作來度量它們之間的距離。其中，非加權組平均（UPGMA）和雙重最小匹配（DMM）是兩種基本的簇間連接準則［13］，根據連接準則可以將跡間距離轉換為簇間距離，本文使用UPGMA連接準則。

定義9［13］ UPGMA連接準則。設L1、L2為兩個事件日志，σV1、σV2分別表示L1和L2中任意的跡變體，L1（σV1）、L2（σV2）分別表示σV1和σV2的基數（頻率），L1與L2的簇間距離函數dUPGMA：β（A）×β（A）→［0，1］，滿足

dUPGMA（L1，L2）=∑σV1∈L1∑σV2∈L2

L1（σV1）·L2（σV2）·dN（σV1，σV2）|L1|·|L2|（2）

其中：dN：A×A→［0，1］表示歸一化的Levenshtein編輯距離函數;dN（σV1，σV2）=d（σV1，σV2）max{|σV1|，|σV2|}。

例如，L1=［〈a，b〉，〈b，c〉］、L2=［〈a，b〉，〈b，c，d〉］，則dUPGMA（L1，L2）=dN1，3+dN1，4+dN2，3+dN2，4|L1|·|L2|=02+33+22+134=712。

定義10 編輯距離矩陣。假設σ1、σ2、…、σn∈A為日志L所有的日志跡，d是Levenshtein編輯距離函數，Μ（L）表示L的編輯距離矩陣。

Μ（L）=0d（σ1，σ2）…d（σ1，σn）

d（σ2，σ1）0…d（σ2，σn）

d（σn，σ1）d（σn，σ2）…0（3）

由于編輯距離代價函數滿足對稱性［15］，Δ（σ，σ′）=Δ（σ′，σ），故編輯距離矩陣Μ（L）也是對稱的。

定義11 簇中心。設L′是聚類后的一個子日志，n表示L′的跡變體數量，M（L′）是L′的編輯距離矩陣，跡σj=arg minσj∈L′∑i∈［1，n］d（σi，σj）代表子日志L′的簇中心。

3.2 基于聚類構造行為子集

采用基于UPGMA連接準則的層次聚類方法處理事件日志，根據跡之間的編輯距離劃分若干子日志，然后使用簇中心法和簇內高頻法從子日志中選出能夠代表典型行為的候選跡。這兩類方法的基本思想分為兩個部分：a）選擇候選跡，基于簇中心的方法是根據定義10計算每個子日志的編輯距離矩陣，再根據定義11計算簇中心，并將此納入候選跡集合中，簇內高頻法是在各子日志中選擇高頻率的跡作為候選跡;b）計算候選跡關于過程模型的最優(yōu)對齊，映射出模型跡構造行為子集。具體算法實現的步驟見算法1、2。

算法1 基于簇中心構造行為子集

輸入：事件日志L;Petri網模型PM。

輸出：行為子集ΣM。

1 ΣL←{}; //初始化候選跡集合

2 ΣM←{}; //初始化行為子集

3 cluster（L，k）

4 for each i∈［1，k］ do

5""" let Li denote each SubLog of L

6 end

7 for each Li∈L do //遍歷子日志，計算簇中心

8" create edit distance matrix Μ（Li） //計算最小編輯距離

9""" if arg minσ（i）L∈M（Li）∑σ（j）L∈M（Li）d（σ（i）L，σ（j）L） then

10""" let σ（i）L denote medoid trace of Li

11"" end

12"" ΣL←ΣL∪{σ（i）L} //計算候選跡集合

13 end

14 for each σ（i）L∈ΣL then

15" γopti←arg minγ∈Γ（PM，σ（i）L，mi，mf）κ（γ） //計算最優(yōu)對齊

16" σ（i）M←π2（γopti）↓A" //映射模型跡

17" ΣM←ΣM∪{σ（i）M} //構造行為子集

18 end

19 return ΣM

在算法1中，行3～6利用基于UPGMA的層次聚類方法將事件日志劃分為k個類別；行9遍歷各子日志，調用Python庫中的Levenshtein方法計算各子日志的編輯距離矩陣Μ（Li）；行7～11根據Μ（Li）計算出各子日志的簇中心，并將其作為候選跡保存到集合ΣL中；最后，行15利用Prom工具計算候選跡關于過程模型的最優(yōu)對齊；行16、17通過π1（γ）↓A映射得到模型跡σ（i）M，以此構造模型的行為子集。

算法2 基于簇內高頻構造行為子集

輸入：事件日志L;Petri網模型PM。

輸出：行為子集ΣM。

1 ΣL←{};

2 ΣM←{};

3 cluster（L，k）

4 for each i∈［1，k］ do

5" let Li denote each SubLog of L

6 end

7 for each Li∈L do //遍歷子日志，選擇高頻跡

8"" for each σ（j）L∈Li do

9""" let f（σ（j）L） denote the frequency of σ（j）L

10""" σ（i）L←arg maxσ（j）L∈Lif（σ（j）L）

11""" ΣL←ΣL∪{σ（i）L} //構造候選跡集合

12"" end

13 end

14 for each σ（i）L∈ΣL do

15" γopti←arg minγ∈Γ（PM，σ（i）L，mi，mf）κ（γ） //計算最優(yōu)對齊

16" σ（i）M←π2（γopti）↓A //映射模型跡

17" ΣM←ΣM∪{σ（i）M} //構造行為子集

18 end

19 return ΣM

在算法2中，依然采用基于UPGMA的層次聚類方法劃分事件日志，行7將子日志導入Prom中，再對其進行遍歷，行8～12選擇各子日志中的頻率最高的跡作為候選跡，形成候選跡集合ΣL，通過計算候選跡與模型的最優(yōu)對齊來構造模型的行為子集。

3.3 近似一致性度的邊界

通過應用編輯距離代價函數Δ代替標準代價函數δ來計算事件日志關于行為子集（ΣMφf（PM））的近似一致性度，該方法可以減少對齊過程中的時間開銷。由式（1）可知，對齊代價的上界值/下界值同于擬合度的下界值/上界值，即一致性度的邊界值，如下給出關于它們的定理。

定理1［14］ 對齊代價的上界值。設σL∈A為一條日志跡，σM∈φf（PM）為過程模型PM中的一條觸發(fā)序列，則有κ（γoptPM（σL））≤Δ（σL，σM）。

證明 文獻［14］已經予以證明。

定理2 對齊代價的下界值。假設minσ′M∈φf|σ′M|=s、maxσ″M∈φf|σ″M|=x分別表示模型跡中最短、最長路徑的長度（循環(huán)體結構除外）。對于任意的日志跡σL∈L，當|σL|lt;s時，則s－|σL|為對齊代價的下界；當|σ′L|≥x時，則|σL|－x為對齊代價的下界；當s≤|σL|≤x時，對齊代價的下界為0。

證明 設lt;gt;為一個空序列，則κδ（γoptPM（lt;gt;））=s為最短模型跡的長度，max κδ（γPM（lt;gt;））=x為最長模型跡的長度。由于使用編輯距離代價函數Δ代替標準代價函數δ，故對齊代價是指由序列σL轉換至σM的最小編輯操作次數。當|σL|lt;s時，則在σL中至少需要s－|σL|次插入操作；當|σL|≥x時，則在σL中至少需要|σL|－x次刪除操作；當|σL|介于s與x之間時，則最少需要0次插入操作。證畢。

算法3、4分別給出計算擬合度的下界值（L_fitness）和上界值（U_fitness）的基本步驟。

算法3 擬合度的下界值算法

輸入：事件日志L;行為子集ΣM。

輸出：擬合度的下界值。

1 for each σL∈L do

2 ""Φ（σL，ΣM） //計算最小編輯距離的代價值

3"" L_fitness（σL，PM）←1－Φ（σL，ΣM）|σL|+minσM∈φf（|σM|）

4 end

5 return L_fitness（σL，PM）

在算法3中，以事件日志L和行為子集ΣM作為輸入，行1～4遍歷整個事件日志，計算每個日志跡與行為子集的最小編輯距離的代價值，將其代入式（1）求出擬合度的下界值。其中，Φ（σ，Σ）=minσi∈Σ（σ，σi）表示序列σ與集合Σ的最小編輯距離代價值。

算法4 擬合度的上界值算法

輸入：事件日志L;行為子集ΣM。

輸出：擬合度的上界值。

1 let lt;gt; denote a empty sequence

2 σ′M←arg minσ′M∈φfκ（γoptPM（lt;gt;）） //σ′M為最短路徑

3 σ″M←arg maxσ″M∈φfκ（γPM（lt;gt;）） //σ″M為最長路徑

4 for each σL∈L do

5"" if |σL|lt;|σ′M| then //小于最短路徑長度時

6""" U_fitness（σL，PM）←1－|σ′M|－|σL||σL|+minσM∈φf（|σM|）

7"" end

8"" else if |σL|gt;|σ″M| then //大于最長路徑長度時

9""" U_fitness（σL，PM）←1－|σL|-|σ″M||σL|+minσM∈φf（|σM|）

10"" end

11"" else then

12""" U_fitness（σL，PM）←1

13" end

14 end

15 return U_fitness（σL，PM）

在算法4中，行1～3通過計算空序列與過程模型之間的對齊來計算模型的最短和最長路徑長度，最優(yōu)對齊對應的序列為最短路徑，代價值最高的對齊對應的序列為最長路徑。在圖2模型中，求得|σ′M|=3、|σ″M|=8，通過比較每個跡變體與最短路徑和最長路徑之間的長度關系，利用行4～14的三個if判斷語句計算出日志跡重演過程模型時的最小編輯操作數目，再代入式（1）求出擬合度的上界值。行5～7表示如果跡的長度小于最短路徑的長度時，則它至少需要|σ′M|-|σ|次插入操作才能將其轉換為合法的模型跡；同理，行8～10表示如果跡的長度大于最長路徑的長度時，則它至少需要|σ|-|σ″M|次刪除操作才能將其轉換為合法的模型跡；行11～13表示如果跡σ的長度介于|σ′M|和|σ″M|兩者之間時，最理想的情況即該跡能夠完全重演模型，需要0次編輯操作，即擬合度為1。

算法3、4是針對每個跡變體計算邊界擬合度值的方法。對于計算完整事件日志的擬合度，需要根據頻率將所有跡變體的邊界擬合度進行加權平均，如式（4）所示。

fitness（L，PM）=∑σi∈Lfitness（σi，PM）·f（σi）∑σi∈Lf（σi）（4）

4 實驗評估

本章通過仿真實驗，從準確度和時間效率兩個方面評估本" 文方法的可行性，并分析不同數目的行為子集對它們的影響。

4.1 聚類分析

PM4py［19］是一個開源且能夠支持過程挖掘算法的Python庫，其中pm4py.algo.clustering［20］包文件中提供了許多關于日志聚類的算法。本文通過調用現有方法，對表1事件數據進行聚類分析。采用3.1節(jié)所介紹的跡間距離的度量方法以及簇間連接準則，圖4為結果返回的聚類樹，其橫坐標表示跡變體ID，縱坐標表示距離。

聚類樹依據編輯距離將句法相似的日志跡歸為一類，表3是水平切割聚類樹后得到的不同子日志和對應的子模型。

假設行為子集ΣM的數目取3時，下面針對構造行為子集的不同方法進行比較：

a）頻率法。即從整個事件日志中選取三條高頻率的跡作為候選跡。由圖5可知，日志跡〈A，B，C，D，F，E，G，H〉、〈A，B，C，D，E，F，G，H〉和〈A，B，C，D，E，G，F，H〉的頻數分別占整個事件日志的25.07%、17.86%和16.92%，故將它們選做候選跡。

經對齊計算，各候選跡均能完全重演模型PM，故得到行為子集ΣM={〈A，B，C，D，F，E，G，H〉，〈A，B，C，D，E，F，G，H〉，〈A，B，C，D，E，G，F，H〉}。

b）簇內高頻法。事件日志經聚類處理后，取簇數n=3，從表3中選出各子日志中頻率最高的跡作為候選跡，即ΣL={〈A，H〉，〈A，B，C，D，F，E，G，H〉，〈A，F，B，C〉}，并與過程模型進行最優(yōu)對齊計算：

從最優(yōu)對齊中映射出模型跡π1（γ）↓A，并構成行為子集ΣM={〈A，B，H〉，〈A，B，C，D，F，E，G，H〉，〈A，B，C，H〉}。

c）簇中心法。設ci表示第i種跡變體，取簇數n=3，聚類后的三個子日志分別為L1={c5}、L2={c0，c1，c2，c3，c4，c6，c7，c8}和L3={c9，c10，c11}。通過調用Python庫中的Levenshtein方法計算子日志的編輯距離矩陣M（L2）、M（L3）（圖6），結合定義9得出：L1為單序列日志；在M（L2）中，∑ci∈M（L2）d（ci，c4）=19為最小的編輯距離之和，故c4為L2的簇中心；同理在M（L3）中，c11為L3的簇中心，其中∑ci∈M（L3）d（ci，c11）=6。

計算出候選跡集合ΣL={〈A，H〉，〈A，B，F，E，G，H〉，〈B，F，G〉}，并與過程模型進行最優(yōu)對齊計算：

其中：序列〈A，H〉的最優(yōu)對齊為γopt1，得到行為子集ΣM={〈A，B，H〉，〈A，B，C，D，H〉，〈A，B，E，F，G，H〉}。

上述三種方法中，由于頻率法沒有考慮跡之間的行為差異，篩選出的三條候選跡之間具有較高的相似性，并且行為子集中缺少短跡行為。當利用聚類技術處理事件日志后，簇內高頻法和簇中心法均能得到同時包含長短跡的行為子集，使其更加全面地代表過程模型，能夠有效降低部分日志跡與行為子集之間的編輯距離代價值，利于近似一致性度的計算。

4.2 近似一致性度的邊界值計算

對于擬合度的上界值，根據算法4計算出過程模型PM中最短模型跡和最長模型跡的長度分別為3和8。然而在給定的事件日志L中，僅活動序列〈A，H〉的長度小于3，計算出其擬合度的上界值U_fitness（〈A，H〉，PM）=0.8；其余日志跡的長度均在3～8，具有完全重演過程模型的可能，故它們的擬合度上界值為1。最后，通過加權平均算出事件日志L的擬合度上界值為0.98。

對于擬合度的下界值，首先通過切割聚類樹將事件日志劃分不同的類別，針對每個子日志中分別使用頻率法和簇中心法得出候選跡，再計算候選跡與過程模型間的最優(yōu)對齊，以得到行為子集ΣM。根據算法3，計算每個跡變體與行為子集之間的最小編輯距離代價值Φ（σL，ΣM）及擬合度的下界值。當計算完每個跡變體的擬合度后進行加權平均，以得到整個事件日志的擬合度。隨著行為子集數目的改變，不同方法計算出擬合度下界值的情況如表4所示。

4.3 效果評估

本節(jié)從準確度和時間效率兩方面對行為子集數目變化時的性能進行評估。使用擬合度的上界值和下界值間的差值來表示約束寬度，以評估近似一致性的準確度，即約束寬度=U_fitness（L，PM）－L_fitness（L，PM），更小的約束寬度代表更加準確的近似邊界。圖7中的約束寬度對應于主（左）坐標軸，L_fitness對應于次（右）坐標軸。圖中顯示隨著行為子集數目的增加，三種方法計算出的擬和度下界值均在增加，約束寬度均在減少，表明越大的行為子集計算得到一致性度的準確度越高。通過應用了聚類技術的簇內高頻法和簇中心法與頻率法相比，近似一致性度的準確度得以提升，主要原因是聚類后的子日志構造出的行為子集的行為差異更為顯著，且同時考慮到長跡和短跡的情況。由于完整日志的擬合度是基于候選跡頻率的加權平均（式（4）），所以簇內高頻法比簇中心法能夠更好地提升近似結果的準確度。

如圖8所示，在時間效率方面，采用基于對齊的傳統一致性方法檢測出事件日志L和模型PM的對齊時間為113 ms。由于使用行為子集的方法只需要在構造行為子集的過程中計算對齊，減少了對齊計算的次數，所以在時間效率方面表現更好。

隨著行為子集數目的增加，對齊計算的次數也會增加，則需要消耗更多的時間，圖9表明本文方法的整體用時明顯低于基于對齊的傳統方法。簇中心法和簇內高頻法需要對事件日志進行聚類的預處理工作，然而頻率法并不需要對事件日志作預處理，故整體用時會更少。

綜上表明，基于行為子集的近似一致性方法節(jié)省了對齊的時間開銷，因此提升了一致性檢查的效率，隨著行為子集數目的增加，近似的準確度越高，同時也會增加處理的時間。因此，近似一致性方法需要在準確度和時間效率方面進行權衡考慮，選擇出一個最合適的行為子集數目。應用日志聚類技術的簇內高頻法和簇中心法能夠構造出具有顯著差異的行為子集，使其更加全面地代表完整的模型行為，從而提升近似一致性的準確度。

5 結束語

基于行為子集的方法能夠較快地檢查大型事件日志和過程模型間的一致性情況，它利用編輯距離的代價函數來代替移動的代價函數［21］，提升了傳統基于對齊的一致性檢查效率。當前構造行為子集的方法對日志選跡間的行為差異要求不高，因此近似一致性度的準確度還有很大的提升空間。本文首先通過調用PM4py中的層次聚類方法預處理事件日志，根據跡間的編輯距離對日志進行聚類，并利用Prom工具對各子日志事件數據進行可視化分析。進一步，運用本文提出的簇內高頻和簇中心兩種算法從各子日志中提取候選跡，再利用最優(yōu)對齊技術構造出模型的行為子集。最后，通過仿真實驗的結果表明，應用日志聚類技術構造出的行為子集能夠更加全面地代表模型行為，可以得到更加準確的近似結果。不過本文僅從控制流的角度處理事件日志，沒有考慮到數據的屬性特征，今后還可以結合數據流方面作進一步的改進。此外，近似一致性的方法需要在準確度和時間效率上作權衡，設計增量工具方便用戶自行調整行為子集的數目也是未來的研究方向之一。

參考文獻：

[1]Van Der Aalst W M P. Process mining： discovery， conformance and enhancement of business processes ［M］.Berlin：Springer，2011：1018-1019.

［2]Weidlich M， Polyvyanyy A， Desai N， et al. Process compliance ana-lysis based on behavioural profiles［J］.Information Systems，2011，36（7）：1009-1025.

［3]Pichon F， Destercke S， Burger T. A consistency-specificity trade-off to select source behavior in information fusion［J］.IEEE Trans on Cybernetics，2015，45（4）：598-609.

［4]Mitsyuk A A， Lomazova I A， Shugurov I S， et al. Process model repair by detecting unfitting fragments［C］//Proc of the 6th International Conference on Analysis of Images， Social Networks and Texts.2017：301-313.

［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]田銀花，杜玉越，韓咚，等.基于Petri網的事件日志與過程模型對齊方法［J］.計算機集成制造系統，2019，25（4）：810-813.（Tian Yinhua， Du Yuyue， Han Dong， et al. Aligning event logs and process models based on Petri nets［J］.Computer Integrated Manufacturing Systems，2019，25（4）：810-813.）

［7]Munoz-Gama J， Carmona J， Van Der Aalst W M P. Single-entry single-exit decomposed conformance checking［J］.Information Systems，2014（46）：102-122.

［8]Schuster D， Zelst S V， Van Der Aalst W M P. Alignment approximation for process trees［M］//Leemans S， Leopold H. Process Mining Workshop.Cham：Springer，2020：247-259.

［9]Nolle T， Seeliger A， Thoma N， et al. DeepAlign： alignment-based process anomaly correction using recurrent neural networks［EB/OL］.（2019-11-29）.https：//arxiv.org/abs/1911.13229.

［10]楊皓然，方賢文.基于概率和時間因素的Petri網業(yè)務流程一致性分析［J］.計算機科學，2020，47（5）：59-63.（Yang Haoran， Fang Xianwen. Business process consistency analysis of Petri net based on probability and time factor［J］.Computer Science，2020，47（5）：59-63.）

［11]方賢文，趙芳，方歡，等.基于Petri網behaviorinclusion的業(yè)務流程變化域融合分析［J］.計算機學報，2018，41（3）：696-706.（Fang Xianwen， Zhao Fang， Fang Huan， et al. The fusion analysis method about the change region of the business process model based on beha-vior inclusion in Petri net［J］.Chinese Journal of Computers，2018，41（3）：696-706.）

［12]Bauer M， Van Der Aa H， Weidlich M. Estimating process confor-mance by trace sampling and result approximation［C］//Proc of International Conference on Business Process Management.Cham：Sprin-ger，2019：179-197.

［13]Cao Yukun. Attribute-driven hierarchical clustering of event data in process mining［EB/OL］.（2020-11-24）.https：//www.pads.rwth-aachen.de/cms/PADS/Studium/Abgeschlossene-Abschlussarbeiten/～giqos/Attribute-Driven-Hierarchical-Clustering/lidx/1/.

［14]Fanisani 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.

［15]Sani M F， Kabierski M， Van Zelst S J， et al. Model independent error bound estimation for conformance checking approximation ［EB/OL］.（2021-03-23）.https：//arxiv.org/abs/2103.13315.

［16]吳哲輝.Petri網導論［M］.北京：機械工業(yè)出版社，2006：11-36.（Wu Zhehui. An introduction to Petri nets［M］.Beijing：China Machine Press，2006：11-36.）

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

［18]Leoni M D， Marrella A. Aligning real process executions and prescriptive process models through automated planning［J］.Expert Systems with Applications，2017，82（1）：162-174.

［19]Berti A， Van Zelst S J， Van Der Aalst W M P. Process mining for Python （PM4Py）：bridging the gap between process-and data science ［EB/OL］.（2019-05-15）.https：//arxiv.org/abs/1905.06169.

［20]Chatain T， Carmona J， Dongen B V. Alignment-based trace clustering［C］//Proc of International Conference on Conceptual Modeling.Berlin：Springer，2017：295-308.

［21]Cabanillas C， Resinas M， Ruiz-Cortés A. A mashup-based framework for business process compliance checking［J/OL］.IEEE Trans on Services Computing.（2020-06-10）.https：//doi.org/10.1109/TSC.2020.3001292.