謝 燕,燕 輝,陳曉杰,段會(huì)龍,4

(1.海南大學(xué) 生物醫(yī)學(xué)工程學(xué)院,海南 ?？?570100；2.海南大學(xué) 信息與通信工程學(xué)院,海南 海口 570100；3.海南省生物醫(yī)學(xué)工程重點(diǎn)實(shí)驗(yàn)室,海南 ?？?570100；4.浙江大學(xué) 生物醫(yī)學(xué)工程與儀器科學(xué)學(xué)院,浙江 杭州 310000)

0 引言

信息時(shí)代背景下，企業(yè)各種信息系統(tǒng)日益龐大復(fù)雜，給業(yè)務(wù)過(guò)程管理帶來(lái)了挑戰(zhàn)。在業(yè)務(wù)執(zhí)行過(guò)程中，信息系統(tǒng)會(huì)產(chǎn)生大量日志，挖掘潛在的有效信息有助于監(jiān)測(cè)和改進(jìn)實(shí)際業(yè)務(wù)過(guò)程[1]，提升業(yè)務(wù)過(guò)程的效率。因此，過(guò)程挖掘技術(shù)逐漸興起，成為業(yè)務(wù)過(guò)程管理領(lǐng)域中的研究熱點(diǎn)。過(guò)程挖掘技術(shù)從業(yè)務(wù)過(guò)程執(zhí)行期間記錄的事件日志中挖掘知識(shí)，其主要研究方向包括過(guò)程發(fā)現(xiàn)、一致性檢測(cè)和過(guò)程改進(jìn)[2-4]。其中，一致性檢測(cè)是將一個(gè)已知過(guò)程模型與所記錄的事件日志進(jìn)行比較，發(fā)現(xiàn)、定位和解釋兩者偏差，以發(fā)現(xiàn)存在的問(wèn)題和可能的改進(jìn)辦法。

早期，令牌重演[5-6 ]和足跡比較[7]是一致性檢測(cè)中比較經(jīng)典的方法，但其會(huì)因無(wú)法準(zhǔn)確定位而出現(xiàn)不一致性偏差。為解決這一問(wèn)題，BOSE等[8]和ADRIANSYAH等[9]引入事件日志與過(guò)程模型之間的“對(duì)齊”(alignments)概念，用于反映事件日志中記錄的事件與模型允許活動(dòng)之間的匹配程度。針對(duì)無(wú)循環(huán)過(guò)程模型，一般將所有對(duì)齊中偏差(也可用“代價(jià)”)最小的稱為最優(yōu)對(duì)齊[10](optimal alignments)。DELEONI等[10]將對(duì)齊問(wèn)題映射為一個(gè)自動(dòng)規(guī)劃問(wèn)題，但無(wú)法準(zhǔn)確計(jì)算出最優(yōu)對(duì)齊。分治法從過(guò)程模型的工作流分解和事件序列分割兩個(gè)角度考慮，通過(guò)修剪搜索空間、減少計(jì)算復(fù)雜度來(lái)提高搜索速度[11-13],但對(duì)過(guò)程模型結(jié)構(gòu)、事件日志遵從性有要求嚴(yán)格。TAYMOURI等[14]采用遺傳算法求近似最優(yōu)對(duì)齊，然而受初始種群和遺傳收斂的影響，該方法僅能找到幾個(gè)近似的最優(yōu)對(duì)齊，無(wú)法保證搜索到最優(yōu)解。目前，較好的計(jì)算對(duì)齊的方法是將最優(yōu)對(duì)齊轉(zhuǎn)化為可用A*算法搜索的最短路徑問(wèn)題[15-17]，可以找到最優(yōu)匹配，但是很難應(yīng)用于復(fù)雜的過(guò)程模型。

隨著業(yè)務(wù)過(guò)程復(fù)雜性和靈活性的增加，業(yè)務(wù)過(guò)程中可能會(huì)出現(xiàn)許多循環(huán)執(zhí)行的活動(dòng)。WANG等[18]提出一種基于Petri網(wǎng)帶循環(huán)語(yǔ)義的過(guò)程模型和事件日志之間的偏差檢測(cè)方法，該方法先識(shí)別出模型中的循環(huán)結(jié)構(gòu)，再?gòu)氖录蛄兄姓业脚c循環(huán)結(jié)構(gòu)相對(duì)應(yīng)的迭代子序列，檢測(cè)迭代子序列和循環(huán)結(jié)構(gòu)之間的行為偏差。然而，該方法只能分析循環(huán)部分的活動(dòng)序列，不能一次性檢測(cè)出整體模型偏差，而且如果循環(huán)結(jié)構(gòu)中出現(xiàn)重復(fù)活動(dòng)或過(guò)程模型存在多個(gè)循環(huán)嵌套，則將對(duì)檢測(cè)造成干擾，降低識(shí)別偏差的準(zhǔn)確性。YAN[17]提出一種窮盡展開(kāi)策略來(lái)查找?guī)аh(huán)的過(guò)程模型與事件日志的最優(yōu)對(duì)齊方法，該方法窮盡搜索所有循環(huán)展開(kāi)情況，搜索效率低，耗費(fèi)時(shí)間長(zhǎng)，甚至導(dǎo)致內(nèi)存溢出。啟發(fā)式搜索方法[19]用于應(yīng)對(duì)狀態(tài)空間爆炸問(wèn)題，VANDONGEN等[20]提出一種順序前綴對(duì)齊方法，利用整數(shù)線性規(guī)劃進(jìn)行迭代搜索，改進(jìn)對(duì)齊的可擴(kuò)展區(qū)域，然而該方法是以犧牲準(zhǔn)確性換取性能的提升。

綜上所述，針對(duì)帶循環(huán)的過(guò)程模型的一致性檢測(cè)方法尚存在以下局限:①在包含多個(gè)循環(huán)結(jié)構(gòu)或循環(huán)嵌套的過(guò)程模型中，不能確保找到全局最優(yōu)對(duì)齊；②搜索效率低下。為了解決這些問(wèn)題，本文提出一種新的基于啟發(fā)式搜索全局最優(yōu)對(duì)齊方法，該方法的主要貢獻(xiàn)為：①對(duì)事件序列迭代部分進(jìn)行分解，用來(lái)依次檢查與每個(gè)迭代部分匹配的循環(huán)結(jié)構(gòu)；②以事件序列與循環(huán)展開(kāi)情況的匹配程度為啟發(fā)信息搜索全局最優(yōu)對(duì)齊，能夠達(dá)到較高的效率和準(zhǔn)確性。

1 相關(guān)知識(shí)

本章介紹一些必要的基礎(chǔ)知識(shí)，從開(kāi)展下一步計(jì)算最優(yōu)對(duì)齊方法的研究。

任何具有執(zhí)行語(yǔ)義的過(guò)程模型均可通過(guò)生成狀態(tài)空間、提取狀態(tài)空間中活動(dòng)與活動(dòng)之間的關(guān)系，轉(zhuǎn)換為一個(gè)有向圖模型，也稱執(zhí)行空間[17]。

定義1執(zhí)行空間。過(guò)程模型的執(zhí)行空間是一個(gè)有向圖，M=(AM,RM)描述了模型中活動(dòng)與活動(dòng)之間的連接關(guān)系。其中：

(1)AM為執(zhí)行空間中活動(dòng)的集合。

(2)RM=AM×AM為一組有向弧,表示AM中活動(dòng)之間的連接關(guān)系。

(1)AL為事件集，每個(gè)事件包括一個(gè)標(biāo)識(shí)符、一個(gè)活動(dòng)名稱和一個(gè)時(shí)間戳。

(2)?L=AL×AL表示對(duì)AL中的事件進(jìn)行總排序，一般以時(shí)間戳排序。

事件日志L是由事件序列σL組成的有限非空集合，L=[σL1,σL2,…,σLn]。

對(duì)齊主要比較σL中的事件與M中的活動(dòng)之間的相關(guān)性，反映如何在模型上重演事件序列。

(1)如果x∈AL,y=⊥，則(x,⊥)為在“事件序列上移動(dòng)”，此時(shí)事件x未與執(zhí)行空間中的活動(dòng)匹配，對(duì)執(zhí)行空間而言，x是一個(gè)額外的新增事件。

(2)如果x=⊥,y∈AM，則(⊥,y)為在“模型上移動(dòng)”，此時(shí)缺少一個(gè)事件去匹配執(zhí)行空間的活動(dòng)y，可看作與給定執(zhí)行空間相比缺失一個(gè)事件。

(3)如果在x與y相關(guān)的條件下x∈AL且y∈AM，則(x,y)為“同步移動(dòng)”，表示事件x能與執(zhí)行空間中的活動(dòng)y匹配。

(4)其他情況為非法移動(dòng)。

定義4最優(yōu)對(duì)齊是ΓσL,M的子集，Γopt為ΓσL,M中同時(shí)滿足同步移動(dòng)數(shù)最大和偏差數(shù)最小的序列集合，Γopt={γopt|?γ∈ΓσL,M[Ω(γ)<Ω(γopt)]}，Ω與γ中的同步移動(dòng)正相關(guān)，當(dāng)兩條對(duì)齊的同步移動(dòng)數(shù)相同時(shí)，偏差數(shù)小的那條對(duì)齊的Ω值更大。

2 展開(kāi)循環(huán)生成多個(gè)執(zhí)行空間

YAN[17]研究了針對(duì)不帶循環(huán)的執(zhí)行空間與給定事件序列的最優(yōu)對(duì)齊計(jì)算方法。帶循環(huán)的過(guò)程模型中可能包含多個(gè)循環(huán)結(jié)構(gòu)，循環(huán)結(jié)構(gòu)展開(kāi)后可看作為不帶循環(huán)的執(zhí)行空間。由于存在多個(gè)循環(huán)結(jié)構(gòu)，且每個(gè)循環(huán)結(jié)構(gòu)均可被多次展開(kāi)，一個(gè)帶循環(huán)的過(guò)程模型所對(duì)應(yīng)的無(wú)循環(huán)的執(zhí)行空間數(shù)為無(wú)窮大。如圖1a所示，一個(gè)帶循環(huán)的執(zhí)行空間MLoop中包含k個(gè)循環(huán)結(jié)構(gòu)，用1st,2nd,…,kth區(qū)分循環(huán)結(jié)構(gòu)出現(xiàn)的順序。令M0為MLoop去掉所有循環(huán)結(jié)構(gòu)的執(zhí)行空間，M1,M2,…,Mk為在M0上分別展開(kāi)循環(huán)1st,2nd,…,kth一次所得的執(zhí)行空間。如圖1b所示，從M0開(kāi)始，逐漸展開(kāi)循環(huán)能不斷生成新的無(wú)循環(huán)的執(zhí)行空間，其中每個(gè)節(jié)點(diǎn)表示一個(gè)執(zhí)行空間，對(duì)應(yīng)一種循環(huán)展開(kāi)情況。例如，節(jié)點(diǎn)M1+2是先展開(kāi)循環(huán)1st再展開(kāi)循環(huán)2nd得到的執(zhí)行空間。根據(jù)圖1b中樹(shù)結(jié)構(gòu)的父—子關(guān)系，執(zhí)行空間之間也可稱為“父執(zhí)行空間”與“子執(zhí)行空間”。尋找最優(yōu)對(duì)齊的關(guān)鍵在于能在生成的多個(gè)執(zhí)行空間內(nèi)找到與事件序列最匹配的執(zhí)行空間。

3 事件序列分解再組合原理

在過(guò)程挖掘領(lǐng)域，事件序列是過(guò)程模型執(zhí)行的記錄(允許有偏差)。過(guò)程模型中的循環(huán)結(jié)構(gòu)表示某個(gè)活動(dòng)又一次被執(zhí)行，對(duì)應(yīng)事件序列中某個(gè)事件重復(fù)出現(xiàn)的情形。根據(jù)這一特點(diǎn)，可將事件序列按重復(fù)事件出現(xiàn)節(jié)點(diǎn)分解成若干子序列，以確定最適合被展開(kāi)的循環(huán)結(jié)構(gòu)。

3.1 事件序列分解

事件序列的事件名稱可能與過(guò)程模型中活動(dòng)的名稱AM相同，YAN[17]提出執(zhí)行空間中活動(dòng)的Floor值的概念。Floor值表示一個(gè)活動(dòng)相對(duì)Start與End的距離，例如緊跟Start的活動(dòng)的Floor值為1，End前一個(gè)活動(dòng)的Floor值為最長(zhǎng)軌跡中活動(dòng)的數(shù)目。圖1a中標(biāo)出了各活動(dòng)的Floor值，延循環(huán)結(jié)構(gòu)上活動(dòng)的Floor值會(huì)下降。

為了檢測(cè)事件序列中迭代部分，首先，為事件序列中每個(gè)事件的Mapfloor賦值。若某事件屬于活動(dòng)集AM，則其Mapfloor值為與該事件名稱相同的活動(dòng)的Floor值；若某事件不屬于活動(dòng)集AM，則其Mapfloor值等于零。其次，定義分解子序列的條件，即Mapfloor下降或保持不變。當(dāng)Mapfloor下降時(shí)，可能存在兩種情況：①M(fèi)apfloor為零，事件不能與模型中的活動(dòng)配對(duì)，此時(shí)不分解子序列；②Mapfloor不為零，說(shuō)明事件在其前驅(qū)事件前已發(fā)生，即重復(fù)，如果Mapfloor不變，則表示事件與其前驅(qū)事件一樣，對(duì)應(yīng)過(guò)程模型中一個(gè)活動(dòng)的自循環(huán)。在遍歷σL時(shí)，從第1個(gè)事件σL(1)開(kāi)始，當(dāng)檢測(cè)到σL(i+1)的Mapfloor值非零且不大于σL(i)的Mapfloor值時(shí)，將從σL(1)到σL(i)的片段識(shí)別為一個(gè)子序列并存儲(chǔ)在Segments中，σL(i+1)成為新的子序列的開(kāi)端，繼續(xù)檢測(cè)Mapfloor值。最終，分解后所有的子序列都存儲(chǔ)在Segments中，除Segments中的第1個(gè)子序列，其余每個(gè)子序列各表示一個(gè)迭代部分。

3.2 重新組合過(guò)程

將Segments中的子序列{Trace1,Trace2,…,Tracek+1}按下標(biāo)順序逐個(gè)取出并組合、累加，形成新的子序列集SegResult={σL0,σL1,σL2,…,σLk}。例如，σL0是Trace1，其不含迭代部分；σL1是下標(biāo)為1和2的Trace組合，其相比σL0新增了一個(gè)迭代部分。這樣，最后一個(gè)序列σLk就等于最初輸入的事件序列σL。

4 基于啟發(fā)式搜索的全局最優(yōu)對(duì)齊計(jì)算方法

第3章的事件序列被轉(zhuǎn)化為迭代部分遞增的子序列集SegResult。為了找到與某個(gè)迭代部分最匹配的循環(huán)結(jié)構(gòu)，將展開(kāi)循環(huán)結(jié)構(gòu)后的執(zhí)行空間看作不帶循環(huán)的執(zhí)行空間，采用不帶循環(huán)的執(zhí)行空間的方法[17](又稱單目標(biāo)搜索空間的最優(yōu)對(duì)齊計(jì)算方法)計(jì)算展開(kāi)該循環(huán)結(jié)構(gòu)后的局部最優(yōu)對(duì)齊，當(dāng)事件序列每次新增一個(gè)迭代部分時(shí)，將其局部最優(yōu)對(duì)齊作為啟發(fā)搜索信息，進(jìn)一步找到全局最優(yōu)對(duì)齊。

4.1 單目標(biāo)搜索空間下的最優(yōu)對(duì)齊計(jì)算方法

單目標(biāo)搜索空間下的最優(yōu)對(duì)齊計(jì)算方法，本質(zhì)上是一個(gè)執(zhí)行空間Mi與σL構(gòu)成的坐標(biāo)系搜索空間GMi:σL內(nèi)求解最短路徑的問(wèn)題[17]。雖然Dijkstra算法、A*算法均能找到單目標(biāo)搜索空間下的最短路徑，但是A*具有更高的搜索效率。具體地，在文獻(xiàn)[17]中，A*算法查找最短路徑的代價(jià)函數(shù)為fest(n)=greal(n)+a×(hL(n)+hM(n))，其中：greal(n)表示節(jié)點(diǎn)n的實(shí)際代價(jià);hM(n),hL(n)表示節(jié)點(diǎn)n沿模型和事件序列兩個(gè)維度的預(yù)估代價(jià);平衡因子a=0.7。

GMi:σL中的最短路徑等于最優(yōu)對(duì)齊的一個(gè)重要前提是合理設(shè)置GMi:σL中每條邊的代價(jià)值。本文在展開(kāi)循環(huán)結(jié)構(gòu)時(shí)需要重新設(shè)置代價(jià)值。當(dāng)節(jié)點(diǎn)ni擴(kuò)展到下一個(gè)節(jié)點(diǎn)nj時(shí)，模型展開(kāi)循環(huán)結(jié)構(gòu)，例如圖 1a 中從活動(dòng)a9跳轉(zhuǎn)到活動(dòng)a3，在實(shí)際的坐標(biāo)系上只移動(dòng)了一個(gè)單位距離，代價(jià)δLoop的實(shí)際值等于1。因此，當(dāng)ni擴(kuò)展到nj執(zhí)行循環(huán)結(jié)構(gòu)時(shí)，eij的代價(jià)設(shè)置為

(1)

式中EB,EM,EL分別為沿同步維度、模型維度和事件序列維度上的邊集。

4.2 展開(kāi)循環(huán)前后同一事件序列的最優(yōu)對(duì)齊結(jié)果比較

推論1給定一條事件序列和一個(gè)有環(huán)有向圖表示的帶循環(huán)的過(guò)程模型，展開(kāi)循環(huán)得到的無(wú)環(huán)有向圖與該事件序列的最優(yōu)對(duì)齊稱為子最優(yōu)對(duì)齊，去掉循環(huán)的無(wú)環(huán)有向圖與該事件序列的最優(yōu)對(duì)齊稱為父最優(yōu)對(duì)齊，則子最優(yōu)對(duì)齊包含的同步移動(dòng)數(shù)不會(huì)小于父最優(yōu)對(duì)齊中的同步移動(dòng)數(shù)。

證明針對(duì)任意事件序列σLx和執(zhí)行空間My，設(shè)σLx與My最優(yōu)對(duì)齊表示為γ(x,y)，

(2)

式中3種移動(dòng)分別為EB,EM,EL。

(3)

(4)

4.3 基于啟發(fā)信息的全局最優(yōu)對(duì)齊計(jì)算方法

利用第3章的方法，σL被分解為迭代部分遞增的子序列的集合SegResult：[σL0,σL1,σL2,…,σLk]。本節(jié)依次檢查σL中每個(gè)迭代部分是否能匹配模型MLoop中的循環(huán)結(jié)構(gòu)，并找到與迭代部分最匹配的“有利”循環(huán)結(jié)構(gòu)，逐漸確定隨迭代部分遞增的最優(yōu)的循環(huán)結(jié)構(gòu)展開(kāi)過(guò)程，最終計(jì)算出全局最優(yōu)對(duì)齊。

隨迭代部分遞增的最優(yōu)循環(huán)結(jié)構(gòu)展開(kāi)過(guò)程如圖2所示，其中：橫坐標(biāo)表示迭代部分遞增的事件序列，縱坐標(biāo)表示隨循環(huán)結(jié)構(gòu)展開(kāi)得到的子執(zhí)行空間；M0為MLoop去掉所有循環(huán)結(jié)構(gòu)的執(zhí)行空間，σL0為原事件序列σL分解后不包含任何迭代部分(重復(fù)事件)的子序列(見(jiàn)3.1節(jié))。因此搜索的起點(diǎn)為(σL0,M0)；坐標(biāo)系中任一節(jié)點(diǎn)(σLx,My)表示子序列σLx與執(zhí)行空間My的最優(yōu)對(duì)齊結(jié)果。

令搜索中的當(dāng)前點(diǎn)為(σLx,My)，首先確定σLx中最新加入的迭代部分是否在My處取得最好的對(duì)齊。在My上展開(kāi)所有循環(huán)結(jié)構(gòu)1st,2nd,…,kth一次，相應(yīng)得到多個(gè)子執(zhí)行空間，分別計(jì)算其與σLx之間的最優(yōu)對(duì)齊。根據(jù)推論1，對(duì)于同一個(gè)事件序列σLx，在My上展開(kāi)循環(huán)結(jié)構(gòu)后，其子執(zhí)行空間與σLx之間的最優(yōu)對(duì)齊存在兩種情況：

(1)同步移動(dòng)數(shù)不變，但最優(yōu)對(duì)齊中偏差增多 由于在My上展開(kāi)了一個(gè)循環(huán)結(jié)構(gòu)，即模型部分變長(zhǎng)，同步移動(dòng)數(shù)不變，表示變長(zhǎng)的部分全部為偏差，說(shuō)明σLx的最優(yōu)執(zhí)行空間為My，可檢測(cè)下一個(gè)迭代部分，即節(jié)點(diǎn)(σLx,My)擴(kuò)展至(σLx+1,My)(沿水平方向移動(dòng))。

(2)同步移動(dòng)數(shù)增加，找到更好的最優(yōu)對(duì)齊 在My上展開(kāi)一個(gè)循環(huán)結(jié)構(gòu)后，新的模型為My+(p+1)opt(在My上展開(kāi)的第p+1個(gè)循環(huán)結(jié)構(gòu))。新模型較舊模型中間增長(zhǎng)了一部分，增長(zhǎng)的這部分恰好能形成同步移動(dòng)，說(shuō)明從My到My+(p+1)opt這一循環(huán)展開(kāi)是有利的，則節(jié)點(diǎn)應(yīng)由(σLx,My)擴(kuò)展至(σLx,My+(p+1)opt)(沿垂直方向移動(dòng))。

綜上所述，從起點(diǎn)(σL0,M0)開(kāi)始，在事件序列上逐漸增加迭代部分，檢查是否存在與新增迭代部分匹配的有利循環(huán)結(jié)構(gòu)，利用分別沿水平方向和垂直方向擴(kuò)展的啟發(fā)信息逐漸確定最優(yōu)的循環(huán)展開(kāi)情況，直到事件序列的最后一個(gè)迭代部分檢查完畢，停止搜索。啟發(fā)式搜索全局最優(yōu)對(duì)齊過(guò)程如算法1所示，其中Mcur為找到的執(zhí)行空間，其初始值為M0，下標(biāo)cur為循環(huán)結(jié)構(gòu)的展開(kāi)順序，當(dāng)新展開(kāi)循環(huán)后得到的子執(zhí)行空間比原執(zhí)行空間含有更多數(shù)目的同步移動(dòng)時(shí)(稱為有利的循環(huán)展開(kāi)情況)，對(duì)Mcur進(jìn)行更新。列表QLoop依次存放有利循環(huán)結(jié)構(gòu)，γgoal存放每次處理子序列時(shí)找到的最優(yōu)對(duì)齊。

算法1全局最優(yōu)對(duì)齊算法。計(jì)算事件序列與循環(huán)模型之間的全局最優(yōu)對(duì)齊。

輸入：子序列集[σL0,σL1,σL2,…,σLk]、模型MLoop。

輸出：記錄最優(yōu)循環(huán)結(jié)構(gòu)展開(kāi)過(guò)程列表QLoop，全局最優(yōu)對(duì)齊γgoal。

1.初始化列表QLoop={};

2.初始化Mcur=M0;

3.初始化γgoal=[];

4.FOR每個(gè)子序列σLxDO //依次遍歷每個(gè)子序列

5. IF σLx==σL0THEN

6. 在搜索空間G(σLx,Mcur)中尋找最優(yōu)對(duì)齊，記為γ(Lx,Mcur)；

7. γgoal=γ(Lx,Mcur)；

8. ELSE

9. Flag=TRUE

10. DO

11. 在搜索空間G(σLx,Mcur)中尋找最優(yōu)對(duì)齊，記為

γ(Lx,Mcur)；

12. 將Mcur中全部有效循環(huán)結(jié)構(gòu)展開(kāi)1次，構(gòu)建子搜索空間G(σLx,Mcur+1),G(σLx,Mcur+2),…;

13. 計(jì)算所有子搜索空間最優(yōu)對(duì)齊，尋找其中最好的最優(yōu)對(duì)齊記為γ(Lx,Mcur+p);

14. IF Ω(γ(Lx,Mcur))<Ω(γ(Lx,Mcur+p)) THEN //展開(kāi)循環(huán)后能找到更優(yōu)的對(duì)齊

15. Mcur=Mcur+P；

16. QLoop=QLoop∪{P}； //循環(huán)P是G(σLx,Mcur)最優(yōu)子搜索空間中最后展開(kāi)的循環(huán)結(jié)構(gòu)

17. γgoal=γ(Lx,Mcur+p)；

18. ELSE

19. γgoal=γ(Lx,Mcur)；

20. Flag=FLASE ；

21. WHILE (Flag==TRUE)

算法1過(guò)程如下：依次從子序列集中取一個(gè)子序列σLx進(jìn)行處理，找到針對(duì)子序列的最優(yōu)執(zhí)行空間。取第1個(gè)子序列時(shí)σLx==σL0，由于σL0中沒(méi)有迭代部分，無(wú)需在Mcur上展開(kāi)循環(huán)。除此之外，每個(gè)σLx相比上個(gè)子序列σLx-1新增了一個(gè)迭代部分，借助單目標(biāo)最優(yōu)對(duì)齊計(jì)算方法，檢查在Mcur上展開(kāi)1次循環(huán)后的子搜索空間中是否能找到更好的對(duì)齊，是則更新Mcur的值，令Mcur=Mcur+P，表示在Mcur上再展開(kāi)有利循環(huán)結(jié)構(gòu)P，將有利循環(huán)結(jié)構(gòu)放入列表QLoop。Flag表示繼續(xù)展開(kāi)的標(biāo)識(shí)符，當(dāng)在子搜索空間中找不到更好的對(duì)齊時(shí)，停止對(duì)子序列σLx的處理，相當(dāng)于找到了σLx的最優(yōu)執(zhí)行空間。遍歷處理完子序列后，γgoal即存儲(chǔ)了最后一個(gè)子序列的最優(yōu)對(duì)齊，其為σL和MLoop之間的全局最優(yōu)對(duì)齊。

值得注意的是，當(dāng)事件序列中包含較多缺失事件時(shí)，可能出現(xiàn)事件序列中一個(gè)迭代部分與兩個(gè)以上循環(huán)結(jié)構(gòu)之間匹配的情況，需要在展開(kāi)一個(gè)有利循環(huán)的執(zhí)行空間My+(p+1)opt上繼續(xù)展開(kāi)循環(huán)結(jié)構(gòu)進(jìn)行查找，直到在其后代子執(zhí)行空間中不能找到更優(yōu)的對(duì)齊才停止對(duì)子序列σLx的搜索。

5 實(shí)例分析與計(jì)算

本章分析了一個(gè)包括4個(gè)循環(huán)結(jié)構(gòu)的模型和對(duì)應(yīng)事件日志集之間的偏差檢測(cè)過(guò)程，驗(yàn)證了基于啟發(fā)信息計(jì)算全局最優(yōu)對(duì)齊方法的高效性和準(zhǔn)確性。

荷蘭馬斯特里赫特大學(xué)醫(yī)學(xué)中心ICU的機(jī)械通氣脫機(jī)過(guò)程模型轉(zhuǎn)換到執(zhí)行空間的研究結(jié)果如圖3所示，其中活動(dòng)序列最大長(zhǎng)度為11。有向圖中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)過(guò)程模型中的一個(gè)活動(dòng)，節(jié)點(diǎn)與活動(dòng)之間的映射關(guān)系如表1所示。該模型包括并行、順序和循環(huán)結(jié)構(gòu)，存在復(fù)雜循環(huán)嵌套。模型中4個(gè)循環(huán)結(jié)構(gòu)按執(zhí)行的先后順序標(biāo)記為1st,2nd,3rd,4th。基于啟發(fā)信息計(jì)算全局最優(yōu)對(duì)齊的源程序采用Python語(yǔ)言編寫，軟件環(huán)境為PyCharm2020.2.3中配置Python 3.7，硬件環(huán)境為Intel(R) Core(TM) 3.10 GHz處理器，8 GB內(nèi)存。

表1 圖3中節(jié)點(diǎn)與活動(dòng)之間的映射關(guān)系

續(xù)表1

檢測(cè)過(guò)程中用M的下標(biāo)表示循環(huán)展開(kāi)情況，例如，M0表示未執(zhí)行任何循環(huán)結(jié)構(gòu)，M123表示循環(huán)結(jié)構(gòu)執(zhí)行的順序?yàn)?st→2nd→3rd。通過(guò)隨機(jī)增加或刪除事件的方式在擬合的事件序列上引入偏差，將新增的事件名稱均記為“Devs”。偏差率為偏差數(shù)目/對(duì)齊序列長(zhǎng)度。

5.1 高效性

對(duì)于給定的包含多條事件序列的事件日志和執(zhí)行空間，平均入隊(duì)節(jié)點(diǎn)數(shù)指計(jì)算單條事件序列的最優(yōu)對(duì)齊時(shí)生成的節(jié)點(diǎn)數(shù)的總和除以事件序列數(shù)，其表示勘探區(qū)域的大??；運(yùn)行時(shí)間指平均檢測(cè)一條事件序列的運(yùn)行時(shí)間。

在查找全局最優(yōu)對(duì)齊時(shí)，啟發(fā)式搜索方法依賴已找到的部分循環(huán)展開(kāi)結(jié)果，從迭代部分遞增的子序列中尋找有利循環(huán)結(jié)構(gòu)，避免檢查不必要的搜索空間，具有較好的搜索效率，而文獻(xiàn)[17]的窮盡展開(kāi)策略會(huì)系統(tǒng)檢查所有循環(huán)展開(kāi)情況。將啟發(fā)式搜索和窮盡展開(kāi)從空間和時(shí)間復(fù)雜度進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表2所示。

表2 窮盡展開(kāi)搜索和啟發(fā)式搜索的比較

表2中，針對(duì)9種循環(huán)展開(kāi)情況(第1列)設(shè)置了偏差率為32%左右的事件日志(L0～L8),每條日志包括100條事件序列。在相同事件序列下，當(dāng)測(cè)試M0時(shí)，采用啟發(fā)式搜索方法僅檢查一個(gè)搜索空間GM0,σL0，而窮盡展開(kāi)策略還需要檢查GM0,σL0的后代子搜索空間。從測(cè)試結(jié)果可以看出，當(dāng)循環(huán)結(jié)構(gòu)增加時(shí)，啟發(fā)式搜索方法無(wú)論在占用內(nèi)存還是計(jì)算時(shí)間方面均明顯優(yōu)于窮盡展開(kāi)策略。當(dāng)模型內(nèi)部循環(huán)結(jié)構(gòu)數(shù)等于7時(shí)(M2212344),窮盡展開(kāi)策略出現(xiàn)內(nèi)存溢出，而啟發(fā)式搜索方法的運(yùn)行時(shí)間不足1 s，驗(yàn)證了啟發(fā)式搜索方法的高效性。

針對(duì)M0,M2,M1233種循環(huán)展開(kāi)情況，設(shè)計(jì)了偏差逐漸增大的14條事件日志(L0～L13)，對(duì)應(yīng)平均偏差率分別為0%，10%，16%，23%，31%，35%，39%，43%，47%，51%，56%，64%，69%，75%，每條日志包括100條事件序列。圖4所示為記錄的平均入隊(duì)節(jié)點(diǎn)數(shù)和運(yùn)行時(shí)間，可見(jiàn)在偏差逐漸增大的事件日志中，最大運(yùn)行時(shí)間不超過(guò)30 ms,驗(yàn)證了該方法的高效性。

當(dāng)偏差率增大時(shí)，將在每個(gè)搜索空間探索更多節(jié)點(diǎn)。當(dāng)隨機(jī)插入缺失事件時(shí)，容易刪除事件序列中的迭代部分而減少子序列數(shù)，相當(dāng)于減少了搜索空間。因此，偏差逐漸增大時(shí)，平均入隊(duì)節(jié)點(diǎn)數(shù)不完全符合遞增規(guī)律。

5.2 準(zhǔn)確性

以同樣方式，針對(duì)9種循環(huán)展開(kāi)情況，設(shè)計(jì)了偏差率由0%增大至75%的14條事件日志(L0～L13)，每條日志包括100條事件序列。圖5所示為記錄的準(zhǔn)確率，其中檢測(cè)到的最低準(zhǔn)確率為94%。少部分事件序列未找到全局最優(yōu)對(duì)齊，原因是：①循環(huán)2nd和循環(huán)4th兩者相似度為50%(存在3個(gè)共同活動(dòng))，針對(duì)個(gè)別子序列誤判了最優(yōu)執(zhí)行空間，導(dǎo)致計(jì)算結(jié)果與理想的全局最優(yōu)對(duì)齊之間存在較小范圍的誤差。在準(zhǔn)確率最低時(shí)，實(shí)際測(cè)得的同步移動(dòng)數(shù)與理想同步移動(dòng)數(shù)之間的平均誤差小于0.1。②在事件序列中插入過(guò)多缺失事件時(shí)，循環(huán)結(jié)構(gòu)的展開(kāi)部分不能與事件序列的迭代部分一一對(duì)應(yīng)。針對(duì)極個(gè)別事件序列，特別是出現(xiàn)循環(huán)嵌套時(shí)，算法陷入局部最優(yōu)。針對(duì)圖4和圖5中的12種循環(huán)展開(kāi)情況，在偏差率逐漸增大的168條事件日志中，應(yīng)用啟發(fā)式策略計(jì)算全局最優(yōu)對(duì)齊，測(cè)得的平均準(zhǔn)確率為99.8%，驗(yàn)證了該方法的準(zhǔn)確性。

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

針對(duì)復(fù)雜的帶循環(huán)過(guò)程模型與事件序列的一致性檢測(cè)問(wèn)題，本文提出一種新的啟發(fā)式信息搜索全局最優(yōu)對(duì)齊方法。由于存在循環(huán)嵌套，不同循環(huán)結(jié)構(gòu)之間相互干擾，使準(zhǔn)確尋找全局最優(yōu)對(duì)齊十分困難。為了避免陷入局部最優(yōu)，首先將事件序列分解為迭代部分遞增的子序列集。通過(guò)遍歷處理子序列，逐漸挖掘與子序列中新增迭代部分匹配的有利循環(huán)結(jié)構(gòu)，找到最優(yōu)的循環(huán)結(jié)構(gòu)展開(kāi)過(guò)程。將已找到的有利循環(huán)結(jié)構(gòu)作為啟發(fā)式搜索信息，有效修剪搜索空間，提高了搜索全局最優(yōu)對(duì)齊的效率。在機(jī)械通氣脫機(jī)過(guò)程模型中對(duì)該方法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明該方法能有效解決循環(huán)模型的全局最優(yōu)對(duì)齊計(jì)算問(wèn)題，達(dá)到接近100%的準(zhǔn)確率，與已有的窮盡展開(kāi)策略對(duì)比顯示了所提方法在效率方面的優(yōu)勢(shì)。

未來(lái)研究的重點(diǎn)是：①將該方法應(yīng)用于真實(shí)事件日志，檢測(cè)模型與真實(shí)事件之間的偏差，以輔助修復(fù)和增強(qiáng)模型；②當(dāng)新增事件屬于循環(huán)結(jié)構(gòu)活動(dòng)集時(shí)，分解后的子序列集會(huì)增大，為了匹配新增事件，將在模型中展開(kāi)循環(huán)結(jié)構(gòu)以檢查更多的搜索空間，增加了對(duì)齊中引入的偏差數(shù)，降低了實(shí)際事件日志與模型之間的匹配程度，導(dǎo)致耗費(fèi)過(guò)多計(jì)算時(shí)間，今后研究將結(jié)合實(shí)際考慮真實(shí)事件中迭代部分的重復(fù)概率，對(duì)事件序列進(jìn)行預(yù)處理，剔除異常事件，限定循環(huán)結(jié)構(gòu)展開(kāi)次數(shù)，使得事件序列更接近模型的執(zhí)行軌跡。