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

李多芹，方賢文*，王麗麗，2，邵叱風(fēng)

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

0 引言

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

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

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

1 知識(shí)準(zhǔn)備

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

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

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

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

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

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

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

2 動(dòng)機(jī)例子

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

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

表1 圖1中各個(gè)字母指代的活動(dòng)Tab.1 Activities referred to letters in Fig.1

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

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

3 基于感知成本的有效對(duì)齊方法

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

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

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

此外，文獻(xiàn)［9］所提方法同樣基于該流程事實(shí)，將流程模型劃分為強(qiáng)制性活動(dòng)路徑和選擇性活動(dòng)路徑，并通過(guò)實(shí)驗(yàn)證明劃分后的準(zhǔn)確檢測(cè)偏差能夠明顯提高適合度測(cè)量值。

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

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

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

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

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

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

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

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

3.3 重要匹配子序列的確定

重要匹配子序列指的是在日志跡和強(qiáng)制性活動(dòng)集中都按一定順序出現(xiàn)的活動(dòng)組成的集合，子序列中的活動(dòng)在對(duì)齊過(guò)程中會(huì)優(yōu)先產(chǎn)出同步移動(dòng)。依據(jù)流程模型中行為的典型流特征劃分活動(dòng)類后，利用文獻(xiàn)［11］中給出的最長(zhǎng)公共子序列（Longest Common Subsequence，LCS）概念從日志跡和Σ+中確定重要匹配子序列。

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

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

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

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

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

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

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

算法1 日志跡分割算法。

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 實(shí)驗(yàn)步驟

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

4.3 準(zhǔn)確性評(píng)估

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

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

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

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

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

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

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

4.4 效率評(píng)估

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

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

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

5 結(jié)語(yǔ)

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