王 琦，聞立杰，鄧雅方，錢(qián) 忱，王建民

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

0 引言

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

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

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

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

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

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

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

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

1 預(yù)備知識(shí)和問(wèn)題定義

1.1 預(yù)備知識(shí)

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

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

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

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

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

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

1.2 問(wèn)題定義

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

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

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

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

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

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

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

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

(1)σ′|=N；

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

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

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

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

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

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

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

定義8變遷優(yōu)先級(jí)。給定一個(gè)無(wú)環(huán)流程模型N=(P,T,F)，模型的開(kāi)始節(jié)點(diǎn)為b_start，結(jié)束節(jié)點(diǎn)為b_end，?t1,t2∈T，m(t1)和m(t2)分別表示變遷t1和t2在流程模型N中的變遷優(yōu)先級(jí)，F(xiàn)(t1,t2) 表示從t1開(kāi)始到節(jié)點(diǎn)t2之間所有路徑包含的變遷集合，變遷優(yōu)先級(jí)遵循如下規(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)先級(jí)時(shí)，需要將循環(huán)結(jié)構(gòu)進(jìn)行展開(kāi)操作，總是將L2中變遷優(yōu)先級(jí)小于L1中的變遷優(yōu)先級(jí)，L3結(jié)構(gòu)中變遷優(yōu)先級(jí)小于L2中的變遷優(yōu)先級(jí)，即?t0∈L0，?t1∈L1，?t2∈L2，?t3∈L3，滿足m(t0)>m(t1)>m(t2)>m(t3)。

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

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

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

(2)若d(e1)

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

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

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

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

(2)若m(φ(e1))

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

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

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

2.2 搜索空間的生成與遍歷

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

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

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

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

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

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

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

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

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

情況1?i

情況2?i

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

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

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

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

情況3不存在i

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

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

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

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

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

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

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

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

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

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

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

(2)LH(σ,σ″)

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

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

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

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

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

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

(1)S是互斥分支B組件，則S一定包含多個(gè)子組件，只需進(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對(duì)應(yīng)的軌跡片段σ′，無(wú)需繼續(xù)向下遍歷。

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

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

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

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

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

輸入：RPST 組件的開(kāi)始節(jié)點(diǎn) Ms、結(jié)束節(jié)點(diǎn) Me和對(duì)應(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ù)軌跡，在合并過(guò)程中，不僅需要保持組件內(nèi)部事件的有序，還要保證組件之間的有序。對(duì)于同屬一個(gè)父節(jié)點(diǎn)的兩個(gè)組件P1和P2，對(duì)應(yīng)修復(fù)后的軌跡片段為σP1和σP2，提出以下兩種合并方式:

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

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

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

4 實(shí)驗(yàn)評(píng)估

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

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

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

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

4.1.1 修復(fù)效率實(shí)驗(yàn)

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

4.1.2 修復(fù)精度實(shí)驗(yàn)

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

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

4.2 人工數(shù)據(jù)集實(shí)驗(yàn)

4.2.1 MMDA方法

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

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

4.2.2 MMDP方法

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

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

5 結(jié)束語(yǔ)

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

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