基于托肯重演的并行結構過程模型修復方法

白二凈，李曉巖，杜玉越

（1.青島黃海學院 大數據學院，山東 青島 266427；2.山東科技大學 計算機科學與工程學院，山東 青島 266590）

0 引言

隨著信息技術不斷變革、信息資源不斷增多，越來越多企業組織關注并使用信息管理系統，從而產生大量的事件日志。過程挖掘通過從企業信息管理系統實際產生的事件日志中提取有用信息，發現并改善實際過程模型［1］。過程挖掘技術［1-3］主要包括過程發現、符合性檢查和過程增強三方面。過程發現［4］根據不同過程挖掘算法和實際事件日志來挖掘不同過程模型。原模型與實際產生的事件日志之間的不一致可通過符合性檢查［1-3］來確定。當模型與事件日志不一致時，通過實際事件日志來修復或擴充模型則屬于過程增強。隨著對過程挖掘技術研究的不斷深化，許多過程挖掘算法被提出。α算法［5］根據日志間的四種次序關系挖掘過程模型，但存有很多缺點，例如，α 算法要求日志的直接跟隨次序關系是完備的，且不能處理重名任務、短循環、不可見變遷和非自由選擇結構等。針對α 算法［5］的不足，文獻［6-7］中提出了相應擴展方法。啟發式挖掘算法在構建過程模型時，根據事件和序列出現頻次［8］的高低，確定路徑是否應該出現在模型中。Fahland 等［9］提出的模型修復方法為提高擬合度加入自環和不可見變遷，導致模型結構變得復雜且精度降低。基于語言的區域挖掘［10］技術，模型擬合度很高，但模型的健壯性有待提升。

衡量過程模型的標準有擬合度、精度、簡潔度和泛化度4個指標［11］：擬合度是評價指標中最重要的，是事件日志中的跡在模型中重演能力的表征；精度是描述模型重演事件日志能力的另一個重要指標，一個精度相對比較高的模型，很少重演事件日志以外的其他事件；簡潔度要求盡可能以簡單的模型來展現事件日志；泛化度是描述模型擴展能力的指標，可以預測將來跡的發生情況。

當業務過程或環境等發生變化時，都會導致已有過程模型不能完全重演事件日志。應對這種情況，既可運用實際日志來挖掘一個全新的模型，又可以根據實際日志修復模型。新挖掘的模型存在丟失原模型原有優勢的風險。模型修復是在原模型的基礎上進行，既可以確保模型重演大部分日志，又不會破壞原模型的優勢［12］。文獻［13］中針對選擇結構模型，提出了一種基于托肯重演的選擇結構模型修復方法，通過托肯重演確定模型偏差所在位置，根據偏差位置采用邏輯Petri網來修復選擇結構模型。本文在文獻［13］托肯重演算法的基礎上針對并行結構提出一種基于邏輯Petri 網和托肯重演的并行結構修復方法。邏輯Petri 網能很好地描述活動之間的邏輯關系，使得修復模型更加簡潔，并且邏輯Petri 網在修復過程中能有效避免自環和不可見變遷，從而提升模型精度。目前國內有很多關于邏輯Petri 網的原理和應用的研究文獻，文獻［14］中提出基于邏輯數據Petri 網的業務過程建模與分析；文獻［15］中提出基于邏輯Petri 網的選擇結構修復方法。鑒于邏輯Petri 網的優勢，本文在其基礎上提出采用托肯重演的方式對并行結構進行修復的方法。首先通過托肯增強重演算法，計算模型與日志之間的偏差；然后根據偏差位置來修復模型。通過實驗與Fahland 等［9］和Goldratt［16］方法對比，本方法具有比較高的擬合度和精度。

1 基本概念

本章簡要介紹相關概念，元組、事件日志［6-9］、Petri 網［1-5］、邏輯Petri網［17］、工作流網［18］、過程樹［19］及一些常用符號表示。

定義1元組［6-9］。x=(a1，a2，…，an)為含有n個元素的元組，其中第i個元素用πi表示，i∈(1，2，…，n)。

定義2跡和事件日志［6-9］。設A是活動集合，跡σ∈A*是活動隊列，且1 ≤i

圖1 所示為一個邏輯Petri 網。t1為邏輯輸入變遷，I（t1）=(p1?p2) ∧p3是t1的邏輯輸入函數，表示有2 種情況會觸發t1。①p1和p3中存在托肯；②p2和p3中存在托肯。t2為邏輯輸出變遷，O（t2）=p5∨p6是t2的邏輯輸出函數，表示t2引發后會有3 種情況：①p5中有托肯；②p6中有托肯；③p5和p6中都有托肯。

圖1 邏輯Petri網模型Fig.1 Logic Petri net model

定義8過程樹［19］。設A是活動集合，⊕是給定的操作符集，τ 是不可見變遷，則有：

1）a∈A∪{τ}是一個過程樹。

2）設PT1，PT2，…，PTn(n>0)是過程樹，則⊕（PT1，PT2，…，PTn）也是過程樹。

3）操作符集共有4種：×代表選擇關系，其對應的子樹選擇其中一個發生；→代表順序關系，其對應的子樹會依次發生；∧表示并行關系，其對應的子樹都會發生表示循環關系，其中PT1表示循環體會重復發生，PT2，PT3，…，PTn（n≥2）表示循環路徑。

過程樹是對工作流網的抽象表示，其中葉子節點代表活動，而非葉子節點代表活動之間的關系。

2 并行結構模型修復

隨著公司或組織規模不斷壯大，管理信息系統逐漸新增或變更一些業務，從而產生新的事件日志。新產生的事件日志在原模型中進行重演時，因托肯缺失導致重演失敗，因此原模型需要被修復。根據文獻［13］將實際產生的事件日志在原模型中進行強制重演［20］，以此來確定日志與模型之間的偏差，根據偏差位置來判定并行變遷是否并發執行，并根據結果來修復原過程模型。本文提出一種基于托肯重演的并行結構修復方法。通過托肯重演，確定原模型與實際事件日志之間的偏差，通過過程樹計算并行變遷集合，然后基于邏輯Petri 網修復模型。

2.1 模型修復

通過事件日志L在模型中進行重演［13，20］，并計算重演過程中缺失的和遺留的托肯來確定模型的偏差位置。在并行結構中進行托肯重演依然會因缺少托肯使得托肯重演無法進行。因此，為確保托肯能從初始庫所動態變化到終止庫所，引用文獻［13］中給出的增強重演算法，并以Petri 網并行結構為例，說明此算法在并行結構中產生偏差所在位置，以及后續修復方法。

算法1 增強重演算法［13］。

通過算法1 使工作流網中的托肯從初始庫所，動態變化到終止庫所，最后消耗終止庫所中的托肯。在從初始庫所到終止庫所變化過程中，根據庫所位置的不同采用不同算式計算M（p）的值。下面以日志L1中跡σ1為例，給出算法1 在并行結構中的執行過程。

圖2 工作流網模型WFN1Fig.2 Workflow net model WFN1

在start 狀態（初始狀態）除M（p1）=1 以外，其余M（pi）=0。對于變遷t1∈T且p1∈?t1-t1?，所以M（p1）←M（p1）-1，而對于t1∈T且p2∈t1?-?t1，所以M（p2）←M（p2）+1。因此在變遷t1處M（p1）=0，M（p2）=1，其他庫所處托肯值不變，以此方法計算后續所有變遷處庫所托肯值，計算結果見表1。最后，M(p10)=0 代表重演結束。結束（end）后，M(p8)=-1 代表缺失的托肯，M（p5）=1 代表遺留的托肯。

表1 重演σ1的托肯值變化表Tab.1 Change table of token in σ1 replay

在原Petri 網并行結構中存在缺失和遺留的托肯，表示此并行分支并不是真的并發執行，需要對日志L1中其他跡繼續進行強制重演。其他跡重演結果如與σ1強制重演后相同，則表示在σ1和σ2中的并行變遷是并發執行，否則是非并發執行。采用邏輯Petri 來修復模型，需增加邏輯輸出函數和邏輯輸入函數，需要計算模型中具有并行關系的變遷集合和并行結構開始和結束對。下面根據過程樹，定義并行結構關系對、并行結構開始和結束對。

定義9并行結構對集合SCRP，并行變遷集合CT。設A是所有活動的集合，PT是工作流網WFN對應的過程樹。CRP代表并行結構對，用元組（t1，t2）來表示。當?N∈PT并且N=“∧”時，t1=?（?Nl），t2=（）?，其中Nl和Nr分別代表并行結構的最左子樹和最右子樹。并行結構對集合用SCRP表示，SCRP=｛（t1，t2）|t1=?（?Nl），t2=（）?，?N∈PTandN=“∧”｝。并行變遷集合用CT表示，CT=｛N.child，?N∈PTandN=“∧”｝。如圖3 所示，CRP=（t2，t6），SCRP=｛（t2，t6）｝，CT=｛t3，t4，t5｝。

圖3 WFN1的過程樹PT1Fig.3 Process tree PT1 of WFN1

算法2 計算并行結構對SCRP，并行變遷集合CT。

算法2 給出了計算并行結構對集合SCRP，并行變遷集合CT方法：步驟1）表示初始化CRP、SCRP和CT集合；步驟2）～17）當N節點是并行結構操作符時，并行結構開始和結束對存儲于SCRP集合中所有具有并行關系的變遷存儲于CT集合中；對PT中所有非葉子節點都重復執行步驟2）～7）；當N為葉子節點時程序結束；步驟18）返回結果。

算法3 并行結構修復算法。

算法3 并行結構修復方法：步驟1）給LPN賦值；步驟2）調用算法2，計算并行結構對SCRP，并行變遷集合CT。步驟3）～14）對日志L中的跡σi進行強制重演，并將σi中含有剩余和缺失托肯庫所分別存儲于R1［］和M1［］中。步驟15）～25）對日志L中的跡σk進行強制重演，并將σk中含有剩余和缺失托肯庫所分別存儲于R2［］和M2［］中。步驟26）～45）計算σi和σk并行結構中第一個變遷、最后一個變遷，分別存儲于CT［a］、CT［c］、CT［b］和CT［d］。步驟46）～63）計算邏輯輸出函數O（t）和邏輯輸入函數I（t）的值。最后一步返回修正后的LPN′模型。算法3 的時間復雜度為O（n3）。下面以L1為例給出基于托肯重演的并行結構修正例子。

圖4 WFN1修復模型Fig.4 Repaired model of WFN1

2.2 含子模型修復

算法3 只能修復日志動作與模型變遷相同的情況，而當實際日志動作與模型變遷不一致時，采用算法3 無法完成模型修復。過程模型在實際運行中因新增或變更業務，會產生新的事件日志，因此當日志與模型不一致時，日志動作經常比模型動作要多。針對這種情況，首先要挖掘由新增日志產生的子模型，然后再根據模型間的關系，將子模型插入原模型中，最后再修復模型。參考文獻［13］給出映射函數的定義和計算新增日志動作的算法。

定義10映射［13］。對于日志L中的跡σ，若存在日志動作a∈&(σ)，且存在模型動作t與日志動作a對應，則稱Map（a，t）是日志動作到模型動作的映射。

算法4 計算子日志SL［13］。

算法4 計算出子日志［13］后，采用歸納算法挖掘對應的子模型。然后，根據子模型與原模型的關系將子模型插入原模型中。在插入模型時需要計算子模型與原模型的關系，具體算法見文獻［13］。最后再根據算法3 修復原模型。下面給出含子模型并行結構修復算法。

算法5 含子模型并行結構修復。

圖5 工作流網模型WFN2Fig.5 Workflow net model WFN2

運用算法5 修復WFN2，生成子模型WFN?如圖6 所示，修復結果如圖7 所示。

圖6 工作流網模型WFN? Fig.6 Workflow net model WFN?

圖7 WFN2修復模型Fig.7 Repaired model of WFN2

3 仿真實驗

對本文方法進行仿真實驗和對比分析。實驗中使用的事件日志和過程模型來自青島某醫院胃腸科。Fahland 等［9］方法對模型修復，是通過過程挖掘工具包ProM6.10 中實現，且可從http：//www.promtools.org 網站下載。Goldratt［16］方法修復模型是在DOS 窗口下實現的。由于還沒有邏輯Petri 網計算工具，本文方法的實現是通過手工模擬完成。

3.1 模型修復

圖8 Petri 網模型是根據事件日志用α 算法［5］挖掘得到，展示了患者從預約開始到就診檢查最后離開醫院的整個過程。過程描述如下：首先患者可以直接到醫院進行登記注冊，也可以先通過網絡預約后獲取預約號；然后醫生根據患者順序進行問診。問診后，患者去做相應的胃鏡檢查，如果患者沒有胃腸道相關疾病則離開醫院；否則要在胃腸科做更詳細的檢查，相應的檢查有X 射線掃描、CT 掃描和核磁共振；然后患者去外科診所準備手術。手術前，需要進行的檢查有心電圖和實驗室檢查，然后病人被送進醫院并進行手術，最后在經過治療效果評估后，病人出院。

圖8 胃腸道疾病患者治療過程模型Fig.8 Process model of treatment of patients with gastrointestinal diseases

表2 是圖8～11 中符號與實際日志動作對應關系。

表2 符號與行為的對應關系Tab.2 Corresponding relationship between symbols and activities

隨著實際檢查項目的增多，出現了新日志動作，原模型與事件日志間出現偏差。例如患者在做胃鏡檢查時，也可以做胃腸道彩超。此外，病人在前往胃腸科作進一步檢查前，亦可選擇腹部超音波檢查。在外科門診，患者除了心電圖和實驗室檢查外，還需做血常規和生化檢查。針對以上情況，采用Fahland 方法、Goldratt 方法和本文所提基于邏輯Petri 網托肯重演的方法對圖8模型進行修復，修復模型分別對應圖9～11。

圖9 Fahland方法修復后的模型Fig.9 Model repaired by Fahland’s method

表3 所示L1～L6為實際產生的事件日志，包括信息有跡的數量與長度、事件數量、活動數等。

表3 事件日志Tab.3 Event logs

在本文修復方法中，根據實際發生日志，患者在門診就診時，可選擇胃鏡檢查或胃腸道彩超或可都選擇，增加邏輯輸出函數O（g）=p6∨p8和邏輯輸入函數I（i）=p7∨p9?；颊咴谖改c科進行檢查時新增腹部超聲波檢查項，增加O（k）=（p11∧p13∧p15）∨p17和I（o）=（p12∧p14∧p16）∨p18。外科門診、患者手術前還需做血常規和生化檢查，增加O（p）=（p20∧p22）∨p24∨p26和I（s）=（p21∧p23）∨p25∨p27。

3.2 模型評估

根據奧卡姆剃須刀原則［21］，分析采用不同方法修復原模型后其簡潔度。表4 給出三種方法修復后在增加庫所、不可見變遷、自環等方面的對比。根據表4，本文方法增加8 個庫所，而Fahland 方法增加11 個，Goldratt 方法因自環存在未增加新庫所。從增加弧數量角度分析，本文方法增加12 條，而Fahland 方法和Goldratt 方法分別增加46 和16 條。從增加自環變遷數分析，本文方法未增加自環，而Fahland 方法和Goldratt 方法分別增加7 個。由此，可見本文相對于其他兩種修復方法，其簡潔度更高。

表4 三種方法的簡潔度對比Tab.4 Comparison of simplicity among three methods

圖10 Goldratt方法修復后的模型Fig.10 Model repaired by Goldratt method

圖11 本文方法修復后的模型Fig.11 Model repaired by the proposed method

擬合度［22］是描述過程模型一致性檢查最為重要的參數。根據不同數量級的跡，圖12 給出了不同方法的擬合度對比。根據文獻［22］，可以計算出邏輯Petri 網模型的擬合度。由圖12 可見，三種方法都有比較好的擬合度，均在0.9 以上，但Goldratt 方法略低一些。本文方法擬合度一直維持在比較高的水平。

圖12 三種方法的擬合度對比Fig.12 Fitting degree comparison among three methods

圖13 是三種修復方法在不同數量跡下精度變化曲線。本文所提出邏輯Petri 網模型精度根據文獻［22］計算得到。Fahland 方法修復精度在0.68 左右浮動，Goldratt 方法修復精度在0.74 左右浮動，而本文修復方法精度在0.85 左右。因此，本文修復方法具有相對較高的精度。

圖13 三種方法的精度對比Fig.13 Precision comparison among three methods

4 結語

本文針對Fahland、Goldratt 方法等修復方法因加入自環、不可見變遷使模型結構發生變化、精度降低等問題，提出一種針對并行結構托肯重演的修復方法。當日志動作和模型動作一致時，通過增強重演來計算日志中缺失和遺留托肯值來判斷原模型中并行變遷的關系，采用邏輯Petri 網的方式來修復模型。當實際的日志動作比模型動作多時，先根據新增日志動作計算子日志，再挖掘子模型；然后將子模型插入原模型中；最后在邏輯Petri 網的基礎上結合給定算法進行修復。通過實驗與Goldratt 方法、Fahland 方法進行對比分析，驗證所提方法的擬合度與精度均相對較高。本文僅對并行結構進行了討論，并未針對循環結構等進行討論，這將作為今后研究的方向。