邵叱風(fēng) 方賢文 盛夢(mèng)君

摘要：過(guò)程挖掘的目的是通過(guò)分析系統(tǒng)中的日志以發(fā)現(xiàn)、構(gòu)建和優(yōu)化系統(tǒng)業(yè)務(wù)流程.，現(xiàn)有的過(guò)程挖掘算法大多采用從控制流角度記錄和觀察進(jìn)程工作流的系統(tǒng)日志，且日志在使用前需進(jìn)行大量預(yù)處理工作將其轉(zhuǎn)換為算法可識(shí)別的事件日志，不僅僅增加了挖掘難度，最終挖掘所獲過(guò)程模型所含屬性單一，很難準(zhǔn)確描述實(shí)際流程的運(yùn)作。為減少預(yù)處理工作，增強(qiáng)過(guò)程挖掘算法挖掘能力，基于系統(tǒng)事件執(zhí)行詳情，通過(guò)可利用屬性的提取，提出了增強(qiáng)日志的概念，并基于增強(qiáng)日志開(kāi)發(fā)出一種新的過(guò)程挖掘算法。此方法利用增強(qiáng)日志中的附加屬性，識(shí)別事件結(jié)構(gòu)，通過(guò)有色Petri網(wǎng)的加入，挖掘出具有場(chǎng)景信息的過(guò)程模型。最后通過(guò)一個(gè)具體的挖掘?qū)嵗M(jìn)一步說(shuō)明了該方法的可行性及結(jié)果的可擴(kuò)展性。

關(guān)鍵詞：過(guò)程挖掘;事件日志;過(guò)程模型;增強(qiáng)日志;有色Petri網(wǎng)

中圖分類(lèi)號(hào)：TP391.9

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098（ 2020）04-0025-08

作者簡(jiǎn)介：邵叱風(fēng)（1995-），男，安徽合肥人，在讀碩士，研究方向：Petri網(wǎng)、過(guò)程挖掘及模型修復(fù)。

數(shù)據(jù)挖掘與過(guò)程挖掘之間既有區(qū)別又有共性。就目的而言，數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中提取或挖掘出有用信息[1j，而過(guò)程挖掘是從表示流程執(zhí)行工作流的數(shù)據(jù)中挖掘流程模型。故數(shù)據(jù)是數(shù)據(jù)挖掘以及過(guò)程挖掘的基礎(chǔ)。從存儲(chǔ)方式來(lái)看二者又是不同的，前者使用的數(shù)據(jù)常用數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)、萬(wàn)維網(wǎng)或其他信息存儲(chǔ)庫(kù)[2]存儲(chǔ)信息，而后者使用的數(shù)據(jù)通常存儲(chǔ)在捕獲系統(tǒng)工作流的日志中。

在傳統(tǒng)的過(guò)程挖掘研究中使用的日志稱(chēng)為事件日志，其用于從控制流角度記錄和觀察進(jìn)程工作流。事件表示任務(wù)的執(zhí)行。不同的挖掘算法使用不同的事件日志，文獻(xiàn)[2]提出α算法，使用跡矩陣定義活動(dòng)間的順序操作符，從基本事件日志中發(fā)現(xiàn)結(jié)構(gòu)化事件模型;文獻(xiàn)[3]提出β算法為每個(gè)事件標(biāo)記一個(gè)類(lèi)型;文獻(xiàn)[4]提出λ算法將后繼任務(wù)添加到事件中。以上方法提出了不同的日志處理方案，生成不同算法所需的日志形式。

過(guò)程挖掘形式化定義用于從事件日志的一組實(shí)際執(zhí)行中提取結(jié)構(gòu)化流程的方法。過(guò)程挖掘至少在兩個(gè)方面是有用的。首先，它可以被用作一個(gè)用來(lái)查明程序真實(shí)運(yùn)作的工具;其次可用于增量分析，即將實(shí)際過(guò)程與一些預(yù)定義的過(guò)程進(jìn)行比較?；冖俣嗪撕筒⑿屑夹g(shù)的發(fā)展導(dǎo)致數(shù)字世界的驚人增長(zhǎng)[5]②隨著數(shù)字世界的發(fā)展和組織進(jìn)程的緊密結(jié)合，使得記錄和分析更多的事件[6]成為可能，過(guò)程挖掘成為工作流技術(shù)的熱點(diǎn)之一。文獻(xiàn)[7]提出了遺傳挖掘算法，該算法提出一種有效的因果矩陣結(jié)構(gòu)來(lái)提高空間搜索的效率;文獻(xiàn)[8]使用Rule -induction過(guò)程挖掘技術(shù)，提出RIPPER算法產(chǎn)生活動(dòng)間的規(guī)則;文獻(xiàn)[9]使用分治策略遞歸地構(gòu)建過(guò)程模型，直到所有的跡都被處理為止，該方法稱(chēng)為歸納式挖掘算法;文獻(xiàn)[10]提出一種由a-算法產(chǎn)生的啟發(fā)式挖掘算法，該方法僅考慮了事件的順序;文獻(xiàn)[11]闡述了靈活啟發(fā)式挖掘算法，它是一個(gè)靈活的控制流挖掘算法，提出的兩個(gè)算法都能處理噪音和低頻行為。針對(duì)過(guò)程挖掘方法有時(shí)不能獲得完備事件日志的問(wèn)題，文獻(xiàn)[12]提出一種從不完備日志中發(fā)現(xiàn)塊結(jié)構(gòu)過(guò)程模型的方法，該方法利用對(duì)完備性不敏感的概率行為關(guān)系，給出了一個(gè)適用性更強(qiáng)的過(guò)程發(fā)現(xiàn)算法;文獻(xiàn)[13]提出一種挖掘局部過(guò)程模型的方法，該方法通過(guò)生成過(guò)程樹(shù)并依據(jù)5種評(píng)估標(biāo)準(zhǔn)選擇局部過(guò)程模型，擴(kuò)展生成新的過(guò)程樹(shù)，以此迭代直到完成任務(wù)。但以上挖掘方法多以基本事件日志作為輸入，且均不能挖掘出系統(tǒng)中的場(chǎng)景信息。

本文主要工作有：首先提出增強(qiáng)日志的相關(guān)定義，繼而提出基于增強(qiáng)日志的挖掘算法（ ProcessMining-Enhanced Log，PM-EL），通過(guò)顏色Petri網(wǎng)的加入用以表達(dá)具有場(chǎng)景信息的挖掘結(jié)果;使用UML轉(zhuǎn)換結(jié)果模型說(shuō)明其可擴(kuò)展性;對(duì)比實(shí)驗(yàn)展示PM-EL算法在結(jié)構(gòu)識(shí)別上的能力。以上工作就基于事件內(nèi)部屬性對(duì)模型做出優(yōu)化[14]的工作提供了可切人點(diǎn)。

本文第1節(jié)介紹準(zhǔn)備知識(shí);第2節(jié)提出增強(qiáng)日志的概念以及基于增強(qiáng)日志的過(guò)程挖掘方法;第3節(jié)通過(guò)仿真實(shí)驗(yàn)驗(yàn)證所提方法的可行性及可擴(kuò)展性;最后總結(jié)全文并展望未來(lái)。

1 準(zhǔn)備知識(shí)

在本節(jié)中，將給出一些定義以及基本概念，用以輔助解釋提出的方法。限于篇幅，有關(guān)Petri網(wǎng)的概念及結(jié)構(gòu)的定義在此不做贅述，具體內(nèi)容可以參考文獻(xiàn)[15]。

定義2[17]（UMI2.0序列圖）序列圖是常用的且偏向于捕獲對(duì)象間行為的圖。它通?？梢耘c正在開(kāi)發(fā)的系統(tǒng)的邏輯視圖中的用例相關(guān)聯(lián)。高級(jí)序列圖（High-Ievel Sequence Diagrams，HLSD）是一個(gè)序列圖，它引用一組基本序列圖（ Basic SequenceDiagram，BSD），并使用一組交互操作符組合它們。主要的操作符是：弱順序（ SEQ）、選擇（ALT），循環(huán)（ LOOP）和并行（PAR）。

在Petri網(wǎng)的許多現(xiàn)有變種中，CPN被用于以序列圖的形式表示的組合和集成場(chǎng)景。庫(kù)所表示BSD，變遷表示操作符，如ALT、LOOP、SEQ和PAR。顏色用于區(qū)分庫(kù)所。圖l顯示了HLSD如何映射到CPN。T3表示條件為C1的操作符LOOP。操作符PAR和SEQ也可以映射，如圖2所示?？梢?jiàn)對(duì)于HLSD，可以相互轉(zhuǎn)換生成一個(gè)可表示主要的UML序列圖操作符的CPN。

2 基于增強(qiáng)日志的過(guò)程挖掘方法

過(guò)程挖掘起源于系統(tǒng)日志的使用，定義和統(tǒng)一系統(tǒng)日志是過(guò)程挖掘的關(guān)鍵步驟。過(guò)程挖掘1995年由J.E.Cook提出至今，技術(shù)方面取得了長(zhǎng)足的發(fā)展，且取得了諸多較完善的研究成果，但多以行為間控制流結(jié)構(gòu)挖掘過(guò)程模型;不同類(lèi)型的事件日志（其中可能包含略微不同的信息）被不同的挖掘算法所使用，但大多數(shù)僅從控制流角度記錄和觀察工作流。

2.1 增強(qiáng)日志

27. Add Transition To CPN（ 'PAR， New CPN）;

28. Add Place To CPN（ New Place， NewCPN）;//加入前置變遷‘par'

29. else

30. Add Place To CPN（ New Place， NewCPN）;

31. End If

32. End If

33. End If

34. End If

35.End Foreach

36. End Foreach

37. retum New CPN

3 仿真實(shí)驗(yàn)

在本節(jié)中，我們選擇了一個(gè)信息查看程序示例。使用應(yīng)用程序?qū)Χ鄨?chǎng)景登錄以及信息查看進(jìn)行操作并產(chǎn)生日志。信息查看程序檢測(cè)登錄類(lèi)型如果是普通用戶(hù)登錄，使用系統(tǒng)的登錄線(xiàn)程（場(chǎng)景1）;員工登錄增加兩個(gè)部分，校驗(yàn)工號(hào)以及工種，每部分都是由不同的線(xiàn)程來(lái)解決（場(chǎng)景2）;管理員賬號(hào)登錄，需要對(duì)登錄IP地址進(jìn)行檢測(cè)（場(chǎng)景3）;普通用戶(hù)登陸后查看信息（場(chǎng)景4）;員工登錄后查看信息（場(chǎng)景5）;管理員登陸后查看信息并對(duì)信息進(jìn)行過(guò)濾（場(chǎng)景6）。不同用戶(hù)登陸后查看信息是不同的。經(jīng)過(guò)以上操作獲得系統(tǒng)日志文件，這個(gè)文件包含系統(tǒng)當(dāng)前運(yùn)行時(shí)被檢測(cè)類(lèi)的對(duì)象的所有創(chuàng)建和銷(xiāo)毀事件。對(duì)象請(qǐng)求的方法調(diào)用和返回事件也同時(shí)被記錄。依據(jù)執(zhí)行的父ID對(duì)日志進(jìn)行聚類(lèi)并記錄執(zhí)行次數(shù)，表l中數(shù)據(jù)字典對(duì)日志中的方法名及對(duì)象名進(jìn)行相應(yīng)替換，生成的最終增強(qiáng)日志如表2所示。

文章在此利用Java編程實(shí)現(xiàn)了算法，其算法復(fù)雜度為O（m*n），圖形化界面如圖3所示，功能包括txt、rtf格式日志導(dǎo)入及算法結(jié)果保存，CPN結(jié)果以節(jié)點(diǎn)形式輸出。

圖4形象的表達(dá)了算法的執(zhí)行步驟，且每條執(zhí)行序列均對(duì)應(yīng)不同場(chǎng)景進(jìn)行了遍歷迭代，故日志的每一條執(zhí)行序列與模型中的可達(dá)路徑都是一一對(duì)應(yīng)的。

通過(guò)定義4、5、6的描述可知L3、L8、L4，L1 0、L12、L14為選擇關(guān)系，L6、L7為并發(fā)關(guān)系。在PM-EL算法結(jié)果中這些結(jié)構(gòu)均被識(shí)別且通過(guò)顏色區(qū)別不同場(chǎng)景;

通過(guò)CPNto014.0.1對(duì)PM-EL所獲結(jié)構(gòu)模型進(jìn)行仿真實(shí)驗(yàn)（見(jiàn)圖5），此CPN模型為可運(yùn)行的。另外通過(guò)定義2及圖1、圖2表述的映射規(guī)則，可將此CPN模型轉(zhuǎn)化為UML模型，可更加直觀展示系統(tǒng)的運(yùn)行，并驗(yàn)證此方法結(jié)果的可擴(kuò)展性。

在此將日志導(dǎo)人Prom平臺(tái)中，并利用AlphaMiner及IDHM（ interactive Data - aware HeuristicMiner）進(jìn)行挖掘，以突出PM-EL算法在不完備日志基礎(chǔ)上對(duì)模型結(jié)構(gòu)的識(shí)別能力。

三個(gè)算法實(shí)驗(yàn)結(jié)果均有完整回路（即循環(huán)結(jié)構(gòu)），現(xiàn)就結(jié)果中選擇結(jié)構(gòu)和并發(fā)結(jié)構(gòu)數(shù)量進(jìn)行對(duì)比，如表3所示。

4 結(jié)論

文章通過(guò)分析數(shù)據(jù)挖掘與過(guò)程挖掘的異同，說(shuō)明日志的重要性，然后提出增強(qiáng)日志的概念。將系統(tǒng)日志中除事件執(zhí)行外的一些可利用信息加入事件日志，基于增強(qiáng)日志提出過(guò)程挖掘算法PM-EL，依賴(lài)事件執(zhí)行的附加屬性識(shí)別結(jié)構(gòu)關(guān)系。依據(jù)定義4、5、6，結(jié)果過(guò)程模型也是符合源增強(qiáng)日志的。通過(guò)UML序列圖的轉(zhuǎn)換說(shuō)明了算法結(jié)果的可擴(kuò)展性。即從增強(qiáng)日志中挖掘出附帶場(chǎng)景信息的過(guò)程模型。

通過(guò)PM-EL算法所提取的過(guò)程模型可以為后續(xù)的模型修復(fù)及優(yōu)化工作提供支持。在此文章的研究基礎(chǔ)之上，未來(lái)可以利用增強(qiáng)日志提升模型修復(fù)精度，將模型優(yōu)化細(xì)分為多場(chǎng)景有針對(duì)性的優(yōu)化。

參考文獻(xiàn)：

[1] F CORUNESCU. Data Mining： Concepts， Models andTechniques[M].Blue Publishing House， ClujNapoca，2011：30-35.

[2] W VAN DER AALST，T WEUTERS，L MARUSTER.Workflow mining： discovering process models from e.vent logs [J]. IEEE Trans. Knowl. Data Eng. 16（ 2004）：1 128-1 142，

[3] L WEN，J WANC，W VAN DER AALST，et al.A novel ap-proach for process mining based on event types[C]//J.Intellig. Inform. Syst.32 （2009）： 163-190.

[4] D WANG，J CE，H HU， et al.Discovering processmodels from event multiset[J]. Exp. Syst. Appl. 39 （2012）：11 970-11 978.

[5] J COOK，A L WOLF. Discovering models of softwareprocesses from event- based data[M].ACM Transac.Softw. Eng. Methodol. （TOSEM）7（1998） 215-249.

[6] K G COMAN，A M ODLYZKO. Intemet growth： isthere a Moore's law for data traffic？ [J]. Handbook ofMassive Data Sets， Kluwer， 2001：47-93.

[7] BROUCKE S K L M V，VANTHIENEN J.BAESENSB. Declarative process discovery with evolutionary com-puting[ C]// 2014 IEEE Congress on Evolutionary Computation （ CEC）. IEEE， 2014 ：2 412-2 419.

[8]MARUSTER L， WEIJTERS A， VAN DER AALST W M P， et al. A rule-based approach for process discovery[J]. Data Mining & Knowledge Discovery， 2015， 13（1） ： 67-87.

[9]LEEMANS S J J， FAHLAND D， VAN DER AALST W MP. Scalable process discovery and conformance chec-king [J]. Software & Systems Modeling， 2018， 17（2） ： 1-33.

[10] WEIJTERS A， VAN DER AALST W M P， DE ME-DEIROS A K A. Process mining with the heuristicsminer- algorithm [ J ] . Technische Universiteit Eind-hoven， Tech. Rep. WP， 2006， 166： 1-34.

[11] WEUTERS A T， RIBEIRO J J. Flexible heuristicsminer（ FHM） [ C ]//Proceedings of IEEE Conferenceon Computational Intelligence and Data Mining.Washington， D. C. ， USA： IEEE， 2011 ：310-317.

[12]LEEMANS S J J， FAHLAND D， VAN DER AALST WMP. Discovering block-structured process models frommcomplete event logs [ C ]//Proceedings of Intemation-al Conference on Applications and Theory of Petri Netsand Concurrency. Berlin， Germany： Springer-Verlag，2014 ：91-110.

[13] TAX N， SIDOROVA N， HAAKMA R， et al. Mininglocal process models[ J] . Joumal of Innovation in Dig-ital Ecosystems ， 2016 ，3 （ 2） ： 183 -196.

[14] 邵叱風(fēng)，基于流程挖掘的并行優(yōu)化算法 [ J] .赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版） ， 2019. 35（ 10） ： 66-70.

[15 ]方賢文. Petri網(wǎng)行為理論及其應(yīng)用 [ M ] .上海 ：上海交通大學(xué)出版社 ，2017 ：39-40.

[16]VAN DER AALST W MP. Process mining： discovery， conformance and enhancement of business processes [M ]. Springer Publishing Company， Incorporated，2011 ：56-89.

[17] ZHANG L， ZEICLER B P， LAILI Y. Introduction to Model Engineering for Simulation [ M ] . Model Engi-neering for Simulation， 2019 ： 43-56.

[18] CHUANYI LI， JIDONC GE， UGUO HUANC， et al.Process mining with token carried data[ J] . InformationSciences， 2016 ： 34-48.