基于依赖关系的数据流Petri网一致性分析

钱 陈 婧

(1.安徽理工大学 数学与大数据学院,安徽 淮南 232001;2.安徽省煤矿安全大数据分析与预警技术工程实验室,安徽 淮南232001)

在业务流程管理中,对业务流程进行一致性分析在保证系统的可信度上有着重要的作用,它既可以用来识别偏离的执行信息并提供相应的诊断信息,也可以用来评估流程模型的质量[1].一致性分析通过将现有的流程模型与来自该流程模型的事件日志作比较,检验记录在日志中的现实的流程是否与流程模型相一致.

已有的关于一致性方面的研究在纯控制流已经进行了深入的研究[2],但忽略了在控制流之外的其他方面,例如操作流程的数据对象、活动资源、活动生命周期等,这可能导致误导性的一致性诊断.文献[3]介绍了一种在考虑数据、资源和时间等视角的同时协调事件日志和模型的方法,通过构建一个ILP(Integer Linear Programming)问题,融合考虑其他视角获得最佳对齐,以量化一致性和分析模型与现实之间的差异.这种方式的缺点是首先考虑控制流,无法平衡数据与控制流之间的成本,因此返回的对齐可能不是最优的.对此,文献[4]提出一种新的平衡考虑多视角的算法,同时考虑控制流与数据属性,基于可定制的代价函数来平衡不同角度的偏差,有助于避免传统的单视角或分阶段方法产生的误导结果.文献[5]提出利用活动依赖进行数据感知过程一致性检查,采用基于过程分解和迹重放的启发式方法来确定参考迹,使得日志与模型的一致性程度变为两个迹之间的一致性程度,识别由活动依赖偏差引起的一致性下降.文献[6]提出一种基于Petri网的事件日志与流程模型之间快速对齐的RapidAlign方法,根据移动类型计算代价值最终生成一个最优对齐图.文献[7]展示了如何将在纯控制流设置中研究的基于 SAT 的编码提升到数据感知案例中,使用 SMT 作为底层形式和算法框架;并引入了一种基于属性保留聚类的预处理技术,以加快一致性检查输出的计算速度.

在业务流程分析中,决策模型与表示法(DMN)是帮助流程建模以及实现一致性检查的一种重要方法.文献[8]为决策模型以及流程和决策的集成提供了形式化的定义,同时提供了一个包含整个流程的决策模型,而不是只关注局部决策点.文献[9]提出了DMN决策表的形式化语义和决策表上分析任务的形式化定义,并基于定义提出一个基于构成决策表的规则的几何解释大决策表分析和重构方法.文献[10]将重点放在数据视角,探讨了在BPMN过程中建模并用于决策的数据如何以及在多大程度上可以在相应的DMN决策模型中表示,并确定一组可以捕获BPMN流程中可能表示的数据的模式,用于派生得到一个与流程一致的决策模型.

融合控制流与数据流来分析业务流程的一致性已经成为现代研究发展的新趋势.本文将重点放在业务流程的数据决策上,从业务流程执行的决策逻辑出发,对生活中常见的业务流程模型分析根据实际情况寻找决策点,建立其带有DMN决策表的BPMN模型;通过将其转换为数据流Petri网给出它正式的执行语义;最后提出一个基于依赖关系的一致性分析算法,计算模型与事件日志的一致性,验证本文提出的方法的合理性.

1 基本概念

本文以数据流Petri网为研究基础,以Petri网模型与事件日志间的一致性检查为研究重点,下面给出贯穿全文的一些基本背景概念.

定义1[11](流程模型Petri网)三元组N=(P,T,F)称为一个流程模型的Petri网,须满足以下条件:

a) 有限库所集P≠φ,有限变迁集T≠φ;

b)P∩T=φ,P∪T≠φ;

c)F⊆(P×T)∪(T×P);

d) dom(F)∪cod(F);

其中:

dom(F)={x∈P∪T|∃y∈P∪T:(x,y∈F)}

cod(F)={x∈P∪T|∃y∈P∪T:(y,x∈F)}

如上,P和T为网N的两个基本元素,在图中分别用圆圈和矩形来表示.

定义2[12](数据流Petri网)一个数据流Petri网DPN=(P,T,F,V,αI,guard)是一个六元组,包含在流程模型Petri网N=(P,T,F)以外的描述,满足以下条件:

a)V是活动的有限集;

b)αI为变量赋初始值;

c)guard为网中每个变迁分配一个守卫,有guard(v)α=true,表示对于变量v的赋值α满足守卫.

不同于控制流Petri网,数据流Petri网包含对业务流程数据信息的描述,即元组中的guard实现了对业务流程中数据信息的有效约束.

2 动机案例

本节利用一个常见的银行贷款的实例来研究提出的基于活动依赖关系的一致性检查方法.在常见的银行贷款业务流程中,客户首先发出贷款申请,银行对提交申请的客户进行信誉评估,综合其职业、工资等各项信息以确定是否符合银行规定的开放贷款的条件,若符合即可开放贷款,不符合则驳回申请.

图1是一个用BPMN语言描述的业务流程.银行评估可对客户开放贷款后,为客户办理贷款,并为客户提供相应的办理通道,不符合开放贷款条件的客户则直接反馈拒绝申请.仅考虑这一业务流程建立的控制流模型,计算模型与事件日志是否一致,可以得到较高的一致性值,但本文在考虑现实的数据信息后并非如此.银行对客户信誉评估通常分为几个等级,不同信誉等级的客户享有不同的贷款额度上限,据此,对原有模型进行调整,解决上述问题,如图2所示.然而,模型的复杂度显而易见,因此,本文引入决策表的概念,将信誉评估任务链接到DMN决策表,该决策表将在应当做出决策时执行,其结果帮助决定BPMN流程的下一步执行.

图1 银行贷款业务流程

图2 信誉评估BPMN流程

3 基于依赖关系的数据流Petri网一致性分析

3.1 引入DMN决策表建模准则

图2流程模型解决了根据客户信誉等级以及客户申请贷款额度决定执行结果的问题,但也同时增加了模型的复杂度.为简单、高效解决银行贷款业务流程中业务执行的决策逻辑问题,本文引入了DMN标准中的决策逻辑的概念来优化原有的流程模型.通过在模型中对需要决策的活动添加DMN决策表构建模型的决策逻辑,并将决策模型转换为相应的数据流Petri网模型DPN,它有效扩展了带有数据属性的Petri网.

定义4[14](DMN决策表)一个DMN标准的决策表DT=(name,I,O,Def,H)是一个五元组,其中:

1)name是决策表名称;

2)I为输入,关联一个类型和一组输入值;

3)O为输出,关联一个类型和一组输出值;

4)Def是一个默认赋值函数,将一些输出属性映射到相应的默认值;

5)H是决策表的命中策略,指定决策表的结果.

图3为将“信誉评估”链接到DMN决策表中,由决策表做出相应决策,决定流程的下一步执行.客户信誉等级和进行贷款申请的额度作为输入,匹配列出的7条规则,命中得到相应的输出结果为同意贷款申请还是拒绝申请.后续将引入DMN决策表得到的BPMN模型编码为数据流Petri网,实现一致性分析的目标.

图3 贷款信誉评估决策表示例

3.2 基于活动依赖关系的一致性检查规则

本节提出了基于依赖关系的一致性分析算法,在算法1中,通过给定的事件日志和数据流Petri网模型计算出在纳入数据约束后,利用活动间的依赖关系得到的日志与模型的一致性度.算法为业务活动及其携带数据分配代价值,据此计算对齐时所需代价值.

首先,本文提出的一致性检查方法要求对流程模型和事件日志进行对齐,以显示事件如何在模型中重放,下面给出与对齐相关的概念.

定义5 (依赖关系)设活动的有限集A={a1,a2,…,an},若从活动ai至活动aj间存在一条有向路径,则称活动aj依赖于活动ai,记为,相反,若两个活动间没有任何依赖关系,则称两个活动是相互独立的.例如在上述提到的银行贷款业务流程中,活动B,C,D,E皆依赖于活动A,活动A中携带的数据信息决定了下一步应当执行哪个活动.

定义6 (对齐)设一个Petri网N=(P,T,F,V,α,guard),σ∈L是一条迹,将日志中事件的依赖关系与模型中活动间依赖关系相对应,形成事件日志与流程模型之间的对齐γ=(R(σ),R(N)).其中,迹中所有事件的依赖关系集为R(σ)={,,…},R(N)={,,…}则表示模型中活动的所有依赖关系集.

假定模型中将发生的变迁为t1,其映射的活动为A,在对齐的过程中,从模型中观察到的直接依赖关系,即观察到依赖于活动A的活动B,在迹中并没有观察到这样的依赖关系,此时就可以得到一个模型移动;反之从迹中观察到的依赖关系在模型中并不能实现,即认为观察到一个日志移动;如果能够在模型和日志中观察到同样的依赖关系,但迹中事件携带的数据信息不能匹配模型的守卫,其移动也认为不合理.

对于基于依赖关系的对齐的定义如下:

1)若(a,b)∈(E×E)且(t1,t2)∈(T×T)或a=≫(b=≫)且t1=τ(t2=τ),记为同步移动MS;

2)若(a,b)∈(E×E)且t1=≫(t2=≫),记为日志移动ML;

3)若(t1,t2)∈(T×T)且a=≫(b=≫),记为模型移动MN;

4)否则记为非法移动.其中≫表示无移动.

定义7 (最优对齐)[15]给定迹和Petri网模型,可能存在着多种对齐,使用代价函数为事件与活动的上述每种移动分配代价值,根据给定的代价函数,找到代价值κ(γ)最低的对齐即为所需的最优对齐.对于一个最优对齐γ,有κ(γ)≤κ(γ′),即最优对齐的代价值小于等于任意一个对齐γ′.

考虑活动的重要性和数据对活动的影响,定义的代价函数如下:

(1)

其中:val(e)表示日志中事件e的属性所对应的数据值,act(e)表示日志中事件所代表的活动名称,|num(attr)|则表示事件或活动所包含的具有数据值的属性个数,|num(attr)|dif则表示具有的不同的数据值的个数.

定义8 (一致性度)设模型N和迹σ=,对齐γO为模型与日志的最优对齐,γR为参考对齐,即考虑最坏情况所得到的对齐,得到模型与日志对齐的一致性度为:

(2)

通过上述定义和公式,给出基于依赖关系的一致性度的计算如算法1所述.

Algorithm 1 Fitness level based on dependencies

Input:DPN=(P,T,F,V,α1,guard),

σ=

Output:F(σ,N)

1R(σ)←{},R(N)←{} // initialize the aggregate of dependencies

2 For eachei∈σdo

3R(σ)←GetEventDep(ei)//get the dependencies of eventei

4 End for

5 For eachti∈DPNdo

6R(N)←GetEventDep(ti) //get the dependencies of activitytiin the model

7 End for

8 For eachri∈R(σ) do

9 For eachrj(N)∈R(N) do

10κ(γOi)←argminγ∈(ri(σ),ri(N))κ(γ) //get the minimum cost value of each alignment

11κ(γRi)←argmaxγ∈(ri(σ),ri(N))κ(γ) // get the maximum cost value of each alignment

12 End for

15 End for

17 ReturnF(σ,N)

算法1描述了使用给定代价函数计算模型与日志的一致性的方法,算法主要分为三部分,首先,行2～7遍历给定的日志迹,获得其依赖关系存储在集合中R(σ),同时,依据控制流结构遍历模型,获得其中存在的依赖关系,存储在集合R(N)中;接着,行8～12将获得的依赖关系对齐,计算每个对齐所需代价值,并分别保存最小和最大代价值;行13、14计算最优对齐和参考对齐总代价值;最后,行16根据定义8的公式计算得到一致性度.

4 实例分析

本节以上述银行贷款流程为例,验证本文提出方法的有效性.针对流程模型中存在的两个决策点构建决策表,得到的模型如图4所示.模型中添加了两个决策表,分别为“信誉评估”决策表和“办理通道”决策表,前者用来根据客户的信誉等级和贷款金额决定申请结果,后者则为可实行贷款申请的用户分配业务办理通道.

图4 带决策表的银行贷款流程

为验证本文提出的一致性检查方法,将给定的事件日志与构建的数据流Petri网模型对齐,并将计算得到的一致性度和事件日志与初始模型对齐得到的一致性度进行比较,说明本文方法所构建的模型能够更有效挖掘事件日志中存在的异常问题,帮助提高业务流程的合理性.图5即为根据图4流程模型得到的数据流Petri网模型.

图5 银行贷款数据流Petri网

给出银行贷款业务中的不完整事件日志,以其中的一条迹σ1为例,σ1=<(A,{amount=296000}),(B,{grade=B,amount=296000}),F,G,(H,{rank=0,channel=common}),J>,分析其与流程模型的一致性.

对于得到的图5数据流Petri网模型M1,首先分别提取出迹与模型的依赖关系集R(σ1)和R(M1),其依赖关系如下:

1)迹中事件依赖关系集

R(σ1)={<(A,{amount=296000}),

(B,{grade=B,amount=296000})>,

<(B,{grade=B,amount=296000}),F>,

,

,

<(H,{rank=0,channel=common}),J>}

2)模型中活动依赖关系集

R(M1)={<(A,{amount>0}),

(B,{(grade=A)∧(amount∈(0,30])})>,

<(A,{amount>0}),

(C,{(grade=B)∧(amount∈(0,20])})>,

<(A,{amount>0}),

(D,{(grade=C)∧(amount∈(0,10])})>,

<(A,{amount>0}),

(E,{amount=undef})>,

<(B,{(grade=A)∧(amount∈(0,30])}),F>,

<(C,{(grade=B)∧(amount∈(0,20])}),F>,

<(D,{(grade=C)∧(amount∈(0,10])}),F>,

(E,{amount=undef}),F>,

,

,

,

,

,

<(H,{rank=0,channel=common}),G>,

<(I,{rank=1,channel=VIP}),G>,

,

,

<(I,{rank=1,channel=VIP}),J>}

根据上述得到的依赖关系进行对齐,计算最小的代价值获得最优对齐,计算模型与给定迹的一致性度如表1所示.

表1 迹σ1与模型M1对齐示例

对于给出的代价函数,表1所示对齐即为找到的最优对齐,因为日志与模型间不存在代价值更小的对齐,因此,其最优对齐代价值为κ(γO)=2,计算得到的数据流模型与事件日志的一致性度:

计算在未加入数据信息的情况下,初始模型M0与它的一致性度,可以看到,在不考虑数据元素时,给定的日志迹可以在模型中完全重放,不存在不一致的行为,因此获得的一致性度F(σ1,M0)=1.但在本文提出的方法中,一致性度仅为0.82,显然,在实际贷款流程中,迹σ1存在着不合理性,客户所申请的贷款金额高于其信誉等级所能获得的最高贷款额度,这种不合理性在不考虑数据信息时无法被模型筛选出来.同时,与文献[3]将控制流优先考虑不同,本文提出的计算方法同时着眼于数据流与控制流,所提出的代价函数也相应地考虑了数据信息对流程执行的影响,实现了控制流和数据流之间的有效融合,因此,本文提出的方法更具合理性.

至此可以得出结论,在不考虑数据因素的情况下,业务流程模型与事件日志具有良好的一致性,能够在模型中有效重放事件日志,但在考虑了贷款额度与客户信誉等级这种与实际情况更相近的数据环境下,数据流模型与事件日志的一致性大大下降,这有利于检测流程执行中存在的与实际执行间的偏差问题,帮助后期对事件日志进行检测、修复或对模型进一步优化以提高一致性.

5 结 语

本文提出一种基于活动依赖关系的数据流模型与事件日志的一致性检查方法,该方法将流程中涉及的数据信息考虑在内,采用给定的代价函数计算模型与迹的一致性度,从而评估业务流程的合理性.同时,该方法通过查找模型中存在的决策点并对其添加决策表来构建合理且尽可能贴合实际系统的流程模型,为一致性分析铺平道路.此方法不仅能在控制流角度分析流程的一致性,还进一步从数据视角加强对业务流程合理性的判断.关于数据流模型一致性检查的研究有很多,未来的工作中,将寻求更合理的代价函数及对齐方法进行一致性检查,同时,根据修复后的事件日志及相关领域知识挖掘更为合理且符合实际的高一致性模型也是今后研究的重点.