劉云峰， 高俊濤

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

0 引言

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

1 研究現(xiàn)狀

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

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

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

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

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

2 基本概念

2.1 算法基礎(chǔ)概念

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

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

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

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

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

表1 事件日志片段

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

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

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

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

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

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

算法1 基于數(shù)據(jù)純度的剩余時間預(yù)測算法輸入:預(yù)測模型M,前綴軌跡θ輸出:剩余時間預(yù)測值^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ù)測只能使用一種抽象機制，而且在實際業(yè)務(wù)過程中需要根據(jù)人工經(jīng)驗來判斷選擇哪種抽象機制，這與智能制造的宗旨不符。因此,本文將實際業(yè)務(wù)過程中的部分已知軌跡θ在預(yù)測模型M中根據(jù)歷史相似數(shù)據(jù)進行匹配，記錄下每個匹配成功的結(jié)果作為備選預(yù)測值。然后我們假設(shè)樣本數(shù)據(jù)純度越高，樣本預(yù)測值可能越接近真實值，在這種假設(shè)情況下通過式(1)純度函數(shù)purf:State→Pre評價每一個預(yù)測值的純度，基于純度高低智能選擇純度最高的預(yù)測值作為最終預(yù)測值,如式(1)。

purf(s)=-sV

(1)

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

4 實驗設(shè)計與分析

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

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

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

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

Helpdesk

(a)

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

Bpi12_w

Environment permit

Sepsis

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

5 總結(jié)

本文提出了一種基于復(fù)合變遷系統(tǒng)的業(yè)務(wù)過程剩余時間預(yù)測方法，改變了傳統(tǒng)預(yù)測方法每次預(yù)測只能使用單一抽象機制的預(yù)測方式。融合了多種抽象機制，基于觀測值的數(shù)據(jù)純度智能選擇最優(yōu)抽象機制進行剩余時間預(yù)測。在4個公開事件日志上進行了實驗，結(jié)果顯示該方法在可解釋性、預(yù)測準確率方面具有一定優(yōu)勢。目前，該方法只基于觀測值的純度進行抽象選擇，結(jié)合觀測值的樣本規(guī)模或增加感受野抽象機制，有望進一步提高預(yù)測的準確率。