基于拟行为轮廓的等距离流程变体再区分

王乐霞 方 欢

（安徽理工大学数学与大数据学院 安徽淮南 232001）

关键字：业务流程模型；变体；编辑距离；拟行为轮廓相似性

随着信息技术的不断发展，商业界也愈发动态多变，这对公司业务流程的调整提出了更高要求。面对商业环境的频繁且未知的变化，流程-软件信息系统（PAISs）[1]应运而生。为保证其市场竞争力，组织和企业不断重新设计或灵活升级其业务流程，因此产生了大量源自同一业务流程的流程变体[2]。这些变体在一定程度上关联相似，但在元素层面、结构层面、行为层面[3]又存在着或多或少的差异。这些变体之间的比较研究，对充分利用流程变体的价值具有重要意义。

文献[4]从变体的结构层面出发，利用图编辑距离的概念研究变体之间的差异性。文献[5]引出了“行为轮廓”的概念，并给出了一致性的判断标准。但在流程比较方面，行为轮廓一致性忽视了插入或删除元素带来的影响。本文引入拟行为轮廓相似性的概念，研究在流程变体距离相等的情况下，原流程与变体在行为关系上的差异性，并合理的区分处理直接行为关系与间接行为关系。

一、相关概念

定义1（流程模型[6]）定义一个六元组PM=(A,G,F,s,e,t)表示一个业务流程模型，其中：

1）A表示包含模型中所有活动的有限活动集；

2）G表示包含模型中所有网关的有限网关集，而N=A∪G表示模型中包含活动和网关在内的所有结点；

3）F表示各结点之间的流弧；

4）s表示整个模型的开始结点；

5）e表示整个模型的终止结点；

6）t表示各个网关的类型，包括{and,xor}

定义2（流程变体）定义PM={PM,PM1,PM2,...,PMi,...}表示一个相关的流程模型集，其中，PM是原流程模型，{PM1,PM2,...,PMi,...}是由原模型经过系列高级变化操作得到的流程变体。

定义3（编辑距离[4]）定义d(PM,PMi)表示由原模型PM到变体PMi所经历的高级变化操作的最小数目，即min{|PM[PMi}。其中，包括从原位置移动一个活动结点到新位置、插入一个新活动结点以及删除一个原有的活动结点。

二、相似性分析

为了在变体与原流程模型距离相等的情况下，在流程行为关系上进一步区别变体之间的差异性，这一部分给出了拟行为轮廓相似性及其度量，并提出了基于距离的拟行为轮廓相似性度量的方法。

（一）定义。

定义4（拟行为轮廓相似性[7]）已知PM为原业务流程模型，其中n⊆N是模型中的结点元素，拟行为轮廓将结点元素之间的行为关系分为直接行为关系与间接行为关系，包括严格序关系、拟严格序关系、交叉序关系、拟交叉序关系、排他序关系、拟排他序关系、严格逆序关系以及拟严格逆序关系，8种行为关系划分了所有结点元素的笛卡尔积。假设PMi为一个流程变体，由此形成的关于两个模型之间的8种行为关系相似性度表示为：

然后将其按不同权重加和就得到了拟行为轮廓相似性Sim(PM,PMi)=w1sim→+w2sim←+w3sim||+w4sim++w5sim⇒+w6sim⇐+w7sim⇔+w8simχ定义5（拟行为轮廓距离度量）已知原模型PM与一个相应的流程变体，两者的编辑距离为d(PM,PMi)，拟行为轮廓相似性度为Sim(PM,PMi)，则拟行为轮廓距离度量为。

（二）变体差异[8]分析。

下面给出对距离相等的变体进一步进行行为差异分析的流程步骤：

步骤一：输入原流程模型与对应的多个流程变体。

步骤二：计算原流程模型到变体的高级变化操作数目，即编辑距离d(PM,PMi)。

步骤三：分析出各个流程模型的拟行为轮廓，并区分直接行为关系与间接行为关系。

步骤四：计算各个变体与原流程模型的严格序相似性度、拟严格序相似性度、排他序相似性度、拟排他序相似性度、交叉序相似性度、拟交叉序相似性度、严格逆序相似性度、拟严格逆序相似性度，并依据不同权重进行组合得到拟行为轮廓相似性度。

步骤五：根据公式计算得到基于距离的拟行为轮廓相似性度。

三、案例分析

在下面的案例[9]中给定了1个原业务流程模型与6个流程变体，其中，每个变体都是由原模型经过4个高级变化操作（移动某元素或插入新元素）得到，所以，它们到原模型的编辑距离d(PM,PMi)=4。例如，变体PM1是由原模型经过这样的四个高级变化操作得到。例如其中的move(PM,H,I,D)操作则表示将PM模型里的H元素从原位置移动到新位置（I元素与D元素之间）。

图1 原业务流程模型

图2 6个流程变体

下面以PM与PMi为例，分析得出两者的拟行为轮廓矩阵，如表1、2所示。

表1 PM原流程模型拟行为轮廓矩阵

表2 PM1变体拟行为轮廓矩阵

在变体到原模型编辑距离相等的情况下，要深入了解这6个变体之间的差异，需要增加一个新度量维度，即拟行为轮廓相似性。以原模型PM与变体PM1为例，依据两者的拟行为轮廓，计算出相应的8个拟行为轮廓相似性，

由于具有直接行为关系的变迁更能影响模型的行为相似性度，因此令w1=w2=w3=w4=0.15,w5=w6=w7=w8=0.1，得出PM与PMi的行为相似性度为0.341。

同理计算得到6个变体与原模型的拟行为轮廓相似性度，如下表3所示。

表3 变体拟行为轮廓相似性度

上述分析结果表明，在多个变体到原模型编辑距离相等是情况下，通过拟行为轮廓相似性度，6个变体进一步得到差异性的区分，这说明在使用编辑距离无法区分多个变体时，拟行为轮廓相似性度是行之有效的差异度量方法。

最后，为了更全面的区分与度量6个变体育原模型之间的差异性，将上述6个变体与原模型的拟行为轮廓相似性和编辑距离结合起来，根据公式，得到6个变体到原模型的拟行为轮廓距离度量值，如下表4所示。

表4 变体拟行为轮廓距离度量值

通过拟行为轮廓距离度量值计算结果分析，得知到原模型PM编辑距离相等的情况下，变体PM5与原模型差异最小，相似性最高；而变体PM2与原模型差异最大，相似性最低，6个变体按照与原模型差异性由大到小排序得到：PM5-〉PM4-〉PM6-〉PM3-〉PM1-〉PM2。

四、结语

本文通过将编辑距离与拟行为轮廓相似性度两个度量标准结合起来，解决了单一变量——编辑距离无法进一步区分多个流程变体与原模型之间差异性的问题，弥补了单一度量方法片面性的缺点。同时，拟行为轮廓相似性不同于简单的行为轮廓相似性，其合理的区分了每个结点元素的直接行为关系与间接行为关系。

本文的研究结果对未来流程变体的管理与维护将是具有一定意义的。然而，行为轮廓无论在模型相似性还是一致性上，都具有举足轻重的意义，进一步充分挖掘模型行为轮廓的研究背景、多元化研究模型之间的相似性都将是下一步研究工作的重点。