齊陳榮

摘 要：為突破固定模式，實(shí)時(shí)預(yù)測，使流程管理更高效更準(zhǔn)確，本文提出一種基于序列模式的對齊預(yù)算方法。以業(yè)務(wù)流程模型和日志集作為輸入，通過分析模型中活動(dòng)的行為關(guān)系，將活動(dòng)劃分為不同的序列模式，利用條件概率對序列模式中活動(dòng)做預(yù)測。并且通過實(shí)例分析了該方法的有效性。

關(guān)鍵詞：Petri網(wǎng);對齊;預(yù)測;序列模式;條件概率

中圖分類號(hào)：TP391.9 ?文獻(xiàn)標(biāo)識(shí)碼：A ?文章編號(hào)：1673-260X（2021）07-0013-04

0 引言

隨著信息技術(shù)的快速發(fā)展，業(yè)務(wù)流程管理在企業(yè)或組織間扮演著越來越重要的角色。然而，真實(shí)的業(yè)務(wù)場景與流程模型間會(huì)存在行為不一致，我們經(jīng)常使用對齊來描述這種差異。目前，國內(nèi)外很多學(xué)者研究了對齊問題。例如，Bloemen V等[1]提出了不同于標(biāo)準(zhǔn)成本函數(shù)的新的成本函數(shù)，設(shè)計(jì)了優(yōu)先考慮最大化同步移動(dòng)對齊算法，該算法不同于A*算法和符號(hào)算法，最后通過實(shí)例說明了算法的實(shí)用性和有效性。Garcia-Banuelos L等[2]介紹了一種新的對齊方法，即通過兩個(gè)事件結(jié)構(gòu)做糾錯(cuò)同步積的對齊方法，并詳細(xì)闡述了日志與模型間的六種不匹配行為，通過一種自然語言來描述這個(gè)變化。劉靜[3]等人提取出事件日志有效的高頻形態(tài)學(xué)發(fā)生片段，在此基礎(chǔ)上發(fā)現(xiàn)最優(yōu)跡對齊。前人在對齊方面的研究，大多是通過暴力搜索來尋找差異且日志與模型都具有完整性。因此，突破固定模式，實(shí)時(shí)預(yù)測，使流程管理更高效更準(zhǔn)確顯得尤為重要。關(guān)于預(yù)測的研究有，Tax N等[4]提出了一種基于機(jī)器學(xué)習(xí)方法預(yù)測在給定的不完整序列之后可能出現(xiàn)的元素。Hamed R I[5]提出了一種基于模糊規(guī)則推理的模糊Petri網(wǎng)方法，通過實(shí)驗(yàn)表明所提出的模型可以達(dá)到與現(xiàn)有軟件相匹配的置信值。Ma Z等[6]利用極小值和可達(dá)圖解決了有標(biāo)識(shí)Petri網(wǎng)中的一個(gè)基本標(biāo)識(shí)估計(jì)問題，提出了基礎(chǔ)標(biāo)識(shí)的兩種概念，并證明對于一組警報(bào)是可預(yù)測的。

基于上述研究，本文提出了一種基于序列模式的業(yè)務(wù)流程模型的預(yù)測對齊方法。第1節(jié)通過動(dòng)機(jī)例子引出本文方法;第2節(jié)介紹相關(guān)定義;第3節(jié)首先將活動(dòng)劃分為三個(gè)序列模式，提高對齊效率。然后，利用條件概率預(yù)測下一節(jié)點(diǎn)的發(fā)生;第4節(jié)進(jìn)行實(shí)例分析;最后總結(jié)全文并展望未來。

1 動(dòng)機(jī)例子

本節(jié)將利用某貸款申請流程來說明本文的研究動(dòng)機(jī)，為了方便起見，將每個(gè)函數(shù)賦予新的標(biāo)簽如表1所示，圖2是用EPC（事件驅(qū)動(dòng)過程鏈）語言描述的貸款申請流程。流程從“銀行收到貸款申請”開始，兩個(gè)任務(wù)“檢查信用度”和“檢查收入來源”或“檢查信用度”和“檢查貸款記錄”并發(fā)，進(jìn)入“評估申請”環(huán)節(jié)，或者直接進(jìn)入“客戶準(zhǔn)備資料”環(huán)節(jié)，然后兩個(gè)分支選擇發(fā)生“提供貸款”或者“通知拒絕”，最后以“貸款結(jié)束”完成整個(gè)貸款流程。

考慮日志L={ACFI，AEFGI}，常見的兩種對齊方式有基于A*最短路徑算法的最優(yōu)對齊和最大化同步移動(dòng)對齊。我們認(rèn)為這兩種對齊方法并不總是合適的，（1）A*算法旨在以暴力搜索的方式尋找最短路徑以達(dá)到成本最低的對齊如γ1，可以看出通過跳過活動(dòng)C以達(dá)到成本最低，但在真實(shí)業(yè)務(wù)場景中，無法判定活動(dòng)C是否應(yīng)該發(fā)生，若活動(dòng)C發(fā)生如γ2。（2）最大化同步移動(dòng)對齊旨在盡量使日志與模型對齊以減少跳過移動(dòng)，進(jìn)而達(dá)到成本最低如γ3，在模型中活動(dòng)G是進(jìn)入循環(huán)的標(biāo)志性活動(dòng)，若進(jìn)入循環(huán)體如γ4。針對這兩種問題，本文提出一種基于序列模式的預(yù)測對齊方法，這種方法不僅能預(yù)測下一個(gè)發(fā)生的節(jié)點(diǎn)，還能更高效更準(zhǔn)確地進(jìn)行預(yù)測。

2 基本概念

定義1[7，8]（業(yè)務(wù)流程Petri網(wǎng)） 一個(gè)網(wǎng)PN=（P，T;F）是業(yè)務(wù)流程Petri網(wǎng)，當(dāng)其滿足以下條件：

（1）P為庫所集，有P≠？覫。

（2）T為變遷集，有T≠？覫。

（3）F=（P×T）∪（T×P）為流關(guān)系集。

在流程模型P的變遷之間存在一種弱序關(guān)系，即一對變遷（x，y）∈T×T是弱序關(guān)系，當(dāng)且僅當(dāng)存在一個(gè)發(fā)生序列？滓=t1t2…tn有（P，M0）[？滓〉，并且有i，j∈N，1≤i≤j≤n使得tj=x，ti=y，記作x？酆y。根據(jù)弱序關(guān)系定義模型和日志的行為輪廓關(guān)系[9]。

定義2[10]（模型的行為輪廓） 設(shè)P是一個(gè)流程模型，對？坌（x，y）∈P，則x，y的行為關(guān)系如下：

（1）嚴(yán)格序關(guān)系→P，若x？酆Py∧y≯Px，記作x→Py。

（2）交叉序關(guān)系||P，若x？酆Py∧y？酆Px，記作x||Py。

（3）排他序關(guān)系+P，若x≯Py∧y≯Px，記作+Py。

則稱集合BP{→P，||P，+P}是模型P的行為輪廓。

定義3[11]（序列模式） 流程模型P中的所有活動(dòng)集A，序列？籽=∈A*是由活動(dòng)組成的非空序列集，其中ak∈A。

定義4（依賴關(guān)系） 序列模式？祝=<<？琢1，？琢2，…，？琢k>，<？茁1，？茁2，…，？茁k>，<？酌1，？酌2，…，？酌k>>=<？琢i，？茁i，？酌i>，其中i=1，…，k。

？坌？琢k∈A，？堝？琢k∈？茁i，？酌i，st.？琢k？埸L，其中？琢i為長期依賴關(guān)系集，？茁i為長期沖突關(guān)系集，？酌i為長期選擇關(guān)系集，L為日志。

如圖2所示，活動(dòng)a和活動(dòng)g處于干路，即此活動(dòng)必須出現(xiàn)在任意一條發(fā)生序列上，我們將其稱為長期依賴關(guān)系。然而，活動(dòng)e和活動(dòng)f只能有一個(gè)出現(xiàn)在發(fā)生序列中，即存在長期選擇關(guān)系，而活動(dòng)h和活動(dòng)i則不能同時(shí)出現(xiàn)在一條發(fā)生序列中，所以，兩者呈長期沖突關(guān)系。理解活動(dòng)集合的劃分不僅是預(yù)測的基礎(chǔ)，還能通過劃分模型提高對齊效率。

3 序列模式的預(yù)測對齊

序列模式旨在分解流程，將流程模型中的活動(dòng)按行為關(guān)系劃分為三個(gè)集合，即？祝=<？琢i，？茁i，？酌i>。在三個(gè)關(guān)系集合中，首先對齊？琢i中的集合，即長期依賴關(guān)系優(yōu)先對齊;然后，在已對齊的活動(dòng)中利用條件概率預(yù)測在集合？茁i中需要對齊的活動(dòng);最后，在沖突集合？酌i中找出與已對齊活動(dòng)呈沖突關(guān)系的其他活動(dòng)將其跳過。

算法1 （序列模式的劃分）

輸入：輸入流程模型P、日志的發(fā)生序列L=[li]。

輸出：基于序列模式的對齊li？蓯。

（1）輸入流程模型P，將流程模型中的活動(dòng)劃分為三個(gè)活動(dòng)集合？琢i、？茁i、？酌i，執(zhí)行步驟（2）。

（2）從日志中選擇一條發(fā)生序列l(wèi)i，首先對齊在？琢i集合中的活動(dòng)得到序列l(wèi)i′;然后以已對齊的活動(dòng)為條件利用條件概率在？茁i集合中預(yù)測需要對齊的活動(dòng)得到序列l(wèi)i″;最后在集合？酌i中找出與已對齊活動(dòng)呈沖突關(guān)系活動(dòng)，執(zhí)行步驟（3）。

（3）將沖突的活動(dòng)直接跳過，輸出一條基于序列模式的預(yù)測對齊序列l(wèi)i？蓯，算法結(jié)束。

由于算法2是在條件概率的基礎(chǔ)上進(jìn)行的，因此，我們先引入條件概率定義。

定義5 （條件概率） 設(shè)A，B是兩個(gè)事件，且P（B）>0，P（A/B）為事件B發(fā)生的條件下事件A發(fā)生的條件概率。當(dāng)B={B1，B2，…，Bn}，Bn≠？覫時(shí)，條件概率公式為P（A）=∑，有，P（A）=1-P（A）。

算法2 （基于條件概率的預(yù)測）

輸入：流程模型P、序列l(wèi)i′和集合？茁i。

輸出：集合？茁i中需要對齊的活動(dòng)。

（1）輸入流程模型P和發(fā)生序列l(wèi)i′，執(zhí)行步驟（2）。

（2）利用定義5的條件概率來判定集合？茁i中需要對齊的活動(dòng)，執(zhí)行步驟（3）。

（3）將序列l(wèi)i′中已對齊的活動(dòng)作為條件，如果在此條件下該活動(dòng)的發(fā)生概率大于1/2，則對齊該活動(dòng);如果在此條件下該活動(dòng)不發(fā)生的概率大于1/2，則對齊與該活動(dòng)成選擇關(guān)系的活動(dòng)，算法結(jié)束。

4 案例分析

算法1和算法2詳細(xì)闡述了如何利用條件概率預(yù)測下一節(jié)點(diǎn)的發(fā)生，通過劃分序列模式，提高了對齊效率。本節(jié)將通過一個(gè)實(shí)例具體分析算法中所提到的方法，由于本文以EPC語義為背景，首先利用方賢文[12]提出的EPC誘導(dǎo)方法將其轉(zhuǎn)化為Petri網(wǎng)，如圖3。

考慮日志l1=ABCEFI，首先利用算法1將流程模型劃分為三個(gè)集合，？琢i=，？茁i=<？子2，CD？子1E;？子2，BD？子1E>，？酌i=對齊長期依賴關(guān)系得到li′;然后利用算法2判定A和F之間需要對齊的活動(dòng)，從圖3中可看出，如果活動(dòng)E發(fā)生，活動(dòng)D和沉默活動(dòng)？子1必須發(fā)生，因此在活動(dòng)A和活動(dòng)F已發(fā)生的條件下來判定活動(dòng)E發(fā)生的概率。如圖3所示，當(dāng)活動(dòng)F發(fā)生時(shí)，庫所e5中必須存在一個(gè)由于觸發(fā)活動(dòng)E或者？子2而產(chǎn)生的標(biāo)識(shí)，即P（E/F）=1/2。在活動(dòng)A被觸發(fā)后若要觸發(fā)活動(dòng)E，沉默變遷？子1必須發(fā)生，即庫所e′和庫所e″中都有標(biāo)識(shí)。觸發(fā)的A使庫所e2和e3都存在一個(gè)標(biāo)識(shí)，活動(dòng)D被觸發(fā)的概率為1/2，所以e′中存在標(biāo)識(shí)的概率為1/2，而e″中存在標(biāo)識(shí)的概率為1，所以P（E/A）=;最后，跳過所有在集合？酌i中未對齊的活動(dòng)，得到l1″，如表3。

5 結(jié)束語

本文提出了一種基于序列模式的業(yè)務(wù)流程模型的預(yù)測對齊方法，它以流程模型和日志發(fā)生序列作為輸入，通過劃分序列模式將活動(dòng)分成三個(gè)關(guān)系集。隨后利用條件概率在已對齊活動(dòng)的情況下預(yù)測下一節(jié)點(diǎn)發(fā)生的概率。該方法打破了以成本和路徑為基礎(chǔ)的常規(guī)對齊方法，并提高了對齊效率，已進(jìn)行的實(shí)例評估驗(yàn)證了該方法在實(shí)踐中的適用性和可擴(kuò)展性。

然而，我們的方法也有一定的局限性，它主要限制于有界的流程模型和完整的日志序列，對于無界的流程和序列，我們無法判斷。在未來工作中，需要對預(yù)測做進(jìn)一步研究，并將其應(yīng)用于Prom框架中。

參考文獻(xiàn)：

〔1〕Bloemen V， Zelst S J V， Aalst W M P V D， et al. Maximizing Synchronization for Aligning Observed and Modelled Behaviour： 16th International Conference， BPM 2018， Sydney， NSW， Australia， September 9-14， 2018， Proceedings[M]// Business Process Management. 2018.

〔2〕Garcia-Banuelos L， Van Beest N， Dumas M， et al. Complete and Interpretable Conformance Checking of Business Processes[J]. IEEE Transactions on Software Engineering， 2015：1-1.

〔2〕Luciano Garcia-Banuelos，Nick R T P van Beest，Marlon Dumas，et al. Complete and interpretable conformance checking of business processes[J]. IEEE Transactions on Software Engineering， 2018， 44（03）：262.

〔3〕劉靜，方賢文.基于成本對齊的業(yè)務(wù)流程變化挖掘方法[J].計(jì)算機(jī)科學(xué)，2020，47（07）：78-83.

〔4〕Tax N， Teinemaa I， Zelst S. An interdisciplinary comparison of sequence modeling methods for next-element prediction[J]. Software and Systems Modeling， 2020， 19（02）.

〔4〕Tax N， Teinemaa I， Zelst S. An interdisciplinary comparison of sequence modeling methods for next-element prediction[J]. Software and Systems Modeling， 2020， 19（02）.

〔5〕Hamed R I. Confidence value prediction of DNA sequencing with Petri net model[J]. Journal of King Saud University ¨c Computer & Information Sciences， 2011， 23（02）：79-89.

〔6〕Ma Z， Yin X， Li Z. Marking Predictability and Prediction in Labeled Petri Nets[J]. IEEE Transactions on Automatic Control， 2020， PP（99）：1-1.

〔7〕應(yīng)麗，方賢文，王麗麗，劉祥偉.基于業(yè)務(wù)能力的可配置業(yè)務(wù)流程模型變化域分析[J].計(jì)算機(jī)科學(xué)，2019，46（10）：322-328.

〔8〕吳哲輝.Petri網(wǎng)理論[M].北京：機(jī)械工業(yè)出版社，2006.6-42.

〔9〕郝晉淵，孫丹丹，郝真鳴，陳凡，冉寧.基于標(biāo)簽Petri網(wǎng)的自動(dòng)制造系統(tǒng)初始資源配置優(yōu)化[J].電子測量與儀器學(xué)報(bào)，2020，34（08）：30-36.

〔10〕郝惠晶，方賢文，王麗麗，劉祥偉.基于Petri網(wǎng)行為緊密度的有效低頻行為模式分析[J].計(jì)算機(jī)科學(xué)，2019，46（02）：321-326.

〔11〕M. Fani Sani， S.J. van Zelst， and W.M.P. van der Aalst. Applying Sequence Mining for Outlier Detection in Process Mining[J]. 2018.

〔12〕方賢文，彭珂，王麗麗，等.基于配置和撤銷狀態(tài)的業(yè)務(wù)流程變化傳播分析[J].計(jì)算機(jī)集成制造系統(tǒng)，2018，24（07）：1621-1630.