翟鵬珺，方賢文，劉祥偉

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

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

翟鵬珺，方賢文，劉祥偉

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

交互流程模型的模塊分解是查找流程模型變化域的核心內(nèi)容之一，已有的模塊分解方法多是基于完整的流程模型，通過挖掘?qū)Ρ攘鞒棠Ｐ椭兴谢顒拥男袨殛P系將流程模型分解為多個模塊網(wǎng)。但是在基于單純的事件日志分解交互流程模型方面，目前的模塊分解方法存在一定的局限性。提出基于Petri網(wǎng)接口變遷的交互流程模型模塊網(wǎng)挖掘方法，首先基于系統(tǒng)運行所記錄的局部有效事件日志確定其中各活動間的前驅(qū)后繼關系，并得到相應的活動前驅(qū)后繼關系表。然后，基于前驅(qū)后繼關系頻繁的活動查找接口變遷，同時考慮無后繼變遷的活動。其次，通過分析接口變遷的前集變遷查找交互流程模型中各個模塊網(wǎng)的初始變遷，并由初始變遷開始，利用活動前驅(qū)后繼關系表，逐個添加活動，以此挖掘交互流程模型的模塊網(wǎng)。論文最后通過實例驗證該優(yōu)化方法的有效性。

Petri網(wǎng)；事件日志；接口變遷；模塊分解；模塊網(wǎng)

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

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

1 動機例子

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

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

表1 支付系統(tǒng)的事件日志

2 基礎知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1：挖掘交互流程模型的模塊網(wǎng)

輸入：事件日志Li

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

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

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

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

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

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

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

圖1 算法流程圖

4 實例分析

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

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

表2 活動前驅(qū)后繼關系表

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

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

圖2 支付系統(tǒng)模塊網(wǎng)

5 結(jié)語

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

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

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

［2］方賢文，陶小燕，劉祥偉.基于微分 Petri網(wǎng)的業(yè)務流程模塊適配方法［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，F(xiàn)ahl 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網(wǎng)理論［M］.北京：機械工業(yè)出版社，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，F(xiàn)ANG 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）；安徽理工大學研究生創(chuàng)新基金（2017CX2048）；安徽省優(yōu)秀青年基金項目（ZY290）

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