基于感知成本的流程模型與事件日志有效對齊

李多芹，方賢文*，王麗麗，2，邵叱風

（1.安徽理工大學 數學與大數據學院，安徽 淮南 232001；2.嵌入式系統與服務計算教育部重點實驗室（同濟大學），上海 201804；3.安徽科技學院 信息與網絡工程學院，安徽 蚌埠 233030）

0 引言

近年來，事件日志與流程模型之間的對齊已被證明對過程挖掘中的服從性校驗問題極為有用［1］。日志跡與流程模型之間可能會存在多種對齊，目前最優的對齊默認為給定成本函數下成本最小的對齊，于是在對齊過程中，成本函數的選取尤為重要。關于對齊及對齊成本函數的選取，很多學者已經做了大量研究：文獻［2］中表明事件日志與流程模型之間保持適當對齊的重要性，并詳細闡述了這種對齊的實現及對齊在服從性校驗和性能分析中的應用；文獻［3］中利用流程模型結構和行為特征的優勢，提出一種在尋找最優對齊時能顯著縮減搜索空間的方法；文獻［4］中將對齊的計算問題轉化為整數線性規劃模型的求解問題，從而顯著降低問題的復雜性；文獻［5］中提出了一種基于Petri 網的事件日志與過程模型之間的快速對齊方法，即Rapid Align 方法，以提高過程挖掘中計算最優對齊的效率；文獻［6］中為了提升了過程挖掘中計算最優對齊的效率，提出一種基于Petri 網可達圖的業務對齊方法。

在上述工作中，都選擇使用標準成本函數進行對齊。事實上，據所知，現有的絕大多數對齊問題中都默認使用該函數，該函數將模型和日志的同步移動及靜默移動的成本記為0，異步移動的成本都記為1，即將模型中的異步移動和日志中的異步移動產生的影響視為是等價的。然而，文獻［7］中通過具體的實例表明，在某些應用情境中使用標準成本函數對齊模型和日志會產生不符合邏輯的對齊結果，于是文獻［7］提出了標準成本函數的一個變體：最大同步成本函數。該函數中模型移動的成本值遠小于日志移動，進而通過產生額外的模型移動使得同步移動的數量最大化；然而，不論是將異步移動的成本值都計為1 還是使得模型移動的成本值遠小于日志移動的成本值都可能會導致對齊成本與感知成本相差甚遠。一個典型的情況是當出現冗余噪聲時，最大化同步成本函數會盡可能犧牲模型移動來將該噪聲事件與模型中的某一活動形成同步移動，從而導致對齊成本嚴重偏離感知成本。

基于此，本文根據業務流程中的典型行為流特征定義了一種新的成本函數，即重要同步成本函數，使得在該函數下對齊流程模型與事件日志時的對齊成本更加貼合感知成本；同時，基于該函數給出一種能夠提升對齊效率的對齊算法，其中，業務流程中的典型行為流特征用于確定流程中各活動的重要程度。關于業務流程中的典型行為流，已有學者做了相關研究：文獻［8］中指出許多流程通常以固定的順序執行初始活動，經過一系列流程走向變化，如，并行分支、循環等，又收斂到更結構化的行為，然后再次發散；文獻［9］中利用行為流的這種特征將流程模型劃分為強制性子序列和選擇性子序列，通過選擇相應的測量公式，切實有效地提升了日志與模型之間的適合度。關于感知成本，本文遷移了文獻［10］中提到的感知一致性概念，該文獻研究的問題是：流程模型間行為一致性的哪一種正式概念可以最好地近似模型專家的感知一致性。類似地，本文的研究問題是：對齊流程模型和事件日志時，哪一種成本函數下的對齊成本能更好地接近感知成本。

1 知識準備

定義1模型與日志的對齊［7］。令Σ為活動集，包含靜默活動τ 的活動集記為Στ，即Στ=Σ∪{τ}；包含跳過符號＞＞的活動集計為Σ＞＞，即Σ＞＞=Σ∪{＞＞}；Στ＞＞=Σ∪{τ，＞＞}則表示同時包含靜默活動和跳過符號的活動集。令σ∈Σ*是一條日志跡，N為一Petri 網模型，則模型N中的執行序列與日志跡σ的對齊γ指的是日志-模型對的一個序列，即γ∈(Σ＞＞×Σ＞＞)*。

定義2對齊成本［7］。令γ∈(Σ＞＞×Σ＞＞)*是σ∈Σ*和Petri網N間的一組對齊。該對齊的成本函數c為對齊對到正實數上的映射，即c：(Σ＞＞×Στ＞＞) →R≥0，于是c(γ)=Σ0≤i≤|γ|-1c(γi)。

若給定對齊成本函數c，在該成本函數下對齊γ為最優的，當且僅當不存在γ'使得c(γ') ＜c(γ)。

定義3標準成本函數［7］。對齊對(l，m)∈(Σ＞＞×Στ＞＞)的標準成本函數cst定義如下：

由上式可以看出，對標準的成本函數而言，靜默移動和同步移動的成本為0；日志移動和模型移動的成本都為1。文獻［7］中通過真實的案例表明，該成本函數雖然在相關文獻中經常使用，但可能會產生不希望得到的，即不符合邏輯的對齊結果，于是提出了最大同步成本函數的概念如下。

定義4最大同步成本函數［7］。對齊對(l，m)∈(Σ＞＞×Στ＞＞)的最大同步成本函數cmax-sync定義如下：

其中0 ＜ε＜1。比較定義3 和定義4 可以看出，兩個成本函數只在模型移動成本值的設置上有所不同，定義4 中將模型移動的成本值設置為任意小的數，即ε，通過這種方式使得對齊結果中同步移動的數量最大化。可以預見，同步移動數量最大化的同時會產生很多額外的模型移動；然而，在某些真實情境中，額外產生的模型移動會帶來更大的影響，以犧牲模型移動為代價一味地追求同步移動數量的最大化并不是明智的選擇，從而使得產生的對齊結果并不可取。

2 動機例子

為了激勵消費者，電子商城經常會發放一定額度優惠券，本文以此背景下的商品購買流程作為動機案例，如圖1用Petri 網給出了該購買流程的控制流依賴。

圖1 中各字母所指代的活動如表1 所示，由圖1 和表1 可知，顧客一旦選擇某一商品后，隨時都可以進入付款界面，且進入付款界面前或進入付款界面后都有查看店鋪優惠券及選擇使用或不使用優惠券的權利，這與當今各大電子商城的購物模式相吻合。

表1 圖1中各個字母指代的活動Tab.1 Activities referred to letters in Fig.1

對跡σ=，若使用標準的成本函數將其與圖1 中的流程P進行對齊，可得到圖2 中的最優對齊γ1，易知在標準成本函數下γ1的成本為2；若使用最大同步成本函數則可得到最優對齊γ2且在最大同步成本函數下γ2的成本為3ε。然而，代入圖1 中所給出的真實問題情境，可以明顯看到γ1和γ2的感知成本與兩種函數下計算出的成本有很大差距，因為在網絡購物這一問題情境中，顧客是否愿意進入到付款界面代表著對該商品購買意愿，是商家十分關注的步驟。尤其在γ2中，跳過活動g（進入付款界面）的成本用一個任意小的ε來衡量是不合理的。此外，把跳過活動g 和跳過活動f（或c）的成本設置為相同的單位值也會使得對齊成本偏離感知成本。

我們知道，對齊模型和日志跡的意義在于反映模型流程和真實執行流程間的偏差，于是對于這類真實的問題情景，γ1和γ2產生的對齊結果是不可取的，因為對齊成本嚴重偏離感知成本，也就是說對齊結果無法反映真實偏差情況。為了解決這個問題，下面將基于感知成本的概念提出標準成本函數的另外一個變體，即重要同步成本函數。

3 基于感知成本的有效對齊方法

3.1 重要同步成本函數

通過對動機例子的分析知道，跳過或插入不同活動的感知成本是有很大差距的；于是，為了使對齊成本更加貼合感知成本，在對齊前將活動集Σ按重要程度進行劃分，并為劃分后的不同的活動類分配不同的成本是必要的。為了劃分活動集Σ，不失一般性，引入流程模型中行為的典型流特征作為重要程度的劃分依據。

文獻［8］中指出許多流程以獨特或類似的行為開始，也就是說，通常一個初始活動（組）是以固定的順序執行的。隨后，根據流程的具體實例，流程中可能出現更多的變化，例如并行分支、循環等。在流程的某些節點上，行為再次收斂為更結構化的，即以固定的順序執行的行為，然后再次發散。圖3 給出了該流程事實的示意圖。

此外，文獻［9］所提方法同樣基于該流程事實，將流程模型劃分為強制性活動路徑和選擇性活動路徑，并通過實驗證明劃分后的準確檢測偏差能夠明顯提高適合度測量值。

基于上述事實，本文將流程模型中強制性活動路徑上的所有活動記作強制性活動或重要活動，所有強制性活動組成的集合記為Σ+；將選擇性活動路徑中的所有活動記作選擇性活動，所有選擇性活動組成的集合記為Σ-，并默認活動集中的活動是按照流程執行的先后順序排列的。這里Σ=Σ+∪Σ-且Σ+∩Σ-=?，即將活動集Σ按重要程度劃分為兩個互不相交子活動集Σ+和Σ-。具體地，對圖1 中的流程有：Σ=｛a，b，c，d，e，f，g，h，i，j｝，Σ+=｛a，g，j｝，Σ-=｛b，c，d，e，f，h，i｝。基于上述活動集的分類，可將重要同步成本函數形式化定義如下。

定義5重要同步成本函數。結合第1 章中對相關符號的定義，定義一個對齊對的重要同步成本函數cimp-sync如下：

其中0 ＜ε＜1。定義5 中活動集被分Σ為強制性活動集Σ+和選擇性活動集Σ-，且Σ+上日志移動和模型移動的成本為1；Σ-上日志移動和模型移動的成本都為ε。通過為兩類活動集賦予差距較大的單位成本值，使得在對齊過程中優先考慮重要活動的對齊，從而得到更加貼近感知成本的對齊結果。

根據定義5 中的成本函數，可以得到跡σ=和圖1 中所示流程的最優對齊如下：

易知γ3在重要同步成本函數下的對齊成本為3ε，雖然γ2的對齊成本也為3ε，但正如第2 章中所述，γ2中為了使同步移動的數量最大化添加了額外的模型移動（如活動g），這導致對齊成本與感知成本有很大差距。相反地，γ3中的對齊因為優先考慮了重要活動的同步（已用陰影突出顯示），所以使得對齊后的成本與感知成本比較貼近。于是對跡σ=和圖1 中的流程來說，重要同步成本函數下的最優對齊γ3更能反映流程模型和真實執行跡間的偏差。

值得注意的是，上述活動類的劃分只是依據流程模型中行為的典型流特征分為兩類，在實際執行中，操作者可根據現實意義自定義地將流程中活動劃分為若干類。此外，不同活動類上單位成本值的分配也可以依據實際需求自定義設置。當按照上述操作劃分活動類時，下面將基于該成本函數給出一種可以提升效率的對齊計算方法。

3.2 重要同步成本函數下的有效對齊方法

基于所提成本函數有效對齊方法的框架如圖5 所示，主要可以被分為3 步：首先，根據流程模型的典型流特征劃分活動類，并基于日志跡和強制性活動集確定重要匹配子序列；然后，依據重要匹配子序列中的活動分別將模型與日志做對應的分割；最后，基于重要同步成本函數對齊每一個子流程和對應的日志跡子序列，并將分段對齊的結果進行合并以得到最終的對齊結果。

3.3 重要匹配子序列的確定

重要匹配子序列指的是在日志跡和強制性活動集中都按一定順序出現的活動組成的集合，子序列中的活動在對齊過程中會優先產出同步移動。依據流程模型中行為的典型流特征劃分活動類后，利用文獻［11］中給出的最長公共子序列（Longest Common Subsequence，LCS）概念從日志跡和Σ+中確定重要匹配子序列。

定義6最長公共子序列［11］。序列Zr=(z1，z2，…，zr)為序列Xm=(x1，x2，…，xm)和序列Yn=(y1，y2，…，yn)的最長公共子序列，當且僅當序列滿足：

1）zs=xis=yjs，1 ≤s≤r；

2）1 ≤i1≤i2≤… ≤ir≤m∧1 ≤j1≤j2≤… ≤jr≤n；

3）對于任意一個Xm和Yn的子序列Z'，都有|Z'| ≤|Zr|。

文獻［11］根據最長公共子序列定義，展示了求最長公共子序列長度算法，該算法以兩個有限序列為輸入，根據遞推計算公式輸出這兩個序列的最長公共子序列定義。以動機案例中所給的日志跡和模型為例，輸入和Σ+=｛a，g，j｝，可得到的σ和Σ+的最長公共子序列，也就是日志跡σ和圖1 中模型的重要匹配子序列為Simp=（a，g，j）。為表示方便，可將該算法視為一個函數，即LCS（σ，Σ+）=Simp。確定了重要匹配子序列Simp后，下面將根據Simp中的活動分別對日志跡和流程模型進行分割。

3.4 日志跡和流程模型的分割

在3.3 節中，通過LCS 函數可以確定對齊流程模型和日志跡的重要匹配子序列Simp，為了提升對齊流程模型和事件日志的效率，下面將依據Simp中的活動分別對流程模型和事件日志進行分割，使得分割后的子模型和日志跡子序列能夠一一對應并對齊，利用這種分而治之的思想旨在縮減對齊整條日志跡和流程模型時需要搜索的狀態空間。下面給出以日志跡和Simp為輸入的日志分割算法（Log Trace Divide，LTD）。該算法通過If-else 語句區分出四種不同的日志分割情況。

算法1 日志跡分割算法。

從算法1 中可以看出，日志跡的分割可以依據日志跡與Simp的1 號位活動、n號位活動是否相同分為4 種情況，進而導出3 種可能的子模型/日志子序列的個數，即h=k-1 orkork+1。此外，可以觀察到，每兩個相鄰的子序列會有一個共享的活動，即上一個子序列的結束活動與下一個子序列的開始活動相同。算法最后輸出日志跡σ的h個子序列（算法1的18））。為表示方便，同樣將該算法視為一個函數，即LTD(σ，Simp)=σ1，σ2，…，σh。延續3.2 節中的例子可對日志跡進行分割：因為Simp=（a，g，j），|Simp|=3且日志跡與Simp的1 號位活動、n號位活動均相同，于是可根據算法1 的4）～5）將日志跡分成2 個子序列：可以看到活動g為σ1和σ2的共享活動。

類似地，可以依據Simp中的活動將流程模型分成若干個個子流程，即流程分割（Process Model Divide，PMD）算法。為表示方便，同樣將該算法視為一個函數，于是有PMD(P，Simp)=P1，P2，…，Ph。此時，每兩個相鄰的子流程也會有一個共享的活動，即上一個子流程的結束活動與下一個子流程的開始活動相同。根據重要匹配子序列Simp可將圖1中的流程分割為兩個子流程P1和P2，如圖6 所示。

根據同一個重要匹配子序列對流程模型和日志跡進行分割后，得到的分割結果是對應的，即子流程與子序列個數相同，且存在一一對應的關系，于是可先對齊分割后得到的子流程與子日志序列，再依據共享活動將各部分的對齊結果合并以得到完整的日志跡和流程模型的對齊。較之于傳統的對齊操作，這種分而治之的對齊策略能大幅提升對齊效率。

通過LTD 和PMD 函數可以將流程模型和事件日志分割成一一對應的子流程和日志跡子序列，接著基于重要同步成本函數對齊每一個子流程和對應的日志跡子序列，將分段對齊的結果進行合并就可以得到最終的對齊結果。

3.5 基于重要同步成本函數的有效對齊算法

到目前為止，前面的內容分別詳細闡述了所提方法的理論基礎，以及重要步驟的具體操作，下面將給出完整的算法實現。該算法以日志跡σ和流程模型P為輸入，經過確定重要匹配子序列Simp、基于Simp分割流程模型與事件日志、在重要同步成本函數下對齊子流程和日志跡子序列及依據共享活動合并對齊結果等步驟，最后輸出重要成本函數下日志跡與流程模型的最優對齊γopt。

算法2 基于重要同步成本函數cimp-sync的對齊算法。

算法首先獲取強制性活動集和選擇性活動集（算法2 中1））；接著利用LCS 長度算法獲取重要匹配子序列Simp（算法2中2））；然后分別通過LTD 和PMD 函數獲取日志跡子序列和子流程（算法2 中3）～4））；同時根據分割后的日志跡提取共享活動集Es（算法2 中5））；對每一組對應的子序列和子流程，在cimp-sync下進行對齊（算法2 中6）～7））；最后利用共享活動將各部分的對齊結果進行合并，并返回最優對齊γopt。

4 實驗與結果分析

為了驗證上述所提方法，實驗部分將先介紹實驗數據的來源；接著，詳細闡述實驗步驟；最后，分別通過3 種函數下對齊準確率和效率的對比來評估所提方法的性能，并在實驗結果對比圖的支撐下得出結論，即本文方法能在滿足準確率需求的同時提升對齊的效率。

4.1 實驗數據

Jouck等［12-13］提出的PTandLogGenerator 可構造同時包含序列、并發、選擇和循環結構的業務流程模型，該構造器已在Prom 中實現，操作者通過輸入模型大小、各個操作符出現的概率等參數可直接批量生成符合要求的流程模型，部分學者將其用于過程發現算法的評估［14-15］。為了驗證所提方法，實驗部分將利用該構造器隨機生成10 條業務流程模型，流程中活動數量為11～37 的均勻分布。通過對每條業務流程進行下述實驗步驟中一系列的處理，最終將對6 000 條對齊結果的數據進行分析。所有的實驗數據均可在線訪問：https：//github.com/duoqinLi/experimenta-data.git。

4.2 實驗步驟

為了評估3 種成本函數下的對齊準確率和對齊效率，設計如下實驗步驟：首先，對每一個用Petri 網表示的流程模型，通過Prom 中的插件隨機運行出10 條完全服從的流程執行序列，稱這些服從的日志跡為參考跡，用σ表示。然后，為了獲取包含各種可能情況的不服從日志，對σ分別添加不同形式且不同比例的噪聲。噪聲的形式包括缺失、錯位、冗余及3 種噪聲的混合，噪聲的比例分別為10%，20%，…，50%，這樣每一條完全服從的執行序列都可以導出20 條不同的不服從序列，加噪后不服從的日志跡用σ'表示，于是每個流程對應200 條不服從的日志跡。接著，先直接利用現有Prom 插件計算cst和cmax-sync下σ'與流程模型的對齊；再基于算法2計算cimp-sync下σ'與流程模型的對齊。對齊結果中的模型執行序列用σ″表示，于是每個流程對應600 條相互獨立的對齊結果。最后，依據這些對齊結果，分別比較3 種成本函數下對齊的準確率和效率，并用可視化的三維圖直觀地展示對比結果。

4.3 準確性評估

對每一個流程模型，將最初獲得的完全服從執行序列σ作為評估不同成本函數下對齊結果所返回的模型執行序列σ″是否準確的標準：如果σ和σ″完全相同，則準確率記為1；當σ和σ″不完全相同時，就需要通過判斷兩個序列的相似度來獲取不同成本函數下對齊結果的準確率。在下面的實驗中，本文利用python 官方庫difflib 中的SequenceMatcher 類來計算兩序列的相似度，其思想是找到不包含無用元素的最長連續匹配子序列，然后遞歸地將相同的思想應用于匹配子序列的左邊和右邊的序列片段。

根據上述的實驗數據和評估標準，可以分別對不同噪聲類型下3 種函數得出的對齊結果進行準確率的比較。當不服從的日志僅包含缺失噪聲時，重要同步成本函數分別與標準成本函數和最大同步成本函數的對齊結果對比如圖7所示。

從圖7 中可以得出，當不服從的日志僅包含缺失噪聲時，cimp-sync下的平均對齊準確率為90.69%，結果略優于cst的90.59%，但是與cmax-sync下的對齊結果相比準確率偏低。另一方面，用標準差衡量圖7（c）中各準確率的離散程度時，可得cimp-sync、cst及cmax-sync下的標準差分別為3.15、3.25 和3.92。這表明，與其他兩種成本函數相比，cimp-sync下的對齊結果更加穩定。下面考慮當不服從的日志僅包含錯位噪聲時三種成本函數的對齊結果，結果對比如圖8 所示。

從圖8 中可以看出，當不服從的日志僅包含錯位噪聲時，3 種成本函數下的對齊結果均有較大的波動，其中cmax-sync下的對齊結果起伏波度最大，標準差為9.40，相比之下cimp-sync與cst的波度較小且起伏軌跡十分接近，標準差分別為6.18和6.13。下面考慮當不服從的日志僅包含冗余噪聲時，3 種成本函數的對齊結果，結果對比如圖9 所示。

從圖9 中可以看出，當不服從的日志僅包含冗余噪聲時，各流程在cimp-sync和cst下對齊結果的準確率十分平穩，平均準確率分別為98.53%和99.10%。相比之下，cmax-sync下的對齊結果波度較大且平均準確率最低，僅為81.09%，與cimp-sync和cst下的對齊準確率分別相差17.44%和18.01%。這是因為cmax-sync下在對齊過程中過分追求同步移動的數量的最大化，于是當出現冗余噪聲時，會盡可能犧牲模型移動來將該噪聲事件與模型中的某一活動形成同步移動，從而降低準確率。下面考慮當不服從的日志包含缺失、錯位和冗余三種類型的混合噪聲時，對齊結果對比如圖10 所示。

從圖10 中可以得出，當不服從的日志包含混合噪聲時，cimp-sync下的平均對齊準確率最高，為88.67%；cst其次，為88.65%，均大幅度高于cmax-sync下的81.34%。此外，cimp-sync下的對齊結果也最為穩定，標準差為3.21；cst其次，標準差為3.29；cmax-sync下的對齊結果最不穩定，標準差高達11.61。事實上，我們知道，在實際的業務流程執行過程中，不服從日志的噪聲在絕大多數情況下并不是單一類型的。而圖10 表明，在包含混合噪聲的情況下，cimp-sync能夠得出準確率更高且更穩定的對齊結果。

綜上，可以得出結論，較之于標準成本函數和最大同步成本函數，重要同步成本函數下的對齊結果滿足準確率的需求，且在某些情況下能夠產出更高準確率、更穩定的對齊結果。

4.4 效率評估

為了評估算法2 中所提對齊算法的效率，同樣與另外兩種函數在對齊所耗時間上進行比較。這里σ'與流程模型在cst和cmax-sync下的對齊時間可直接通過對齊插件獲取并記錄，cimp-sync下σ'與流程模型的對齊時間則通過累加各個子序列和子模型的對齊時間得到。

根據上述的實驗數據和評估標準，當不服從的日志包含缺失、錯位和冗余三種類型的混合噪聲時，重要同步成本函數分別與標準成本函數和最大同步成本函數的對齊所耗時間對比如圖11 所示。

從圖11中可以得出，cimp-sync、cst和cmax-sync下對齊流程模型和事件日志的平均耗時分別為0.63 s、1.58 s 和2.21 s，即較之于現存的兩種成本函數，所提成本函數下的對齊效率分別提升了約150.79%和250.79%。這得益于對模型和不服從日志的分割，因為分段后的對齊能夠大幅縮減對齊時的搜索空間。相比之下，cmax-sync下對齊的平均耗時最高，主要因為在對齊過程中產出了大量的同步移動。上述結果說明算法2 中所提方法能夠很好地提升模型與不服從日志的對齊效率。

5 結語

本文針對現存成本函數存在的問題給出了一種新的成本函數，在該成本函數下能夠優先同步操作者自定義的活動類，進而得出更貼近感知成本的對齊結果；同時，基于該函數提出了一種能夠提升對齊效率的算法。實驗部分通過對大量對齊結果數據的分析，驗證了所提函數及對應算法能夠在滿足準確率需求的同時提升對齊的效率。在未來的工作中，將考慮進一步提升算法的效率，以便所提方法能更好地應用于實際的問題情境中。