王 琦，聞立杰，鄧雅方，錢 忱，王建民

(清華大學(xué) 軟件學(xué)院，北京 100084)

0 引言

隨著企業(yè)信息化的推進(jìn)，海量的日志數(shù)據(jù)源源不斷地從企業(yè)信息系統(tǒng)中產(chǎn)生，促進(jìn)了信息挖掘領(lǐng)域的發(fā)展。與此同時，日志的完備性一直是備受關(guān)注的問題，由于系統(tǒng)原因或者人為原因，常常會導(dǎo)致系統(tǒng)日志中的時間信息錯誤，使得日志數(shù)據(jù)無法正確表達(dá)業(yè)務(wù)活動之間的次序關(guān)系，增加了信息挖掘的難度。此類可以表達(dá)活動之間相對次序關(guān)系的日志被稱為軌跡日志。針對軌跡日志的亂序問題，業(yè)內(nèi)提出了許多修復(fù)的手段用來提升日志質(zhì)量。

目前，基于模型約束的軌跡對齊是主要的修復(fù)方式，LEONI等[1]最早提出利用流程模型和日志軌跡對齊修復(fù)日志的方法，可以對日志中存在的多種問題進(jìn)行修復(fù),然而此類修復(fù)方法的時間效率表現(xiàn)較差；為了提升對齊算法性能，業(yè)界學(xué)者提出一種分治的策略，將大規(guī)模流程模型分解為易于分析的子流程模型集，大大提升了算法性能[2]；在分治的基礎(chǔ)上，SONG等[3]利用剪枝規(guī)則，進(jìn)一步提升了對齊修復(fù)方法的性能。

此外，基于啟發(fā)式的軌跡修復(fù)方式Effa[4]，雖然獲得了良好的性能表現(xiàn)，但是修復(fù)準(zhǔn)確率有待提高。針對軌跡修復(fù)問題，ROGGE-SOLTI[5]等提出結(jié)合隨機(jī)Petri網(wǎng)、對齊和貝葉斯網(wǎng)絡(luò)來實現(xiàn)軌跡修復(fù)的方法。有學(xué)者提出了修復(fù)軌跡缺失事件的分支定界修復(fù)方法[6]，還有基于時間約束網(wǎng)的亂序軌跡修復(fù)方法等[7]。

針對上述問題，本文圍繞軌跡亂序問題展開研究，提出亂序軌跡的高效修復(fù)方法，主要貢獻(xiàn)如下：

(1)首先對軌跡亂序問題的最優(yōu)修復(fù)進(jìn)行了形式化定義，并提出了基于移動距離的修復(fù)代價函數(shù)。

(2)提出一種基于A*算法的亂序軌跡修復(fù)方法，通過將軌跡與流程模型進(jìn)行對齊，來尋找亂序軌跡的最優(yōu)修復(fù)。

(3)提出一種基于精煉流程結(jié)構(gòu)樹的亂序軌跡修復(fù)方法，通過模型分解技術(shù)，將原始模型分解為多種不同類型的子結(jié)構(gòu)，然后通過事件重放算法對模型子結(jié)構(gòu)進(jìn)行修復(fù)，修復(fù)效率獲得了明顯提升。

(4)設(shè)計了實驗對本文提出的兩種修復(fù)方法進(jìn)行測試分析，并與業(yè)內(nèi)主流修復(fù)方法進(jìn)行了對比實驗。

1 預(yù)備知識和問題定義

1.1 預(yù)備知識

本文以亂序軌跡日志的修復(fù)為主要目標(biāo)，本節(jié)將對研究內(nèi)容所涉及的預(yù)備知識進(jìn)行說明，主要包含建模語言的選擇和流程模型的定義。

定義1軌跡。軌跡是多個活動的非空有序集合，實際發(fā)生的活動在軌跡中稱為事件。

本文使用Petri網(wǎng)作為主要建模語言[8]，Petri網(wǎng)是由Carl Adam Petri設(shè)計發(fā)明，用來描述非同步的因果和非因果行為的表達(dá)。

定義2Petri網(wǎng)。一個Petri網(wǎng)N是一個三元組(P,T,F)，其中：P為有限的庫所集合；T為有限的變遷集合，且P∪T≠?∧P∩T=?；F?(P×T)∪(T×P)，為有向邊集合(即流關(guān)系)；對于任意節(jié)點(diǎn)x∈P∪T,·x={y|(y,x)∈F}，x·={y|(x,y)∈F}。

定義3流程模型。一個Petri網(wǎng)N=(P,T,F)是一個工作流網(wǎng)，當(dāng)且僅當(dāng)下列條件同時成立：①有且僅有一個輸入庫所i∈P(源庫所)滿足·i=?；②有且僅有一個輸出庫所o∈P(匯庫所)滿足O·=?；③任意節(jié)點(diǎn)x∈P∪T都在源庫所到匯庫所的某一條路徑上。

定義4前序集合和后序集合。對于一個流程模型N=(P,T,F)，σ為對應(yīng)的觸發(fā)軌跡，任意事件e∈σ，*e表示事件e的前序事件集合，包含從軌跡的開始事件到當(dāng)前事件e之間的所有事件。e*表示事件e的后序事件集合，包含從當(dāng)前事件e到軌跡最后一個事件之間所有的事件。

1.2 問題定義

軌跡的亂序問題是指軌跡中事件的相對順序存在錯位。在亂序軌跡修復(fù)過程中充滿了不確定性和多樣性，同一亂序軌跡存在多種修復(fù)方式和不同修復(fù)結(jié)果，為了量化軌跡修復(fù)過程中事件移動的代價，并提供一種對修復(fù)結(jié)果評價地方式，提出了基于位置的移動距離代價函數(shù)。

定義5位置映射函數(shù)。給定一個事件日志軌跡σ，σ可以被等價地轉(zhuǎn)換為位置映射函數(shù)πσ，其中πσ關(guān)聯(lián)事件和位置信息，即?e∈σ，πσ(e)=k，其中k為事件e的位置信息。

軌跡中事件的位置分為兩種類型：①在未修復(fù)的原始軌跡中，一個事件的位置信息對應(yīng)該事件在軌跡中的索引下標(biāo)，從1開始逐一遞增至軌跡長度，即1～|σ|；②間隙位置，間隙位置k(x)就表示位于初始位置k和k+1之間的第x個事件。對于一條待修復(fù)軌跡σ=，如圖1所示為軌跡事件的初始位置信息，若將T2前移到T3之前，則事件T2的新位置為1(1)，表示介于位置1和2區(qū)間內(nèi)的第一個事件。

事件的移動將伴隨著位置的修改，將軌跡修復(fù)前后事件位置的變化定義為軌跡的修復(fù)代價。

定義6移動距離(MD)。原始待修復(fù)軌跡σ的位置映射函數(shù)為πσ，修復(fù)軌跡σ′對應(yīng)位置映射函數(shù)為πσ′，將修復(fù)的代價定義如下所示:

MD(σ,σ′)=∑t∈σ|πσ(t)-πσ′(t)|。

本文使用移動距離衡量原始待修復(fù)與修復(fù)軌跡之間的差異大小，最優(yōu)修復(fù)軌跡定義如下。

定義7最優(yōu)修復(fù)。對于過程模型N=(P,T,F) 的一個日志軌跡σ，最小修復(fù)軌跡σ′需要滿足如下條件：

(1)σ′|=N；

(2)MD(σ,σ′)最小，當(dāng)且僅當(dāng)不存在修復(fù)方案σ″，使得MD(σ,σ″)

2 基于A* 的亂序軌跡修復(fù)方法

A*(A Star)算法最早由Hart等[9]提出，被認(rèn)為是最著名的人工智能算法之一。過程挖掘領(lǐng)域常用A*算法在搜索空間內(nèi)尋找最優(yōu)解，A*算法是基于啟發(fā)式的路徑搜索算法，可以在靜態(tài)網(wǎng)絡(luò)中搜尋最小路徑。目前該算法已經(jīng)用于解決各個領(lǐng)域的問題，例如DNA序列的比對、智能路徑規(guī)劃以及物聯(lián)網(wǎng)智能流量等[10-13]。

本文提出的基于A*算法的亂序軌跡修復(fù)方法(Minimum Moving Distance repair using A*,MMDA)由軌跡事件優(yōu)先級分析和解的搜索空間遍歷兩部分組成，修復(fù)方法的流程描述如圖2所示。

2.1 事件優(yōu)先級分析

MMDA方法在修復(fù)過程中，通過調(diào)整軌跡事件的相對位置，獲得無錯位事件的軌跡。為識別和修復(fù)軌跡中的錯位事件，需要分析模型中的約束信息，判斷軌跡中兩個事件之間的相對順序是否發(fā)生錯位。

流程模型中的約束關(guān)系決定了變遷節(jié)點(diǎn)之間的觸發(fā)順序，本文將變遷節(jié)點(diǎn)的觸發(fā)先后次序關(guān)系定義為變遷優(yōu)先級，定義如下：

定義8變遷優(yōu)先級。給定一個無環(huán)流程模型N=(P,T,F)，模型的開始節(jié)點(diǎn)為b_start，結(jié)束節(jié)點(diǎn)為b_end，?t1,t2∈T，m(t1)和m(t2)分別表示變遷t1和t2在流程模型N中的變遷優(yōu)先級，F(xiàn)(t1,t2) 表示從t1開始到節(jié)點(diǎn)t2之間所有路徑包含的變遷集合，變遷優(yōu)先級遵循如下規(guī)則:

(1)m(t1)>m(t2)，如果滿足t2∈F(t1, b_end)，或者t1∈F(b_start,t2)；

(2)m(t1)

如圖4所示，如果流程模型內(nèi)部包含循環(huán)結(jié)構(gòu)，將存在若干條從后向前的反向邊，在分析變遷優(yōu)先級時，需要將循環(huán)結(jié)構(gòu)進(jìn)行展開操作，總是將L2中變遷優(yōu)先級小于L1中的變遷優(yōu)先級，L3結(jié)構(gòu)中變遷優(yōu)先級小于L2中的變遷優(yōu)先級，即?t0∈L0，?t1∈L1，?t2∈L2，?t3∈L3，滿足m(t0)>m(t1)>m(t2)>m(t3)。

軌跡中每個事件都是由對應(yīng)的模型變遷節(jié)點(diǎn)觸發(fā)生成，通過分析模型變遷節(jié)點(diǎn)的觸發(fā)次序，進(jìn)而可以推斷軌跡中事件的生成順序，首先給出事件優(yōu)先級的定義。

定義9事件優(yōu)先級。給定一個日志軌跡σ，?e∈σ，d(e)表示事件e的事件優(yōu)先級。?e1,e2∈σ，事件優(yōu)先級表示事件的觸發(fā)生成次序先后關(guān)系：

(1)若d(e1)>d(e2)，表示事件e1在模型中的觸發(fā)生成次序早于事件e2；

(2)若d(e1)

(3)若d(e1)=d(e2)，表示在模型中對事件e1和e2之間的觸發(fā)次序無要求。

通過將軌跡事件與模型變遷進(jìn)行一一映射，獲得事件優(yōu)先級信息。對于僅包含串行、互斥分支和并行結(jié)構(gòu)的流程模型，使用同名映射方式，t=φ(e)表示與事件e同標(biāo)簽名的變遷節(jié)點(diǎn)t。

規(guī)則1普通事件優(yōu)先級比較規(guī)則 給定一個無環(huán)流程模型N=(P,T,F)和對應(yīng)的日志軌跡σ，?e1,e2∈σ，則事件優(yōu)先級的比較遵循以下規(guī)則:

(1)若m(φ(e1))>m(φ(e2))，則事件優(yōu)先級滿足d(e1)>d(e2)；

(2)若m(φ(e1))

如圖3所示的流程模型，對于一個待修復(fù)軌跡σ=，按照模型和上述定義，可以推斷出d(T1)>d(T2)，代表事件T1的生成次序應(yīng)早于事件T2，但是在軌跡σ中，事件T2卻出現(xiàn)在事件T1之前，因此可以判斷事件T1和T2之間存在錯位問題。

如果模型中包含循環(huán)結(jié)構(gòu)，軌跡中會包含多個同標(biāo)簽的事件，需要按照循環(huán)次數(shù)進(jìn)行切分，從而區(qū)分多個同標(biāo)簽事件。如圖5所示包含循環(huán)結(jié)構(gòu)的流程模型，給定一個待修復(fù)軌跡σ，按照事件在軌跡中的出現(xiàn)順序，將循環(huán)事件切分為S1和S2兩部分，屬于循環(huán)觸發(fā)S1中的事件優(yōu)先級一定大于屬于S2中的事件，即?e1∈S1,e2∈S2，滿足d(e1)>d(e2)。

給定一個日志軌跡σ，如果修復(fù)后的軌跡σ′，滿足：?0

2.2 搜索空間的生成與遍歷

為了使用A*算法尋找最優(yōu)修復(fù)，需要定義一個合適的搜索空間，搜索空間中的節(jié)點(diǎn)代表修復(fù)的過程，原軌跡作為初始節(jié)點(diǎn)出現(xiàn)在搜索空間中，空間中相連的兩個修復(fù)節(jié)點(diǎn)代表修復(fù)過程的連續(xù)性，每一個部分修復(fù)軌跡經(jīng)過一次修復(fù)，都可能生成多個新的軌跡，將軌跡的修復(fù)操作定義如下：

定義10錯位事件修復(fù)函數(shù)。給定一個流程模型N=(P,T,F)，對于一條部分修復(fù)軌跡σ，?e1∈σ，錯位事件修復(fù)函數(shù)ad(e1,σ)表示以事件e1為基準(zhǔn)，調(diào)整軌跡中的錯位事件，生成新的軌跡，調(diào)整規(guī)則如下:

(1)?e2∈*e1，且d(e2)

通過連續(xù)的調(diào)用錯位事件修復(fù)函數(shù)，可以漸進(jìn)性的對待修復(fù)軌跡進(jìn)行修復(fù)；同時，以不同的事件作為參數(shù)調(diào)用修復(fù)函數(shù)，可以生成不同的新軌跡，對應(yīng)不同的修復(fù)分支。如圖3所示的流程模型，給定對應(yīng)的一個待修復(fù)軌跡σ=，其生成的局部修復(fù)分支如圖6所示。

如果修復(fù)后的新軌跡是一條完全修復(fù)軌跡，則暫存當(dāng)前修復(fù)軌跡和對應(yīng)的修復(fù)代價。因為修復(fù)的多樣性，在生成修復(fù)分支的過程中，將獲得多個不同的完全修復(fù)軌跡和對應(yīng)的修復(fù)代價，根據(jù)最優(yōu)修復(fù)的定義，選取修復(fù)代價最小的一條完全修復(fù)結(jié)果作為最優(yōu)修復(fù)。

除此之外，待修復(fù)軌跡修復(fù)遍歷的過程中，會出現(xiàn)許多等價的部分修復(fù)軌跡，如圖6中所示，通過ad(T2,σ)和ad(T3,σ)修復(fù)后得到的新軌跡是等價的，即軌跡中對應(yīng)事件的順序完全一致，為了加速遍歷算法，對于等價的軌跡，只保留修復(fù)代價(移動距離)較小的軌跡即可。

2.3 代價預(yù)估啟發(fā)式

代價預(yù)估啟發(fā)式是A*算法的重要組成部分，A*算法會維護(hù)一個優(yōu)先級隊列，在修復(fù)過程中，將所有部分修復(fù)軌跡加入到隊列中，其中預(yù)估修復(fù)代價越小的部分修復(fù)軌跡，在隊列中優(yōu)先級越高，越容易被優(yōu)先修復(fù)。理想情況下，通過優(yōu)先級隊列和代價預(yù)估啟發(fā)式，A*算法能夠優(yōu)先獲得修復(fù)代價最小的修復(fù)結(jié)果，并且將后續(xù)預(yù)估代價較大的修復(fù)分支進(jìn)行修剪。

對于一個待修復(fù)軌跡σ，假設(shè)軌跡的修復(fù)預(yù)估代價為LHσ，實際修復(fù)代價為MDσ，為了獲得預(yù)估修復(fù)代價的計算方式，首先可以對流程模型中的兩個相鄰變遷節(jié)點(diǎn)進(jìn)行分析。給定一個流程模型N=(P,T,F)，模型N的任意兩個相鄰變遷節(jié)點(diǎn)x和y，滿足y∈(x·)·，將存在以下幾種情況：

情況1?i

情況2?i

(1)將σ(i)移動到σ(j)之后，如圖7b所示，y′為y的新位置，事件修復(fù)的移動代價為Costij=j-i；

(2)將σ(j)移動到σ(i)之前，如圖7c所示，x′為x的新位置，事件修復(fù)的移動代價為Costij=j-i；

(3)σ(i)和σ(j)同時移動位置進(jìn)行修復(fù)，如圖7d所示，事件x和y同時向中間的某個事件位置k進(jìn)行移動，事件修復(fù)的移動代價為Costij=(j-k) + (k-i)=j-i；如圖7e所示，事件同時向y左側(cè)的某個事件位置k進(jìn)行移動，則事件修復(fù)的移動代價Costij≥j-i；同理如7f所示，也滿足Costij≥j-i；

按照上述的分類討論得知，不管如何修正事件錯位問題，都有Costij≥j-i。

情況3不存在i

由上述討論可知，對于模型中的兩個相鄰變遷x和y，只要其對應(yīng)的事件相對順序錯誤，其修復(fù)代價一定大于其位置差值的絕對值。同時，為了防止最終預(yù)估的代價超過實際修復(fù)代價，同一個模型變遷及其對應(yīng)的軌跡事件在代價預(yù)估的過程中，應(yīng)該僅被使用一次，因此提出后繼二元集的定義。

定義11后繼二元集。給定一個流程模型N=(P,T,F)，后繼二元集(Subsequent Binary Set，SBS)是一個二元組的集合，其中?(x,y)∈SBS滿足如下條件:

(1)x∈T，y∈T，并且y∈(x·)·;

(2)不存在其他的一個后繼二元組(m,n)，使得x或y包含在(m,n)中。

對于部分修復(fù)軌跡σ，將其完全被修復(fù)所需要的代價稱為剩余修復(fù)代價，基于上述討論和后繼二元集，下面給出剩余修復(fù)代價的預(yù)估方式。

定義12剩余修復(fù)代價。設(shè)函數(shù)k(a,b)表示修復(fù)事件a和b所需要的預(yù)估代價，在此給出剩余修復(fù)代價的預(yù)估函數(shù)

FCσ=∑?(a,b)∈SBSk(a,b)=

FCσ是對修復(fù)代價的一種預(yù)估值，始終滿足0≤Fcσ≤MDσ,即預(yù)估剩余修復(fù)代價始終小于實際修復(fù)代價。對于修復(fù)過程中的一條部分修復(fù)的軌跡σ′，將其全部的修復(fù)代價預(yù)估定義如下:

LH(σ,σ′)=MD(σ,σ′)+FCσ′。

其中：MD(σ,σ′)是已有的修復(fù)代價，F(xiàn)Cσ′是軌跡完全被修復(fù)所需要的剩余修復(fù)代價，兩部分修復(fù)代價共同構(gòu)成了軌跡σ′的預(yù)估修復(fù)代價。在遍歷解空間的過程中，已知一個已經(jīng)產(chǎn)生的修復(fù)方案的代價為MDσ′，可以將該方案的修復(fù)代價設(shè)置為剪枝閾值。對于遍歷過程中的任意一個修復(fù)節(jié)點(diǎn)σ″，計算σ″對應(yīng)預(yù)估修復(fù)代價LH(σ,σ″)，將預(yù)估代價與剪枝閾值進(jìn)行比較：

(1)LH(σ,σ″)≥MDσ′，則該節(jié)點(diǎn)最終修復(fù)方案的修復(fù)代價一定大于MDσ′，可以安全地修剪掉當(dāng)前分支；

(2)LH(σ,σ″)

通過修復(fù)代價預(yù)估對搜索空間內(nèi)的無用修復(fù)分支進(jìn)行修復(fù)，從而加速修復(fù)算法的時間效率表現(xiàn)，基于A*算法的亂序軌跡修復(fù)方法的實現(xiàn)如算法1所示。算法第1行首先聲明一個優(yōu)先級隊列Q，內(nèi)部存放軌跡和位置信息的二元組；第3行表示每次從隊列Q中選擇一個預(yù)估代價最小的部分修復(fù)軌跡進(jìn)行修復(fù)；第7行表示調(diào)用錯位事件修復(fù)函數(shù)生成新軌跡；第8行表示修復(fù)后的軌跡符合模型約束，始終保留修復(fù)代價最小的修復(fù)結(jié)果；第11行表示新軌跡中仍然存在亂序問題，加入到隊列Q中；最后返回最優(yōu)修復(fù)結(jié)果。

算法1基于A*算法的亂序軌跡修復(fù)方法。

輸入：工流程模型Ns、待修復(fù)軌跡σ及其位置映射函數(shù)πσ；

輸出：最小修復(fù)方案σmin和位置映射函數(shù)πmin。

1 Q：={(σ, πσ)}，(σmin,πmin)：=NULL

2 while Q≠? do

3 (σ,πσ′)：=argmin(σ′,πσ′)∈QLH(σ,σ′)

4 Q：=Q{(σ,πσ′)}

5 ifLH(σ,σ′)

6 foreach e∈ECSσ′do

7 (σ″,πσ″)：=ad(e,σ)

8 if (σ″,πσ″)|=Nsthen

9 (σmin,πmin)：=Min((σ″,πσ″),(σmin,πmin))

10else

11Q：=Q∪{(σ″,πσ″)}

12 returnσmin,πmin

3 基于精煉流程結(jié)構(gòu)樹的亂序軌跡修復(fù)方法

基于A*的亂序軌跡修復(fù)方法，需要遍歷整個解的搜索空間，尋找修復(fù)代價最小的修復(fù)結(jié)果作為最優(yōu)修復(fù)。因此，為了加速修復(fù)方法的修復(fù)性能，提出一種基于精煉流程結(jié)構(gòu)樹的修復(fù)方法(Minimum Moving Distance repair using refined Process structure tree，MMDP)。精煉流程結(jié)構(gòu)樹 (Refined Process Structure Tree，RPST)最早由Polyvyanyy等[13]提出,是一種流程模型的層次化結(jié)構(gòu)表示，可以將流程模型轉(zhuǎn)換為由多個單入單出子結(jié)構(gòu)表示的樹狀結(jié)構(gòu)，每個子結(jié)構(gòu)稱為組件。MMDP方法流程框架描述如圖8所示。

3.1 模型分解

RPST的葉子節(jié)點(diǎn)代表了流程模型中的邊，在進(jìn)行軌跡修復(fù)前，需要將邊轉(zhuǎn)換為變遷節(jié)點(diǎn)，轉(zhuǎn)換規(guī)則如下：

規(guī)則2變遷節(jié)點(diǎn)轉(zhuǎn)換規(guī)則。

每一個RPST中的葉子節(jié)點(diǎn)，都對應(yīng)流程模型中的一條邊，每條邊都關(guān)聯(lián)一個變遷節(jié)點(diǎn)，若變遷節(jié)點(diǎn)只歸屬于一個組件，則直接轉(zhuǎn)換；若變遷節(jié)點(diǎn)同時屬于多個組件，則重復(fù)歸屬于多個組件中。

3.2 自頂向下的軌跡修復(fù)

從上到下依次遍歷RPST中的每一個組件，對于每個組件中包含的模型變遷節(jié)點(diǎn)，需要從軌跡中抽取對應(yīng)的事件，分離為單獨(dú)的軌跡片段。給定一個流程定義N，待修復(fù)軌跡σ，對應(yīng)位置映射函數(shù)π，對于遍歷過程中的一個組件S，分以下幾種情況討論：

情況1S是B組件，B組件同時可以表示互斥分支結(jié)構(gòu)、并發(fā)結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，細(xì)分為以下3種情況處理:

(1)S是互斥分支B組件，則S一定包含多個子組件，只需進(jìn)行子組件的修復(fù)即可;

(2)S是并發(fā)B組件，首先需要將以S為根結(jié)點(diǎn)的所有子組件標(biāo)記為MMDA修復(fù)組件，然后進(jìn)行子組件的遍歷;

(3)S是循環(huán)B組件，使用MMDA方法直接修復(fù)S對應(yīng)的軌跡片段σ′，無需繼續(xù)向下遍歷。

(1)若S除包含組件外，還包含其他組件，需繼續(xù)向下進(jìn)行子組件的遍歷修復(fù);

(2)若S僅包含組件，且沒有被標(biāo)記為MMDA修復(fù)組件，則可利用軌跡重放算法修復(fù)，如算法2所示；

情況 3S是組件，無需修復(fù)，組件內(nèi)部僅包含一個變遷節(jié)點(diǎn)，對應(yīng)軌跡片段不存在錯位問題。

情況 4S是R組件，非結(jié)構(gòu)化部分，使用MMDA修復(fù)對應(yīng)軌跡片段。

對于不同的組件，首先抽取對應(yīng)的軌跡片段，然后分類別進(jìn)行修復(fù)。軌跡重放算法如算法2所示。第1行定義最終返回的最小修復(fù)軌跡，集合history為已經(jīng)觸發(fā)過的事件集合；第2行表示遍歷模型變遷，進(jìn)行對比重放；第3～第4行表示跳過已重放事件；第5～第8行表示當(dāng)前事件σ′(i)可以被重放，然后添加到結(jié)果當(dāng)中；第9～第11行表示當(dāng)前事件σ′(i)無法被重放，需要從軌跡中尋找一個可以被重放的事件t進(jìn)行重放;第12行更新當(dāng)前可達(dá)模型變遷；最后返回重放結(jié)果。

輸入：RPST 組件的開始節(jié)點(diǎn) Ms、結(jié)束節(jié)點(diǎn) Me和對應(yīng)軌跡片段σ′；

輸出：最小修復(fù)軌跡片段σmin。

1 σmin：=<>, M：=Ms, history：=?, i：=0

2 while M≠M(fèi)e do

3 if σ′∈history then

4 i：=i+1

5 if M[σ′(i)>M′ then

6 σmin：=σmin·σ′(i)

7 history:=history∪{σ′(i)}

8 i：=i+1

9 else?t∈σ′,M[t>M′then

10 σmin：=σmin·t

11 history：=history∪{t}

12 M：=M′

13 returnσmin

3.3 自底向上的軌跡合并

修復(fù)后的軌跡片段需要進(jìn)行合并整合，獲得最終的修復(fù)軌跡，在合并過程中，不僅需要保持組件內(nèi)部事件的有序，還要保證組件之間的有序。對于同屬一個父節(jié)點(diǎn)的兩個組件P1和P2，對應(yīng)修復(fù)后的軌跡片段為σP1和σP2，提出以下兩種合并方式:

(1)交叉合并。軌跡片段σP1和σP2，按照事件位置從小到大進(jìn)行排列合并，相同位置的事件按照原待修復(fù)軌跡中的出現(xiàn)次序排列，并對重復(fù)的開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)進(jìn)行判斷去重;

(2)追加合并。軌跡片段σP1或σP2，需借助2.1節(jié)中的變遷優(yōu)先級進(jìn)行合并，子結(jié)構(gòu)P1的開始節(jié)點(diǎn)MP1和子結(jié)構(gòu)P2的開始節(jié)點(diǎn)MP2，若m(MP1)>m(MP2)，則直接將軌跡σP2追加到軌跡σP1之后，否則將軌跡σP1追加到軌跡σP2之后。最后，判斷合并組件中，前一個組件的結(jié)束節(jié)點(diǎn)和后一個組件的開始節(jié)點(diǎn)是否重復(fù)，進(jìn)行節(jié)點(diǎn)去重。

(2)B組件包含的子組件，使用交叉合并方式合并子組件對應(yīng)的修復(fù)軌跡片段。

4 實驗評估

實驗部分除了本文提出的兩種修復(fù)方法之外，還將與Effa[4]和對齊Alignment[1]方法進(jìn)行對比。實驗數(shù)據(jù)主要分為企業(yè)流程模型數(shù)據(jù)集和人工實驗數(shù)據(jù)集兩大類。數(shù)據(jù)集詳細(xì)信息如表1所示。

表1 實驗使用的3種數(shù)據(jù)集統(tǒng)計信息

基于流程模型，使用日志生成器BeehiveZ生成正確的模型日志軌跡，根據(jù)實驗要求，使用ProM的DisorderLog插件對軌跡數(shù)據(jù)進(jìn)行事件亂序處理。

4.1 基于企業(yè)數(shù)據(jù)集實驗

4.1.1 修復(fù)效率實驗

如圖9所示為修復(fù)時間效率對比結(jié)果，本實驗將超過10 000 ms的修復(fù)過程視為超時修復(fù)，不再進(jìn)行最終時間的統(tǒng)計。分析實驗結(jié)果可得：Alignment方法修復(fù)效率最慢，MMDA修復(fù)時間效率明顯優(yōu)于Alignment；MMDP方法的修復(fù)效率要優(yōu)于MMDA，說明基于RPST的加速方式起到了明顯的效果；此外，基于啟發(fā)式的Effa修復(fù)方法是最快的。

4.1.2 修復(fù)精度實驗

如圖10a所示為因果網(wǎng)數(shù)據(jù)集最小修復(fù)精度對比實驗結(jié)果，因果網(wǎng)是只包含順序結(jié)構(gòu)和并發(fā)結(jié)構(gòu)的流程模型，其中MMDA,MMDP和Aligament修復(fù)精度較高；雖然Effa方法修復(fù)速度較快，但是修復(fù)精度較低，啟發(fā)式無法確保修復(fù)結(jié)果為最優(yōu)修復(fù)。

如圖10b所示為包含循環(huán)結(jié)構(gòu)的數(shù)據(jù)集絕對修復(fù)精度實驗結(jié)果，其中MMDA和MMDP方法可以較好地對包含循環(huán)結(jié)構(gòu)的亂序軌跡進(jìn)行修復(fù)；Effa方法修復(fù)精度最低，這是由于其循環(huán)切分規(guī)則導(dǎo)致的。在修復(fù)過程中，Effa方法會首先選取軌跡中的某個事件作為切分點(diǎn)，然后直接將原始軌跡切分為多個片段，在每個片段內(nèi)對軌跡進(jìn)行修復(fù)，修復(fù)結(jié)果的好壞，很大程度上取決于循環(huán)切分點(diǎn)的選擇。

4.2 人工數(shù)據(jù)集實驗

4.2.1 MMDA方法

如圖11a所示為 MMDA方法的時間效率實驗結(jié)果圖，設(shè)置了4個軌跡事件亂序比例:20%、40%、60% 和 80%。由實驗結(jié)果可知，修復(fù)方法的性能表現(xiàn)不僅受到軌跡長度的影響，還受到軌跡內(nèi)事件亂序程度影響。

為了驗證等價軌跡檢測剪枝規(guī)則對修復(fù)方法性能的加速作用，進(jìn)行了如圖11b的實驗。圖中縱坐標(biāo)軸為修復(fù)算法遍歷的修復(fù)節(jié)點(diǎn)總數(shù)，由圖可知，采用剪枝的修復(fù)方法遍歷節(jié)點(diǎn)數(shù)始終低于無剪枝的修復(fù)方法，這也證明剪枝規(guī)則對修復(fù)方法起到了有效的加速作用。

4.2.2 MMDP方法

圖12a 所示為 MMDP方法時間效率實驗結(jié)果圖，分別選取了4個不同的軌跡亂序比例:20%、40%、60% 和 80%。相較于圖11a，MMDP性能表現(xiàn)更好，因為在遍歷的過程中，MMDP避免了大部分分支遍歷和分支回滾。除此之外，通過對比圖中不同的亂序比例修復(fù)曲線，可得 MMDP方法受軌跡亂序比例影響較小。

圖12b所示為拓展實驗，根據(jù)文獻(xiàn)[15]的調(diào)研結(jié)果顯示，一般企業(yè)級別的流程，上限活動數(shù)目為60個，實驗中將流程模型變遷節(jié)點(diǎn)數(shù)量上限拓展為150個，修復(fù)方法仍然可在30 ms內(nèi)完成修復(fù)，相較于MMDA方法，性能提升效果明顯。

5 結(jié)束語

本文提出了基于A*的亂序軌跡修復(fù)方法。首先，通過分析模型約束，比較軌跡中事件之間的次序優(yōu)先級，從而調(diào)整軌跡中的錯位事件。通過對比多個修復(fù)結(jié)果的修復(fù)代價，選取代價最小的結(jié)果作為最優(yōu)修復(fù)。為了進(jìn)一步提升修復(fù)算法的性能表現(xiàn)，提出了基于RPST的加速方式，有效地提升了修復(fù)時間效率表現(xiàn)。

本文未來的工作之一是多種軌跡錯誤類型的聯(lián)合修復(fù)，如軌跡事件的缺失和重復(fù)等。另外，無模型約束的亂序軌跡日志修復(fù)，也是值得拓展的方向之一。