邵叱風(fēng)

摘 要：過(guò)程挖掘技術(shù)將觀察到的行為（即事件日志）與建模的行為（如bpmn模型或petri網(wǎng)）聯(lián)系起來(lái).可以通過(guò)對(duì)日志進(jìn)行挖掘，獲得實(shí)際業(yè)務(wù)流程模型，再對(duì)其中關(guān)聯(lián)嚴(yán)格結(jié)構(gòu)檢測(cè)，通過(guò)并行優(yōu)化的方法優(yōu)化實(shí)際業(yè)務(wù)流程模型.目前的業(yè)務(wù)流程優(yōu)化主要是針對(duì)管理者或開(kāi)發(fā)者給出的業(yè)務(wù)流程模型，其與實(shí)際運(yùn)行中的業(yè)務(wù)流程可能與之有些許偏差，從而影響了優(yōu)化結(jié)果.在此提出一種新方法對(duì)業(yè)務(wù)流程進(jìn)行優(yōu)化.首先使用Prom框架中的Alpha Miner及Heuristic miner獲得流程模型的Petri Net及C-net結(jié)構(gòu);然后使用最大分解的方法修復(fù)流程模型;針對(duì)修復(fù)后的模型提出其中高頻簡(jiǎn)單網(wǎng)部分，并發(fā)現(xiàn)關(guān)聯(lián)嚴(yán)格結(jié)構(gòu)，使用Colored Petri nets對(duì)關(guān)聯(lián)嚴(yán)格結(jié)構(gòu)重新構(gòu)造為關(guān)聯(lián)并行結(jié)構(gòu)，確定優(yōu)化結(jié)果.該方法通過(guò)實(shí)際業(yè)務(wù)流程的研究案例及比較實(shí)驗(yàn)進(jìn)行評(píng)估，其結(jié)果表明關(guān)聯(lián)并行優(yōu)化可明顯縮短實(shí)際業(yè)務(wù)流程耗時(shí).

關(guān)鍵詞：Colored Petri nets;C-net;最大分解;關(guān)聯(lián)嚴(yán)格;關(guān)聯(lián)并行

中圖分類(lèi)號(hào)：TP391.9? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2019）10-0066-05

1 引言

1.1 研究背景

隨著大數(shù)據(jù)時(shí)代的到來(lái)，業(yè)務(wù)流程的管理?yè)碛信e足輕重的地位.業(yè)務(wù)流程管理的核心內(nèi)容便是業(yè)務(wù)流程挖掘及優(yōu)化，由此對(duì)流程挖掘及優(yōu)化方面的深入研究日益重要.本文著重于修復(fù)和優(yōu)化的方面.修復(fù)流程的目標(biāo)是細(xì)化現(xiàn)有流程模型，使它們符合給定的事件日志.優(yōu)化流程的目標(biāo)是修改現(xiàn)有的流程模型，使其對(duì)應(yīng)的實(shí)際業(yè)務(wù)流程更加合理、便捷.本文所考慮的修復(fù)及優(yōu)化方法分別稱(chēng)為分解模型修復(fù)方法與并行優(yōu)化算法.假設(shè)事件日志描述了正確的和最新的業(yè)務(wù)流程行為，而流程模型可能是錯(cuò)誤的.模型修復(fù)后是最新的且正確的，可它表示的流程不一定是最合適的流程.在此，先以實(shí)際流程日志為基礎(chǔ)，通過(guò)執(zhí)行Prom平臺(tái)中的Alpha Miner獲得實(shí)際流程運(yùn)行初始Petri Net模型，并使用Heuristic miner獲得實(shí)際流程運(yùn)行C-net模型，通過(guò)分析繪制出最新流程模型，然后使用最大分解算法[1]對(duì)流程模型與初始日志進(jìn)行三步操作：（1）將流程模型和事件日志分解為模型片段和子日志，（2）選擇需要修復(fù)的片段，（3）使用流程發(fā)現(xiàn)算法修復(fù)選中的片段.獲得修復(fù)模型后，進(jìn)行三步操作：（1）將模型中高頻部分提出，（2）檢測(cè)提取模型中關(guān)聯(lián)嚴(yán)格結(jié)構(gòu)，（3）使用并行優(yōu)化算法優(yōu)化提取的模型.最后得到符合實(shí)際業(yè)務(wù)流程的模型優(yōu)化后的模型.

近年來(lái)，過(guò)程挖掘[2]是被廣泛研究與應(yīng)用的新興技術(shù)，主要分為以下三個(gè)階段：過(guò)程發(fā)現(xiàn)、服從性校驗(yàn)、模型完善[3].其中，流程發(fā)現(xiàn)是流程挖掘領(lǐng)域中最關(guān)鍵的問(wèn)題之一，其目的是從事件日志中發(fā)現(xiàn)流程模型來(lái)描述日志[4]中觀察到的行為.在文獻(xiàn)中提出了許多流程挖掘技術(shù)，例如，在基于Alpha算法的抽取技術(shù)[5]和它的變體[6，8，9]，啟發(fā)式挖掘算法[10]，基于狀態(tài)空間搜索的遺傳算法[11]，基于語(yǔ)言的區(qū)域算法[12]，基于狀態(tài)的區(qū)域算法[13]，復(fù)雜感知算法[14]，基于正確塊結(jié)構(gòu)的算法[15]，和無(wú)鎖保證算法[16].

1.2 動(dòng)機(jī)案例

通過(guò)政府在線采購(gòu)系統(tǒng)進(jìn)行采購(gòu)是當(dāng)今政府常見(jiàn)的采購(gòu)方式，本文使用政府采購(gòu)的在線采購(gòu)流程作為研究案例來(lái)分析所提出的方法，圖1給出政府在線采購(gòu)系統(tǒng)案例的給定模型M.

由于政府采購(gòu)系統(tǒng)是在不斷完善中，所以實(shí)際的流程模型是不斷變化的，給定的模型M很難保證其是最新的且正確的系統(tǒng)流程模型，如果在此模型上對(duì)系統(tǒng)流程模型進(jìn)行優(yōu)化，難以達(dá)到預(yù)期的采購(gòu)系統(tǒng)模型優(yōu)化效果.

2 基本概念

定義3 （關(guān)聯(lián)嚴(yán)格）Petri Net模型對(duì)應(yīng)實(shí)際業(yè)務(wù)流程，任意一個(gè)變遷均對(duì)應(yīng)有實(shí)際操作，如果操作B必須有操作A的結(jié)果才可進(jìn)行，則稱(chēng)操作A、B對(duì)應(yīng)變遷具有關(guān)聯(lián)嚴(yán)格，記CB（A，B）.

如圖2所示，其中A，B，C，D如圖所示為嚴(yán)格序關(guān)系，但在實(shí)際流程操作中，操作B的前提為A，操作C的前提為A，操作D的前提為B、C.分別記為CB（A，B），CB（A，C），CB（B，D），CB（C，D）.則可對(duì)流程模型進(jìn)行方案1優(yōu)化，并不會(huì)發(fā)生任何阻塞.情況2則可使用方案2進(jìn)行優(yōu)化.

3 流程挖掘及修復(fù)

本節(jié)基于表1政府采購(gòu)系統(tǒng)的事件日志可以對(duì)現(xiàn)有的政府采購(gòu)系統(tǒng)流程模型進(jìn)行挖掘及修復(fù).此處采用Prom平臺(tái)中的Alpha Miner及Mine for a Heuristics Net using Heuristics Miner兩個(gè)插件對(duì)日志進(jìn)行挖掘處理，并使用最大分解算法對(duì)模型進(jìn)行修復(fù).

3.1 政府采購(gòu)流程日志挖掘（Alpha-algorithm、Heuristic miner）

對(duì)表1中的日志進(jìn)行挖掘操作，此處（默認(rèn)插件設(shè)置）可獲得如圖3、4所示Petri net流程模型及C-net流程模型.

由圖4中C-net流程模型的Fitness=0.999可知，此刻的因果網(wǎng)能極大程度上表達(dá)日志1中的流程.結(jié)合圖3中Petri net流程模型，可得最新日志1中的政府采購(gòu)流程模型如圖5所示.此刻的初步流程模型相較于給定的模型M已經(jīng)多出了t6、t14、t20三個(gè)操作流程，可見(jiàn)保持最新且正確的流程模型是極其困難的.故在對(duì)系統(tǒng)流程進(jìn)行優(yōu)化時(shí)最好采用最新的日志進(jìn)行挖掘，以獲得相對(duì)更適應(yīng)當(dāng)前系統(tǒng)的流程模型.

3.2 政府采購(gòu)流程日志修復(fù)（最大分解法）

對(duì)圖5中的初步流程模型及表1中的日志使用最大分解法優(yōu)化，如圖6所示，此刻獲得的實(shí)時(shí)流程模型在初始狀態(tài)時(shí)，增加了2個(gè)Token，根據(jù)實(shí)際業(yè)務(wù)流程分析可知，t6，t14兩個(gè)操作與另外兩個(gè)系統(tǒng)有交互操作，相較于初步流程模型更加細(xì)化了.

4 業(yè)務(wù)流程中關(guān)聯(lián)嚴(yán)格并行優(yōu)化算法

過(guò)程模型的Petri網(wǎng)模型的性能分析通常從以下評(píng)估指標(biāo)中觀察，例如有效性，適應(yīng)性，過(guò)程周期時(shí)間，效率和過(guò)程成本.過(guò)程周期時(shí)間和效率是相關(guān)的，并且難以測(cè)量有效性和適應(yīng)性.故在此主要性能評(píng)價(jià)指標(biāo)選用流程周期長(zhǎng)度.在Petri網(wǎng)中主要依靠實(shí)體token的數(shù)據(jù)傳遞來(lái)實(shí)現(xiàn)時(shí)間參數(shù)的計(jì)算，其中業(yè)務(wù)流程平均周期時(shí)間計(jì)算公式為：

其中InToken.Time初始為0，在這里我們假設(shè)所有變遷在token輸入庫(kù)所后立刻發(fā)生，即Waiting.Time=0.n是流程個(gè)數(shù)，m是每個(gè)流程的變遷個(gè)數(shù).在模型優(yōu)化過(guò)程中，分析變遷之間的關(guān)聯(lián)嚴(yán)格關(guān)系，并設(shè)計(jì)如下所示的ProcessOptimization算法.

該算法包括流程模型中的變遷的重新組合，以及有色Petri網(wǎng)形式的輸出，其中不同的顏色對(duì)應(yīng)于不同的分支，通過(guò)并發(fā)的方式減少流程耗時(shí).還有對(duì)顏色petri網(wǎng)colorSet以及對(duì)應(yīng)顏色路徑耗時(shí)的輸出，最后使用冒泡排序?qū)臅r(shí)進(jìn)行排序輸出.鑒于重新構(gòu)造系統(tǒng)模型會(huì)改變?cè)攘鞒?，可能?huì)使某些系統(tǒng)的開(kāi)發(fā)維護(hù)產(chǎn)生大量工作，所以在保證優(yōu)化效率及資源合理利用前提下，建議對(duì)流程中部分高頻片段進(jìn)行優(yōu)化.

5 實(shí)驗(yàn)評(píng)估

并行優(yōu)化算法主要思想即結(jié)合關(guān)聯(lián)嚴(yán)格結(jié)構(gòu)，重新構(gòu)造為并發(fā)結(jié)構(gòu)，以減少流程耗時(shí).首先對(duì)任意模型（例如圖2模型），設(shè)InToken.Time=0及Waiting.Time=0，且任意Act.Timei>0，采用并行操作前的流程耗時(shí)為：

Total.Time=Act.TimeA+Act.TimeB+Act.TimeC+Act.TimeD

優(yōu)化方案1中流程耗時(shí)為：

Total.Time=Act.TimeA+max{Act.TimeB，Act.TimeC}Act.TimeD

顯然

max{Act.TimeB，Act.TimeC}<Act.TimeB+Act.TimeC

優(yōu)化方案2中流程耗時(shí)為：

Total.Time=Act.TimeA+max{（Act.TimeB+Act.TimeD），Act.TimeC}

顯然

max{（Act.TimeB+Act.TimeD），Act.TimeC}<Act.TimeB+Act.TimeC+Act.TimeD

無(wú)論任意并發(fā)執(zhí)行方案，均縮短了流程執(zhí)行耗時(shí).說(shuō)明了并行優(yōu)化的可行性.

5.1 實(shí)驗(yàn)設(shè)置

對(duì)于圖6使用最大分解獲得的實(shí)時(shí)流程模型，其中的高頻事件如圖7.不妨取出如圖8所示模型進(jìn)行優(yōu)化實(shí)驗(yàn).其關(guān)聯(lián)嚴(yán)格關(guān)系CB（t7，t8），CB（t7，t9），CB（t9，t10），CB（t8，t11），CB（t10，t11）.

5.2 實(shí)驗(yàn)結(jié)果分析

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

將高頻部分代入算法進(jìn)行優(yōu)化，對(duì)于模型重構(gòu)部分有如圖9所示過(guò)程.

5.2.2 結(jié)果評(píng)估

使用表2中周期參數(shù)，使用計(jì)算公式

計(jì)算，設(shè)InToken.Time=0及Waiting.Time=0，可得如圖11所示完成流程各階段耗時(shí).

選擇處理時(shí)間減少率作為評(píng)估處理效率的指標(biāo)，并且處理時(shí)間減少率用于反映處理優(yōu)化之后整個(gè)處理時(shí)間減少的影響.從上述模擬計(jì)算得出，優(yōu)化前后圖所示業(yè)務(wù)流程的平均周期分別為28.5天和19.5天，整體流程時(shí)間縮短率為31.6%.因此，所采取的優(yōu)化措施是正確的，有效地減少了圖3的業(yè)務(wù)流程周期，并提高了流程執(zhí)行的效率.因此，該過(guò)程的成本降低到一定程度，此優(yōu)化算法是實(shí)際可行的.

最終優(yōu)化模型如圖12所示，相較于給定的模型M增加了3個(gè)變遷及三個(gè)初始Token，反映了當(dāng)前系統(tǒng)與其他系統(tǒng)的交互，且在場(chǎng)地安排流程實(shí)行了優(yōu)化，大大縮短了流程耗時(shí).基于模型挖掘的并行優(yōu)化算法在實(shí)際流程優(yōu)化中是極符合優(yōu)化要求的.

6 結(jié)束語(yǔ)

本文在已有研究的基礎(chǔ)上，給出了基于過(guò)程挖掘的并行優(yōu)化方法.首先使用Prom框架中的Alpha Miner及Heuristic miner獲得流程模型的Petri Net及C-net結(jié)構(gòu);然后使用最大分解的方法修復(fù)流程模型;針對(duì)修復(fù)后的模型提出其中高頻部分（模型優(yōu)化可能會(huì)修改流程邏輯，針對(duì)高頻大量事件，減少系統(tǒng)二次開(kāi)發(fā)工作量，相對(duì)提高優(yōu)化的實(shí)際意義），并發(fā)現(xiàn)關(guān)聯(lián)嚴(yán)格結(jié)構(gòu)，使用Colored Petri nets對(duì)關(guān)聯(lián)嚴(yán)格結(jié)構(gòu)重新構(gòu)造為關(guān)聯(lián)并行結(jié)構(gòu)（通過(guò)不等式證明并發(fā)操作減少耗時(shí)的可行性），確定優(yōu)化后流程模型結(jié)構(gòu).

未來(lái)關(guān)于過(guò)程挖掘進(jìn)行優(yōu)化的研究還有很多工作去做.例如，在基于整數(shù)線性規(guī)劃的約束體下，從包含大量事件的日志中挖掘滿(mǎn)足需求的實(shí)時(shí)業(yè)務(wù)流程模型.

參考文獻(xiàn)：

〔1〕Mitsyuk， A.A.， Lomazova， I.A.， Shugurov， I.S.， and van der Aalst， W.M.P.， Process model repair by detecting unfitting fragments， Supplementary Proceedings of AIST 2017， CEUR-WS.org， 2017.

〔2〕宋健，方賢文，王麗麗.基于流程切的過(guò)程模型挖掘方法[J].計(jì)算機(jī)科學(xué)，2019，46（7）：1-7.

〔3〕VANDERASLST W， WEIJTERS T， MARUSTER L. Process Mining： Discovery， Conformance and Enhancement of Business Processes[M]. Springer-Verlag， Berlin， 2011.

〔4〕Wil van de. Aalst， Arya Adriansyah， Ana Karla Alves de Medeiros， Franco Arcieri， Thomas Baier， Tobias Blickle， Jagadeesh Chandra Bose， Peter van den Brand， Ronald Brandtjen， Joos Buijs， et al.， Process mining manifesto， in： Business Process Management Workshops， Springer， 2012， pp.169–194.

〔5〕Wil van der Aalst， Ton Weijters， Laura Maruster， Workflow mining：Discovering process models from event logs， IEEE Trans. Knowl. Data Eng.16 （9） （2004） 1128–1142.

〔6〕L. Wen， J. Wang， W.M. Aalst， et al.， A novel approach for process mining based on event types， J. Intell. Inf. Syst. 32 （2） （2009） 163–190.

〔7〕L. Wen， W.M. Aalst， J. Wang， et al.， Mining process models with non-free-choice constructs， Data Min. Knowl. Discov. 15 （2） （2007）145–180.

〔8〕L. Wen， J. Wang， J. Sun， Mining invisible tasks from event logs， in： Advances in Data and Web Management， Springer， 2007， pp. 358–365.

〔9〕L. Wen， J. Wang， W.M.P. van der Aalst， B. Huang， J. Sun， Mining process models with prime invisible tasks， Data Knowl. Eng. 69 （10） （2010） 999–1021.

〔10〕A.J.M.M. Weijters， Wil M.P. van der Aalst， A.K. Alves De Medeiros， Process mining with the heuristics miner algorithm， in： Tech. Rep， Vol. 166， Technische Universiteit Eindhoven， WP， 2006， pp. 1–34.

〔11〕A.K. Alves De Medeiros， A.J.M.M. Weijters， Wil M.P. van der Aalst， Genetic process mining： a basic approach and its challenges， in： Business Process Management Workshops， Springer， 2006， pp. 203–215.

〔12〕Robin Bergenthum， J？rg Desel， Robert Lorenz， Sebastian Mauser， Process mining based on regions of languages， in： Business Process Management， Springer， 2007， pp. 375–383.

〔13〕Josep Carmona， Jordi Cortadella， Michael Kishinevsky， A region-based algorithm for discovering petri nets from event logs， in： Business Process Management， Springer， 2008， pp. 358–373.

〔14〕Chathura C. Ekanayake， Marlon Dumas， Luciano Garc？a-Bauelos， Marcello La Rosa， Slice， mine and dice： Complexity-aware automated discovery of business process models， in： International Conference on Business Process Management， Springer， 2013.

〔15〕Sander J.J. Leemans， Dirk Fahland， Wil M.P. van der Aalst， Discovering block-structured process models from incomplete event logs， Lecture Notes in Comput. Sci. 8489 （2014） 311–329.

〔16〕Adriano Augusto， Raffaele Conforti， Marlon Dumas， Marcello La Rosa， Split miner： discovering accurate and simple business process models from event logs， in： IEEE International Conference on Data Mining， 2017.