基于過程模型約束的軌跡亂序事件修復方法

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

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

0 引言

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

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

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

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

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

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

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

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

1 預備知識和問題定義

1.1 預備知識

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

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

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

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

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

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

1.2 問題定義

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

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

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

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

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

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

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

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

(1)σ′|=N；

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

2 基于A* 的亂序軌跡修復方法

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

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

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

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

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

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

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

(2)m(t1)

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

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

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

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

(2)若d(e1)

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

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

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

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

(2)若m(φ(e1))

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

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

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

2.2 搜索空間的生成與遍歷

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

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

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

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

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

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

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

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

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

情況1?i

情況2?i

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

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

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

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

情況3不存在i

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

定義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)中。

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

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

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

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

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

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

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

(2)LH(σ,σ″)

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

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

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

輸出：最小修復方案σ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 基于精煉流程結構樹的亂序軌跡修復方法

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

3.1 模型分解

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

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

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

3.2 自頂向下的軌跡修復

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

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

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

(2)S是并發(fā)B組件，首先需要將以S為根結點的所有子組件標記為MMDA修復組件，然后進行子組件的遍歷;

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

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

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

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

情況 4S是R組件，非結構化部分，使用MMDA修復對應軌跡片段。

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

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

輸出：最小修復軌跡片段σmin。

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

2 while M≠Me 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 自底向上的軌跡合并

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

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

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

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

4 實驗評估

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

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

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

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

4.1.1 修復效率實驗

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

4.1.2 修復精度實驗

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

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

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

4.2.1 MMDA方法

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

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

4.2.2 MMDP方法

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

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

5 結束語

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

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