一種面向業(yè)務(wù)過(guò)程的剩余時(shí)間預(yù)測(cè)算法

劉云峰， 高俊濤

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院， 黑龍江 大慶 163318)

0 引言

業(yè)務(wù)過(guò)程管理是管理、分析、控制和改進(jìn)企業(yè)產(chǎn)生經(jīng)營(yíng)過(guò)程的系統(tǒng)化與結(jié)構(gòu)化方法，幫助企業(yè)提升管理體系的關(guān)鍵。越來(lái)越多的企業(yè)開(kāi)始建立自己的業(yè)務(wù)過(guò)程模型、運(yùn)行和部署過(guò)程模型，并通過(guò)對(duì)運(yùn)行流程的檢測(cè)以及歷史數(shù)據(jù)的分析來(lái)逐步優(yōu)化企業(yè)流程。業(yè)務(wù)過(guò)程評(píng)價(jià)的重要指標(biāo)是時(shí)間，剩余時(shí)間預(yù)測(cè)是業(yè)務(wù)過(guò)程的一項(xiàng)核心任務(wù)。研究及時(shí)準(zhǔn)確的剩余時(shí)間預(yù)測(cè)方法不僅可以幫助企業(yè)調(diào)整生產(chǎn)計(jì)劃和服務(wù)流程，還有助于緩解用戶(hù)因長(zhǎng)時(shí)間的等待而產(chǎn)生的焦慮。

1 研究現(xiàn)狀

流程監(jiān)控的對(duì)象主要包括流程的周轉(zhuǎn)時(shí)間、資源占用情況、成本開(kāi)銷(xiāo)等流程性能指標(biāo)。預(yù)測(cè)方法可以歸結(jié)為分析型方法和比較型方法兩類(lèi)。

典型的分析型預(yù)測(cè)方法包括Rogge-Solti于2015年提出基于隨機(jī)Petri網(wǎng)的預(yù)測(cè)方法[1]和Dumas于2017年提出的基于流分析(Flow Analysis)技術(shù)的預(yù)測(cè)方法[2]。

比較型預(yù)測(cè)方法包括SVM[3]、決策樹(shù)[4]和聚類(lèi)[5]在內(nèi)的多種數(shù)據(jù)挖掘模型和算法分析影響監(jiān)控指標(biāo)的企業(yè)流程因素和外部環(huán)境因素。2011年，Wil van der Aalst等[6]提出了基于變遷系統(tǒng)的剩余時(shí)間預(yù)測(cè)方法，該方法用變遷系統(tǒng)描述事件日志中流程實(shí)例的所有可能狀態(tài)，并在狀態(tài)上標(biāo)記時(shí)間信息，以便根據(jù)當(dāng)前流程實(shí)例所處的狀態(tài)預(yù)測(cè)其剩余執(zhí)行時(shí)間。

除了采用傳統(tǒng)數(shù)據(jù)挖掘方法進(jìn)行類(lèi)比預(yù)測(cè)外，將深度學(xué)習(xí)技術(shù)應(yīng)用于業(yè)務(wù)流程預(yù)測(cè)也是近年來(lái)流程管理領(lǐng)域一個(gè)新涌現(xiàn)的研究熱點(diǎn)[7]。

本文在前人研究的基礎(chǔ)上，以數(shù)據(jù)純度作為重點(diǎn)，提出一種基于模型數(shù)據(jù)純度高低選擇合適預(yù)測(cè)模型的剩余時(shí)間預(yù)測(cè)方法。該方法采用搜尋歷史相似數(shù)據(jù)的方式，適用于現(xiàn)在主流的XES和CSV格式事件日志。

2 基本概念

2.1 算法基礎(chǔ)概念

業(yè)務(wù)過(guò)程實(shí)例的剩余時(shí)間預(yù)測(cè)需要先從歷史事件日志中獲取時(shí)間戳及相關(guān)信息。為了敘述方便，首先對(duì)業(yè)務(wù)過(guò)程的相關(guān)概念進(jìn)行定義。

定義1(軌跡) 軌跡是一種有限非空線(xiàn)性集合，即σ∈ε*。在任意一個(gè)軌跡中，每個(gè)事件只發(fā)生一次并且時(shí)間是非遞減的。

定義2(事件日志) 一個(gè)事件日志L={σ1,σ2,…}是多條日志軌跡的集合，每個(gè)事件在整個(gè)日志中最多只出現(xiàn)一次。

定義3(變遷系統(tǒng)) 變遷系統(tǒng)是一個(gè)三元組TS=(S,E,T)，其中S為狀態(tài)集合;E為活動(dòng)集合;T∈S×E×S為轉(zhuǎn)移集合。

傳統(tǒng)TS預(yù)測(cè)方法采用帶時(shí)間標(biāo)注的變遷系統(tǒng)預(yù)測(cè)業(yè)務(wù)過(guò)程的剩余時(shí)間。其方法采用序列、集合、多重集中某一種抽象機(jī)制構(gòu)建預(yù)測(cè)模型，并根據(jù)模型預(yù)測(cè)剩余時(shí)間。如果構(gòu)建預(yù)測(cè)模型的抽象機(jī)制發(fā)生了變化，剩余時(shí)間的預(yù)測(cè)結(jié)果可能不一樣。事件日志片段案例如表1所示。

表1 事件日志片段

對(duì)表1所示的事件日志片段，采用序列和集合抽象分別得到2個(gè)模型,如圖1所示。

(b) 基于set抽象的變遷系統(tǒng)

以軌跡前綴〈A,C,B〉為例，采用序列抽象的剩余時(shí)間預(yù)測(cè)值為7，采用集合抽象的預(yù)測(cè)值為5.3。因此序列抽象預(yù)測(cè)結(jié)果的MAE為1，集合抽象預(yù)測(cè)結(jié)果的MAE為1.7。

定義4(預(yù)測(cè)模型) 本文在TS預(yù)測(cè)方法的基礎(chǔ)上，將原來(lái)只包含單一抽象機(jī)制的變遷系統(tǒng)擴(kuò)展為包含3種抽象機(jī)制的復(fù)合變遷系統(tǒng)。預(yù)測(cè)模型M是一個(gè)集合，其元素為三元組(C,E,V)。其中,C為預(yù)測(cè)狀態(tài)編碼;E為剩余時(shí)間觀察值的均值;V為觀察值的標(biāo)準(zhǔn)差。

3 基于數(shù)據(jù)純度的預(yù)測(cè)算法

本節(jié)在預(yù)測(cè)模型M的基礎(chǔ)上，介紹在實(shí)際企業(yè)業(yè)務(wù)過(guò)程的部分軌跡已知的情況下，對(duì)其剩余時(shí)間進(jìn)行預(yù)測(cè)的算法。算法1描述了在輸入部分已知軌跡θ和模型M的情況下，根據(jù)觀察值的標(biāo)準(zhǔn)差V進(jìn)行選擇，返回預(yù)測(cè)值的過(guò)程。

算法1 基于數(shù)據(jù)純度的剩余時(shí)間預(yù)測(cè)算法輸入:預(yù)測(cè)模型M,前綴軌跡θ輸出:剩余時(shí)間預(yù)測(cè)值^tFunction Predict(M,θ)1. l=len(θ)2. maxpur f=0 //最大純度3. while (l>0)4. Foreach abs in {hdl(θ),bag(hdl(θ)),set(hdl(θ))}5. Foreach m in {m∈M|mcode=abs}6. If pur f(m)>maxpur f7. ^t←mE-(e|θ|-el)8. return ^tEndFunction

3.1 狀態(tài)選擇

傳統(tǒng)TS方法每次預(yù)測(cè)只能使用一種抽象機(jī)制，而且在實(shí)際業(yè)務(wù)過(guò)程中需要根據(jù)人工經(jīng)驗(yàn)來(lái)判斷選擇哪種抽象機(jī)制，這與智能制造的宗旨不符。因此,本文將實(shí)際業(yè)務(wù)過(guò)程中的部分已知軌跡θ在預(yù)測(cè)模型M中根據(jù)歷史相似數(shù)據(jù)進(jìn)行匹配，記錄下每個(gè)匹配成功的結(jié)果作為備選預(yù)測(cè)值。然后我們假設(shè)樣本數(shù)據(jù)純度越高，樣本預(yù)測(cè)值可能越接近真實(shí)值，在這種假設(shè)情況下通過(guò)式(1)純度函數(shù)purf:State→Pre評(píng)價(jià)每一個(gè)預(yù)測(cè)值的純度，基于純度高低智能選擇純度最高的預(yù)測(cè)值作為最終預(yù)測(cè)值,如式(1)。

purf(s)=-sV

(1)

為了計(jì)算方便，式(1)采用樣本的標(biāo)準(zhǔn)差作為數(shù)據(jù)純度的反向指標(biāo)。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

回歸任務(wù)的主要誤差評(píng)估標(biāo)準(zhǔn)是平均絕對(duì)誤差(MAE)和均方根誤差(RMSE)。由于事件之間的時(shí)間差值往往變化很大，大多在不同的數(shù)量級(jí)上，并且由于RMSE對(duì)異常數(shù)據(jù)點(diǎn)的錯(cuò)誤非常敏感，所以我們使用MAE對(duì)誤差進(jìn)行評(píng)估。

本文實(shí)驗(yàn)采用真實(shí)業(yè)務(wù)過(guò)程的公開(kāi)事件日志數(shù)據(jù)集，它們均可以在4TU Center for Research Data下載。日志的具體統(tǒng)計(jì)信息如表2所示。

表2 事件日志的統(tǒng)計(jì)信息

我們將實(shí)驗(yàn)日志切分為2部分，第1部分包括前2/3的軌跡，作為訓(xùn)練集；剩余1/3軌跡作為第2部分測(cè)試集。我們從大小為1的軌跡前綴開(kāi)始，預(yù)測(cè)并評(píng)估每個(gè)通過(guò)事件的剩余時(shí)間。本文將傳統(tǒng)TS方法作為基準(zhǔn)方法進(jìn)行對(duì)比,對(duì)比結(jié)果如圖2所示。

Helpdesk

(a)

(a) 基于sequence抽象的變遷系統(tǒng)

Bpi12_w

Environment permit

Sepsis

圖2顯示了本文的純度方法與傳統(tǒng)TS方法在不同前綴長(zhǎng)度上的平均絕對(duì)誤差(MAE)。從圖中可以看出，本文的純度方法在絕大多數(shù)情況下要優(yōu)于傳統(tǒng)TS方法。在實(shí)際業(yè)務(wù)過(guò)程中，本文方法可以代替人工選擇，自動(dòng)的選擇數(shù)據(jù)純度最高的抽象機(jī)制進(jìn)行剩余時(shí)間預(yù)測(cè)。并且在業(yè)務(wù)過(guò)程運(yùn)行的中后期，基于數(shù)據(jù)純度的預(yù)測(cè)方法候選空間變大，預(yù)測(cè)精度明顯提高。

5 總結(jié)

本文提出了一種基于復(fù)合變遷系統(tǒng)的業(yè)務(wù)過(guò)程剩余時(shí)間預(yù)測(cè)方法，改變了傳統(tǒng)預(yù)測(cè)方法每次預(yù)測(cè)只能使用單一抽象機(jī)制的預(yù)測(cè)方式。融合了多種抽象機(jī)制，基于觀測(cè)值的數(shù)據(jù)純度智能選擇最優(yōu)抽象機(jī)制進(jìn)行剩余時(shí)間預(yù)測(cè)。在4個(gè)公開(kāi)事件日志上進(jìn)行了實(shí)驗(yàn)，結(jié)果顯示該方法在可解釋性、預(yù)測(cè)準(zhǔn)確率方面具有一定優(yōu)勢(shì)。目前，該方法只基于觀測(cè)值的純度進(jìn)行抽象選擇，結(jié)合觀測(cè)值的樣本規(guī)?；蛟黾痈惺芤俺橄髾C(jī)制，有望進(jìn)一步提高預(yù)測(cè)的準(zhǔn)確率。