基于軌跡聚類的業務流程剩余時間預測方法

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

（1.山東理工大學計算機科學與技術學院，山東淄博 255000；2.同濟大學嵌入式系統與服務計算教育部重點實驗室，上海 200092）

0 概述

預測型流程監控［1］作為業務流程管理領域中的主要研究內容，旨在對當前正在運行的流程實例進行有效地分析，從而預測在今后一段時間內流程實例出現的行為狀態，例如可能發生的活動、實例所需的執行時間等［2］。相較于現有監控形式的方法，預測型流程監控是在過程感知信息系統的基礎上對歷史數據加以記錄［3］，不僅能有效規避偏差、信息缺失等風險，而且還可以防止因流程實例持續執行而帶來資源沖突等情況的發生。

業務流程剩余時間預測［4］作為預測型流程監控中重要的預測任務，采用合理的方式準確預測流程實例需要執行的剩余時間。而傳統的剩余時間預測方法是基于業務系統中產生的事件日志挖掘形式化變遷系統［5］、隨機Petri 網［6］等可描述模型，并通過該模型對剩余時間進行有針對性的預測。隨著深度學習技術的發展，研究人員將其與剩余時間預測相結合，并取得較優的預測效果，特別是文獻［7］提出的預測方法，相較于傳統方法的預測效果得到顯著提升。

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

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

1 相關工作

1.1 聚類方法

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

1.2 業務流程剩余時間預測方法

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

2 預備知識

2.1 基本概念

本文介紹與業務流程剩余時間預測任務相關的基本概念，并給出形式化描述。

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

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

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

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

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

定義6（事件日志）事件日志描述了業務系統歷史運行情況，以L=｛Q1，Q2，…，Q|l|｝表示。

定義7（剩余時間預測）在業務系統中，假設事件空間為T，則軌跡和軌跡前綴空間記為T*，剩余時間預測旨在利用映射函數對軌跡前綴剩余時間進行預測，即f=T* →R+。

本文僅關注流程實例中軌跡基本信息（即事件、活動、執行時間），并開展剩余時間預測任務。

2.2 業務流程剩余時間預測任務

本文在利用深度學習技術開展業務流程剩余時間預測任務時，可分為訓練階段和應用階段。訓練階段的主要目標是通過事件日志中詳細描述的歷史流程實例對剩余時間預測函數f進行學習，應用階段則是利用訓練階段獲得的函數f對業務流程中流程實例（即軌跡前綴）的剩余執行時間進行預測。

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

應用階段是利用生成的訓練數據集DCluster對業務流程剩余時間模型f進行學習，為了防止出現過擬合的現象，利用正則項的方式加以克服，如式（3）所示：

3 基于軌跡聚類的剩余時間預測方法

本文提出的基于軌跡聚類的剩余時間預測方法流程如圖1 所示。

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

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

3.1 軌跡聚類

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

3.1.1 向量空間方法

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

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

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

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

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

3.2 基于注意力機制的卷積準循環神經網絡

3.2.1 事件向量表示

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

3.2.2 卷積神經網絡

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

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

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

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

然后，將CNN 中池化層得到的特征值組合在一起。為了避免過擬合現象的出現，本文利用Dropout減少網絡權重連接，同時將Dropout 輸出的向量作為雙向準循環神經網絡的輸入。

3.2.3 準循環神經網絡

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

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

其中：Wz表示權重矩陣；tanh 表示激活函數；*表示沿時間步長序列卷積運算。

此外，QRNN 利用門函數計算序列向量，并將其作為池化層的輸入，同時QRNN 在內部結構上將LSTM線性操作轉化為卷積操作且使用了遺忘門F和輸出門O［34］。QRNN 門函數計算如式（8）和式（9）所示：

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

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

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

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

其中：Ot為輸出門在t時刻的序列信息；ht為網絡輸出。

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

3.2.4 注意力機制

注意力機制是基于資源分配原理，旨在關注重要內容。本文引入注意力機制主要是為了更好地學習軌跡前綴中每個事件的權重，以識別不同事件對業務流程剩余時間預測任務的重要程度。將Bi-QRNN 的輸出ht_QRNN作為注意力機制輸入，則：

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

基于注意力機制的卷積準循環神經網絡結構如圖2 所示。

圖2 基于注意力機制的卷積準循環神經網絡結構Fig.2 Structure of convolutional quasi-recurrent neural network based on attention mechanism

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

4 實驗與結果分析

4.1 實驗數據集

本文實驗使用7個來自4TU Center for Research的公開事件日志數據集：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 來源于某財政機構貸款申請審批日志；Helpdesk 來源于某票務管理系統后臺日志；Hospital_Billing來源于某醫院EPR 中出院結算流程日志；Sepsis_Cases 來源于醫院敗血癥病歷事件日志；Prepaid_Travel_Costs 來源于某機構差旅費報銷事件日志。事件日志數據集的相關信息如表1所示。

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

4.2 對比實驗

4.2.1 評價指標

本文以平均絕對誤差（MAE）作為評價指標，該指標是以計算軌跡前綴σ（U）真實值RT（σ（U））與預測值f（σ（U））之間差值的絕對值來評估業務流程剩余時間預測的準確度。若MAE 值較低，則說明預測的準確度較高。MAE 計算過程如式（16）所示：

除此之外，本文采用5 折交叉驗證的方式評估預測模型，即將事件日志數據集通過隨機的方式劃分為5 等份，其中4 份作為訓練集，1 份作為測試集，并重復5 次，將得到的MAE 求和平均，得到最終的評估結果。

4.2.2 對比方法

為驗證以CQRNN 為基準的網絡模型（即CQRNN、引入雙向機制的Bi-CQRNN、引入雙向機制和注意力機制的Att-Bi-CQRNN）相較于其他網絡模型在剩余時間預測任務上的有效性，本文將CQRNN、Bi-CQRNN、Att-Bi-CQRNN 與 LSTM、Bi-LSTM、Att-Bi-LSTM、GRU、Bi-GRU、Att-Bi-GRU、QRNN、Bi-QRNN、Att-Bi-QRNN 神經網絡的預測效果進行對比。同時，為進一步驗證軌跡聚類方法在剩余時間預測任務中的可行性，本文將軌跡聚類方法分別應用在以LSTM、GRU、QRNN、CQRNN 為基準的網絡模型中，并與其他網絡模型對比剩余時間預測結果。

上述網絡模型均采用2 層順序結構，神經元隱向量維度為10，Batch_size 為512，學習率為0.01，迭代150 輪，使用Adam 優化算法。本文實驗是基于PC Intel Core i5-10400F 2.90 GHz、NVIDIA GeForce RTX 2070 SUPER 環境，使用Pytorch 框架。

4.3 實驗結果

4.3.1 基于軌跡聚類的剩余時間預測效果分析

本節主要分析基于軌跡聚類的剩余時間預測效果。為進一步獲得最優集群和集群類別，本文在實驗過程中使用3.1 節所描述的3 種軌跡聚類方法（ActiTrac、Guide Miner Tree、K-Means），并將余弦相似度作為區分不同集群間軌跡相似性和軌跡聚類方法優劣的評價指標。

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

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

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

由表2 可以看出，在7 個事件日志數據集上ActiTrac 軌跡聚類方法在經加權平均后獲得的余弦相似度相較于其他兩種軌跡聚類方法更低，說明使用ActiTrac 軌跡聚類方法獲得的子事件日志之間不相似程度高，從而驗證了該方法可以有效區分事件日志中存在的軌跡。因此，本文選擇ActiTrac 軌跡聚類方法對事件日志數據集進行軌跡聚類。當K=3時，在BPIC_2012_A、BPIC_2012_W、Sepsis_Cases數據集上ActiTrac 軌跡聚類方法的余弦相似度均優于K=4 和K=5 的余弦相似度，說明K=3 可以準確地將這3 個事件日志數據集中相似性高的軌跡劃分到一個子類中。因此，本文在BPIC_2012_A、BPIC_2012_W、Sepsis_Cases 事件日志數據集中選取K=3的集群。此外，當K=4 和K=5 時，在BPIC_2012_O、Helpdesk、Hospital_Billing、Prepaid_Travel_Costs 數據集上，ActiTrac 軌跡聚類方法余弦相似度較低，因此，對于BPIC_2012_O、Helpdesk、Hospital_Billing、Prepaid_Travel_Costs 事件日志數據集，本文選取了K=4 和K=5 的集群。最后，針對BPIC_2012_W、Hospital_Billing 事件日志數據集中部分軌跡聚類方法無結果的情況，其原因為BPIC_2012_W、Hospital_Billing 事件日志數據集復雜度過高。

合理的軌跡聚類方法可以有效地解決異質事件日志的問題，在降低事件日志整體復雜度的同時，實現提升預測效果的目標。因此，本文在Att-Bi-LSTM、Att-Bi-GRU、Att-Bi-QRNN、Att-Bi-CQRNN 的基礎上嘗試增加軌跡聚類方法（即C-Att-Bi-LSTM、C-Att-Bi-GRU、C-Att-Bi-QRNN、C-Att-Bi-CQRNN），并且將其與其他網絡模型進行對比，相關設置如下：

1）對事件日志數據集不做任何處理，利用式（1）和式（2）生成的訓練數據集DCluster作為網絡模型的輸入，以此對預測模型進行迭代訓練，并獲得剩余時間預測結果。

2）對事件日志數據集進行軌跡聚類，將得到的集群利用式（1）和式（2）生成訓練數據集DCluster，并將其作為網絡模型的輸入，以此對預測模型進行迭代訓練，并獲得剩余時間預測結果。

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

圖3 不同預測模型的剩余時間預測效果對比Fig.3 Effect of the remaining time prediction comparison among different prediction models

4.3.2 業務流程剩余時間預測準確度對比分析

本節主要是驗證本文方法在業務流程剩余時間預測任務中的有效性，并對業務流程剩余時間平均絕對誤差進行對比分析。在7 個事件日志數據集上不同預測模型的平均絕對誤差對比如表3 所示。

表3 不同預測模型的平均絕對誤差對比Table 3 Mean absolute errors comparison among different prediction models

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

此外，單向和雙向QRNN 相較于單向和雙向LSTM、GRU 在剩余時間預測效果上提高了約3%～5%，說明QRNN 利用交替卷積層的神經序列建模方法，可以充分使用輸入序列順序信息的結果。而在QRNN 的基礎上加入卷積神經網絡是因為QRNN 只能捕獲對剩余時間預測任務有決定性影響的時間特征信息，加入卷積神經網絡后（CQRNN）可以更充分地獲取對剩余時間預測任務有影響的空間特征信息。因此，CQRNN 預測效果優于不加入卷積神經網絡的QRNN，同時證明了本文提出的模型在剩余時間預測任務中存在一定優勢。

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

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

表4 不同預測模型的參數量對比Table 4 Parameter quantity comparison among different prediction models

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

5 結束語

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