基于前綴樹的業(yè)務(wù)流程增強(qiáng)預(yù)測(cè)方法

孫大志

摘 要：預(yù)測(cè)性業(yè)務(wù)流程監(jiān)控主要利用已經(jīng)發(fā)生的流程執(zhí)行的數(shù)據(jù)，目前的主流方法是通過建立深度學(xué)習(xí)模型預(yù)測(cè)在線流程的執(zhí)行情況。現(xiàn)有的流程預(yù)測(cè)深度學(xué)習(xí)方法主要利用歷史事件日志數(shù)據(jù)來學(xué)習(xí)模型進(jìn)行預(yù)測(cè)，較少考慮日志間的行為關(guān)系，本文通過挖掘流程執(zhí)行期間日志之間的行為關(guān)系，以幫助提高預(yù)測(cè)模型的質(zhì)量。將挖掘出的日志間的行為關(guān)系使用前綴樹進(jìn)行表示，并使用現(xiàn)有的基于深度學(xué)習(xí)的業(yè)務(wù)流程預(yù)測(cè)模型，在結(jié)果預(yù)測(cè)階段通過前綴樹結(jié)構(gòu)篩選符合行為關(guān)系的預(yù)測(cè)結(jié)果提供決策支持，以此提高預(yù)測(cè)結(jié)果的精確度，并在事件日志中與基線方法進(jìn)行比對(duì)，在預(yù)測(cè)下一個(gè)活動(dòng)以及預(yù)測(cè)后綴方面，預(yù)測(cè)精度均有所提高。

關(guān)鍵詞：業(yè)務(wù)流程監(jiān)控；深度學(xué)習(xí)；信息挖掘；前綴樹；決策支持

中圖分類號(hào)：TP391.9? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2023）02-0044-06

引言

對(duì)企業(yè)而言，找到一種能夠預(yù)測(cè)業(yè)務(wù)流程的未來行為的技術(shù)非常重要，企業(yè)需要在流程實(shí)例運(yùn)行之前識(shí)別出不符合標(biāo)準(zhǔn)的異常事件，以便能夠根據(jù)相應(yīng)的信息及時(shí)找到應(yīng)對(duì)措施來避免損失，而預(yù)測(cè)性流程監(jiān)控[1]主要從事件日志中訓(xùn)練模型，用來預(yù)測(cè)一個(gè)正在進(jìn)行的案例在未來的執(zhí)行情況，可以為企業(yè)提供所需預(yù)測(cè)技術(shù)，是目前業(yè)務(wù)流程管理領(lǐng)域的一個(gè)研究熱點(diǎn)。

針對(duì)不同的預(yù)測(cè)任務(wù)，對(duì)預(yù)測(cè)性流程監(jiān)控技術(shù)的分類有所不同，現(xiàn)有預(yù)測(cè)性流程監(jiān)控技術(shù)論文主要分為三類：第一類側(cè)重于時(shí)間方面的預(yù)測(cè)，Aalst等人通過從事件日志中構(gòu)建帶注釋的變遷系統(tǒng)來預(yù)測(cè)流程的剩余時(shí)間[2]。Rogge-Solti等人使用了一種特定類型的隨機(jī)Petri網(wǎng)，它可以捕獲任意持續(xù)時(shí)間的分布，以此來預(yù)測(cè)一個(gè)案件的剩余時(shí)間[3]。Aburomman等人提出了一種新的基于向量和基于ATS的預(yù)測(cè)業(yè)務(wù)流程中的剩余時(shí)間方法，該方法考慮了與過程執(zhí)行相關(guān)的結(jié)構(gòu)特征或?qū)傩裕珙l率、重復(fù)、周期等[4]。Verenich等人將預(yù)測(cè)分解為更基本的向量，在活動(dòng)的級(jí)別上預(yù)測(cè)性能指標(biāo)，以一種透明的白盒方法預(yù)測(cè)正在進(jìn)行的過程實(shí)例的剩余周期時(shí)間。第二類側(cè)重于預(yù)測(cè)活動(dòng)的結(jié)果。這類方法目標(biāo)在于產(chǎn)生預(yù)測(cè)和建議的方法，以減少風(fēng)險(xiǎn)[5]。Conforti等人提出了一種技術(shù)，以支持過程參與者做出風(fēng)險(xiǎn)知情的決策，目的是降低過程風(fēng)險(xiǎn)。通過遍歷從過去流程執(zhí)行日志中生成的決策樹來預(yù)測(cè)風(fēng)險(xiǎn)[6]。Pika等人通過識(shí)別和利用事件日志中可觀察到的統(tǒng)計(jì)指標(biāo)來預(yù)測(cè)與時(shí)間相關(guān)的過程風(fēng)險(xiǎn)，這些指標(biāo)強(qiáng)調(diào)了超過最后期限的可能性[7]。Teinemaa等人將結(jié)構(gòu)化數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)結(jié)合以盡早預(yù)測(cè)出違約客戶無法在合理期限內(nèi)支付任何款項(xiàng)的情況[8]，Maggi等人提出了一個(gè)框架，根據(jù)給定情況下執(zhí)行過的活動(dòng)序列和案例中最后執(zhí)行過的活動(dòng)的數(shù)據(jù)屬性值來預(yù)測(cè)案例（正常與異常）的結(jié)果[1]。第三類側(cè)重于預(yù)測(cè)未來事件的延續(xù)。Lakshmanan等人提出了一個(gè)馬爾可夫預(yù)測(cè)模型來建立一個(gè)特定于實(shí)例的概率模型，該模型可以預(yù)測(cè)給定一個(gè)運(yùn)行過程實(shí)例的實(shí)例中特定事件的概率[9]。Polato等人提出了使用簡(jiǎn)單回歸、上下文信息回歸和數(shù)據(jù)感知轉(zhuǎn)換系統(tǒng)來預(yù)測(cè)剩余時(shí)間和未來活動(dòng)的序列[10]。Evermann等人提出了一個(gè)其中有兩個(gè)通過反向傳播訓(xùn)練的隱藏層的循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN）[11，12]，而Tax等人利用長(zhǎng)短期記憶（Long Short Term Memory，LSTM）和一個(gè)基于活動(dòng)和時(shí)間戳的編碼用來預(yù)測(cè)事件的延續(xù)[13]。Taymouri等人提出了一種對(duì)抗性訓(xùn)練框架通過同時(shí)訓(xùn)練兩個(gè)神經(jīng)網(wǎng)絡(luò)，一個(gè)作為生成器，一個(gè)作為鑒別器，讓他們相互對(duì)抗學(xué)習(xí)使得生成器能夠更好地解決下一個(gè)事件預(yù)測(cè)的問題[14]。Lin L等人設(shè)計(jì)了一個(gè)組件調(diào)制器來定制事件及其屬性表示的權(quán)重對(duì)于每個(gè)預(yù)測(cè)任務(wù)，使用不同的調(diào)制器同時(shí)進(jìn)行下一事件及其屬性的預(yù)測(cè)并最終預(yù)測(cè)事件序列后綴[15]。宮子優(yōu)等人使用時(shí)間卷積網(wǎng)絡(luò)將業(yè)務(wù)流程中的事件及其屬性作為輸入，在業(yè)務(wù)流程的執(zhí)行場(chǎng)景中預(yù)測(cè)流程的下一個(gè)事件和剩余流程[16]。黃曉芙等人提出了一種基于頻繁活動(dòng)集的序列編碼處理日志中的低頻活動(dòng)，并通過搜尋歷史相似數(shù)據(jù)進(jìn)行預(yù)測(cè)下一個(gè)活動(dòng)[17]。

上述預(yù)測(cè)方法都是根據(jù)已發(fā)生事件日志中活動(dòng)的執(zhí)行順序，時(shí)間戳以及已執(zhí)行活動(dòng)中的數(shù)據(jù)屬性值訓(xùn)練預(yù)測(cè)模型后進(jìn)行預(yù)測(cè)。事實(shí)上，現(xiàn)有絕大多數(shù)預(yù)測(cè)性業(yè)務(wù)流程監(jiān)控方法只考慮利用活動(dòng)以及活動(dòng)屬性值訓(xùn)練模型進(jìn)行預(yù)測(cè)，并未考慮日志中隱藏的行為信息，本文通過挖掘算法挖掘流程執(zhí)行期間日志之間的行為關(guān)系并用來提供決策支持增強(qiáng)業(yè)務(wù)流程預(yù)測(cè)質(zhì)量。

本文使用文本挖掘算法將日志活動(dòng)的行為關(guān)系用前綴樹表示，提出了一種將深度學(xué)習(xí)模型與前綴樹結(jié)合的預(yù)測(cè)方法。在訓(xùn)練好的預(yù)測(cè)模型中利用前綴樹增強(qiáng)預(yù)測(cè)正在進(jìn)行的案例的未來執(zhí)行情況。本文以LSTM模型[13]作為所提出方法的基礎(chǔ)，在四個(gè)事件日志中預(yù)測(cè)了正在執(zhí)行的案例的下一個(gè)活動(dòng)及后綴，并與基線LSTM方法進(jìn)行比較。結(jié)果表明相比只使用預(yù)測(cè)模型進(jìn)行預(yù)測(cè)的方法，使用前綴樹提供決策支持進(jìn)行增強(qiáng)業(yè)務(wù)流程預(yù)測(cè)的方法精度有所提升。

1 基本概念

定義1 跡 一個(gè)跡？滓=<-a1，a2，…，an>∈A*是一個(gè)有限的事件序列，由定義在活動(dòng)集A上的一系列活動(dòng)組成。

定義2 事件日志 一個(gè)事件日志是活動(dòng)集A上的多組跡的集合。

定義3 前綴跡 一個(gè)跡的前綴跡是它的從頭開始的子序列，例如，給定一個(gè)跡？滓=∈A*，它的長(zhǎng)度為k的前綴跡prefk（？滓）=∈A*，其中1≤k

定義4 下一活動(dòng)預(yù)測(cè) 給定一個(gè)前綴跡prefk（？滓）=∈A*以及預(yù)測(cè)函數(shù)f，則給定前綴的下一個(gè)活動(dòng)為ak+1=f（prefk（？滓））。

定義5 后綴跡 一個(gè)跡的后綴跡是其前綴跡的剩余部分的子序列，例如，給定一個(gè)跡？滓=∈A*，它的長(zhǎng)度為k的后綴跡為suffk（？滓）=∈A*。

2 業(yè)務(wù)流程預(yù)測(cè)方法

2.1 循環(huán)神經(jīng)網(wǎng)絡(luò)與LSTM

人工神經(jīng)網(wǎng)絡(luò)是一種基于模仿大腦神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)和功能而建立的一種信息處理系統(tǒng)（簡(jiǎn)稱神經(jīng)網(wǎng)絡(luò)），在分類任務(wù)中作用非常顯著[18]。人工神經(jīng)網(wǎng)絡(luò)主要架構(gòu)是由神經(jīng)元、層和網(wǎng)絡(luò)三個(gè)部分組成。整個(gè)人工神經(jīng)網(wǎng)絡(luò)包含一系列基本的神經(jīng)元、通過權(quán)重相互連接。神經(jīng)元是人工神經(jīng)網(wǎng)絡(luò)最基本的單元。單元以層的方式組，每一層的每個(gè)神經(jīng)元和前一層、后一層的神經(jīng)元連接，共分為輸入層、輸出層和隱藏層，三層連接形成一個(gè)神經(jīng)網(wǎng)絡(luò)。輸入層神經(jīng)元經(jīng)過權(quán)重加權(quán)之后得到的輸出作為隱藏層神經(jīng)元的輸入，隱藏層神經(jīng)元經(jīng)過權(quán)重加權(quán)之后得到了輸出層的輸入。輸出層經(jīng)過激活函數(shù)的激活就可以進(jìn)行分類任務(wù)的判別。其中每層神經(jīng)元加權(quán)的權(quán)重通過基于梯度的優(yōu)化進(jìn)行反向傳播從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)得到。

RNN是神經(jīng)網(wǎng)絡(luò)的其中一個(gè)子類，它的展開之后的結(jié)構(gòu)如下。

一個(gè)循環(huán)神經(jīng)網(wǎng)絡(luò)可以看作多個(gè)神經(jīng)網(wǎng)絡(luò)的連接，如虛線所示，對(duì)于任意的時(shí)間步長(zhǎng)t，在這個(gè)時(shí)間步的執(zhí)行就相當(dāng)于一次神經(jīng)網(wǎng)絡(luò)的執(zhí)行，Xt是輸入層，ht是隱藏層，yt是輸出層，此時(shí)ht包含所有時(shí)間步長(zhǎng)到t時(shí)所提取的信息。在不同的時(shí)間步中輸入不同的數(shù)據(jù)，通過當(dāng)前時(shí)間步上的隱藏狀態(tài)的激活以及輸出層的激活，得到在此時(shí)間步在各個(gè)預(yù)測(cè)活動(dòng)上的概率分布進(jìn)行分類預(yù)測(cè)。在RNN中不同時(shí)間步的權(quán)重Wh，Wx，Wy是共享的。RNN已經(jīng)被證明非常適用于序列化建模，（A.： Sequence Modeling： Recurrent and Recursive Nets.），例如，自然語(yǔ)言處理（Natural Language Processing， NLP）任務(wù)中，I like eating apple和The Apple is a great company。為apple打上標(biāo)簽，第一句中apple指代水果，而在第二句中apple指代一個(gè)公司，這種分類預(yù)測(cè)任務(wù)不僅與當(dāng)前狀態(tài)的輸入有關(guān)，同時(shí)也取決于目前已經(jīng)發(fā)生過的輸入，正常的全連接網(wǎng)絡(luò)單獨(dú)的訓(xùn)練apple這個(gè)單詞的標(biāo)簽，無法結(jié)合上下文去訓(xùn)練模型，循環(huán)神經(jīng)網(wǎng)絡(luò)可以通過不同時(shí)刻的參數(shù)共享，使得在時(shí)間步t可以獲得前面t-1個(gè)時(shí)間步的狀態(tài)信息來幫助進(jìn)行預(yù)測(cè)。現(xiàn)實(shí)任務(wù)同樣如此，下一個(gè)活動(dòng)的發(fā)生不僅取決于當(dāng)前的活動(dòng)，同時(shí)取決于先前已發(fā)生的活動(dòng)，因此，把預(yù)測(cè)任務(wù)看作是NLP任務(wù)，把跡中的每個(gè)活動(dòng)看作是NLP任務(wù)中的單詞，可以使用循環(huán)神經(jīng)網(wǎng)絡(luò)進(jìn)行序列化建模。但對(duì)于基本的RNN來說，它只能夠處理一定的短期依賴，并不能處理長(zhǎng)期依賴關(guān)系，因此通過對(duì)RNN的隱藏層網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行修改，產(chǎn)生了LSTM[19]，它與基本的RNN相比引入了輸入門、遺忘門、輸出門三種門來保持和控制信息，能夠長(zhǎng)時(shí)間保存隱藏狀態(tài)的信息，解決了RNN無法處理長(zhǎng)期依賴關(guān)系的問題。

2.2 LSTM算法實(shí)現(xiàn)

目前已有許多預(yù)測(cè)過程監(jiān)控方法使用帶有LSTM單元的RNN。本文采用Tax等人提出的LSTM方法[13]，它的執(zhí)行方法依賴于活動(dòng)序列編碼，使用最為常用的one-hot編碼，對(duì)于一個(gè)給定的活動(dòng)集合A={a，b，c，d}，需要?jiǎng)?chuàng)建一個(gè)索引函數(shù)，確定活動(dòng)在集合中所處的位置，索引函數(shù)為index： A={a，b，c，d}，有index（a）=1，即活動(dòng)a在集合A中所處位置為第1個(gè)，活動(dòng)b在集合A中所處位置為第2個(gè)。對(duì)活動(dòng)序列進(jìn)行編碼時(shí)，為每個(gè)活動(dòng)ai∈？滓創(chuàng)建一個(gè)長(zhǎng)度為|A|的向量Ai，當(dāng)前活動(dòng)所處的索引值位置為1，其他位置均為0。跡的編碼方式將跡中所有活動(dòng)獲得的向量組合成一個(gè)矩陣。訓(xùn)練階段，使用編碼好的跡訓(xùn)練LSTM模型，預(yù)測(cè)階段，使用一個(gè)正在進(jìn)行的活動(dòng)序列（進(jìn)行one-hot編碼）進(jìn)行預(yù)測(cè)監(jiān)控。具體算法如下：

該算法輸入一個(gè)已經(jīng)訓(xùn)練好的LSTM模型，一個(gè)給定的最大迭代次數(shù)max，以及一個(gè)正在進(jìn)行的活動(dòng)序列prefk（？滓），通過迭代的預(yù)測(cè)下一個(gè)活動(dòng)來預(yù)測(cè)后綴，當(dāng)max=1的時(shí)候只迭代一次，即預(yù)測(cè)當(dāng)前活動(dòng)序列的下一個(gè)活動(dòng)，max>1進(jìn)行后綴預(yù)測(cè)。

3 使用前綴樹增強(qiáng)預(yù)測(cè)方法

預(yù)測(cè)性業(yè)務(wù)過程監(jiān)控使用存儲(chǔ)在事件日志中的過去的跡來構(gòu)建模型對(duì)未來進(jìn)行預(yù)測(cè)，在某些場(chǎng)景非常有用，例如在醫(yī)療場(chǎng)景中，需已知患者執(zhí)行了哪些活動(dòng)從而對(duì)患者進(jìn)行下一步的治療方案進(jìn)行決策，但現(xiàn)實(shí)中進(jìn)行后續(xù)序列預(yù)測(cè)仍然存在很大的挑戰(zhàn)，隨著活動(dòng)事件持續(xù)發(fā)生，預(yù)測(cè)后面序列越發(fā)困難，現(xiàn)有方法只考慮使用歷史事件日志中的跡訓(xùn)練深度學(xué)習(xí)預(yù)測(cè)模型，并利用訓(xùn)練完成的模型預(yù)測(cè)未來活動(dòng)的序列，忽略了歷史事件日志中隱藏的行為關(guān)系。通過挖掘日志間的行為關(guān)系以流程圖、前綴樹、后綴樹等形式進(jìn)行表達(dá)，并結(jié)合深度學(xué)習(xí)預(yù)測(cè)模型可以幫助預(yù)測(cè)模型提高未知事件預(yù)測(cè)的質(zhì)量。

3.1 從跡中學(xué)習(xí)

對(duì)歷史事件日志的跡挖掘信息有多種方式，第一種為流程挖掘方法，通過流程挖掘方法獲得活動(dòng)的流程圖，常見的幾種流程圖類型如下：（1）Petri nets（也叫petri網(wǎng)）；（2）流程樹（Process Tree，PT）；（3）業(yè)務(wù)流程建模標(biāo)記（Business Process Modeling Notation，BPMN）；（4）直接跟隨圖（Directly Follow Graph，DFG）。上述方法能夠展現(xiàn)活動(dòng)之間的直接跟隨關(guān)系。對(duì)于Petri nets，流程樹以及BPMN模型，不僅可以確定活動(dòng)間的直接跟隨關(guān)系，同時(shí)可以展現(xiàn)活動(dòng)之間的行為輪廓關(guān)系，例如兩個(gè)活動(dòng)之間相互排斥，兩個(gè)活動(dòng)相互嚴(yán)格順序執(zhí)行以及兩個(gè)活動(dòng)是并發(fā)執(zhí)行，已知兩個(gè)活動(dòng)a和b是并發(fā)的，即a發(fā)生b一定發(fā)生，發(fā)生的順序不定，預(yù)測(cè)時(shí)利用行為輪廓關(guān)系剔除不符合活動(dòng)關(guān)系的跡，從而使得預(yù)測(cè)結(jié)果更貼近真實(shí)的結(jié)果，這些行為輪廓關(guān)系不止可以為深度學(xué)習(xí)模型預(yù)測(cè)提供決策支持，同時(shí)可考慮在訓(xùn)練模型階段將行為輪廓關(guān)系編碼作為輸入屬性進(jìn)行預(yù)測(cè)模型的訓(xùn)練，這些工作在未來是我們嘗試的方向。

第二種信息挖掘方式為數(shù)據(jù)挖掘，本文基礎(chǔ)LSTM算法即是數(shù)據(jù)挖掘主要方法中的一類，屬于預(yù)測(cè)模型方法，其余預(yù)測(cè)模型算法包括決策樹、支持向量機(jī)等。

第三種信息挖掘方式為文本挖掘，文本挖掘是從非結(jié)構(gòu)化的文本信息中抽取潛在的、用戶感興趣的重要模式或知識(shí)的過程，文本挖掘的主要研究?jī)?nèi)容包括關(guān)聯(lián)分析、文本分類、文本聚類。轉(zhuǎn)換一下思路，把事件日志看作文檔，把跡看作文本中的字符串，可以使用文本數(shù)據(jù)挖掘相應(yīng)的信息，本文的想法把跡看作字符串，使用字典樹（也稱前綴樹）進(jìn)行儲(chǔ)存。字典樹是一種字符串上的樹型數(shù)據(jù)結(jié)構(gòu)，在NLP中使用非常廣泛，在NLP任務(wù)中，預(yù)測(cè)一句話的下一個(gè)單詞需要此時(shí)所有已經(jīng)發(fā)生過的單詞即前綴，通過已知的前綴預(yù)測(cè)下一個(gè)可能的單詞。前綴樹支持有效的字符串匹配和查詢，結(jié)構(gòu)如下，下圖展示使用abb，abc，bca，bacd，bacc字符串這幾個(gè)字符串來構(gòu)建的前綴樹，該方法可以用作文本匹配，也可以清晰看出給定前綴的所有能夠執(zhí)行的后綴。

3.2 預(yù)測(cè)增強(qiáng)算法實(shí)現(xiàn)

本文使用文本挖掘算法將歷史事件日志的行為關(guān)系用前綴樹表示，結(jié)合深度學(xué)習(xí)預(yù)測(cè)模型，為預(yù)測(cè)模型提供決策支持，并在真實(shí)事件日志上進(jìn)行了實(shí)驗(yàn)。算法2介紹了提出方法的偽代碼，該算法在算法1的基礎(chǔ)上得到，運(yùn)用了前綴樹為L(zhǎng)STM模型提供決策支持增強(qiáng)預(yù)測(cè)。算法如下，此時(shí)的輸入為正在進(jìn)行的跡、訓(xùn)練好的LSTM模型以及預(yù)測(cè)最大迭代次數(shù)，同時(shí)需要給定預(yù)測(cè)候選活動(dòng)的最大個(gè)數(shù)k。

對(duì)于上述方法，在預(yù)測(cè)階段同時(shí)預(yù)測(cè)前k個(gè)概率最大的活動(dòng)，與跡進(jìn)行拼接產(chǎn)生多個(gè)候選跡，按照概率大小對(duì)跡進(jìn)行排序，將候選跡放入前綴樹中重演，能夠重演說明選取的跡在前綴樹中真實(shí)存在，將該跡作為預(yù)測(cè)結(jié)果進(jìn)行下一個(gè)預(yù)測(cè)，無法重演說明當(dāng)前跡在歷史日志中并未發(fā)生，舍棄當(dāng)前預(yù)測(cè)結(jié)果，從候選跡中選取概率次之的跡進(jìn)行判斷，直到找到確定符合前綴樹的跡，把當(dāng)前跡作為預(yù)測(cè)輸入進(jìn)行下一次預(yù)測(cè)直到預(yù)測(cè)結(jié)束。

4 實(shí)驗(yàn)與結(jié)果評(píng)估

4.1 事件日志

本文采用四個(gè)真實(shí)的事件來評(píng)估提出的方法的可行性，其中BP12W和BP13是來自于BPIC（業(yè)務(wù)流程智能競(jìng)賽）12年和13年提供的事件日志，BP12W-no-repeat是對(duì)BP12-W事件日志處理后的事件日志，該事件日志是清洗掉循環(huán)后的日志，Helpdesk是某公司的幫助臺(tái)的票務(wù)管理后臺(tái)記錄的日志。這些事件日志已經(jīng)被過濾過。這些事件日志數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)見下表：

4.2 實(shí)驗(yàn)設(shè)置與評(píng)估方法

本文實(shí)驗(yàn)環(huán)境在Windows10系統(tǒng)中使用Python3.7語(yǔ)言，并使用Keras深度學(xué)習(xí)庫(kù)。對(duì)于LSTM的參數(shù)設(shè)置，使用了和Tax論文中一樣的設(shè)置。同時(shí)對(duì)數(shù)據(jù)集進(jìn)行劃分，其中67%的跡作為訓(xùn)練集用于構(gòu)建LSTM模型，剩余的33%作為測(cè)試集用來做測(cè)試。預(yù)測(cè)下一個(gè)活動(dòng)時(shí)，需要對(duì)所有前綴進(jìn)行預(yù)測(cè)，對(duì)于不同的數(shù)據(jù)集，本文僅選取了一些前綴長(zhǎng)度進(jìn)行展示，在Helpdesk數(shù)據(jù)集中，k∈{2，4，6}，BPIC12W數(shù)據(jù)集中k∈{2，4，6，8，10，15， 20，25，30，35，40}，BPIC12W（no duplicates）數(shù)據(jù)集中k∈{2，4，6，8}以及BPIC13數(shù)據(jù)集中k∈{2，4， 6，8，10，15，20，25，30}。在預(yù)測(cè)后綴任務(wù)中，只需要選取一個(gè)大于2的前綴長(zhǎng)度進(jìn)行測(cè)試即可，本文選取了四個(gè)前綴長(zhǎng)度進(jìn)行測(cè)試，k∈{2，3，4，5}。

為了評(píng)估預(yù)測(cè)下一個(gè)活動(dòng)標(biāo)簽的準(zhǔn)確性，使用準(zhǔn)確率來作為衡量指標(biāo)，它是指正確預(yù)測(cè)占預(yù)測(cè)總數(shù)的比例。

其中TP為正確預(yù)測(cè)的個(gè)數(shù)，F(xiàn)P為錯(cuò)誤預(yù)測(cè)的個(gè)數(shù)。

為了衡量后綴生成的質(zhì)量，使用基于Damerau-Levenstein距離（DL distance）的相似度來比較生成的后綴和真實(shí)跡后綴之間的相似度。Damerau–Levenshtein Distance用來測(cè)量?jī)蓚€(gè)字符序列之間的編輯距離的字符串度量標(biāo)準(zhǔn)。兩個(gè)詞的Damerau–Levenshtein Distance是從一個(gè)詞轉(zhuǎn)換為另一個(gè)詞的最少操作數(shù)，與Levenshtein Distance不同的是，除了單個(gè)字符的插入、刪除和變更之外，還包括兩個(gè)相鄰字符的轉(zhuǎn)換。對(duì)于兩個(gè)序列給定序列s1，s2，它們的相似度為

其中l(wèi)en（s）代表序列的長(zhǎng)度，Sim越大說明兩個(gè)序列越像，Sim=1說明兩個(gè)序列完全相同，反之Sim=0說明兩個(gè)序列沒有相似的地方，是完全不同的。

4.3 結(jié)果與討論

下一個(gè)活動(dòng)預(yù)測(cè)：表2報(bào)告了使用前綴樹增強(qiáng)預(yù)測(cè)的方法與基線方法在四個(gè)事件日志中的加權(quán)平均準(zhǔn)確率，與基線進(jìn)行對(duì)比，使用前綴樹增強(qiáng)預(yù)測(cè)方法提高了總體的預(yù)測(cè)準(zhǔn)確率，在循環(huán)次數(shù)較少的事件日志中，如Helpdesk以及BPIC12W（no duplicates），增強(qiáng)預(yù)測(cè)方法具有更高的提升。圖3展示了基線方法與使用前綴樹增強(qiáng)預(yù)測(cè)方法在預(yù)測(cè)的不同前綴上預(yù)測(cè)下一個(gè)活動(dòng)的準(zhǔn)確率，結(jié)果表明使用前綴樹增強(qiáng)預(yù)測(cè)獲得的準(zhǔn)確率始終在基線算法之上，最差也與基線算法準(zhǔn)確率相同。產(chǎn)生此結(jié)果的原因是在前綴樹的決策支持中，將會(huì)使得不符合活動(dòng)間行為關(guān)系的跡無法產(chǎn)生，確保了預(yù)測(cè)結(jié)果滿足活動(dòng)間的行為關(guān)系，從而增強(qiáng)了預(yù)測(cè)的準(zhǔn)確率。

活動(dòng)后綴預(yù)測(cè)：表3總結(jié)了每個(gè)日志的后綴預(yù)測(cè)結(jié)果，使用前綴樹增強(qiáng)預(yù)測(cè)方法與基線方法相比相對(duì)在各個(gè)日志上都有所提高，在循環(huán)次數(shù)較高的日志上提升明顯，如BPIC12W和BPIC13，這是因?yàn)樵陬A(yù)測(cè)后綴時(shí)循環(huán)的存在可能會(huì)導(dǎo)致產(chǎn)生的后綴結(jié)果一直處在循環(huán)之中，使得后綴長(zhǎng)度增長(zhǎng)同時(shí)數(shù)據(jù)不斷增長(zhǎng)，基于前綴樹增強(qiáng)預(yù)測(cè)方法避免跡的無限增長(zhǎng)，當(dāng)不斷循環(huán)的跡不再符合活動(dòng)間的行為關(guān)系時(shí)，及時(shí)的結(jié)束預(yù)測(cè)，從而提高了預(yù)測(cè)后綴結(jié)果的相似度，但是并沒有真正解決循環(huán)問題，未來如何以一種較好的方式在合適的位置結(jié)束循環(huán)仍然是繼續(xù)研究的方向。

5 結(jié)語(yǔ)

本文提出一種將使用深度學(xué)習(xí)模型與前綴樹結(jié)合的預(yù)測(cè)方法，在對(duì)歷史事件日志學(xué)習(xí)預(yù)測(cè)模型之外，對(duì)歷史事件日志進(jìn)行了信息挖掘，將日志中的行為關(guān)系通過前綴樹表示，在結(jié)果預(yù)測(cè)階段通過前綴樹結(jié)構(gòu)篩選符合行為關(guān)系的預(yù)測(cè)結(jié)果提供決策支持，以此提高預(yù)測(cè)的精確度。在四個(gè)事件日志上的結(jié)果表明，利用表示日志中行為關(guān)系的前綴樹來增強(qiáng)預(yù)測(cè)的精確度是有效果的，因此在現(xiàn)實(shí)中進(jìn)行預(yù)測(cè)監(jiān)控時(shí)，可以通過挖掘日志中隱藏的行為關(guān)系來提高預(yù)測(cè)精度。未來的工作有以下幾個(gè)方向：（1）繼續(xù)結(jié)合預(yù)測(cè)模型與挖掘出的活動(dòng)關(guān)系，嘗試將活動(dòng)之間的行為輪廓關(guān)系，如選擇關(guān)系，并發(fā)關(guān)系作為額外信息在模型之外增強(qiáng)預(yù)測(cè)。（2）將活動(dòng)之間的行為關(guān)系作為屬性在訓(xùn)練預(yù)測(cè)模型時(shí)使用。（3）以一種合理的方式解決后綴中的循環(huán)。

——————————

參考文獻(xiàn)：

〔1〕Maggi F M， Francescomarino C D， Dumas M， et al. Predictive monitoring of business processes[C]//International conference on advanced information systems engineering. Cham， Switzerland：Springer， 2014： 457-472.

〔2〕Van der Aalst W M P， Schonenberg M H， Song M. Time prediction based on process mining[J]. Information systems， 2011， 36（02）： 450-475.

〔3〕Rogge-Solti A， Weske M. Prediction of business process durations using non-Markovian stochastic Petri nets[J]. Information Systems， 2015， 54： 1-14.

〔4〕Aburomman A， Lama M， Bugarín-Diz A. Estimating Remaining Time of Business Processes with structural attributes of the traces[M]//Computational Intelligence and Mathematics for Tackling Complex Problems 2. Cham， Switzerland：Springer， 2022： 47-54.

〔5〕Verenich I， Dumas M， La Rosa M， et al. Predicting process performance： A white‐box approach based on process models[J]. Journal of Software： Evolution and Process， 2019， 31（06）.

〔6〕Conforti R， Leoni M， Rosa M L， et al. Supporting risk-informed decisions during business process execution[C]//International Conference on Advanced Information Systems Engineering. Berlin， Heidelberg： Springer， 2013： 116-132.

〔7〕Pika A， van der Aalst W M P， Fidge C J， et al. Predicting deadline transgressions using event logs[C]//International Conference on Business Process Management. Berlin，Heidelberg： Springer， 2012： 211-216.

〔8〕Teinemaa I， Dumas M， Maggi F M， et al. Predictive business process monitoring with structured and unstructured data[C]//International Conference on Business Process Management. Cham， Switzerland：Springer， 2016： 401-417.

〔9〕Lakshmanan G T， Shamsi D， Doganata Y N， et al. A markov prediction model for data-driven semi-structured business processes[J]. Knowledge and Information Systems， 2015， 42（01）： 97-126.

〔10〕Polato M， Sperduti A， Burattin A， et al. Time and activity sequence prediction of business process instances[J]. Computing， 2018， 100（09）： 1005-1031.

〔11〕Evermann J， Rehse J R， Fettke P. A deep learning approach for predicting process behaviour at runtime[C]//International Conference on Business Process Management. Cham， Switzerland：Springer ， 2016： 327-338.

〔12〕Evermann J， Rehse J R， Fettke P. Predicting process behaviour using deep learning[J]. Decision Support Systems， 2017， 100： 129-140.

〔13〕Tax N， Verenich I， Rosa M L， et al. Predictive business process monitoring with LSTM neural networks[C]//International Conference on Advanced Information Systems Engineering. Cham， Switzerland：Springer， 2017： 477-492.

〔14〕Taymouri F， Rosa M L， Erfani S， et al. Predictive business process monitoring via generative adversarial nets： the case of next event prediction[C]//International Conference on Business Process Management. Cham， Switzerland：Springer ， 2020： 237-256.

〔15〕Lin L， Wen L， Wang J. Mm-pred： A deep predictive model for multi-attribute event sequence[C]//Proceedings of the 2019 SIAM international conference on data mining. Philadelphia：Society for Industrial and Applied Mathematics， 2019： 118-126.

〔16〕宮子優(yōu)，方賢文.基于時(shí)間卷積網(wǎng)絡(luò)的業(yè)務(wù)流程預(yù)測(cè)監(jiān)控[J].安徽理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，41（05）：64-70.

〔17〕黃曉芙，曹健，譚煜東.基于頻繁活動(dòng)集序列編碼業(yè)務(wù)過程預(yù)測(cè)性監(jiān)控[J].北京郵電大學(xué)學(xué)報(bào)，2019，42（04）：1-7.

〔18〕韓力群，施彥.人工神經(jīng)網(wǎng)絡(luò)理論及應(yīng)用[M].北京：機(jī)械工業(yè)出版社，2017.

〔19〕Schmidhuber J， Hochreiter S. Long short-term memory[J]. Neural Comput， 1997， 9（08）： 1735-1780.

收稿日期：2022-09-27

基金項(xiàng)目：國(guó)家自然科學(xué)基金（61402011）