基于啟發(fā)式搜索的帶循環(huán)模型一致性檢測方法

謝 燕,燕 輝,陳曉杰,段會龍,4

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

0 引言

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

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

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

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

1 相關(guān)知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 事件序列分解

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

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

3.2 重新組合過程

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

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

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

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

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

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

(1)

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

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

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

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

(2)

式中3種移動分別為EB,EM,EL。

(3)

(4)

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

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

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

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

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

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

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

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

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

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

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

2.初始化Mcur=M0;

3.初始化γgoal=[];

4.FOR每個子序列σLxDO //依次遍歷每個子序列

5. IF σLx==σL0THEN

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

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

8. ELSE

9. Flag=TRUE

10. DO

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

γ(Lx,Mcur)；

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

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

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

15. Mcur=Mcur+P；

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

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

18. ELSE

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

20. Flag=FLASE ；

21. WHILE (Flag==TRUE)

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

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

5 實例分析與計算

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

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

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

續(xù)表1

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

5.1 高效性

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

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

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

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

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

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

5.2 準(zhǔn)確性

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

6 結(jié)束語

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

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