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

翟鵬珺，方賢文，劉祥偉

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

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

翟鵬珺，方賢文，劉祥偉

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

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

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

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

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

1 動(dòng)機(jī)例子

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

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

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

2 基礎(chǔ)知識(shí)

下面僅介紹與本文密切相關(guān)的概念，其它概念及術(shù)語(yǔ)參見文獻(xiàn)［8］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：事件日志Li

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

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

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

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

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

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

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

圖1 算法流程圖

4 實(shí)例分析

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

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

表2 活動(dòng)前驅(qū)后繼關(guān)系表

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

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

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

5 結(jié)語(yǔ)

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

未來(lái)關(guān)于交互流程模型模塊網(wǎng)的挖掘，進(jìn)一步的研究主要是針對(duì)存在交叉序結(jié)構(gòu)的流程模型以及對(duì)挖掘出的模塊網(wǎng)進(jìn)行一致性檢測(cè)評(píng)估。

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

［2］方賢文，陶小燕，劉祥偉.基于微分 Petri網(wǎng)的業(yè)務(wù)流程模塊適配方法［J］. 電子學(xué)報(bào)，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］.北京：機(jī)械工業(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

國(guó)家自然科學(xué)基金項(xiàng)目（61572035，61402011，61272153）；安徽省自然科學(xué)基金（1508085MF111）；安徽省高校自然科學(xué)基金重點(diǎn)項(xiàng)目（KJ2014A067）；安徽理工大學(xué)研究生創(chuàng)新基金（2017CX2048）；安徽省優(yōu)秀青年基金項(xiàng)目（ZY290）

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