基于Petri網接口變遷的交互流程模型模塊網挖掘方法

翟鵬珺，方賢文，劉祥偉

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

基于Petri網接口變遷的交互流程模型模塊網挖掘方法

翟鵬珺，方賢文，劉祥偉

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

交互流程模型的模塊分解是查找流程模型變化域的核心內容之一，已有的模塊分解方法多是基于完整的流程模型，通過挖掘對比流程模型中所有活動的行為關系將流程模型分解為多個模塊網。但是在基于單純的事件日志分解交互流程模型方面，目前的模塊分解方法存在一定的局限性。提出基于Petri網接口變遷的交互流程模型模塊網挖掘方法，首先基于系統運行所記錄的局部有效事件日志確定其中各活動間的前驅后繼關系，并得到相應的活動前驅后繼關系表。然后，基于前驅后繼關系頻繁的活動查找接口變遷，同時考慮無后繼變遷的活動。其次，通過分析接口變遷的前集變遷查找交互流程模型中各個模塊網的初始變遷，并由初始變遷開始，利用活動前驅后繼關系表，逐個添加活動，以此挖掘交互流程模型的模塊網。論文最后通過實例驗證該優化方法的有效性。

Petri網；事件日志；接口變遷；模塊分解；模塊網

模塊最初由Gallai提出［1］，常用于研究圖表、2-結構、分類方面等。如今，隨著模塊應用的普遍性，許多研究著手將模塊和流程模型相結合對交互流程模型進行分解。合理的模塊分解不僅能清晰地分析交互流程模型的結構，還有利于分析行為對間的關系，從而快速有效地查找流程模型中的變化域或分析模型。

目前在模塊分解方面，已經提出了一些研究。文獻［2］提出基于微分Petri網的業務流程模塊適配方法，指出修復變化域最容易想到的方法是模塊替換，利用極小支持數來確定最佳適配模塊，使其滿足結構上的最穩定性。良構流程模型在拓撲學上與基于Petri網行為輪廓的弱序關系圖結構相關。一種基于弱序關系圖的模塊分解方法在文獻［3］中被提出，利用模塊分解對源流程模型進行抽象，根據模塊分解的特點構造其抽象模型，并說明模塊分解樹可以在線性時間內被構建。對業務流程模型進行模塊分解，不僅能夠將流程模型進行細化，還可以按需要進行分類。文獻［4］結合模塊分解的優勢，基于模塊行為輪廓分析模塊間的行為關系，并以模塊間的共用輸出點為觀測點，分析業務流程模型的變化域。文獻［5］利用功能構架將功能模塊分解，并基于通訊行為輪廓查找特征的模塊日志，從而運用歸納挖掘算法［6］挖掘模塊網。文獻［7］通過繪制所有模塊的所有事件的數據，可以很容易地可視化模塊的類型隨時間的變化模式。但上述的交互流程模塊分解方法要求已知完整的流程模型，對于只知道系統運行所記錄的事件日志的情況并不適用。針對這一缺陷本文提出了基于Petri網接口變遷挖掘交互流程模型模塊網的模塊分解方法，該方法克服了必須挖掘完整流程模型的缺陷，能夠基于簡單的事件日志有效挖掘交互流程模型的模塊網。

1 動機例子

目前，儲蓄卡、支付寶等支付方式在購物過程中被更多顧客采用。以某商場支付寶支付系統為例，考慮其系統運行所記錄的事件日志，如表1所示。表1中所記錄的事件日志并非系統運行的所有事件日志，且其中可能包含系統不能重放的事件日志，即無效事件日志。

模塊分解在分析流程模型結構和查找流程模型變化域的過程中具有很重要的作用，有效的模塊分解可以更快查找出模型中的變化域，從而很好的優化模型。但是對于只有事件日志的系統（如支付系統），已有的模塊分解方法首先要基于事件日志挖掘出完整的交互流程模型，然后基于完整的模型進行模塊分解，在一定程度上具有局限性。為了在不挖掘出完整的流程模型情況下合理分解流程模型，本文提出基于Petri網接口變遷的交互流程模型模塊網的挖掘方法。

表1 支付系統的事件日志

2 基礎知識

下面僅介紹與本文密切相關的概念，其它概念及術語參見文獻［8］。

定義1 （Petri網）設一個Petri網N=(P,T,F)是一個三元組：

（1）P和T分別是有限的庫所集和變遷集；

（2）P≠?，T≠?且P?T=?；

（3）F=(P×T)?(T×P)表示PN的流關系，(P?T,F)是強連通圖；

一個Petri網N=(P,T,F)，給定一個節點，則有n的前集的后集另外，一個流程模型Petri網PN和一個初始標識M0，就確定了一個標識網，變遷t在標識M0下可以發生（M0[t＞），如果稱M1為從M0可達的，若存在t∈T，使得M0[t＞M1。

定義2（標簽Petri網）一個網BN=(N,l)是標簽Petri網，其中N=(P,T,F)是一個Petri網。標簽函數l∈T→UA，UA是活動名稱集［10］。

一個標簽Petri網BN=(N,l)定義了一個Petri網中各個節點和流關系的有向圖，N中每個可見變遷t∈dom(l)都有一個活動標簽標簽Petri網是Petri網的一個特殊子集，可以被用來構建流程模型。在一個標簽Petri網BN中，用i來表示初始標識，用f來表示終止標識。

定義3（事件日志）A是一個有限的活動集。跡可以被描述為活動的一個有限序列，即σ∈A?。一個事件日志L是跡的一個多重集，即L∈Μ(A?)［11］。

定義4（模塊網）N=(P,T,F,l)是一個標簽Petri網：

（4）空集?和網N中的所有活動集TA所對應的模塊網，是網N的平凡模塊網，其他均為非平凡模塊網［3］。

3 基于Petri網接口變遷逐步挖掘交互流程模型的模塊網

已有的交互流程模型模塊分解方法主要基于完整的流程模型，本部分基于Petri網接口變遷提出交互流程模型模塊網的挖掘算法。該算法主要是基于有效的事件日志，確定各個事件活動的前驅后繼關系，結合活動前驅后繼關系分析查找接口變遷和初始變遷。然后，由初始變遷開始逐個添加后繼活動，以此挖掘交互流程模型的模塊網。挖掘出的模塊網不一定為合理的流程模型，為檢驗其有效性給出完全流程模型的定義。

定義5（完全流程模型）模型N=(P,T,F,l)是一個帶標簽的流程模型，M:P→{0,1…}是流程模型中的一個標識，χ是標識集合，N是一個完全流程模型，當且僅當對任意的，總存在σj使得

定義7（前驅后繼關系）模型N=(P,T,F,L)是一個帶標簽的流程模型，對任意的變遷t∈T存在一個或多個前驅變遷和后繼變遷。前驅變遷，且前驅變遷有直接的流關系到變遷t后繼變遷，且變遷t有直接的流關系到后繼變遷

算法1：挖掘交互流程模型的模塊網

輸入：事件日志Li

步驟1：確保輸入事件日志Li為有效的日志。即對每個事件日志，在系統中都可以被有效重放。刪除無效的事件日志，保留有效事件日志。轉步驟2；

步驟2：基于步驟1所保留的有效事件日志中各個活動事件的前驅后繼關系，繪制相應的活動前驅后繼關系表。轉步驟3；

步驟3：查找活動前驅后繼關系表中活動關系緊密的部分，在圖表中對該部分活動進行標記。轉步驟4；

步驟4：對步驟3的標記部分進行分析，確定接口變遷。圖表中被標記部分中的活動ej（j≥1），若其無后繼活動，則記錄該活動為接口變遷。轉步驟5；

步驟5：考慮活動前驅后繼關系表中無后繼活動的活動ej。若其至多5個連續前驅活動中，至少存在一個活動e，使得在不發生ej的情況下仍有合理的發生序列σj，則該活動ej無后繼活動是由于token數不夠。且該活動ej與接口變遷相連，為接口變遷的前驅活動e←j。否則，該活動為結束變遷te。轉步驟6；

步驟6：確定初始變遷ts。接口變遷前集變遷中，后繼變遷最多的變遷以及總是發生在某些前集變遷之前的活動為模塊網的初始變遷。轉步驟7；

步驟7：由初始變遷開始，通過活動前驅后繼關系表，逐個添加活動，直至無后繼活動或結束變遷。轉步驟8；

圖1 算法流程圖

4 實例分析

本部分以支付寶支付系統（動機例子）的事件日志為例來分別說明本文基于Petri網接口變遷挖掘交互流程模型模塊網的方法的可行性。

分析表1中14個事件日志，對于有效日志中每個活動得到其前驅活動和后繼活動。如案例1中活動A無前驅活動，其后繼活動為B；活動D的前驅活動和后繼活動分別為C和I；活動J無后繼活動，其前驅活動為I。根據每個活動的前驅后繼關系繪制活動前驅后繼關系表，表中縱向表示各個活動的前驅關系，橫向則表示各個活動的后繼關系。從表2中很容易可以標記出前驅后繼關系緊密的活動，如表2中方框所標記的活動。對于表2中左上角的方框，其中包含了4個活動A、B、C、D的前驅后繼關系。可以看出活動D無后繼活動，所以活動D為接口變遷，同理可知活動N和Q也是接口變遷。

表2 活動前驅后繼關系表

另外，由表2可以觀察到活動H、J和R均無后繼活動。由于活動H和J的前驅活動G和I存在其他后繼活動L和K，且由案例7、8、11等可知模型中存在不包含活動H和J的發生序列使得活動L和K有效發生，所以活動H和J無后繼活動是因為不滿足Petri網變遷發生規則，即其前集庫所中的token數不夠。但是，對于活動R的連續5個前驅活動Q、P、L、O、K，均沒有不包含活動R的合理發生序列，所以判定活動R為結束變遷。

考慮接口變遷D的前集變遷A、B和C，由表2可知活動A的發生總在活動B發生之前，且活動C的后繼活動數最多（3個），由此判定活動A和活動C為初始變遷（同理可得活動M為初始變遷）。根據活動的前驅后繼關系，由初始活動A，C和M開始，逐個添加活動無后繼活動J、H或結束變遷R。由于活動J、H前集庫所中的token數不夠，其后繼活動為接口變遷D。綜上所述，支付系統的三個模塊網如圖2所示。

圖2 支付系統模塊網

5 結語

目前，交互流程模型模塊分解是查找流程模型變化域的重要任務之一。基于完整交互流程模型模塊分解的方法要求必須已知系統的完整流程模型，這類模塊分解方法在只得知系統運行所記錄的事件日志的情況下具有一定的局限性。為了在不挖掘完整流程模型的前提下合理分解交互流程模型，本文提出了基于Petri網接口變遷的交互流程模型模塊網挖掘方法。該方法避免了挖掘過程中存在的一些不必要的工作，在一定程度上減少了挖掘過程的工作量。而且，基于事件日志中各個活動的前驅后繼關系查找接口變遷，提高了本文挖掘算法的精準度。

未來關于交互流程模型模塊網的挖掘，進一步的研究主要是針對存在交叉序結構的流程模型以及對挖掘出的模塊網進行一致性檢測評估。

［1］Gallai T.Transitiv orientierbare graphen［J］.Acta Mathematica Hungarica，1967，18（1-2）：25-66.

［2］方賢文，陶小燕，劉祥偉.基于微分 Petri網的業務流程模塊適配方法［J］. 電子學報，2017，45（4）：777-781.

［3］Sergey Smirnov，Matthias Weidlich，Jan Mendling.Business process model abstraction based on synthesis from well-structured behavioral profiles［J］.International Journal of Cooperative Information Systems，2012，21（01）：55-83.

［4］Fang X，Liu L，Liu X.Analyzing method of change region in BPM based on module of Petri net［J］.Information Technology Journal，2013，12（8）：1655-1659.

［5］van der Werf J M，Kaats E.Discovery of functional architectures from event logs［C］//PNSE@Petri Nets，2015：227-243.

［6］Leemans S J J，Fahl and D，van der Aalst W M P.Discovering p tit e=quot;pagenum er_eboo models from event logs-a constructive approach［C］.International Conference on Application and Theory ofPetri Nets and Concurrency，Springer Berlin Heidelberg，2013：311-329.

［7］Buijs J，van der Aalst W M P.Enabling interactive process analysis with process mining and visual analytics［J］.BIOSTEC，2017（2017）：573-578.

［8］吳哲輝.Petri網理論［M］.北京：機械工業出版社，2006：6-22.

［9］Smirnov S，Weidlich M，Mendling J.Business process model abstraction based on behavioral profiles［C］.International Conference，Heidelberg：Springer Berlin Heidelberg，2010（6470）：1-16.

［10］Aalst W M P V D，Kalenkova A，Rubin V，et al.Process discovery using localized events［M］.Application and Theory of Petri Nets and Concurrency，2015：287-308.

［11］Kalenkova A A，Lomazova I A.Discovery of cancellation regions within process mining techniques［M］.IOS Press，2014.

［12］Zha H，Wang J，Wen L，et al.A workflow net similarity measure based on transition adjacency relations［J］.Computers in Industry，2010，61（5）：463-471.

The Module Net of Interaction Process Model Mining Method Based on Interface Transitions of Petri Net

ZHAI Pengjun，FANG Xianwen，LIU Xiangwei
（School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001）

Module decomposition of the interaction process model is one of the core contents of search change region of process model.The existing module decomposition methods are mostly based on a complete process model，the process model is decomposed into multiple module nets by mining and comparing the behavior relation of all activities in the process model.However，there are some limitations in the current module decomposition method of decomposing interaction process model just based on the event log.This paper puts forward a mining method of module net of interaction process model based on the interface transition of Petri net.Firstly，determine the predecessor and successor relation of the activities that from the local effective event logs which are recorded by the system running，and obtain the corresponding table of predecessor and successor relation of activities.Then，search the interface transition based on the activities with frequent precursor successor relation，and consider the activities without successor transition.Secondly，determine the initial transition in each module net of the interaction process model by analyzing the pre-set of the interface transition，and add activity one by one that start from the initial transition using the table of precursor successor relation of activities to mining the module net of interaction process model.Finally，an example is given to prove the effectiveness of the mining method.

Petri net；event log；interface transition；module decomposition；module net

TP391.9

A

1672-9870（2017）05-0132-04

2017-06-05

國家自然科學基金項目（61572035，61402011，61272153）；安徽省自然科學基金（1508085MF111）；安徽省高校自然科學基金重點項目（KJ2014A067）；安徽理工大學研究生創新基金（2017CX2048）；安徽省優秀青年基金項目（ZY290）

翟鵬珺（1991-），女，碩士研究生，E-mail：877191453@qq.com