白二凈，李曉巖，杜玉越

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

0 引言

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

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

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

1 基本概念

本章簡要介紹相關概念，元組、事件日志［6-9］、Petri 網(wǎng)［1-5］、邏輯Petri網(wǎng)［17］、工作流網(wǎng)［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 網(wǎng)。t1為邏輯輸入變遷，I（t1）=(p1?p2) ∧p3是t1的邏輯輸入函數(shù)，表示有2 種情況會觸發(fā)t1。①p1和p3中存在托肯；②p2和p3中存在托肯。t2為邏輯輸出變遷，O（t2）=p5∨p6是t2的邏輯輸出函數(shù)，表示t2引發(fā)后會有3 種情況：①p5中有托肯；②p6中有托肯；③p5和p6中都有托肯。

圖1 邏輯Petri網(wǎng)模型Fig.1 Logic Petri net model

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

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

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

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

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

2 并行結構模型修復

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

2.1 模型修復

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

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

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

圖2 工作流網(wǎng)模型WFN1Fig.2 Workflow net model WFN1

在start 狀態(tài)（初始狀態(tài)）除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，其他庫所處托肯值不變，以此方法計算后續(xù)所有變遷處庫所托肯值，計算結果見表1。最后，M(p10)=0 代表重演結束。結束（end）后，M(p8)=-1 代表缺失的托肯，M（p5）=1 代表遺留的托肯。

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

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

定義9并行結構對集合SCRP，并行變遷集合CT。設A是所有活動的集合，PT是工作流網(wǎng)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節(jié)點是并行結構操作符時，并行結構開始和結束對存儲于SCRP集合中所有具有并行關系的變遷存儲于CT集合中；對PT中所有非葉子節(jié)點都重復執(zhí)行步驟2）～7）；當N為葉子節(jié)點時程序結束；步驟18）返回結果。

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

算法3 并行結構修復方法：步驟1）給LPN賦值；步驟2）調(diào)用算法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）計算邏輯輸出函數(shù)O（t）和邏輯輸入函數(shù)I（t）的值。最后一步返回修正后的LPN′模型。算法3 的時間復雜度為O（n3）。下面以L1為例給出基于托肯重演的并行結構修正例子。

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

2.2 含子模型修復

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

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

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

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

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

圖5 工作流網(wǎng)模型WFN2Fig.5 Workflow net model WFN2

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

圖6 工作流網(wǎng)模型WFN? Fig.6 Workflow net model WFN?

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

3 仿真實驗

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

3.1 模型修復

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

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

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

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

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

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

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

表3 事件日志Tab.3 Event logs

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

3.2 模型評估

根據(jù)奧卡姆剃須刀原則［21］，分析采用不同方法修復原模型后其簡潔度。表4 給出三種方法修復后在增加庫所、不可見變遷、自環(huán)等方面的對比。根據(jù)表4，本文方法增加8 個庫所，而Fahland 方法增加11 個，Goldratt 方法因自環(huán)存在未增加新庫所。從增加弧數(shù)量角度分析，本文方法增加12 條，而Fahland 方法和Goldratt 方法分別增加46 和16 條。從增加自環(huán)變遷數(shù)分析，本文方法未增加自環(huán)，而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］是描述過程模型一致性檢查最為重要的參數(shù)。根據(jù)不同數(shù)量級的跡，圖12 給出了不同方法的擬合度對比。根據(jù)文獻［22］，可以計算出邏輯Petri 網(wǎng)模型的擬合度。由圖12 可見，三種方法都有比較好的擬合度，均在0.9 以上，但Goldratt 方法略低一些。本文方法擬合度一直維持在比較高的水平。

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

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

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

4 結語

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