基于對齊的BPMN 2.0模型符合性檢測算法

汪玉泉 聞立杰 閆志強

1(清華大學軟件學院 北京 100084)2 (首都經(jīng)濟貿(mào)易大學信息學院 北京 100070)

基于對齊的BPMN 2.0模型符合性檢測算法

汪玉泉1聞立杰1閆志強2

1(清華大學軟件學院 北京 100084)2(首都經(jīng)濟貿(mào)易大學信息學院 北京 100070)

(272269222@qq.com)

符合性檢測方法作為比較和關聯(lián)事件日志與流程模型的技術，是三大核心流程挖掘技術之一，可用于量化符合性和診斷偏差.BPMN 2.0模型具有豐富的表達能力，能夠表達多實例、子流程、邊界事件、OR網(wǎng)關等多種復雜模式，但是目前還沒有針對這些復雜模式的BPMN 2.0模型符合性檢測算法.針對該問題，提出了基于對齊的BPMN 2.0模型符合性檢測算法Acorn，該算法支持上述多種復雜模式.在深入分析BPMN 2.0模型中多種復雜模式的具體語義并分析其具體使能情況的基礎上，Acorn算法引入對齊操作，利用A*搜索算法尋找到代價最小的匹配軌跡，同時引入虛擬代價和預估代價來對A*算法進行搜索空間的優(yōu)化，最后根據(jù)最佳匹配軌跡來計算模型與日志的契合度.實驗表明，Acorn算法能夠正確有效地計算帶有復雜模式的BPMN 2.0模型與日志之間的契合度，且虛擬代價和預估代價的引入，大大減少了搜索空間，有效提高了算法的運行速度.

BPMN 2.0模型；復雜模式；A*搜索；符合性檢測；對齊

工作流技術在最近十幾年得到了迅速的發(fā)展，該技術通過對日常工作中固定程序活動進行抽象，將工作分解成定義良好的任務或者角色工作，按照一定的規(guī)則和流程來執(zhí)行這些任務并對其進行監(jiān)控，達到提高工作效率、更好地控制流程、增強對客戶的服務、有效管理業(yè)務流程等目的[1].

BPMN(business process model and notation)[2]是由BPMI(Business Process Management Initiative)開發(fā)的一套標準的業(yè)務流程建模符號.BPMN 2.0規(guī)范于2011年正式發(fā)布，相比于2004年提出的BPMN 1.0規(guī)范有了巨大的改進，多實例、子流程、邊界事件等多種元素的引入，極大地豐富了BPMN 2.0模型的表達能力.BPMN 2.0模型符號容易被業(yè)務分析員理解和使用，現(xiàn)已成為當前最流行的業(yè)務流程可視化描述語言.

符合性檢測是工作流技術中非常重要的模塊.符合性檢測是用來檢測流程模型和日志之間匹配程度的技術，即該模型能在多大程度上反映出該日志相關流程執(zhí)行過程的本質(zhì).通常企業(yè)在初始階段沒有進行系統(tǒng)地建模，但在其系統(tǒng)中仍記錄了大量的活動執(zhí)行過程.在企業(yè)規(guī)模逐漸擴大、業(yè)務逐漸復雜之后，企業(yè)通常通過一些自動挖掘技術，在大量實際日志的基礎上挖掘出工作流模型來更好地管理業(yè)務[3-5]，從而提高工作效率，但我們往往需要符合性檢測來衡量挖掘出來的模型的質(zhì)量.此外，當流程模型執(zhí)行產(chǎn)生的流程日志與原始模型偏差較大，即二者的符合性低于給定閾值時，有必要對原始模型進行修復操作[6].

然而目前的符合性檢測技術大都集中在Petri網(wǎng)[7]上，很少有針對BPMN模型的符合性檢測，即便有也是只考慮了BPMN模型中的活動和網(wǎng)關[8]，并沒有考慮到BPMN 2.0標準中的多實例、子流程、邊界事件等特殊元素的存在和影響.多實例、子流程和邊界事件等復雜模式的存在，大大增加了符合性檢測算法的設計難度.

BPMN 2.0模型的符合性檢測算法具有如下3個難點：

1) 多實例、子流程的存在，使得模型可以對應無窮多個實例軌跡，直接計算匹配程度較為困難；

2) OR網(wǎng)關的不對稱存在，使得OR網(wǎng)關的使能情況異常復雜；

3) 邊界事件和多實例的存在，使得多種事件可以同時使能，但相互之間是沖突的，需要根據(jù)具體情況進行分析.

本文致力于在考慮BPMN 2.0標準中的多實例、子流程、邊界事件等特殊元素的基礎上，研究BPMN 2.0模型和已有日志的符合性檢測工作，主要貢獻如下：

1) 針對多實例、子流程、邊界事件等每種特殊元素，進行其語義分析；

2) 設計對齊算法，尋找BPMN 2.0模型上可執(zhí)行的1條軌跡，使其轉(zhuǎn)換成已有軌跡所需的代價最小；

3) 提出Acorn算法，用于衡量BPMN 2.0模型和日志之間的契合度.

1 相關工作

符合性檢測主要用于檢測模型能在多大程度上來描述已有日志的行為，目前比較公認的流程模型和日志之間符合性檢測的衡量指標主要有4種：

1) 契合度(fitness).用于衡量有多少日志中的行為被模型所支持.

2) 準確率(precision).用于衡量有多少模型上的行為被日志所支持.

3) 一般性(generalization).用于衡量模型解析日志之外行為的能力，如用90%的日志挖掘出來的模型，能很好地解析剩下的10%的日志行為，就可以說該模型具有良好的一般性.

4) 復雜性(complexity).用于衡量模型的復雜程度，通常而言，在有同樣的表達能力的前提下，用戶往往希望模型是簡單易懂的.

把同時出現(xiàn)在模型和日志中的行為稱為“TruePositive”，出現(xiàn)在模型中但不出現(xiàn)在日志中的行為稱為“FalsePositive”，反之只出現(xiàn)在日志中但不出現(xiàn)在模型中的行為稱為“FalseNegative”，通常：

(1)

(2)

Molka等人[8]針對BPMN模型提出了計算召回率和準確率的符合性檢測算法.該文定義了“局部行為”和“全局行為”，并設計算法在模型和日志中抽取這2種行為，從而進一步計算召回率和準確率.然而該算法針對的BPMN模型仍停留在BPMN 1.0時代，并未包含BPMN 2.0模型中的多實例、子流程、邊界事件等各種特殊元素，故應用場景比較有限.

Adriansyah等人[9]提出了若干個關于契合度方面的衡量指標，針對每條軌跡t1，作者通過A*算法尋找到模型上的最優(yōu)的1條軌跡t2，且要保證t2是t1的子集，由此可以計算出軌跡t1中不能被模型解析的部分，從而進一步來計算契合度指標.

de Leoni等人[10]針對聲明式(declarative)模型[11]提出基于對齊的符合性檢測算法.基于對齊的算法假設模型和日志都可以保持自身不變，等待對方強制執(zhí)行某流程，從而越過不匹配的活動，同時記錄不匹配活動的代價，通過A*搜索算法來尋找到代價最小的1條對齊軌跡.然而，聲明式模型與BPMN 2.0模型存在顯式差別，且未見BPMN 2.0模型到聲明式模型的轉(zhuǎn)換工作.因此，本文無法直接使用文獻[10]的研究成果.

vanden Broucke等人[12]通過引入負事件(nega-tive event)，從全新的角度來衡量模型與日志之間的準確度和模型的一般性.通過對日志的全局分析，即可計算出每條軌跡中每個活動對應的負事件.隨后讓每條軌跡在模型上一步步執(zhí)行，每執(zhí)行1步即可得到該步之后有哪些使能的活動屬于負事件或者正事件(positive event)，并將相應的結(jié)果計算入最終的準確度和一般性結(jié)果中.但由于該方法在某活動不能在模型上執(zhí)行的情況下采取的是強制執(zhí)行的方法，適合于大部分模型，但卻不適合BPMN 2.0模型，因為BPMN 2.0模型中包含多實例的活動和子流程，若某活動或子流程需要被強制執(zhí)行，但是它被標記為多實例，即有多個活動或子流程實例，那么強制執(zhí)行哪個實例仍是未知的問題，強制執(zhí)行不同的實例會導致不同的計算結(jié)果.

契合度是4個指標最為重要的衡量指標.由于負事件的應用在BPMN 2.0模型中有上述局限性，故本文主要關注BPMN 2.0與日志之間契合度的衡量.與文獻[10]中的方法相似，本文通過對BPMN 2.0模型的深入理解，設計基于對齊的算法，通過A*算法尋找到代價最小的匹配軌跡，進一步計算契合度.

2 Acorn算法設計

2.1 BPMN 2.0模型元素含義

BPMN 2.0定義了規(guī)范的執(zhí)行語義和格式，利用標準的圖元來描述現(xiàn)實的流程，從而保證即便在不同的流程引擎下得到的執(zhí)行結(jié)果也是一樣的.其模型定義如下：

定義1. BPMN 2.0模型.BPMN 2.0模型為一個四元組M=(A,G,E,S)，其中：A表示“Activity”，表示在流程圖中具備聲明周期狀態(tài)的元素，包含原子級的任務(task)和子流程(sub-process)；G表示“Gateway”，主要包含XOR網(wǎng)關、OR網(wǎng)關和AND網(wǎng)關；E表示“Event”，利用事件機制，為系統(tǒng)增加輔助功能，主要包含啟動(start event)、結(jié)束(end event)和中間事件(intermediate event)等；S表示“Sequence”，主要為流向(sequence flow).

BPMN 2.0規(guī)范支持的元素異常之多，表1列舉了本文算法中支持的各種BPMN 2.0元素及該元素的執(zhí)行語義.

2.2 BPMN 2.0模型元素使能分析

對于任務來說，只要有輸入流到達，則該任務就是使能的，然而BPMN 2.0模型中包含了很多特殊元素，需要逐一考慮.

1) XOR網(wǎng)關.XOR網(wǎng)關分為2種，即XOR-SPLIT網(wǎng)關和XOR-MERGE網(wǎng)關.XOR-SPLIT表示選擇開始，XOR-MERGE表示選擇結(jié)束.根據(jù)表1中的語義，XOR網(wǎng)關表示只有1條分支能夠執(zhí)行，故遇到XOR-SPLIT網(wǎng)關，假設其有n條流出的序列流，則可以產(chǎn)生n種不同的使能狀態(tài)，每條分支為1種狀態(tài).遇到XOR-MERGE則直接使能該網(wǎng)關，因為任意1條輸入的序列流都可以使能該網(wǎng)關.

2) AND網(wǎng)關.AND網(wǎng)關分為2種，即AND-SPLIT網(wǎng)關和AND-MERGE網(wǎng)關.AND-SPLIT網(wǎng)關表示并發(fā)的開始，則其輸出序列流對應的活動都應該使能；AND-MERGE網(wǎng)關則表示并發(fā)的結(jié)束，需要所有分支都已經(jīng)執(zhí)行完，故對每個AND-MERGE網(wǎng)關，需要記錄該網(wǎng)關哪些流入的序列流已經(jīng)使能.

Table 1 BPMN 2.0 Elements and Their Execution Semantics

3) OR網(wǎng)關.OR網(wǎng)關同樣分為OR-SPLIT網(wǎng)關和OR-MERGE網(wǎng)關.根據(jù)表1的語義，OR-SPLIT后可以有若干個(至少1個)分支被使能，假設該網(wǎng)關有n個流出向的序列流，則有2n-1種對應的使能狀態(tài)；OR-MERGE則相對來說復雜一些，并不像XOR-MERGE和AND-MERGE那樣有規(guī)則，而是需要根據(jù)前面OR-SPLIT的情況來定.圖1展示了2種不同的OR-MERGE情況，圖1(a)展示了一種規(guī)則的情況，即OR-MERGE網(wǎng)關與OR-SPLIT一一對應;而圖1(b)則展示了一種不規(guī)則的情況，即可以有n個OR-MERGE和m個OR-SPLIT對應.鑒于有存在圖1(b)展示的情況，判斷OR-MERGE是否使能顯得有些復雜.需要按照以下步驟來進行：

Fig.1 A sample for OR-SPLIT圖1 OR-SPLIT示例

① 預處理BPMN 2.0模型中每個元素能到達的OR-MERGE網(wǎng)關，本文用R(x)表示x元素能夠到達的OR-MERGE網(wǎng)關，在圖1(b)中，任務A和B能夠到達的OR-MERGE為o2和o4，即R(A)=R(B)={o2,o4}，C和D能夠到達的OR-MERGE為o3和o4，即R(C)=R(D)={o3,o4}.

② 每使能1個任務，則更新該任務能夠到達的OR-MERGE網(wǎng)關，表明該活動使能，則這些OR-MERGE網(wǎng)關需要等到這個任務執(zhí)行完后才能使能，即每使能任務x，需要更新?o∈R(x),o.waitingList.add(x)，其中waitingList為2.3節(jié)中間狀態(tài)的變量之一，表示該OR-MERGE網(wǎng)關需要等待的任務集合.在圖1(b)中，若o1網(wǎng)關后使能的是A和D，則更新o2，o4需要等待A的執(zhí)行，更新o3，o4需要等待D的執(zhí)行，即o2.waitingList={A},o3.waitingList={D},o4.waitingList={A,D}.

③ 每執(zhí)行完1個任務，則更新該任務對應的所有OR-MERGE網(wǎng)關，告訴該網(wǎng)關不必繼續(xù)等待該任務，即每執(zhí)行任務x，需要更新?o∈R(x),o.waitingList.remove(x)，其中waitingList表示該OR-MERGE網(wǎng)關需要等待的任務集合.圖1(b)中，任務A執(zhí)行后，則o2，o4進行更新，更新之后o2不必再等待任何活動，而o4還需要等待任務D的執(zhí)行，即o2.waitingList={},o4.waitingList={D}.

④ 當訪問到OR-MERGE網(wǎng)關時，若該網(wǎng)關不需要等待任何任務，則該網(wǎng)關使能，即若該OR-MERGE網(wǎng)關的waitingList為空，則該網(wǎng)關使能，反之則不使能.圖1(b)中，續(xù)上面的例子，任務A執(zhí)行后，o2.waitingList={}，即o2不需要等待任何任務，則使能，而o3，o4都需要等待D的執(zhí)行，則不使能.

4) 子流程.每次使能1個子流程，則使能該子流程中的開始事件.每次執(zhí)行完子流程中的結(jié)束事件后，則跳出該子流程.

5) 多實例.多實例表明該任務或者子流程可以發(fā)生多次，故需要用實例編號來區(qū)分各個實例.當某個任務體現(xiàn)出多實例的特性時，第1個實例給予編號“_1”，第2個實例給予編號“_2”，若有多層的多實例，如子流程被標記為多實例，且其中的任務也被標記為多實例，則可以采用“_1_1”，“_1_2”的形式來進行區(qū)分，當多實例結(jié)束時，則修改成上層的實例編號.本文默認，存儲在優(yōu)先隊列中的任務都帶有實例編號.

6) 邊界事件.包括取消事件、定時事件和錯誤事件.這3種事件的語義表現(xiàn)基本一致，只是產(chǎn)生事件的原因不同.若任務或者子流程包含這些事件，則這些事件對應的分支隨時是使能的.

2.3 基于對齊的匹配算法

定義3. 日志.日志L={T1,T2,…,Ti,…,Tn}，其中Ti表示第i條軌跡.

基于對齊的模型與日志匹配算法，其本質(zhì)是在模型上逐條重演相應日志的軌跡，即模型中任務依據(jù)規(guī)則逐個執(zhí)行的同時，軌跡中對應任務進行逐個遍歷輸出.往往1條軌跡中的所有任務不能完美地在模型上按照次序重演下來，故需要引入對齊的概念.引入“?”標識符，表示用來對齊，并不執(zhí)行真正的具體任務.

定義4. 對齊.假定s′為模型中依據(jù)規(guī)則執(zhí)行的當前任務，s″為軌跡中按序遍歷輸出的當前任務，則(s′,s″)是模型和軌跡的1次對齊，其中：

1) 若s′為模型中的任務而s″=?，則該對齊僅為模型中s′的執(zhí)行，而軌跡未動；

2) 若s′=?而s″為軌跡中的任務，則該對齊僅為軌跡中s″的輸出，而模型未動；

3) 若s′=s″≠?，則該對齊表示模型中s′執(zhí)行的同時，對軌跡中s″進行輸出.

例1. 圖2表示已有的BPMN2.0模型，整個流程先執(zhí)行A任務，之后D任務和1個子流程并發(fā)執(zhí)行，該子流程在執(zhí)行若干個B任務實例后執(zhí)行C任務，該子流程可以同時產(chǎn)生多個實例，待并發(fā)結(jié)束后，最后執(zhí)行E任務.現(xiàn)在已有軌跡t=A,C,E，需要通過重演在模型上找1條匹配軌跡.圖3展示了4種軌跡在模型上重演的對齊方案.

Fig. 2 A sample for BPMN 2.0 model圖2 BPMN 2.0模型示例

Fig. 3 Several alignments between the trace and the model in example 1圖3 例1軌跡與模型的若干種對齊方案

軌跡在模型上重演，可以產(chǎn)生非常多的對齊方案.需要找到和軌跡最為相似的那種重演方式，很明顯，Y1是需要的那種對齊方式，因為Y1中只引入了2次“?”，只有任務B和D沒有找到相匹配的，任務A，C，E均完成了匹配.

定義下面的代價函數(shù)，可以用來評估對齊方案Y的好壞，其中單個對齊代價的具體值用戶可以自定義：

(3)

由該代價函數(shù)易知，Y1的對齊方案的代價為2，Y3的對齊方案的代價為3，而Y2和Y4的對齊方案的代價為4，故Y1是最優(yōu)的對齊方案.基于對齊的軌跡與模型的匹配方案，即尋找代價最小的對齊方案.

存在子流程可能會被標記成多實例的情況，每次使能1個子流程的實例，都只是簡單地啟動該子流程的開始事件，而事件這種元素并不會記錄在最終的日志中，故事件不會累計在最終的代價里.如此一來，就會產(chǎn)生一個問題，隊列是按照代價大小排序的，而子流程可能產(chǎn)生無數(shù)個實例且代價不變(假設每個實例都只是啟動開始事件)，將會導致算法陷入死循環(huán)，故在此引入真實代價和虛擬代價的概念.

真實代價是引入對齊符號“?”所產(chǎn)生的代價，即模型和軌跡某個活動沒有匹配上產(chǎn)生的代價；而虛擬代價是啟動子流程實例產(chǎn)生的代價，每次啟動1個子流程的開始事件，標記1次虛擬代價，即虛擬代價總和加1.

Fig.4 The core idea of finding the optimal alignment for example 1 using A* search algorithm圖4 例1使用A*搜索算法尋找最佳匹配示意

本文采用A*搜索算法來尋找基于對齊的最佳匹配，整體思路是通過優(yōu)先隊列，維護一系列的匹配中間狀態(tài)，每次挑選最小代價的中間狀態(tài)，在其基礎上繼續(xù)重演，直到找到總體代價最小的匹配.優(yōu)先隊列維護的中間狀態(tài)如定義5所示.

定義5. 中間狀態(tài).優(yōu)先隊列中維護著一系列的匹配中間狀態(tài)，每個狀態(tài)包括多個中間變量：

1)currentAvailable，類型為HashSetTask，記錄目前所有已經(jīng)使能的任務.

2)parallelSync，類型為HashMapTask,HashSetSequenceFlow，鍵為AND-MERGE網(wǎng)關，值為該網(wǎng)關流入的序列流，用來標記哪些入口已經(jīng)使能，當所有入口均已使能，則該AND-MERGE網(wǎng)關使能.

3)waitingList，類型為HashMapTask,HashSetTask，鍵為OR-MERGE網(wǎng)關，值為該網(wǎng)關需要等待執(zhí)行的任務，當該網(wǎng)關需要等待的任務數(shù)為0時，該OR-MERGE網(wǎng)關使能.

4)modelTrace，類型為ListString，記錄模型上的軌跡，包括任務名字和對齊標志“?”.

5)traceToMatch，類型為ListString，記錄還需等待匹配的軌跡.

6)cost，分為totalCost，realCost，virtualCost和expectedCost，每種類型均為Int.totalCost為后面3種代價之和，優(yōu)先隊列中按totalCost從小到大排序；realCost記錄當前狀態(tài)下的真實代價，每增加1個對齊標志“?”，代價加1；virtualCost為引入子流程開始事件的代價；expectedCost為當前狀態(tài)到匹配結(jié)束狀態(tài)的估算代價，在2.4節(jié)會具體介紹.

圖4展示了例1中A*搜索算法的具體執(zhí)行過程，最初始有一個狀態(tài)如節(jié)點1所示，節(jié)點1表示當前狀態(tài)下模型上只有A是使能的，模型上的執(zhí)行軌跡暫為空，待匹配的軌跡為A,C,E，代價為0，隨后狀態(tài)2，3，4則是根據(jù)上述規(guī)則所衍生出的下一系列中間狀態(tài)：狀態(tài)2表明模型上不執(zhí)行任務但待匹配軌跡上執(zhí)行任務A，引入了對齊操作，故代價為1；狀態(tài)3表明模型與待匹配軌跡均執(zhí)行任務A，沒有引入對齊操作，故代價仍保持為0；狀態(tài)4則是與狀態(tài)2相反，模型上執(zhí)行任務A但待匹配軌跡不執(zhí)行，即待匹配軌跡上引入了對齊操作，故代價也變成1.之后狀態(tài)2，3，4也根據(jù)如上規(guī)則繼續(xù)進行狀態(tài)的演變，由于篇幅限制，圖4中省略了很多的中間狀態(tài)只展示了關鍵的若干中間變量，集中表現(xiàn)了其中代價為2和代價為3的對齊情況的具體衍生過程.根據(jù)A*算法的剪枝規(guī)則，在已經(jīng)得到代價為2的對齊方案(狀態(tài)5)后，圖中帶有灰度的部分將會被剪枝，不會真正被一步步執(zhí)行，以此來減少計算量.

假設當前軌跡為tr，通過A*搜索算法找到代價最小的匹配軌跡為match_trace，便可對該條軌跡的契合度進行計算[13](其中cost為算法得到的最小代價，len(tr)和len(match_trace)為2條軌跡的長度)，而整個日志和模型的契合度則可以看成是所有軌跡契合度的平均，分別見式(4)和式(5).

(4)

(5)

2.4 A*搜索算法優(yōu)化

A*搜索算法的代價函數(shù)為f(x)=g(x)+h(x).其中，g(x)為當前已有代價，為真實代價與虛擬代價之和；h(x)為啟發(fā)式的預估當前狀態(tài)到結(jié)束狀態(tài)所需的代價，即中間狀態(tài)中的預估代價.

本節(jié)主要討論h(x)預估代價的計算.多實例的存在，使得軌跡可以無限變長，而邊界事件的存在，使得子流程又可以中途結(jié)束，故很多情況下很難預估當前狀態(tài)到結(jié)束狀態(tài)所需的代價.有種情況例外，即模型上使能了多個子流程的開始事件，若執(zhí)行完所有子流程得到的最短軌跡長度已經(jīng)大于待匹配軌跡長度，則兩者差的絕對值便為預估代價.

例2. 圖2表示已有的BPMN 2.0模型，假設當前狀態(tài)中的modelTrace為A，并且使能了2次包含B活動的子流程的開始事件，traceToMatch為E，說明模型上已經(jīng)執(zhí)行了任務A，且將要執(zhí)行2次子流程，而待匹配的軌跡為任務E，可以看到，執(zhí)行2次子流程最少需要4步(如B,C,B,C)，而待匹配的軌跡僅為E，故至少需要|B,C,B,C|-|E|=3次對齊的代價來完成匹配.

針對此種情況，可以對模型進行預處理，根據(jù)BPMN 2.0元素的語義，計算出每個開始事件到該子流程結(jié)束狀態(tài)的最短軌跡長度，在計算中間狀態(tài)時，若發(fā)現(xiàn)執(zhí)行已使能的子流程所需要最短軌跡長度大于待匹配的軌跡長度，則可以把該長度差計入預估代價中.

需要注意的是，以上通過對子流程代價的預估，來進行搜索空間的剪枝是必須的，而不是可選的.因為子流程多實例的特性，語義上可以產(chǎn)生無數(shù)個子流程，盡管已經(jīng)使用虛擬代價使得子流程多的中間狀態(tài)優(yōu)先級降低，但是在計算真實代價的時候，不會將虛擬代價計算入內(nèi)，仍會導致無數(shù)個中間狀態(tài).大部分情況下，通過對子流程代價的預估，往往限定了子流程的使能次數(shù)，可以大大減少搜索空間，然而若該子流程的任何一個父流程標有取消、錯誤等事件，說明使能的若干個子流程隨時可以退出，則對子流程的預估便會變得無效，因為這些子流程不是必須完整執(zhí)行的了.在此種情況下，可以設定子流程多實例的上限閾值，即最多可以同時使能多少個子流程，而這同時也是符合實際情況的，一個事件或者流程不可能無限制地被執(zhí)行.

3 Acorn算法實現(xiàn)

本文采用A*搜索算法來尋找基于軌跡對齊的最佳匹配.如算法1所示:

算法1. 單條軌跡與流程模型最佳對齊算法(BestBPMN2.0Alignment).

輸入：單條軌跡trace、BPMN 2.0模型model；

輸出：最小代價cost、對齊后軌跡match_trace.

① 令q為一個保存按照totalCost由低到高排序的中間狀態(tài)的優(yōu)先隊列；

② 令cost為當前最小的realCost,初始化為INT_MAX;

③ Whileqis not empty do

④ 令s為具有最小totalCost的當前狀態(tài);

⑤ Ifs.currentAvailableis NULL ors.traceToMatchis NULL do

⑥ updatecostandmatch_trace; continue;

⑦ End If

⑧ Ifs.realCost≥costdo continue;

⑨ End If

⑩ Foreach tasktins.currentAvailabledo

每次循環(huán)，算法1都從隊列中取出當前代價最小的中間狀態(tài)(行④)，并進行狀態(tài)的演變.

算法1的行⑤～⑦處理狀態(tài)不能再繼續(xù)演變的情況，即模型上已經(jīng)走到盡頭(沒有使能的任務)或者軌跡已經(jīng)全部匹配完的情況.如果是模型已經(jīng)匹配完的情況下，則s的代價需要加上未匹配軌跡的長度當成額外的代價，而如果是軌跡已經(jīng)全部匹配完，則根據(jù)當前狀態(tài)計算模型上離結(jié)束所需的最小步數(shù)，并將其計入代價中.行⑧～⑨ 用來剪枝，排除代價已經(jīng)高于目前最小值的中間狀態(tài).

Fig. 5 Two samples for conflicts between enabled tasks圖5 使能任務的2種沖突示例

圖5(a)展示了前后沖突，當任務A執(zhí)行完后，使能的任務有A和B，當選擇任務B來執(zhí)行時，說明任務A的多實例已經(jīng)結(jié)束，故需要在已經(jīng)使能的任務列表中刪除任務A的實例.圖5(b)則展示了內(nèi)外沖突，當任務A執(zhí)行完后，任務B使能，同時由于該子流程標記著邊界事件，任務C也使能，當接下來選擇C來執(zhí)行時，則說明子流程通過邊界事件跳出，則B任務不應該再使能.

1) 模型執(zhí)行當前任務，產(chǎn)生一系列的后繼狀態(tài)，而軌跡則保持不變，即軌跡上執(zhí)行對齊“?”.該行為僅為模型上的1次移動，代價需要在原先基礎上加1，如圖4中狀態(tài)1到狀態(tài)4的轉(zhuǎn)變.

2) 模型執(zhí)行當前任務，產(chǎn)生一系列的后繼狀態(tài)，且軌跡中第1個任務與模型當前任務相同，則軌跡也執(zhí)行該任務，且更新軌跡(去除軌跡中第1個任務).該行為為模型與軌跡的同時移動，代價不變，如圖4中狀態(tài)1到狀態(tài)3的轉(zhuǎn)變.

3) 模型不執(zhí)行任務，而軌跡則執(zhí)行當前第1個任務，即模型上執(zhí)行對齊“?”.該行為僅為軌跡上的1次移動，代價需要在原先基礎上加1，如圖4中狀態(tài)1到狀態(tài)2的轉(zhuǎn)變.

需要注意的是，在進行對齊產(chǎn)生新狀態(tài)的時候，需要更新中間狀態(tài)中的所有中間變量.

Acorn算法的實現(xiàn)如算法2所示.對日志中的每條軌跡均用其最佳匹配進行契合度計算，最后取其均值作為日志與模型的契合度.

算法2. 流程日志與流程模型的契合度算法(Acorn).

輸入：流程日志L、BPMN 2.0模型model；

輸出：流程日志與流程模型的契合度.

① 令f為契合度，初始化為0;

② Foreach tracetinLdo

③cost,match_trace=BestBPMN2.0-Alignment(t,model);

④f+=fitness(model,t);

⑤ End For

⑥f=|L|;

⑦ Returnf.

4 實驗評估

4.1 實驗設置

所有實驗均在筆記本電腦上完成，其配置為：酷睿2雙核處理器，T7500 CPU (2.2 GHz,800 MHz FSB,4 MB L2 cache)，內(nèi)存為4 GB，操作系統(tǒng)為Windows 7,JDK為1.6版本.

實驗用的BPMN 2.0模型來自國內(nèi)某大型通信公司，均由專業(yè)人員建模形成.對每個BPMN 2.0模型，使用課題組自主研發(fā)的模型仿真工具來產(chǎn)生一系列的日志，再隨機對日志中軌跡進行增刪改操作，如遍歷每條軌跡并對每個活動隨機應用以下任意一種操作：1)在該活動前添加1個活動；2)修改該活動的名稱；3)刪除該活動；4)保持不變.然后，對模型與日志應用Acorn算法來計算契合度，把得到的結(jié)果與專家人工進行最優(yōu)匹配的結(jié)果進行對比，以此確保算法的正確性.

4.2 效果評估

本實驗使用多個模型來驗證算法契合度計算的正確性，每個模型的特征如表2所示.根據(jù)引言所述，基于對齊的BPMN 2.0模型符合性檢測算法主要針對多實例、OR網(wǎng)關、子流程、邊界事件等特殊屬性，故表2枚舉了每個BPMN 2.0模型所包含的特殊屬性.

可以看到，所有特殊屬性均包括在測試用例中，包括特殊屬性之間的混合搭配.在效果評估試驗中，Acorn算法得到的結(jié)果與專家人工進行最優(yōu)匹配的結(jié)果完全一致，這歸功于Acorn算法采用了A*搜索算法來尋找基于軌跡對齊的最佳匹配.

Table 2 The Structural Features and Conformance of Process Models and Logs for Effectiveness Testing Experiments

4.3 性能評估

表3展示了Acorn算法在不同日志規(guī)模輸入下的性能表現(xiàn)，其中日志8_1和8_2，9_1和9_2，10_1和10_2分別對應模型8，9，10，該結(jié)果表明在正常規(guī)模下的模型與日志來進行符合性算法檢測，其耗時均在可接受范圍內(nèi).日志8_1和8_2的對比表明，相同模型下帶匹配軌跡長度越長，耗時越長.同樣，日志9_1和9_2，日志10_1和10_2的對比也能得出該結(jié)論.日志9_1，9_2與日志10_1，10_2對應的實驗結(jié)果表明，模型的復雜程度同樣影響算法運行時間，一般模型越復雜，耗時越多.實驗結(jié)果中可以看到，含有OR網(wǎng)關或者多實例子流程的模型，往往需要更多的匹配時間.原因也較好理解，這2種元素均會產(chǎn)生多個臨近的中間狀態(tài)，故BPMN 2.0模型中包含的特殊元素是影響其運行時間的重要因子之一.

Table 3 The Performance of Acorn Algorithm on Process Models with Different Sizes

4.4 優(yōu)化評估

表4展示了針對同一個包含若干多實例和嵌套多實例的過程模型和其對應日志，在不同多實例閾值下Acorn算法進行契合度計算時需要訪問的中間狀態(tài)的數(shù)量.可以看到，在不做任何優(yōu)化的前提下，隨著閾值的增加，很快便出現(xiàn)狀態(tài)爆炸的情況，虛擬代價和預估代價的引入均能在一定程度上進行有效的剪枝，而兩者的結(jié)合則是大大提升了算法的剪枝能力，避免了很多無用狀態(tài)的訪問.需要注意的是，在使用虛擬代價+預估代價的情況下，無論多實例閾值如何，節(jié)點搜索過程始終按照最優(yōu)路徑行進，而沒有訪問多余的中間狀態(tài)，因此在3種不同多實例閾值的情況下，Acorn算法訪問的中間狀態(tài)數(shù)量相同.

Table 4 Comparison of the Number of Intermediate States Accessed Under Various Costs in Different

5 總結(jié)與展望

本文提出了基于BPMN 2.0模型的符合性檢測算法Acorn.特殊網(wǎng)關、多實例、子流程、邊界事件等的存在，使得BPMN 2.0模型的符合性檢測變得比較困難，通過對這些特殊元素的語義的深入研究，且引入對齊操作，通過A*算法來搜索代價最小的匹配軌跡，從而完成符合性檢測分析.實驗結(jié)果表明該算法能有效地支持多種BPMN 2.0特殊元素，且準確有效.

該算法尚存在一些不足.基于A*的搜索算法，在最壞情況下會遍歷所有可能的匹配，故需要較長時間才能完成符合性檢測，故之后的研究方向?qū)旁贏*算法的優(yōu)化方面.此外，將針對準確性[14-15]、一般性和復雜性等其他符合性指標繼續(xù)開展研究工作.再者，考慮用多個不同維度的信息來計算契合度也是一大研究重點[16].

[1]Georgakopoulos D, Hornick M, Sheth A. An overview of workflow management: From process modeling to workflow automation infrastructure[J]. Distributed and Parallel Databases, 1995, 3(2): 119-153

[2]Chinosi M, Trombetta A. BPMN: An introduction to the standard[J]. Computer Standards & Interfaces, 2012, 34(1): 124-134

[3]van Dongen B F, de Medeiros A K A, Wen L. Process mining: Overview and outlook of Petri net discovery algorithms[G]LNCS 5460: Trans on Petri Nets and Other Models of Concurrency II. Berlin: Springer, 2009: 225-242

[4]Maggi F M, Bose R P J C, van der Aalst W M P. Efficient discovery of understandable declarative process models from event logs[C]Proc of Advanced Information Systems Engineering. Berlin: Springer, 2012: 270-285

[5]Wang Y, Wen L, Yan Z, et al. Discovering BPMN models with sub-processes and multi-instance markers[C]Proc of Conf on the Move to Meaningful Internet Systems (OTM 2015). Berlin: Springer, 2015: 185-201

[6]Polyvyanyy A, van der Aalst W M P, ter Hofstede A H M, et al. Impact-driven process model repair[J]. ACM Trans on Software Engineering and Methodology, 2017, 25(4): 1-60

[7]Murata T. Petri nets: Properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4): 541-580

[8]Molka T, Redlich D, Drobek M, et al. Conformance checking for BPMN-based process models[C]Proc of the 29th Annual ACM Symp on Applied Computing. New York: ACM, 2014: 1406-1413

[9]Adriansyah A, van Dongen B F, van der Aalst W M P. Towards robust conformance checking[C]Proc of Business Process Management Workshops. Berlin: Springer, 2010: 122-133

[10]de Leoni M, Maggi F M, van der Aalst W M P. Aligning event logs and declarative process models for conformance checking[C]Proc of the 10th Int Conf on Business Process Management (BPM 2012). Berlin: Springer, 2012: 82-97

[11]van der Aalst W M P, Pesic M, Schonenberg H. Declarative workflows: Balancing between flexibility and support[J]. Computer Science-Research and Development, 2009, 23(2): 99-113

[12]vanden Broucke S K L M, De Weerdt J, Vanthienen J, et al. Determining process model precision and generalization with weighted artificial negative events[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(8): 1877-1889

[13]van der Aalst W M P, Adriansyah A, van Dongen B. Replaying history on process models for conformance checking and performance analysis[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2012, 2(2): 182-192

[14]Adriansyah A, Munoz-Gama J, Carmona J, et al. Measuring precision of modeled behavior[J]. Information Systems and E-Business Management, 2015, 13(1): 37-67

[15]Chatain T, Carmona J. Anti-alignments in conformance checking-The dark side of process models[C]Proc of Int Conf on Applications and Theory of Petri Nets and Concurrency. Berlin: Springer, 2016: 240-258

[16]Mannhardt F, de Leoni M, Reijers H A, et al. Balanced multi-perspective checking of process conformance[J]. Computing, 2016, 98(4): 407-437

Wang Yuquan, born in 1990. Master. His main research interests include process mining and conformance checking.

Wen Lijie, born in 1977. PhD, associate professor, PhD supervisor. His main research interests include process mining, process data management, workflow for big data analysis.

Yan Zhiqiang, born in 1983. PhD. Assistant professor. Member of CCF. His main research interests include process mining, process similarity and process repository.

Alignment Based Conformance Checking Algorithm for BPMN 2.0 Model

Wang Yuquan1, Wen Lijie1, and Yan Zhiqiang2

1(SchoolofSoftware,TsinghuaUniversity,Beijing100084)2(SchoolofInformation,CapitalUniversityofEconomicsandBusiness,Beijing100070)

Process mining is an emerging discipline providing comprehensive sets of tools to provide fact-based insights and to support process improvements. This new discipline builds on process model-driven approaches and data-centric analysis techniques such as machine learning and data mining. Conformance checking approaches, i.e., techniques to compare and relate event logs and process models, are one of the three core process mining techniques. It is shown that conformance can be quantified and that deviations can be diagnosed. BPMN 2.0 model has so powerful expression ability that it can express complex patterns like multi-instance, sub-process, OR gateway and boundary event. However, there is no existing conformance checking algorithm supporting such complex patterns. To solve this problem, this paper proposes an algorithm (Acorn) for conformance checking for BPMN 2.0 model, which supports aforesaid complex patterns. The algorithm uses A*algorithm to find the minimum cost alignment, which is used to calculate fitness between BPMN 2.0 model and the log. In addition, virtual cost and expected cost are introduced for optimization. Experimental evaluations show that Acorn can find the best alignment by exploiting the meanings of BPMN 2.0 elements correctly and efficiently, and the introduction of virtual cost and expectation cost indeed reduces the search space.

BPMN 2.0 model; complex pattern; A*search; conformance checking; alignment

2016-10-24；

2017-03-07

國家重點研發(fā)計劃項目(2016YFB1001101)；國家自然科學基金項目(61472207，61325008，61402301) This work was supported by the National Key Research and Development Plan of China (2016YFB1001101) and the National Natural Science Foundation of China (61472207, 61325008, 61402301).

聞立杰(wenlj@tsinghua.edu.cn)

TP315