基于邻接矩阵的业务流程间距离计算方法

吴亚锋,,2

(1.南京航空航天大学 计算机科学与技术学院,南京 211106;2.上海第二工业大学 计算机与信息工程学院,上海 201209)

0 概述

随着业务流程管理技术的不断发展,企业应用的各类信息管理系统越来越多,如人力资源管理系统、供应链管理系统、企业资源计划系统等。记录企业运行的数据信息以事件日志的形式保存在这些信息管理系统中[1],这些保存下来的数据信息蕴藏着企业运行的具体执行过程,具有重大的商业价值。如何利用好保存下来的数据信息,是企业面临的重要问题。

关于业务流程间距离的计算问题,即业务流程相似度的计算,一直是企业界和学术界共同关心的热点问题。但现有流程相似度计算方法多数仅考虑流程模型本身所蕴含的信息,忽视了保存在信息系统中事件日志的重要作用。针对该问题,本文基于信息管理系统保存的事件日志提取活动轨迹,利用文献[2]提出的变迁紧邻关系,通过遍历事件日志中的活动轨迹寻找两两活动之间存在的紧邻活动关系,利用此关系的组合构造邻接矩阵,并将其结合事件日志中案例轨迹发生的总次数得到概率邻接矩阵,最后以矩阵间的距离表示业务流程间的距离。

1 相关工作

现有的业务流程相似度计算方法都是从业务流程模型本身出发,主要可以分为3类:1)文本内容相似度计算;2)流程模型结构相似度计算;3)流程行为相似度计算。

文本内容相似度计算主要从节点的语法、语义、属性、类型和节点上下文进行计算[3-5],这类方法计算简单、快捷,只需计算节点对应标签文本的相似度。然而,当流程模型的结构发生改变影响流程间相似度时,该类方法却无法捕获,因此,其准确性不高。

现有流程结构相似度计算方法大多通过计算流程拓扑结构的相似度,基于图编辑距离[6]或树编辑距离[7]计算流程结构相似度。首先通过某种编辑距离来计算流程拓扑结构的相似度;然后使用流程拓扑结构的相似度表示流程结构相似度。流程模型的拓扑结构反映了不同业务逻辑单元之间的逻辑关系,如顺序、选择、并行和循环等。

关于流程行为相似度的计算,早期的方法主要集中于流程等价方面,如轨迹等价[8]、互模拟等价[9]。然而这些方法只能得到等价与非等价结果,无法求出流程行为相似度的具体数值,因此,在大多数实际应用中是无效的。现有计算结果较好的流程行为相似度计算方法有变迁紧邻关系法、行为轮廓法、主变迁序列法和因果足迹法。

文献[2]提出了一种称为变迁紧邻关系(Transition Adjacent Relation,TAR)算法的流程相似性度量方法。该方法以Petri网为建模基础,通过计算流程变迁之间的两两紧邻关系来构造TAR集合,最后以2个TAR集合之间的Jaccard系数表示2个流程的相似度。文献[10]在TAR算法的基础上提出TAR++算法,其在具有紧邻关系的任务之间增加一个重要性系数,再使用带重要性系数的任务紧邻关系集合的相似度表示流程行为的相似度。

文献[11-12]提出了一种称为行为轮廓(Behavioral Profile,BP)算法的流程行为相似性计算方法,其对TAR中的紧邻关系进行扩充,允许将流程变迁之间的非紧邻关系定义为一种弱关系,从而将变迁关系细化,具体包含严格顺序关系、交错顺序关系和互斥关系等。但是该方法无法有效处理不可见任务,也不能区分循环结构和并发结构。

文献[13]提出一种称为主变迁序列(Principal Transition Sequence,PTS)算法的流程行为相似性度量方法,该方法给出了主变迁序列的概念,通过3种不同的主变迁序列表示3种不同的逻辑结构。使用这3种主变迁序列来表示流程模型的行为,2个序列的相似度为这2个序列的最长公共子序列长度和这2个序列中最长序列长度的比值,最后将不同类型的序列相似度加权求和所得值作为流程的相似度。但是该方法不能有效处理循环结构,同时也破坏了流程模型的语义完整性。文献[14]在PTS算法的基础上提出了PTS++算法,通过定义完整触发序列表示流程行为,基于A*算法结合剪枝策略实现触发序列集合间的映射,进而完成流程行为相似度的计算。

文献[15]提出一种称为因果足迹(Causal Footprint,CF)算法的流程行为相似度计算方法。该方法使用模型中的活动、路由、前向连接链、后向连接链等将流程模型表示为一个向量,并利用2个向量间的夹角余弦值表示2个流程间的相似度。但该方法无法有效区分AND、XOR等路由结构,且计算效率较低。

本文首先介绍有关事件日志的基本概念,给出从事件日志的执行案例轨迹中构造邻接矩阵的方法;然后借鉴矩阵论中矩阵范数的概念定义流程间距离,证明所定义的流程间距离满足距离度量的2个特性;最后将文献[2]中使用的业务流程实例模型利用事件日志产生工具(Process Log Generator,PLG)[16]生成人工事件日志,通过对比实验证明本文所提方法的有效区分性,同时利用真实事件日志数据集对其时间性能进行分析。

2 事件日志

目前事件日志的数据源多种多样,如数据库、文本文件、消息日志、事务日志等。这些保存下来的事件日志信息为科学研究和企业生产实践提供了大量的数据来源。从信息系统的角度来看,事件日志反映了业务流程在实际运行中的真实执行情况。事件日志具有时间戳、成本、资源和活动等相关信息。

表1是一个关于网上购物的索赔申请处理过程,每个索赔申请对应于一个案例。事件可能与某些活动有关,其中活动指register request、check ticket、reject等。由表1可以看出:1)案例是由事件组成的,且每个事件仅属于一个案例;2)案例中的事件是有序的;3)事件具有属性,典型的属性包括活动、时间戳、成本和资源等。

表1 网上购物索赔申请处理过程

定义1(事件、属性) 设E为事件空间,即所有可能的事件标识的集合。事件可以由不同的属性来表示。设AN为属性名的集合。对于任意的事件e∈E和属性名n∈AN,#n(e)是事件e的属性n的值。

例:表1中一个事件(事件ID为110)有一个与活动#activity(e)=(register request)相对应的时间戳#time(e)=(2015-12-22 10∶19∶16),被一个特定的人#person(e)=(Pete)所执行,有相关的成本#cost(e)=(50)等。

定义2(分类器) 对任意的事件e∈E,e是事件的名称,将e称为事件的分类器。

定义3(轨迹) 轨迹t是事件e的一个有限序列。

定义4(案例) 设C为案例空间,即所有可能的案例标识符的集合。每一个案例都有一个强制性的属性——轨迹。

例:表1中案例1的轨迹为{110,111,112,113,114},案例2的轨迹为{200,201,202,203,204}。

如果使用事件的活动名称来表示事件,那么e=#activity(e)。

定义5(事件日志) 事件日志是案例的集合。

例:表1表示的事件日志为{案例1,案例2,…}。

定义6(简单轨迹) 简单轨迹t被定义为活动的有限序列。

例:表1中案例1对应的简单轨迹t1为{register request,examine thoroughly,check ticket,decide,reject request}。

定义7(简单事件日志) 令A为活动名称的集合。简单轨迹t被定义为一个活动的序列,即t∈A*。简单事件日志L被定义为A上轨迹的一个多集。

例:表1对应的简单事件日志为L={register request,examine thoroughly,check ticket,decide,reject request},{register request,check ticket,examine casually,decide,pay compensation},…},其中一个简单轨迹t={register request,examine thoroughly,check ticket,decide,reject request}。

定义8(从事件日志提取简单事件日志) 设L是定义5中定义的事件日志,假设存在一个分类器,e是事件的名称,则使用这个分类器可以将L中的案例序列转换成活动名称序列。

事件日志的来源和格式多种多样,有关事件日志的更多知识可以参考文献[17]。

3 邻接矩阵构造

事件日志中保存着业务流程运行过程产生的丰富信息,反映流程的特征。然而,在业务流程的实际运行过程中可能会出现流程执行异常或日志记录错误的情况,日志数据中往往存在一些噪声,因此,如何对保存在事件日志中的信息进行有效的提取与分析是本文需要解决的关键问题之一。现有研究已经证实噪声的特点是发生概率低。因此,本文利用噪声的这一特点首先对事件日志进行预处理,删除发生率小于给定阈值的案例轨迹,然后再进行邻接矩阵的构造。以文献[1]中使用的2个简单事件日志为例,详细介绍紧邻活动关系和活动邻接矩阵的构造。

表2所示的简单事件日志中共有5个不同的活动、6个案例轨迹,例如有2个案例的简单轨迹为。表3所示的简单事件日志中共有6个不同的活动、13个案例轨迹,例如有3个案例的简单轨迹为。

表2 简单事件日志数据表L1

表3 简单事件日志数据表L2

3.1 预处理

由于事件日志中可能存在噪声,因此在构造邻接矩阵之前需要对简单事件日志进行预处理,即删除案例轨迹的发生率小于给定阈值的轨迹,从而降低噪声对计算结果的影响。事件日志的预处理包括以下2个部分:1)求出2个事件日志中相同活动的比例;2)求出事件日志中每条轨迹所占的比率。

表4 预处理后的简单事件日志数据表L2

3.2 邻接矩阵构造过程

邻接矩阵构造是根据事件日志中的活动紧邻关系进行的。因此,在介绍邻接矩阵构造之前,首先给出紧邻活动与邻接矩阵的定义。

定义11(紧邻活动) 设L为简单事件日志,A为活动集合,活动a,b∈A,a、b是紧邻活动当且仅当简单事件日志L中存在有简单轨迹t=t1,t2,…,tn,使得ti=a,ti+1=b,其中i∈{1,2,…,n-1}。

例:表2所示的案例1中紧邻活动关系有a1a2、a2a3、a3a4。

定义12(邻接矩阵) 以紧邻活动在事件日志的所有简单轨迹中出现次数的总和作为元素的矩阵称为邻接矩阵(Adjacent Matrix,AM)。

对于任意给定的事件日志,可以按照如下方法为其构造邻接矩阵:对于一个包含有N个不同活动的事件日志,首先初始化一个N×N的方阵,其中,N表示事件日志中不同类型活动的数量,例如表2所示的事件日志中共包含有5个不同的活动a1、a2、a3、a4、a5,因此,表2所示的事件日志对应于一个5×5的邻接矩阵。对于事件日志中的任意2个活动ai和aj,依次遍历事件日志中的每条轨迹,求出活动ai和aj在简单事件日志中所有简单轨迹中紧邻出现的总次数,假设为n,,那么在邻接矩阵中AM(i,j)所对应的位置填入n,即AM(i,j)=n,如果活动ai和aj没有作为紧邻活动在简单事件日志中出现过,则邻接矩阵的相应位置填入0。为了表示简单,本文对于邻接矩阵中0元素的所在位置留有空白表示。

将表2和表4中的事件日志进行邻接矩阵的构造,所求出的邻接矩阵如图1和图2所示。

图1 L1预处理后所对应的邻接矩阵

图2 L2预处理后所对应的邻接矩阵

定义13(概率邻接矩阵) 由邻接矩阵中的每个元素除以事件日志中案例轨迹的总数所得到的矩阵,称为概率邻接矩阵。

图3 L1预处理后所对应的概率邻接矩阵

图4 L2预处理后所对应的概率邻接矩阵

4 流程间距离计算

流程间距离的计算分为定性分析和定量计算,所谓定性分析就是对2个事件日志中的活动集合求取相同活动率,若所求的相同活动率较小,则说明所对应的流程间距离较大;若所求的相同活动率较大,则说明所对应的流程间距离较小。所谓流程间距离的定量计算就是指利用一种数值化的方法来度量流程间距离的具体大小。

定义14(同维概率邻接矩阵) 设L1和L2为2个事件日志,A1和A2为对应事件日志L1和L2的活动集合,AM1和AM2为事件日志L1和L2所对应的概率邻接矩阵,NAM1和NAM2表示同维概率邻接矩阵,其维数m=|A1∪A2|,假设A1∪A2={a1,a2,…,am},则NAM1(i,j)和NAM2(i,j)可以进行如下的定义:

根据定义14所给的同维概率邻接矩阵的定义,可以给出表2和表4所示的事件日志L1和L2所对应的同维概率邻接矩阵,分别如图5和图4所示(简单事件日志L2的同维概率邻接矩阵同图4)。

图5 简单事件日志L1的同维概率邻接矩阵

在矩阵论中,矩阵间距离的度量可以使用矩阵范数进行表示,因此,本文给出流程间距离的定义。

定义15(流程间距离) 设Li、Lj为任意2个事件日志,NAMi、NAMj为其对应的同维概率邻接矩阵,事件日志Li、Lj所对应的流程间距离D(Li,Lj)定义如下:

D(Li,Lj)=tr[(NAMi-NAMj)×(NAMi-NAMj)T]

定理1任意给定3个简单事件日志L1、L2和L3,流程间距离D满足以下性质:

1)非负性:D(L1,L2)≥0,当且仅当L1=L2成立时,有D(L1,L2)=0。

2)对称性:D(L1,L2)=D(L2,L1)。

3)三角不等式:D(L1,L2)≤D(L1,L3)+D(L3,L2)。

证明:

1)由流程间距离的定义可知D(L1,L2)≥0,若D(L1,L2)=0,则说明NAM1-NAM2是零矩阵,从而得NAM1=NAM2,即L1=L2,反之亦然。

2)由事件日志L1和L2的流程间距离的定义可得:

D(L1,L2)=

tr[(NAM1-NAM2)×(NAM1-NAM2)T]=

tr[(NAM2-NAM1)×(NAM2-NAM1)T]=

D(L2,L1)

3)由事件日志L1和L2的流程间距离的定义可得:

D(L1,L2)=

tr[(NAM1-NAM2)×(NAM1-NAM2)T]=

NAM3(i,j)-NAM2(i,j)}2≤

tr[(NAM1-NAM3)×(NAM1-NAM3)T]+

tr[(NAM3-NAM2)×(NAM3-NAM2)T]=

D(L1,L3)+D(L3,L2)

证毕。

5 验证实验

本节首先使用人工生成的事件日志进行对比实验,对本文方法进行可行性验证,然后,利用真实事件日志数据集对本文方法的执行效率进行实验分析。本文实验环境为:Inter(R) Core(TM)i5-6420P CPU @2.80 GHz 8 GB内存。实验程序使用Java语言编写,JDK版本为1.7.0,运行在64位Windows7系统上。

5.1 实例验证

首先使用事件日志产生工具(PLG)进行人工事件日志的生成。本文使用文献[2]所给的4个流程模型进行人工事件日志的生成,所用流程模型如图6所示。

图6 流程模型实例

使用PLG分别执行图1所示的4个业务流程模型,每个业务流程模型执行50次,即使得生成的4个人工事件日志为分别包含50条案例轨迹的简单事件日志,所生成的4个事件日志分别为:{25,25};{25,25};{20,30};{15,15,5,5,5,5}。

本文所构造的邻接矩阵和文献[2]使用的TAR集合都是通过活动邻接关系构造的,但是TAR算法仅考虑了变迁之间的紧邻关系,属于流程模型的局部行为特征,因而不能有效地识别出非自主选择结构,同时也无法区分流程模型中存在的循环结构和顺序结构。且TAR算法仅考虑了流程模型本身所蕴含的信息,而忽视了保存在信息系统中事件日志的有效应用。因此,将本文方法与TAR方法进行比较,从而证明本文方法能够更好地区分选择结构和并行结构,同时可以发现不可见任务。

由图7可知,流程模型N2和N3的距离为0,则说明流程模型N2和N3应该相同,但笔者发现模型N2为选择分支结构,流程模型N3为并行分支结构,这两个流程模型并不相同,但是它们的执行轨迹相同,形成的TAR集合也相同。因此,说明TAR不能有效地区分选择分支结构和并行分支结构。

图7 基于TAR算法的流程间距离

由图8可知,流程模型N2和N3的距离为0.06,则说明流程模型N2和N3是不相同的,这说明即使2个流程模型的执行轨迹相同,但其对应的流程模型仍有可能是不同的。因此,基于邻接矩阵的流程间距离计算方法可以有效地区分选择分支结构和并行分支结构。同时,笔者发现流程N1和N4的距离只有0.04,相较TAR算法求出的0.5小很多,这是因为不可见任务在真实的执行过程中出现的次数较少,因此,可以在预处理阶段设置一个较大的阈值将其过滤掉。如果轨迹发生率的阈值设置的大一点,则N1和N4的距离为0,会把不可见任务当成噪声去掉。

图8 基于邻接矩阵的流程间距离

5.2 效率分析

影响本文方法执行效率的2个关键因素分别是事件日志中每条案例轨迹的长度以及事件日志中案例轨迹的个数。因此,本节分别从这2个因素对流程间距离计算所花时间进行验证。本节实验所使用的数据来自https://data.4tu.nl保存的真实数据集,从中选择了4类事件日志数据,分别是:Hospital Log,Sepsis Cases,Road Traffic和BPIC 2012。所挑选的事件日志具体细节如表5所示。

表5 事件日志数据集

从所选的4个事件日志中,分别将每个事件日志形成新的4类事件日志,形成的事件日志中的案例轨迹数分别为5、10、15和20。每类中的轨迹长度从5增加到20。笔者观察在轨迹数一定的情况下,随着轨迹长度的增加,计算所花时间的变化情况。

图9中的每条曲线表示,在轨迹数一定的情况下,随着轨迹长度的增加,计算所花的时间也随之增加。增加的幅度和事件日志的案例轨迹数有关,事件日志的案例轨迹数越大,增加的幅度也越大。例如当轨迹数为20时,随着轨迹长度从5增加到20,计算所花时间由92.1 ms增加到了780.4 ms,增加的幅度分别为200.4%、201.4%和209.8%。在图9所示的不同曲线之间,笔者发现在轨迹长度一定的情况下,事件日志中的案例轨迹数越大,计算所需的时间也就越多。

图9 实验结果

6 结束语

现有的流程间距离计算方法大多从流程模型本身入手,而忽略了流程模型实际执行产生的事件日志。本文依据流程模型实际执行产生的事件日志来计算流程间距离,通过挖掘流程执行产生的案例轨迹中包含的活动紧邻关系构造活动邻接矩阵,同时使用矩阵论中矩阵范数的定义表示矩阵间的距离,利用所求得的矩阵间距离来定义流程间距离,并证明所定义的流程间距离满足距离度量的性质。实验结果表明,本文算法具有有效区分性,并且计算效率较高。下一步将提升邻接矩阵构造算法的效率,并设计更合理的预处理参数阈值。

[1] AALST W M P V D,SCHONENBERG M H,SONG M.Time prediction based on process mining[J].Information Systems,2011,36(2):450-475.

[2] ZHA H,WANG J,WEN L,et al.A workflow net similarity measure based on transition adjacency relations[J].Computers in Industry,2010,61(5):463-471.

[3] AKKIRAJU R,IVAN A.Discovering business process similarities:an empirical study with SAP best practice business processes[C]//Proceedings of ICSOC’10.San Francisco,USA:[s.n.],2010:515-526.

[4] YAN Z,DIJKMAN R,GREFEN P.Fast business process similarity search with feature-based similarity estima-tion[C]//Proceedings of OTM’10.Berlin,Germany:Springer,2010:60-77.

[5] 宋有美,李建波,和天玥,等.基于节点相似性的容迟网络概率路由算法[J].计算机工程,2016,42(9):63-70.

[6] DIJKMAN R,DUMAS M.Graph matching algorithms for business process model similarity search[C]//Proceedings of BPM’09.Berlin,Germany:Springer,2009:835-842.

[7] KUNZE M,WESKE M.M.Metric trees for efficient similarity search in large process model repositories[C]//Proceedings of BPM’10.Berlin,Germany:Springer,2010:535-546.

[8] POMELLO L,ROZENBERG G,SIMONE C.A survey of equivalence notions for net based systems[M]//ROZENBERG G.Advances in Petri Nets.Berlin,Germany:Springer,1992:410-472.

[9] GLABBEEK R J V,WEIJLAND W P.Branching time and abstraction in bisimulation semantics(extended abstract)[J].Journal of the ACM,1991,43(3):555-600.

[10] 殷 明,闻立杰,王建民,等.基于变迁紧邻关系重要性的流程相似性算法[J].计算机集成制造系统,2015,21(2):344-358.

[11] WEIDLICH M,MENDLING J,WESKE M.Efficient consistency measurement based on behavioural profiles of process models[J].IEEE Transactions on Software Engineering,2011,37(3):410-429.

[12] WEIDLICH M,POLYVYANYY A,MENDLING J,et al.Efficient computation of causal behavioural profiles using structural decomposition[M]//LILIUS J,PENCZEK W.Applications and Theory of Petri Nets.Berlin,Germany:Springer,2010:77-685.

[13] WANG J,HE T,WEN L,et al.A behavioral similarity measure between labeled petri nets based on principal transition sequences[C]//Proceedings of OTM’10.Berlin,Germany:Springer,2010:394-401.

[14] 董子禾,闻立杰,黄浩未,等.基于触发序列集合的过程模型行为相似性算法[J].软件学报,2015,26(3):449-459.

[15] DIJKMAN R,DUMAS M,DONGEN B V,et al.Similarity of business process models:metrics and evaluation[J].Information Systems,2011,36(2):498-516.

[16] BURATTIN A,SPERDUTI A.PLG:a framework for the generation of business process models and their execution logs[C]//Proceedings of BPM’10.Berlin,Germany:Springer,2011:214-219.

[17] WIL V D A.Process mining:data science in action[M].Berlin,Germany:Springer,2016.