基于感知成本的流程模型与事件日志有效对齐

李多芹，方贤文*，王丽丽，2，邵叱风

（1.安徽理工大学 数学与大数据学院，安徽 淮南 232001；2.嵌入式系统与服务计算教育部重点实验室（同济大学），上海 201804；3.安徽科技学院 信息与网络工程学院，安徽 蚌埠 233030）

0 引言

近年来，事件日志与流程模型之间的对齐已被证明对过程挖掘中的服从性校验问题极为有用［1］。日志迹与流程模型之间可能会存在多种对齐，目前最优的对齐默认为给定成本函数下成本最小的对齐，于是在对齐过程中，成本函数的选取尤为重要。关于对齐及对齐成本函数的选取，很多学者已经做了大量研究：文献［2］中表明事件日志与流程模型之间保持适当对齐的重要性，并详细阐述了这种对齐的实现及对齐在服从性校验和性能分析中的应用；文献［3］中利用流程模型结构和行为特征的优势，提出一种在寻找最优对齐时能显著缩减搜索空间的方法；文献［4］中将对齐的计算问题转化为整数线性规划模型的求解问题，从而显著降低问题的复杂性；文献［5］中提出了一种基于Petri 网的事件日志与过程模型之间的快速对齐方法，即Rapid Align 方法，以提高过程挖掘中计算最优对齐的效率；文献［6］中为了提升了过程挖掘中计算最优对齐的效率，提出一种基于Petri 网可达图的业务对齐方法。

在上述工作中，都选择使用标准成本函数进行对齐。事实上，据所知，现有的绝大多数对齐问题中都默认使用该函数，该函数将模型和日志的同步移动及静默移动的成本记为0，异步移动的成本都记为1，即将模型中的异步移动和日志中的异步移动产生的影响视为是等价的。然而，文献［7］中通过具体的实例表明，在某些应用情境中使用标准成本函数对齐模型和日志会产生不符合逻辑的对齐结果，于是文献［7］提出了标准成本函数的一个变体：最大同步成本函数。该函数中模型移动的成本值远小于日志移动，进而通过产生额外的模型移动使得同步移动的数量最大化；然而，不论是将异步移动的成本值都计为1 还是使得模型移动的成本值远小于日志移动的成本值都可能会导致对齐成本与感知成本相差甚远。一个典型的情况是当出现冗余噪声时，最大化同步成本函数会尽可能牺牲模型移动来将该噪声事件与模型中的某一活动形成同步移动，从而导致对齐成本严重偏离感知成本。

基于此，本文根据业务流程中的典型行为流特征定义了一种新的成本函数，即重要同步成本函数，使得在该函数下对齐流程模型与事件日志时的对齐成本更加贴合感知成本；同时，基于该函数给出一种能够提升对齐效率的对齐算法，其中，业务流程中的典型行为流特征用于确定流程中各活动的重要程度。关于业务流程中的典型行为流，已有学者做了相关研究：文献［8］中指出许多流程通常以固定的顺序执行初始活动，经过一系列流程走向变化，如，并行分支、循环等，又收敛到更结构化的行为，然后再次发散；文献［9］中利用行为流的这种特征将流程模型划分为强制性子序列和选择性子序列，通过选择相应的测量公式，切实有效地提升了日志与模型之间的适合度。关于感知成本，本文迁移了文献［10］中提到的感知一致性概念，该文献研究的问题是：流程模型间行为一致性的哪一种正式概念可以最好地近似模型专家的感知一致性。类似地，本文的研究问题是：对齐流程模型和事件日志时，哪一种成本函数下的对齐成本能更好地接近感知成本。

1 知识准备

定义1模型与日志的对齐［7］。令Σ为活动集，包含静默活动τ 的活动集记为Στ，即Στ=Σ∪{τ}；包含跳过符号＞＞的活动集计为Σ＞＞，即Σ＞＞=Σ∪{＞＞}；Στ＞＞=Σ∪{τ，＞＞}则表示同时包含静默活动和跳过符号的活动集。令σ∈Σ*是一条日志迹，N为一Petri 网模型，则模型N中的执行序列与日志迹σ的对齐γ指的是日志-模型对的一个序列，即γ∈(Σ＞＞×Σ＞＞)*。

定义2对齐成本［7］。令γ∈(Σ＞＞×Σ＞＞)*是σ∈Σ*和Petri网N间的一组对齐。该对齐的成本函数c为对齐对到正实数上的映射，即c：(Σ＞＞×Στ＞＞) →R≥0，于是c(γ)=Σ0≤i≤|γ|-1c(γi)。

若给定对齐成本函数c，在该成本函数下对齐γ为最优的，当且仅当不存在γ'使得c(γ') ＜c(γ)。

定义3标准成本函数［7］。对齐对(l，m)∈(Σ＞＞×Στ＞＞)的标准成本函数cst定义如下：

由上式可以看出，对标准的成本函数而言，静默移动和同步移动的成本为0；日志移动和模型移动的成本都为1。文献［7］中通过真实的案例表明，该成本函数虽然在相关文献中经常使用，但可能会产生不希望得到的，即不符合逻辑的对齐结果，于是提出了最大同步成本函数的概念如下。

定义4最大同步成本函数［7］。对齐对(l，m)∈(Σ＞＞×Στ＞＞)的最大同步成本函数cmax-sync定义如下：

其中0 ＜ε＜1。比较定义3 和定义4 可以看出，两个成本函数只在模型移动成本值的设置上有所不同，定义4 中将模型移动的成本值设置为任意小的数，即ε，通过这种方式使得对齐结果中同步移动的数量最大化。可以预见，同步移动数量最大化的同时会产生很多额外的模型移动；然而，在某些真实情境中，额外产生的模型移动会带来更大的影响，以牺牲模型移动为代价一味地追求同步移动数量的最大化并不是明智的选择，从而使得产生的对齐结果并不可取。

2 动机例子

为了激励消费者，电子商城经常会发放一定额度优惠券，本文以此背景下的商品购买流程作为动机案例，如图1用Petri 网给出了该购买流程的控制流依赖。

图1 中各字母所指代的活动如表1 所示，由图1 和表1 可知，顾客一旦选择某一商品后，随时都可以进入付款界面，且进入付款界面前或进入付款界面后都有查看店铺优惠券及选择使用或不使用优惠券的权利，这与当今各大电子商城的购物模式相吻合。

表1 图1中各个字母指代的活动Tab.1 Activities referred to letters in Fig.1

对迹σ=，若使用标准的成本函数将其与图1 中的流程P进行对齐，可得到图2 中的最优对齐γ1，易知在标准成本函数下γ1的成本为2；若使用最大同步成本函数则可得到最优对齐γ2且在最大同步成本函数下γ2的成本为3ε。然而，代入图1 中所给出的真实问题情境，可以明显看到γ1和γ2的感知成本与两种函数下计算出的成本有很大差距，因为在网络购物这一问题情境中，顾客是否愿意进入到付款界面代表着对该商品购买意愿，是商家十分关注的步骤。尤其在γ2中，跳过活动g（进入付款界面）的成本用一个任意小的ε来衡量是不合理的。此外，把跳过活动g 和跳过活动f（或c）的成本设置为相同的单位值也会使得对齐成本偏离感知成本。

我们知道，对齐模型和日志迹的意义在于反映模型流程和真实执行流程间的偏差，于是对于这类真实的问题情景，γ1和γ2产生的对齐结果是不可取的，因为对齐成本严重偏离感知成本，也就是说对齐结果无法反映真实偏差情况。为了解决这个问题，下面将基于感知成本的概念提出标准成本函数的另外一个变体，即重要同步成本函数。

3 基于感知成本的有效对齐方法

3.1 重要同步成本函数

通过对动机例子的分析知道，跳过或插入不同活动的感知成本是有很大差距的；于是，为了使对齐成本更加贴合感知成本，在对齐前将活动集Σ按重要程度进行划分，并为划分后的不同的活动类分配不同的成本是必要的。为了划分活动集Σ，不失一般性，引入流程模型中行为的典型流特征作为重要程度的划分依据。

文献［8］中指出许多流程以独特或类似的行为开始，也就是说，通常一个初始活动（组）是以固定的顺序执行的。随后，根据流程的具体实例，流程中可能出现更多的变化，例如并行分支、循环等。在流程的某些节点上，行为再次收敛为更结构化的，即以固定的顺序执行的行为，然后再次发散。图3 给出了该流程事实的示意图。

此外，文献［9］所提方法同样基于该流程事实，将流程模型划分为强制性活动路径和选择性活动路径，并通过实验证明划分后的准确检测偏差能够明显提高适合度测量值。

基于上述事实，本文将流程模型中强制性活动路径上的所有活动记作强制性活动或重要活动，所有强制性活动组成的集合记为Σ+；将选择性活动路径中的所有活动记作选择性活动，所有选择性活动组成的集合记为Σ-，并默认活动集中的活动是按照流程执行的先后顺序排列的。这里Σ=Σ+∪Σ-且Σ+∩Σ-=∅，即将活动集Σ按重要程度划分为两个互不相交子活动集Σ+和Σ-。具体地，对图1 中的流程有：Σ=｛a，b，c，d，e，f，g，h，i，j｝，Σ+=｛a，g，j｝，Σ-=｛b，c，d，e，f，h，i｝。基于上述活动集的分类，可将重要同步成本函数形式化定义如下。

定义5重要同步成本函数。结合第1 章中对相关符号的定义，定义一个对齐对的重要同步成本函数cimp-sync如下：

其中0 ＜ε＜1。定义5 中活动集被分Σ为强制性活动集Σ+和选择性活动集Σ-，且Σ+上日志移动和模型移动的成本为1；Σ-上日志移动和模型移动的成本都为ε。通过为两类活动集赋予差距较大的单位成本值，使得在对齐过程中优先考虑重要活动的对齐，从而得到更加贴近感知成本的对齐结果。

根据定义5 中的成本函数，可以得到迹σ=和图1 中所示流程的最优对齐如下：

易知γ3在重要同步成本函数下的对齐成本为3ε，虽然γ2的对齐成本也为3ε，但正如第2 章中所述，γ2中为了使同步移动的数量最大化添加了额外的模型移动（如活动g），这导致对齐成本与感知成本有很大差距。相反地，γ3中的对齐因为优先考虑了重要活动的同步（已用阴影突出显示），所以使得对齐后的成本与感知成本比较贴近。于是对迹σ=和图1 中的流程来说，重要同步成本函数下的最优对齐γ3更能反映流程模型和真实执行迹间的偏差。

值得注意的是，上述活动类的划分只是依据流程模型中行为的典型流特征分为两类，在实际执行中，操作者可根据现实意义自定义地将流程中活动划分为若干类。此外，不同活动类上单位成本值的分配也可以依据实际需求自定义设置。当按照上述操作划分活动类时，下面将基于该成本函数给出一种可以提升效率的对齐计算方法。

3.2 重要同步成本函数下的有效对齐方法

基于所提成本函数有效对齐方法的框架如图5 所示，主要可以被分为3 步：首先，根据流程模型的典型流特征划分活动类，并基于日志迹和强制性活动集确定重要匹配子序列；然后，依据重要匹配子序列中的活动分别将模型与日志做对应的分割；最后，基于重要同步成本函数对齐每一个子流程和对应的日志迹子序列，并将分段对齐的结果进行合并以得到最终的对齐结果。

3.3 重要匹配子序列的确定

重要匹配子序列指的是在日志迹和强制性活动集中都按一定顺序出现的活动组成的集合，子序列中的活动在对齐过程中会优先产出同步移动。依据流程模型中行为的典型流特征划分活动类后，利用文献［11］中给出的最长公共子序列（Longest Common Subsequence，LCS）概念从日志迹和Σ+中确定重要匹配子序列。

定义6最长公共子序列［11］。序列Zr=(z1，z2，…，zr)为序列Xm=(x1，x2，…，xm)和序列Yn=(y1，y2，…，yn)的最长公共子序列，当且仅当序列满足：

1）zs=xis=yjs，1 ≤s≤r；

2）1 ≤i1≤i2≤… ≤ir≤m∧1 ≤j1≤j2≤… ≤jr≤n；

3）对于任意一个Xm和Yn的子序列Z'，都有|Z'| ≤|Zr|。

文献［11］根据最长公共子序列定义，展示了求最长公共子序列长度算法，该算法以两个有限序列为输入，根据递推计算公式输出这两个序列的最长公共子序列定义。以动机案例中所给的日志迹和模型为例，输入和Σ+=｛a，g，j｝，可得到的σ和Σ+的最长公共子序列，也就是日志迹σ和图1 中模型的重要匹配子序列为Simp=（a，g，j）。为表示方便，可将该算法视为一个函数，即LCS（σ，Σ+）=Simp。确定了重要匹配子序列Simp后，下面将根据Simp中的活动分别对日志迹和流程模型进行分割。

3.4 日志迹和流程模型的分割

在3.3 节中，通过LCS 函数可以确定对齐流程模型和日志迹的重要匹配子序列Simp，为了提升对齐流程模型和事件日志的效率，下面将依据Simp中的活动分别对流程模型和事件日志进行分割，使得分割后的子模型和日志迹子序列能够一一对应并对齐，利用这种分而治之的思想旨在缩减对齐整条日志迹和流程模型时需要搜索的状态空间。下面给出以日志迹和Simp为输入的日志分割算法（Log Trace Divide，LTD）。该算法通过If-else 语句区分出四种不同的日志分割情况。

算法1 日志迹分割算法。

从算法1 中可以看出，日志迹的分割可以依据日志迹与Simp的1 号位活动、n号位活动是否相同分为4 种情况，进而导出3 种可能的子模型/日志子序列的个数，即h=k-1 orkork+1。此外，可以观察到，每两个相邻的子序列会有一个共享的活动，即上一个子序列的结束活动与下一个子序列的开始活动相同。算法最后输出日志迹σ的h个子序列（算法1的18））。为表示方便，同样将该算法视为一个函数，即LTD(σ，Simp)=σ1，σ2，…，σh。延续3.2 节中的例子可对日志迹进行分割：因为Simp=（a，g，j），|Simp|=3且日志迹与Simp的1 号位活动、n号位活动均相同，于是可根据算法1 的4）～5）将日志迹分成2 个子序列：可以看到活动g为σ1和σ2的共享活动。

类似地，可以依据Simp中的活动将流程模型分成若干个个子流程，即流程分割（Process Model Divide，PMD）算法。为表示方便，同样将该算法视为一个函数，于是有PMD(P，Simp)=P1，P2，…，Ph。此时，每两个相邻的子流程也会有一个共享的活动，即上一个子流程的结束活动与下一个子流程的开始活动相同。根据重要匹配子序列Simp可将图1中的流程分割为两个子流程P1和P2，如图6 所示。

根据同一个重要匹配子序列对流程模型和日志迹进行分割后，得到的分割结果是对应的，即子流程与子序列个数相同，且存在一一对应的关系，于是可先对齐分割后得到的子流程与子日志序列，再依据共享活动将各部分的对齐结果合并以得到完整的日志迹和流程模型的对齐。较之于传统的对齐操作，这种分而治之的对齐策略能大幅提升对齐效率。

通过LTD 和PMD 函数可以将流程模型和事件日志分割成一一对应的子流程和日志迹子序列，接着基于重要同步成本函数对齐每一个子流程和对应的日志迹子序列，将分段对齐的结果进行合并就可以得到最终的对齐结果。

3.5 基于重要同步成本函数的有效对齐算法

到目前为止，前面的内容分别详细阐述了所提方法的理论基础，以及重要步骤的具体操作，下面将给出完整的算法实现。该算法以日志迹σ和流程模型P为输入，经过确定重要匹配子序列Simp、基于Simp分割流程模型与事件日志、在重要同步成本函数下对齐子流程和日志迹子序列及依据共享活动合并对齐结果等步骤，最后输出重要成本函数下日志迹与流程模型的最优对齐γopt。

算法2 基于重要同步成本函数cimp-sync的对齐算法。

算法首先获取强制性活动集和选择性活动集（算法2 中1））；接着利用LCS 长度算法获取重要匹配子序列Simp（算法2中2））；然后分别通过LTD 和PMD 函数获取日志迹子序列和子流程（算法2 中3）～4））；同时根据分割后的日志迹提取共享活动集Es（算法2 中5））；对每一组对应的子序列和子流程，在cimp-sync下进行对齐（算法2 中6）～7））；最后利用共享活动将各部分的对齐结果进行合并，并返回最优对齐γopt。

4 实验与结果分析

为了验证上述所提方法，实验部分将先介绍实验数据的来源；接着，详细阐述实验步骤；最后，分别通过3 种函数下对齐准确率和效率的对比来评估所提方法的性能，并在实验结果对比图的支撑下得出结论，即本文方法能在满足准确率需求的同时提升对齐的效率。

4.1 实验数据

Jouck等［12-13］提出的PTandLogGenerator 可构造同时包含序列、并发、选择和循环结构的业务流程模型，该构造器已在Prom 中实现，操作者通过输入模型大小、各个操作符出现的概率等参数可直接批量生成符合要求的流程模型，部分学者将其用于过程发现算法的评估［14-15］。为了验证所提方法，实验部分将利用该构造器随机生成10 条业务流程模型，流程中活动数量为11～37 的均匀分布。通过对每条业务流程进行下述实验步骤中一系列的处理，最终将对6 000 条对齐结果的数据进行分析。所有的实验数据均可在线访问：https：//github.com/duoqinLi/experimenta-data.git。

4.2 实验步骤

为了评估3 种成本函数下的对齐准确率和对齐效率，设计如下实验步骤：首先，对每一个用Petri 网表示的流程模型，通过Prom 中的插件随机运行出10 条完全服从的流程执行序列，称这些服从的日志迹为参考迹，用σ表示。然后，为了获取包含各种可能情况的不服从日志，对σ分别添加不同形式且不同比例的噪声。噪声的形式包括缺失、错位、冗余及3 种噪声的混合，噪声的比例分别为10%，20%，…，50%，这样每一条完全服从的执行序列都可以导出20 条不同的不服从序列，加噪后不服从的日志迹用σ'表示，于是每个流程对应200 条不服从的日志迹。接着，先直接利用现有Prom 插件计算cst和cmax-sync下σ'与流程模型的对齐；再基于算法2计算cimp-sync下σ'与流程模型的对齐。对齐结果中的模型执行序列用σ″表示，于是每个流程对应600 条相互独立的对齐结果。最后，依据这些对齐结果，分别比较3 种成本函数下对齐的准确率和效率，并用可视化的三维图直观地展示对比结果。

4.3 准确性评估

对每一个流程模型，将最初获得的完全服从执行序列σ作为评估不同成本函数下对齐结果所返回的模型执行序列σ″是否准确的标准：如果σ和σ″完全相同，则准确率记为1；当σ和σ″不完全相同时，就需要通过判断两个序列的相似度来获取不同成本函数下对齐结果的准确率。在下面的实验中，本文利用python 官方库difflib 中的SequenceMatcher 类来计算两序列的相似度，其思想是找到不包含无用元素的最长连续匹配子序列，然后递归地将相同的思想应用于匹配子序列的左边和右边的序列片段。

根据上述的实验数据和评估标准，可以分别对不同噪声类型下3 种函数得出的对齐结果进行准确率的比较。当不服从的日志仅包含缺失噪声时，重要同步成本函数分别与标准成本函数和最大同步成本函数的对齐结果对比如图7所示。

从图7 中可以得出，当不服从的日志仅包含缺失噪声时，cimp-sync下的平均对齐准确率为90.69%，结果略优于cst的90.59%，但是与cmax-sync下的对齐结果相比准确率偏低。另一方面，用标准差衡量图7（c）中各准确率的离散程度时，可得cimp-sync、cst及cmax-sync下的标准差分别为3.15、3.25 和3.92。这表明，与其他两种成本函数相比，cimp-sync下的对齐结果更加稳定。下面考虑当不服从的日志仅包含错位噪声时三种成本函数的对齐结果，结果对比如图8 所示。

从图8 中可以看出，当不服从的日志仅包含错位噪声时，3 种成本函数下的对齐结果均有较大的波动，其中cmax-sync下的对齐结果起伏波度最大，标准差为9.40，相比之下cimp-sync与cst的波度较小且起伏轨迹十分接近，标准差分别为6.18和6.13。下面考虑当不服从的日志仅包含冗余噪声时，3 种成本函数的对齐结果，结果对比如图9 所示。

从图9 中可以看出，当不服从的日志仅包含冗余噪声时，各流程在cimp-sync和cst下对齐结果的准确率十分平稳，平均准确率分别为98.53%和99.10%。相比之下，cmax-sync下的对齐结果波度较大且平均准确率最低，仅为81.09%，与cimp-sync和cst下的对齐准确率分别相差17.44%和18.01%。这是因为cmax-sync下在对齐过程中过分追求同步移动的数量的最大化，于是当出现冗余噪声时，会尽可能牺牲模型移动来将该噪声事件与模型中的某一活动形成同步移动，从而降低准确率。下面考虑当不服从的日志包含缺失、错位和冗余三种类型的混合噪声时，对齐结果对比如图10 所示。

从图10 中可以得出，当不服从的日志包含混合噪声时，cimp-sync下的平均对齐准确率最高，为88.67%；cst其次，为88.65%，均大幅度高于cmax-sync下的81.34%。此外，cimp-sync下的对齐结果也最为稳定，标准差为3.21；cst其次，标准差为3.29；cmax-sync下的对齐结果最不稳定，标准差高达11.61。事实上，我们知道，在实际的业务流程执行过程中，不服从日志的噪声在绝大多数情况下并不是单一类型的。而图10 表明，在包含混合噪声的情况下，cimp-sync能够得出准确率更高且更稳定的对齐结果。

综上，可以得出结论，较之于标准成本函数和最大同步成本函数，重要同步成本函数下的对齐结果满足准确率的需求，且在某些情况下能够产出更高准确率、更稳定的对齐结果。

4.4 效率评估

为了评估算法2 中所提对齐算法的效率，同样与另外两种函数在对齐所耗时间上进行比较。这里σ'与流程模型在cst和cmax-sync下的对齐时间可直接通过对齐插件获取并记录，cimp-sync下σ'与流程模型的对齐时间则通过累加各个子序列和子模型的对齐时间得到。

根据上述的实验数据和评估标准，当不服从的日志包含缺失、错位和冗余三种类型的混合噪声时，重要同步成本函数分别与标准成本函数和最大同步成本函数的对齐所耗时间对比如图11 所示。

从图11中可以得出，cimp-sync、cst和cmax-sync下对齐流程模型和事件日志的平均耗时分别为0.63 s、1.58 s 和2.21 s，即较之于现存的两种成本函数，所提成本函数下的对齐效率分别提升了约150.79%和250.79%。这得益于对模型和不服从日志的分割，因为分段后的对齐能够大幅缩减对齐时的搜索空间。相比之下，cmax-sync下对齐的平均耗时最高，主要因为在对齐过程中产出了大量的同步移动。上述结果说明算法2 中所提方法能够很好地提升模型与不服从日志的对齐效率。

5 结语

本文针对现存成本函数存在的问题给出了一种新的成本函数，在该成本函数下能够优先同步操作者自定义的活动类，进而得出更贴近感知成本的对齐结果；同时，基于该函数提出了一种能够提升对齐效率的算法。实验部分通过对大量对齐结果数据的分析，验证了所提函数及对应算法能够在满足准确率需求的同时提升对齐的效率。在未来的工作中，将考虑进一步提升算法的效率，以便所提方法能更好地应用于实际的问题情境中。