石彎彎，劉祥偉，王麗麗

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，淮南 232001）

基于區(qū)域事件日志的過(guò)程挖掘方法研究

石彎彎，劉祥偉，王麗麗

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，淮南 232001）

過(guò)程挖掘是從事件日志中運(yùn)用挖掘方法得到過(guò)程模型。已有的挖掘方法在處理大量事件日志上還存在一定的局限性，提出一種基于區(qū)域日志過(guò)程挖掘方法，首先根據(jù)事件日志間任務(wù)的可達(dá)性分為不同區(qū)域，在此基礎(chǔ)上將不同區(qū)域日志轉(zhuǎn)化為間接繼承矩陣再對(duì)應(yīng)Petri網(wǎng)，建立區(qū)域過(guò)程模型；然后，將各個(gè)區(qū)域進(jìn)行融合，得到完整的過(guò)程模型。最后，通過(guò)分析建模實(shí)例驗(yàn)證算法的可行性。

過(guò)程挖掘；Petri網(wǎng)；可達(dá)性

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

本文采取的方法：（1）將事件日志任務(wù)的可達(dá)性分為不同區(qū)域；（2）各個(gè)區(qū)域中將事件日志中任務(wù)的可達(dá)性轉(zhuǎn)化為間接繼承矩陣，得到子過(guò)程模型；（3）子過(guò)程模型作為一個(gè)塊結(jié)構(gòu)，將各個(gè)塊結(jié)構(gòu)再次轉(zhuǎn)化為間接繼承矩陣；（4）將得到的間接繼承矩陣轉(zhuǎn)化為Petri圖得到最終過(guò)程模型。

1 基本概念

1.1 Petri網(wǎng)基本概念

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

1.2 行為輪廓的定義

在跡語(yǔ)義的基礎(chǔ)上，行為輪廓描述了一個(gè)網(wǎng)系統(tǒng)的行為特征和變遷的潛在并發(fā)的順序。它的定義是在弱序概念的基礎(chǔ)上，給出了變遷對(duì)之間的依賴關(guān)系。

定義［11］2 （弱序）設(shè)是一個(gè)網(wǎng)，初始標(biāo)識(shí)為M0，一對(duì)變遷是弱序，記作ta?tb，當(dāng)且僅當(dāng)存在一個(gè)發(fā)生序列σ=t1,...,tn使得并且有a=i,b=i，1≤i＜j≤n。

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

2 基于區(qū)域日志的挖掘方法

2.1 基于區(qū)域的事件日志

由于現(xiàn)在的過(guò)程模型越來(lái)越復(fù)雜，而且許多網(wǎng)系統(tǒng)可以被分為不同區(qū)域，因此可以將圖1過(guò)程模型化，根據(jù)任務(wù)的相關(guān)性分為5個(gè)區(qū)域，r1和r5為公共區(qū)域，r2，r3，r4區(qū)域互不交互，因此在分析過(guò)程模型時(shí)，可以針對(duì)不同區(qū)域進(jìn)行分類討論。本文討論根據(jù)事件日志任務(wù)的可達(dá)性，將事件日志分為不同模塊，針對(duì)不同模塊進(jìn)行挖掘，提高過(guò)程挖掘效率。

圖1 區(qū)域Petri網(wǎng)模型

2.2 將日志轉(zhuǎn)換成間接繼承矩陣值

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

定義4：（間接繼承運(yùn)算符）在工作流中定義間接繼承基礎(chǔ)命令關(guān)系如下：工作流例如令ab∈T定義為：

（1）a?wb僅當(dāng)存在且例如（間接繼承）

（2）a→→wb當(dāng)且僅當(dāng)a?wb且b?wa（因果關(guān)系）

（3）awb當(dāng)且僅當(dāng)（無(wú)直接關(guān)系和間接關(guān)系）

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

（1）若Mi,j=1時(shí)，則Ai→LAj；即事件日志任務(wù)存在因果關(guān)系；

（2）否則Mi,j=0時(shí)，則Ai→LAj；即事件日志任務(wù)無(wú)直接和間接關(guān)系。

基于日志行為輪廓中的各種結(jié)構(gòu)利用繼承矩陣表示日志的可達(dá)性如下： /

（1）順序模式

在Petri網(wǎng)中A，B，C D順序模式如圖2所示。

圖2 順序模式Petri網(wǎng)圖

表1 順序模式對(duì)應(yīng)的繼承矩陣

（2）選擇模式

選擇模式相互排斥，在Petri網(wǎng)中如圖3所示。

圖3 選擇模式Petri圖

表2 選擇模式對(duì)應(yīng)的繼承矩陣

如上表2的值表示了B，C之間沒(méi)有繼承關(guān)系，且對(duì)A，D的作用值是相等的。

（3）循環(huán)模式

在Petri圖中事件日志任務(wù)B、C循環(huán)發(fā)生，如圖4所示，對(duì)應(yīng)的繼承矩陣如表3所示。

圖4 循環(huán)模式Petri圖

表3 循環(huán)模式對(duì)應(yīng)的繼承矩陣

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

（4）平行模式

在Petri網(wǎng)中事件日志任務(wù)B，C同時(shí)發(fā)生,如圖5所示，對(duì)應(yīng)的繼承矩陣值如表4所示。

圖5 平行模式Petri圖

表4 平行模式對(duì)應(yīng)的繼承矩陣

基于上述對(duì)模型中事件日志任務(wù)的可達(dá)性對(duì)模型進(jìn)行劃分區(qū)域及Petri網(wǎng)與繼承矩陣的轉(zhuǎn)換，提出了基于區(qū)域事件日志算法，算法步驟如下：

算法：基于區(qū)域事件日志的挖掘算法

輸入：事件日志；

輸出：過(guò)程模型；

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

（2）將各區(qū)域事件日志任務(wù)因果關(guān)系轉(zhuǎn)化為間接繼承矩陣，分別計(jì)算出行和列值的總和；

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

（4）為選定的任務(wù)，運(yùn)用邏輯算子的相似性；

（5）選定的任務(wù)是在一個(gè)塊結(jié)構(gòu)，試圖發(fā)現(xiàn)事件日志任務(wù)所屬模式；

（6）創(chuàng)建一個(gè)子Petri網(wǎng)Ni=(1,2,3...n)框架；

（7）重復(fù)未選中的任務(wù)執(zhí)行所有步驟直至所有任務(wù)都被選中；

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

3 實(shí)例分析

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

圖6 對(duì)應(yīng)的區(qū)域事件日志

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

（1）根據(jù)日志r1區(qū)域用矩陣表示如表5所示。

表5 間接繼承矩陣

圖7 r1區(qū)域過(guò)程模型

則得出B，C是循環(huán)關(guān)系且A，BC，D是繼承關(guān)系（2）根據(jù)日志r2區(qū)域用矩陣表示，如表6 所示。

表6 間接繼承矩陣

由表6得E,F是平行關(guān)系且對(duì)D，G，H，I，影響值相同，分析得出E，F(xiàn)為平行關(guān)系，則E,F歸為一類，繼續(xù)用矩陣表達(dá)在日志中D，EF，G，H，I的關(guān)系。

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

由表7得出G，H為選擇關(guān)系，且對(duì)D，EF，I的影響值相同。

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

由表8得出EF，GH為選擇關(guān)系，且對(duì)D，EF，GH，I的影響值相同，由此分析得出E，F(xiàn)為平行關(guān)系，G，H為選擇關(guān)系，則EF，G，H為選擇關(guān)系，用Petri網(wǎng)圖表示，如圖8所示。

圖8 r2區(qū)域過(guò)程模型

（3）合并r1和r2區(qū)域

表9 間接繼承矩陣

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

圖9 融合區(qū)域的過(guò)程模型

4 結(jié)論

基于Petri網(wǎng)及行為輪廓的研究，通過(guò)對(duì)事件日志任務(wù)的可達(dá)性分析，對(duì)事件日志劃分區(qū)域，再轉(zhuǎn)化為間接繼承矩陣，最終得到過(guò)程模型。對(duì)事件日志分區(qū)域能大大減少計(jì)算量，避免過(guò)程模型的過(guò)度擬合性。

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

［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，F(xiàn)ahland 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，F(xiàn)ahland 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網(wǎng)導(dǎo)論［M］.北京：機(jī)械工業(yè)出版社，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

國(guó)家自然科學(xué)基金（61402011，61572035）；安徽省自然科學(xué)基金（1508085MF111）；安徽省高校自然科學(xué)基金重點(diǎn)項(xiàng)目（KJ2014A067）

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