基于區域事件日志的過程挖掘方法研究

石彎彎，劉祥偉，王麗麗

（安徽理工大學 數學與大數據學院，淮南 232001）

基于區域事件日志的過程挖掘方法研究

石彎彎，劉祥偉，王麗麗

（安徽理工大學 數學與大數據學院，淮南 232001）

過程挖掘是從事件日志中運用挖掘方法得到過程模型。已有的挖掘方法在處理大量事件日志上還存在一定的局限性，提出一種基于區域日志過程挖掘方法，首先根據事件日志間任務的可達性分為不同區域，在此基礎上將不同區域日志轉化為間接繼承矩陣再對應Petri網，建立區域過程模型；然后，將各個區域進行融合，得到完整的過程模型。最后，通過分析建模實例驗證算法的可行性。

過程挖掘；Petri網；可達性

近年來，隨著信息技術的發展，過程挖掘的應用越來越廣泛。過程挖掘的目的是從事件日志中提取模型，發現真實的過程并對其進行監控、改進。各種過程發現算法已經被提出并且被采用，文獻［1］中基于局部事件的挖掘算法，通過給每個事件分配一個非空的域集定位事件；文獻［2］中描述了從不完備事件日志中發現流程模型結構,分析不完備日志對過程發現的影響，引入概率行為，利用這些關系處理不完備日志，給出基于這些概率關系的算法,用于重新發現流程模型；文獻［3］中啟發式的算法在構建過程模型時考慮到了任務的頻率；文獻［4］中在考慮間接繼承的基礎上把事件日志任務的可達性用矩陣表示,根據矩陣值把總體事件日志分離成子日志，不斷迭代，自動發現流程塊結構；文獻［5］中基于局部日志的過程發現把Petri網分為不同區域，再對不同區域分析；文獻［6］中基于語言的域挖掘算法，算法中域理論從行為的演變方面來構建Petri網；文獻［7］中采用了不同的方法，把過程挖掘問題分解成了較小的多個問題，從而提高了過程挖掘效率；文獻［8］介紹了從事件日志中挖掘出塊結構的過程模型方法；此外在文獻［9］中提出對于過程發現模型，一般使用4個標準進行判斷：適合性、簡潔性、精確性、一般性，避免過程模型的過度擬合或低度擬合。

本文采取的方法：（1）將事件日志任務的可達性分為不同區域；（2）各個區域中將事件日志中任務的可達性轉化為間接繼承矩陣，得到子過程模型；（3）子過程模型作為一個塊結構，將各個塊結構再次轉化為間接繼承矩陣；（4）將得到的間接繼承矩陣轉化為Petri圖得到最終過程模型。

1 基本概念

1.1 Petri網基本概念

定義［10］1 滿足下列條件的三元組N=(P,T,F)稱作一個網：

1.2 行為輪廓的定義

在跡語義的基礎上，行為輪廓描述了一個網系統的行為特征和變遷的潛在并發的順序。它的定義是在弱序概念的基礎上，給出了變遷對之間的依賴關系。

定義［11］2 （弱序）設是一個網，初始標識為M0，一對變遷是弱序，記作ta?tb，當且僅當存在一個發生序列σ=t1,...,tn使得并且有a=i,b=i，1≤i＜j≤n。

（4）若t1?t2且t2?t1，則稱交叉序關系，記作t1×t2；

2 基于區域日志的挖掘方法

2.1 基于區域的事件日志

由于現在的過程模型越來越復雜，而且許多網系統可以被分為不同區域，因此可以將圖1過程模型化，根據任務的相關性分為5個區域，r1和r5為公共區域，r2，r3，r4區域互不交互，因此在分析過程模型時，可以針對不同區域進行分類討論。本文討論根據事件日志任務的可達性，將事件日志分為不同模塊，針對不同模塊進行挖掘，提高過程挖掘效率。

圖1 區域Petri網模型

2.2 將日志轉換成間接繼承矩陣值

要求的事件日志轉化成間接繼承矩陣，首先要引用以下定義：

定義4：（間接繼承運算符）在工作流中定義間接繼承基礎命令關系如下：工作流例如令ab∈T定義為：

（1）a?wb僅當存在且例如（間接繼承）

（2）a→→wb當且僅當a?wb且b?wa（因果關系）

（3）awb當且僅當（無直接關系和間接關系）

定義5：（間接繼承矩陣）定義L為n個事件組成的日志，且表示日志中的一組事件間接繼承用矩陣是二進制矩陣(0,1)當

（1）若Mi,j=1時，則Ai→LAj；即事件日志任務存在因果關系；

（2）否則Mi,j=0時，則Ai→LAj；即事件日志任務無直接和間接關系。

基于日志行為輪廓中的各種結構利用繼承矩陣表示日志的可達性如下： /

（1）順序模式

在Petri網中A，B，C D順序模式如圖2所示。

圖2 順序模式Petri網圖

表1 順序模式對應的繼承矩陣

（2）選擇模式

選擇模式相互排斥，在Petri網中如圖3所示。

圖3 選擇模式Petri圖

表2 選擇模式對應的繼承矩陣

如上表2的值表示了B，C之間沒有繼承關系，且對A，D的作用值是相等的。

（3）循環模式

在Petri圖中事件日志任務B、C循環發生，如圖4所示，對應的繼承矩陣如表3所示。

圖4 循環模式Petri圖

表3 循環模式對應的繼承矩陣

B C D 0 0 0 1 1 0 1 1 0 1 1 0

（4）平行模式

在Petri網中事件日志任務B，C同時發生,如圖5所示，對應的繼承矩陣值如表4所示。

圖5 平行模式Petri圖

表4 平行模式對應的繼承矩陣

基于上述對模型中事件日志任務的可達性對模型進行劃分區域及Petri網與繼承矩陣的轉換，提出了基于區域事件日志算法，算法步驟如下：

算法：基于區域事件日志的挖掘算法

輸入：事件日志；

輸出：過程模型；

（1）根據事件日志任務因果關系將事件日志分為不同區域ri(i=1,2,3...n)；

（2）將各區域事件日志任務因果關系轉化為間接繼承矩陣，分別計算出行和列值的總和；

（3）選擇任務組（兩個或更多個）具有最高的行中的值的總和；

（4）為選定的任務，運用邏輯算子的相似性；

（5）選定的任務是在一個塊結構，試圖發現事件日志任務所屬模式；

（6）創建一個子Petri網Ni=(1,2,3...n)框架；

（7）重復未選中的任務執行所有步驟直至所有任務都被選中；

（8）重組Petri網流程框架，得到最終模型N。

3 實例分析

為了驗證基于區域事件日志的挖掘算法，給定一組事件日志，其中事件日志包含6種情形，任務包括A，B，C，D，E，F，G，H，I；根據事件任務的可達性將6種情形分為2個區域，其中事件任務A，B，C為r1區域；事件任務D，E，F，G，H，I為r2區域；r1和r2區域間的事件任務相互獨立，事件任務D為公共區域；如圖6所示。

圖6 對應的區域事件日志

將圖6中各區域的事件日志用繼承矩陣表示。

（1）根據日志r1區域用矩陣表示如表5所示。

表5 間接繼承矩陣

圖7 r1區域過程模型

則得出B，C是循環關系且A，BC，D是繼承關系（2）根據日志r2區域用矩陣表示，如表6 所示。

表6 間接繼承矩陣

由表6得E,F是平行關系且對D，G，H，I，影響值相同，分析得出E，F為平行關系，則E,F歸為一類，繼續用矩陣表達在日志中D，EF，G，H，I的關系。

表7 間接繼承矩陣（減少）

由表7得出G，H為選擇關系，且對D，EF，I的影響值相同。

表8 間接繼承矩陣（減少）

由表8得出EF，GH為選擇關系，且對D，EF，GH，I的影響值相同，由此分析得出E，F為平行關系，G，H為選擇關系，則EF，G，H為選擇關系，用Petri網圖表示，如圖8所示。

圖8 r2區域過程模型

（3）合并r1和r2區域

表9 間接繼承矩陣

由表9矩陣值得出ABC，DEFHHI為繼承關系，由此得出日志的過程模型Petri圖如圖9所示。

圖9 融合區域的過程模型

4 結論

基于Petri網及行為輪廓的研究，通過對事件日志任務的可達性分析，對事件日志劃分區域，再轉化為間接繼承矩陣，最終得到過程模型。對事件日志分區域能大大減少計算量，避免過程模型的過度擬合性。

本文雖然在過程挖掘上減少了計算量，但是需要保證事件日志區域劃分的正確性，針對過程挖掘還有許多問題有待解決，例如通過挖掘方法得到的過程模型是否與事件日志相一致，需要在以后的工作中繼續研究。

［1］AalstWVD,Weijters T，Maruster L.Workflow mining：discovering process model from event logs［J］.IEEE Transactions on Knowledge and Data Engineering，2004，16（16）；1128-1142.

［2］Leemans S J J，Fahland D，Aalst W M P V D.Discovering block-structured process models from incomplete event logs［M］.Application and Theory of Petri Nets andConcurrency.Sprin-erInternationalPublishing，2014：91-110.

［3］Carmona J，Cortadella J，Kishinevsky M.A Regionbased algorithm for discovering Petri Nets from event logs［J］.Springer Belin Heidelberg，2008（5240）：358-373.

［4］Boushaba S，Kabbaj.MI，BakkouryZ.Process discovery：automated approach for block discovery［C］.International Conference on Evaluation of Novel Approaches To Software Engineering.IEEE，2014：1-8.

［5］Aalst WMPVD，KalenkovaA，Rubin.V，et al.Process discovery using localized events［M］.Application and Theory of Petri Nets and Concurrency，Springer International Publishing，2015：287-308.

［6］Leemans SJJ，Fahland D，Aalst WMPVD.Discovering block-structured process models from event logs-a constructive approach［C］.International Conference on Application and Theory of Petri Nets and Concurrency，2013，23（5）：311-329.

［7］A.K.Alves de Medeiros.Genetic process mining PhD thesis［J］.The Nethherlands，2006，21（3）：105-107.

［8］Aalst W M P V D.A general divide and conquer approach for process mining［C］.Computer Science and Information Systems.IEEE，2013.

［9］Werf J，Kaats E.Discovery of functional architectures from event logs［C］.International Workshop on Petri Nets and Software Engineering，2015：227-243.

［10］吳哲輝.Petri網導論［M］.北京：機械工業出版社，2006：15-78.

［11］Weidlich M，Mendling J，Weske M.Efficient consistency measurement based on behavioral profiles of process models［J］.Software Engineering IEEE Transactions on，2011，37（3）：410-429.

Research on Process Mining Based on Region Event Log

SHI Wanwan，LIU Xiangwei，WANG Lili
（College of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001）

The mine model of process is gained by mining method from event log.With the limiting from exsiting mining method，it is difficult to dealing with a large number of event logs.In this paper，a mining algorithm based on regin log is proposed.Firstly，according to the accessibility of task between different event logs，the different regio logs are transformed into indirect inheritant martrix.The complete model can be got by mixing them together.Finally，the effectiveness of our model is verified through analysis.

process mining；petri net；accessibility

TP391.9

A

1672-9870（2017）04-0120-05

2017-03-28

國家自然科學基金（61402011，61572035）；安徽省自然科學基金（1508085MF111）；安徽省高校自然科學基金重點項目（KJ2014A067）

石彎彎（1993-），女，碩士研究生，E-mail：1091258607@qq.com