流程相似性度量一直是工作流研究中的一个主要方向^[1].业务流程作为企业的三要素之一, 在实际的业务流程管理中, 需要对2个业务流程进行比较, 以求得不同流程之间的相似性^[2].在互联网大时代背景下, 如中国移动这类办公自动化的大集团公司, 其业务流程非常繁杂众多, 流程数量动辄数以万计, 且具有较大的冗余性^[3].高效的流程相似性算法可以为基数庞大的流程比较、索引和搜索提供有效的保证^[4].除此之外, 流程相似性计算同样被广泛地运用于组织合并、用户需求变更、模型仓库管理等多个领域^[5].

主流的流程相似性算法一般基于以下3个方面展开:1) 任务标签、事件或其他建模元素; 2) 模型拓扑结构; 3) 过程模型的执行语义.殷明等^[3]针对流程相似性研究, 总结提出了流程相似性算法应该满足的五大基本性质, 即:顺序结构漂移不变性、互斥结构漂移不变性、跨度负相关性、非替代无关递减性和循环序列长度负相关性.近年来, 流程相似性算法层出不穷, 经典的流程相似度算法有:TAR算法^[6]、CF算法^[7]、BP算法^[8]、PTS算法^[9], 还包括一些改进算法, 如:TAR++算法^[10]和PTS++算法^[5]，但是仍然存在一些未能解决的问题, 具体表现为对一些常见模型的相似性度量与预期值不符、算法复杂度太高不适用于实际生产或不满足上述五大基本性质等.

本文基于标签Petri网对业务流程建模, 引入BP算法中行为轮廓^[11]和变迁关系的概念, 定义5类变迁之间的基本关系, 对已有行为轮廓进行扩充.对传统的工作流网进行改进, 提出一种不同流程中映射变迁的关系相似性度量(transition relation similarity, TRS)方法, 从映射变迁结构相似性的角度, 给出计算流程相似度的新思路.

1 Petri网模型介绍 1.1 Petri网基本元素

Petri网为简单的过程模型, 如图 1所示, 由下列几类基本元素构成：

1) 库所(Place)圆形节点, 以○表示;

2) 变迁(Transition)方形节点, 以□表示;

3) 有向弧(Directed arc)库所和变迁之间的有向弧, 以有向线段“→”表示;

4) 令牌(Token)动态存在于库所中, 以“·”表示.

Petri网是一个三元组，N=(P, T, F)，P={p₁, p₂, p₃, …, p_m}是库所的有限集合, T={t₁, t₂, t₃, …, t_n}是变迁的有限集合, 有P∪T≠∅且P∩T=∅.F代表流关系, 即有向弧的有限集合, F=(T×P)∪(P×T)={e₁, e₂, e₃, …, e_k}, “×”代表笛卡尔乘积.Petri网集合P∪T中的任意一个库所p_i或变迁t_i均为Petri网中的一个节点; Petri网集合F中的任意元素即为一条有向弧称为Petri网的边, 相同类型的2个节点之间不允许存在相连接的边.

1.2 Petri网基本概念

前集与后集:对于一个Petri网结构N=(P, T, F), 设x∈(P∪T), 称∙x为x的前集或输入集, x∙为x的后集或输出集.特别地，当x∈T时, 称∙x为x的输入库所集合, 称x∙为x的输出库所集合^[12].

顺序(Order)关系:对于一个Petri网结构N=(P, T, F), 设t₁∈T, t₂∈T, t₂只能在t₁发生后才有可能发生, t₁和t₂的发生存在直接的因果关系.顺序关系是不对称的, 且存在传递性, 如图 2所示.

并发(And)关系:对于一个Petri网结构N=(P, T, F), 设t₁∈T, t₂∈T, t₁和t₂是相互独立的, 即(∙t₁∪t₁∙)∩(∙t₂∪t₂∙)=∅, t₁和t₂的发生不存在因果关系.并发关系是对称的, 且没有传递性.

设And-split结构与And-join结构分别对应于一个变迁有多个输出库所和一个变迁有多个输入库所, 如图 3所示.And-split变迁表示通过该变迁使得多个任务可以同时被执行, 而And-join变迁只有当前任务都完成才能触发.

冲突(Xor)关系:对于一个Petri网结构N=(P, T, F), 设t₁∈T, t₂∈T, t₁和t₂的发生存在着冲突, 当其中某一个发生时另一个一定不会发生.冲突关系是对称的, 即“t₁和t₂冲突”与“t₂和t₁冲突”是等价的.

设Xor-split结构与Xor-join结构分别对应于一个库所有多条以其为始点的边和以其为终点的边, 如图 4所示, 库所中令牌用于对接下来发生的变迁进行选择.

1.3 工作流网——WF-net

基于Petri网模型对系统流程进行建模, 用变迁表示资源的消耗、使用及系统状态产生的变化等.用库所表示系统中的资源, 如状态、条件、媒介等^[13].库所可以容纳一定数量的令牌, 用来表示资源的数量, 若一个变迁的输入库所集合中存在足够数量的令牌使其使能, 则该变迁可以被触发(firing), 当变迁触发后会消耗一定数量的令牌, 并在其输出库所中生成新的令牌^[14].

基于上述关系将系统流程构建成一个Petri网结构N_Petri=(P, T, F), 若N_Petri满足以下条件:

1)N_Petri只存在一个起始库所s, 即∙s=∅;

2)N_Petri只存在一个终止库所e, 即e∙=∅;

3) 若增加一个变迁t连接库所s和e, 即t∙={e}且∙t={s}.

Petri网N_Petri=(P, T, F)∪{(e, s)}是强连通的, 如图 5所示.在此基础上引入标签的概念, 给变迁分配任务名称, 使得变迁跟实际流程中的任务对应起来, 构成工作流网, 其中M₀为初始标识, 即初始的资源分布, M₀:P→{0, 1, 2, …}.因此, 给定六元组工作流网为N_W=(P, T, F, M₀, s, e).

定义1  节点度数:对工作流网N_W中的某一个节点v, 与之连接的边称为该节点的边.从该节点流出的边称为输出边, 简称出边, 记输出边的集合为E_o, |E_o|称为该节点的出度; 流向该节点的边称为输入边, 简称入边, 记输入边的集合为E_i, |E_i|称为该节点的入度, 显然, s的入度和e的出度均为0.出度与入度之和|E_o|+|E_i|, 称为节点的度数, 简称度, 记作Deg (v).

定义2  变迁可达关系:对工作流网N_W中任意2个变迁t₁∈T, t_n∈T.若N_W中存在一个由有限数量的边和节点组成的点边交替可执行序列S_trace=(t₁, …, e_i, p_j, e_i+1, t_k, …, t_n), 使节点t₁和t_n分别位于序列的始点和终点, i, j, k∈N⁺, 则称t₁和t_n可达, 记作t₁Rt_n, R表示变迁可达关系, S_trace称为t₁和t_n的可达路径.

在序列S_trace中, 如果同一条边不出现2次, 则称此路径为简单可达路径, 同一节点不出现2次的简单可达路径称为基本可达路径.如果路径的始点t₁和终点t_n相重合, 即t₁=t_n, 则称此路径为可达回路, 没有相同边的可达回路称为简单可达回路, 通过各节点不超过一次的简单可达回路称为基本可达回路.S_trace的长度|S_trace|等于序列中所有边的数量和.

2 变迁相似性度量

在普遍的业务流程管理中, 企业组织内的各个行为活动并不单独地属于某个特定的流程, 而是根据不同的工作需要, 某些行为活动会在不同的业务流程中多次出现, 配合其他的行为活动从而达到完成特定业务目标的作用^[15].本文利用Petri网对业务流程进行建模研究, 变迁元素代表了实际业务流程中的行为活动, 库所代表了相关行为的条件或状态.在对不同的工作流网模型进行元素映射时, 主要通过对变迁与库所节点展开.

需要说明的是, 本文旨在提出一种流程模型相似度的度量方法, 只关注流程模型定义本身，因此, 对不同业务流程实例及其运行情况或令牌分布, 不予讨论.同时, 由于本文选取的角度是基于变迁映射的, 库所映射不在讨论范围之内.下面将从变迁映射展开对变迁关系相似度度量的具体研究.

2.1 变迁映射

前文已经提及变迁元素对应的行为活动可以出现在不同的业务流程中, 在实际应用中, 一般可以通过行为活动的标识, 对不同流程中的相同行为进行识别和对应.本文在建模过程中将基于行为活动标识的互异性这一特性, 同样用行为的标识代替对变迁节点的标识.

通常情况下, 变迁的标识一般为一个字符串, 因此判断2个标识是否表示为同一个任务, 可以结合上下文的执行语义或行为相似度, 同时, 也可以通过判断2个字符串是否相等进行确定^[15].本文的研究是在变迁映射的基础上展开的, 旨在研究2个不同业务模型的相似度.同时, 上文提到行为相似度与下文将提出的变迁关系相似度是2个完全不同的概念.前者用于对2个变迁进行映射, 后者指的是在良好的变迁映射的前提下, 求得不同工作流网模型中的同一个变迁节点在整体结构上的相似度.

2.2 变迁关系

在工作流网的基础上, 任意2个变迁在整个工作流网的结构上存在着不同的关系, 为了便于表述, 在进行变迁关系相似性度量之前, 本文首先对变迁之间的关系进行如下定义.

定义3  强线性(Strong linear)关系:设流程A的工作流网为N_W(A)=(P_A, T_A, F, M₀, s, e), 存在t_m∈T, t_n∈T且t_m≠t_n, t_m和t_n不在同一条可达回路上, 若∃p∈P使∃((t_m, p)∈F∧(p, t_n)∈F)或∃((t_n, p)∈F∧(p, t_m)∈F), 则称t_m和t_n存在强线性关系, 记为→或←, t_m和t_n的关系记为→(t_m, t_n)或←(t_m, t_n), 如图 6所示.显然, 由Petri网的规则可知, 强线性关系是反对称的且不满足传递性.将满足强线性关系的变迁对构成的集合称为强线性关系集合, 记作→A, 可知, →A⊆(T×T).

定义4  弱线性(Weak linear)关系:设流程A的工作流网为N_W(A)=(P_A, T_A, F, M₀, s, e), 存在不同变迁t_m∈T, t_n∈T且t_m≠t_n, t_m和t_n不在同一条可达回路上.若t_m和t_n不满足强线性关系, 但存在一个有限序列S_trace, (|S_trace| > 2), 使得t_m至t_n可达, 则称t_m和t_n存在弱线性关系, 关系符号记为~≻或≺~, t_m和t_n的关系记为~≻(t_m, t_n)或≺~(t_m, t_n)(箭头方向代表t_m至t_n路径S_trace中起始点指向终点的方向), 如图 7所示.显然, 弱线性关系是反对称的且满足传递性, 将满足弱线性关系的变迁对构成的集合称为弱线性关系集合, 记作~≻A, 可知, ~≻A⊆(T×T).

定义5  互斥(Mutex)关系:设流程A的工作流网为N_W(A)=(P_A, T_A, F, M₀, s, e), 存在t_m∈T, t_n∈T且t_m≠t_n, t_m和t_n之间不存在任何可达路径, 同时t_m和t_n满足冲突关系, 则称t_m和t_n存在互斥关系, 关系符号记作+, t_m和t_n关系记为+(t_m, t_n), 如图 8所示.显然, 互斥关系是对称的且满足传递性, 即若存在+(t_m, t_n), 则一定存在+(t_n, t_m).特别地, 如果t_m=t_n, 则有+(t_m, t_m), 即变迁自身满足互斥关系.将满足互斥关系的变迁对构成的集合称为互斥关系集合, 记作+A, 可知, +A⊆(T×T).

定义6  并行(Parallel)关系:设流程A的工作流网为N_W(A)=(P_A, T_A, F, M₀, s, e), 存在t_m∈T, t_n∈T且t_m≠t_n, t_m和t_n不在同一条可达回路上, 同时, t_m和t_n满足并发关系.则称t_m和t_n之间存在并行关系, 关系符号记作‖, t_m和t_n关系记为‖(t_m, t_n), 如图 9所示.显然, 并行关系是对称的且满足传递性, 即若存在‖(t_m, t_n), 则一定存在‖(t_n, t_m).将满足互斥关系的变迁对构成的集合称为并行关系集合, 记作‖A, 可知, ‖A⊆(T×T).

定义7  循环(Circulation)关系:设流程A的工作流网为N_W(A)=(P_A, T_A, F, M₀, s, e), 存在t_m∈T, t_n∈T且t_m≠t_n, t_m和t_n之间在同一条可达回路上，则称t_m和t_n之间存在循环关系, 关系符号记作$\leftrightarrow, {{t}_{m}}$和t_n关系记为$\leftrightarrow $(t_m, t_n), 如图 10所示.显然, 循环关系是对称的且不满足传递性.将满足循环关系的变迁对构成的集合称为循环关系集合, 记作$\leftrightarrow $A, 由此可知, $\leftrightarrow $A⊆(T×T).

基于上述5类变迁关系定义, 在前述六元组工作流网中, 加入一个关系类集合r, 构成本文所提出的七元组工作流网:N′_W=(P, T, F, M₀, r, s, e), 其中r={→, ~≻, +, ‖, $\leftrightarrow $ }.可以将一个流程的行为轮廓通过这5种变迁关系集合表示出来，如流程A的行为轮廓可以记为B_A={→A, ~≻A, +A, ‖A, $\leftrightarrow $A}, 行为轮廓展现了某个工作流程大量的属性及特征, 为进行流程的相似度分析提供了一个新的角度.

2.3 变迁关系相似性度量

通过5类变迁之间的基本关系定义, 本文提出一种变迁关系相似性度量方法(TRS).上述部分介绍了行为轮廓提供一组行为的抽象, 其意义在于不用具体考虑行为的细节而仅仅关注行为在整体结构中的关系和可能的执行路径.

利用变迁之间的关系可以将行为轮廓通过变迁关系矩阵的形式表达出来, 称为变迁关系矩阵, 流程A和B的变迁关系矩阵如表 1和2所示.

由变迁关系的定义可知, 变迁关系矩阵是一个对称矩阵, 满足对称阵的基本性质.通过变迁关系矩阵可以很直观地得到各个变迁之间的关系, 同时在此基础上, 也便于研究映射变迁之间相似度问题.

为了更好地表述相关概念, 进行如下定义.

定义8  变迁关联集合:设流程A的工作流网为N_W(A)=(P_A, T_A, F, M₀, s, e), 其行为轮廓为B_A={→A, ~≻A, +A, ‖A, $\leftrightarrow $ A}, 对∀t_m:t_m∈T_A, 存在下列集合:

$ \begin{array}{l} \to A\left( {{t_m}} \right) = \{ < {t_m}, {t_n} >, < {t_n}, {t_m} > |{t_n} \in {T_A} \wedge ( \to ({t_m}, \\ {t_n}) \in \to A \vee \to \left( {{t_n}, {t_m}} \right) \in \to A)\} \sim \succ A\left( {{t_m}} \right) = \{ < {t_m}, \\ {t_n} >, < {t_n}, {t_m} > |{t_n} \in {T_A} \wedge \sim \succ \left( {{t_m}, {t_n}} \right) \in \to A \vee \sim \succ \\ \left( {{t_n}, {t_m}} \right) \in \sim \succ A\} + A\left( {{t_m}} \right) = \{ < {t_m}, {t_n} > |{t_n} \in {T_A} \wedge \\ \left( { + \left( {{t_m}, {t_n}} \right) \in + A \vee + \left( {{t_n}, {t_m}} \right) \in + A} \right)\} \parallel A\left( {{t_m}} \right) = \\ \{ < {t_m}, {t_n} > |{t_n} \in {T_A} \wedge (\parallel \left( {{t_m}, {t_n}} \right) \in \parallel A \vee \parallel \left( {{t_n}, {t_m}} \right) \in \\ \parallel A)\} \leftrightarrow A\left( {{t_m}} \right) = \{ < {t_m}, {t_n} > |{t_n} \in {T_A} \wedge ( \leftrightarrow ({t_m}, {t_n}) \in \\ \leftrightarrow A \vee \leftrightarrow ({t_n}, {t_m}) \in \leftrightarrow A)\} \end{array} $

令C_A(t_m)={→A(t_m), ~≻A(t_m), +A(t_m), ‖A(t_m), A(t_m)}, 则称C_A(t_m)为变迁t_m的关联集合.特别地, 变迁关联集合C_A(t_m)的模|C_A(t_m)|计算如下:

$|{C_A}\left( {{t_m}} \right)| = | \to A\left( {{t_m}} \right)| + | \sim \succ A\left( {{t_m}} \right)| + | + A\left( {{t_m}} \right)| + \parallel |A\left( {{t_m}} \right)| + | \leftrightarrow A\left( {{t_m}} \right)| = \sum {|\Re A\left( {{t_m}} \right)|.} $其中$\Re $ ∈r, m=1, 2, 3, …, |T|.

如图 11所示, 流程A的工作流网为N_W(A)=(P_A, T_A, F, M₀, s, e).其中, T_A={t₁, t₂, t₃, t₄, t₅, t₆, t₇}, 取t₅∈T_A, 由流程A关系矩阵易得:

$ \begin{array}{*{20}{l}} { \to A\left( {{t_5}} \right) = \{ < {t_5},{t_6} > , < {t_1},{t_5} > \} ,\left| { \to A\left( {{t_5}} \right)} \right| = 2;}\\ { \sim \succ A\left( {{t_5}} \right) = \{ < {t_5},{t_8} > \} ,\left| { \sim \succ A\left( {{t_5}} \right)} \right| = 1;}\\ { + A\left( {{t_5}} \right) = \{ < {t_5},{t_4} > , < {t_5},{t_5} > \} ,\left| { + A\left( {{t_5}} \right)} \right| = 2;}\\ {\parallel A\left( {{t_5}} \right) = \{ < {t_5},{t_2} > , < {t_5},{t_3} > \} ,\parallel \left| {A\left( {{t_5}} \right)} \right| = 2;}\\ { \leftrightarrow A\left( {{t_5}} \right) = \{ < {t_5},{t_7} > \} ,\left| { \leftrightarrow A\left( {{t_5}} \right)} \right| = 1.} \end{array} $

则$\left| {{C_A}\left( {{t_5}} \right)} \right| = \sum \left| {\Re A\left( {{t_5}} \right)} \right|$, 其中,

$\Re \in r, m = 1, 2, \ldots, \left| {{T_A}} \right| = 8$, 可得|C_A(t₅)|=|T_A|=8.

不失一般性, 可以得到以下推论:

对任意工作流网N_W=(P, T, F, M₀, r, s, e), 对∀t∈T, 有|C(t)|=|T|.

定义9  映射变迁关系相似度:设流程A、B的工作流网分别为N_W(A)=(P_A, T_A, F, M₀, s, e), N_W(B)=(P_B, T_B, F, M₀, r, s, e).

若∃t_m:t_m∈T_A∧t_m∈T_B, 令:f_Inter(t_m)_{A, B}=C_A(t_m)∩C_B(t_m), 指t_m在流程A、B中, 基于本文所提出的上述5类变迁关系, 求得的变迁关系交集, 其中,

$ \begin{array}{*{20}{l}} {{C_A}\left( {{t_m}} \right) \cap {C_B}\left( {{t_m}} \right) = \left\{ { \to A\left( {{t_m}} \right) \cap \to B\left( {{t_m}} \right),} \right.}\\ { \sim \succ \left\{ {A\left( {{t_m}} \right) \cap \sim \succ B\left( {{t_m}} \right), + A\left( {{t_m}} \right) \cap + B\left( {{t_m}} \right),} \right.}\\ {\left. {\parallel A\left( {{t_m}} \right) \cap \parallel B\left( {{t_m}} \right), \leftrightarrow A\left( {{t_m}} \right) \cap \leftrightarrow B\left( {{t_m}} \right)} \right\}.} \end{array} $

令:f_Union(t_m)_{A, B}=C_A(t_m)∪C_B(t_m), 指t_m在流程A、B中, 基于本文所提出的上述5类变迁关系, 求得的变迁关系并集, 同理,

$ \begin{array}{*{20}{l}} {{C_A}\left( {{t_m}} \right) \cup {C_B}\left( {{t_m}} \right) = \left\{ { \to A\left( {{t_m}} \right) \cup \to B\left( {{t_m}} \right),} \right.}\\ { \sim \succ \left\{ {A\left( {{t_m}} \right) \cup \sim \succ B\left( {{t_m}} \right), + A\left( {{t_m}} \right) \cup + B\left( {{t_m}} \right),} \right.}\\ {\left. {\parallel A\left( {{t_m}} \right) \cup \parallel B\left( {{t_m}} \right), \leftrightarrow A\left( {{t_m}} \right) \cup \leftrightarrow B\left( {{t_m}} \right)} \right\}.} \end{array} $

由此定义映射变迁关系相似度计算方法如下:

$\begin{array}{l} {f_{{\rm{Sim}}}}{\left( {{t_m}} \right)_{A, B}} = |{f_{{\rm{Inter}}}}{\left( {{t_m}} \right)_{A, B}}\left| / \right|{f_{{\rm{Union}}}}{\left( {{t_m}} \right)_{A, B}}|, \\ \left( {{t_m} \in {T_A} \wedge {t_m} \in {T_B}, m \le \left\{ {\left. {|{T_A}|, |{T_B}|} \right\}} \right.} \right), \end{array}$其中,

$ \begin{array}{*{20}{l}} {|{f_{{\rm{Inter}}}}{{\left( {{t_m}} \right)}_{A,B}}\left| = \right| \to A\left( {{t_m}} \right) \cap \to B\left( {{t_m}} \right)| + }\\ {| \sim \succ A\left( {{t_m}} \right) \cap \sim \succ B\left( {{t_m}} \right)\left| + \right| + A\left( {{t_m}} \right) \cap + }\\ {B\left( {{t_m}} \right)\left| { + \parallel } \right|A\left( {{t_m}} \right) \cap \parallel B\left( {{t_m}} \right)\left| + \right| \leftrightarrow A\left( {{t_m}} \right) \cap }\\ { \leftrightarrow B\left( {{t_m}} \right)\parallel = \sum {\left| {\Re A\left( {{t_m}} \right) \cap \Re B\left( {{t_m}} \right)} \right|} ,\left( {\Re \in r} \right);}\\ {|{f_{{\rm{Union}}}}{{\left( {{t_m}} \right)}_{A,B}}\left| = \right| \to A\left( {{t_m}} \right) \cup \to B\left( {{t_m}} \right)| + }\\ {| \sim \succ A\left( {{t_m}} \right) \cup \sim \succ B\left( {{t_m}} \right)\left| + \right| + A\left( {{t_m}} \right) \cup + B\left( {{t_m}} \right)| + }\\ {\parallel |A\left( {{t_m}} \right) \cup \parallel B\left( {{t_m}} \right)| + | \leftrightarrow A\left( {{t_m}} \right) \cup \leftrightarrow B\left( {{t_m}} \right)\parallel = }\\ {\sum {\left| {\Re A\left( {{t_m}} \right) \cup \Re B\left( {{t_m}} \right)} \right|} ,\left( {\Re \in r} \right).} \end{array} $

如图 11所示的流程A、B, 取t₅∈T_A, T_B, 可得

$ \begin{array}{l} {f_{{\rm{Sim}}}}{\left( {{t_5}} \right)_{A, B}} = \\ \left( {1 + 1 + 2 + 2 + 0} \right)/\left( {3 + 1 + 3 + 2 + 1} \right) = 0.6. \end{array} $

因此, 可以计算出流程A和B所有公共变迁节点的关系相似度.把每一个变迁及其关系相似度关联起来, 记作f_Sim(t_m)-t_m, 如上述变迁节点t₅, 可改记为0.6-t₅.

特别地, 在流程A和B中, 当∃t_n:(t_n∈T_A∧t_n∉T_B)∨(t_n∉T_A∧t_n∈T_B), f_Sim(t_n)=0.

3 实验与分析

基于上文对映射变迁关系相似度的介绍及研究, 从映射变迁关系相似度和流程相似度计算2个方面进行具体的分析.需要说明的是, 工作流网模型是基于Petri网建立的, 属于静态模型, 下文提到的插入和删除操作只是用于对整体结构的模拟分析, 与Petri网的静态特性并没有矛盾.

3.1 变迁关系相似度实例

对于2个不同的工作流网模型, 流程C和D, N_W(C)=(P_C, T_C, F, M₀, r, s, e), N_W(D)=(P_D, T_D, F, M₀, r, s, e).其变迁集合的关系可分为两大类(T_C, T_D均不为空集):1)T_C∩T_D=∅;2)T_C∩T_D≠∅.第一种情况下, C和D中不存在相同的变迁节点, 此时讨论变迁的关系相似度没有意义.下文只针对第二种情况, 即C和D中含有相同的变迁节点, 进行相关实验分析.

如图 12中(a)和(b)所示, T_C={t₁, t₂, t₃, t₄, t₅, t₆}, T_D={t₁, t₄, t₅, t₆, t₇}.

令T′=T_C∩T_D={t₁, t₄, t₅, t₆}, 则对∨t_m∈T′均可得f_Sim(t_m)_{C, D}, 计算结果如下:

$ {f_{{\rm{Sim}}}}{\left( {{t_1}} \right)_{C, D}} = 0.57, {\rm{ }}{f_{{\rm{Sim}}}}{\left( {{t_4}} \right)_{C, D}} = 0.38, $

$ {f_{{\rm{Sim}}}}{\left( {{t_5}} \right)_{C, D}} = 0.38, {\rm{ }}{f_{{\rm{Sim}}}}{\left( {{t_6}} \right)_{C, D}} = 0.22. $

由f_Sim(t_m)_{C, D}=|f_Inter(t_m)_{C, D}|/|f_Union(t_m)_{C, D}|, (m≤{|T_A|, |T_B|})可知, 在流程C和D中插入或删除变迁, 将会提高或降低映射变迁的关系相似度.鉴于实际工作流程会比较复杂, 为了便于叙述和讨论, 本实验选取的2个示例均不含重名变迁.

3.1.1 删除变迁

对流程删除变迁, 需要存在变迁t, 且满足以下约束性条件:

1)T_C∩T_D≠∅, 且t∈(T_C∪T_D)-(T_C∩T_D);

2) Deg(t)=2;

3) 删除变迁t后, 对于∀t_m∈T_C∩T_D, 有|(f_Inter(t_m)_{C, D})′|=|f_Inter(t_m)_{C, D}|.

在包含变迁t的工作流网模型中删除变迁t, 并对其结构作出相应的调整, 会提高C和D中相同变迁节点的关系相似度.其中, 第二个条件是为了在执行删除操作后保持工作流模型的整体结构没有大的改变, 另外2个条件则是2个流程相似度提高的充分条件.

对于删除变迁操作, 如图 13(a)所示, 在流程C中删除变迁t₃, 对其工作流网结构作出相应的调整.相应地, 可以得到f_Sim′(t₁)_{C, D}=0.67, f_Sim′(t₄)_{C, D}=0.43, f_Sim′(t₅)_{C, D}=0.43, f_Sim′(t₆)_{C, D}=0.25.比较f_Sim(t_m)_{C, D}和f_Sim′(t_m)_{C, D}可知，删除变迁操作使映射变迁的关系相似度有了较大的提高.

3.1.2 插入变迁

类同于变迁, 在工作流网模型中, 对流程插入变迁, 需要存在变迁t, 且满足以下约束性条件:

1)T_C∩T_D≠∅, 且t∈[(T_C∪T_D)-(T_C∩T_D)];

2) Deg (t)=2;

3) 插入变迁t后, 对于∀t_m∈T_C∩T_D, 有|(f_Inter(t_m)_{C, D})″|>|f_Inter(t_m)_{C, D}|.

在不包含变迁t的工作流网模型中插入变迁t, 使得Deg(t)=2.同时, 在保持整体结构的前提下调整模型, 会提高流程C和D中相同变迁节点的相似度.

对于插入变迁操作, 如图 13(b)所示, 在流程D中插入变迁t₂, 对其工作流网结构作出相应的调整，得到T″=T∪t₂, 此时流程C和流程D的相同变迁节点的关系相似度如下：

$ \begin{array}{l} {f_{{\rm{Sim}}}}^{\prime \prime }{\left( {{t_1}} \right)_{C, D}} = 0.71, {f_{{\rm{Sim}}}}^{\prime \prime }{\left( {{t_2}} \right)_{C, D}} = 0.71, \\ {\rm{ }}{f_{{\rm{Sim}}}}^{\prime \prime }{\left( {{t_4}} \right)_{C, D}} = 0.50, {f_{Sim}}^{\prime \prime }{\left( {{t_5}} \right)_{C, D}} = 0.50, {\rm{ }}\\ {f_{Sim}}^{\prime \prime }{\left( {{t_6}} \right)_{C, D}} = 0.33. \end{array} $

比较f_Sim(t_m)_{C, D}和f_Sim″(t_m)_{C, D}可知，插入变迁操作同样使映射变迁的关系相似度有了较大的提高.

3.2 仿真实验

对变迁数量较多和结构比较复杂的工作流程模型, 选取如表 3所示的数据集进行仿真实验(2个模型为一组, 为了便于描述分别记作A′、B′).

对每一组模型执行有限次数满足上述条件的变迁删除操作, 删除变迁数量(number of deleting transitions, NDT)记为N_Delete, 显然N_Delete≤(|T_A′∪T_B′|-|T_A′∩T_B′|).相同变迁集合记作T′=T_A′∩T_B′, T′中元素的平均关系相似度(average relation similarity, ARS)记为${{\bar d}_{{\rm{Sim}}}} = \sum {f_{{\rm{Sim}}}}\left( {{t_m}} \right)/T\prime, ({t_m} \in T\prime )$.得到N_Delete和${{\bar d}_{{\rm{Sim}}}}$的关系如图 14所示(取实验数据中的5组模型为例).

类同于删除变迁, 对上述的数据集进行仿真实验, 对每一组模型执行满足上述条件的变迁插入操作有限次数, 插入变迁数量(number of inserting transitions, NIT)记为N_Insert, 显然, N_Insert≤(|T_A′∪T_B′|-|T_A′∩T_B′|).得到N_Insert和${{\bar d}_{{\rm{Sim}}}}$的关系如图 15所示(取实验数据中的5组模型为例).

3.3 流程相似度测量

本文研究的是2个不同工作流网模型中相同变迁的关系相似性度量, 目的在于对流程整体相似性的度量.基于映射变迁的关系相似度, 可求得图 12中流程C和D初始的流程相似度, 计算公式为

$ \begin{array}{l} {f_{Sim}}\left( {C, D} \right) = \\ \frac{{\sum (|{f_{{\rm{Inter}}}}{{\left( {{t_m}} \right)}_{C, D}}\left| / \right|{f_{{\rm{Union}}}}{{\left( {{t_m}} \right)}_{C, D}}|)}}{{\sum {f_{{\rm{Inter}}}}{{\left( {{t_m}} \right)}_{C, D}}\left| / \right|{f_{{\rm{Union}}}}{{\left( {{t_m}} \right)}_{C, D}})\left| { + (} \right|{T_C} \cup {T_D}\left| - \right|{T_C} \cap {T_D}|)}} \approx 0.34. \end{array} $

其中, t_m∈T_C∩T_D, $\Re $ ∈r, m≤min {|T_C|, |T_D|}, 由此可知, 当T_C∩T_D=∅时, f_Sim(C, D)=0.

通过如图 13所示的删除变迁和插入变迁操作, 同理可求得f_Sim′(C, D)≈0.47, f_Sim″(C, D)≈0.58.同初始的流程相似性比较可知, 约束性的增删变迁能较为显著地提高流程的相似性:

$ \begin{array}{l} {f_{{\rm{Sim}}}}\prime C,D)/{f_{{\rm{Sim}}}}\left( {C,D} \right) = 138\% ,\\ {f_{{\rm{Sim}}}}^{\prime \prime }\left( {C,D} \right)/{f_{{\rm{Sim}}}}\left( {C,D} \right) = 171\% . \end{array} $

需要说明的是, 上述流程相似度计算方法是针对不含重名变迁的工作流网模型, 但在实际业务流程中, 工作流程含有重名任务的情况是常见的, 所以需要对流程模型进行消除重名变迁的处理.为了方便表述, 本文实验选取的都是不含重名变迁的模型.

为了进一步验证本文提出方法的有效性, 将约束性的增删变迁操作应用于其他的流程相似性算法, 如表 4所示.

针对不同的方法, 流程相似性的初始值会有所不同.本文的TRS方法是基于映射变迁关系, 立足于比较流程整体结构的相似度, 因此其流程相似性初始值较低于其他方法.在不同的流程相似性算法中, 约束性增删变迁操作均可提高流程相似性.然而, 通过比较约束性增删变迁操作对各算法流程相似性的提高程度可知, TRS方法具有更为显著的提高效果.

4 结语

本文的主要贡献可以归纳为如下3点:

1) 基于标签Petri网对业务流程建模, 将传统的工作流网模型进行了变迁之间5类基本关系的定义, 构造了新的工作流网.对比已有的业务流程模型进行了结构描述功能方面的完善, 更加全面地刻画了流程行为之间的关系.

2) 在变迁映射的基础上, 提出了2个不同工作流网模型之间映射变迁关系相似性的概念, 反映了相同变迁节点在整体结构上的相似度, 并通过实验对映射变迁关系相似度进行了相关的分析.

3) 提出了一种基于映射变迁关系相似度的流程相似性度量方法提供了一种研究流程相似性的新方法.未来拟考虑从如下几个方面进行研究:

1) 在保证变迁关系相似度准确计算的前提下, 研究出一种对含有重名变迁的工作流网模型进行消除重名的处理算法.

2) 目前存在的流程相似性算法很多, 如CF、BP、PTS、TAR算法等, 在今后的研究中, 需要将本文提出的这种流程相似性度量方法与这些经典算法的效率和准确率进行多方面比较, 进一步降低算法的复杂度.

3) 本文提出的映射变迁的关系相似性度量方法还可以进一步被改进以提高效率和准确度，如何优化本文所提方法或如何找出一种更为高效的算法是未来的主要研究工作.