基于BPDF的流程相似性度量

2020-04-24何克清

计算机工程与设计 2020年4期

李昭，吴军，陈鹏+，何克清

(1.三峡大学计算机与信息学院，湖北宜昌 443002；2.武汉大学计算机学院，湖北武汉 430072)

0 引言

新兴信息技术正在改变甚至颠覆社会组织的经营运作方式，企业及组织通常维护大量的业务流程集，例如，中国移动公司维护了超过1000种业务流程[1]。业务流程对于企业和组织来说，是提供一种描述某些具体服务的内部过程的机制。随着各类信息技术在人类社会方方面面的深入应用，致使业务流程管理变得日益复杂，给业务流程管理带来了一系列新的挑战[2]，尤其是对业务流程的相似性度量提出了更高的新的要求。例如，现有业务流程模型相似性度量方法中存在缺失典型业务流程特征和预处理缺少自动化处理方法，业务流程推荐策略缺失业务流程典型特征的问题。业务流程管理的目标在于改进产品质量，提升服务水平，确切提高业务流程的描述能力、分析能力以及改进流程的能力。业务流程管理作为现代信息系统的共性基础技术，已经被工业界和学术界广泛关注，并在领域内快速发展，业务流程相似性度量作为BPM研究的重要组成部分愈发需要符合特定标准的方法和工具。

业务流程相似性度量方法通常用于计算两个给定的流程间的相似性。本文基于现有相似性度量方法的研究，为了提高业务流程相似性度量的准确性和有效性，有效实现流程建模的目标，更好地体现业务流程的典型特征和描述业务流程，提出了基于BPDF的流程相似性度量方法。该方法基于作者前期研究工作[3]，并且使用机器学习和统计学方法对业务流程元层数据特征进行处理，以及提出一种新的基于元数据标准的业务流程三层管理框架，以提高业务流程相似性度量的科学性和准确性。

在实际的生产业务中，随着业务需求的改变和新的市场因素的产生，业务流程通常需要进行变更，以应对新的市场变化与业务需求；或者在新的市场环境驱动下，急需在现有流程库中寻找功能相近的其它流程来替代已整体失效或异常的业务流程。此时，可以使用该方法对流程库中的流程进行分级，并优先推荐相似性处于较高级别的流程对故障流程进行替换或为故障流程的变更提供决策支持[4]。

1 相关工作

近年来业务流程的相似性度量已经被广泛研究，现有业务流程相似性度量通常涉及3个方面：①文本概念相似性；②结构相似性；③行为相似性[5]。事实已经证明业务流程结构相似性与文本概念相似性等业务流程相关特征相结合可以提高业务流程相似性度量的准确性。

Michael等[6]对业务流程相似性度量方法进行了比较研究，得出对于不同目的和规范的服务都建议使用业务流程模型的相似性度量，从文本的角度评估业务流程的相似性。Huang等[7]提出了一种改进的基于流程图结构的流程模型搜索方法。Li等[8]基于流程模型之间的结构相似性，研究流程模型的存储机制，并改进模型存储，便于用户查询和变更业务流程。Sun等[9]提出了一种基于语义任务邻接和重要性(ISTAR)语义工作流的包含领域知识的行为相似性度量方法。ISTAR相似性基于两个ISTAR集之间的相似性，表示语义工作流之间的相似性。Matthias等[10]提出了一种查询流程模型的方法，以流程样本为输入，发现所有允许查询行为的模型，并提供基于跟踪语义和抽象行为包含的概念。除了相似性匹配度的决定之外，还提供了一个亲密度评价，并可用于排名。Becker等[6]阐述了相似度度量应该具有的8个属性, 并分析了在学术文献中发表的22种如何实现这些属性的不同的相似性度量方法。

以上这些有关于业务流程相似性度量的研究，对于本文的研究有极强的指导和启示作用。

2 Metadata_based业务流程描述框架的构建

2.1 流程注册元模型框架

本节的研究工作基于武汉大学何克清教授、李昭副教授团队前期研究中研发的ISO国际标准[11]：流程注册元模型框架(metamodel framework for interoperability-part 5：metamodel for process model registration，MFI-5)，如图1所示。该国际标准的主要功用是通过具体的建模语言描述业务流程模型，然后从多个维度选取该模型中相关的业务流程元数据特征，并对所选元数据特征进行注册与管理。

图1 流程注册元模型框架(MFI-5)

在MFI-5中，流程模型(Process_Model)是一种元类，用于流程的描述，并在使用一个具体的流程建模语言(Process_Modelling_Language)时，描述所包含的流程模型元素(Process_Model_Element)。流程模型元素包括流程(Process)以及流程间的依赖关系(Dependency)。对于每一个流程模型元素，存在某些事件(Event)能够触发该流程模型元素，或者由该流程模型元素产生相应的事件。为了实现特定的业务目标，在执行一个流程模型元素时，会创建、使用或消耗相关的资源(Resource)。

依赖用于描述流程间的控制约束，并能够归为顺序依赖(Sequence_Dependency)、分支依赖(Split_Dependency)，以及联结依赖(Join_Dependency)。顺序依赖指明流程模型元素是按照一定的顺序执行的。分支依赖则指出当前驱的流程模型元素执行完后，将并行地执行一个或多个后继的流程模型元素。联结依赖指出当前驱的一个或多个流程模型元素执行完后，将开始执行后续的流程模型元素。分支依赖的类型用于为后继流程指明逻辑选择，同理，联结依赖的类型则为前驱流程指明逻辑选择。分支依赖类型以及联结依赖类型的值可以为异或(XOR)、或(OR)以及和(AND)。分支依赖类型XOR意味着有且仅一个后继流程模型元素允许执行，OR是指一个或多个后继流程模型元素允许执行，而AND指出所有后继流程模型元素必须执行。联结依赖类型XOR意味着当且仅当一个前驱的流程模型元素执行完成，后继的单个流程模型元素才可执行，OR是指当且仅当一个或多个前驱的流程模型元素执行完成，后继的单个流程模型元素才可执行，AND是指当且仅当全部的前驱流程模型元素执行完成，后继的单个流程模型元素才可执行。此外，在分支依赖类型的值确定以后，分支依赖选项(Split_Dependency_Option)表达了后继流程模型元素执行的安全条件。类似的，在联结依赖类型的值确定以后，联结依赖选项(Join_Dependency_Option)指明了前驱流程模型元素执行的安全条件。

2.2 基于BPDF构建业务流程相似性特征集

当前流程注册元模型框架(MFI-5)研究成果显著，但是其忽略了业务流程的顺序特性，导致在含有复杂结构，例如循环结构，并行结构等业务流程中缺少用于描述不同业务流程元素间执行顺序的特征。为了解决该问题并在实际应用中实现有效度量业务流程的目标，并作为以前工作[11]的扩展，我们通过研究流程注册元模型框架和业务流程的元层数据特征，基于MFI-5构建业务流程描述框架BPDF，这被证明比以前的适用性更有效用于描述业务流程执行顺序的有向性，以很好地体现业务流程典型的元数据特征。

图2 业务流程描述框架(BPDF)

业务流程描述框架(business process description framework，BPDF)是对业务流程的一种规范而形象化的数据描述。一个业务流程是一个由图形对象组成的有向网状图，可以用如下七元组表示

BP=(NL，R，E，α，β，γ，A)

其中，NL表示由L标号的业务活动节点(Process_Activity)的有限集合，N→L表示活动节点标号映射函数，标号主要用于区分每个流程活动节点，可用任意字符序列表示；R表示业务流程的执行实体资源(Resource)；E表示业务流程开始，结束，异常停止等特定情况(Event)；α表示业务流程的顺序依赖(Sequence_Dependency)，是流程活动节点间的控制约束，指明若一个前驱活动执行完毕，一个后继活动将开始执行；β表示业务流程的分支依赖(Split_Dependency)，是流程活动节点间的控制约束，指明若一个前驱流程执行完毕，一个或多个后继流程将开始执行，类型主要指and-split，or-split不同组合；γ表示业务流程的联结依赖(Join_Dependency)，是流程间的控制约束，指明若前驱的多个流程执行完毕，后继的一个流程将开始执行，and-join，or-join不同组合；A表示业务流程的关联关系(Association)，用于描述业务流程活动或任务间有向的关联关系。

为了便于对业务流程模型进行准确标识与量化，本文须采用上述7个元数据特征。元数据特征构成业务流程模型相似性特征集SFS，本文定义SFS内容如式(1)所示

(1)

相似性特征集(SFS)的成功定义为业务流程模型的描述提供了元数据支持，并为向量的相似性计算奠定了基础。

2.3 业务流程三层管理框架

业务流程的描述作为业务流程管理中的一项重要的工作，越来越多的研究人员因为研究工作的需要制定了自己的业务流程描述规则和管理框架。本文提出了一种业务流程“三层模式”的概念，并将业务流程应用划分为：业务流程描述层、业务流程管理层和业务流程应用层，如图3所示。这种“高内聚低耦合”业务流程管理框架，为后文的研究工作奠定了基础。

图3 业务流“三层”管理框架

该框架主要分为4个功能模块：业务流程描述、流程挖掘与存储、相似性度量、个性化推荐。模块内高度耦合而模块间高度松散。业务流程描述模块作为业务流程描述层的基础模型为其它模块提供辅助功能。业务流程挖掘与存储模块联系紧密，而个性化推荐模块通过原始流程模型和挖掘出来的模型的相似性来评估挖掘算法，是流程相似性度量的一个应用功能。

(1)业务流程描述层

业务流程描述层主要目的是对业务流程进行一个形象而规范的描述，该框架提出可以采用特定的建模语言，例如BPMN[12]、Petri Net[13]等，结合基于元数据的业务流程描述框架BPDF对业务流程进行描述，满足用户的特定目标需求。

(2)业务流程管理层

业务流程管理层主要目的是对业务流程挖掘、业务流程存储、业务流程相似性度量、业务流程个性化推荐等操行为进行管理和规范化说明。

(3)业务流程应用层

业务流程应用层整理归纳为以下几个方面：业务流程特征转换与提取、业务流程模型图像化展示、业务流程模型检索、业务流程变更、业务流程替换等，主要为业务流程的相关应用提供支撑。

3 业务流程相似性计算

3.1 流程模型的描述

基于业务流程三层管理框架可知，在业务流程相似性度量、业务流程挖掘、业务流程推荐等领域，选择一种合适的建模语言尤为重要，业内常用的建模语言有BPMN、Petri Net等。本文选择其抽象级别位于实际业务流程与MFI-5之间的业务流程建模标注语言(BPMN)作为业务流程建模语言。BPMN由于其具有图形化特征，尤其能描述多方参与的复杂应用场景，因此适合进行业务流程的描述。

首先对数据集中3个在线售货服务进行业务流程解释，以便于对其进行业务流程进行描述，并获得相应的图4中的业务流程BPMN模型，为业务流程BPMN模型的标识与量化奠定基础。

图4 在线售货服务BPMN模型

在Model 1(M1)中，用户首先执行“购买商品”，然后执行分支依赖中的“排他逻辑门”，流程将在所有输出分支中依据情境(条件)仅选取其中一个分支执行，即仅执行“获得商品”或仅执行联结依赖中的“相容逻辑门”。若选择执行“获得商品”，则依次执行分支依赖中的“并行逻辑门”、联结依赖中的“相容逻辑门”、“验证发票”、“储存商品”、联结依赖中的“并行逻辑门”，最后结束流程；若选择执行联结依赖中的“相容逻辑门”，则依次执行“验证发票”、联结依赖中的“并行逻辑门”，最后结束流程。

在Model 2(M2)中，用户首先执行“购买商品”，然后执行分支依赖中的“排他逻辑门”，流程将在所有输出分支中依据情境(条件)仅选取其中一个分支执行，即仅执行“获得商品”或仅执行联结依赖中的“排他逻辑门”。若选择执行“获得商品”，则依次执行联结依赖中的“排他逻辑门”、“储存商品”，最后结束流程；若选择执行联结依赖中的“排他逻辑门”，则执行“储存商品”并结束流程。

在Model 3(M3)中，用户依次执行“购买商品”、“获得商品”、分支依赖中的“并行逻辑门”、“验证发票”、“储存商品”、联结依赖中的“并行逻辑门”，最后结束流程。

此外，为进一步体现流程的直接参与者，并增强BPMN模型的可理解性，本文在BPMN模型中额外考虑模型的资源特征(Resource)，对BPMN模型的Resource进行描述。

3.2 业务流程BPMN模型的标识与量化

为了有效度量业务流程间的相似性，我们基于Metadata_based业务流程描述框架BPDF中元数据特征与BPMN图形化标识映射关系，见表1，具体的，基于元数据特征与业务流程BPMN模型的映射关系使用SFS对业务流程进行标识与量化，分别得到业务流程在7个元数据特征中的向量，为元数据特征向量的相似性计算奠定基础。

表1 元数据特征的图形化标识映射关系

本文中Metadata_based业务流程描述框架(BPDF)认为，对于业务流程描述、相似性度量以及业务流程推荐等应满足一些常见的特征性质。元数据特征1～元数据特征7是基于BPDF推理而得的业务流程元数据特征，业务流程BPMN模型的标识与量化结果见表2，具体的，7个业务流程模型元数据特征(Process_Activity，Resource，Event，Sequence_Dependency，Split_Dependency，Join_Depende-ncy，Association)的标识与向量化请参见文献[3]。

表2 业务流程元数据特征向量表示

3.3 基于元数据特征向量的流程相似性度量

业务流程元数据特征向量相似性计算是业务流程相似性度量的重要步骤，本文将业务流程间的相似性计算过程等价转换为计算两个业务流程在7个元数据特征的向量相似性，并进行综合考虑，从而得出两个业务流程间的相似性。

本文中，我们基于元数据特征构成流程相似性特征集(SFS)。基于SFS对BPMN模型进行标识和量化，以通过每个特征中向量的相似性确保BPMN模型的相似性。基于流程在7个特征中的向量，使用相似性度量算法计算任意两个业务流程在某一特征中向量的相似性，并充分考虑元数据特征权重，进而获取整体业务流程模型的相似性。

本文基于对经典相似性度量算法的研究，采用余弦相似度对业务流程集中任意两个BPMN模型在每一个元数据特征中向量的相似性进行计算。参考余弦相似度，定义式(2)对任意两个BPMN模型的元数据特征向量相似性进行计算

(2)

其中，MA和MB分别代表数据集MS中任意两个业务流程模型；MAi=(x1，x2，…，xn)、MBi=(y1，y2，…，yn) 分别代表MS中任意两个模型在第i个元数据特征中的n维向量，且i=1，2，3，4，5，6，7； Sim(MAi,MBi) 表示向量MAi与MBi间的相似性值，即任意两个业务流程模型在第i个元数据特征的相似性，其值域处于[0,1]的范围。

基于式(2)计算得到MS中任意两个业务流程BPMN模型的元数据特征中向量的相似性，结果见表3。

表3 BPMN模型在7个特征中向量的相似性

依据表3的计算结果并考虑7个元数据特征权重，进而根据式(3)获取两个BPMN模型的相似性

(3)

其中， Sim(MA,MB) 表示业务流程BPMN模型MA与MB间的相似性，w是根据向前逐步回归算法处理元层数据特征得到的权重。

为了更清晰地展示业务流程模型间的相似性，为业务流程的相似性进行分析提供支持，依据计算结果构建出BPMN模型的相似性表示矩阵(SM)。

业务流程模型相似性的成功获取为业务流程分析、讨论提供了支持，并为业务流程推荐奠定了基础。根据本文所提方法可以对流程库中的流程进行分级，并优先推荐相似性处于第一级的流程对故障流程进行替换或为故障流程的变更提供决策支持。

4 实验研究

4.1 实验数据准备

为了验证所提方法的有效性，本文利用实际的修车流程数据集进行了验证。我们将100个修车服务业务流程模型随机分成10组，然后从每一组数据中抽取3个业务流程模型得到拥有30个业务流程模型组成的测试数据集，对提出的方法进行实验实证。

4.2 实验实施

依据本文所提方法，首先利用BPMN对测试数据集中的30个业务流程进行描述，随机选取10个业务流程模型组成实验数据集MS

MS={TM1,TM2,TM3，…，TM10}

其次，输入MS，依据业务流程相似性特征集(SFS)，对MS中任意业务流程BPMN模型的每个元数据特征进行标识与量化，得到每个BPMN模型在每个元数据特征中的向量。最后，输入得到的元数据特征向量，依据式(3)计算出MS中任意两个修车业务流程的相似性，并获取相似性矩阵，如图5所示。

图5 测试集流程相似性矩阵

4.3 实验结果分析

基于实验数据集MS的相似性矩阵SM可知，以TM1为例，TM1于实验数据集MS中其它业务流程BPMN模型的相似性分别为：TM1与TM2为0.73，TM1与TM3为0.70，TM1与TM4为0.60，TM1与TM5为0.48，TM1与TM6为0.66，TM1与TM7为0.61，TM1与TM8为0.45，TM1与TM9为0.62，TM1与TM10为0.79。数据表明TM1与自身的相似性最高，TM1与TM10的相似性较高，TM1与TM8的相似性最低。

为了研究本文所提流程相似性度量方法的效果，选取了结构、文本和行为特征与本文针对汽车修理实际应用的业务流程进行相似性计算，结果如图6所示。

图6 测试集流程实例特征相似性图

在图6中示例的3个元数据特征中，我们可以直观地发现，若仅仅以第三个特征(Event)度量业务流程显然不符合客观实际。第一个特征(Process_Activity)和第二个特征(Resource)在行为和结构上更符合直观感受，但是较于图5中的实验结果误差较大。从业务流程相似性和业务流程特征相似性的对比中可以发现，基于BPDF使用SFS度量业务流程得到的结果更科学，更符合直观感受，更能全面地刻画业务流程。实验结果表明，本文提出的方法对于业务流程相似性度量具有有效性，较于传统单一维度，能够更好地体现业务流程的典型特征，提高了业务流程相似性度量的准确性。

为了给业务流程推荐提供有效的决策支持[14,15]，并在一定程度降低业务流程推荐的难度，我们基于业务流程相似性计算结果进行分级处理，将业务流程的相似性按其值域[0，1]划分为4个级别：[0，0.3)，[0.3，0.6)，[0.6，0.8)和[0.8，1]，即，如果业务流程间相似性属于[0，0.3)，则将其视为较低的相似性(第四级)，[0.3，0.6)视为中等相似性(第三级)，[0.6，0.8)视为较高的相似性(第二级)，[0.8，1] 视为高相似性(第一级)。

基于测试数据集中30个业务流程相似性进行分级，以TM1为例，其相似性从高到低依次是：[TM10，TM25，TM2，TM11，TM3，TM6，TM22，TM12，TM9，TM24，TM7，TM13，TM15，TM19，TM30，TM4，TM21，TM29，TM5，TM14，TM28，TM8，TM20，TM16，TM23，TM18，TM17，TM27，TM26]，没有处于[0.8，1]值域(第一级)的业务流程；处于[0.6，0.8)值域(第二级)的是[TM10，TM25，TM2，TM11，TM3，TM6，TM22，TM12，TM9，TM24，TM7，TM13，TM15，TM19，TM30，TM4，TM21]；处于[0.3，0.6)值域(第三级)的是[TM29，TM5，TM14，TM28，TM8，TM20，TM16，TM23，TM18，TM17，TM27]；处于[0，0.3)值域(第四级)的是[TM26]。

随着业务需求市场因素的改变，业务流程也会发生改变，为了适应这种变化，根据业务流程的相似性分级，可以为业务流程的变更与推荐提供决策支持。若其处于第一级，可以基于第一级中的业务流程模型有效地进行业务流程间相似性组件的替换与集成；同时，也可以在当前业务流程失效或工作异常的情况下，优先推荐相似性处于第一级的流程作为替代流程为故障流程的变更提供决策支持。