随着企业对过程重视程度的不断提高,过程模型在不同企事业单位中正变得日益普遍.由于过程模型的不断积累和演化,企业组织有可能拥有并管理维护成百上千个业务过程模型[1].因为建模目标和应用场景的不同,同一业务过程可能被描述为多个相似的业务过程模型.建模人员也可能根据特定的需求和环境定制、裁剪现有的参考模型(如添加、删除或修改模型中的活动),以节约建模的时间和成本.此外,过程模型也可能被不断地修改成一系列的不同版本.上述因素导致企业组织的过程模型库中可能存在大量相似的过程模型变体(以下简称过程变体).如何有效地管理和识别过程变体之间的共同点和差异性,并保持这些过程变体的一致性演化,是过程模型管理的关键问题之一[2].而准确有效地建立过程变体之间的元素匹配关系,是解决这一问题的重要基础[3].此外,除了从微观视角对过程模型的元素进行匹配分析,还可以宏观地度量模型之间整体的匹配程度,为过程模型的查询和检索提供有效的技术支持[4].因此,本文重点研究如何有效地建立过程变体之间的模型元素匹配关系,并在此基础上进一步整体地度量过程模型之间的匹配程度.
目前,对该领域的研究工作通常首先建立过程模型之间的节点匹配关系,然后基于这些节点对应关系和匹配程度,从结构[5-7]或行为[8-10]的视角度量模型整体的相似性程度.现有研究中,模型元素匹配关系的建立通常依赖于唯一的活动命名,或者利用活动名称之间的文本相似度计算来解决不同模型间的语义差异.然而在不同的过程模型之间,除了活动命名的差异性外,由于建模目标和习惯的不同,一个相同的业务逻辑可能被不同的建模人员用不同数量的活动甚至不同的模型结构来实现.因此,仅仅简单地考虑模型元素之间的原子对应关系是不够的,在分析过程变体之间的共性和差异性时,还需要建立并考虑节点组合之间的复杂对应关系.更加全面准确地建立模型元素匹配关系,也将有助于提高模型整体匹配度量的效果[11].
建立过程变体之间复杂对应关系时,主要面临以下挑战:首先,复杂对应关系可能并非完全由原子对应关系组成,若干相似性较低的节点对有可能组合出相似程度较高的复杂对应关系;此外,节点组合的选择显然具有指数级的时间复杂度,因此需要一种有效的组合策略来保证效率.通过引入单入口单出口过程模型片段(single- entry-single-exit process fragment,简称SESE过程块)的概念[12],在过程模块能够很大程度上地表达相对完整独立业务逻辑的假设基础上,提出了基于过程结构树(process structure tree,简称PST)[12]的模型元素对应关系的构建方法,高效率地建立了过程模型元素之间的复杂对应关系;然后,基于过程模型相应的过程结构树之间的节点匹配关系,提出了基于树编辑距离[13]的过程模型相似性度量方法;最后,利用从BPM AI过程模型库(BPM academic initiative repository)[14]中选取的过程变体集合,对本文提出的方法进行了实验评估.
本文的贡献可以分为两个方面:1) 提出了基于SESE过程块的过程模型复杂对应关系的构建方法,相比现有支持原子对应关系[6, 15]或者单对多复杂对应关系[5, 16]的方法,在支持更全面合理对应关系构建的同时又保证了查找效率;2) 提出了基于SESE过程块对应关系度量过程模型相似度的方法,探索了从树编辑距离的视角度量模型之间的匹配程度,并且实验评估表明,该方法能够较好地应用于过程模型查询和相似性分析等场景中.
本文第1节通过模型示例对研究问题进行分析,并介绍本文工作的相关背景和概念.第2节介绍基于过程结构树的模型片段对应关系的构建方法.第3节阐述基于树编辑距离的过程模型相似性度量算法.第4节讨论本方法实验评估的结果和存在问题的.第5节讨论并比较本文的相关工作.第6节对全文的研究工作进行总结,并提出接下来的研究方向.
1 问题背景本节首先通过一组过程变体的示例对本文的研究问题进行了解释说明,然后介绍了本文方法有关的背景和概念,包括过程模型、SESE过程块以及过程结构树等.
1.1 一组过程变体的示例图 1给出了两个使用BPMN描述的请求处理过程.可以看出:两个模型表达的业务流程是相似的,都是首先创建或获取一个请求,然后对请求进行处理和状态的跟踪.但是仍然不难发现,两个模型之间存在不少差异,不仅包括活动命名的不同(如,模型(a)中的活动track request status和模型(b)中的活动tracking state of request),而且还存在由于建模目标和粒度的不同引起的模型结构的差异(如,模型(a)中的活动pull request在模型(b)中被分解为两个活动操作search request和load request来表达).因此,在模型间建立元素对应关系时,不仅需要匹配具有相同命名的模型元素,也需要考虑这些具有差异但又相似的地方.为了定量地表示他们的相似程度,每组对应关系可以被分配一个匹配值(match value),匹配值的计算和阈值的选取是对应关系建立的关键.我们在图 1中通过活动的颜色和标记给出了所建立的活动对应关系,包括原子对应关系(例如,模型(a)中的活动A对应模型(b)中的A),单对多复杂对应关系(例如,模型(a)中的活动C对应模型(b)中的{C1,C2})以及多对多复杂对应关系(例如,模型(a)中的活动{B1,B2}对应模型(b)中的{B3,B4}).
目前,在实践中已有多种过程建模语言用于描述业务过程,包括业务过程建模与标注(business process model and notation,简称BPMN)、事件驱动过程链 (event-driven process chains,简称EPC)以及UML活动图(UML activity diagram)等.这些过程建模语言至少包括两类基本节点:活动节点和控制节点.活动节点描述由人工或软件程序执行的任务,而控制节点描述了活动节点间的行为顺序.我们希望本文提出的方法能够应用于不同建模语言,因此,后文中将使用过程模型图PMG(process model graph)而非某种特定的建模语言来阐述过程模型匹配的过程.一个PMG是由节点和边的集合组成的连通有向图,其中,节点可能包含命名标签、类型、资源使用等属性.
定义1(过程模型图PMG). 过程模型图PMG是一个五元组(N,E,T,W,a),其中,
· N表示模型中所有节点的集合;
· EÍNxN表示节点间有向边的集合;
· T表示一组属性名的集合,例如TYPE,LABEL,RESOURCE,INPUT,OUTPUT等属性;
· W表示由若干个字符串组成的集合;
· a:N®(T®W)表示节点和属性的映射关系,其中,属性由属性名和字符串属性值的映射构成.
图 2给出了图 1中过程模型(b)相应的过程模型图PMG的描述.可以看出:不同类型的节点在BPMN中用不同的图符描述,但在PMG中都统一表示为圆型的节点.节点的类型和名称等均作为节点拥有的属性,根据过程模型的需要,也可以添加更多的附加属性,如资源使用、输入/输出数据等.
为了限制问题的范围,本文假设所有涉及的过程模型是块结构化的(block-structured).当一个过程模型中的顺序关系、分支和循环都是由具有明确开始和结束节点的块表示时,我们称该过程模型是块结构化的[17].这些块可以相互嵌套但不能重叠.相比于非块结构化的模型,块结构化的模型更易于用户理解,并且出现结构错误的可能性更小[18].文献[19]的案例研究表明:块结构化的过程模型在模型库中所占比例极高,并且一个非块结构化的过程模型在通常情况下能够被转换为块结构化的模型[17].因此,我们使用这一假设保证本文基于过程块方法的有效性,并且该限制并不会对本文方法的适用性产生较大影响.
1.3SESE过程块和过程结构树一个块结构化的过程模型可以层次分解为一组模型模块组成的集合,本文引入SESE过程块的概念[12]对过程模型进行层次化分解.文献[18]分析指出,过程模块通常能够表达一个相对完整独立业务逻辑.因此,SESE过程块可以作为复杂对应关系识别的理论基础.
定义2(SESE过程块). 令x,y为过程模型图G中的两个节点:如果每条从起始节点到y的通路上都包含x,则称x控制y;如果每条从y到终止节点的通路上都包含x,则称y受控于x.同理,边之间的控制与受控关系也可以类似地定义.过程模型图G中的SESE过程块是一个由两条相异的边(a,b)定义的过程块:
· a控制b;
· b受控于a;
· 每条包含a的回路中均包含b,每条包含b的回路中均包含a.
根据上述形式化的定义,过程块就是过程模型图中由单一入口开始并且由单一出口结束的任何区域.图 3给出了对示例过程模型图的过程块划分结果,所有的过程块用虚线方框标出.我们可以认为一个活动节点本身是一个过程块,并且整个过程模型图也可以当作是一个过程块.
事实上,图 3所示的过程模型图包含的过程块比图中标识出来的要更多.例如,由R10和R11合并组成的模型片段(记作R10ÈR11)同样也是SESE过程块,但仅有图中虚线框标出的过程块才是规则的(canonical).该概念的解释是:两个过程块F1和F2是顺序相邻的当且仅当F1的出口边与F2的入口边相同.一个过程块F不是规则的当且仅当存在过程块X,Y,Z,其中,F=XÈY,并且F和Z顺序相邻;否则,我们称F为规则的过程块.我们约定,下文所有提到的过程块均是指规则的过程块.
已有研究证明,两个过程块之间要么相互嵌套要么不相交[12].因此,一个过程模型的过程块可以构成一个树形结构,称为过程结构树PST(process structure tree)[12],它与经典的程序结构树(program structure tree)[20]的概念类似.图 3给出了图 1中两个过程模型相应的过程结构树,图中圆圈表示过程块,根节点表示整个过程模型,叶子节点表示模型节点.利用环路等价算法[20]对过程模型图进行处理,可以在线性时间复杂度内生成与其对应的过程结构树.这一理论基础,保证了我们方法的有效性和效率.
2 基于PST的过程变体元素匹配建立过程变体之间准确的元素对应关系,是识别模型差异性、保证变体演化一致性的重要前提.为了支持模型间复杂对应关系的建立并保证方法的效率,避免节点间无意义的随意组合,我们在能够表达相对独立完整业务逻辑的过程块之间寻找对应关系,并度量过程块之间的匹配程度.我们将过程模型元素对应关系的构建问题转化为两棵过程结构树之间节点映射关系的查找过程,模型间的元素对应关系包括:
· 原子对应关系:两个叶子节点之间的映射关系;两个包含单一子节点的非叶子节点之间的映射关系;
· 单对多对应关系:包含单一子节点的非叶子节点与包含多个子节点的非叶子节点之间的映射关系;
· 多对多对应关系:两个包含多个子节点的非叶子节点之间的映射关系.
本节定义了过程结构树之间两个节点对应关系成立的条件,并分别提出叶子节点之间以及非叶子节点之间匹配程度的度量方法.
2.1PST节点之间映射关系的判别依据PST节点之间映射关系的判别依据,决定了两个过程模型中哪些过程块之间存在对应关系.我们根据PST节点类型的不同,基于节点之间的相似性程度,提出叶子节点之间以及非叶子节点之间映射关系的判别依据.
定义3(PST叶子节点之间映射关系的判别依据). 令n和m分别为过程结构树PST1和PST2中的叶子节点,分别代表过程模型图PMG1和PMG2中的节点元素node1和node2,它们之间存在候选映射关系当且仅当它们之间的匹配值Match(n,m)不低于某给定阈值:
$Match\left( {n,m} \right) = SimN\left( {nod{e_1},nod{e_2}} \right) \ge cutof{f_n}$ | (1) |
其中,叶子节点n和m之间的匹配值可以由节点node1和node2之间的节点相似度SimN(node1,node2)表示,其值域为[0, 1],具体计算方法在第2.3节中的定义11中说明.参数cutoffn表示叶子节点间映射关系成立的判别阈值,取值范围为[0, 1],通过实验评估将该值设置为0.55.
候选映射关系之间可能出现重叠,即一个节点与多个节点之间存在映射关系.这种情况下,仅保留其中匹配值最高的映射关系(若存在多个相同的最高值,任意选取其中之一),将其他候选映射关系删除,从而最终得到节点之间的映射关系.另外,该规则在下面提出的非叶子节点之间映射关系中同样适用.
定义4(PST非叶子节点之间映射关系的判别依据). 令P和R分别为过程结构树PST1和PST2中的非叶子节点,若P和R均有唯一的子节点(分别记作n和m),则P和R之间存在候选映射关系当且仅当它们的子节点n和m之间存在候选映射关系,且P和R之间的匹配值Match(P,R)=Match(n,m);否则,P和R之间存在候选映射关系当且仅当它们之间的匹配值Match(P,R)不低于某给定阈值:
$\begin{array}{l} Match(P,R) = {\omega _1} \cdot \frac{{Num(P,R)}}{{Min(P,R)}} + {\omega _2} \cdot SimT(Str(P),Str(R))\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} + {\omega _3} \cdot \frac{{SimN({}^ \circ P,{}^ \circ R) + SimN({P^ \circ },{R^ \circ })}}{2} \ge cutof{f_p} \end{array}$ | (2) |
上述表达式定义了PST非叶子节点P和R之间的匹配值的计算方法,公式中考虑了3种因素对相似程度的影响:两者的子孙叶子节点之间存在的对应关系的覆盖率、两者的子孙叶子节点属性的综合文本相似度以及两者相应的上下文模型节点的相似度,具体地说:
· Num(P,R)表示P和R各自的子孙叶子节点之间存在的映射关系数量;
· Min(P,R)表示P和R中包含子孙叶子节点较少者的子孙叶子节点数量;
· Str(P)表示P中子孙叶子节点对应的模型元素所有属性值串联构成的字符串.例如,对于图 3中的PSTb,R4的串联属性串Str(R4)=“GTW Direct Approval ACT Indirect Approval ACT GTW”(即节点按深度优先顺序排列).如果过程模型中节点包含其他更多的属性,也可以类似地添加进该字符串中;
· SimT(Str1,Str2)表示字符串Str1和Str2之间的文本相似度,其值域为[0, 1],具体计算方法在第2.3节中的定义7中详细说明;
·${}^ \circ P$和$P{}^ \circ \$分别表示P对应的过程块的前后顺序相邻的模型节点;
· w1,w2,w3分别表示赋予对应关系覆盖率、文本相似度以及上下文节点相似度的权重,并且三者之和为1.通过实验分析,本文设定w1=0.2,w2=0.7,w3=0.1;
· cutoffp表示非叶子节点间的判别阈值,取值范围为[0, 1],通过实验评估,我们将该值设置为0.6.
在过程块包含的节点之间存在更多的对应关系,意味着过程块之间相似程度很可能更高.因此,在从上述表达式中,两个过程块之间的相似程度除了考虑过程块包含的所有节点属性的文本相似度之外,也考虑了过程块中所包含节点的对应关系的覆盖率.另外,过程块在模型中的前后相邻节点的匹配程度也会对其相似度产生影响,因此,我们将过程块的匹配程度定义为上述3项因素的加权平均值.
2.2PST节点之间映射关系的构建方法由于非叶子节点的映射关系的判别条件依赖于叶子节点之间的对应关系,因此我们首先需要构建叶子节点之间的映射关系,然后再构建非叶子节点之间的映射关系.首先,按照深度优先顺序对第一棵过程结构树PST1进行遍历,遍历到叶子节点时,在另一棵PST2中遍历寻找符合判别依据的叶子节点,并将该对应关系及其匹配值保存.全部遍历完成之后,需要根据匹配值的高低最终构建出不重叠的映射关系.最终建立的叶节点映射关系及其匹配值是:(Start,Start,1),(g1,g1,0.83),(A,A,1),(g2,g2,0.67),(g3,g3,0.67),(C,C2,0.88),(g4,g4,0.72),(D,D,1),(g5,g5, 0.58),(E2,E3,1),(H,H,0.92),(End,End,1).
非叶子节点之间对应关系的构建与上一步类似,在PST1中遍历到非叶子节点时,在另一棵PST2中遍历寻找符合判别依据非叶子节点,并将该对应关系及其匹配值保存.我们以PST1中的P11为例,如图 4所示.
假设算法寻找到了PST2中的R12,在两过程块包含的节点中,活动E2和E3之间存在一条对应关系,因此,对应关系的覆盖率为0.5,P11的串联属性串Str(P11)=“GTW Inform Department ACT Log Request ACT GTW”, R12的串联属性串Str(R12)=“Log Request ACT Request Inform ACT”,从而SimT(Str(P11),Str(R12))≈0.75.此外,P11和R12的上下文节点相似度约为0.29,计算得到匹配值Match(P11,R12)≈0.66>cutoffp,从而认为P11和R12之间存在候选映射关系.
遍历所有节点后并去除重叠关系后,建立过程块之间映射关系及其匹配值如下:(P1,R1,0.76),(P2,R2,0.77), (P3,R3,1),(P4,R4,0.71),(P7,R9,0.88),(P8,R10,1),(P9,R11,0.67),(P11,R12,0.66),(P13,R13,1),(P17,R16,0.92).
2.3 过程模型节点相似性度量为了PST之间叶子节点的匹配值,需要定义过程模型节点之间的相似性度量,即:给定两个过程模型图中的两个节点,返回表征它们相似程度的值,取值范围为[0,1].首先,我们认为只有相同类型的模型节点之间可能存在相似关系,例如活动节点与控制节点之间的相似度为0,因此定义类型相似度如下:
定义5(类型相似度). 给出(N1,E1,T1,W1,a1)和(N2,E2,T2,W2,a2)两个PMG,对于节点n1ÎN1和n2ÎN2,它们之间的类型相似度记作:
$SimY({n_1},{n_2}) = \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ }}{\alpha _1}({n_1}).TYPE = {\alpha _2}({n_2}).TYPE}\\ {0,{\rm{ otherwise}}} \end{array}} \right.$ | (3) |
对于事件和活动等具有明确命名标签的模型节点,我们可以通过它们具有的属性值来度量节点间的相似程度.属性相似度是两个节点公共属性值的文本相似度的加权平均:
定义6(属性相似度). 给出(N1,E1,T1,W1,a1)和(N2,E2,T2,W2,a2)两个PMG,对于节点n1ÎN1和n2ÎN2,它们之间的属性相似度记作:
其中,x表示两个节点具有的公共属性的数量,wi表示赋予各个属性的权重.例如,在本文实验评估的模型集合中,节点属性仅包括在任何模型中都存在的命名标签LABEL和类型TYPE两种,并未包含资源和数据等其他属性,因此应用的属性相似度计算式可以特例化为SimA(n1,n2)=SimT(a1(n1).LABEL,a2(n2).LABEL).
上述定义中的SimT表示两个字符串的文本相似度.考虑到在过程模型的节点名称中经常存在的近义词和单词顺序的影响,例如Check Invoice和Invoice Verified,我们引入同义词的概念,将字符串之间的文本相似度定义如下[8]:
定义7(文本相似度). 假设f1和f2分别是字符串l1和l2所含单词构成的多重集合(允许集合中含有相同元素),则字符串l1和l2的文本相似度可以用两个字符串拥有的相同或同义的单词的数量来衡量,记作:
$SimT({l_1},{l_2}) = \frac{{{\omega _i} \cdot |{f_1} \cap {f_2}| + {\omega _j} \cdot \sum\nolimits_{(s,l) \in {f_1}\backslash {f_2} \times {f_2}\backslash {f_1}} {sym(s,l)} }}{{\max (|{f_1}|,|{f_2}|)}}$ | (5) |
其中,sym(s,l)表示单词s和l是否为同义词(基于字典查询判断):如果是,则返回值为1;否则,返回0.参数wi和wj分别是赋予相同词和同义词的权重,我们根据文献[8]中的推荐值设定为1和0.75.在考虑文本相似度时,我们忽略特殊字符、字母大小写和一些常用词,并使用词干提取算法统一动词时态[21].
对于控制节点(网关gateway)而言,他们除了类型之外并不具有其他的属性,因此属性相似度并不适用.我们采用上下文相似度对它们进行评估,上下文相似度表示节点的前驱或后继节点组成的集合之间的相似程度.我们注意到:由于控制节点的前驱(后继)节点仍有可能为控制节点,例如图 1模型(a)中的节点g6.为了保证此类节点的上下文相似度能够有效计算,我们首先引入传递前驱节点集合和传递后继节点集合的概念:
定义8(传递前驱节点集合,传递后继节点集合). 在一个PMG:(N,E,T,W,a)中,两个节点n,mÎN之间存在路径当且仅当存在一系列节点n1,…,nkÎN,其中,n=n1,m=nk,并且对于所有iÎ1,...,k-1而言,(ni,ni+1)ÎE成立.控制节点路径是一条路径,满足:其中任意节点n¢Î{n2,…,nk-1}均为控制节点,记作nÞm.定义n的传递前驱节点集合为{n¢ÎN|n¢Þn},记作nin;n的传递后继节点集合为{n¢ÎN|nÞn¢},记作nout.
上述定义可以直观地理解为:当查找节点的前驱(后继)节点时,如果找到的节点仍为控制节点,则继续寻找该节点的前驱(后继)节点,直到不是控制节点为止,例如图 1模型(a)中g6in={D}.基于上述概念,定义节点间上下文相似度如下:
定义9(上下文相似度). 给出(N1,E1,T1,W1,a1)和(N2,E2,T2,W2,a2)两个PMG,对于节点n1ÎN1和n2ÎN2,它们之间的上下文相似度是传递前驱和传递后继节点集合之间匹配程度,记作:
$SimC({n_1},{n_2}) = \frac{{\sum\nolimits_{({n_i},{n_j}) \in M_{SimA}^{opt}(n_1^{in},n_2^{in})} {SimA({n_i},{n_j})} + \sum\nolimits_{({n_p},{n_q}) \in M_{SimA}^{opt}(n_1^{out},n_2^{out})} {SimA({n_p},{n_q})} }}{{\max (|n_1^{in}|,|n_2^{in}|) + \max (|n_1^{out}|,|n_2^{out}|)}}$ | (6) |
其中,$M_{SimA}^{opt}(n_1^{in},n_2^{in})$表示n1和n2的传递前驱节点集合之间的最佳节点对应关系集合.即在$n_1^{in}$和$n_2^{in}$之间选择不
重叠的节点配对,使得它们属性相似度之和为最高,其详细定义如下:
定义10(最佳节点对应关系集合). 给出(N1,E1,T1,W1,a1)和(N2,E2,T2,W2,a2)两个PMG,其中,S1ÍN1,S2ÍN2是两
个PMG节点的子集,节点n1ÎS1,n2ÎS2.S1和S2之间的节点对应关系集合是一个S1到S2的局部内射S1aS2,记作M(S1,S2).$M_{SimA}^{opt}({S_1},{S_2})$是一个最佳节点对应关系集合当且仅当对于任意的节点对应关系集合M(S1,S2)满足条件:
$\sum\nolimits_{({n_1},{n_2}) \in M_{SimA}^{opt}({S_1},{S_2})} {SimA({n_1},{n_2})} \ge \sum\nolimits_{({n_1},{n_2}) \in M({S_1},{S_2})} {SimA({n_1},{n_2})}$ | (7) |
基于上述定义的类型相似度、属性相似度和上下文相似度,我们可以综合地给出过程模型之间任意两个节点的相似度计算方法:
定义11(节点相似度). 给出(N1,E1,T1,W1,a1)和(N2,E2,T2,W2,a2)两个PMG,对于节点n1ÎN1和n2ÎN2,它们之间的节点相似度记作:
$SimN({n_1},{n_2}) = \left\{ {\begin{array}{*{20}{l}} {SimY({n_1},{n_2}) \cdot SimA({n_1},{n_2}),{\rm{ }}{\alpha _1}({n_1}).TYPE \ne Gateway}\\ {SimY({n_1},{n_2}) \cdot SimC({n_1},{n_2}),{\rm{ otherwise}}} \end{array}} \right.$ | (8) |
本节将基于两个过程模型对应的过程结构树及其之间的节点映射关系来度量过程模型之间的整体匹配程度.树是计算机科学中最常见和广泛研究的组合结构之一,树之间的相互比较问题已经应用于结构化文本数据库、程序分析、编译器优化等多个研究领域中.树编辑距离[13]是一种常见的有序树(ordered tree)之间相似性度量方法,由字符串编辑距离的概念扩展得到.我们将本文使用的树编辑距离的概念定义如下:
定义12(树编辑距离). 两棵有序树T1和T2之间的编辑距离是将T1转换到T2的所有基本操作的最小开销总和,记作d(T1,T2).基本操作包括删除和转换现有节点以及插入新节点等3种.我们把插入和删除节点v的操作开销记作cdel(v),把节点v1转换为节点v2的操作开销记作cmatch(v1,v2).本文中定义插入或删除节点操作开销cdel(v)=1,节点转换操作开销反比于节点之间的匹配程度,具体地:cmatch(v1,v2)=2×(1-Match(v1,v2)).
由于树T1中的一个删除操作等价于树T2中的一个插入操作,在计算编辑距离时,可以仅考虑在两棵树上进行删除和转换操作来将T1和T2转换成相同的树.目前的树编辑距离的算法都是在有序森林(ordered forest)的基础上进行,而有序树是有序森林的特例.本文使用文献[22]中提出的经典递归算法来计算树编辑距离.我们把空的森林或树记作Æ,森林F的节点集合简单记作F.对于节点vÎF,以节点v为根的子树记作Fv,删除节点v后得到的森林记作F-v.特别地,若F为一棵树,将删除F的根节点后得到的森林记作F-.森林F中最左边和最右边的树分别记作LF和RF,它们的根节点记作lF和rF,则F和G之间的编辑距离d(F,G)递归地计算如下:
δ(Ø,Ø)=0 | (9) |
δ(F-rF,Ø)+cdel(rF) | (10) |
δ(Ø,G)=δ(Ø,G-rG)+cdel(rG) | (11) |
$\delta (F,G) = \min \left\{ {\begin{array}{*{20}{l}} {\delta (F - {r_F},G) + {c_{del}}({r_F})}\\ {\delta (F,G - {r_G}) + {c_{del}}({r_G})}\\ {\delta (R_F^ - ,R_G^ - ) + \delta (F - {R_F},G - {R_G}) + {c_{match}}({r_F},{r_G})} \end{array}} \right.$ | (12) |
文献[22]中证明,该算法的复杂度为O(nheight×mheight×n×m),其中,n和m分别表示树F和G的规模,即节点的数量;nheight和mheight分别表示树F和G的高度.当我们度量两棵树之间的相似度时,需要对编辑距离进行归一化处理,在两棵树之间不存在任何节点对应关系的极端情况下,他们之间的编辑距离将达到最大值.因此,可以定义树编辑距离相似度如下:
定义13(树编辑距离相似度). 给定两棵过程结构树PST1和PST2,他们之间的树编辑距离相似度为
$TSim(PS{T_1},PS{T_2}) = 1 - \frac{{\delta (PS{T_1},PS{T_2})}}{{|PS{T_1}| + |PS{T_2}|}}$ | (13) |
本节将使用真实的过程模型对过程变体匹配技术进行评估,评估分为两个部分:第1部分的目标是评估模型变体之间元素匹配关系构建的有效性,并寻找匹配关系判别依据中各参数的合适取值;第2部分我们在过程模型集合中查找与给定的输入模型相似的模型,通过分析查询结果来评估过程模型整体匹配度量的有效性.
4.1 过程变体元素匹配的评估使用BPM AI过程模型库[14]作为实验评估模型的来源.BPM AI是由工业界和学术界合作创建的用于科学研究的过程建模平台,合作组织的研究人员和学生使用平台提供的在线建模工具创建了大量描述真实过程的模型.通过设定过滤条件,我们从模型库中共获得2 183个使用BPMN Process描述的过程模型,其中,修订版本数量多于5个的模型516个,我们选取每个模型的初始版本及最新版本的组合作为候选过程变体集合,以保证过程变体之间具有一定程度的差异性.为了从这些过程变体集合中更广泛地选取具有代表性的模型,并且避免活动语义不明确的模型,通过设置模型名称关键字来定义实验集的选取范围.最终,从符合条件的255组过程变体中随机选择了25组模型,去除2组具有明显结构错误的模型,最后得到23组过程变体组成的实验模型集合**.集合中包含的过程变体分布情况见表 1.
通过使用本文方法自动构建的匹配关系和手工建立的参考匹配关系进行对比分析,来评估方法的有效性.首先将23组测试模型以问卷形式分发给课题组内其他2名具有过程建模项目经验的研究生,由他们建立每组过程模型之间的元素匹配关系,并为找到的每条复杂匹配关系赋予信任值(取值范围为{1,2,3,4,5},值越高则表示匹配程度越高).本文作者同时也对所有23组模型进行手工分析,将分析结果与回收的问卷结果进行对比,通过与问卷者讨论解决不一致意见后,最终建立参考匹配关系318条,其中包括原子对应关系248条、单对多对应关系18条以及多对多对应关系52条.
为了寻找复杂对应关系的匹配值计算的3个权重参数的合理取值,我们以0.1为间隔对3个权重值的所有组合进行测试,即,(0.1,0.1,0.8),(0.1,0.2,0.7),…,(0.8,0.1,0.1)等共计36种情况,将人工建立的70条复杂对应关系的信任值与他们在本文方法中计算得到的匹配值进行线性回归分析,结果表现最好的4组权重值组合见表 2,可以看出过程块所包含节点的属性组合而成的文本相似度w2对过程块的匹配程度起到最重要的影响.
PST节点映射关系判别依据中的阈值是决定匹配关系是否成立的重要因素,我们通过准确率P、召回率R以及F值等指标来评估构建匹配关系的有效性:准确率表示构建的匹配关系中正确的比例;召回率表示构建的匹配关系在参考匹配关系集合中的覆盖率;F值则是综合考虑准确率和召回率的结果,即,F=2×(P×R)/(P+R).为了得到阈值cutoffn和cutoffp的合适取值,我们以0.05为间隔在[0, 1]的范围内进行了测试,得到的各项评价指标的结果如图 5所示.可以看出:设置较低的阈值事实上对准确率的影响并不大,这是因为去除了候选映射关系集合中重叠的匹配关系,即每个节点或过程块都最多只能存在一条匹配关系;但是过高的阈值会导致召回率的迅速下降.如果我们以F值为综合评价指标,阈值cutoffn和cutoffp可以分别设置为0.55和0.6.
通过设定上述实验得到的权重和阈值参数,最终得到如表 3第1行所示的匹配关系构建结果.表 3中各列指标的数值中均在括号内依次给出了3类对应关系的分类统计结果.我们还将其他文献中相关的3种方法在本文的实验集的基础上进行了分析,这些方法包括活动标签匹配法[15]、贪心图编辑距离匹配法[6]以及文献[23]中提出的业务-IT模型映射方法,它们的实验结果同样在表 3列出.可以看出:方法1和方法2仅支持原子对应关系的构建,方法3能够支持复杂对应关系的建立,但本文方法在原子和复杂匹配关系的构建上都能够表现出较好的效果.通过分析认为原因是:1) 尽管方法1采用词法和语义相似度结合的活动名称相似度计算技术,方法2利用图编辑距离选取最佳对应关系集合,它们都能够一定程度的提高原子匹配关系构建的准确率,但并没有涉及控制节点之间匹配关系构建的策略,使得原子对应关系查找的召回率较低;2) 尽管方法3能够支持复杂对应关系的构建,但它未考虑活动命名的差异,即要求原子对应关系的两个节点具有相同的命名,并且在判别复杂对应关系时过于依赖于原子对应关系的识别结果,使得构建出的复杂对应关系遗漏数量较多.
通过实验评估发现:尽管本文提出的元素匹配技术相比现有方法在构造复杂对应关系方面具有一定的优势,但仍然存在局限性.由于本方法以过程结构树为载体,因此仅能够支持过程块之间的复杂对应关系的自动构建,导致了一些匹配关系查找的遗漏.此外,为了有效地生成过程结构树,本文假设进行匹配的过程模型是块结构化的,在实施本方法前需要对部分非结构化的模型进行结构化转换处理[17],因此对包含复杂控制流结构的过程模型的支持有待提升.
4.2 过程模型相似性度量的评估本节对基于过程结构树编辑距离的过程模型全局相似性度量方法进行评估分析.我们使用过程模型搜索的场景来进行实验,即给定一个输入模型M和被查询模型集合S,在集合S中查询与输入M相似的过程模型,并将查询结果按照相似程度排序.采用上节实验中使用的46个模型为基础,另外还在其相应的23组过程变体中随机选择了14个中间版本的模型,得到60个过程模型组成的被查询模型集合.我们从这60个模型的集合中随机选取了10个模型作为输入模型.为了使输入模型和被查询模型保持一定的差异,我们对输入模型进行了任意的少量修改操作,包括改变节点名称、删除或添加节点以及改变节点之间的顺序.将每个输入模型与60个被查询模型依次进行相似性分析,最终,每个输入模型都得到了按照树编辑距离相似度值由高到低排序的被查询模型的序列.
通过手工在被查询模型集合中为每个输入模型选择与之相似的模型.从直观上看,对于每个输入模型,集合中应该有2个或3个与之匹配的模型,但实际上存在更多相似的模型,这是因为不同组的过程变体之间也可能存在相似关系.通过人工判断,确认共有31对模型之间存在相似关联关系.将本文方法与节点匹配相似度[4]、图编辑距离相似度[24]以及我们前期工作[25]中扩展的图编辑距离相似度等方法进行对比分析.为了统一评估标准,这里的4种方法在进行模型节点文本相似性度量时均使用本文定义7给出的计算方法.图 6的结果表示了准确率随召回率的变化曲线,即:按照相似度值由高到低依次判断该组模型是否被人工判定为相似,直到找全所有人工判别的匹配对(即正确解).为了便于展示实验结果,在图中按照每发现3个正确解标出一次准确率数据的曲线呈现.可以看出:本文提出的基于树编辑距离的方法在找到超过80%正确解的情况下仍然保持着较高的准确率,能够较好地适用于过程模型查询的应用场景中.
分析结果看出:基于树编辑距离的过程模型相似性度量方法虽然具有较好的准确率,但相比其他方法优势并不明显.未来可以从以下两个方面来提高方法的有效性和效率:1) 针对不同层次和类型的树编辑操作,研究设定合适的权重值以提高度量的准确性;2) 由于复杂元素匹配关系的构建以及树编辑距离度量过程占用较多的时间开销,可以研究设置高效而相对简单的过滤条件(如文本特征),把一些明显不存在关联的模型组快速排除,避免在这些模型上耗费匹配度量时间,从而提高相似性搜索的效率.
5 相关工作如何有效地追踪管理模型库中的过程变体,并保持它们之间的一致性演化,是广泛研究的问题.目前,对过程变体的管理技术可以分为两类:1) 通过过程模型合并[26, 27]的方式,将相关联的过程变体通过一个可配置过程模型[28, 29]进行统一集中地管理;2) 分散管理过程变体,仍然保持它们之间的独立性,但是通过一致性分析[30]、变更传播[31]、版本控制[32]等技术手段,保证过程变体之间的一致性演化.这两类方法有一个相同之处,就是它们都需要识别过程变体之间的共同点和差异性.构建过程变体之间的匹配关系,是它们共同的理论基础.
文献[6]提出并对比了3种过程模型元素匹配的方法,包括活动名称词法匹配、贪心图匹配以及A*图匹配.实验评估结果表明:基于图编辑距离的贪心算法(贪心图匹配)能够表现出最佳的匹配结果,准确率和召回率分别达到0.89和0.60.但是这3种方法都只能支持原子对应关系的识别.
ICoP过程模型匹配框架[5]提供了一种组件式的体系架构,它将过程模型的元素匹配过程规范化为输入/输出明确的4个步骤.对于每个步骤都提供不同的可选组件,通过选择组件来创建出需要的模型匹配器,具有较强的可扩展性.但是这些组件的具体实现算法并没有具体描述.该框架中表现出最佳实验结果的匹配器实例的准确率和召回率分别达到0.82和0.51,能够支持原子对应关系和单对多复杂对应关系的构建.
文献[15]提出了一种优化的活动标签词法匹配的方法,采用单词包(bag-of-words)和活动标签剪枝(label pruning)的思想,在原子对应关系的识别上能够比字符串编辑距离和语义相似度等技术的准确率更高.文献[16]提出了基于语义注释的过程模型匹配方法,并在活动匹配中考虑了活动输入输出数据的影响,但是该方法同样不能支持多对多对应关系,并且没有给出具体的实验评估数据.
文献[23]提出的业务层模型到IT层模型映射方法能够支持多对多对应关系的识别,但是没有考虑节点名称之间的相似性,即要求匹配节点具有相同的命名;此外,在判别复杂对应关系是否成立时,该方法采用两个阈值“一刀切”的方法,即所包含节点的原子对应关系覆盖率和综合文本相似度必须同时超过给定阈值,这使得复杂对应关系的建立过于依赖于原子对应关系的识别结果.而本文采用加权平均的判别方法,并考虑了上下文节点相似度的因素.上述方法各自支持的特性在表 4中进行了总结.
本文相关的另一个研究问题是过程模型之间的相似性度量.Dijkman等人[4]提出并评估了3类过程模型相似性度量方法:节点匹配相似度、结构相似度和行为相似度.实验结果表明,基于图编辑距离的结构相似度的表现略优于其他两种度量方法.文献[24]进一步分析和评估了4种基于图编辑距离相似度指标的算法,最终,贪心算法能够得到更加准确的度量结果并且效率最佳.文献[7]提出了一种快速过程模型相似性搜索方法,它能够在传统的结构相似性度量之前,通过提取简单的模型特征对模型的相似度进行快速评估,避免了过多不必要的结构分析操作,从而较大幅度地提高了时间效率.本文的前期研究[25]扩展了传统的图编辑距离相似度的计算方法,考虑了模型元素的复杂对应关系对相似度的影响.而本文采用了更直观的树编辑距离的相似性度量方法,从模型结构的另一种角度进行了探索.此外,还有一些研究通过抽取模型的行为特征,基于活动之间的因果关系来度量模型之间的行为相似性[8-10].
6 结束语本文从模型的微观和宏观两个视角对过程变体匹配技术进行了研究:从微观的角度,提出了基于过程结构树的模型元素匹配关系查找技术,保证了过程变体匹配的效率和有效性;此外,还从宏观的角度进一步研究了如何度量过程模型之间整体的匹配程度,利用已构建好的模型元素匹配关系,提出了基于树编辑距离的过程模型相似性度量方法.利用从BPM AI过程模型库中选取的过程变体集合进行了实验评估,结果表明,本文提出的过程变体匹配方法能够有效地支持全部3种类型的元素对应关系,并在查全率和查准率指标上表现出了良好的效果,基于树编辑距离的过程相似性度量方法也能够较好地适用于过程模型查询的应用场景中.
在评估过程中发现:仍然存在少量的匹配关系并非由过程块构成,造成了一些匹配关系的遗漏.在未来工作中,我们考虑研究过程块形式以外的其他模型节点组合模式,以提高匹配关系发现的召回率.此外,将对方法进行扩展来支持包含复杂控制流模式(如取消和多实例等)的过程模型.最后,本文实验使用的过程变体源自于修改模型带来的不同版本,未来将使用多种来源以及更大规模的过程变体集合对本方法作进一步地评估和改进.
[1] | Dijkman R, La RM, Reijers HA. Managing large collections of business process models—Current techniques and challenges. Computers in Industry, 2012,63(2):91-97 . |
[2] | Lu R, Sadiq S, Governatori G. On managing business processes variants. Data & Knowledge Engineering, 2009,68(7):642-664 . |
[3] | Weidlich M, Mendling J, Weske M. Propagating changes between aligned process models. Journal of Systems and Software, 2012, 85(8):1885-1898 . |
[4] | Dijkman R, Dumas M, Van Dongen B, Kaarik R, Mendling J. Similarity of business process models: Metrics and evaluation. Information Systems, 2011,36(2):498-516 . |
[5] | Weidlich M, Dijkman R, Mendling J. The ICoP framework: Identification of correspondences between process models. In: Proc. of the 22th Int’l Conf. on Advanced Information Systems Engineering. 2010. 483-498 . |
[6] | Dijkman R, Dumas M, García-Banuelos R. Aligning business process models. In: Proc. of the 13th IEEE Int’l Enterprise Distributed Object Computing Conf. 2009. 45-53 . |
[7] | Yan ZQ, Dijkman R, Grefen P. Fast business process similarity search. Distributed and Parallel Databases, 2012,30(2):105-144 . |
[8] | Van Dongen B, Dijkman R, Mendling J. Measuring similarity between business process models. In: Proc. of the 20th Int’l Conf. on Advanced Information Systems Engineering. 2008. 450-464 . |
[9] | Kunze M, Weidlich M, Weske M. Behavioral similarity—A proper metric. In: Proc. of the 9th Int’l Conf. on Business Process Management. 2011. 166-181 . |
[10] | Wang SH, Wen LJ, Wei DS, Wang JM, Yan ZQ. SSDT matrix-based behavioral similarity algorithm for process models. Computer Integrated Manufacturing Systems, 2013,19(8):1822-1831 (in Chinese with English abstract). |
[11] | Dijkman RM, Van Dongen B, Dumas M, Garcia BL, Kunze M, Leopold H, Mendling J, Uba R, Weidlich M, Weske M, Yan ZQ. A short survey on process model similarity. In: Proc. of the 25 Years of CAiSE: Seminal Contributions to Information Systems Engineering. 2013. 421-427 . |
[12] | Vanhatalo J, Volzer H, Leymann F. Faster and more focused control-flow analysis for business process models through SESE decomposition. In: Proc. of the 5th Int’l Conf. on Service-Oriented Computing. 2007. 43-55 . |
[13] | Bille P. A survey on tree edit distance and related problems. Theoretical Computer Science, 2005,337(1):217-239 . |
[14] | BPM academic initiative. http://bpt.hpi.uni-potsdam.de/BPMAcademicInitiative/ |
[15] | Klinkmüller C, Weber I, Mendling J, Leopold H, Ludwig A. Increasing recall of process model matching by improved activity label matching. In: Proc. of the 11th Int’l Conf. on Business Process Management. 2013. 211-218 . |
[16] | Gater A, Grigori D, Bouzeghoub M. Complex mapping discovery for semantic process model alignment. In: Proc. of the 12th Int’l Conf. on Information Integration and Web-Based Applications & Services. 2010. 317-324 . |
[17] | Kiepuszewski B, Hofstede AHM, Bussler CJ. On structured workflow modelling. In: Proc. of the 12th Int’l Conf. on Advanced Information Systems Engineering. 2000. 431-445 . |
[18] | Reijers HA, Mendling J. Modularity in process models: Review and effects. In: Proc. of the 6th Int’l Conf. on Business Process Management. 2008. 20-35 . |
[19] | Thom LH, Reichert M, Iochpe C. Activity patterns in process-aware information systems: Basic concepts and empirical evidence. Int’l Journal of Business Process Integration and Management, 2009,4(2):93-110 . |
[20] | Johnson R, Pearson D, Pingali K. The program structure tree: Computing control regions in linear time. In: Proc. of the ACM SIGPLAN ’94 Conf. on Programming Language Design and Implementation. 1994. 171-185 . |
[21] | Porter MF. An algorithm for suffix stripping. Program: Electronic Library and Information Systems, 1980,14(3):130-137 . |
[22] | Zhang K, Shasha D. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing, 1989,18(6):1245-1262 . |
[23] | Branco MC, Troya J, Czarnecki K, Kuster J, Völzer H. Matching business process workflows across abstraction levels. In: Proc. of the 15th Int’l Conf. on Model Driven Engineering Languages and Systems. 2012. 626-641 . |
[24] | Dijkman R, Dumas M, Garcia BL. Graph matching algorithms for business process model similarity search. In: Proc. of the 7th Int’l Conf. on Business Process Management. 2009. 48-63 . |
[25] | Ling JM, Zhang L, Feng Q. An improved structure-based approach to measure similarity of business process models. In: Proc. of the 26th Int’l Conf. on Software Engineering and Knowledge Engineering. 2014. 377-380. |
[26] | La Rosa M, Dumas M, Uba R, Dijkman R. Business process model merging: An approach to business process consolidation. ACM Trans. on Software Engineering and Methodology, 2013,22(2):1-42. |
[27] | Li C, Reichert M, Wombacher A. Mining business process variants: Challenges, scenarios, algorithms. Data & Knowledge Engineering, 2011,70(5):409-434 . |
[28] | La Rosa M, Dumas M, Hofstede AHM, Mendling J. Configurable multi-perspective business process models. Information Systems, 2011,36(2):313-340 . |
[29] | Rosemann M, Van der Aalst WMP. A configurable reference modelling language. Information Systems, 2007,32(1):1-23. |
[30] | Weidlich M, Mendling J, Weske M. Efficient consistency measurement based on behavioral profiles of process models. IEEE Trans. on Software Engineering, 2011,37(3):410-429 . |
[31] | Weidlich M, Weske M, Mendling J. Change propagation in process models using behavioral profiles. In: Proc. of the 6th Int’l Conf. on Services Computing. 2009. 33-40 . |
[32] | Ekanayake CC, La Rosa M, Hofstede AHM, Fauvet MC. Fragment-Based version management for repositories of business process models. In: Proc. of the 10th Int’l Conf. on Cooperative Information Systems. 2011. 20-37 . |
[10] | 汪抒浩,闻立杰,魏代森,王建民,闫志强.基于任务最短跟随距离矩阵的流程模型行为相似性算法.计算机集成制造系统,2013, 19(8):1822-1831. |