基于流程挖掘的并行優(yōu)化算法

邵叱風

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

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

中圖分類號：TP391.9? 文獻標識碼：A? 文章編號：1673-260X（2019）10-0066-05

1 引言

1.1 研究背景

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

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

1.2 動機案例

通過政府在線采購系統(tǒng)進行采購是當今政府常見的采購方式，本文使用政府采購的在線采購流程作為研究案例來分析所提出的方法，圖1給出政府在線采購系統(tǒng)案例的給定模型M.

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

2 基本概念

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

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

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

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

3.1 政府采購流程日志挖掘（Alpha-algorithm、Heuristic miner）

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

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

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

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

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

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

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

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

5 實驗評估

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

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

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

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

顯然

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

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

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

顯然

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

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

5.1 實驗設(shè)置

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

5.2 實驗結(jié)果分析

5.2.1 仿真實驗

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

5.2.2 結(jié)果評估

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

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

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

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

6 結(jié)束語

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

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

參考文獻：

〔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〕宋健，方賢文，王麗麗.基于流程切的過程模型挖掘方法[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.