基于軌跡聚類的業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)方法

徐興榮，張帥鵬，李 婷，郭 娜，董樂樂，劉 聰，2，任崇廣

（1.山東理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東淄博 255000；2.同濟(jì)大學(xué)嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室，上海 200092）

0 概述

預(yù)測(cè)型流程監(jiān)控［1］作為業(yè)務(wù)流程管理領(lǐng)域中的主要研究?jī)?nèi)容，旨在對(duì)當(dāng)前正在運(yùn)行的流程實(shí)例進(jìn)行有效地分析，從而預(yù)測(cè)在今后一段時(shí)間內(nèi)流程實(shí)例出現(xiàn)的行為狀態(tài)，例如可能發(fā)生的活動(dòng)、實(shí)例所需的執(zhí)行時(shí)間等［2］。相較于現(xiàn)有監(jiān)控形式的方法，預(yù)測(cè)型流程監(jiān)控是在過程感知信息系統(tǒng)的基礎(chǔ)上對(duì)歷史數(shù)據(jù)加以記錄［3］，不僅能有效規(guī)避偏差、信息缺失等風(fēng)險(xiǎn)，而且還可以防止因流程實(shí)例持續(xù)執(zhí)行而帶來資源沖突等情況的發(fā)生。

業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)［4］作為預(yù)測(cè)型流程監(jiān)控中重要的預(yù)測(cè)任務(wù)，采用合理的方式準(zhǔn)確預(yù)測(cè)流程實(shí)例需要執(zhí)行的剩余時(shí)間。而傳統(tǒng)的剩余時(shí)間預(yù)測(cè)方法是基于業(yè)務(wù)系統(tǒng)中產(chǎn)生的事件日志挖掘形式化變遷系統(tǒng)［5］、隨機(jī)Petri 網(wǎng)［6］等可描述模型，并通過該模型對(duì)剩余時(shí)間進(jìn)行有針對(duì)性的預(yù)測(cè)。隨著深度學(xué)習(xí)技術(shù)的發(fā)展，研究人員將其與剩余時(shí)間預(yù)測(cè)相結(jié)合，并取得較優(yōu)的預(yù)測(cè)效果，特別是文獻(xiàn)［7］提出的預(yù)測(cè)方法，相較于傳統(tǒng)方法的預(yù)測(cè)效果得到顯著提升。

軌跡聚類利用相似性度量方式對(duì)事件日志中的軌跡進(jìn)行分組，以更好地發(fā)現(xiàn)過程模型［8］。在軌跡聚類中使用的相似性度量因結(jié)構(gòu)相似性和性能相似性不同而異［9］，同時(shí)不同集群會(huì)為結(jié)構(gòu)和行為變化提供更加細(xì)致的表示。此外，軌跡聚類還可以有效減少事件日志中冗余數(shù)據(jù)，從而降低事件日志復(fù)雜度［10］。

為降低異質(zhì)事件日志（如多變體、多流程實(shí)例）對(duì)業(yè)務(wù)流程剩余時(shí)間［11］預(yù)測(cè)準(zhǔn)確度的影響，本文利用聚類方式為異質(zhì)事件日志中不同長(zhǎng)度的軌跡建立集群，以降低事件日志復(fù)雜度及細(xì)化結(jié)構(gòu)，同時(shí)設(shè)計(jì)基于注意力機(jī)制的卷積準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)（Convolutional Quasi-Recurrent Neural Network，CQRNN）模型，有效地捕獲對(duì)剩余時(shí)間預(yù)測(cè)任務(wù)有決定性影響的時(shí)間和空間特征信息，進(jìn)一步改進(jìn)剩余時(shí)間預(yù)測(cè)效果。

1 相關(guān)工作

1.1 聚類方法

在預(yù)測(cè)型流程監(jiān)控任務(wù)中，異質(zhì)事件日志會(huì)影響業(yè)務(wù)流程剩余時(shí)間的預(yù)測(cè)效果，而合理的聚類方法在一定程度上可以解決該問題。文獻(xiàn)［12］利用聚類方法在事件日志中檢測(cè)業(yè)務(wù)流程存在的變種，通過回歸技術(shù)在不同變種流程實(shí)例上構(gòu)建剩余時(shí)間預(yù)測(cè)模型。文獻(xiàn)［13］提出一種數(shù)據(jù)與聚類相結(jié)合的方法用于預(yù)測(cè)剩余時(shí)間，該方法主要是根據(jù)邏輯規(guī)則來表示聚類模型，以加強(qiáng)對(duì)上下文分析的適應(yīng)能力。文獻(xiàn)［14］提出利用聚類方法為業(yè)務(wù)流程場(chǎng)景配備預(yù)測(cè)模型的流程挖掘算法，以預(yù)測(cè)業(yè)務(wù)流程剩余時(shí)間。文獻(xiàn)［15］構(gòu)建預(yù)測(cè)型流程監(jiān)控框架，該框架首先根據(jù)控制流信息對(duì)事件日志中的軌跡進(jìn)行聚類，然后針對(duì)每個(gè)集群建立不同的分類器，最后將正在運(yùn)行的案例映射到集群并應(yīng)用相應(yīng)的分類器進(jìn)行剩余時(shí)間預(yù)測(cè)。文獻(xiàn)［16］提出以聚類為基礎(chǔ)的原因分析方法，該方法對(duì)事件日志進(jìn)行預(yù)處理，并對(duì)其進(jìn)行聚類，同時(shí)通過決策樹檢測(cè)事件日志中檢索超時(shí)故障的原因，其中事件日志包含時(shí)間、延遲等豐富信息。文獻(xiàn)［17］提出將事件日志分組到同質(zhì)子集的方法，該方法利用聚類捕獲過程模型，在過程模型中構(gòu)建預(yù)測(cè)器，從而對(duì)業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)進(jìn)行有針對(duì)性的預(yù)測(cè)。

1.2 業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)方法

業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)方法［11］有助于企業(yè)開展流程控制以及傳遞高質(zhì)量服務(wù)，因此受到國(guó)內(nèi)外研究人員的廣泛關(guān)注。文獻(xiàn)［4］提出基于變遷系統(tǒng)的剩余時(shí)間預(yù)測(cè)方法，該方法主要是在事件日志中挖掘變遷系統(tǒng)，通過變遷系統(tǒng)記錄流程實(shí)例可能發(fā)生的狀態(tài)，利用流程實(shí)例的狀態(tài)預(yù)測(cè)剩余時(shí)間。文獻(xiàn)［6］是在事件日志中挖掘Petri 網(wǎng)，利用Petri 網(wǎng)模擬當(dāng)前流程實(shí)例執(zhí)行的狀況，根據(jù)結(jié)果預(yù)測(cè)剩余時(shí)間。然而，由于傳統(tǒng)流程挖掘方法存在一定的局限性，因此在處理大量事件日志時(shí)不能很好地展現(xiàn)出預(yù)測(cè)效果。隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展，其被有效地應(yīng)用到業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)中。文獻(xiàn)［18］在文獻(xiàn)［4］的基礎(chǔ)上提出數(shù)據(jù)感知變遷系統(tǒng)，在該系統(tǒng)中是采用樸素貝葉斯分類方式為各個(gè)狀態(tài)節(jié)點(diǎn)建立模型，同時(shí)，利用支持向量機(jī)進(jìn)行剩余時(shí)間預(yù)測(cè)。文獻(xiàn)［19］將業(yè)務(wù)流程抽象為流程樹，并在每個(gè)流程樹的節(jié)點(diǎn)上訓(xùn)練回歸模型以預(yù)測(cè)剩余時(shí)間。近年來，在深度學(xué)習(xí)技術(shù)得到大范圍應(yīng)用的背景下，研究人員將長(zhǎng)短期記憶網(wǎng)絡(luò)作為剩余時(shí)間預(yù)測(cè)任務(wù)中的關(guān)鍵方法。文獻(xiàn)［20］利用長(zhǎng)短期記憶神經(jīng)網(wǎng)絡(luò)和嵌入方式對(duì)變量進(jìn)行分類，進(jìn)而實(shí)現(xiàn)對(duì)業(yè)務(wù)流程剩余時(shí)間的預(yù)測(cè)。文獻(xiàn)［21］采用生成對(duì)抗網(wǎng)絡(luò)在生成事件后綴的同時(shí)預(yù)測(cè)業(yè)務(wù)流程的剩余時(shí)間。文獻(xiàn)［22］設(shè)計(jì)一種基于注意力機(jī)制的高級(jí)表示學(xué)習(xí)方法，解決業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)中不能很好地捕捉輸入序列長(zhǎng)期依賴關(guān)系，達(dá)到對(duì)業(yè)務(wù)流程剩余時(shí)間有效預(yù)測(cè)的目標(biāo)。

2 預(yù)備知識(shí)

2.1 基本概念

本文介紹與業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)相關(guān)的基本概念，并給出形式化描述。

定義1（事件）事件是業(yè)務(wù)系統(tǒng)中活動(dòng)的運(yùn)行實(shí) 例，以多元組e=｛Caseid，a，Time，p｛1，2，…，n｝｝表 示。其中：Caseid 為事件所屬案例的ID；a為事件執(zhí)行活動(dòng)的名稱；Time 為事件執(zhí)行時(shí)間，即Time=事件結(jié)束時(shí)間EndTime-事件開始時(shí)間StartTime；p｛1，2，…，n｝為事件其余屬性，包括資源、執(zhí)行代價(jià)等信息。

定義2（軌跡）軌跡是一個(gè)非空且有限的事件序列，表示為σ=｛e1，e2，…，e|σ|｝（1 ≤i≤|σ|）。其中：ei表示第i個(gè)事件；|σ|表示軌跡σ中事件數(shù)量。

定義3（軌跡前綴）軌跡前綴是軌跡σ中前U個(gè)事件，記作σ（U）?｛e1，e2，…，eU｝。

定義4（軌跡前綴剩余時(shí)間）軌跡前綴剩余時(shí)間是軌跡σ中未執(zhí)行事件e的執(zhí)行時(shí)間總和，可以表示為RT（σ（U））=eU+1.Time+eU+2.Time+…+e|σ|.Time。

定義5（流程實(shí)例）流程實(shí)例是業(yè)務(wù)系統(tǒng)從開始到結(jié)束一次有效的運(yùn)行過程，以元組Q=｛Cid，σ，q｛1，2，…，m｝｝表示。其中：Cid 表示軌跡σ的案例ID；σ表示流程實(shí)例中的軌跡；q｛1，2，…，m｝表示流程實(shí)例中其他屬性。

定義6（事件日志）事件日志描述了業(yè)務(wù)系統(tǒng)歷史運(yùn)行情況，以L=｛Q1，Q2，…，Q|l|｝表示。

定義7（剩余時(shí)間預(yù)測(cè)）在業(yè)務(wù)系統(tǒng)中，假設(shè)事件空間為T，則軌跡和軌跡前綴空間記為T*，剩余時(shí)間預(yù)測(cè)旨在利用映射函數(shù)對(duì)軌跡前綴剩余時(shí)間進(jìn)行預(yù)測(cè)，即f=T* →R+。

本文僅關(guān)注流程實(shí)例中軌跡基本信息（即事件、活動(dòng)、執(zhí)行時(shí)間），并開展剩余時(shí)間預(yù)測(cè)任務(wù)。

2.2 業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)

本文在利用深度學(xué)習(xí)技術(shù)開展業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)時(shí)，可分為訓(xùn)練階段和應(yīng)用階段。訓(xùn)練階段的主要目標(biāo)是通過事件日志中詳細(xì)描述的歷史流程實(shí)例對(duì)剩余時(shí)間預(yù)測(cè)函數(shù)f進(jìn)行學(xué)習(xí)，應(yīng)用階段則是利用訓(xùn)練階段獲得的函數(shù)f對(duì)業(yè)務(wù)流程中流程實(shí)例（即軌跡前綴）的剩余執(zhí)行時(shí)間進(jìn)行預(yù)測(cè)。

在訓(xùn)練階段，需將事件日志L轉(zhuǎn)化為深度學(xué)習(xí)可使用的數(shù)據(jù)集。因此，本文利用軌跡聚類的方式將事件日志L劃分為不同集群（集群內(nèi)部軌跡相似，不同集群軌跡不相似），在集群中設(shè)定截取軌跡前綴范圍u∈N*，并將其作為訓(xùn)練集，如式（1）和式（2）所示：

應(yīng)用階段是利用生成的訓(xùn)練數(shù)據(jù)集DCluster對(duì)業(yè)務(wù)流程剩余時(shí)間模型f進(jìn)行學(xué)習(xí)，為了防止出現(xiàn)過擬合的現(xiàn)象，利用正則項(xiàng)的方式加以克服，如式（3）所示：

3 基于軌跡聚類的剩余時(shí)間預(yù)測(cè)方法

本文提出的基于軌跡聚類的剩余時(shí)間預(yù)測(cè)方法流程如圖1 所示。

圖1 本文方法流程Fig.1 Procedure of the proposed method

該方法采用軌跡間相似度的聚類方式為事件日志建立Cluster｛1，2，…，n｝集群，根據(jù)式（1）和式（2）對(duì)Cluster｛1，2，…，n｝集群設(shè)定所要截取的軌跡前綴范圍，并生成訓(xùn)練數(shù)據(jù)集｛1，2，…，n｝，將生成的訓(xùn)練數(shù)據(jù)集｛1，2，…，n｝依次輸入到基于注意力機(jī)制的卷積準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)中進(jìn)行迭代訓(xùn)練，獲得Cluster｛1，2，…，n｝各集群的剩余時(shí)間，并將結(jié)果加權(quán)平均，從而得到最終剩余時(shí)間。本文將該方法應(yīng)用于業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)后，剩余時(shí)間預(yù)測(cè)效果得到顯著提升。

3.1 軌跡聚類

在過程挖掘領(lǐng)域中，已有很多文獻(xiàn)提出不同的軌跡聚類方法，而大多數(shù)軌跡聚類方法是基于數(shù)據(jù)挖掘聚類方法對(duì)事件日志進(jìn)行更深入的轉(zhuǎn)換與處理，通過已有的聚類方法開展有效的聚類任務(wù)。現(xiàn)有軌跡聚類方法分為3 類：1）向量空間方法，將事件日志中具有代表性的特征向量化，并抽象為特征矩陣，利用傳統(tǒng)距離度量計(jì)算事件日志中軌跡之間的距離，同時(shí)，通過傳統(tǒng)聚類方法進(jìn)行軌跡聚類；2）上下文感知的軌跡聚類，在當(dāng)前軌跡聚類方法的基礎(chǔ)上以上下文感知的方式對(duì)其進(jìn)行補(bǔ)充與擴(kuò)展；3）基于模型的序列聚類，利用過程模型對(duì)事件日志中的軌跡進(jìn)行聚類處理。因此，本文使用上述3 種代表性的軌跡聚類方法對(duì)業(yè)務(wù)流程信息系統(tǒng)產(chǎn)生的事件日志進(jìn)行處理，從而比較不同軌跡聚類方法對(duì)剩余時(shí)間預(yù)測(cè)結(jié)果影響的差異性。

3.1.1 向量空間方法

文獻(xiàn)［23］提出向量空間的概念，將軌跡中的活動(dòng)構(gòu)建成活動(dòng)向量空間模型，保證聚類事件日志中的相似軌跡處于同一集群中，經(jīng)聚類后生成的子事件日志盡可能地分離工作流，以達(dá)到發(fā)現(xiàn)更加簡(jiǎn)單過程模型的目的。文獻(xiàn)［24］分析了事件日志中軌跡的行為特征，為軌跡構(gòu)建完整的向量空間模型，與文獻(xiàn)［23］不同，文獻(xiàn)［24］主要利用大量的配置文件以確定與每個(gè)過程實(shí)例相關(guān)聯(lián)的向量。此外，該方法還提出一系列距離度量方法和聚類方法，用于對(duì)配置文件進(jìn)行后續(xù)操作。在本文實(shí)驗(yàn)部分對(duì)應(yīng)的軌跡聚類方法為K-Means。

3.1.2 上下文感知的軌跡聚類方法

文獻(xiàn)［25-26］描述了一種以上下文感知為基礎(chǔ)的軌跡聚類擴(kuò)展方法。上下文感知僅考慮事件日志中軌跡的控制流屬性（如活動(dòng)序列），并不考慮事件日志的資源屬性、時(shí)間戳屬性等。文獻(xiàn)［25］提出一種通用編輯距離技術(shù)［27］，該技術(shù)利用編輯操作量化了從一條軌跡轉(zhuǎn)換為另一條軌跡所用的距離，通過傳統(tǒng)軌跡聚類方法進(jìn)行聚類處理。文獻(xiàn)［26］通過不同長(zhǎng)度子序列對(duì)上下文感知的軌跡聚類原理進(jìn)行擴(kuò)充，并定義了極大、超極大和接近超極大重復(fù)概念，以創(chuàng)建、確定事件日志中軌跡向量特征集，從而更精確地表示軌跡的行為特征。在本文實(shí)驗(yàn)部分對(duì)應(yīng)的軌跡聚類方法為Guide Miner Tree。

3.1.3 基于模型的序列聚類方法

文獻(xiàn)［28］提出一種不同以往方法的軌跡聚類方法。受文獻(xiàn)［29］的啟發(fā)，研究人員針對(duì)混合一階馬爾科夫模型以期望最大化算法的方式進(jìn)行學(xué)習(xí)，從而實(shí)現(xiàn)聚類軌跡的目標(biāo)。文獻(xiàn)［30］以模型為基準(zhǔn)的軌跡聚類方法被完整地應(yīng)用于服務(wù)器日志中，進(jìn)一步驗(yàn)證該方法在生活中的有效性與可用性。文獻(xiàn)［31］提出基于目標(biāo)擬合度的軌跡聚類方法，該方法的主要原理是在已有的軌跡集合中添加一條新的軌跡，若添加后的軌跡集合擬合度大于原來擬合度，則將該軌跡添加到當(dāng)前軌跡集合中，以此循環(huán)迭代，最終每個(gè)集合表示一個(gè)聚類集群。相比現(xiàn)有軌跡聚類方法，該方法在每次選擇的軌跡中可以更好地適合特定的過程模型。在本文實(shí)驗(yàn)部分對(duì)應(yīng)的軌跡聚類方法為ActiTrac。

3.2 基于注意力機(jī)制的卷積準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)

3.2.1 事件向量表示

訓(xùn)練數(shù)據(jù)集DCluster是由不同長(zhǎng)度的軌跡前綴σ（U）組成，因此本文將軌跡前綴σ（U）?｛e1，e2，…，eU｝作為網(wǎng)絡(luò)模型的輸入。由于軌跡前綴σ（U）包含眾多不同事件，每個(gè)事件又具有活動(dòng)、執(zhí)行時(shí)間等多種離散和連續(xù)屬性，因此本文將軌跡前綴中各個(gè)事件表示為網(wǎng)絡(luò)模型可接受的事件向量xt。對(duì)于事件中存在的離散屬性（如活動(dòng)），利用One-Hot 編碼將其表示為0/1向量；對(duì)于事件中存在的連續(xù)屬性（如活動(dòng)執(zhí)行時(shí)間），首先對(duì)其進(jìn)行離散化處理，然后利用One-Hot 編碼將其轉(zhuǎn)化為0/1 向量；而事件向量xt為離散屬性向量與連續(xù)屬性向量拼接的結(jié)果，并將xt作為卷積準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)模型中卷積神經(jīng)網(wǎng)絡(luò)的輸入。

3.2.2 卷積神經(jīng)網(wǎng)絡(luò)

卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）［32］作為一種前饋神經(jīng)網(wǎng)絡(luò)，可以有效捕捉局部重要信息，因此，在許多研究領(lǐng)域中得到廣泛應(yīng)用。在CNN 中，每個(gè)卷積層之間的神經(jīng)元采用部分連接，通過特征信息組合形成高級(jí)特征，從而減少網(wǎng)絡(luò)模型參數(shù)量并降低網(wǎng)絡(luò)模型訓(xùn)練的復(fù)雜度。

卷積層作為CNN 的關(guān)鍵模塊，通過與序列數(shù)據(jù)向量維度為m×n的矩陣P進(jìn)行卷積運(yùn)算，得到新輸出特征oi，如式（4）所示：

其中：j表示第j個(gè)特征值；w表示濾波器；windows_size表示滑動(dòng)窗口；b表示偏置值；Pj：j+windows_size-1表示選擇向量矩陣P中第j行到j(luò)+windows_size-1 行的局部序列數(shù)據(jù)。在本文實(shí)驗(yàn)中，卷積核大小為3×3，windows_size 為2。同時(shí)，滑動(dòng)窗口被應(yīng)用于各局部序列數(shù)據(jù)向量矩陣，經(jīng)計(jì)算后得到的特征向量O如式（5）所示：

池化層作為CNN 另一個(gè)重要模塊，旨在提取卷積層中輸出的特征圖信息，在減少神經(jīng)網(wǎng)絡(luò)參數(shù)的同時(shí)，保留有用的特征信息。本文采用最大池化的方法，以選擇池化區(qū)域中最大特征值，如式（6）所示：

然后，將CNN 中池化層得到的特征值組合在一起。為了避免過擬合現(xiàn)象的出現(xiàn)，本文利用Dropout減少網(wǎng)絡(luò)權(quán)重連接，同時(shí)將Dropout 輸出的向量作為雙向準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)的輸入。

3.2.3 準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)

長(zhǎng)短期記憶神經(jīng)網(wǎng)絡(luò)（Long Short-Term Memory，LSTM）和門控循環(huán)單元（Gated Recurrent Unit，GRU）處理序列數(shù)據(jù)時(shí)依賴上一時(shí)間步的輸出，消耗較多的時(shí)間且不能很好地處理長(zhǎng)序列數(shù)據(jù)。而準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)（Quasi-Recurrent Neural Network，QRNN）［33］利用交替卷積層神經(jīng)序列建模方法，在輸出過程中充分利用輸入序列的順序信息，實(shí)現(xiàn)對(duì)序列數(shù)據(jù)跨時(shí)間步長(zhǎng)的并行處理。

QRNN 由卷積層和池化層組成。在序列數(shù)據(jù)X=（x1，x2，…，xT）作為QRNN 的輸入后，卷積層會(huì)通過數(shù)量為k的濾波器對(duì)輸入的序列數(shù)據(jù)進(jìn)行卷積處理，得到新序列Z=（z1，z2，…，zT）。如果將卷積層中濾波器的寬度設(shè)置為可變長(zhǎng)度h，那么經(jīng)卷積后得到zt寬度為xt-h+1～xt，其中zt是新序列Z一個(gè)向量。QRNN 卷積層的計(jì)算如式（7）所示：

其中：Wz表示權(quán)重矩陣；tanh 表示激活函數(shù)；*表示沿時(shí)間步長(zhǎng)序列卷積運(yùn)算。

此外，QRNN 利用門函數(shù)計(jì)算序列向量，并將其作為池化層的輸入，同時(shí)QRNN 在內(nèi)部結(jié)構(gòu)上將LSTM線性操作轉(zhuǎn)化為卷積操作且使用了遺忘門F和輸出門O［34］。QRNN 門函數(shù)計(jì)算如式（8）和式（9）所示：

其中：Wf、Wo表示權(quán)重矩陣；σ表示激活函數(shù)。假設(shè)增大卷積層中濾波器寬度h，則可以計(jì)算更多N-gram特征。本文將濾波器寬度h設(shè)置為2，即在進(jìn)行卷積運(yùn)算時(shí)，時(shí)間步長(zhǎng)序列維度的跨度為2。

QRNN 池化層主要提取卷積層中全部的輸出特征信息，以減少特征數(shù)目。同時(shí)，QRNN 池化層結(jié)構(gòu)與LSTM 相似，為進(jìn)一步確保序列數(shù)據(jù)在時(shí)間變化上進(jìn)行有效建模，達(dá)到維持序列數(shù)據(jù)上下文相關(guān)性的目的，不同時(shí)刻記憶單元狀態(tài)Ct的更新方式如式（10）所示：

其中：ft、it分別為遺忘門、輸入門在t時(shí)刻的序列信息；Ct-1為上一時(shí)刻記憶單元狀態(tài)；⊙為不同向量之間按位相乘。

QRNN 模型的最終輸出ht由t時(shí)刻的輸出門Ot和記憶單元狀態(tài)Ct計(jì)算而得，如式（11）所示：

其中：Ot為輸出門在t時(shí)刻的序列信息；ht為網(wǎng)絡(luò)輸出。

在業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)中，每條軌跡前綴所含的事件之間都具有一定的關(guān)聯(lián)性，若僅利用單向QRNN 處理此類序列數(shù)據(jù)，不僅忽略了下文事件信息對(duì)上文事件信息的影響，而且并不能達(dá)到提升預(yù)測(cè)效果的目的。因此，本文在單向QRNN 的基礎(chǔ)上引入雙向機(jī)制，即雙向QRNN（Bi-QRNN），以有效地提取上文事件中有用的特征信息，從而捕捉下文特征信息，進(jìn)一步提升網(wǎng)絡(luò)模型預(yù)測(cè)效果。Bi-QRNN由一條正向QRNN和一條反向QRNN 組成，若正向QRNN 和反向QRNN在t時(shí)刻獲得的輸出隱向量為，那么拼接后得到的上下文編碼如式（12）所示：

3.2.4 注意力機(jī)制

注意力機(jī)制是基于資源分配原理，旨在關(guān)注重要內(nèi)容。本文引入注意力機(jī)制主要是為了更好地學(xué)習(xí)軌跡前綴中每個(gè)事件的權(quán)重，以識(shí)別不同事件對(duì)業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)的重要程度。將Bi-QRNN 的輸出ht_QRNN作為注意力機(jī)制輸入，則：

其中：W表示權(quán)重矩陣；b表示偏置值；ut是ht_QRNN隱藏層表示；at表示權(quán)重值；M表示上下文矩陣。

基于注意力機(jī)制的卷積準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖2 所示。

圖2 基于注意力機(jī)制的卷積準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 Structure of convolutional quasi-recurrent neural network based on attention mechanism

在過程挖掘領(lǐng)域中，因事件日志的異質(zhì)性特點(diǎn)，傳統(tǒng)剩余時(shí)間預(yù)測(cè)方法（如文獻(xiàn)［4，6］）難以對(duì)整個(gè)事件日志的基本特征進(jìn)行描述。本文提出的剩余時(shí)間預(yù)測(cè)方法利用神經(jīng)網(wǎng)絡(luò)強(qiáng)大的序列數(shù)據(jù)建模能力以及較強(qiáng)的魯棒性處理事件日志，因此本文方法相較于傳統(tǒng)剩余時(shí)間預(yù)測(cè)方法具有一定優(yōu)勢(shì)。此外，相比利用深度學(xué)習(xí)技術(shù)開展剩余時(shí)間預(yù)測(cè)任務(wù)的預(yù)測(cè)方法（如文獻(xiàn)［11，20］），本文方法首先利用軌跡聚類的方式合理地解決了事件日志的異質(zhì)性問題，降低了異質(zhì)事件日志對(duì)剩余時(shí)間預(yù)測(cè)結(jié)果的影響；其次通過將CNN 與QRNN 相結(jié)合，并引入雙向機(jī)制和注意力機(jī)制，以捕獲和增強(qiáng)對(duì)剩余時(shí)間預(yù)測(cè)任務(wù)有決定性影響的時(shí)間和空間特征信息，從而克服了循環(huán)神經(jīng)網(wǎng)絡(luò)在空間維度的局限性。因此，本文提出基于軌跡聚類的剩余時(shí)間預(yù)測(cè)方法具有一定的可行性與有效性。

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

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

本文實(shí)驗(yàn)使用7個(gè)來自4TU Center for Research的公開事件日志數(shù)據(jù)集：BPIC_2012_A［35］、BPIC_2012_O［35］、BPIC_2012_W［35］、Helpdesk［36］、Hospital_Billing［37］、Sepsis_Cases［38］、Prepaid_Travel_Costs［39］。其中BPIC_2012_A、BPIC_2012_O、BPIC_2012_W 來源于某財(cái)政機(jī)構(gòu)貸款申請(qǐng)審批日志；Helpdesk 來源于某票務(wù)管理系統(tǒng)后臺(tái)日志；Hospital_Billing來源于某醫(yī)院EPR 中出院結(jié)算流程日志；Sepsis_Cases 來源于醫(yī)院敗血癥病歷事件日志；Prepaid_Travel_Costs 來源于某機(jī)構(gòu)差旅費(fèi)報(bào)銷事件日志。事件日志數(shù)據(jù)集的相關(guān)信息如表1所示。

表1 事件日志數(shù)據(jù)集的基本信息Table 1 Basic information of event log datasets

4.2 對(duì)比實(shí)驗(yàn)

4.2.1 評(píng)價(jià)指標(biāo)

本文以平均絕對(duì)誤差（MAE）作為評(píng)價(jià)指標(biāo)，該指標(biāo)是以計(jì)算軌跡前綴σ（U）真實(shí)值RT（σ（U））與預(yù)測(cè)值f（σ（U））之間差值的絕對(duì)值來評(píng)估業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)的準(zhǔn)確度。若MAE 值較低，則說明預(yù)測(cè)的準(zhǔn)確度較高。MAE 計(jì)算過程如式（16）所示：

除此之外，本文采用5 折交叉驗(yàn)證的方式評(píng)估預(yù)測(cè)模型，即將事件日志數(shù)據(jù)集通過隨機(jī)的方式劃分為5 等份，其中4 份作為訓(xùn)練集，1 份作為測(cè)試集，并重復(fù)5 次，將得到的MAE 求和平均，得到最終的評(píng)估結(jié)果。

4.2.2 對(duì)比方法

為驗(yàn)證以CQRNN 為基準(zhǔn)的網(wǎng)絡(luò)模型（即CQRNN、引入雙向機(jī)制的Bi-CQRNN、引入雙向機(jī)制和注意力機(jī)制的Att-Bi-CQRNN）相較于其他網(wǎng)絡(luò)模型在剩余時(shí)間預(yù)測(cè)任務(wù)上的有效性，本文將CQRNN、Bi-CQRNN、Att-Bi-CQRNN 與 LSTM、Bi-LSTM、Att-Bi-LSTM、GRU、Bi-GRU、Att-Bi-GRU、QRNN、Bi-QRNN、Att-Bi-QRNN 神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)效果進(jìn)行對(duì)比。同時(shí)，為進(jìn)一步驗(yàn)證軌跡聚類方法在剩余時(shí)間預(yù)測(cè)任務(wù)中的可行性，本文將軌跡聚類方法分別應(yīng)用在以LSTM、GRU、QRNN、CQRNN 為基準(zhǔn)的網(wǎng)絡(luò)模型中，并與其他網(wǎng)絡(luò)模型對(duì)比剩余時(shí)間預(yù)測(cè)結(jié)果。

上述網(wǎng)絡(luò)模型均采用2 層順序結(jié)構(gòu)，神經(jīng)元隱向量維度為10，Batch_size 為512，學(xué)習(xí)率為0.01，迭代150 輪，使用Adam 優(yōu)化算法。本文實(shí)驗(yàn)是基于PC Intel Core i5-10400F 2.90 GHz、NVIDIA GeForce RTX 2070 SUPER 環(huán)境，使用Pytorch 框架。

4.3 實(shí)驗(yàn)結(jié)果

4.3.1 基于軌跡聚類的剩余時(shí)間預(yù)測(cè)效果分析

本節(jié)主要分析基于軌跡聚類的剩余時(shí)間預(yù)測(cè)效果。為進(jìn)一步獲得最優(yōu)集群和集群類別，本文在實(shí)驗(yàn)過程中使用3.1 節(jié)所描述的3 種軌跡聚類方法（ActiTrac、Guide Miner Tree、K-Means），并將余弦相似度作為區(qū)分不同集群間軌跡相似性和軌跡聚類方法優(yōu)劣的評(píng)價(jià)指標(biāo)。

余弦相似度是指將事件日志轉(zhuǎn)化為對(duì)應(yīng)矩陣后，通過計(jì)算得到的行向量夾角余弦值來評(píng)估它們之間的相似度。具體地，將軌跡聚類后得到的事件日志轉(zhuǎn)換為相應(yīng)的矩陣，并以行向量的方式進(jìn)行表示，通過計(jì)算不同事件日志間行向量的余弦相似度，并對(duì)結(jié)果加權(quán)，從而得到經(jīng)軌跡聚類后各事件日志的相似度，計(jì)算過程如式（17）所示：

其中：X、Y分別表示事件日志轉(zhuǎn)化為矩陣后對(duì)應(yīng)的每個(gè)行向量。利用式（17）對(duì)生成的事件日志進(jìn)行評(píng)價(jià)后，獲得事件日志之間余弦相似度越小，說明事件日志之間越不相似，而事件日志之間的不相似性也進(jìn)一步反映了所使用的軌跡聚類方法的聚類質(zhì)量。因此，本文通過分析事件日志數(shù)據(jù)集中軌跡數(shù)量的差異性，將不同軌跡聚類方法的聚類集群類別分別設(shè)置為K=3、K=4、K=5，并依次計(jì)算在利用軌跡聚類方法處理后獲得的子事件日志之間余弦相似度，隨后將結(jié)果加權(quán)平均得到不同聚類方法和不同聚類集群的余弦相似度，從而獲得最優(yōu)軌跡聚類方法和集群。在不同數(shù)據(jù)集上，各軌跡聚類方法的不同聚類集群的余弦相似度對(duì)比如表2 所示。

表2 不同軌跡聚類方法的余弦相似度對(duì)比Table 2 Cosine similarity comparison among different trajectory clustering methods

由表2 可以看出，在7 個(gè)事件日志數(shù)據(jù)集上ActiTrac 軌跡聚類方法在經(jīng)加權(quán)平均后獲得的余弦相似度相較于其他兩種軌跡聚類方法更低，說明使用ActiTrac 軌跡聚類方法獲得的子事件日志之間不相似程度高，從而驗(yàn)證了該方法可以有效區(qū)分事件日志中存在的軌跡。因此，本文選擇ActiTrac 軌跡聚類方法對(duì)事件日志數(shù)據(jù)集進(jìn)行軌跡聚類。當(dāng)K=3時(shí)，在BPIC_2012_A、BPIC_2012_W、Sepsis_Cases數(shù)據(jù)集上ActiTrac 軌跡聚類方法的余弦相似度均優(yōu)于K=4 和K=5 的余弦相似度，說明K=3 可以準(zhǔn)確地將這3 個(gè)事件日志數(shù)據(jù)集中相似性高的軌跡劃分到一個(gè)子類中。因此，本文在BPIC_2012_A、BPIC_2012_W、Sepsis_Cases 事件日志數(shù)據(jù)集中選取K=3的集群。此外，當(dāng)K=4 和K=5 時(shí)，在BPIC_2012_O、Helpdesk、Hospital_Billing、Prepaid_Travel_Costs 數(shù)據(jù)集上，ActiTrac 軌跡聚類方法余弦相似度較低，因此，對(duì)于BPIC_2012_O、Helpdesk、Hospital_Billing、Prepaid_Travel_Costs 事件日志數(shù)據(jù)集，本文選取了K=4 和K=5 的集群。最后，針對(duì)BPIC_2012_W、Hospital_Billing 事件日志數(shù)據(jù)集中部分軌跡聚類方法無結(jié)果的情況，其原因?yàn)锽PIC_2012_W、Hospital_Billing 事件日志數(shù)據(jù)集復(fù)雜度過高。

合理的軌跡聚類方法可以有效地解決異質(zhì)事件日志的問題，在降低事件日志整體復(fù)雜度的同時(shí)，實(shí)現(xiàn)提升預(yù)測(cè)效果的目標(biāo)。因此，本文在Att-Bi-LSTM、Att-Bi-GRU、Att-Bi-QRNN、Att-Bi-CQRNN 的基礎(chǔ)上嘗試增加軌跡聚類方法（即C-Att-Bi-LSTM、C-Att-Bi-GRU、C-Att-Bi-QRNN、C-Att-Bi-CQRNN），并且將其與其他網(wǎng)絡(luò)模型進(jìn)行對(duì)比，相關(guān)設(shè)置如下：

1）對(duì)事件日志數(shù)據(jù)集不做任何處理，利用式（1）和式（2）生成的訓(xùn)練數(shù)據(jù)集DCluster作為網(wǎng)絡(luò)模型的輸入，以此對(duì)預(yù)測(cè)模型進(jìn)行迭代訓(xùn)練，并獲得剩余時(shí)間預(yù)測(cè)結(jié)果。

2）對(duì)事件日志數(shù)據(jù)集進(jìn)行軌跡聚類，將得到的集群利用式（1）和式（2）生成訓(xùn)練數(shù)據(jù)集DCluster，并將其作為網(wǎng)絡(luò)模型的輸入，以此對(duì)預(yù)測(cè)模型進(jìn)行迭代訓(xùn)練，并獲得剩余時(shí)間預(yù)測(cè)結(jié)果。

不同預(yù)測(cè)模型在7 個(gè)事件日志數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖3 所示。從圖3 可以看出，相比以LSTM、GRU、QRNN、CQRNN 為基準(zhǔn)的網(wǎng)絡(luò)模型，利用軌跡聚類方法的C-Att-Bi-LSTM、C-Att-Bi-GRU、C-Att-Bi-QRNN、C-Att-Bi-CQRNN 剩余時(shí)間預(yù)測(cè)模型在各數(shù)據(jù)集中均取得了較優(yōu)的預(yù)測(cè)結(jié)果，同時(shí)在預(yù)測(cè)準(zhǔn)確度方面，使用軌跡聚類方法比不使用軌跡聚類方法的MAE 值平均下降了約30%，證明了軌跡聚類方法有助于解決異質(zhì)事件日志的問題，在降低事件日志整體復(fù)雜度的同時(shí)，進(jìn)一步提升剩余時(shí)間預(yù)測(cè)效果，因此，基于軌跡聚類方法在剩余時(shí)間預(yù)測(cè)任務(wù)具有一定優(yōu)勢(shì)。

圖3 不同預(yù)測(cè)模型的剩余時(shí)間預(yù)測(cè)效果對(duì)比Fig.3 Effect of the remaining time prediction comparison among different prediction models

4.3.2 業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)準(zhǔn)確度對(duì)比分析

本節(jié)主要是驗(yàn)證本文方法在業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)中的有效性，并對(duì)業(yè)務(wù)流程剩余時(shí)間平均絕對(duì)誤差進(jìn)行對(duì)比分析。在7 個(gè)事件日志數(shù)據(jù)集上不同預(yù)測(cè)模型的平均絕對(duì)誤差對(duì)比如表3 所示。

表3 不同預(yù)測(cè)模型的平均絕對(duì)誤差對(duì)比Table 3 Mean absolute errors comparison among different prediction models

從表3 可以看出，在不增加任何機(jī)制的前提下，CQRNN 模型在剩余時(shí)間預(yù)測(cè)任務(wù)中相較于LSTM、GRU 和QRNN 取得了較優(yōu)的預(yù)測(cè)結(jié)果。因此，CQRNN 模型在對(duì)序列數(shù)據(jù)進(jìn)行處理時(shí)，相比于LSTM、GRU 和QRNN 可以更好地捕獲和聯(lián)系時(shí)間與空間特征信息，使得剩余時(shí)間預(yù)測(cè)效果得到一定提升。因此，本文將CQRNN 模型應(yīng)用于剩余時(shí)間預(yù)測(cè)任務(wù)具有一定的可行性。在引入雙向機(jī)制后，相較于LSTM、GRU、QRNN、CQRNN 模 型，Bi-LSTM、Bi-GRU、Bi-QRNN、Bi-CQRNN 剩余時(shí)間平均絕對(duì)誤差分別減少約3%、4%、7%、9%，說明融入雙向機(jī)制可以有效地提升模型對(duì)上文事件特征信息的提取以及捕獲下文特征信息的能力，以提高業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)準(zhǔn)確度。同時(shí)，本文進(jìn)一步驗(yàn)證了單向的LSTM、GRU、QRNN、CQRNN 在對(duì)序列數(shù)據(jù)進(jìn)行處理的過程中不能充分考慮上下文信息之間的聯(lián)系，并且在構(gòu)建剩余時(shí)間預(yù)測(cè)模型時(shí)存在局限性問題。

此外，單向和雙向QRNN 相較于單向和雙向LSTM、GRU 在剩余時(shí)間預(yù)測(cè)效果上提高了約3%～5%，說明QRNN 利用交替卷積層的神經(jīng)序列建模方法，可以充分使用輸入序列順序信息的結(jié)果。而在QRNN 的基礎(chǔ)上加入卷積神經(jīng)網(wǎng)絡(luò)是因?yàn)镼RNN 只能捕獲對(duì)剩余時(shí)間預(yù)測(cè)任務(wù)有決定性影響的時(shí)間特征信息，加入卷積神經(jīng)網(wǎng)絡(luò)后（CQRNN）可以更充分地獲取對(duì)剩余時(shí)間預(yù)測(cè)任務(wù)有影響的空間特征信息。因此，CQRNN 預(yù)測(cè)效果優(yōu)于不加入卷積神經(jīng)網(wǎng)絡(luò)的QRNN，同時(shí)證明了本文提出的模型在剩余時(shí)間預(yù)測(cè)任務(wù)中存在一定優(yōu)勢(shì)。

在預(yù)測(cè)模型中引入注意力機(jī)制，Att-Bi-LSTM、Att-Bi-GRU、Att-Bi-QRNN、Att-Bi-CQRNN 剩余時(shí)間平均絕對(duì)誤差相較于LSTM、GRU、QRNN、CQRNN模型分別降低了約5%、1%、2%、2%，說明注意力機(jī)制通過計(jì)算不同位置的序列信息權(quán)重，以區(qū)分每個(gè)事件對(duì)剩余時(shí)間預(yù)測(cè)任務(wù)的重要程度，達(dá)到提取重要事件信息的目的，從而降低無用事件信息對(duì)剩余時(shí)間預(yù)測(cè)效果的影響。

綜合分析各預(yù)測(cè)模型在不同事件日志數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，在LSTM、GRU、QRNN、CQRNN 模型的基礎(chǔ)上引入雙向和注意力機(jī)制后，剩余時(shí)間預(yù)測(cè)準(zhǔn)確度都得到不同程度提升，從而進(jìn)一步說明雙向機(jī)制和注意力機(jī)制的引入提高了模型對(duì)序列數(shù)據(jù)的建模能力，加強(qiáng)了上下文事件信息之間的關(guān)聯(lián)性，更好地捕獲到對(duì)剩余時(shí)間預(yù)測(cè)任務(wù)有決定性影響的特征信息，達(dá)到提升剩余時(shí)間預(yù)測(cè)質(zhì)量的目標(biāo)。此外，相比以LSTM、GRU、QRNN 為基準(zhǔn)的9 種模型，CQRNN在同級(jí)比較的前提下取得較優(yōu)的預(yù)測(cè)效果，表明在QRNN 基礎(chǔ)上加入卷積神經(jīng)網(wǎng)絡(luò)可以彌補(bǔ)QRNN 模型在獲取空間特征信息的不足。此外，不同預(yù)測(cè)模型的參數(shù)量對(duì)比如表4所示。本文模型的參數(shù)量與同級(jí)QRNN 參數(shù)量相差較少，但明顯低于LSTM和GRU 模型，說明本文模型在參數(shù)量未明顯增加的條件下提升了剩余時(shí)間的預(yù)測(cè)性能。

表4 不同預(yù)測(cè)模型的參數(shù)量對(duì)比Table 4 Parameter quantity comparison among different prediction models

綜上所述，在業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)任務(wù)中，本文提出的基于軌跡聚類的業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)方法相較于傳統(tǒng)預(yù)測(cè)方法在全部事件日志數(shù)據(jù)集上預(yù)平均絕對(duì)誤差（MAE）平均降低約20%，表明該方法具有一定的可行性。

5 結(jié)束語

本文提出一種基于軌跡聚類的業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)方法。根據(jù)余弦相似度，通過對(duì)事件日志中的軌跡進(jìn)行聚類，以降低事件日志的復(fù)雜度。設(shè)計(jì)基于注意力機(jī)制的卷積準(zhǔn)循環(huán)神經(jīng)網(wǎng)絡(luò)，在為不同集群構(gòu)建剩余時(shí)間預(yù)測(cè)模型的同時(shí)，捕獲和增強(qiáng)集群中對(duì)剩余時(shí)間預(yù)測(cè)結(jié)果起決定性作用的時(shí)間和空間特征信息。在事件日志數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文方法具有有效性，能夠改進(jìn)剩余時(shí)間預(yù)測(cè)效果。由于在面對(duì)更加復(fù)雜的業(yè)務(wù)流程場(chǎng)景中的剩余時(shí)間預(yù)測(cè)任務(wù)時(shí)，高效的事件日志采樣方式可以提升事件日志質(zhì)量［40］，因此后續(xù)將采樣技術(shù)應(yīng)用于剩余時(shí)間預(yù)測(cè)任務(wù)中，進(jìn)一步改進(jìn)業(yè)務(wù)流程剩余時(shí)間預(yù)測(cè)效果。