基于最优近似迹的增量日志过程挖掘优化方法
2021-01-12周衍志
周衍志
（安徽理工大学，安徽 淮南 232001）
0 引言
过程挖掘是介于计算智能与数据挖掘、过程建模与分析之间的一门新兴的学科［1］。过程挖掘的起点是事件日志。所有过程挖掘技术都假设可以顺序记录事件，使得每个事件都指向一个活动（即流程中定义良好的步骤），并且与特定情况（即流程实例）相关。事件日志可以存储额外的信息，例如执行或发起活动的资源（即人或设备）、事件的时间戳或与事件一起记录的数据元素（例如命令的大小）。事件日志可用于发现、监视和改进基于事实而不是虚构的流程。过程挖掘主要有三种类型：获取事件日志并生成模型而不使用任何其他先验信息；将现有流程模型与同一流程的事件日志进行比较；采用事件日志和过程模型并使用观察到的事件扩展或改进模型。
业务过程挖掘是实现业务过程自动化管理的途径之一，用于实现业务过程的发现、监控和改进。由于外部环境的影响和用户的个性化需求，业务过程需要不断变化，过程模型需要不断地改进和更新，基于先前历史事件日志的过程模型很难满足更新后的业务过程。以目的指导作为每个特定流程模型创建的决定因素，这种建模方式的结果是，公司需要为同一过程创建不同的模型。这些模型驻留在不同的抽象层次上，并根据建模目标的适当程度，假设不同的建模视角，例如这些差异导致了众所周知的“业务-IT差距”［2-3］。文献［4］描述一个组织的运作过程和实际实施的模型之间的关系。调整业务流程以适应不断变化的业务需求的灵活性是业务流程的核心。因此，变化在几个相关的过程模型之间的传播是模型对齐的主要用例［5］。Gartner 认为，变更与业务流程的关键要素高度相关，业务流程的关键要素是“使业务流程模型与流程执行保持同步，使流程和底层系统能够快速迭代以进行持续的流程改进和优化”［6］。Logica 咨询公司在最近的白皮书中公布的令人印象深刻的数字也说明了业务流程变化的重要性：“大多数欧洲公司将10%至55%的平均利润率用于业务流程的改变”［7］。文献［8］中提出了过程发现的α 算法。α是第一个过程发现算法，给定一个事件日志，通过算法可以发现一个过程模型，该过程模型只能够重演给定的事件日志。基于这样的局限性，文献［9］提出了α+算法用于解决算法无法处理短循环的问题。文献［10］中提出了一种具有完备性、精确性和简单性的适应度函数的遗传算法来发现模型中的频繁行为，用以解决过去几年中没有算法能够保证为所给定的日志找到完整、精确和简单模型的问题。文献［11］提出了一种启发式的挖掘方法，该方法在构建过程模型时仅使用了因果网的结构，而且考虑到了事件和序列的频率，该方法的目标是从一个事件日志中提取出一个因果网：首先，通过事件日志中活动之间的相互依赖关系与设定的阈值，构建相对应的依赖图，从而得到不包含非频繁行为的因果网。上述算法能够很好地处理日志的挖掘问题，但是对于增量日志或所生成的模型具有很大的缺陷，原日志不能在生成的模型中重演，不能很好地在实际中运用。
为保证原系统主要行为在特征不变的前提下，尽可能根据增量日志更新业务流程，本文提出了基于最优近似迹的增量日志过程挖掘优化方法。首先基于串比较的思想在原日志中寻找与增量迹差异最小的最优近似的初始迹，然后通过比对增量迹和最优近似迹之间的差异确定最优近似迹的变化位置，再根据最优近似迹寻找原模型中对应的变化域，最后根据不同的变化类型分别采取不同的优化方案，从而得到优化之后的过程模型。实验结果表明，该方法得到的过程模型能保持原系统的主要行为不发生改变，和初始过程模型具有较好的一致性度，有效地提高了模型的适合度，避免了重复挖掘问题。
1 研究背景
现实中由于用户需求的不断变化及各种外界因素的影响，业务流程常常会发生变化，因此可能会出现增加、删除或者修改某些活动现象。下面给出初始日志和增量日志，初始事件日志为：
L1=［
L2=［
利用Alpha Miner+（α+挖掘）算法对日志L1进行挖掘得到模型M1，如图1所示。
图1 初始过程模型M1
显然，此时L2中的迹无法在模型M1中进行重演，传统的做法是合并日志L1和增量日志L2，然后利用过程挖掘算法对合并后的日志进行重新挖掘。再次利用α+挖掘算法对合并后的日志进行重新挖掘得到模型，如图2所示。
图2 合并日志L1 和L2 得到的模型M2
本文采用文献［12］中的适合度计算方法，
其中，k 为给定日志的不同轨迹数，n 为日志轨迹中所含的数目，m 为日志轨迹中缺少的标识数，r为日志轨迹中遗留的标识数，c 为日志轨迹中消耗的标识数，p 为日志轨迹中产生的标识数。分别计算模型M1和模型M2的fitness，得到结果为过程模型M1的fitness=0.9945，过程模型M2的fitness=0.8723。通过M1和M2模型的适合度的对比发现，尽管仅在日志L1中添加了两条不同的增量迹，但是挖掘得到的过程模型M2适合度显然低于模型M1的适合度，而且模型M1和模型M2的一致性度很低，导致了原日志L1中很多迹不能再次在模型M2中重演，如
通过上述实例不难发现，在原有日志的基础上添加新的变化日志（即使只包含很少的几条变化迹），通过现有的挖掘算法对合并后的日志进行重新挖掘，会导致挖掘以后的更新模型和原模型的差异度很大、甚至会丢失原模型中的一些主要行为，更新后的模型适合度可能会大幅度降低。为了解决这样的问题，本文提出了基于最优近似迹的增量日志过程挖掘优化方法，该方法能在尽可能保持原模型行为结构不变的情况下拓展新功能，使得优化后的模型能更好地重演原日志和增量日志。
2 基础知识
定义1［13］（过程模型）过程模型是一个元组P=(A,I,C,F,T)，其中：
A 作为活动节点的非空集，C 作为控制节点的集，A 和C 是不相交的，I ⊆A 作为一组初始活动，F ⊆(A ⋃C)×(AI ⋃C) 作 为 流 关 系，T:C →{and,or,xor}作为为控制节点分配类型的函数。
定义2［14］（行为轮廓）设(N,M0) 是一个网，初始状态为M0，对任意的变迁对( t1,t2)∈(T×T )满足下面关系：
1）若t1>t2且t2≯ t1，则称变迁对(t1,t2)中的t1与t2为严格序关系，记作t1→t2；
2）若t1≯ t2且t2>t1，则称变迁对(t1,t2)中的t1与t2为逆严格序关系，记作t1→-1t2；
3）若t1≯ t2且t2≯ t1，则称变迁对(t1,t2)中的t1与t2为排他关系，记作t1+t2；
4）若t1>t2且t2>t1，则称变迁对(t1,t2)中的t1与t2为交叉序关系，记作 t1‖t2；
5）将所有的关系集合称为网系统的行为轮廓，记作BP={→,→-1,+,||}。
定义3［15］（日志迹、业务流程日志，L）A 是一组活动。 A* 表示A 上一组有限序列集，并且σ=a1a2…an∈ A*是一条日志迹。 L ∈( A*) 是一业务流程日志。‖ L‖ 表示一条日志迹中的活动数量。
定义4［16］（完整的业务流程日志）完整的业务流程日志是包含所有已执行迹的日志。完整的业务流程日志用L*来表示，L*∈ *(A*) 。L ⊆L*。
定义5［17］（带标签的Peri 网）一个带标签的Petri网是一个4-元组N:=(P,T,F,λ)，其中(P,T,F)是一个Petri网，λ:T →A ⋃{τ} 是一个将标签分配给变迁的函数。如果λ(t)≠ τ，则t 是可见的，否则，t 是不可见的或沉默的。
定义6［17］（活动对齐）一个网系统S:=(N,Nini,Mfin)一条迹υ ∈ A*与另一条迹υ′∈ A*′执行活动σ 的对齐，其中N:=(P,T,F,λ) ，是S 上满足π1(γ)|A=υ 和π2(γ)|T=σ 合法移动的有限序列
3 基于最优近似迹的增量日志过程挖掘优化方法
3.1 查找最优近似迹
基于串首尾比较的思想，首先将原日志中的迹与增量日志中的迹分别从每条迹的开始活动逐个向后对齐以及从每条迹的结束活动逐个向前对齐，分别计算增量日志中的迹和原日志中的迹不对齐活动的数量所占比例，然后通过计算两个情况的平均值得到两条迹差异度。其中与增量日志中迹差异度最小的原日志中迹，即为最优近似迹。算法实现如下：首先将原日志（Original Log）中每一条迹分别与增量日志（Incremental Log）中每条迹的初始变迁对齐，当增量日志中迹的活动与原日志中迹的活动tj相同，则对比差异值取0；若两迹中活动不相同，则对比差异值取1。由于增量日志中的迹有对活动的增加或删除等操作，使得原日志单条迹的活动数量||Original Log||与增量日志单条迹的活动数量||Incremental Log||存在差异，上述方法计算差异度时，没有考虑迹长度不相等时的对比规则。基于此，对计算步骤进一步优化，令Lo=||Original Log||，Li=||Incremental Log||，SSFromHead 函数用上述方式处理日志之后，获取增量日志与原日志顺序对齐之后的差异度。
函数SSFromHead 将原日志中迹与增量日志中迹从开始活动逐个向后对齐，计算原日志与增量日志的差异度DDS′。其中Original Log 表示原日志，Incremental Log 表示增量日志，函数执行时，将原日志中每条迹分别与增量日志的初始变迁对齐，依次向后，当原迹的变迁与增量日志迹的变迁相同时，返回值0；若变迁不相同，返回值1；两条迹中任意一条迹中出现无活动比较时，比较操作终止。此时两条迹活动数量求差的绝对值，与所有对比返回的值求和，然后除以增量日志迹的长度，得到的结果即为该原日志迹与增量日志迹的差异度。
同时，基于数据结构串比对的思想，将原日志中的迹序与增量日志中的迹结束活动对齐，对齐之后序列使用SSFromEnd 函数处理对齐日志，获取增量日志迹与原日志迹结束活动对齐的差异度DDS″。
function SSFromEnd(Lo,Li,Original Log,Incremental Log)
OLi⊆Original Log∧
ILi⊆Incremental Log∧
tj∈OLi∧t′
j∈ILi∧
m=min{Li,Lo}∧
ML=|Li-Lo|}
return…,
end function
求得原日志与增量日志所有迹对比差异度之后，将起始活动对齐求得的差异度与结束活动对齐求得的差异度取平均值，作为最终原日志迹与增量日志迹的差异度。从最终的差异度中找到最小的值，即可获得原日志中与增量日志差异度最小的日志。
functionFLSe arch(
Lo,Li,Original Log,Incremental Log
)
FinalLog←{OringalLogt|t∈(1,n)∧
DDSt⊆min{DDS1,…,DDSn}
returnFinalLog
end function
3.2 基于增量日志的变化类型优化过程模型
上文算法1求得了在原日志中与增量日志差异度最小的迹。在此基础上，首先通过比对增量迹和最优近似迹之间的差异确定最优近似迹的变化位置，再根据最优近似迹寻找原模型中对应的变化域，最后，根据不同的变化类型分别采取不同的优化方案，从而得到了优化之后的过程模型。
下面给出常见的变化类型，并针对不同的变化类型提出了不同的优化方案，这些优化方案保证了变化域的原行为不变。
图3 修复操作规则
图3 中的修复操作在保证源模型中活动行为不变的前提下，进一步拓展了新的业务流程，达到了对源模型修复的目的，有效地避免了重复挖掘增量日志的低效问题，保证了源模型的主要行为不会丢失。
算法:String Comparison Algorithm
输入：原日志，增量日志
输出：可重演原日志以及增量日志的模型
Step1 根据给定的所有原事件日志L1，使用prom 工具的α+插件分析各个变迁的行为轮廓关系，建立初始的Petri网过程模型M1。
Step2 将原日志L1与增量日志L2输入算法l（Find the optimal approximation trace algorithm），求得原日志L1中与增量日志L2中相似度最高的迹τx。
Step3 从Step1 已建立的初始过程模型M1中取出迹τx的子模块M2。根据τx模块中的变迁表现得到行为关系，建立增量日志L2的过程模型M3。
Step4 对比模型M2与模型M3，引入静默变迁，基于约定的模型修复规则，使得模型M2优化后的日志L2可以在优化后的模型M4中重演。
Step5 用模型M4替换子模块M2，得到最终的过程模型M5。
Step6 输出最后的过程模型M5，即为优化后的过程模型，算法结束。
4 实例分析
以上述增量日志为例来验证所提算法String Comparison Algorithm的可行性。。如图4 所示，图中Ⅰ为日志L2中迹τ′1，Ⅱ、Ⅲ、Ⅳ分别为日志L1中迹τ2、迹τ3和迹τ4。算法String Comparison Algorithm运行时，将迹如图所示依次头尾对齐，如果对齐迹的活动相同，权值取0；如果对齐迹的活动不相同，权值取1。将对比所得到的迹的权值进行求和，得到L1中迹τ2、迹τ3和迹τ4与L2中迹τ′1对比的权值。计算图4中（a）（b）（c）的差异度：
图4 求差异度过程图
根据求出的差异度，继而求出差异值最小的迹。得到迹
图5 模型变化执行过程
图5中，模型Ⅰ为传统α+算法将原日志与增量日志合并后挖掘的模型中增量日志的子模块。模型Ⅲ与模型Ⅰ对比，不仅增量日志可以在模型Ⅰ中重演，原日志中的迹也可以在模型中重演。将该变化带入源模型，得到如图6 所示的变化后模型M3。
图6 变化后模型M3
相较于图2所示的Prom插件挖掘模型，使用算法String Comparison Algorithm 求得原日志与增量日志差异度最小的迹，并基于约定的修复规则修复模型，加入静默变迁的使用，使得原日志L1中的迹可以在图6 模型中重演。经计算得该模型Fitness=0.9947，此模型能极大程度上表达日志L1与日志L2中的过程，可作为当前项目实施过程模型。
5 总结
本文在已有研究的基础上，给出了基于日志变化的模型变化的方法。在Prom 软件中使用Alpha Miner+插件获得当前日志序列过程模型。经分析发现，使用上述插件当日志发生变化时无法产生与变化后日志相符合的模型，由此提出算法String Comparison Algorithm，先求出原日志迹与增量日志迹起始活动对齐时的差异值，再求出原日志迹与增量日志迹结束活动对齐时差异值，继而获得与增量日志差异值最小的原日志迹。基于约定的模型修复规则，对所求日志模型进行修复，最后将该模型发生的变化映射到原日志模型，确定变化后的过程模型。经检验，原日志的迹可以在得到的过程模型中进行重演。
