流程挖掘一致性檢驗算法研究綜述

趙百威， 韓 珣， 謝志偉， 石勝飛

（1 哈爾濱工業大學 計算學部， 哈爾濱 150001； 2 四川警察學院 智能警務四川省重點實驗室， 四川 瀘州 646000；3 黑龍江農墾職業學院， 哈爾濱 150025）

0 引言

工業4.0 的背景下，越來越多的制造企業通過各類信息系統來管理企業中的業務流程，這些系統產生的大量日志數據成為可操作的信息資源。 作為一個數據驅動的方法，流程挖掘（Process Mining）從信息系統的事件日志中獲取過程知識，發現、監測和改進實際系統行為模式［1］，并能自動發現業務流程和許多額外的流程增強技術。 目前，流程挖掘的研究主要有3 個方面，即：流程發現、一致性檢驗和流程增強。 現已在醫療、金融領域得到初步的應用［2－4］。 與此同時，在制造業領域中也備受關注。文獻［5－12］中初步介紹了制造業中流程挖掘的應用前景。 文獻［13－14］中分別就衡量產品質量和預測制造流程中的工作負載方面進行了應用實例分析。 文獻［15－16］提出了針對中小型的制造企業，通過流程挖掘來預測流程的結束時間。 利用流程挖掘中的一致性檢驗技術，可以對制造企業生產流程中異常流程進行診斷，提高產品的質量和生產的效率。 現如今，亦有數目可觀的制造企業正致力于通過一致性檢驗算法來改進自身的生產流程。 文獻［17－18］中提出了面向一致性檢驗算法的智能生產流程日志采集方案。 文獻［19－21］中介紹了針對制造企業生產流程應用一致性檢驗技術提出的流程評價方案。 文獻［22］分別在數據流方面和運行時間方面對制造企業流程進行分析，診斷出偏離模型的異常流程。

一致性檢驗作為流程挖掘中的一部分，與過程發現從日志信息中獲取可能的流程模型不同的是，一致性檢驗的主要目標是判斷流程模型和日志數據之間的匹配關系。 一致性檢驗不僅可以為這些企業診斷出可能存在問題的生產制造流程，同時也可以作為由過程發現獲得的流程模型的一種評測方案。近些年來，流程發現取得了顯著進展，大量的過程發現算法以及各種模型的表達方式陸續得以提出［23－28］，一致性檢驗在衡量這些流程模型方面也發揮著重要的作用。

本文將從如何定量體現模型與日志之間的擬合度以及如何定量地評測流程模型入手，總結介紹了近幾年來常規一致性檢驗算法以及特定應用場景下的近似算法和在線算法的現狀，隨后還詳細論述了近幾年來這些算法的研究進展，并指出未來亟需探討解決的研究問題。

1 流程挖掘中對模型進行評價的指標

在進行流程模型和流程日志之間的一致性檢驗時，需要對模型與日志中的擬合關系進行量化表示，主要通過4 個方面來展現［29］，擬做闡釋分述如下。

（1）Fitness：最常用的衡量指標，表現流程模型對流程日志的重現能力。 重現能力越強，Fitness指標越高。

（2）Precision：用于衡量模型的精度。 模型越復雜，精度越高，但是為了防止過擬合現象，通常需要和Simplicity一起來得到綜合評價。

（3）Generalization：用于衡量模型的泛化度。主要是針對由統一模型產生的非訓練數據，檢測模型對這些數據的辨別能力。

（4）Simplicity：用于衡量模型的簡化程度。 主要是為了防止過擬合現象的產生，在考慮模型的前3 個指標的同時，同時也要兼顧模型的復雜程度（簡化程度）。

2 一致性檢驗算法綜述

目前常見的一致性檢驗算法主要可以分為3類：基于token 重演的一致性檢驗算法，基于日志中活動行為模型的一致性檢驗算法和基于模型和日志對齊的一致性檢驗算法。

2008年，文獻［30］較早地提出了一種一致性檢驗的方案。 根據fitness指標和適當性（行為的適當性與結構的適當性）來對業務流程是否按照合理的模型執行做出量化表示，自此之后依據fitness指標來衡量模型與業務流程之間的擬合程度逐漸成為一種業界認可的通用方案。

目前，常見的一致性檢驗算法主要是考慮模型的Fitness指標，最早提出的方案就是直接在模型中模擬重現日志的生成路徑，通過重現的過程來判斷日志數據與模型之間的擬合度、即Token Based Replay。 這種方式旨在針對用Petri Net 來表示的模型去進行一致性檢驗。 主要步驟是：基于Petri Net中的轉移函數，先將日志解析為token 的形式，然后依據轉移函數來重現這些token 序列，通過統計重現后的missing tokens、consumed tokens、remaining tokens 和produced tokens 等各類別中的數量，由此來計算fitness指標。 這種基于Token 重演的算法在甫一面世時，取得了較為明顯的效果，但是近些年來，隨著各種一致性檢驗算法的相繼提出，已逐漸退出了公眾視野。 但要指出的是，當日志中存在較長流程時，這種算法相較于其他算法也仍然有著更高的穩定性。 接下來，Alessandro 等人［31］針對token based replay 算法進行優化，通過使用后向的重現算法再加上緩存日志后綴的方案緩解了token based replay 這種方案的運行速度，同時選用決策樹來診斷問題的根源，提高診斷信息的可解釋性。

基于日志中活動行為模式的一致性檢驗算法在最近一段時間比較引發關注的是Log Skeleton 算法［32］。 該算法最初用于過程發現，當時的學術界普遍認同“一個表現能力較強的模型，其fitness指標應該較高”，即能夠準確判斷出日志數據中trace 是否是由該模型產生。 Log Skeleton 算法認為可以準確地完成日志數據的分類任務的模型，具備更強的模型表達能力。 通過獲取日志數據中活動之間的關系來表現流程模型：equivalence，always after，always before，directly follow 和never together。 Log Skeleton算法的核心更像是一個分類的任務，算法的結果類似于提取日志之中的共性特征。 因此，在開源庫pm4py［33］一致性檢驗模塊中，通過對比流程模型和流程日志之間關系的差異計算fitness指標。 這種檢測方法較為簡單，同時具備一定的可解釋性，但是這種做法默認所有的活動之間的關聯關系都是等價的，可能會導致不同重要程度的日志活動出現偏差時對整體流程上產生影響的差異。 王媛媛等人［34］提出一種基于擴展足跡矩陣的一致性檢驗的方案，主要是針對Petri Net 表示出的模型，獲取日志以及模型的擴展足跡矩陣，矩陣中的元素表示活動之間的擴展次序關系，這些擴展關系包括直接跟隨關系、直接因果關系、間接因果關系、排他（互斥）關系和并行關系，通過對模型的重現，可以得到模型的擴展足跡矩陣，將日志的擴展足跡矩陣和模型的擴展足跡矩陣進行對比，通過2 個矩陣中的差異來表示偏差的出現，這種思想類似于前面提到的基于Log Skeleton 的一致性檢驗算法，也是具備較強的可解釋性，基于得到的擴展足跡矩陣也可以較為方便地進行模型的修正。

2012年，文 獻［35］ 中 提 出 一 種 基 于 對 齊（Alignment）的一致性檢驗。 這種方案更像是在處理字符串的編輯距離，自從提出以來，就一直受到學術界的青睞，且被公認為是迄今為止效率最高的一致性檢驗算法。 算法通過計算move in log、move in model、both move 和illegal move 這4 種移動方式在進行比對時出現的次數來計算模型和日志之間的擬合度。 這個最初的算法在面對日志與模型之間出現偏差時，雖然可以得到兩者之間的偏差，但是沒有考慮到日志中不同event 之間出現偏差的影響程度，這一問題已然在后續的優化研究中得到了有效解決。 文獻［36］中提出一種基于cost 的一致性檢驗，通過對原始的Petri Net 進行擴展，加入轉移的cost來區分不同活動的重要程度。 這也是目前獲得廣泛認可的一種方案。 這種基于對比的一大類一致性檢驗算法存在的普遍問題是算法具備較差的擴展性。另一個問題是，如果需要和前文提到的算法一樣具備提供精確的偏差定位信息時，就要在算法的執行過程中花費額外的內存空間來存儲對比過程中各個步驟得到的中間信息。 文獻［37］中針對擴展性給出了一個方案，核心思想是把模型和日志都表現成自動機的形式，這樣可以減少對公共片段進行處理時造成的時間消耗。 通過啟發式的A?算法［38］來保證日志中的軌跡和模型中軌跡的最佳對齊。 另一種方案是將模型分解為一組自動機，這些自動機組合在一起可以完整地表示出流程模型，通過對這些自動機進行單獨處理，在算法的執行時間上得到了明顯改善。 王穎等人［39］提出的算法把對齊方案進行了擴展，并未考慮流程是否按照模型中的流程軌跡來執行，同時還把流程中的每個活動對應的屬性是否符合模型中的賦值規則也一并進行了研究。 算法仍是根據Petri Net 構建狀態轉移空間，使用A?算法來搜索最接近的目標軌跡。 這種綜合考慮執行流程和規則約束的一致性檢驗方案具有更加廣闊的應用場景，卻仍然需要面對嚴重的算法耗時問題。

3 近似算法

目前，常見的一致性檢驗算法普遍存在的一個問題是算法耗時嚴重。 究其原因，主要是這些算法都是以返回最為準確的擬合度這一思想作為基礎提出的。 為了準確地計算得出最終結果，將會花費大量的計算時間，例如前文提到的Alignment Based Conformance Checking 中，就需要在模型中搜索最接近的合法化路徑，如此一系列的操作在保證算法結果準確度的同時，卻會造成很高的時間開銷，這樣嚴重的耗時問題在面對一些可能隨著時間推演而不斷改進的模型時，會忽略日志的時效信息。 同時，某些應用場景下并不需要提供較為準確的擬合指標，一種常見的方案是計算擬合度的上下限。 在此基礎上，隨即就提出了許多近似一致性檢驗算法。

Lee 等人［40］提出了一種基于劃分模型的算法，將復雜的、含有并發的模型按塊劃分為簡單的子模型，通過融合分解模型的一致性檢驗結果來確定整個復雜模型的指標。 在面對較為復雜的模型時，會涉及到更加復雜的搜索空間，通過這種將模型劃分成較為簡單的模型板塊的做法，可以顯著降低搜索時的時間開銷。 文獻［41］首先對日志進行分析，統計日志中活動序列的出現概率；基于日志的前綴，通過用戶確定前綴的擴展長度，分析日志中前綴的后續動作的出現概率，據此概率來確定擬合度的范圍區間。 文獻［42］提出一種通過采樣的方法來近似估算模型與日志之間的擬合度。 與前面提到的算法不同的是，該模型面對的應用場景是把重點放在日志整體與流程模型的一致性上，而不是聚焦在單一的某一個流程上。 與篩選出和模型有偏差的異常流程相比較來說，這種算法能夠更好地對流程模型進行評測。

4 在線算法

前面提到的一系列算法都是以“日志中所有的流程都已經結束”這一前提條件為基礎的，但是在實際的應用場景中，往往面對的是一些仍在進行中的數據，對于這些不完整的日志流程，前文論述的離線算法的表現往往不盡如人意，所以很多學者著眼于研發在線的一致性檢驗算法。 文獻［43－44］中分析了在線一致性檢驗算法對制造企業的重要作用。將在線一致性檢驗算法與離線算法相比，最主要的區別就是需要算法在未知后續活動序列的情況下對整個案例進行評估［45］，下面就系統總結了近幾年來在線的一致性檢驗算法的研究成果。

2018年，文獻［46］中提出一種較為經典的在線一致性檢驗算法框架。 同時提出不再使用fitness這個唯一的指標作為一致性檢驗算法的結果。 因為在線算法并不像離線算法那樣可以確定后續完整的日志，也無法確定后續的活動，所以除了使用fitness之外，還將使用completeness來判斷案例是否已經完成，confidence來表示前面參數的可信度。 考慮到在線算法的特點，就需要解決冷啟動的問題。 算法使用由某一模型推衍的多種由不同的模型階段產生的不同長度的不同案例來解決冷啟動問題。 算法離線得對初始模型進行解析，得到用于在線一致性檢驗算法的流程模型，首先對初始模型進行轉換，去除模型中的循環，依據定義的行為模式，構造三元組（B，P，F）。 這里，B為滿足規定的行為模式的集合，P為任意模式b在出現前的行為模式的個數區間，F（b） 為從任意b開始、到流程結束，需要的不同行為模式的最少個數。 框架中主要使用日志活動間的行為模型，算法需要認為確定行為模式的類別、即日志活動之間的關系，通過將日志流轉化為行為模式流。 算法統計在到達某一個行為模式時，前面已經觀測到的合法以及不合法的行為模式的個數。 算法以更新行為模式的個數、計算擬合度指標、釋放內存為總體的框架。 這種算法框架中可以由用戶自己定義具體行為模型，有一定的擴展性，但是算法需要離線做的前置工作較為復雜，并不是所有的流程模型都可以適配這種算法框架。

Lee 等人［47］提出一種基于隱馬爾可夫模型的在線一致性檢驗算法。 由于在計算擬合度指標時，對于當前處理的日志活動，其前期所有的日志活動以及當前的活動本身都會對擬合度產生影響，算法將數據流處理的過程看作是隱馬爾可夫鏈。 整個算法受文獻［8］啟發，也通過增加在線算法的擬合度指標來更為確切地表示流程與模型之間的擬合度。算法通過離線對模型進行解析，得到狀態轉移矩陣、初始狀態描述、定義用于表示擬合程度的計算函數來構造用于在線一致性檢驗算法的隱馬爾可夫模型。 以日志流、構造得到的隱馬爾可夫模型、狀態的距離矩陣作為輸入，算法以更新狀態估計、計算擬合度指標、釋放內存為總體框架。 算法可以在保證準確率的同時，降低對內存的需求。

Zelst 等人［48］提出一種基于前綴對齊的一致性檢驗技術，前面提及了基于alignment 的離線一致性檢驗算法，該算法主要思想與離線的算法相似，研究中主要針對，在面對illegal move 時尋找其他路徑的優化搜索算法以及在線算法中對內存使用和算法優化之間的折中選擇方面。 文獻［49］提出一種針對多方面對齊的在線一致性檢驗算法，可以從多個角度對進行中的流程加以分析。 文獻［50］提出一種較為高效地計算對齊過程中偏差定位的算法，提高了在線對齊算法的性能。 現已證實這種基于對齊的各種算法具備較高的準確率，但是盡管研究中對算法進行了優化，以及提高了算法的運行效率，但是與前文提及的算法相比，在運行效率方面卻仍未表現出明顯優勢。 除此之外，這種算法也仍然面臨著冷啟動的問題有待進一步的研究解決。

5 結束語

本文中梳理了近年來一致性檢驗算法的研究進展，針對不同應用場景下的算法需求研究現狀進行了較為深入的探索與討論。 雖然已有算法可達到較高的準確度，但是在實際的應用場景下仍然無法滿足需求。 綜合分析現在的實際需求，一致性檢驗算法在以下方面仍亟待接下來的改進與完善：

（1）優化現有算法體系的性能，降低算法運行的時間。

（2）研究近似算法中錯誤信息的準確定位問題。

（3）解決在線一致性檢驗算法的冷啟動問題。