基于Petri網行為輪廓的業務流程模型審查

李多芹，方賢文，李 莉，邵叱風

(安徽理工大學 數學與大數據學院，安徽 淮南 232001)

0 引 言

在現實生活中，為了高效協調公司內部各部門的運轉，許多公司會成立專門的團隊針對不斷變化的市場需求創建新的業務流程模型以保障公司業務的正常運營。然而，隨著建模思想在各企業中的不斷深入，業務流程建模工作已經達到了相當復雜的水平，根據業務需求建立高質量的流程模型已然成為了建模團隊的主要挑戰之一。

目前，關于如何創建一個高質量的業務流程模型，已經有許多學者做了相關的研究。其中Fellmann M等開發了專門的過程建模推薦系統，該系統主要通過對各個過程的分析進而輔助流程建模[1]；Matsuda T等基于點過程模型框架，利用實驗數據來實現流程的建模工作[2]；歸思超等所提的方法基于流程的行為，可以在建模過程中為下一步節點的建立給出推薦的節點集[3]；鄭光鍵提出的流程推薦方法基于流程挖掘技術，并通過實驗證明所提方法更加符合語義性需求[4]；胡華等基于業務流程中活動發生的概率和時間，提出了一種可以向用戶推薦結構相似且時間效率較高的流程推薦方法[5]。

值得注意的是，上述方法旨在在建模過程中提升模型的質量，是一個著眼于當下的機制，即其關注的只是“下一步的可能節點”，故此類方法對模型質量的提升來說是局部的，很難全局把控。于是本文基于Petri網行為輪廓，在新建的業務流程模型投入使用之前，根據從流程庫中提取的相關信息對新建模型中事件間的行為關系進行全局的審查，以此來獲取更高質量的業務流程模型。

1 預備知識

定義1[6]標簽Petri網

定義2[7]弱序關系

令(N,M0)是一個變遷集T上的網系統，其中N=(S,T;F)， 弱序關系ψ?T×T包含所有變遷對(x,y)，存在一個發射序列σ=t1,t2,…,tn， 當 (N,[i])[σ>，j∈{1,2,…,n-1},j

定義3[7]行為輪廓

令標簽Petri網P=(N,L,fL)， 其中N=(S,T;F) 且T’是一個變遷集，一對變遷 (x,y)∈T’×T’若滿足下面之一條件：

(1)嚴格序關系x→y，當且僅當x>y,y≯x；

(2)嚴格逆序關系x→-1y，當且僅當y>x,x≯y；

(3)排他序關系x+y，當且僅當x≯y,y≯x；

(4)交叉序關系x‖y，當且僅當x>y,y>x。

以上關系構成了網N的行為輪廓，記作BP={→,→-1,+,‖}。

將一個標簽Petri網的上述行為關系用矩陣形式表達，就可以得到行為輪廓矩陣。

定義4[8]關聯規則

關聯規則是形如X→Y的蘊涵表達式，其中X和Y是不相交的項集，即X∩Y=0。關聯規則的強度可以用它的支持度和置信度度量。支持度確定規則可以用于給定數據集的頻繁程度，而置信度確定Y在包含X的事務中出現的頻繁程度。支持度(s)和置信度(c)這兩種度量的形式定義如下

(1)

(2)

基于上述關聯規則的定義本文提出了行為輪廓置信度的概念，用于計算行為對到行為輪廓的置信度。

定義5 行為輪廓置信度

在蘊含表達式X→Y中，X代表流程模型中的行為對，Y代表行為輪廓，于是得到行為對到行為輪廓的置信度計算方法如下：

(1)行為對呈嚴格序關系的置信度

(3)

(2)行為對呈排他序關系的置信度

(4)

(3)行為對呈交叉序關系的置信度

(5)

2 基于行為輪廓的模型審查與優化方法

所提方法的整體框架如圖1所示，主要可分為預處理、構建候選輪廓矩陣及生成輪廓差異矩陣3個部分。

圖1 所提方法的整體框架

2.1 預處理部分

首先，將業務流程模型庫中的所有流程用標簽Petri網表示；然后，提取每一個流程的行為輪廓矩陣Ai；最終獲得流程庫的行為輪廓矩陣集Λ={A1,A2,…,An}， 其中n為流程庫中業務流程的個數；最后，提取新建業務流程模型的行為輪廓矩陣A0。由于流程模型的行為輪廓可以以矩陣的形式存儲在后端，于是每個流程只需要提取一次行為輪廓即可。例如，圖2為標簽Petri網表示的真實業務流程圖。該流程源自于中國浙江省杭州市某區政府的業務流程庫，刻畫了該區新建計量標準器具的申請流程。

圖2 用標簽Petri網表示的真實業務流程

圖2中各標識符所指代的具體事件見表1，首先申請人提交書面申請(A2發生)，然后計量科工作人員對申請材料進行受理(A3發生)。當材料齊全時觸發A4，即指定考核單位組織考評員進行考核；若材料不齊全則通過隱變遷重新觸發申請活動?？己说慕Y果分3種情況：限期整改(A8發生)后重新考核；不符合核準條件的駁回申請(A10發生)；完全符合核準條件的頒發《計量標準考核證書》(A17發生)并歸檔(A46發生)。

表1 圖2中各標識符與具體事件的對應

該流程模型的行為輪廓矩陣見表2，其中1：嚴格序→；2：排他序+；3：交叉序‖。注意，由于行為輪廓矩陣的對稱性，我們只考慮矩陣的上三角區域。

表2 圖2中標簽Petri網的行為輪廓矩陣

2.2 候選輪廓矩陣的構建

經過預處理之后，可以得到新建業務流程模型的行為輪廓矩陣A0以及流程庫中流程模型的行為輪廓矩陣集Λ={A1,A2,…,An}， 其中n為流程庫中業務流程的個數。算法1給出了以A0和Λ為輸入構建候選輪廓矩陣Ac的具體步驟。

Algorithm 1：Construct the candidate profile matrix

Input：A0；Λ={A1,A2,…,An}

Output：Ac

(1) InitializeAc；C；C→；C+；C‖

(2) ForaijinA0//對A0中的每一個元素

(3) (U,V)=GetEventPairs(aij)//獲取aij對應的事件對

(4) ForAiinΛ//對Λ中的每一個矩陣元素Ai

(5) If there isbijinAis.t. GetEventPairs(aij)=(U,V)=GetEventPairs(bij)

(6)C←C∪Ai

(7) Ifbij=1//Ai中事件對(U,V)是嚴格序關系

(8)C→←C→∪Ai

(9) else Ifbij=2//Ai中(U,V)是排他序關系

(10)C+←C+∪Ai

(11) else//Ai中(U,V)是交叉序關系

(12)C‖←C‖∪Ai

(13) cS=|C→|/|C| ;cE=|C+|/|C|； cI=|C‖|/|C|

(14) If max(cS,cE,cI)=cS

(15) mark(Ac(cij))=1//將Ac第i行第j列元素記為1

(16) else If max(cS,cE,cI))=cE

(17) mark(Ac(cij))=2//將Ac第i行第j列元素記為2

(18) else

(19) mark(Ac(cij))=3//將Ac第i行第j列元素記為3

(20) returnAc

構建候選輪廓矩陣的算法主要分為4步：

(1)首先初始化一個與A0同階的矩陣Ac及用于存放滿足不同條件業務流程模型的空集合C，C→，C+和C‖(算法1中：(1))。

(2)對矩陣A0中的任意一個元素aij，其對應新建業務流程模型中的一個事件對，記作(U,V)，將行為輪廓矩陣集Λ={A1,A2,…,An} 中搜索同時包含事件U和事件V的行為輪廓矩陣放入新的集合C中(算法1中：(2)～(6))。注意，不同的事件對(U,V)對應著不同的集合C。

(3)在搜索獲取集合C的同時，分別記錄事件對(U,V) 在C中每一個矩陣上所處的行為關系。若事件U和事件V呈嚴格序關系，則將對應的行為輪廓矩陣Ai放入新的集合C→中(算法1中：(7)～(8))；當事件U和事件V呈排他序或交叉序關系時，采用類似的處理方式(算法1中：(9)～(12))。在搜索完行為輪廓矩陣集Λ之后，就能得到完整的集合C、集合C→、集合C+和集合C‖。最后，根據定義5計算事件對(U,V)的3個行為輪廓置信度(算法1中：(13))。

(4)對于算法1中(13)行計算出來的3個行為輪廓置信度：若最大值為cS(算法1中(14))，則表明，事件對(U,V)在流程庫中呈嚴格序的置信度最高。于是，候選矩陣Ac中第i行第j列元素，即cij，記為1(算法1中：(15))；若最大值為cE或cI，則做類似處理(算法1中：(16)～(19))其中，i和j的值通過算法1中第1行的aij確定。

對矩陣A0中的每一個元素aij，經過步驟(2)～步驟(4)之后能夠得到與之對應的Ac中的元素cij，最終返回候選輪廓矩陣Ac(算法1中：(20))。

下面將通過一個簡單的例子說明算法1的實現。例如，假設圖2是建模者新建的業務流程模型，表2展示的是該模型的行為輪廓矩陣。對事件對(A3,A4)，即受理活動和考核活動來說，若遍歷流程庫后發現庫中有51個流程模型同時包受理活動和考核活動，且在其中的9個模型中兩活動處于嚴格序關系；在其中的36個模型中兩活動處于交叉序關系；在其中的6個模型中兩行為處于排他序關系。那么受理活動和考核活動成嚴格序關系的置信度cS=9/51≈0.18；成交叉序關系的置信度cE=36/51≈0.71；成排他序關系的置信度cI=6/56=0.11。于是兩活動在流程庫中成交叉序關系的置信度最高，故在候選輪廓矩陣Ac中事件對(A3,A4)的行為輪廓被記為“3”。類似的，逐個遍歷A0中的元素便可得到與A0同階的矩陣Ac，Ac作為候選輪廓矩陣反映的是流程庫中批量流程模型的行為輪廓統計信息。

2.3 輪廓差異矩陣的生成

算法1給出了候選輪廓矩陣Ac的構造方法，下面的算法2則闡述了如何利用新建業務流程模型行為輪廓矩陣A0和候選輪廓矩陣Ac來產出輪廓差異矩陣Ad。

Algorithm 2：Generate the profile difference matrix

Input：A0；Ac

Output：Ad

(1) InnitializeAd初始化一個與A0同階的矩陣Ad

(2) ForaijinA0andcijinAc//對A0和Ac每一對對應位置元素

(3) Ifaij=cij

(4) mark(Ad(dij))=-

(5) else

(6) mark(Ad(dij))=aij-cij

(7) returnAd

算法首先初始化一個與A0和Ac同階的矩陣Ad(算法2中：(1))。接著，對任意的aij屬于A0以及cij屬于Ac(算法2中：(2))，如果aij等于cij，則dij屬于Ad記為“-”(算法2中：(3)～(4))；否則，dij屬于Ad記為“aij-cij”(算法2中：(5)～(6))。遍歷A0和Ac中的每一對對應元素，即可得到矩陣Ad(算法2中：(7))。注意，矩陣Ad中只有兩種元素，即“-”或“aij-cij”。

3 實例分析

3.1 數據簡介

為了驗證所提方法的可行性，下面將在真實數據集上進行分析，該數據集是從中國浙江省杭州市某區政府收集的各種業務流程模型[9]，表3中給出了該數據集的統計信息。鄧水光等在該數據集上進行了業務流程建模推薦系統的實驗，并在實驗的預處理環節將庫中模型的所有事件用數字1～52簡化表示，用矩陣簡易的表示每個業務流程模型，同時為每一個流程編號。原始數據集和預處理后的數據集均可在線獲取https://github.com/duoqinLi/real-business-process-data。

表3 數據集的統計信息

本文將從上述預處理后的數據集中隨機抽取2組，每組20個流程作為實驗流程庫進行實例分析，下面的表4分別列出了2組實驗流程庫中各流程的編號。于是每組的行為輪廓矩陣集可分別表示為Λi={A1,A2,…,A20}，i=1,2。

表4 兩組實驗流程庫中各流程的編號

關于新建業務流程的構造，為了模擬更加真實的新建模型，實驗部分不考慮重新構造新的業務流程，而是適當調整圖2中流程某些事件間的行為關系，使得調整后流程的行為輪廓矩陣與表2中所示的行為輪廓矩陣相比略有差異，從而達到模擬新建模型的效果。表5給出了調整圖2后所得新建業務流程模型的行為輪廓矩陣。

表5 新建業務流程模型的行為輪廓矩陣A0

3.2 工具支持與實驗設計

為了提升本文所提方法的實用性，編寫了能夠自動化實現算法1和算法2的Python程序BPBR(behavior profile based review)?；诖?，本文的實例分析將按如下設計進行：

首先，將第1組實驗流程庫作為對照組，基于該實驗流程庫手動計算出候選輪廓矩陣Ac及輪廓差異矩陣Ad，并與BPBR程序運行出的矩陣進行對比以驗證代碼實現的準確性。其次，將第2組實驗流程庫作為實驗組，利用BPBR程序自動化運行實驗組的實驗流程庫。最后，利用圖表展示實驗結果。

3.3 結果展示

3.3.1 對照組結果展示

第1組實驗流程庫作為對照組，手動計算候選輪廓矩陣Ac及輪廓差異矩陣Ad的步驟如下：

首先，計算出A0中各個事件對在流程庫中出現的頻數：對A0中的第一個元素，即第1行第1列元素 a1,1=3， 其對應的事件對為(A2,A2)，為表示方便，將其簡記為(2,2)。遍歷Λ1={A1,A2,…,A20}， 搜索出同樣包含事件對(2,2)的矩陣，遍歷后便可獲取該事件對在第1組實驗流程庫中出現的頻數，即算法1中集合C所含元素的個數。對A0中的每一個元素實施上述的操作，便可得到如圖3所示的結果。

圖3 A0中各個事件對在流程庫中出現的頻數

由圖3可知，A0中共有28個事件對，分別對應著圖中的28條數據，每條數據縱坐標上的數字代表每個事件對在實驗流程庫中出現的頻數。容易看出，65%的事件對在實驗流程庫中出現的頻數超過15，這一結果表明該組實驗流程庫適合被用作對本文所提方法的實例分析。

其次，在圖3的基礎上進一步計算出A0中各事件對在第1組實驗流程庫中的行為輪廓置信度。圖4展示了每個事件對在實驗流程庫中分別呈嚴格序、排他序及交叉序關系的置信度。

圖4 A0中各事件對在實驗流程庫中的行為輪廓置信度

接著，通過圖4獲取A0中每個事件對在實驗流程庫中置信度最高的行為關系，從而構建候選輪廓矩陣Ac如表6所示。

表6 候選輪廓矩陣Ac

最后，將得到候選輪廓矩陣Ac與表5中的矩陣A0進行比對就可以得到表7所示的輪廓差異矩陣。

表7 輪廓差異矩陣Ad

為了驗證代碼實現的準確性，在第1組實驗流程庫上運行BPBR程序，并將運行出的矩陣與表6和表7中的矩陣進行對比，對比結果顯示，運行BPBR程序得到的矩陣與表6和表7中的矩陣一致。驗證了代碼實現的可靠性后，下面將擺脫手動計算，利用BPBR程序運行實驗組實驗流程庫。

3.3.2 實驗組結果展示

第2組實驗流程庫作為實驗組，在該組數據上運行BPBR程序，可以得到如圖5所示的運行結果，其中Ac中下三角的元素已用0補充。容易看出圖5中的與表6、表7一致，即，當給定新建業務流程矩陣A0時，隨機抽取的兩組實驗流程庫能夠得到完全相同的結果，這表明，通過本文所提方法生成輪廓差異矩陣的具有一定的穩定性。

圖5 實驗組實驗流程庫運行結果

3.4 結果分析

上述實驗一方面驗證了所提方法的有效性，另一方面也表明所生成的輪廓差異矩陣具有穩定性。該矩陣本質上是以流程庫為依托，基于行為輪廓對新建業務流程模型的審查結果，矩陣中的“x-y”類型元素反映了新建模型與流程庫所有模型在行為輪廓上的差異。這些差異可能暗含著新建業務流程模型中事件對間行為關系的偏差。建模者可以基于該類型的元素結合實際需求對新建模型中某些事件間的行為關系進行再次確認，從而進一步對新建業務流程進行優化，得到更高質量的流程模型。

例如，對于新建業務流程中的事件對(3,8)，表5中第2行第4列元素為“1”，即受理活動和限期整改活動在新建的流程中處于嚴格序關系(對圖2中流程進行調整所產生的結果)。然而，通過圖4(a)我們可以發現該事件對在實驗流程庫中處于嚴格序關系的置信度僅為13%。另外，圖4(b)中顯示該事件對處于排他序關系的置信度為0，圖4(c)中顯示該事件對處于交叉序關系的置信度最高，為88%。這說明，在實驗流程流程庫中，若某個流程中同時包含受理活動和限期整改活動，那么這兩個活動以88%的概率呈交叉序關系，即事件限期整改既可發生在受理后，也可能發生在受理前(當限期整改后發現申請材料不全時)。此時，建模者可以結合實際需求再次確認新建模型中受理活動和限期整改活動的行為關系，若在某些業務情景中受理活動確實能夠在限期整改發生后再次發生，則建模者需要對新進模型進行調整優化，以得到更符合實際需求的業務流程模型。

4 結束語

隨著企業內部業務的不斷完善，業務流程模型的質量也有了更高的要求。為了輔助建模者提升新建模型的質量，本文基于行為輪廓，從流程模型行為關系的角度提出了一種模型審查方法。對應的兩個算法詳細闡述了所提方法的具體步驟，其中算法1以新建模型的行為輪廓矩陣和流程庫中流程模型的行為輪廓矩陣集為輸入，根據從流程庫中基于行為輪廓提取的流程知識，輸出候選輪廓矩陣；算法2則以新建模型的行為輪廓矩陣和算法1輸出的候選輪廓矩陣為輸入，輸出所需的輪廓差異矩陣。輸出的矩陣顯示了新建模型與流程庫所有模型在行為輪廓上的差異，用以輔助建模者審查新建模型的行為關系，從而提升模型質量。在未來的工作中，將考慮把行為關系延伸到因果關系、共現關系等以捕獲流程模型更加全面的行為特征，從而得到更加完善的模型審查方法。