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

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

0 引言

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

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

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

1 流程挖掘中對模型進(jìn)行評價(jià)的指標(biāo)

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

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

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

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

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

2 一致性檢驗(yàn)算法綜述

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

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

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

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

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

3 近似算法

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

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

4 在線算法

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

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

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

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

5 結(jié)束語

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

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

（2）研究近似算法中錯(cuò)誤信息的準(zhǔn)確定位問題。

（3）解決在線一致性檢驗(yàn)算法的冷啟動(dòng)問題。