基于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，即指定考核单位组织考评员进行考核；若材料不齐全则通过隐变迁重新触发申请活动。考核的结果分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输出的候选轮廓矩阵为输入，输出所需的轮廓差异矩阵。输出的矩阵显示了新建模型与流程库所有模型在行为轮廓上的差异，用以辅助建模者审查新建模型的行为关系，从而提升模型质量。在未来的工作中，将考虑把行为关系延伸到因果关系、共现关系等以捕获流程模型更加全面的行为特征，从而得到更加完善的模型审查方法。