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

（1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001；2.嵌入式系統(tǒng)與服務(wù)計算教育部重點實驗室（同濟大學(xué)），上海 201804；3.安徽科技學(xué)院 信息與網(wǎng)絡(luò)工程學(xué)院，安徽 蚌埠 233030）

0 引言

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

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

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

1 知識準備

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

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

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

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

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

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

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

2 動機例子

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

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

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

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

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

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

3.1 重要同步成本函數(shù)

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

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

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

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

定義5重要同步成本函數(shù)。結(jié)合第1 章中對相關(guān)符號的定義，定義一個對齊對的重要同步成本函數(shù)cimp-sync如下：

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

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

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

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

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

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

3.3 重要匹配子序列的確定

重要匹配子序列指的是在日志跡和強制性活動集中都按一定順序出現(xiàn)的活動組成的集合，子序列中的活動在對齊過程中會優(yōu)先產(chǎn)出同步移動。依據(jù)流程模型中行為的典型流特征劃分活動類后，利用文獻［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］根據(jù)最長公共子序列定義，展示了求最長公共子序列長度算法，該算法以兩個有限序列為輸入，根據(jù)遞推計算公式輸出這兩個序列的最長公共子序列定義。以動機案例中所給的日志跡和模型為例，輸入和Σ+=｛a，g，j｝，可得到的σ和Σ+的最長公共子序列，也就是日志跡σ和圖1 中模型的重要匹配子序列為Simp=（a，g，j）。為表示方便，可將該算法視為一個函數(shù)，即LCS（σ，Σ+）=Simp。確定了重要匹配子序列Simp后，下面將根據(jù)Simp中的活動分別對日志跡和流程模型進行分割。

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

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

算法1 日志跡分割算法。

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

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

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

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

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

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

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

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

4 實驗與結(jié)果分析

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

4.1 實驗數(shù)據(jù)

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

4.2 實驗步驟

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

4.3 準確性評估

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

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

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

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

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

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

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

4.4 效率評估

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

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

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

5 結(jié)語

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