基于増廣Petri網生成受控日志

邵叱風，方賢文，王吳松

(1.安徽理工大學 數學與大數據學院，安徽 淮南 232001； 2.安徽科技學院 信息與網絡工程學院，安徽 蚌埠 233030)

0 引 言

Petri Net[1]是常用系統建模語言之一，廣泛應用于過程挖掘[1]、模型修復[3]、建模優化[4]及算術計算[5]等諸多領域。Prom是一個過程挖掘相關插件平臺，可以利用XES[6]標準日志及挖掘算法生成結果，并利用Petri網等建模語言對挖掘結果進行可視化處理[7]。為了更好地測試和評估過程挖掘算法，需要人工生成的日志。文獻[8]提出了一種日志生成方法，可用于隨機生成多角度流程模型并進行仿真，以合成多角度事件日志。文獻[9]可以根據用戶定義的控制流規范隨機自動地生成過程樹和事件日志。它采用了一種通用的兩步方法：生成一個流程樹，然后將該樹仿真為事件日志，在文獻[10]中進行了描述。但通常需要生成日志解決的問題如：通過模擬所選過程模型來生成事件日志，然后對此日志應用了新穎的過程發現算法，最后將發現的模型與初始模型進行比較發現了特殊結構。但是在現實事件日志中，經常缺少這樣的“特殊結構”。因此，能夠以受控方式生成模型和日志很重要。文獻[11]提出了一種基于BPMN模型生成日志的方法，但目前Petri網與BPMN之前的轉換仍有諸多不便。在少量日志挖掘模型時，為提升挖掘能力，文獻[12]提出一種基于增強日志的過程挖掘方法，加強了算法對多屬性日志的依賴并提升對并發結構的識別能力，但在重構日志時較為復雜。在日志生成后可能存在一些與預期或模型有差距需修改的內容，文獻[13]提出了一種基于神經網絡的日志修復方法，在識別大量不同活動標簽效率表現一般。

本文利用增廣Petri網直接模擬系統運行并實現一種用于生成XES標準事件日志的具體方法，且通過直接修改多重集日志來降低生成預期日志的難度。

1 準備知識

本節介紹了部分定義用以輔助理解日志生成工具中關于網的輸入、運行以及日志的導出。限于篇幅原因Petri網相關定義見文獻[1]。在此選用増廣Petri網作為建模語言，可在建模過程中以更簡潔的結構便捷模擬現實條件。

定義1[1]帶抑制弧Petri網:一個帶抑制弧的Petri網是一個五元組∑=(S,T,F,I,M)， 其中， (S,T,F) 是一個網，M是網的一個標識，I?S×T稱為抑制弧集，I∩F=Φ。

對于t∈T， 如果

則t在標識M有發生權，記為M[t>。

若M[t>， 則變遷t在M可以發生，t在M發生產生新的標識M′

為增加PSLG(Petri simulation log generation)的實用性，利用輸入矩陣對網模型進行輸入。對如圖1所示的6種關系和庫所中的token數量均在輸入矩陣中進行了定義。

圖1 輸入矩陣中庫所與變遷的6種關系

定義2 輸入矩陣：一個輸入矩陣M是基于矩陣元素擴展生成的，元素Mij定義了庫所si與變遷tj的關系。最后一位數字代表兩個元素之間的流弧關系，其中0-5分別表示NULL、arc(s,t)、arc(t,s)、arc(s,t) 和arc(t,s)、inhibit(s,t)、inhibit(s,t) 和arc(t,s)， 元素Mij剔除最后一位數字即為當前關系庫所si中token的數量，一行元素token之和即當前系統si中token的數量，輸入矩陣及元素拓展如圖2所示。

圖2 輸入矩陣及元素擴展

如果λ(t)≠τ，t∈T， 那么t是可觀測的，反之t是靜默變遷。標簽的執行語義是根據狀態和狀態轉換定義的。標簽網的狀態由標識的概念俘獲。

標簽網N=(P,T,F,λ) 的標識M一般表示Token到庫所的分配。如M(p) 分配Token在庫所p,p∈P。

PSLG含豐富的日志導出功能，支持定義7系統記錄、事件日志以及XES格式日志文件的導出，分別用作系統執行過程的展示、多重集日志的展示以及Prom等工具的直接可用日志。

定義7 系統記錄、事件日志:跡是一個有限的標簽序列。系統記錄為跡的可重復記錄集，一個事件日志是一組跡上的多重集。假定跡上的每個標簽都代表一個事件，即一個活動的發生。此外假定標簽在跡中出現的順序表出了事件發生的順序，即j>i， 那么位于跡i處的標簽表示的事件發生在位于跡j處的標簽表示的事件之前。

系統記錄形如：R1=[,,,];

事件日志形如：L1=[10,7,5]。

為統一軟件的日志輸入格式，文獻[6]提出了XES格式日志文件，是XML語言的一種擴展。主要由分層組件(Hierarchicalcomponents)、屬性組件(Attributecomponent)、全局屬性(Globalattributes)、分類器(Classifiers)和擴展(Extensions)共5個部分構成。

2 日志生成方法及實現

現有的日志生成方法大多是隨機生成的模型日志，大量的冗余數據導致事件結構之間約束不可控；或者生成日志的方式較為繁瑣，需要學習新的編程語言。以上方法在日志生成時難以生成實驗需要的特定的滿足模型結構的日志，并憑此去檢驗算法在某些行為模式上的識別能力。

在此提出對系統直接仿真生成指定條數的執行跡，后期處理生成多重集事件日志及XES標準日志的方法。主要過程為：①系統建模；②推導輸入矩陣；③初始化輸入模型；④手動或隨機執行模型過程；⑤統計執行記錄生成事件日志；⑥XES標準日志的轉換。其中系統建模部分即利用増廣Petri網對現有系統進行模擬，在此不做贅述。

對于大規模負載程序的開發，程序的處理流程并非單一的一條主線，而是錯綜負載的網狀結構。面向對象編程比起面向過程編程更能夠應對復雜類型的程序開發；面向對象編程擁有更加豐富的特性(封裝、繼承、抽象和多態)，利用這些特性可以使得代碼更加易擴展，易維護，易復用。下面給出具體Java應用實現日志生成方法的過程。

2.1 輸入矩陣

為了便捷化輸入Petri網模型，Java應用采用定義2形式的輸入矩陣進行模型輸入。如圖3所示利用split(“ ”)分割矩陣得m條字符串(即網包含m個庫所s1,s2,…sm)， 每條字符串split(“,”) 可獲得n個元素(即網包含n個變遷t1,t2,…,tn), 第i條字符串第j個元素為庫所si與變遷tj的關系描述，結合for循環利用定義1計算模型中弧的個數，初始化變遷、庫所及弧的數組，并依據矩陣元素關聯庫所和變遷，得到初始化Petri網模型。抑制弧、庫所流向變遷及變遷流向庫所的關聯代碼如Code_1所示。

aArray[z][total]=pnlist[z].inhibitor("arc"+total,pArray[i],tArray[l]);//添加庫所到變遷的抑制弧

aArray[z][total]=pnlist[z].arc("arc"+total,pArray[i],tArray[l]);//添加庫所到變遷的流弧

aArray[z][total]=pnlist[z].arc("arc"+total,tArray[l],pArray[i]);//添加變遷到庫所的流弧

圖3 利用輸入矩陣初始化Petri網的原理

2.2 網的運行

為保證流程執行的隨機性，定義AutoRun()方法，使用ArrayList記錄下Petri網當前狀態所有具備觸發條件的變遷，Math.random()在數組大小范圍內生成隨機數k， 觸發數組中下標為k的元素包含的變遷后進入下一個可達狀態，并對觸發的變遷進行記錄，如此循環直到當前狀態中無可觸發變遷。具體實現的部分代碼如Code_2所示：

(1)for (intj=1;j

(2) intfireState=1;

(3) intlogLength=0;

(4) while (fireState>0) {

(5) ArrayListwaitRun=new

ArrayList();

(6)fireState=0;

(7) for (inti=0;i

size();i++) {

(8) if (pnlist[j].getTransitions().get(i).canFire()) {

(9)waitRun.add(pnlist[j].getTransitions().get(i));

(10)fireState++;

(11) }

(12) }

(13) if (waitRun.size()>0) {

(14) intmax=waitRun.size();

(15) intranNum=(int) (Math.random() *max);

(16)waitRun.get(ranNum).fire();

(17)logArea.append(waitRun.get(ranNum).get Name() + ",");

(18)logLength++;

(19) }

(20) }

(21)}

fireState為標識可觸發變遷的個數，logLength為統計每條執行記錄的長度。定義canFirestate=1，進入while循環，初始化可觸發變遷緩存數組waitRun，標記當前可觸發變遷個數為0。Code_2(7-12)對網中變遷進行遍歷，方法canFire()判斷變遷能否觸發，如果可以數組waitRun記錄下可觸發變遷且fireState=fireState+1，Code_2(13-19)如果waitRun含有可觸發變遷，利用Math.random()*max在數組大小范圍內生成隨機數，觸數組中對應下標的元素所含變遷，到達下一可達狀態，循環至終態即遍歷網中變遷無一可觸發，fireState=0結束循環。

2.3 多重集日志

為統計網運行記錄庫中每條記錄出現頻次，增加了普通的事件記錄轉為多重集日志的功能。編寫工具類String-SameCount，利用HashMap 對事件記錄進行統計，利用 判斷是否包含此條記錄，如果有則計數增加，如果沒有增加此條記錄(如圖4所示)。具體實現代碼如Code_3所示。

(1)public class StringSameCount {

(2) private HashMapmap;

(3) private intcounter;

(4) public StringSameCount() {

(5)map= new HashMap();

(6) }

(7) public void hashInsert(Stringstring) {

(8) if (map.containsKey(string)) {

(9)counter= (Integer)map.get(string);

(10)map.put(string, ++counter);

(11) } else {

(12)map.put(string, 1);

(13) }

(14) }

(15) public HashMap getHashMap() {

(16) returnmap;

(17) }

(18)}

Code_3定義了一個日志跡計數的功能，通過統計網運行記錄，map記錄每條執行跡的執行次數，生成一個跡上的多重集事件日志。Code_3(8-13)判斷當前map中是否含有當前字符串ri(執行記錄)，如果有則對此key=ri對應的value值進行加1(即增加一次執行次數)，如果沒有則新增key=ri,value=1(即新增一種執行跡，并記執行次數為1)。

2.4 XES標準日志

Prom是一個過程挖掘插件平臺，XES為該平臺日志支持標準。為減少日志后期處理，增加導出日志的可用性，增加了XES標準日志導出功能。主要是遍歷系統執行記錄，將每條執行記錄記為一個Trace，記錄中的事件記為一個Event，并對key=”concept:name”、key=”time:timestamp” 進行賦值，再與文件的頭文件進行拼接，生成XES格式日志。具體實現代碼如Code_4所示：

(1)public static String pLog(StringtxtLog, StringlogName) {

(2) Stringfile=headerOfFile;// XES格式日志頭文件

(3) String[]Ilist=txtLog.split(" ");

(4) for (inti=0;i

(5)file=file+" ";

(6)caseID++;

(7) String[]splitLog=Ilist[i].split(",");

(8) for (intj=0;j

(9) SimpleDateFormatPdf=new SimpleDateFormat("yyyy-MM-dd");// 設置日期格式

(10) SimpleDateFormatLdf=new SimpleDateFormat("HH:mm:ss");// 設置日期格式

(11) intx=1+(int) (Math.random() * 1000);

(12)file=file+" "

+"

+Pdf.format(new Date())+"T"

+ " "

+ "

+"=”complete”/> "

+ " ";

(13) }

(14)file=file+" ";

(15) }

(16)file=file+"";// XES格式日志結尾

(17) returnfile;

(18)}

Code_4中，txtLog為系統運行記錄，logName為日志導出時文件的名稱，headOfFile為XES標準日志拼裝時的頭部文件(可自定義)。Code_4(3)按行分割系統運行記錄，獲得記錄列表；Code_4(4-15)為日志中層信息的拼裝，其中Code_4(12)完成中層信息內部event的拼裝，通過遍歷運行記錄中的活動，完成事件名稱及執行時間的賦值，Code_4(14)補全 標簽； Code_4(16)補全 標簽。

為調節網中部分變遷的發生頻率、屏蔽部分運行路徑、增加日志噪音等，通過編輯定義7形式多重集日志的方式進行實現。對于記錄 (t0,t1,t3,t2,t5,t6,t8,t9,t11,t13,t14;47;)，t0,t1,t3,t2,t5,t6,t8,t9,t11,t13,t14； 用作XES日志event組裝源數據，數字47代表此條跡的執行次數即在日志中的條數。依據輸入矩陣創建日志界面如圖5(a)所示，多重集日志轉XES日志界面如圖5(b)所示。

圖5 方法實現的界面截圖

3 實驗評估

PSLG實現日志生成方法，主要是對系統進行建模，直接仿真模型運行，記錄網的運行情況，并通過工具類OperationOfLog.java、StringSameCount.java對之進行處理生成多重集事件日志及XES標準日志，并支持多重集日志直接轉換為XES標準日志。相較于PIPE、CPNTools和Tina等工具，PSLG更注重于模型信息及執行結果的展示，表1給出了輸入方式、模型數據、記錄生成和結果導出共4個方面對比結果。

表1 工具的多方面對比

為檢驗方法的效率及有效性，基于BPIC2020數據中的Domestic Declarations.xes和Request For Payment.xes兩個日志文件，使用Prom平臺中的Mine with Inductive visual Miner S.J.J.Leemans插件挖掘得到如圖6所示Petri模型，轉換為輸入矩陣如下所示。

圖6 Domestic Declarations流程模型(左)與Request For Payment流程模型(右)

inputmatrixofDomesticDeclarations11,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 02,02,01,01,01,01,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,02,02,02,02,00,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,02,01,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,02,00,00,01,01,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,02,02,00,00,01,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,02,02,01,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,02,01,01,01,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,02,02,02,01,00,00,00,00,00,00,00,00 00,00,00,00,00,00,02,00,00,00,00,00,00,00,00,00,02,01,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01,01,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,00,01,01,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,02,02,01,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02

inputmatrixofRequestForPayment11,01,00,00,00,01,00,00,01,00,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 02,00,01,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,02,02,02,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,02,02,01,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,02,02,02,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,02,02,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,02,01,01,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,02,02,01,01,00,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,02,01,00,00,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01,00,00,00,01,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01,00,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,00,01,00,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,00,01,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01,00,00,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,02,01,00,00,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01,01,00,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,02,01,00,00,00 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,01,01,01 00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,02,02,02

利用PSLG工具為這兩個模型各生成執行記錄10 000條；同時構造一個變遷個數為60的直鏈網模型(保證每條執行跡長度相等)，并為其生成執行記錄1000條。利用以上數據對工具的效率進行分析，并對其穩定性、可移植性以及日志的有效性等進行實驗分析。所有的測試均在配有I5-7300HQ 2.5 Ghz四核處理器和16 GB內存的機器上進行，使用Java SE 1.7開發包。

3.1 耗時分析

為檢驗工具運行穩定性，在執行直鏈模型時，記錄下變遷觸發時間，對大小為60×1000的時間數據繪制如圖7所示。其中變遷觸發時間大多在100 ns～1000 ns之間，保持較高的變遷觸發穩定性。

圖7 變遷觸發時間展示(60×1000)

圖8 不同跡的觸發時間

圖9 不同日志大小的生成時間

3.2 日志有效性

為驗證日志有效性，首先利用日志挖掘出Petri網模型與原模型對比，對于BPIC模型生成的事件日志，再次使用Prom中Mine with Inductive visual Miner S.J.J.Leemans插件，以消除不同算法對挖掘結果的影響。將BPIC的兩個生成日志導入Prom挖掘結果與原模型保持一致。

圖10 隨日志大小變化的精度和適應度

鑒于日志大小在100時precision已達到1，僅對前100條跡組成的日志進行時間分析如圖11所示，前100條跡長度各不相同，生成時間在一定范圍內對應變化(圖11(a))，日志生成耗時與日志大小成正比(圖11(b))。

圖11 前100條跡組成日志的時間分析

3.3 編輯有效性

PSLG是對現有模型進行日志生成，但日志中跡的執行次數、不同事件發生頻次具有一定隨機性，對于模型生成日志的修改有以下3種方案：

(1)可通過修改輸入矩陣即可修改(直接修改了用于日志生成的模型，執行次數、頻次仍不可控)；

(2)對于已生成的XES日志可通過直接修改XES文件(文件結構復雜，且體積一般較大)；

(3)對于已生成的多重集日志可通過改變序列及執行次數，再利用圖5(b)所示插件轉為XES日志(不同執行序列是有限的，變遷增刪便捷，序列發生次數易修改)。

對于Domestic Declarations模型的運行記錄(100條發生序列)，分別刪除變遷t6,t10,t15,t20， 導入Prom利用Alpha插件挖掘結果如圖12所示，利用方法(3)調節日志是可行的。

4 結束語

本文提出一種對現有系統生成受控日志的方法，使用増廣Petri對現有系統進行建模，便于盡可能滿足真實系統運行條件。PSLG利用矩陣輸入的方式輸入Petri網模型，在主界面展示了網的一些屬性值用以確認模型輸入的正確性；通過隨機觸發可發生變遷達到下一可達狀態并記錄觸發過程，重復模擬n次網的完整運行以生成大小為n條的系統運行記錄；利用Hash Map對系統運行記錄進行分類統計生成多重集日志；遍歷系統運行記錄，通過嵌套循環拼裝的方式生成XES標準日志，并以此為模板增加了多重集日志轉為XES標準日志的方法；最后的實驗驗證了實現插件PSLG的可行性、穩定性、日志的有效性及可編輯性。

圖12 修改后日志的Alpha挖掘結果

通過PSLG生成日志，為過程挖掘、模型修復等諸多依賴于日志的算法驗證及評估提供了有效助力。未來工作包括使用更多建模語言作為輸入，豐富日志中的屬性，增加日志導出格式，高頻行為的可控觸發以及基于受控日志的過程挖掘、一致性檢驗等算法的研究。