基于行為校驗(yàn)與偏差組合的過(guò)程模型修復(fù)

張力雯，方賢文+，邵叱風(fēng)，王麗麗，2

(1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001；2.同濟(jì)大學(xué) 嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室,上海 201804)

0 引言

(1)研究背景

過(guò)程挖掘技術(shù)是從信息系統(tǒng)所記錄的事件日志中提取知識(shí)發(fā)現(xiàn)過(guò)程模型，并通過(guò)提供技術(shù)和工具對(duì)其實(shí)現(xiàn)性能上的改善[1]。過(guò)程挖掘技術(shù)主要從過(guò)程發(fā)現(xiàn)、服從性校驗(yàn)和過(guò)程完善[2]3個(gè)方面對(duì)業(yè)務(wù)流程進(jìn)行分析，其中過(guò)程發(fā)現(xiàn)及服從性校驗(yàn)最為重要[3]。模型修復(fù)是介于過(guò)程發(fā)現(xiàn)與服從性校驗(yàn)之間的一種過(guò)程挖掘的新類型，主要考慮使得事件日志無(wú)法回放于過(guò)程模型的部分行為，并使修復(fù)后的過(guò)程模型盡可能與初始模型相似[4]。模型修復(fù)適用于一致性校驗(yàn)、演變過(guò)程監(jiān)測(cè)、定制化需求3種情況，本文主要根據(jù)一致性校驗(yàn)檢測(cè)到的無(wú)法回放行為對(duì)業(yè)務(wù)流程進(jìn)行修復(fù)[5]。一致性校驗(yàn)可以被應(yīng)用于不同的設(shè)置中，主要包括合規(guī)性審計(jì)、模型維護(hù)以及自動(dòng)化的過(guò)程發(fā)現(xiàn)。合規(guī)性審計(jì)只可以檢測(cè)出事件日志無(wú)法回放于過(guò)程模型的行為，即不適合行為[6];模型維護(hù)是檢測(cè)所有偏差行為的設(shè)置，既可以診斷事件日志無(wú)法回放于模型的行為也可以發(fā)現(xiàn)模型中所特有的行為，即不適合行為與額外行為[7]；自動(dòng)化的過(guò)程發(fā)現(xiàn)是根據(jù)一致性校驗(yàn)的輸出結(jié)果對(duì)過(guò)程模型進(jìn)行調(diào)整，通過(guò)移除日志中沒(méi)有記錄但模型中可以捕獲的行為或者添加僅日志中可觀測(cè)的行為來(lái)實(shí)現(xiàn)對(duì)初始模型的自動(dòng)化調(diào)整。本文通過(guò)并發(fā)關(guān)系、序列關(guān)系、沖突關(guān)系劃分事件日志與過(guò)程模型的可達(dá)活動(dòng)圖表，并基于行為關(guān)系的一致性校驗(yàn)識(shí)別它們之間可回放與不可回放的行為模式。

模型修復(fù)主要針對(duì)事件日志無(wú)法回放于過(guò)程模型上的不適合行為進(jìn)行處理，當(dāng)前技術(shù)采用自循環(huán)插入/跳過(guò)的方式優(yōu)先考慮適合度的改善[8-9]。對(duì)齊事件日志與過(guò)程模型，并檢測(cè)到它們之間盡可能少的偏差元素，更有利于對(duì)適合度的分析[10]。通過(guò)最優(yōu)對(duì)齊檢測(cè)偏差成本，并將多個(gè)經(jīng)典問(wèn)題的解決方案轉(zhuǎn)換為搜索修復(fù)建議的方法,即基于偏差成本與修復(fù)資源間的單調(diào)性在適合度與計(jì)算量之間進(jìn)行權(quán)衡[11]。根據(jù)一致性校驗(yàn)的四個(gè)性能參數(shù)從不同角度介紹過(guò)程模型的修復(fù)方法，并將滿足并發(fā)關(guān)系的兩個(gè)直接跟隨偏差組合為子結(jié)構(gòu)[12]。這種方法能夠在保證適合度的前提下，對(duì)精度起到一定的改善。但其沒(méi)有定義對(duì)應(yīng)的偏差檢測(cè)方法，因此無(wú)法適用于各種不同的情況。由于當(dāng)前技術(shù)往往需要犧牲一定的精度來(lái)?yè)Q取適合度的提升，容易出現(xiàn)欠擬合的情況[13-14]。產(chǎn)生上述問(wèn)題的原因主要是修復(fù)工作只基于偏差的成本和位置信息來(lái)進(jìn)行，而不考慮它們之間的行為關(guān)系。本文是對(duì)之前研究工作的延伸，其將所有滿足特定行為關(guān)系的直接跟隨偏差構(gòu)建為子結(jié)構(gòu)。由于擬合度直接反映事件日志是否完整地回放于過(guò)程模型，需要在保證擬合度的前提下盡可能提高精度的值。

(2)相關(guān)工作

本文所提方法與以下兩個(gè)方面的技術(shù)有著緊密聯(lián)系：①業(yè)務(wù)流程的服從性校驗(yàn)；②插入自循環(huán)結(jié)構(gòu)的簡(jiǎn)單模型修復(fù)[15]。

根據(jù)偏差類型的不同將當(dāng)前服從性校驗(yàn)方法分為兩類：①基于事件日志與過(guò)程模型之間的最優(yōu)對(duì)齊檢測(cè)偏差的發(fā)生次數(shù)與位置；②基于事件日志與過(guò)程模型之間行為關(guān)系發(fā)現(xiàn)不匹配行為模式。第①類校驗(yàn)方法利用啟發(fā)式算法與跡回放來(lái)獲取有效的最優(yōu)對(duì)齊[16]，并將其中所有同步移動(dòng)與非同步移動(dòng)的成本分別設(shè)置為“0”、“1” (含有不可視變遷r的非同步移動(dòng)成本為“0”)；第②類校驗(yàn)方法則是通過(guò)構(gòu)建事件日志與過(guò)程模型的事件結(jié)構(gòu)產(chǎn)生它們之間的部分同步化產(chǎn)品，再將所有事件的執(zhí)行配置集展開(kāi)發(fā)現(xiàn)偏差元素及其潛在的行為關(guān)系。通過(guò)介紹9種不匹配模式下可能產(chǎn)生的偏差，分別從不同角度對(duì)不匹配模式中的隱操作進(jìn)行分析[17]。本文將這兩種一致性校驗(yàn)方法相結(jié)合，首先基于行為關(guān)系識(shí)別事件日志與過(guò)程模型相對(duì)應(yīng)的行為模式(包括可回放的行為模式與不可回放的行為模式)，并利用由此產(chǎn)生的最優(yōu)對(duì)齊檢測(cè)出修復(fù)操作所需要的偏差完整信息[18]。這種完整信息不僅包含偏差的發(fā)生和位置，還包括不可回放模式中直接跟隨偏差之間的行為關(guān)系。

模型修復(fù)技術(shù)旨在使修復(fù)后的過(guò)程模型能夠回放事件日志，并盡可能保存初始模型中的行為。使用最小成本完成最大可能的修復(fù)以及使用手動(dòng)修復(fù)盡可能減少模型上冗余的行為，僅考慮擬合度的改善而忽視精度[19-20]。定義后的擴(kuò)展對(duì)齊被添加到模型上的可達(dá)標(biāo)識(shí)，且過(guò)程模型上的偏差能夠被核算和修復(fù)[21]。模型的修復(fù)位置通過(guò)邏輯Petri網(wǎng)和選擇結(jié)構(gòu)之間的轉(zhuǎn)換關(guān)系確定[22]。盡管上述兩種方法能夠綜合考慮模型修復(fù)的各種度量標(biāo)準(zhǔn)，但只適用于有選擇結(jié)構(gòu)的過(guò)程模型。根據(jù)6種不同算法在特定的約束條件下獲得修復(fù)建議，旨在權(quán)衡適合度與修復(fù)效率之間的最優(yōu)性[11]。由于這種修復(fù)方法僅根據(jù)修復(fù)建議對(duì)每個(gè)偏差元素進(jìn)行插入/跳過(guò)操作，因此會(huì)以犧牲精度為代價(jià)換取適合度的改善?；诓l(fā)行為關(guān)系構(gòu)建子結(jié)構(gòu)可以使精度略有提升，但仍然存在一定的局限性[12]。本文將偏差的發(fā)生、位置以及直接跟隨偏差活動(dòng)之間的行為關(guān)系作為模型修復(fù)的輸入信息，并將若干個(gè)具有特定行為關(guān)系的直接跟隨偏差構(gòu)建為一個(gè)子結(jié)構(gòu)。因此，可通過(guò)減少事件日志中無(wú)法被準(zhǔn)確修復(fù)的偏差數(shù)量來(lái)提升精度值。

1 基本定義

定義 2標(biāo)簽Petri網(wǎng)系統(tǒng)。 設(shè)定一個(gè)元組N*=(P,T,F,,λ,Mi)為標(biāo)簽工作流網(wǎng)系統(tǒng)，其中P表示庫(kù)所集，p表示網(wǎng)系統(tǒng)中的庫(kù)所，?p∈P；T是變遷集，t是網(wǎng)系統(tǒng)中的變遷，?t∈T；F是連接所有直接跟隨庫(kù)所與變遷之間的流關(guān)系，F(xiàn)?(P×T)(T×P)；為標(biāo)簽WF-net系統(tǒng)上所有活動(dòng)的標(biāo)簽集，=Z∪{τ}；λ是指定函數(shù)，將所有變遷指定為相應(yīng)活動(dòng)的標(biāo)簽或τ：T←Z∪{τ},?λ(t)∈Z∪{τ};Mi是網(wǎng)系統(tǒng)N*中的初始標(biāo)識(shí)，Mi(p)≥1。

表1 單位移動(dòng)的成本

定義 4不可回放的行為模式。模型修復(fù)針對(duì)事件日志無(wú)法回放于過(guò)程模型的非一致行為進(jìn)行處理，根據(jù)兩個(gè)相對(duì)應(yīng)模式之間行為關(guān)系的差異可將它們合并為一個(gè)不可回放的行為模式，記作：BL/N*=(B(L/N*)(+,,×),BL/N*?,Bl(e),Bλ(t),B┘)。其中：B(L/N*)(+,,×)是由并發(fā)、沖突、因果中任意兩個(gè)行為關(guān)系所產(chǎn)生的不可回放行為模式；BL/N*?表示由行為包含所產(chǎn)生的不可回放行為模式，根據(jù)行為包含的嚴(yán)格性等級(jí)不同，可以將行為包含模式分為以下兩種類型：①行為模式的整體包含；②行為模式的部分包含。前者是將一個(gè)完整的不可回放模式看作子結(jié)構(gòu)進(jìn)行修復(fù)，而后者僅考慮片段中的部分包含行為。根據(jù)行為關(guān)系的不同可將行為包含模式分為以下3種類型：①并發(fā)關(guān)系的行為包含，包括整體包含與部分包含(并發(fā)/因果模式屬于并發(fā)結(jié)構(gòu)中的部分行為包含，反之則無(wú)需進(jìn)行修復(fù))，記作BL/N*?+、BL?·+(B+/)；②因果關(guān)系的行為包含，這種情況只涉及整體包含，記作BL/N*?;③沖突關(guān)系的行為包含，包括整體包含與部分包含，分別記作BL/N*?×、BL?·×。這里的部分包含主要指事件日志包含過(guò)程模型的行為，反之則無(wú)需進(jìn)行修復(fù)。例如：過(guò)程模型的行為模式中只有一個(gè)活動(dòng)λ(t)，而事件日志與之相對(duì)應(yīng)的行為模式中有兩個(gè)滿足沖突關(guān)系的活動(dòng)BL×(l(e),l(e′))，其中l(wèi)(e)=λ(t)。這兩個(gè)模式可以合并為一個(gè)沖突關(guān)系的部分行為包含模式：BL?·×(BN*(λ(t),BL×(l(e),l(e′)))。Bl(e)表示事件日志中可觀測(cè)但過(guò)程模型中無(wú)法捕獲的單個(gè)活動(dòng)；Bλ(t)表示過(guò)程模型中使得事件日志無(wú)法回放的單個(gè)活動(dòng)。判定事件日志與過(guò)程模型之間的兩個(gè)活動(dòng)匹配需同時(shí)滿足標(biāo)簽與發(fā)生位置一致。

2 檢測(cè)偏差的完整信息

事件日志與過(guò)程模型在實(shí)際運(yùn)行中可能存在一些不被期望的差異，而其中對(duì)日志無(wú)法回放行為的處理則是模型修復(fù)需要解決的問(wèn)題。本章通過(guò)劃分事件日志與過(guò)程模型的可達(dá)活動(dòng)圖表獲得它們之間相對(duì)應(yīng)的行為模式，并由此產(chǎn)生最優(yōu)對(duì)齊來(lái)檢測(cè)偏差的完整信息[23]。

2.1 劃分可達(dá)活動(dòng)圖表

可達(dá)活動(dòng)圖表的劃分是在精煉過(guò)程樹的基礎(chǔ)上作的改進(jìn)，采用從整體到部分層層遞進(jìn)的搜索方法尋找事件日志與過(guò)程模型之間相對(duì)應(yīng)的片段[24-25]。根據(jù)給定約束條件在回放過(guò)程中所劃分的可達(dá)活動(dòng)圖表可以獲得事件日志與過(guò)程模型之間所有滿足活動(dòng)最短距離的可回放片段與不可回放片段(相同活動(dòng)的距離為“0”，反之則為“1”)[26]。

(2)entry(seq/conc/conf)(seq/conc/conf)exit(seq/conc/conf);

(3)|entry(seq/conc/conf)|=|exit(seq/conc/conf)|;

(6)pre(seq)>pre(conc,conf)。

根據(jù)劃分后的可達(dá)活動(dòng)圖表可獲得事件日志L與初始網(wǎng)系統(tǒng)N*之間滿足活動(dòng)最短距離的對(duì)應(yīng)片段，并記錄于表2。

表2 L與N*的片段

其中灰色陰影部分表示4對(duì)不可回放的片段，且第一組片段中包含若干個(gè)子片段。

2.2 確定偏差的發(fā)生、位置以及行為關(guān)系

最優(yōu)對(duì)齊是指事件日志與過(guò)程模型之間擁有最低成本的對(duì)齊，即cost(ξop)≤cost(ξ)，且?ξ∈ξ*，?ξop∈ξ*。為了更清楚地闡述如何構(gòu)建偏差子結(jié)構(gòu)，首先將圖1中劃分的所有對(duì)應(yīng)片段轉(zhuǎn)換為行為模式。并記錄于表3。

表3 L與N*的行為模式

通過(guò)行為關(guān)系的一致性校驗(yàn)，可回放的行為模式被直接合并為兩個(gè)對(duì)應(yīng)模式之間的一致行為，表4中不可回放的行為模式根據(jù)定義4中的規(guī)定以及相應(yīng)模式之間的差異行為進(jìn)行合并。

表4 L和N*之間的可回放與不可回放行為模式

由此可獲得事件日志與過(guò)程模型之間的兩組最優(yōu)對(duì)齊ξop1并記錄于表5。

表5 最優(yōu)對(duì)齊

表中背景顏色用來(lái)區(qū)分不同行為模式所產(chǎn)生的偏差，由于B?·×(BN*(C)/BL×(CBL?(DE)))可拆分為Bλ(t)(C)和BL?(DE)，將最優(yōu)對(duì)齊檢測(cè)出的偏差分為以下五組：{EsertC}、{EsertD/EsertE}、{EsertI,EsertJ}、{EsertK}、{EsertL,EsertM}、{SkipN}。根據(jù)偏差種類的不同，使用以下兩種方法分別確定它們的修復(fù)位置：①插入偏差的位置是由最優(yōu)對(duì)齊中產(chǎn)生該偏差的非同步移動(dòng)前最后一個(gè)同步移動(dòng)中的變遷在網(wǎng)系統(tǒng)N*上的后置庫(kù)所來(lái)確定的，記作loc(Esertl(e))=(σ(a′))·，λ((σ(a′)·)·)=a；②跳過(guò)偏差是將網(wǎng)系統(tǒng)N*上移動(dòng)變遷的前置庫(kù)所和后置庫(kù)所分別作為隱變遷τ的起始點(diǎn)和終止點(diǎn)，記作loc(Skipλ(t))=·(σ(a))∪(σ(a))·(σ是映射函數(shù)，將活動(dòng)標(biāo)簽轉(zhuǎn)換為網(wǎng)系統(tǒng)N*上的變遷)。根據(jù)不可回放行為模式的劃分，可從上述最優(yōu)對(duì)齊ξop中檢測(cè)到3組直接跟隨的偏差：并基于它們所對(duì)應(yīng)的不可回放行為模式判定每組偏差元素之間的行為關(guān)系分別為：序列、序列、并發(fā)。

通過(guò)確定可回放與不可回放的行為模式產(chǎn)生最優(yōu)對(duì)齊，且依靠行為關(guān)系的一致性校驗(yàn)檢測(cè)偏差元素的完整信息。由于事件日志與過(guò)程模型之間所有可回放的行為模式無(wú)需比較，僅搜索不可回放行為模式的最優(yōu)對(duì)齊。由于偏差的完整信息被看作是模型修復(fù)的輸入信息，這種方法能夠減少最優(yōu)對(duì)齊搜索的工作量且不影響模型修復(fù)的效率。

3 關(guān)于事件日志對(duì)過(guò)程模型所做的修復(fù)

本章介紹一種方法，該方法基于行為關(guān)系將事件日志與過(guò)程模型之間的直接跟隨偏差構(gòu)建為子結(jié)構(gòu)，從而通過(guò)減少單次發(fā)生的插入偏差個(gè)數(shù)來(lái)提升精度。根據(jù)各種不可回放行為模式所產(chǎn)生的不同偏差行為，可對(duì)其修復(fù)進(jìn)行具體的分析。

3.1 基于偏差子結(jié)構(gòu)的修復(fù)操作

通過(guò)構(gòu)建直接跟隨偏差的子結(jié)構(gòu)過(guò)程模型上的修復(fù)主要依賴于并發(fā)、序列、沖突3種行為關(guān)系。由于具有排他性的偏差元素之間不存在直接跟隨關(guān)系，可以將沖突結(jié)構(gòu)中每條分支上的偏差元素根據(jù)并發(fā)或序列關(guān)系構(gòu)建為子結(jié)構(gòu)，并分別以自循環(huán)的方式插入過(guò)程模型中合適的位置。各種不可回放行為模式中直接跟隨偏差所組合的子結(jié)構(gòu)類型可被概括為以下兩種：Nsl-E(l(e),l(e′))/NS(λ(t),λ(t))，Nsl-E(l(e),l(e′))+/NS(λ(t),λ(t′))+。圖2a和圖2b描述了上述兩種子結(jié)構(gòu)的具體操作，它們都是以自循環(huán)的方式插入到網(wǎng)系統(tǒng)N*中的。在實(shí)際修復(fù)過(guò)程中，如果一個(gè)不可回放行為模式中包含若干個(gè)子模式，則可能導(dǎo)致直接跟隨偏差的并發(fā)子結(jié)構(gòu)嵌套在序列子結(jié)構(gòu)中或者序列子結(jié)構(gòu)嵌套于并發(fā)子結(jié)構(gòu)中。如圖2c和圖2d所示，使用2.2節(jié)所介紹的方法對(duì)偏差完整信息進(jìn)行檢測(cè)，并將這兩種特殊的偏差子結(jié)構(gòu)記作：Nsl-E((l(e),l(e′))+,l(e″))/NS((λ(t),λ(t′))+，λ(t″))，Nsl-E((l(e),l(e′)),l(e″))+/NS((λ(t),λ(t′)),λ(t″))+。值得注意的，當(dāng)一個(gè)不可回放行為模式中包含的偏差或者子結(jié)構(gòu)都來(lái)自于過(guò)程模型時(shí)，即只會(huì)通過(guò)跳過(guò)偏差行為對(duì)該模式進(jìn)行修復(fù)，則修復(fù)后過(guò)程模型與事件日志之間的適合度能夠得到改善但對(duì)精度的提升沒(méi)有影響，如：B(×/+)/(×/)，BN*?(+,,×)，Bλ(t)。因此，由跳過(guò)偏差組成的子結(jié)構(gòu)不能對(duì)精度的提升產(chǎn)生幫助。

圖2中的方法可以將若干個(gè)偏差活動(dòng)構(gòu)建為一個(gè)子結(jié)構(gòu)，從而將所有直接跟隨的偏差活動(dòng)看作1個(gè)。事件日志與過(guò)程模型之間擬合度的度量公式為

其中:Ccost表示業(yè)務(wù)流程中的所有偏差成本，|L|+|ML|為事件日志的尺寸以及與它進(jìn)行最優(yōu)對(duì)齊的模型尺寸。本文方法以保證適合度為前提，因此統(tǒng)一使用自循環(huán)插入方式修復(fù)日志中的可觀測(cè)偏差。事件日志與過(guò)程模型之間精度的度量公式為

其中Ecost是指插入偏差的總成本。準(zhǔn)確修復(fù)表示偏差活動(dòng)在過(guò)程模型與事件日志中發(fā)生的形式完全一致，而使用自循環(huán)方式修復(fù)后每個(gè)單次插入偏差的回放準(zhǔn)確度為1/∞=0。因此，自循環(huán)插入方式只能修復(fù)迭代的插入偏差。將所有直接跟隨的單次發(fā)生偏差根據(jù)特定的行為關(guān)系構(gòu)建為子結(jié)構(gòu)，則可以通過(guò)減少事件日志的尺寸提升精度。例如，直接跟隨的n個(gè)單次發(fā)生偏差成本為Ecost′，將它們構(gòu)建為一個(gè)子結(jié)構(gòu)后精度為

值得注意的是，這種構(gòu)建子結(jié)構(gòu)的方式僅針對(duì)單次發(fā)生的插入偏差，而不適用于由日志中自循環(huán)產(chǎn)生的迭代插入偏差。迭代插入偏差需要使用自循環(huán)的方式單個(gè)插入過(guò)程模型，以確保正常的回放。

3.2 各種不可回放行為模式的修復(fù)

因?yàn)楸竟?jié)所提方法的修復(fù)目的是為了有效改善事件日志與過(guò)程模型之間的精度，所以主要介紹如何修復(fù)包含插入偏差的不可回放模式，即并發(fā)/因果模式并發(fā)/沖突模式。因果/沖突模式，以及事件日志的行為包含模式。

3.2.1 行為輪廓所產(chǎn)生差異的修復(fù)

行為輪廓主要指因果、并發(fā)、序列3種行為關(guān)系，本節(jié)對(duì)其中任意兩種行為之間產(chǎn)生的差異進(jìn)行修復(fù)。并發(fā)/因果模式是并發(fā)關(guān)系中的部分行為包含模式，它與并發(fā)/沖突模式分別表示事件日志與過(guò)程模型相對(duì)應(yīng)模式中活動(dòng)之間的行為關(guān)系為并發(fā)與因果或者并發(fā)與沖突。由于并發(fā)模式中活動(dòng)發(fā)生順序的任意性，對(duì)并發(fā)/因果模式和并發(fā)/沖突模式進(jìn)行修復(fù)首先需要通過(guò)最優(yōu)對(duì)齊檢測(cè)出偏差的完整信息，并將具有直接跟隨關(guān)系的偏差元素構(gòu)建為子結(jié)構(gòu)。因果/沖突模式是指兩個(gè)相對(duì)應(yīng)模式中活動(dòng)之間的行為關(guān)系分別為因果和沖突，它們所產(chǎn)生的偏差行為在沖突模式中包含活動(dòng)個(gè)數(shù)最小的一條分支上。對(duì)該模式進(jìn)行修復(fù)可將這條分支上所有偏差元素構(gòu)建為序列子結(jié)構(gòu)。假設(shè)圖3中初始網(wǎng)系統(tǒng)N*與事件日志L之間的對(duì)應(yīng)行為模式記錄于表6。

表6 可回放與不可回放行為模式

根據(jù)最優(yōu)對(duì)齊檢測(cè)出的偏差完整信息，圖3中采用構(gòu)建子結(jié)構(gòu)的方式對(duì)上述3種不可回放的行為模式進(jìn)行修復(fù)：①紅色虛線部分是對(duì)插入偏差進(jìn)行的修復(fù)，圖3中分別用藍(lán)色填充和橘色填充的庫(kù)所來(lái)標(biāo)注每個(gè)插入偏差/偏差子結(jié)構(gòu)在過(guò)程模型上的位置以及子結(jié)構(gòu)中的連接庫(kù)所；②紫色虛線部分是對(duì)跳過(guò)偏差的修復(fù)，其中綠色填充的庫(kù)所用來(lái)表示插入偏差與跳過(guò)偏差的共同位置。修復(fù)并發(fā)/因果模式中產(chǎn)生的直接跟隨跳過(guò)偏差{D,E}不會(huì)對(duì)精度造成影響，這里根據(jù)行為關(guān)系將它們構(gòu)建為子結(jié)構(gòu)只能在一定程度上降低修復(fù)后過(guò)程模型的復(fù)雜度[27]。如圖3所示，并發(fā)/因果模式與并發(fā)/沖突模式產(chǎn)生的差異既包括單個(gè)偏差活動(dòng)也包括偏差子結(jié)構(gòu)，而因果/沖突模式的差異則只有序列子結(jié)構(gòu)。由于同一個(gè)位置的相同偏差重復(fù)出現(xiàn)多次成本仍然為1，因此從提升精度的角度考慮，可將Esert(l(e))∪{Esert(l(e)),Esert(l(e′))}={Esert(l(e)),Esert(l(e′))}看作是Esert(l(e))∪NE(l(e),l(e′))。圖3基于三組直接跟隨偏差之間的序列關(guān)系構(gòu)建偏差子結(jié)構(gòu)進(jìn)行修復(fù)，即：Nsl-E(D,E)、Nsl-E(F,G)、Nsl-E(M,N)。

3.2.2 行為包含模式的修復(fù)

事件日志的行為包含模式是指在當(dāng)前模式中過(guò)程模型可以捕獲的行為都被記錄于事件日志中，但事件日志中可觀測(cè)的行為則不能完全在過(guò)程模型中被捕獲[28]。根據(jù)定義4中行為包含模式的各種類型，假設(shè)圖4中初始網(wǎng)系統(tǒng)N*與事件日志L之間的對(duì)應(yīng)行為模式被記錄于表7。

表7 可回放與不可回放行為模式

根據(jù)最優(yōu)對(duì)齊檢測(cè)出的偏差完整信息，圖4使用紅色虛線和紫色虛線分別描述了對(duì)插入偏差和跳過(guò)偏差的修復(fù)。BL?·×(BN*(B)BL×(BBL?(CD))) 的修復(fù)可被看作是Bλ(t)(B)和BL?(CD)兩個(gè)模式，它所產(chǎn)生的偏差分別為：Skip(B)，{Esert(C),Esert(D)}兩部分。其他3個(gè)事件日志的整體行為包含模式中只包含插入偏差，且它們的修復(fù)操作是根據(jù)當(dāng)前模式中包含的所有偏差及偏差之間的行為關(guān)系所構(gòu)建的。因此，圖4根據(jù)4組直接跟隨偏差之間的行為關(guān)系構(gòu)建偏差子結(jié)構(gòu)對(duì)過(guò)程模型進(jìn)行修復(fù)，即Nsl-E(C,D)，Nsl-E(G,H)+，Nsl-E(J,K)，Nsl-E(L,M,N)。這里，偏差{J,K}是整體沖突行為包含模式中一條分支上的活動(dòng)，它與另一條分支上的偏差活動(dòng){I}之間具有排他性，因此將{J,K}與{I}分別插入過(guò)程模型的同一個(gè)位置。

算法1描述了各種不適合行為模式的修復(fù)操作，首先將空集賦予修復(fù)操作的集合Ro，然后主要對(duì)以下2部分進(jìn)行分析：

(1)行為輪廓所產(chǎn)生差異的修復(fù)操作主要分為以下3種情況：①并發(fā)/因果模式。當(dāng)該模式中的活動(dòng)總數(shù)不超過(guò)3時(shí)，修復(fù)操作插入并且跳過(guò)后一個(gè)活動(dòng)；反之，其操作是插入并且跳過(guò)后半條分支上所有活動(dòng)的子結(jié)構(gòu)(第5～第7行)。②并發(fā)/沖突模式，這種模式的修復(fù)操作類似于并發(fā)/因果，但它沒(méi)有跳過(guò)偏差，且插入的活動(dòng)或者子結(jié)構(gòu)來(lái)自于兩條分支中的任意一條(第8-10行)。③因果/沖突模式。該模式的修復(fù)操作僅將包含活動(dòng)個(gè)數(shù)少的一條分支上的偏差行為插入過(guò)程模型，其可能是單個(gè)活動(dòng)或者子結(jié)構(gòu)(第11～第13行)。

(2)因果、沖突、并發(fā)關(guān)系所產(chǎn)生的整體行為包含模式的修復(fù)操作，以及沖突模式中部分行為包含的修復(fù)操作。整體行為包含可根據(jù)偏差之間的行為關(guān)系構(gòu)建該模式中所有偏差元素的子結(jié)構(gòu)(第14～第16行)。事件日志的沖突行為部分包含模式需要分別插入和跳過(guò)它與過(guò)程模型之間不相交以及相交行為中的單個(gè)活動(dòng)或者直接跟隨偏差的子結(jié)構(gòu)(第17～19行)。

算法 1基于偏差于結(jié)構(gòu)的修復(fù)操作。

輸出: RO。

1: RO←?

2: for each ei∈L do

3: for each tj∈T do

4: for each ak∈∪do

5: if l(ei)=λ(tj)=ak∧BL+((a1,a2)/((a1,…,an),(an+1，…，an+m)L))∧BN*((a1,a2)/(a1,…,an),(an+1,…,an+m)L)) then

6: RO←(SEsert(a1)∪Skip(a1))/(Nsl-E(an+1,…,an+m)∪SEsert(an+1,…,an+m)∪NS(an+1,…,an+m))

7: end

8: if l(ei)=λ(tj)=ak∧BL+/×((a1,a2)/((a1,…,an),(an+1,…,an+m)))∧BN*×/+((a1,a2)/((an+1,…,an+m))) then

9: RO←(SEsert(a1,a2))/(Nsl-E(a1,…,an)/(an+1,…,an+m)∪SEsert(a1,…,an,an+1,…,an+m)))/((skip(a1)∪skip(a2))/Ns(a1,…,an)/(an+1,…,an+m))

10: end

11: if l(ei)=λ(tj)=ak∧ B((a1,a2)/((a1,…,an),((an+1,…,an+m))) ∧BN*×/((a1,a2)/((a1,…,an),(an+1,…,an+m))) then

12: RO←(SEsert(a1/a2)/Nsl-E((a1,…,an)/(an+1,…,an+m)))/(skip(a1/a2)/NS((a1,…,an)/(an+1,…,an+m)))

13: end

14: if l(ei)=λ(tj)=ak∧B((a1,a2)/((a1,…,an),(an+1,…,an+m)))∈R(L/N*) then

15: RO←Nsl-E((a1,a2)/((a1,…,an),(an+1,…an+m)))+//×/

Ns((a1,a2)/((a1,…,an),(an+1,…,an+m)))+//×

16: end

18: R0←(SEsert(a2)∪Skip(a1))/(Nsl-E(an+1,…,an+m)∪NS(a1,…an))

19: end

20: end

21: end

22： end

23: return RO

4 評(píng)估

本章記錄了本文方法與當(dāng)前兩種方法之間修復(fù)性能的比較結(jié)果[13]。本文方法在實(shí)驗(yàn)中主要根據(jù)行為關(guān)系將直接跟隨偏差元素構(gòu)建為子結(jié)構(gòu)，并使用自循環(huán)插入的方式進(jìn)行修復(fù)。

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 工具集

當(dāng)前，模型修復(fù)可以使用Prom框架進(jìn)行驗(yàn)證，但其原始代碼并沒(méi)有提供本文方法中的改進(jìn)部分。為保證實(shí)驗(yàn)結(jié)果的公平性，本文在此基礎(chǔ)上使用Java語(yǔ)言編寫了插件M-repair，其可以根據(jù)不同方法的性能分別校驗(yàn)修復(fù)后數(shù)據(jù)集的適合度與精度。實(shí)驗(yàn)使用Java語(yǔ)言編寫類似于CPN Tools功能的插件PSLG，其利用活動(dòng)的隨機(jī)觸發(fā)性自動(dòng)生成常見(jiàn)格式或xes格式的事件日志。

4.1.2 數(shù)據(jù)集

實(shí)驗(yàn)使用4個(gè)數(shù)據(jù)集進(jìn)行評(píng)估，它們分別來(lái)自人造業(yè)務(wù)流程和真實(shí)業(yè)務(wù)流程。因?yàn)槊總€(gè)業(yè)務(wù)流程中都包含一個(gè)無(wú)循環(huán)結(jié)構(gòu)的數(shù)據(jù)集和一個(gè)有循環(huán)結(jié)構(gòu)的數(shù)據(jù)集，所以分別記作：Da，Dla，Dr，Dlr，其中真實(shí)業(yè)務(wù)流程來(lái)自于中國(guó)一家人壽保險(xiǎn)公司的投保流程。通過(guò)模擬4個(gè)業(yè)務(wù)流程的發(fā)生實(shí)例分別獲得與它們一致的4個(gè)序列集δ*，并將數(shù)據(jù)集中存在的不可回放片段化分為以下3種：①并發(fā)因果沖突行為以及單個(gè)活動(dòng)插入/跳過(guò)產(chǎn)生的不一致行為；②行為包含產(chǎn)生的不一致行為；③循環(huán)路徑產(chǎn)生的不行為。為了指導(dǎo)實(shí)驗(yàn)的正常進(jìn)行可根據(jù)上述3種情況下的不適合行為模式對(duì)發(fā)生序列進(jìn)行更改，產(chǎn)生與業(yè)務(wù)流程不一致的執(zhí)行序列集σ*，每個(gè)執(zhí)行序列集與其對(duì)應(yīng)的發(fā)生序列集組成一個(gè)數(shù)據(jù)集。根據(jù)執(zhí)行序列集σ*中包含的所有活動(dòng)及其之間的行為構(gòu)建過(guò)程模型，并使用PSLG插件將其自動(dòng)生成為事件日志。因?yàn)镻SLG插件所生成的事件日志包含500多條不同案例的跡，所以選擇可以反映所有活動(dòng)及其之間行為關(guān)系的10條不同案例的跡，并在每條跡的發(fā)生次數(shù)之上模擬20次。4個(gè)數(shù)據(jù)集中的事件日志包含200～360條跡，且它們的尺寸分別為L(zhǎng)*={5 920,5 860,6 160,8 880}。

4.2 適合度確定為1的實(shí)驗(yàn)評(píng)估

為保證適合度在修復(fù)后始終能夠達(dá)到1，本節(jié)使用的現(xiàn)存修復(fù)方式與所提方法都是以自循環(huán)的方式修復(fù)插入偏差。兩種方法在適合度與精度上的度量可參照表8中記錄的公式，且它們之間精度的差異來(lái)自于構(gòu)建偏差子結(jié)構(gòu)對(duì)日志尺寸的減少。

表8 修復(fù)性能的度量公式

4.2.1 在含有迭代插入偏差數(shù)據(jù)集上的評(píng)估

圖5a和圖5b中分別描述了來(lái)自真實(shí)業(yè)務(wù)流程數(shù)據(jù)集的精度值比較，其中非循環(huán)部分都存在差異。圖5a中的數(shù)據(jù)集沒(méi)有來(lái)自于循環(huán)部分的差異，兩種方法在精度上的提升僅依靠于對(duì)迭代可觀測(cè)偏差的準(zhǔn)確修復(fù)(迭代可觀測(cè)偏差產(chǎn)生于事件日志中的自循環(huán)路徑)。圖5b的數(shù)據(jù)集中事件日志的一個(gè)模式有循環(huán)路徑，而過(guò)程模型中與之相對(duì)應(yīng)的模式則沒(méi)有。由于該循環(huán)部分的不可回放模式同時(shí)由它們的非循環(huán)部分和返回路徑所產(chǎn)生，它們統(tǒng)一按照非循環(huán)部分的方法進(jìn)行修復(fù)。由此可知，兩種方法在循環(huán)部分與非循環(huán)部分上就精度改善而言的差異是一樣的。圖5c和圖5d中分別描述了來(lái)自人造業(yè)務(wù)流程數(shù)據(jù)集的精度值比較，其中非循環(huán)部分都存在差異。圖5c只在非循環(huán)部分產(chǎn)生差異，因此兩種方法對(duì)精度的改善與圖5a一樣。圖5d的數(shù)據(jù)集中事件日志的一個(gè)模式有循環(huán)路徑。由于該循環(huán)部分的不可回放模式僅由事件日志中包含的循環(huán)路徑所產(chǎn)生，返回路徑上沒(méi)有活動(dòng)，使用本文所提出的方法和現(xiàn)存方法都可以準(zhǔn)確地修復(fù)由它產(chǎn)生的偏差。從圖中4組數(shù)據(jù)可以看出，相較于現(xiàn)存方法而言，本文方法可以在保證適合度的基礎(chǔ)上平均提升精度約13%，其中P與M-p分別表示現(xiàn)存方法與本文方法所產(chǎn)生的精度值。

4.2.2 在不含有迭代插入偏差數(shù)據(jù)集上的評(píng)估

圖6中的4個(gè)數(shù)據(jù)集是在圖5所使用的數(shù)據(jù)集基礎(chǔ)上進(jìn)行的改進(jìn)，即其中4個(gè)事件日志都不包含迭代可觀測(cè)偏差。由于僅使用自循環(huán)方式插入可觀測(cè)偏差無(wú)法提升精度，現(xiàn)存方法在圖6a～圖6c中都始終保持初始的值。圖6d中現(xiàn)存方法的精度值增長(zhǎng)依賴于循環(huán)所引起的重復(fù)活動(dòng)。本文方法在圖6a～圖6c中的精度增長(zhǎng)點(diǎn)都依賴于將該模式中直接跟隨插入偏差構(gòu)建為子結(jié)構(gòu)的修復(fù)，而圖6d中的精度增長(zhǎng)還有循環(huán)所產(chǎn)生偏差的修復(fù)。

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

本文提出一種新的有效方法來(lái)修復(fù)事件日志無(wú)法回放于過(guò)程模型的行為，該方法主要解決了當(dāng)前模型修復(fù)方法在精度問(wèn)題上的局限性。首先，在給定約束條件下劃分事件日志與過(guò)程模型的可達(dá)活動(dòng)圖表，并由此產(chǎn)生它們之間的對(duì)應(yīng)行為模式；然后，通過(guò)行為關(guān)系的一致性校驗(yàn)將對(duì)應(yīng)行為模式合并為可回放與不可回放的模式并產(chǎn)生最優(yōu)對(duì)齊。根據(jù)這種最優(yōu)對(duì)齊所檢測(cè)出的偏差行為關(guān)系將所有直接跟隨的偏差元素構(gòu)建為子結(jié)構(gòu)；最終，采用自循環(huán)插入/跳過(guò)式的方法對(duì)偏差元素/偏差子結(jié)構(gòu)進(jìn)行修復(fù)。本文所提方法能夠通過(guò)減少日志所產(chǎn)生的插入偏差，實(shí)現(xiàn)在保證適合度的前提下盡可能的提升精度。

本文方法是針對(duì)靜態(tài)過(guò)程模型進(jìn)行的實(shí)時(shí)修復(fù)，并沒(méi)有考慮當(dāng)需求與環(huán)境不斷變化時(shí)過(guò)程模型在實(shí)際運(yùn)行中可能產(chǎn)生的額外行為。未來(lái)工作將分析這種修復(fù)方式如何解決動(dòng)態(tài)過(guò)程模型與事件日志之間的修復(fù)問(wèn)題。