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

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

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

中圖分類號：TP391.9

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

文章編號：1672-1098（ 2020）04-0025-08

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

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

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

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

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

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

1 準(zhǔn)備知識

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

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

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

2 基于增強日志的過程挖掘方法

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

2.1 增強日志

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 仿真實驗

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

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

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

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

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

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

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

4 結(jié)論

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

通過PM-EL算法所提取的過程模型可以為后續(xù)的模型修復(fù)及優(yōu)化工作提供支持。在此文章的研究基礎(chǔ)之上，未來可以利用增強日志提升模型修復(fù)精度，將模型優(yōu)化細(xì)分為多場景有針對性的優(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é)報（自然科學(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.