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

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

（1 哈爾濱工業(yè)大學(xué) 計算學(xué)部， 哈爾濱 150001； 2 四川警察學(xué)院 智能警務(wù)四川省重點實驗室， 四川 瀘州 646000；3 黑龍江農(nóng)墾職業(yè)學(xué)院， 哈爾濱 150025）

0 引言

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

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

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

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

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

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

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

（3）Generalization：用于衡量模型的泛化度。主要是針對由統(tǒng)一模型產(chǎn)生的非訓(xùn)練數(shù)據(jù)，檢測模型對這些數(shù)據(jù)的辨別能力。

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

2 一致性檢驗算法綜述

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

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

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

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

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

3 近似算法

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

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

4 在線算法

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

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

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

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

5 結(jié)束語

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

（1）優(yōu)化現(xiàn)有算法體系的性能，降低算法運行的時間。

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

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