基于完全前缀展开的业务过程模型结构化简与行为保持方法
2022-12-05王基书汤雅惠吕昌龙
黄 月，朱 锐，李 彤，王基书，汤雅惠 ，吕昌龙
(1.山东大学 软件学院，山东 济南 250101；2.云南大学 软件学院，云南 昆明 650091；3.云南省软件工程重点实验室，云南 昆明 650091；4.云南农业大学 大数据学院，云南 昆明 650201)
0 引言
伴随着当前全球产业结构由“工业型经济”向“服务型经济”的加速转型，智能制造作为“中国制造2025”的主攻方向，其中涉及到的“柔性制造”和“去中心化”对于过程控制技术的挑战更是全方面的。因此，过程驱动的业务过程管理(Business Process Management，BPM)[1]在当前生产开发中的作用日益凸显。BPM是一套利用过程管理、服务计算、数据挖掘以及工作流等技术来整合、分析、控制与改进企业各种业务环节的全方位管理模式。在实践中，企业已经针对不同的业务场景建立了各种各样的业务过程模型，然而复杂的业务过程模型常面临着如下问题：
(1)过程模型固有的复杂性。在过程挖掘领域，过程模型复杂性长期困扰着相关从业人员。特别是在实践中业务过程模型往往会出现模型节点过多、行为难以分析的问题。例如荷兰一家信息通信技术企业的实施软件变更管理系统的日志包含案例数达4万个，其中事件数达37万[2]。面对如此庞大的过程模型，模型往往会呈现出一种“意大利面式”的复杂结构[3]。
(2)复杂的业务过程模型通常可能包含大量错误信息，而这些错误信息会对模型分析和控制带来负面影响。例如死锁和活锁[4]，前者会导致模型停止执行并停止与环境的交互，而后者可能会继续工作，但模型永远无法执行完毕。因此，对业务过程模型进行验证，发现其中存在的问题十分必要。
(3)当业务过程模型十分庞大时，即使不包含复杂结构，用户要理解其不同业务活动的结构关系仍然十分困难。因此，对一些庞大的业务过程模型进行抽象化，有利于用户理解总体业务过程。当一个过程模型中的节点数达到数百乃至数千时，用户要理解其图形结构就已经很困难了，更不用说理解其中复杂的行为语义信息。事实上，用户很难去理解一个元素数超过60的过程模型[5]。
在实际的工业应用中，为了克服这些因素，需要通过简化业务过程模型消除模型中的冗余，得到一个关于复杂业务过程模型的“简单视图”，即业务过程模型抽象(Business Process Model Abstraction，BPMA)[6]。通过BPMA降低业务过程模型的复杂性，不仅有利于用户对过程模型的快速理解，更有利于大规模业务过程分析以及提高自动建模质量。
为了有效地提高此类复杂业务过程模型的可理解性，本文提出一种基于完全前缀展开的业务过程模型结构化简算法，该算法利用完全前缀展开技术分析业务过程模型中的行为，使用过程树简洁直观地表示模型行为，再根据过程树中的行为和语义重构业务模型。最后通过实验表明，该算法不但具有正确性和可行性，并且有效降低了业务过程模型的复杂度。
1 问题背景
对业务过程而言，常用的形式化建模工具主要有工作流[7]、进程代数[8]、自动机[9]、Petri网等。其中，Petri网[5]具有精确的数学形式定义，能够描述真发[10]，并且具有图形化描述以及严格的执行语义[11]，是当前以图形方式描述并发性的最常用形式化工具。因此，本文研究将采用Petri网作为业务过程模型的描述工具。
目前，实践中业务过程模型却呈现海量特征、模型节点过多、行为难以分析等问题。针对此类规模庞大且结构复杂的业务过程模型，如何有效地提高其可理解性是亟待解决的问题。当前针对该问题的解决方法主要有模型频繁行为模式发现[12-14]和精简模型结构[15-19]等。
其中，模型频繁行为模式发现的核心思想是保留日志中具有代表性的关键路径，除去一些噪声和非频繁日志带来的低频次行为依赖，从而简化了模型的规模。这种方法能够有效地保留模型中发生次数较多的行为，但也可能去掉非频繁的关键行为。文献[20]根据故障和修复过程理论分析了位置之间的相互作用和过渡点火率函数，并简化了随机Petri网，该方法不适用于复杂模型的简化，因为它需要研究每个位置与模型其余部分的相互作用。
精简模型结构主要强调从细粒度的过程模型中发现高层次的粗粒度的模型结构，常用的技术包括模型优化[15-17]、模型整合[18]、日志聚类[19]等。精简模型结构方面，文献[21]提出一种结构化的过程，并简化了该过程中对称系统的行为，但是该简化方法仅适用于对称系统的行为。文献[22]提出一种向弧添加时间属性的延迟，从而简化了过程，同时保留了调度和死锁属性。文献[23]提出了4种性能等效公式来简化通用模型结构的过程。文献[24-25]中利用搜索树和模型的行为轮廓得到变迁关联搜索树，从而实现模型的抽象化简。
无论是频繁行为模式发现，还是对模型结构进行精简，在一定程度上都会对模型的行为造成损失。这就使得一些对模型质量要求较高的领域，无法容忍模型行为损失的关键过程，例如软件开发版本的重要分支过程、交通事故的保险理赔过程等，这些分支过程虽然在整个业务过程中极少出现，但尤为重要[26]，而当前的模型化简算法，无法在保持行为的同时提高此类复杂业务过程模型的可理解性。
针对上述问题，本文将聚焦在保持行为的条件下如何化简业务过程模型。换而言之，即在除去业务过程模型的复杂结构的同时保留模型行为。以此来降低“意大利面式”复杂结构所引起的模型不易理解问题。如图1所示为在保持行为的条件下化简具有复杂结构的业务过程模型的案例，仔细分析可以看出，化简前后模型中活动的行为未改变，但是模型结构的复杂度被大幅降低了。
为了在保持模型行为的同时化简模型的复杂结构，本文采用过程树[27-28]对模型行为进行抽象。过程树是一种包含了过程模型信息的树形结构图，过程树不仅有对应的健全模型表示，还支持基本的控制流模式[29]。过程树中任意两个活动(叶子节点)的关系即它们最近的公共父亲节点。图1中的业务过程模型所对应的行为等价过程树为∝(→(→(×(A,B),×(C,D)),→(×(E,F),G)),→(∝(H,→(K,J)),I))。
尽管图1中的业务过程模型存在对应的行为等价过程树，但是当前对于过程树转化的算法只能针对基于块结构的过程模型[31-33](Block-Structured Process Model，BSPM)，具体见定义2,与过程树的行为等价的过程模型[30](process Tree in behavior Equivalent’s Process Model，TEPM)，具体见定义4,是可以转化为行为等价过程树的模型。TEPM与BSPM的关系如图2 所示。因此，本文提出一种可以判断TEPM行为的算法，从而在不损失行为的情况下化简业务过程模型。综合上述内容，本文的研究内容及贡献主要集中在以下方面：
(1)本文提出一种行为判断方法，该方法不仅可以支持基于基本块的过程模型BSPM中简单的活动关系判断，还可以判断具有复杂结构的过程模型活动关系(例如图1)。其次定义相应的可合并的关系判断条件，可以选出抽象后不影响活动的行为进行合并。通过不断循环这些操作，最终抽象出模型中的TEPM结构。
(2)本文提出一种基于完全前缀展开的业务过程模型结构化简与行为保持的算法，该算法通过活动关系构造过程树，根据过程树与过程模型之间的映射，对模型结构进行化简。
(3)该算法考虑了业务过程模型的复杂结构的化简问题，能真正应用到业务过程模型的化简之中，具有一定实用性。在保持模型行为的同时消除多余的模型结构，利于增加模型设计的弹性，提高业务过程的执行效率。
2 预备知识
2.1 过程模型和过程树
定义1业务过程模型。业务过程模型p是一个四元组，p=(C,A;F,M0)，其中：C是条件的有穷集合，A是活动的有穷集合；F⊆C×A∪A×C，F是p上的流关系；M0⊆C，M0作为p的初始情态。
本文使用Petri网系统来表示业务过程模型，Petri网的其他相关概念请参阅文献[34-35]。
定义2基于块结构的过程模型BSPM[31-33]。设s为一个过程片段，s可以使用基本块和有限次地活动重构(具体请参阅文献[31-33])操作得到s，则将该过程片段s称为BSPM。基本块具体如图3所示，其中黑色的活动表示内部活动，它不会产生其他任何外部行为。
定义3复杂结构。设s为一个过程片段，无法使用基本块和有限次地活动重构(具体请参阅文献[28-30])操作得到s，则将该过程片段s称为复杂结构。
定义4过程模型的行为空间[30]。设p=(C,A;F,M0)是一个过程模型，设σ⊆A*为过程模型p上的一个变迁序列，则p上所有可能发生的变迁序列的集合称为p行为空间，记为(p)，则σ∈(p)。
定义5与过程树行为等价的过程模型TEPM[30]。一个四元组p=(C,A;F,M0)被称作一个TEPM，当且仅当存在一个过程树模型t，使得p与t之间满足：①不存在σ使得σ∈(p)∧σ(t)；②不存在σ使得σ∈(t)∧σ(p)。
其中:σ表示过程模型p或者过程树t的一个变迁序列;p和t行为等价，即过程模型p中所有出现的变迁序列一定会在过程树t中出现，反之亦然。TEPM包含所有BSPM模型和一部分具有复杂结构的模型，这两部分模型都有对应的行为等价过程树，换而言之，有对应行为等价过程树的过程模型就是TEPM。
定义6过程树[27]。对于一个过程模型p=(C,A;F,M0)，A为其活动集，则活动a∈A为一个过程树；设M1,M2,…Mn(n>0)为n个过程树，过程树间关系符号记为◎，则◎(M1,M2,…Mn)为过程树。
本文中使用顺序(→)，选择(×)，并发(||)，迭代(∝)共4种关系符号，不同结构对应的结构如图3所示，使用符号◎表示括号内的活动关系。
2.2 完全前缀展开
为分析对业务过程模型的行为，本文采用了ESPARZA[36]提出完全前缀展开的方法，该方法与传统的可达树或者可达图不同。完全前缀展开可以将过程模型展开为一个包含截断事件的分支进程，从而避免可达树或者可达图中面临的状态空间爆炸问题。下面对该技术中一些基本概念进行说明，更多相关介绍详见文献[36]。
定义8分支进程。对于一个过程模型p=(C,A;F,M0)，其分支进程是一个二元组Π=(o,h)，其中o=(S,T;F′)是一个出现网，h是一个从(S,T;F′)到(C,A;F)的映射，其中：①h(P)⊆C，h(T)⊆A，h(F′)⊆F；②Min(o)与M0是双射关系，Min(o)表示出现网o中根据适当偏序关系得到的最小元素集合；③∀t1,t2∈T，且t1,t2满足·t1=·t2∧h(t1)=h(t2)，则t1=t2。
定义10适当偏序关系。一个出现网o=(P,T;G)的适当偏序关系是本地配置之间的关系，用<·表示适当偏序关系，其中：①<·是对⊂的改进，即∀t,t′∈T有[t]⊂[t′]，则[t]<·[t′]；②<·通过有限扩展得到保留，即∀t,t′∈T有[t]<·[t′]和Mark(t)=Mark(t′)，则对于[t]的有穷扩展[t]⨁E，存在同构变换I，使[t]⨁E<·[t′]⨁I(E)。
定义11割集。一个出现网o=(P,T;G)的有限配置C，其割集Cut(C)，是一组只包含co关系的条件集，Cut(C)被定义为Cut(C)=(Min(N)∪C·)·C。
定义12截断事件。Π=(o,h)是过程模型p=(C,A;F,M0)的一个分支进程，如果Π中的两个事件e′和e满足：①h(Cut([e]))=h(Cut([e′]))，即通过e到达的情态与e′的相等；②[e′]<·[e]，本地配置[e′]和本地配置[e]是适当偏序关系。将e称为截断事件、e′称为e的对应事件，可记为corr(e)=e′：
完全前缀展开的方法通过不断计算分支进程的可能扩展集扩展模型的分支进程，并在遭遇截断事件时停止扩展分支进程，从而回避了状态空间爆炸问题。图4是一个完全前缀展开的案例，该案例是针对图4中复杂模型P的展开，其中模型P′是模型P的一个包含截断事件的分支进程。其中[A]={A}，[F]={A,C,F}，[G]={A,C,E,G}。因为[J]= {A,C,E,G,H,K,J}、[G]<·[J]以及Mark([G])=Mark([J])，因此事件J是一个截断事件，条件6′是一个截断条件，存在corr(J)=G。
3 业务过程模型的化简
本章首先对基于完全前缀展开的业务过程模型结构化简与行为保持的总体流程进行介绍；然后详细阐述总体流程中的模型抽象部分，该部分在不影响其他行为的基础上逐一抽象模型行为；最后阐述分解模型的方法，从而化简复杂结构。
3.1 总体流程
基于完全前缀展开的业务过程模型结构化简与行为保持主要步骤可分为两部分，具体流程图如图5所示。①抽象模型。通过完全前缀展开，得到一个包含截断事件的分支进程，从而判断每2个活动之间的关系，出现可合并的活动关系时，依次重构不会影响其他行为的活动关系。不断迭代上述操作，直到模型中不存在合并后不影响其他行为的活动关系。②分解模型。通过遍历模型中的过程树逐个将其分解开来，最终输出化简后的业务过程模型。
3.2 抽象模型
本文的目标是简化业务过程模型。抽象模型算法的伪代码如算法1所示，其重点在于如何判断活动之间的关系，然后根据判断结果构造不同的过程树，然后更新模型。该算法主要分为四步：
(1)完全有限前缀展开。将输入的模型展开，从中获取相关信息用于后续操作。
(2)抽取可合并的活动关系。判断展开网中每一组事件之间是否存在可合并的关系，存在某种关系时，将其保存到对应的活动关系矩阵中。
(3)判断是否存在可重构的活动关系。去掉相互冲突的活动关系，获得一个无冲突的活动关系集合。若活动关系集合为空，输出过程模型；若活动关系集合不为空，则进入第(4)步。
(4)活动关系重构。通过依次合并活动关系集合中的活动关系更新模型，然后转第(1)步。
通过连续循环这些操作，最终将所有TEPM结构转换为过程树，输出一个包含过程树的过程模型。算法1的第4行、第5行、第8行分别对应第(2)、第(3)和第(4)步。
算法1抽象模型算法。
输入：过程模型p=(C,A;F,M0)；
输出：抽象后的过程模型p=(C,A;F,M0)。
MergeOfProcess(p)
1. flag = true
2. while flag:
3. flag = false
4. RM = IdentifiesRelation(p) //获取行为矩阵RM，具体见4.2.1节算法2
5. RL = getRelationList(RM) //获取活动关系集合RL，具体见4.2.2节算法3
6. for each ◎(a1, a2)∈ RL then
7. if ◎(a1, a2)⊂ p.A then
8. p = refactoringOfProcess(p, ◎(a1, a2))
//合并活动关系，具体见4.2.3节算法4
9. flag = true
10.return p
在最理想的情况下(模型中结构都属于TEPM)，算法1可将业务过程模型转化为一个完整的过程树。
一个合理的业务过程Petri网模型，通常具有恰当终止性(proper termination)、活性(liveness)、无死锁性(deadlock free)[37]等性质。为此，下面对本文提出的算法的相关性质进行分析。
定理1设过程模型p存在相应的行为等价过程树t，则p必然具有：①恰当终止性；②活性；③无死锁性。
证明①恰当终止性包含两方面：恰当终止的和无死事件。
设过程模型为p相应的行为等价过程树为t。过程树中的叶子节点代表活动，分支节点代表活动关系。因此，使用递归的方法，可以逐步遍历过程树的节点，将其在p中对应的活动合并，最终p中的活动被合并为一个活动a。p中只会保留活动a、a的入度和a的出度。p必存在源节点a的入度、终止节点a的出度。因此模型p是恰当终止的。
根据过程模型与行为等价过程树之间的关联，可知过程模型中每一个活动都能对应过程树中的一个叶子节点。过程树中任意两个叶子节点的最近公共父节点代表这两个叶子节点之间的行为关系。由此可知过程模型中任意两个活动必存在某种行为关系，它们之间是可达的，因此模型p中无死事件。
②和③的证明与①类似，不再赘述。
3.2.1 判定活动关系
本节详细介绍根据展开网抽取模型行为的方法。首先通过完全前缀展开技术可以将过程模型展开为一个包含截断事件的分支进程，从分支进程中可以便利地获取一些相关信息，具体需要的信息如表1所示。其中包括CM和oRM两个二维数组以及corr和h两个一维数组，二维数组CM表示展开网中的事件间的配置关系，例如表1中CM[F][C]=√表示事件F的配置包含C；oRM表示展开网中事件间的关系；符号“<”、“#”和“co”的含义可参见定义7，符号“>”表示逆因果关系，即a
表1 图4中完全前缀展开案例的信息
本文使用了顺序(→)，选择(×)，并发(||)，迭代(∝)4种关系来描述模型行为。为了构建一棵完整的行为等价过程树，需要先构建底层的子树。因此本文抽取出的活动关系需满足两个条件：①该活动关系属于4种关系中的一种；②所对应的两个活动合并后不改变其他任何行为的活动关系。下面给出4种关系的判断方法，这4种判断方法可以判断出任意一组活动间是否存在直接关系，即不需要通过其他活动，就可直接发生的行为，例如图1中的K和J间的顺序关系是在不涉及其活动时就可以发生，属于直接关系；H和J间的迭代关系是需要通过K才能发生，不属于直接关系。
对于过程模型p=(C,A;F,M0)，Π=(o,h)为过程模型p对应的一个包含截断事件的分支进程，其中，o=(S,T;F′)是一个出现网，h是一个映射函数，∀t1,t2∈T, ∀a1,a2∈A,h(t1)=a1,h(t2)=a2。
定义13顺序关系判断条件。当t1,t2满足下述条件时，a1与a2存在顺序关系，a1先发生，记为→(a1,a2)。
(1)oRM[t1][t2]= <，即t1与t2之间存在因果关系。
(2)对于所有t∈T且t≠t1∧t≠t2，①存在CM[t1][t]=CM[t2][t]∧CM[t][t1]=CM[t][t2]；②存在h(t)=h(t2)时，必有h(··t)=h(t1)；③存在corr(t)=t1时，必有h(t)=h(t1)∧oRM[t][t2]=<，以及对于任意t′∈T且t′≠t∧t′≠t2有CM[t][t′]=CM[t2][t′]。
定义14迭代关系判断条件。当t1,t2满足下述条件时，a1与a2存在迭代关系，其中a1先发生，记为∝(a1,a2)，a2先发生，记为∝(a2,a1)。
(1)oRM[corr(t2)][t1]= <∧oRM[t1][t2]= <，即存在corr(t2)，并且corr(t2)与t1、t1与t2之间存在因果关系。
(2)对于所有t∈T且t≠t1∧t≠t2，存在CM[t1][t]=CM[t2][t]。
(3)对于所有t∈T且t≠t1∧t≠corr(t2)，存在CM[t1][t]=CM[corr(t2)][t]。
(4)若h(t2)≠h(corr(t2))，则a1与a2存在可合并的迭代关系，且a1先发生；否则，a2与a1存在可合并的迭代关系，且a2先发生。
定义15选择关系判断条件。当t1,t2满足下述条件时，a1与a2存在选择关系，记为×(a1,a2)或×(a2,a1)。
(1)oRM[t1][t2]= #，即t1与t2之间存在冲突关系。
(2)corr(t1)=t2或corr(t2)=t1，即t1或t2是一个截断事件且对应事件是对方。
(3)对于所有t∈T且t≠t1∧t≠t2，存在CM[t1][t]=CM[t2][t]。
定义16并发关系判断条件。当t1,t2满足下述条件时，a1与a2存在并发关系，记为||(a1,a2)或||(a2,a1)。
(1)oRM[t1][t2]= co，即t1与t2之间存在co关系。
(2)corr(t1)=null∧corr(t2)=null，即t1和t2都不是截断事件。
(3)对于所有t∈T且t≠t1∧t≠t2，①存在CM[t1][t]=CM[t2][t]∧CM[t][t1]=CM[t][t2]；②当存在hList[t]=hList[t1]时，必有CM[t2][t]==true；③当存在hList[t]=hList[t2]时，必有CM[t1][t]==true。
任意两个事件只要满足定义13～定义16中的(1)就可以确定相应的活动之间存在关系，但这两个事件若不能满足其他几点，则对应的两个活动合并后必定会对其他活动关系产生影响。
通过表1中的信息以及上述4种关系判断方法，可以从图1中抽取出×(A,B)、×(C,D)、×(E,F)和→(K,J)4个关系。利用上述的4种关系判断方法，下面本文给出生成行为矩阵算法IdentifiesRelation的伪代码。
算法2生成行为矩阵算法。
输入：包含过程树的过程模型p=(C, A; F, M0)；
输出：行为矩阵RM。
IdentifiesRelation(p)
1. get an branching processes Π =(o, h)with p //展开过模型程 p
3. T = o.T, get corr、h、oRM、CM form Π =(o, h)、RM=[len(p.A)][len(p.A)]
4. foreach(t1: T)
5. foreach(t2: T)
6. if t1!= t2then
7. if isSequnence(t1, t2)then RM[h(t1)][h(t2)].add(→) //判断方法参考定义13
8. if isIteration(t1, t2)then RM[h(t1)][h(t2)].add(∝) //判断方法参考定义14
9. if isChoice(t1, t2)then RM[h(t1)][h(t2)].add(×) //判断方法参考定义15
10. if isConcurrency(t1, t2)then RM[h(t1)][h(t2)].add(||) //判断方法参考定义16
11.return RM
3.2.2 选择可合并的活动关系
接下来需要选择可合并的活动关系，这些可合并的活动关系需要满足在重构后不会对其他活动关系造成影响。上文中抽取出的活动关系是直接关系，因此只需要考虑有相同活动的关系是否冲突。
定义17可合并的关系判断条件。当◎(a1,a2)满足下述条件时，a1与a2之间的关系是可合并的。对与任意◎′(a1′,a2′)∈RM且{a1,a2}∩{a1′,a2′}≠∅有：①◎只表示一种关系；②◎=→时◎′=→；③◎=×时◎′=×或◎′=||；④◎=||时◎′=||；⑤◎=∝时◎′≠∝或a1′≠a2∧a1≠a2′。
迭代关系合并后会使不同方向的流关系合并到一处，容易影响其他活动关系，因此存在其他可合并的关系时不合并迭代关系。下面给出选择合并的活动关系算法getRelationList。
算法3选择合并的活动关系算法。
输入：行为矩阵RM；
输出：活动关系算集合RL。
getRelationList(RM)
1. tRL= {} lRL= {} RL= {}
2. for each ◎(ai, aj)∈ RM then //获取非空活动关系
3. if(◎ != ∅)tRL.add(◎(ai, aj))
4. foreach(◎(a1, a2): tRL)
5. falg= len(◎)==1 //判断活动是否满足定义17中的①
6. foreach(◎′(a′1, a′2): tRL) //判断活动是否满足定义17中的②③④⑤
7. if falg and {a1, a2}∩{a′1, a′2}≠∅ then
8. if ◎==→ and ◎′!= → then flag = false, break
9. else if ◎==× and(◎′==→ or ◎′==∝)then flag = false, break
10. else if ◎==∝ and(◎′!= ∝ or a1′== a2or a1==a2′)then flag = false, break
11. else if ◎==||and(◎′!=||)then flag = false, break
12. if falg then //分别存储迭代关系和其他关系
13. if ◎ == ∝then lRL.add(◎(a1, a2))
14. else then RL.add(◎(a1, a2))
15.if lRL.size > 0 then return RL //判断是否需要优先选择迭代关系以外的其他关系
16.return RL
3.2.3 合并活动关系
合并活动关系的基本思想如图6所示，即删除原有的两个活动，增加新活动，并有选择地令新活动继承原活动的一部分流关系。保留那些流关系，根据活动关系可以分为两种：①活动关系不属于迭代关系，此时在排除需要删除的条件后，令新活动同时继承原有的两个活动的流关系；②活动关系属于迭代关系，令新活动继承原活动中先发生的活动的流关系，但是有时先发生的活动的后继属于需要删除的条件，此时令新活动继承后发生的活动与其后继之间的流关系。
其次还需要删除一部分条件及其相关的流关系，需要删除的条件可分为3种情况：①不属于初始情态，仅仅连接了原有的两个活动，作为这两活动的过渡；②不和其他活动产生联系的，即出度和入度都为0；③具有相同的情态、前集和后继[38]的两个条件，删除其中一个。这3种情况中第①种容易影响流关系的选择，需在选择流关系前确定。后两种情况受流关系的影响，在最后确定。
算法4是合并活动关系算法refactoringOfProcess，其中流关系的选择对应第5～8行。删除条件的3种情况分别对应第2行、第10行和第11-15行。
算法4合并活动关系。
输入：过程模型p=(C, A; F, M0), 需要合并的活动关系◎(a1, a2)；
输出：过程模型p′=(C, A; F, M0)。
refactoringOfProcess(p, ◎(a1, a2))
1. newa = ◎(a1, a2), delA = {a1, a2} //新建新的活动、选择需要删除的活动
3. delF = { e1×e2|e1×e2∈p.F and {e1, e2}∩(delA∪delC)≠∅} //选择需删除的流关系
4. p′=(p.C-delC, p.A + newa-delA; F-delF, p.M0) //根据之前的选择更新模型
5. if ◎ ==∝ then //根据关系类型，增加新的流关系
6. p′.F += {newa×c|c∈((a1·⊆delCa2·: a1·)-delC)}∪{c×newa|c∈(·a1-delC)}
7. else then
8. p′.F += {newa×c|c∈((a1·+a2·)-(·a1+·a2)-delC)}∪{c×newa|c∈((·a1+·a2)-(a1·+a2·)-delC)}
9. newC = p′.C
10.for(i = newC; i >= 0; i--) //遍历模型中的条件
11. if(·newC[i]==∅∧newC[i]·==∅)then p′.C-= newC[i],continue//newC[i]出入度为0时删除
12. for(j = i-1; j >= 0; j--)//存在newC[j]且与newC[i]有相同的情态、前集和后继时，删除newC[i]
13. if(newC[i]∈M0∧newC[j]∈M0∧·newC[i]==·newC[j]∧newC[i]·== newC[j]·)
14. p′.F-= { e1×e2|e1×e2∈p.F and {e1, e2}∩(newC[i])≠∅}
15. if newC[i]∈ M0then p′.M0-= newC[i]
16. p′.C-= newC[i], break
17.return p′
3.3 分解模型
抽象模型通过遍历模型中所有的过程树，然后根据根节点(代表孩子节点的行为)，将其对应的孩子拆开作为不同活动，并重新构造不同活动之间的结构。
分解过程模型算法的基本思想的示意图如图7所示。即在将原活动a删除后，增加新的活动a1和a2，同时原本与a相关的流关系也会被修改保留，其次还会根据结构不同新增一些流关系和条件。
图7中红色和蓝色的表示原有的流关系，在模型被分解后所对应的位置，其中除了顺序结构中由a1和a2分别继承原本的出入流关系，其他结构中原有的流关系都是由a1继承。图7中绿色部分表示新增的流关系和条件，选择结构和迭代结构类似只需要新增的流关系，区别在于流关系的方向不同。顺序结构需要新增一个条件，并且还需要增加与a1和a2的新流关系。并发结构比较特别，需要新增两个条件，这两个条件分别作为a2的前驱和后继，同时还要复制对应于a1的前驱和后继的原有的流关系。
对过程模型进行分解时，顺序结构和并发结构都需要新增条件，此时根据流关系从抽象前的模型中选择相应的条件作为新增条件。设抽象前模型为p=(C,A;F,M0)、当前模型newp，将a中包含的活动加入A得到A′，则顺序结构的新增条件c满足{c|c∈p.Cand·c⊆A′∧c·⊆A′}，则并发结构新增的前驱条件c1满足 {c|c∈·A′-newp.A}，新增的后继条件c2满足 {c|c∈A′·-newp.A}。
不断重复分解操作，直到模型中不再包含过程树。最后输出的模型便是一个在保持行为的情况下结构被化简的过程模型。具体伪代码如算法5所示。
算法5分解过程模型算法。
输入：抽象后的过程模型p=(C, A; F, M0)，原过程模型p′=(C, A; F, M0)；
输出：过程模型newp=(C, A; F, M0)。
RefinePetriNet(p, p′)
1. flag = true, newC = C, newA = A, newF= F, newM0= M0
2. while flag:
3. flag = false //判断模型是否还存在可分解的过程树
4. foreach(a: newA) //遍历模型中的活动
5. if a is process tree and a == ◎(a1,a2)then //该活动是否可分解
6. flag = true, newA +={a1, a2} //增加新活动
7. //根据行为增加流关系、条件，具体如图7所示
8. get a condition set nC according to ◎, and newC += nC
9. get a flow relationship set nF according to ◎, and newF += nF
10. newF-= { e1×e2|e1×e2∈ newF and {e1, e2}∩{a}=∅} //删除与原活动相关的流关系
11. newA-= {a} //删除原活动
12.return newp =(newC, newA; newF, newM0)
将算法1和算法5结合起来,就可以化简具有复杂结构的业务过程模型。
4 案例测试与实验分析
为分析模型的化简程度和效率，本章对基于完全前缀展开的业务过程模型结构化简与行为保持的方法进行了实验分析。在本章中，首先分析一个详细的业务过程模型化简案例来验证该方法。其次，通过具有一定规模的实验数据测试了方法的效率。最后通过对比实验，证明本文方法对TEPM模型结构的化简具有优势。本章所有实验均在Intel(R)Core(TM)i5-6200U CPU @ 2.30 GHz 2.40 GHz且具有8 G RAM的 PC平台上完成。
4.1 案例分析
4.1.1 案例描述
首先给出一个业务过程模型案例，如图8所示。该业务过程是一个治疗流程，模型中包含的活动和执行条件具体有：感到不适的患者(a1)、担架(a2)、候诊室(a3)、经评估的救护车患者(a4)、护士(a5)、经评估的患者(a6)、等待治疗的患者(a7)、接受手术治疗的病人(a8)、医生(a9)、接受治疗的患者(a10)、恢复健康的患者(a11)；救护车到达(A)、预约到达(B)、急诊护士评估(C)、护士评估(D)、进行急诊化验(E)、完成急诊评估(F)、完成评估(G)、化验(H)、小手术(I)、大手术(J)、医生诊断(K)、医生集体诊断(L)、康复(M)、出院(N)。
图8中所示的治疗过程一开始存在两个分支：一个是患者坐救护车到医院，另一个是患者自行到医院挂号，之后再由医生决定治疗方案，然后进入不同的流程。由此，不同路径的事件有差别，但仍然会共享一些服务资源，例如a5和a7。
4.1.2 过程树生成
表2是一个将图8中的治疗过程案例抽象的例子，表中第1列代表了当前的循环次数，第2列代表了该次循环中的流程，第3列代表需要进行重构的活动。第3列是需要进行重构的活动，但是并不等于该次循环只检测出了这些活动，例如在第2次循环中，可以同时判断出关系有×(E,F)、×(K,L)、×(G,H)、×(J,I)、×(F,E)、×(L,K)、×(H,G)、×(I,J)，但是这些关系显然不能同时进行重构。最终该案例被转化为一个完整的过程树，即→(×(→(→(A,C),×(E,F)),→(→(B,D),×(G,H))),×(→(×(K,L),N),→(×(J,I),M)))。
表2 过程模型抽象案例
4.1.3 模型化简
表3中展示了将治疗流程中的过程模型分解的案例。表中第1列表示循环次数，第2列表示该次循环中的模型，第3列表示进行重构的活动。可以看出，得到的新模型相比原模型减少了两个条件和12个流关系。
表3 过程模型分解案例
4.2 效率分析
在评价算法的性能之前，首先分析算法的时间复杂度。本文算法可分为抽象模型部分和分解模型部分。
抽象模型部分的复杂度由IdentifiesRelation算法、getRelationList算法、refactoringOfProcess算法以及迭代次数(过程树深度)决定。IdentifiesRelation算法的复杂度受完全前缀展开算法影响，完全前缀展开算法的复杂度最坏情况下为O(|A|·Rξ)，|A|是模型中的活动数量，R是展开网中非截断条件的数量，ξ是活动的出度和入度中的最大数，因此IdentifiesRelation算法的复杂度最坏情况下为O(|T|3+|A|·Rξ)，|T|是展开网中的事件数。getRelationList算法的复杂度最坏情况下为O(|T|2)，refactoringOfProcess算法的复杂度最坏情况下为O(|A|2)。
抽象模型部分的复杂度最坏情况下为O(h*(|T|3+|A|2+|A|·Rξ))，其中h*为过程模型中所包含的过程树的最大深度。分解模型部分的复杂度为O(h*|A|2)。因此本文算法复杂度最坏为O(h*(|T|3+|A|2+|A|·Rξ))。
但通常情况下完全前缀展开算法的复杂度为O(R)，本文算法在通常情况下的时间复杂度为O(h*(|T|3+|A|2))
为了评价算法的性能，本节使用不同规模的业务过程模型模型组进行实验，这些样本包含不同数量、不同行为的元素。表4所示实验数据的具体情况。其中：counts表示该组数据中的模型总数；nmin、nmax、navg分别表示该组模型中包括条件、活动和流关系在内的最小数量、最大数量和平均数量；tmin、tmax、tavg分别表示算法在该组模型中花费的最小时间、最大时间和平均时间；WN1组数据中的模型属于TEPM，WN2组数据中的模型属于BSTM。
表4 实验数据
图9和图10是两组实验样本所对应的时间曲线图，其中横轴是已化简的模型数量，竖轴是花费的时间。这些实验表明，算法花费的时间会随着流程模型规模的增加而增加，但是对于大多数流程模型，算法所花费的时间平均到每个活动上都是非常短的时间(ns级，如图11所示)。其中WN1组数据中的模型属于TEPM，WN2组数据中的模型属于BSTM，它们总体模型规模是相近的，但WN1的时间变化曲线更不平滑。因此，绝大多数情况下，可以认为复杂结构所耗时间相比BSPM更加不稳定。
4.3 对比分析
为了评价本文中算法的化简效率和行为保持的程度，本节使用LEEMANS在文献[26-27]中的生成过程树方法作对比实验，该方法使用了花模型对无法转化的行为结构进行了泛化。本节使用20个TEPM的案例作为原始模型，根据每个模型中包含的元素数量，将附录表1中20个模型编号为M1～M20，将这一组模型作为PNO组实验模型。其中，最小模型(M1)和最大模型(M2)分别包含11和50个元素。使用本文化简算法对PNO组模型进行化简，将化简后的模型作为PNA组实验模型。使用文献[26-27]中生成过程树算法将PNO组模型转化为过程树，并根据过程树生成相应模型，作为PNB组实验模型。
三组实验模型以及在生成PNA和PNB两组模型过程中产生的过程树的可视图如附录表1所示，该表中的所有可视图使用图形可视化工具Graphviz(http://www.graphviz.org/)生成。观察附录表1中(a)列～(c)列，可以发现本文提出算法有效简化了业务过程模型的复杂结构。为客观分析模型结构的精简程度，本文对比了化简前后模型的条件数和流关系数的变化，如图12和图13所示。可以发现利用本文算法化简的PNA组可以有效地减少了条件和流关系。从图12和图13可以看出PNB组也有效地减少条件和流关系，而且对原始模型的精简程度更高。但实际上PNB组模型过于泛化，具体原因可见下文对模型的准确率、召回率以及F1分数的分析。
表1 实验案例
为分析本文算法对于行为保持的程度，下面将分析PNO组模型与PNA组模型、PNB组模型之间的差异，本文对模型进行仿真模拟获取日志信息。具体地本文对三组模型中的每个模型进行1 000次仿真模拟，使每个模型都有一个对应的路径多重集。每个路径多重集都会包含1 000条路径，其中会包含大量重复路径。去除多重集中的重复路径可以得到路径集合，每个模型对应的路径集合中的路径数量具体如表5所示。
表5 实验数据的路径集的大小
路径多重集中包含一些重复路径，这些不同的路径重复率可以体现模型不同事件的发生频率，而路径集去掉了重复的路径，从表5可以看到，相比多重集的1 000条路径，路径集中的路径数量被大幅度减少，特别是模型M4所对应的路径集只包含一条路径，小型的路径集有利于对模型行为进行对比分析。因此，本文同时使用路径多重集和路径集进行分析计算。
利用这些日志信息，将PNO组模型对应的集合作为实际值，PNA组模型和PNB组模型对应的集合作为预测值，就可以计算原模型与化简后模型之间的准确率、召回率以及F1分数。
本文比较了PNA组模型和PNB组模型的准确率、召回率以及F1分数，如图14～图19所示。可以看出，PNA组模型的3种指标值都非常高，证明PNA组模型在极大程度上还原了PNO模型的行为。而PNA组模型由于行为过于泛化，指标值基本很低，说明了本文算法更加适应TEPM模型，可以在保持行为(路径集和路径多重集的准确率、召回率以及F1分数的得分都趋近于一)的条件下化简模型。
5 结束语
本文提出一种在保持活动关系的基础上化简业务过程模型的方法。该方法采用完全前缀展开技术分析过程模型，然后快速准确地提取模型的行为关系，接着根据这些行为构造相应行为等价过程树。最后重组业务过程模型结构，从而化简了模型中的复杂结构。该方法利用基于完全前缀展开对具有复杂结构的业务过程模型的活动关系进行判断，这样可以避免“状态空间爆炸”问题。其次，该方法可以以过程树的形式呈现业务过程模型，有利于从不同角度分析模型的行为结构。同时通过实验验证了化简方法的有效性和效率。
业务过程不仅存储控制流信息，还会包含组织维、信息维、资源维等多维信息。因此，在本文所提出的基于行为等价过程树的业务过程模型的化简方法的基础上，如何增加流程的其他维度信息，并从不同维度化简业务过程是下一步需要考虑的问题。
