基于Petri網(wǎng)行為輪廓從事件日志中挖掘隱變遷的方法

王曉悅，方賢文，曹芮浩

(安徽理工大學理學院 安徽　淮南　232001)

?

基于Petri網(wǎng)行為輪廓從事件日志中挖掘隱變遷的方法

王曉悅，方賢文，曹芮浩

(安徽理工大學理學院 安徽淮南232001)

隱變遷是指一些存在于過程模型中，但沒有出現(xiàn)在日志序列中的變遷。這樣的變遷會大量存在于現(xiàn)實的模型中。從事件日志中尋找挖掘隱變遷的方法是過程挖掘技術(shù)的一個重要的難題。目前針對自由選擇網(wǎng)有一些解決辦法，但是對于復雜的過程模型有一定的局限性。本文提出了基于Petri網(wǎng)行為輪廓尋找隱變遷的方法。首先根據(jù)發(fā)生頻率最高日志序列得出源模型，再根據(jù)剩余的日志序列一步步優(yōu)化源模型從而找到隱變遷，最后通過評價指標來判定模型的合理性。

事件日志；行為輪廓；隱變遷；過程模型

在近幾年，隨著計算機的發(fā)展，各大企業(yè)都在尋找一種不但可以滿足客戶要求還可以通過提高業(yè)務水平節(jié)約成本的辦法，換句話說就是用更短的時間生產(chǎn)更多的產(chǎn)品給客戶提供更好的服務，從而提出了業(yè)務流程挖掘這項技術(shù)。但是挖掘業(yè)務流程模型的過程中往往會出現(xiàn)一些存在于過程模型中，但沒有出現(xiàn)在日志序列中的變遷，同時這樣的變遷又大量存在于現(xiàn)實的模型中。從事件日志中挖掘隱變遷可以很好的還原模型，提高操作的運轉(zhuǎn)效率，既而達到高效率的生產(chǎn)及服務。

在日志中挖掘不可見變遷最開始是由W.M.P.van der Aalst等人提出來的，他分析了不可見任務產(chǎn)生的原因。在文獻[1]中提出了Petri的相關(guān)概念。在文獻[2-4]17中有提到不可見任務在哪幾種情形下產(chǎn)生。在過程挖掘中常常會因為類似的原因出現(xiàn)一些存在于過程模型中，但沒有出現(xiàn)在日志序列中的變遷。這樣的變遷稱之為隱變遷。然而從事件日志中挖掘隱變遷在流程挖掘中是一個巨大挑戰(zhàn)。文獻[5]163-176中提出了判定日志與模型一致性的分析方法，通過日志序列在模型中重放來計算其合理性和適當性。國外學者van der Aalst已經(jīng)做了很多關(guān)于不可見任務挖掘的文章，文獻[6]中給出了Petri網(wǎng)的相關(guān)知識。文獻[7-8]講述了有關(guān)流程挖掘的方法。文獻[9]先介紹了行為輪廓的相關(guān)概念，之后Weidlich. M等人又提出因果行為輪廓的概念，因果行為輪廓是行為輪廓的一個補充及擴展在原來的三種關(guān)系基礎上添加了共生關(guān)系。在文獻[10]中基于流程挖掘提出了一種新穎的方法去解決異常的事件日志，這種方法能夠形成一個與源模型相關(guān)的新的進程模型，最后基于新的進程模型重新執(zhí)行事件日志。在文獻[11]中把流程挖掘的技術(shù)運用到社會網(wǎng)絡服務中檢測異常行為的出現(xiàn)，使得社會網(wǎng)絡服務系統(tǒng)更加完善。

在流程挖掘方面，文獻[12]中給出了日志的相關(guān)概念。在文獻[13]里給出了一個新的建模方法，此建模方法支持精確流程建模。文獻[14]提出了一種與Web服務的相關(guān)的挖掘。文獻[15]將流程挖掘技術(shù)運用到現(xiàn)實的結(jié)賬過程中，結(jié)果會對其產(chǎn)生影響并取得進步。文獻[16-17]說明了流程挖掘這項技術(shù)可以運用在醫(yī)療方面，介紹了基于過程挖掘這項技術(shù)來分析門診的流程，并對其數(shù)據(jù)進行集成、探索和分析。提出了PALIA算法，把流程挖掘這項技術(shù)運用到衛(wèi)生保健的設計和質(zhì)量控制的流程。文獻[18]在挖掘過程中分別從用戶、時間的角度來對比方法的可用性。文獻[19]將流程挖掘技術(shù)運用在現(xiàn)實教育中，通過對學生行為的分析來促進流程比較。

本文主要通過行為輪廓的關(guān)系來挖掘事件日志中的隱變遷。通過發(fā)生篇頻率最高的且最長的日志序列得出源模型，再通過剩余的序列一步步優(yōu)化。最后通過計算合理性及適當性得出所挖掘出模型的完備性。這種方法能夠方便快捷的挖掘出日志中的隱變遷，從而使得模型更加完備。

1　研究動機

在本文的介紹中，已經(jīng)提到了挖掘隱變遷的重要性，并且介紹了挖掘隱變遷的算法。在實際生活中，不乏存在不可見任務的業(yè)務流程日志。本節(jié)中利用一個簡單的例子來證明隱變遷的存在性及挖掘隱變遷的重要性。下面給出了一個操作記錄的日志序列L：{ABCEDFGHJ， ABEDFGHJ， ABJ， ABCEGHJ，ABEGHJ，ABCDEFGHJ，ABDEFGHJ，ABDCEFGHJ，ABDFCEGHJ，ABCEGDFHJ，ABCEDGFHJ，ABCDEGFHJ，ABDCEGFHJ}

α算法挖掘出來的模型如圖1、圖2所示。

圖1　挖掘的模型圖

圖2　挖掘的模型圖

分析圖1與圖2可知，這兩個模型的合理性與行為適當性的值偏低。在運轉(zhuǎn)的過程中會出現(xiàn)死鎖的情況。而且它們產(chǎn)生的日志軌跡并不符合過程挖掘的準則。在過程挖掘中所得到的模型必須完全覆蓋所有的日志軌跡。在本文的第四部分就介紹了基于行為輪廓挖掘日志中的隱變遷的合理性。

2　基本知識

這部分介紹了petri網(wǎng)的相關(guān)概念。

定義1[6]324(流程模型)設P=(A，ai，a0，C，F(xiàn)，T)為一個六元組的流程模型，

-A為一個非空的活動變遷節(jié)點集，C為控制流節(jié)點集，A和C不相交；

-ai∈A為一個最初的活動變遷，a0∈A為一個最終的活動變遷；

-F?((A{a0})∪C)×((A{ai})∪C)為流關(guān)系；

-T∶C|→{and，or，xor}流程模型控制流的類型。

定義2[6]325(弱序關(guān)系(流程模型))設P=(A，ai，a0，C，F(xiàn)，T)是一個六元組的流程模型，εp為它的執(zhí)行序列集。?P?(A×A)包含所有的變遷對(x，y)，如果εp存在一條執(zhí)行序列σ=n1，…，nm，并且存在j∈{1，…，m-1}，j

流程模型中弱序關(guān)系是以變遷對為基礎的，在弱序關(guān)系的基礎上又定義了變遷集合的三種關(guān)系即嚴格序關(guān)系、排他序關(guān)系和交叉序關(guān)系。這三種關(guān)系稱為行為輪廓。

定義3[6]325(行為輪廓(流程模型))設P=(A，ai，a0，C，F(xiàn)，T)為一個六元組的流程模型，變遷對(x，y)∈(A×A)至多存在下面三種關(guān)系的一種：

-嚴格序關(guān)系→p，當且僅當x?py，y?/px.

-排他序關(guān)系+p，當且僅當x?/py，y?/px

-交叉序關(guān)系‖p，當且僅當x?py，y?px.

這三種關(guān)系的集合BP={→P，+P，‖P}組成了行為輪廓。

此外，如果變遷對(x，y)滿足嚴格序關(guān)系，即x→y，那么變遷對(y，x)滿足逆嚴格序關(guān)系，即y→-1x。

下面介紹了關(guān)于日志的行為輪廓的相關(guān)概念。與流程模型行為輪廓的定義方式類似，日志的行為輪廓是定義在日志弱序關(guān)系的基礎上的。

定義4[6]327(弱序關(guān)系(日志))設LP=n1，…，nm是流程模型P=(A，ai，a0，C，F(xiàn)，T)中的一條日志。弱序關(guān)系?L?(AL×AL)包含了所有的變遷對(x，y)，如果存在兩個下標指數(shù)j，k∈{1，…，m-1}使得j

定義5[6]327(行為輪廓(日志))設LP=n1，…，nm為流程模型P=(A，ai，a0，C，F(xiàn)，T)中的一條日志，變遷對(x，y)∈(AL×AL)至多存在下面兩種關(guān)系的一種：

-嚴格序關(guān)系→L，當且僅當x?Ly，y?/Lx.

-交叉序關(guān)系‖L，當且僅當x?Ly，y?Lx.

這兩種關(guān)系的集合BPL={→L，‖L}稱之為日志中的行為輪廓。

注：一條日志中的兩個活動變遷是不存在排他序關(guān)系的。

3　基于行為輪廓挖掘事件日志中的隱變遷

在本文的介紹中已經(jīng)提到，在過程挖掘中尋找隱變遷的重要性。文獻[2]15中也已經(jīng)給出了尋找不可見任務的算法，本文的這一部分將運用行為輪廓的的關(guān)系定性分析日志序列，從而尋找隱變遷，最終達到還原模型的目的，此方法可以直觀，簡單且不失準確性的還原模型。下面首先給出了隱變遷的形式化定義，再給出基于Petri網(wǎng)行為輪廓挖掘隱變遷的一個算法。

首先根據(jù)日志序列在模型中的重放來評價模型的合理性程度，下面根據(jù)[5]163-176中合理性的判斷標準。

式中：k為給定日志中的不同軌跡數(shù)，n為日志軌跡中所含的數(shù)目，m為日志軌跡中缺少的標識數(shù)，r為日志軌跡中遺留的標識數(shù)，c為日志軌跡中消耗的標識數(shù)，p為日志軌跡中產(chǎn)生的標識數(shù)。

最后，在f→1的情況下再考慮行為適當性aB(指的是所觀察到的行為在此模型中的精確程度)。

式中：k為給定日志中的不同軌跡數(shù)，n為日志軌跡中所含的數(shù)目，x表示日志軌跡重放時就緒變遷的平均數(shù)目。m表示模型中可見任務的個數(shù)。

定義6[12]21(日志的弱行為輪廓)設L為一條日志，對任意兩個變遷P，Q∈L，則P與Q之間的至多存在下面三種關(guān)系的一種：

1) 如果滿足Ν(P，Q)≠0∧Ν(P，Q)=0，則稱為嚴格序關(guān)系→L，記作P→LQ；

2) 如果滿足Ν(P，Q)≠0∧Ν(P，Q)≠0，則稱為交叉序關(guān)系‖L，記作P‖LQ；

3) 如果滿足Ν(P，Q)=0∧Ν(P，Q)=0，則稱為排他序關(guān)系+L，記作P+LQ。

我們稱集合BL={→L，‖L，+L}為日志L的弱行為輪廓。

其中，對任意兩個變遷P和Q，N(P，Q)=n，n表示以PQ形式在所有執(zhí)行日志中出現(xiàn)的次數(shù)。下面給出一組日志序列{ACDE，ABDE，ADBE，ADCE}，根據(jù)定義6可以畫出日志活動關(guān)系如表1所示。

表1　活動關(guān)系表

定義7(標記函數(shù)[2]75)T′是進程模型的變遷集合，L′是對應的日子序列集合，標記函數(shù)l∈T′→L′是一個偏序標記函數(shù)，它把每一個變遷和日志序列相關(guān)聯(lián)。

定義8(隱變遷)T′是進程模型的變遷集合，l代表來自T′的標記函數(shù)的定義域，變遷t∈T′被稱為隱變遷當且僅當t?dom(l)，即t不在l的定義域范圍內(nèi)。

下面給出隱變遷常出現(xiàn)的幾種類型：

1) 給出完備日志W(wǎng)1={ABC，BAC}，由行為輪廓弱關(guān)系定義得知A‖LB，A→LC，B→LC，得出圖3。

圖3　不可見任務類型一

2) 給出完備日志W(wǎng)2={ABC，AC}，由行為輪廓弱關(guān)系定義得知A→LB，A→LC，B→LC，得出圖4。

圖4　不可見任務類型二

3) 給出完備日志W(wǎng)3={ABC，ABBBC}，由行為輪廓弱關(guān)系定義得知A→LB，A→LC，B→LC，得出圖5。

圖5　不可見任務類型三

4) 給出完備日志W(wǎng)4={ABCD，ACBD，ACD}，由行為輪廓弱關(guān)系定義得知A→LB，A→LC，A→LD，B‖LC，C→LD，得出圖6。

圖6　不可見任務類型四

算法1：行為輪廓挖掘隱變遷

輸入：執(zhí)行日志序列

輸出：Petri網(wǎng)模型

步驟1：在記錄產(chǎn)生的日志序列中找出發(fā)生頻率最高的且最長的日志序列(一般情況下最長的日志序列中發(fā)生作用的隱變遷最少)。

步驟2：根據(jù)日志序列得出模型簡圖(初始模型λ0)。根據(jù)最長的日志序列建立日志活動關(guān)系表，根據(jù)日志活動關(guān)系表可以畫出Petri網(wǎng)模型簡圖，此時不考慮評價指標。

步驟3：將已確定的具有嚴格序關(guān)系的變遷相連形成的鏈，把它們視為整體，剔除冗余的日志序列(冗余的日志序列指的是在嚴格序關(guān)系的變遷中夾有與其存在并列關(guān)系的變遷)。找出缺省的變遷，可以確定與缺省變遷并列存在隱變遷。

步驟4：剩余日志序列中用發(fā)生頻率最高的且最長的來優(yōu)化模型λ0中的控制流，從而得到模型λ1。根據(jù)執(zhí)行日志來計算模型的合理性f，根據(jù)合理性來判斷日志的重放效果。

步驟6：所有日志重放完畢，模型λ1即為所挖掘的模型。

注：1)如果日志序列中的起始變遷或者終止變遷出現(xiàn)不一致，則考慮起始變遷或者終止變遷是隱變遷的情況。

2)如果出現(xiàn){ABC，ABBC}此類日志序列，則考慮此自交叉變遷與隱變遷構(gòu)成循環(huán)結(jié)構(gòu)的情況。

4　案例說明

在本節(jié)中，利用一個簡單的實例來說明上述挖掘隱變遷方法的可行性。表2是各個日志的軌跡和實例數(shù)(即頻數(shù))。

表2　執(zhí)行日志列表

下面給出了一個操作作記錄的日志序列L：

{ABCEDFGHJ，ABEDFGHJ，ABJ，ABCEGHJ，ABEGHJ，ABCDEFGHJ，ABDEFGHJ，ABDCEFGHJ，ABDFCEGHJ，ABCEGDFHJ，ABCEDGFHJ，ABCDEGFHJ，ABDCEGFHJ}

1) 首先根據(jù)幾個最長的序列且發(fā)生頻率較高的可以畫出如圖7所示的簡圖。

圖7源模型M0

2) 再把具有具有并列關(guān)系的嚴格序(集)分為一個模塊，如圖8所示。

圖8　模塊圖M1

3) 剔除冗余的日志序列{ABCDEFGHJ， ABDCEFGHJ，ABDFCEGHJ}及{ABDEFGHJ， ABDFEGHJ}并由缺省的C可以判斷出與C并列的存在一個隱變遷，如圖9所示。

圖9　源模型優(yōu)化一M2

4) 由缺省D、F的這個模塊的序列{ABCEGHJ}可以判斷出與D、F并列的存在一個隱變遷，如圖10所示。

圖10　源模型優(yōu)化二M3

5) 由剩余的序列{ABJ，ABEGHJ}優(yōu)化得出圖11。

圖11　源模型優(yōu)化三M4

表3　一致性評價表

5　結(jié)束語

本文提出了基于行為輪廓尋找挖掘事件日志中隱變遷的方法。首先介紹了進程模型與日志的相關(guān)概念。然后講述了日志與模型間的一致性判別方法。在其之后，引出了本文的核心部分，即基于行為輪廓挖掘事件日志中的隱變遷。首先根據(jù)最長的日志序列集得出源模型，再根據(jù)剩余日志中最長的序列一步步優(yōu)化源模型從而找到隱變遷，最后通過與源模型進行比較得出挖掘出帶有隱變遷模型的合理性及適當性。

本文基于Petri網(wǎng)行為輪廓提出了從事件日志中挖掘隱變遷的方法，但是在實際的流程挖掘中還存在其它異常變遷，比如block變遷。所以在未來的工作中，應該對更多的異常變遷加以分析，使得流程挖掘技術(shù)能夠更加完善。

[1]WU ZHEHUI.Petri net Introduction[M].BeiJing:Press of machinery industry,2006：5-80.

[2]WEN LIJIE.Study on process mining algorithm based on WF net[D].BeiJing: Tsinghua University.2007.

[3]W M P VAN DER AALST, B F VAN DONGEN, J HERBST, et al. Workflow Mining: A Survey of Issues and Approaches[J]. Data and Knowledge Engineering, 2003,47(2):237-267.

[4]W M P VAN DER AALST, A J M M WEIJTERS.Process Mining:A Research Agenda[J]. Computers in Industry,2004,53(3):231-244.

[5]ROZINAT A, W M P VAN DER AALST . Conformance Testing: Measuring the Fit and Appropriateness of Event Logs and Process Models [J].Computer Science,2005,3812 LNCS:163-176.

[6]MATTHIAS W, ARTEM POLYVYANYY, NIRMIT DESAI, et al. Process Compliance Measurement based on Behavioural Profiles [J]. Computers in industry, 2004, 53(3):321-343.

[7]W M P VAN DER AALST .Process Mining:Discovery, Conformance and Enhancement of Business Processes[M]. 1st Edition. Berlin: Springer, 2011: 352-374.

[8]W M P VAN DER AALST. Work-flow mining: Discovering process models from event logs [J]. Knowledge and Data Engineering ,2004, 16(9): 1 128-1 142.

[9]MATTHIAS W, JAN M. Perceived consistency between process models [J]. Information Systems, 2012, 37(2): 80-98.

[10]YANG ZHANMIN , ZHANG LIQUN , HU YUAN. A Method to Tackle Abnormal Event Logs Based on Process Mining[C]//2nd International Conference on Software Engineering, Knowledge Engineering and Information Engineering , 2014:34-38.

[11]MAHDI SAHLABADI,RAVIE CHANDREN MUNIYANDI ，ZARINA SHUKUR.Detecting Abnormal Behavior In Social Net Work Websites By Using A Process Mining Technique[J].Journal of Computer Science ,2014,10 (3): 393-402.

[12]WU JUNZHI.Researches on Mining Methods of Business Process Based on Behavioral Profiles of Petri Net[D]. HuaiNan:Anhui University of Science and Technology,2014.

[13]王廣立. 基于日志的流程挖掘算法研究[D].山東：山東大學，2008.

[14]ANDRZEJ STROINSKI, DARIUSZ DWORNIKOWSKI, JERZY BRZEZIN SKI. Resource Mining: Applying Process Mining to Resource-Oriented[J]. Systems Business Information Systems, Lecture Notes in Business Information Processing, 2014, 176: 217-228.[15]JAKUB STOLFA,MARTIN KOPKA,SVATOPLUK STOLFA,et al. An Application of Process Mining to Invoice Verification Process in SAP[J]. Advances in Intelligent Systems and Computing, 2014, 237: 61-74.

[16]MINSU CHO, MINSEOK SONG, SOOYOUNG YOO. A Systematic Methodology for Outpatient Process Analysis Based on Process Mining[J]. Lecture Notes in Business Information Processing 2014, 181: 31-42.

[17]CARLOS FERNANDEZ-LLATAS,BERNARDO VALDIVIESO,VICENTE TRAVER,et al. Using Process Mining for Automatic Support of Clinical Pathways Design[M]. Methods in Molecular Biology,2015,1 246:79-88.[18]JAKUB STOLFA, SVATOPLUK STOLFA, KATE INA SLANINOVA, JAN MARTINOVI, et al. An Impact of the User and Time Parameters to Sequence Alignment Methods for Process Mining[M]. Computer Information Systems and Industrial Management,2014,8 838: 580-591.

[19]W M P VAN DER AALST, SHENGNAN GUO, PIERRE GORISSEN. Comparative Process Mining in Education: An Approach Based on Process Cubes[J]. Lecture Notes in Business Information Processing, 2015, 203: 110-134.

(責任編輯：李麗，范君)

A Mining Method of the Hide Transitions From the Event Logs Based on theBehavioral Profiles of Petri Net

WANG Xiao-yue，F(xiàn)ANG Xian-wen，CAO Rui-hao

(School of Science, Anhui University of Science and Technology, Huainan, Anhui 232001,China)

The hide transitions exist in the process models, but can not be found in the log sequence. Such transitions exist in the realistic models. It is one of the important difficulties to find the methods about mining the hide transitions from the event logs. There are some solutions to the free choice nets, but they have some limitations due to the complex process models. The method to find hide transitions based on the behavioral profiles of Petri net is proposed in the paper. First of all, according to the highest frequency of occurrence log sequence the source model is obtained, and then, according to the remaining log sequence step by step optimization model, the hidden transitions are required. Finally, the fitness of the model by means of evaluation index is judged.

Event log； Behavioral profiles； Hide transition； Process model

2015-09-22

國家自然科學基金資助項目(61572035，61272153，61402011)；安徽省自然科學基金資助項目(1508085MF111)；安徽省高校自然科學基金資助項目(KJ2014A067，KJ2016A208)

王曉悅(1990-)，女，安徽壽縣人，在讀碩士，研究方向：Petri網(wǎng)和過程挖掘。

TP391.9

A

1672-1098(2016)03-0013-07