基于混合型事件日志的模型合规性检验方法∗

尚庆民 宋 巍

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

作为过程挖掘领域一项不可忽视的技术，合规性检验旨在分析发现的过程模型所捕获行为和事件日志所描述行为的差异性［1～2］。合规性检验的输入为事件日志及其对应的过程模型，其中事件日志是事件序列的集合，并且是过程发现技术的输入［3］。现实中大部分事件在执行过程会持续一段时间，即区间事件，因此该事件的开始和结束信息都会被系统记录在事件日志中［4～5］，然而，瞬时完成事件的开始和结束会被合并记录成一个点事件。因此，现实中的事件日志大部分是包含点事件和区间事件的混合型事件日志。

现有过程挖掘合规性检验方法不能直接应用到混合型事件日志。Cook 等最早提出通过比较事件日志和过程模型分别生成的事件流进行合规性检验的方法，为后来的合规性检验技术发展奠定了基础［6］。随后的十几年里，很多学者提出不同方法从不同方面进行合规性检验［7～8］。现有研究主要从拟合度、精确度和简洁度几个方面分析过程模型与事件日志的合规性。然而现有方法都是针对只包含点事件的事件日志进行分析［9～12］，当这些方法应用到混合型事件日志时，由于区间事件的开始事件和结束事件在事件日志重放过程中重复出现，导致合规性检验结果不够准确。

针对现有技术的不足，本文提出一种针对混合型事件日志及其对应的过程模型进行合规性检验的方法，从拟合度、精确度和简洁度三个方面衡量模型与事件日志的合规性。通过对事件日志重放计算令牌变化以计算拟合度，通过比较事件日志和过程模型分别包含的事件关系计算精确度，通过比较事件日志和过程模型分别包含的变迁数量计算简洁度，最后整合三个指标，计算出合规性检验结果值F1。我们实现原型工具HCC 并通过案例分析验证本文方法的有效性。

2 相关概念

2.1 过程模型

Petri 网是支持并发语义的建模语言，由库所、变迁和令牌等基本元素组成。 其形式化定义如下。

定义1（Petri网）Petri网是一个三元组PN=（P，T，F）：

·P是库所有限集合；

·T是变迁有限集合，并且满足P∩T=∅；

·F ⊆（P×T）∪（T×P）是被称为流关系的有向弧的有限集合。

对于任一节点z∈P∪T，·z=｛y|＜y，z>∈F｝，并且z·=｛y|＜z，y>∈F｝。Petri网引入令牌表示当前状态，如果变迁t能够消耗每个·t库所的一个令牌，并且在每个t·中产生一个新的令牌，则表示变迁t 在当前状态下是使能的。Petri 网可用来表示业务过程模型，其中变迁表示活动，库所和边表示活动间的控制流关系。本文与现有多数过程挖掘工作［13～14］一致，采用Petri 网表示业务过程模型，所用过程模型拥有唯一源库所Pi∈P（·Pi=∅）和唯一终止库所Po∈P（Po·=∅），每一个库所和变迁都在从Pi到Po的路径上。

2.2 事件日志

信息系统的业务过程PN 包含多个活动，这些活动的生命周期有三类，对于区间活动，其开始和结束通常会被记录成两个有不同生命周期的事件，对于瞬时完成的活动，开始和完成通常会合并记录成一个点事件。业务过程PN 可执行多次，每次执行产生一条事件序列，多条事件序列组合构成该系统的事件日志。假设业务活动集合为T，T*表示基于T的所有可能发生的事件序列集合。

定义2（事件序列）业务过程PN=（P，T，F）的一条事件序列σ∈T*用一组符号t1t2… tn表示，其中ti=x（1 ≤i ≤n）表示事件ti为瞬时活动x（x∈T），ti=ys（ye）表示事件ti为区间活动y（y∈T）的开始事件（完成事件）。

定义3（事件日志）业务过程PN=（P，T，F）对应的事件日志L是事件序列的多重集，即L∈（T*）*，本文所用日志是以xes格式描述的事件日志［14］。

图1 业务过程PN

图1 所示是一个业务过程PN，黑色填充的变迁表示区间事件，无填充的表示瞬时事件，又称为点事件。表1 是该业务过程的一个事件日志L，该事件日志包含几条事件序列，每条事件序列记录了业务过程执行的事件顺序，其中由于σ5存在事件移位导致L与PN不完全相符。

表1 事件日志

2.3 过程挖掘的合规性检验

合规性检验，又称为合规性分析，是检测事件日志与对应的过程模型之间的匹配的程度，并用一定的指标去量化［7］。本文的合规性检验方法用三个指标量化，即拟合度、精确度、和简洁度。其中拟合度是指事件日志的序列在过程模型中重现的程度，重现程度越高，则拟合度越高；精确度是指过程模型是否描述了日志包含的事件序列之外的行为，描述的事件日志之外行为越多，则精确度越低；简洁度是指模型应该足够简洁，不能包含事件日志之外的多余事件［14～16］。

表2列举了本文的符号、算法中的单词及其含义。

表2 符号对应表

3 基于混合型事件日志的模型合规性检验方法

3.1 拟合度计算

在混合型事件日志中，每个区间事件在事件序列中对应一个开始事件和一个结束事件，进行日志重放的过程中，由于模型中并发的存在，需考虑所有并发的结束事件都完成之后才能使能后续的事件，这使得传统日志重放算法不能直接应用于混合型事件日志。

本文与经典算法［17］采用相同思想，基于令牌计算合规性检验的拟合度，对日志中的事件序列基于模型进行重放。首先在初始库所生成一个令牌，之后执行该库所之后的事件，消耗库所中的令牌，当该事件执行完成后，该事件之后的库所才能产生令牌，与经典算法不同的是，若事件为区间事件，则应在其compete事件执行完成之后才生成令牌。在事件日志重放过程中，若序列中要执行的事件之前的库所缺乏令牌，则人为添加并记录，统计出重放过程令牌情况及次数，然后计算拟合度。事件日志包含的事件序列数量用k 表示，重放过程中生成的令牌数用p 表示，缺失的令牌数用m 表示，剩余的令牌数用r 表示，自然消耗的令牌数用c 表示，拟合度的计算表达式如式（1）所示。

算法1 旨在计算事件日志与过程模型的拟合度，第1～2 行是对事件日志中每条序列的起始库所生成一个令牌，第3～25 行是事件日志重放的过程，其中第4～8 行是对区间事件的开始事件重放，判断前驱库所是否有token，没有则人为添加，m 加1，之后消耗c加1，前驱库所令牌数置零，第9～25行是对点事件和区间事件的结束事件进行重放，重放结束后右侧库所产生令牌，第19～25 行是对后继事件是否为不可见事件的判断，若为不可见事件则不需要重放，第26～29 行是当前序列重放完成计算剩余令牌数量，第30～31行是计算拟合度并返回结果。

算法1：日志重放算法

输入：事件日志L，过程模型P。输出：拟合度结果f。

用n 表示事件日志L 包含的事件序列的条数，m 表示每条事件序列包含的事件的平均值，用k 表示模型P 中每个变迁对应前驱库所及后继库所的平均值，用h 表示模型中每个库所对应的后继变迁的平均值，则算法1 在最坏情况下的时间复杂度为O（m×n×h×k2），相对于m 和n 来说，h 和k 的值是非常小的。

3.2 精确度计算

在混合型事件日志中，对于区间事件t，对应一个开始事件和一个结束事件，对于两个并发事件t1和t2，其可能发生的事件序列如表3所示，对于点事件t3和t4，其并发事件序列只有两种｛t3，t4，t4，t3｝，由于区间事件的开始和结束事件的同时存在，使得精确度计算比只针对包含点事件日志的合规性检验更复杂，传统的合规性检验算法不能准确计算混合型事件日志的精确度。本文提出的精确度衡量方法，通过比较事件日志的事件关系和过程模型的事件关系来计算。

在过程模型和事件日志中，活动的发生遵循一定的规则，他们在过程模型和事件日志中的关系都可以分别通过某种方式获取。在计算精确度时，过程模型中的描述的行为比事件日志中记录的行为可能要多，以基于事件日志的关系为基准。用PL表示事件日志包含的并发和因果关系集合，PM 表示过程模型包含的并发和因果关系集合，合规性检验的精确度计算表达式如式（2）所示。

表3 并发事件序列集合

日志中对并发关系和因果关系的判断如下：

1）直接优先关系（>）。当事件序列内两个事件ti和tj同时满足以下五个条件：（1）ti=x 或ti=xe；（2）tj=y 或tj=ys；（3）不存在p，i＜p＜j，tp=z；（4）不存在k，i＜k＜j，ti=zs；（5）不存在p，i＜l＜j，tl=ze；则x>y；

2）相交关系（|）。当事件序列内几个事件ti，tj，tp，tq满足以下条件中任意一个：（1）ti=xs，tj=xe，tp=ys，tq=ye，且p＜i＜q 或i＜p＜j；（2）ti=ys，tj=ye，tp=x，且i＜k＜j，则x|y，y|x；

3）因果关系（→）。对于事件x 和y，若x>y，y≯x，且非x|y，则x→y；

4）并发关系（||）。对于事件x和y，若x|y，或x>y且y>x，则x||y。

算法2旨在挖掘过程模型中的因果关系和并发关系。第1 行对集合进行初始化，第2～3 行是遍历模型中的边，第4～6 行是求过程模型中的因果关系，第7～20 行是求过程模型中的并发关系，第21行，返回过程模型的因果关系和并发关系集合。用m 表示过程模型PN 中包含的弧的个数，用n 表示并发事件关系的数量，则算法2 在最坏情况下的时间复杂度为O（m2×n2）。

算法2：模型并发和因果关系判断算法

输入：过程模型PN。

输出：PN包含的并发关系Cc，因果关系Cs。

3.3 简洁度计算

本文比较过程模型中事件的数量和事件日志中包含的不同事件的数量来计算模型的简洁度，用LT 表示事件日志中不同的事件集合，用MT 表示过程模型中的所有事件的集合，MT"表示去重后过程模型中的事件集合，令ST=LT∩MT"表示LT 和MT"的相同变迁的个数，简洁度的计算表达式如式（3）所示。

即

算法3旨在计算混合型事件日志合规性检验的简洁度。第1 行对集合进行初始化，第2～4 行是遍历过程模型的事件集合和事件日志的事件集合，找到相同的事件则添加到集合ST中，第6行是计算结果，第7 行返回合规性检验的简洁度。用m 表示LT 中变迁个数，用n 表示MT"中变迁个数，则算法3在最坏情况下的时间复杂度为O（m×n）。

算法3：简洁度计算

输入：混合型事件日志变迁集合LT，过程模型变迁集合MT"。

输出：简洁度结果s。

3.4 合规性检验结果综合计算

为各个指标设置权重，求出最终的合规性检验结果。设拟合度f、精确度p、简洁度s的权重分别为a，b，c，计算表达式如式（4）所示。

4 工具

4.1 实现

为评估本文方法的有效性，我们在Eclipse 集成开发环境中使用Java语言实现原型工具HCC，工具的总体架构如图2所示。主要包含模块有：

1）输入解析模块。工具的输入是xes 格式描述的事件日志文件和pnml 格式的Petri 网模型，对于事件日志的解析是借助第三方类库dom4j 将其解析为事件序列的数据结构，对于过程模型的解析是将过程模型包含的变迁、库所及其对应的关系解析为模型的数据结构。

2）合规性指标计算模块。对事件日志基于过程模型进行重放，记录重放过程产生、缺失、剩余及消耗的令牌数，根据式（1）计算出合规性检验的拟合度；分别整合事件日志和过程模型对应的事件关系集合，根据式（2）计算出合规性检验的精确度；分别统计过程模型缺少和重复的事件数量，以及过程模型和事件日志分别包含的事件总数，根据式（4）计算出合规性检验的简洁度。

3）合规性检验结果计算及视图模块。给计算出的拟合度、精确度和简洁度设置不同权重，计算出合规性检验的最终结果并输出到控制台中。

图2 HCC总体架构

4.3 案例分析

由于缺乏准确的指标衡量各合规性检验方法的准确性，因此我们进行案例分析，通过对图1 所示过程模型及表1 的事件日志进行合规性检验来衡量本文所提方法的有效性。图3 可视化地展示了该案例的运行结果。下面将对本文所提方法应用于该案例进行合规性校验过程进行详细分析。

首先进行拟合度分析，根据算法1，对表1所示事件日志中的事件序列σ1进行重放，在库所Pi中生成一个令牌，生成令牌数p加1，接着读入点事件t1，判断其前驱库所Pi有令牌，则执行t1，Pi令牌个数置零，消耗令牌数c 加1，并在其后继库所p1生成令牌，p 加1；读入事件t2s，其前驱库所p1有令牌，则执行t2，p1令牌数置零，c 加1，令t（t2）=1，表示t2正在执行；读入事件t2e，判断t（t2）=1，则执行t2e，令t（t2）=0，表示t2执行完成，并在其后继库所p2生成令牌，p 加1；后续事件执行与其一致，需注意的是事件t4和t5的complete事件都完成后，库所p5和p6才会有令牌，t6才能执行，否则需人为添加令牌；对σ1持续重放直到t8执行完成，可得该序列重放过程中不需要认为添加或删除令牌。对表1 中剩余序列进行重放，事件日志重放完成后得到拟合度结果如图3 所示。需要注意的是，σ5由于存在事件移位，重放时需人为添加并消除令牌，若将此事件序列中的区间事件只保留开始或结束事件，则现有的合规性检验方法可应用于此事件序列，而由于部分开始或结束事件的舍弃，可能导致现有方法无法检测出该事件序列不能完整重放，从而无法得出正确的拟合度结果。

拟合度计算完成后，计算事件日志与模型的精确度，根据3.2中的定义，可以求得事件日志包含的因果 关 系 有｛t1→t2，t2→t3，t2→t7，t3→t4，t3→t5，t4→t6，t5→t6，t6→t8，t7→t8｝，并发关系有｛t4|| t5，t6|| t8｝；根据算法2 求得模型的因果关系有｛t1→t2，t2→t3，t2→t7，t3→t4，t3→t5，t4→t6，t5→t6，t6→t8，t7→t8｝，并发关系有｛t4||t5｝，根据式（2），可以求出合规性检验的精确度为1。

根据算法3 计算模型与事件日志合规性检验的简洁度，事件日志包含的事件集合为｛t1，t2，t3，t4，t5，t6，t7，t8｝，模型包含的事件集合与其一致，可以求得合规性检验的简洁度为1。

最后，将拟合度f、精确度p、简洁度s 的权重都设置为1，可得合规性检验结果F1 如图3 所示。通过该案例分析可得，本文所提的方法可以对混合型事件日志及对应过程模型有效地进行合规性分析，即使在过程模型与事件日志不完全相符的情况下，也能够对合规性进行适度的衡量。

我们将该实例运行在Inter（R）3.40GHz 处理器，8GB 内存的Windows10 系统的台式机上。为了有效判断算法效率，我们将表1 所示的事件日志扩大十倍进行计算，经过100 次计算，统计得到合规性检验耗时104ms，表现了算法具有较高的效率。

图3 基于混合型事件日志的模型合规性检验工具HCC

5 结语

本文提出一种针对混合型事件日志及其对应的过程模型进行合规性检验的方法，通过三个评价指标综合评判日志和模型的合规性。该方法可直接应用于包含点事件和区间事件的混合型事件日志，同时又适用于只包含点事件和只包含区间事件的事件日志，我们将该算法实现在原型工具“HCC”中，并通过案例分析阐明了算法的有效性。