带里程碑活动的业务过程对齐方法

摘要

本发明公开了一种带里程碑活动的业务过程对齐方法，涉及事件数据技术领域。带里程碑活动的业务过程对齐方法，首先，将给定迹中活动映射到Petri网的变迁，构建日志模型；其次，考察日志模型与过程模型中标记为里程碑活动的变迁，进行同步合成运算；然后，找出日志模型与过程模型中其他具有相同活动的变迁，进行乘积运算；最后，给出算法在新生成的模型中查找迹与过程模型之间基于给定代价函数的最优对齐。通过实例分析，验证了该方法的可行性与优越性。实验结果表明业务过程中含有的里程碑活动越多，计算最优对齐的效率越高。

说明书

技术领域

本发明涉及事件数据技术领域，具体涉及一种带里程碑活动的业务过程对齐方法。

背景技术

近年来，伴随着事件数据的获得越来越容易，过程挖掘技术得以快速发展。过程挖掘是从事件日志中得到过程模型的关键技术，在业务过程管理中起着举足轻重的作用。许多软件商已将过程挖掘功能添加到产品套件中。过程挖掘的研究对于实施新的业务过程以及分析、改进已实施的业务过程具有重要的意义，是近年来相关领域全世界范围的研究热点。过程挖掘的基本理念主要是从事件日志中提取知识，进而发现、监控和改进实际业务过程。所谓事件日志，是指业务过程管理系统在运行过程中所积累、收集的事件执行数据，通常包含了过程的实际执行信息，如活动名称、时间戳、执行者等。过程挖掘的主要应用包括发现业务过程的控制流结构，即通过分析事件日志中记录的活动执行信息自动构造一个能够描述活动间因果依赖关系的过程模型。过程模型的建模工具种类较多，如BPMN(BusinessProcess Modeling Notation)、YAWL(Yet Another Workflow Language)、C-Nets(CausalNets)、变迁系统、过程树、Petri网等。

为了估量及评价挖掘模型的质量，需要对事件日志与过程模型之间的合规性进行检查和度量。合规性检查的基础是事件日志中迹与过程模型之间基于给定代价函数的最优对齐。寻找迹与过程模型之间最优对齐的过程本质上是一个优化问题。目前最经典的对齐方法是Arya Adriansyah等人提出的通过构造业务过程Petri网模型与迹对应Petri网模型的乘积网(product net)，然后构造乘积网的可达状态图，这样最优对齐的求解问题就转化成在可达状态图中搜索从初始状态到终止状态的最短路径问题，然后采用A*搜索算法即可解决该问题。该方法称为A*对齐方法。在最优对齐中，拟合度指标用来量化迹与过程模型中对齐活动与未对齐活动的情况。如果日志中所有的迹都可以与过程模型完全对齐，则该事件日志能够在模型上重演，其拟合度值为1。

目前已有大量文献对业务对齐方法进行了研究，考察了业务对齐方法的不同应用背景与环境，并针对不同的目的提出了一系列的改进方法，从一定程度上提高了计算最优对齐的效率，拓展了最优对齐的应用。

闻立杰教授等针对拟合度评价指标不适用于包含多实例子过程行为的模型的问题，提出了基于BPMN模型的合规性检查算法，该方法在BPMN模型基础上对子过程、多实例等复杂模式进行语义分析，设计对齐算法并在A*算法基础上计算最优对齐代价。

刘海滨教授等针对现有一致性检测技术忽略数据操作方面检测的问题，提出了一种基于Artifact快照序列的行为一致性检测方法。将Artifact行为一致性检测问题转换为语言可判定问题，检测了Artifact生命周期中服务路径的一致性。

Song Wei等提出了过程模型与事件日志之间的一种高效业务对齐方法。该方法利用迹重演及启发式规则等技术降低了查找空间的复杂度，从而提高了对齐的查找效率。该方法能够找到给定迹与过程模型之间的部分最优对齐。

Han Dong等提出一种基于关系矩阵与Petri网的过程模型与事件日志之间的业务对齐方法。该方法利用关系矩阵涵盖了事件日志中所有活动之间的因果依赖关系，并实现了矩阵中活动与模型中活动的比对，进而将对齐结果全部体现在一个变迁系统中。该变迁系统包含了事件日志中所有迹与过程模型之间的对齐。

Andrea Burattin等针对当前合规性检查技术只允许进行后验分析，即在流程实例完成之后量化(不)一致行为的数量的问题，提出了一个在线合规性检查框架。该框架不仅在执行过程中量化(不一致)行为，而且将计算限制在每个分析事件的恒定时间复杂度，从而实现了对事件流的在线分析。

Vincent Bloemen提出一种通过最大化同步移动(synchronous moves)及使用里程碑(milestones)来对齐观察行为和建模行为的方法，称之为MTCG方法。根据过程模型求解出一种数据结构，该数据结构可以用来计算带有最多同步移动的对齐，并可作为分析不符合行为的工具。

除此之外，过程挖掘领域还有更多的科技文献对业务对齐方法进行研究。通过对现有对齐方法进行分析，发现现有算法要么适用于一种特定应用场景，要么复杂度较高。

为了约束事件日志中迹的有效发生，去除事件日志中的噪音，文献BLOEMEN V,VANZELST S J,DER AALST W M,et al.Aligning observed and modelled behaviourbymaximizing synchronous moves and using milestones[J].Information Systems,2019:101456提出了里程碑活动的概念。里程碑活动指的是必须在迹中被观察到且同步被过程模型模拟的活动。不包含里程碑活动的迹，被视为噪音；而里程碑活动在过程模型运行期间也不允许被跳过。因此，里程碑活动是迹与过程模型中都必须有的活动，而且要同步。里程碑活动的引入是避免对齐过程中过程模型选择无意义执行路径的最低需求。

发明内容

本发明的目的是针对上述不足，提出了一种通过约束迹与过程模型中里程碑活动的同步发生，提高计算最优对齐的效率的带里程碑活动的业务过程对齐方法。

本发明具体采用如下技术方案：

带里程碑活动的业务过程对齐方法，包括以下步骤：

步骤1，将给定迹中活动映射到Petri网的变迁，构建日志模型；

步骤2，考察日志模型与过程模型中标记为里程碑活动的变迁，进行同步合成运算；

步骤3，找出日志模型与过程模型中其他具有相同活动的变迁，进行乘积运算；

步骤4，给出算法在新生成的模型中查找迹与过程模型之间基于给定代价函数的最优对齐。

优选地，步骤1中：根据对计算机系统中文件的操作情况构建过程模型N

在给定过程模型的基础上，指定过程模型中一些特定的活动为里程碑活动，在表示里程碑活动时采用序列的形式，既记录了所有的里程碑活动，也说明了活动之间的顺序关系；

定义里程碑活动序列，合理的里程碑活动序列是过程模型的一个完整变迁引发序列映射的活动序列的子序列；

给定迹σ

优选地，步骤2中：对于任意里程碑活动，在生成AwMA模型时，首先确定其在迹和过程模型中对应的变迁，将两个变迁视作相同变迁，进行同步合成运算，同步合成运算即将两个变迁合成为一个变迁，新生成变迁的前集为原变迁前集的并集，后集为原变迁后集的并集。

优选地，步骤3中，比对迹和过程模型中的非里程碑活动，若某活动只能在迹中被观察到，而不能在过程模型中被模拟，则该类活动为日志活动，日志活动在对齐结果中只能对应着日志移动，在生成AwMA模型时，该类活动对应的变迁也就直接转化为日志变迁；

比对迹和过程模型中的非里程碑活动，若某活动不能在迹中被观察到，但能在过程模型中被模拟，则该类活动为模型活动，模型活动在对齐结果中只能对应着模型移动；过程模型中的不可见变迁无法模拟实际活动，此类特殊情况称之为不可见活动，不可见活动在对齐结果中只能对应着不可见移动；

在生成AwMA模型时，模型活动对应的变迁转化为模型变迁；不可见活动对应的变迁就转化为不可见变迁；

比对迹和过程模型中的非里程碑活动，若某活动既能在迹中被观察到，又能在过程模型中被模拟，则该类活动为同名活动，在生成AwMA模型时，迹中活动需与模型中活动进行乘积运算，以保证所有可能对齐结果都考虑到在生成AwMA模型时，迹中活动需与模型中活动进行乘积运算，以保证所有可能对齐结果都考虑到；

根据日志模型、过程模型和里程碑活动序列生成AwMA模型；

优选地，步骤4中，加权Petri网中查找代价值最小的变迁引发序列，采用了最直观的查找方式，在查找过程中采用了宽度优先的搜索算法，本算法是NP-hard问题，其时间复杂度与Petri网的复杂情况及其可达状态数有关。

本发明具有如下有益效果：

本方法通过约束迹与过程模型中里程碑活动的同步发生，很大程度上提高了计算最优对齐的效率。该方法给出了AwMA方法的详细算法，并通过一个例子对该方法的具体执行过程进行了描述。最后，通过对一个煤矿斜巷进路建立的实例的分析，说明了该方法的优越性。本方法和MTCG方法等比较，无需生成Petri网的可达图，因此不存在状态空间爆炸的问题。

附图说明

图1为带里程碑活动的业务过程对齐方法的执行流程图；

图2为过程模型N

图3为日志模型N

图4为里程碑活动对应变迁的同步合成运算示意图；

图5为日志活动对应变迁的转换示意图；

图6为模型活动及不可见活动对应变迁的转换示意图；

图7为同名活动对应变迁的乘积运算示意图；

图8为基于过程模型N

图9为查找过程中一条有效的最短路径；

图10为煤矿斜巷进路建立的Petri网模型N

具体实施方式

下面结合附图和具体实施例对本发明的具体实施方式做进一步说明：

本方案主要介绍和研究内容相关的基础知识，包括多重集、迹、Petri网、对齐和最优对齐等，为后期工作的叙述与展开做好准备。

多重集是包含相同元素多次的无序集合。给定集合S，其上的一个多重集记作β(S)。例如，集合S＝{a,b,c,d}，β(S)＝[a

迹是一个事件的有序列表，即序列，记作σ＝<σ[1],σ[2],…,σ[|σ|]>。其中，|σ|表示迹中活动的个数，即迹的长度。符号

Petri网是一种数学形式的建模语言，其为描述进程的有效手段，并能够以相对紧凑的方式表示并行行为。Petri网由两种互不相交的结点组成，分别称之为库所和变迁。从库所到变迁或从变迁到库所的有向连线称作弧，即流关系。Petri网的状态称作标识。

将经典Petri网的每一个变迁都关联一个标签，则构成标签Petri网。标签的作用是为Petri网中每一个变迁分配一个相应的活动名称。实际业务中的活动一旦映射到变迁上，则变迁与活动之间就相互一一对应起来。在不产生混淆的情况下，将标签Petri网简称为Petri网。

定义1(Petri网)Petri网是一个元组N＝(P,T；F,α,m

①P是一个有限库所集合；

②T是一个有限变迁集合，且

③

④α:T→A

⑤

⑥

标识被定义为库所的多重集，表示令牌在Petri网中的分布情况。根据流关系，借助标识之间的可达关系，接下来对变迁的发生规则进行描述。任意可达状态

①对于任意变迁t∈T，若

②如果m[t＞，那么在标识m下，变迁能够引发。标识m下，引发变迁t后得到一个新标识m′，记作m[t＞m′，

从状态m可达的一切状态的集合记作R(m)，且规定m∈R(m)，则R(m

在Petri网模型上重演事件日志中的迹时，可能会出现二者不完全拟合的情况。不拟合的活动一般称为偏差，对齐能够找到不拟合活动，进而对偏差进行标记。

定义2(对齐)给定A是一个活动集合。σ∈A

①π

②

上述定义中，符号“>>”代表无移动，A

对于对齐中任意一个二元组(a,t)∈γ，对(a,t)进行如下划分：

①若a∈A且t＝>>，则称之为日志移动；

②若a＝>>且t∈T，则称之为模型移动；

③若a∈A且t∈T，则称之为同步移动；

④若a＝>>且α(t)＝τ，则称之为不可见移动；

⑤否则，称作非法移动。

根据里程碑活动的含义，里程碑活动在对齐中必定为同步移动。由定义2可知，迹和过程模型之间的对齐是一个由移动组成的序列。移动为迹中的活动和模型中的行为建立起关联关系。其中，日志移动是指迹中观察到的活动不允许在模型上进行模拟；模型移动是指由模型运行产生的行为却未在迹中观察到；同步移动是指迹中的活动与模型中的行为一一对应；不可见移动可以由模型运行产生，但是不会产生任何活动，因此也无需在迹中被观察。日志移动和模型移动说明了迹与过程模型之间的不拟合，体现了对齐中的偏差。

给定一条迹与过程模型，可能会有多个不同的对齐结果。为了得到最合乎需求的对齐结果，应该为每一类移动赋予一个特定代价函数值c((a,t))。在给定代价函数的约束下，且确保里程碑事件都同步的情况下，计算出的代价值最小的对齐就是最优对齐。给定代价函数c((a,t))的取值情况直接决定了迹σ与过程模型N之间的一个最优对齐集合。

指定里程碑活动的最优对齐和通常情况下的最优对齐是不同的。通常情况下的最优对齐只需保证代价值最小。而指定里程碑活动后所求得的最优对齐有可能代价值并非最小，其首先必须保证里程碑活动都按顺序发生，然后再保证代价值最小。

在本方案中，代价函数采用标准似然代价函数lc((a,t))。该函数为各类移动分配代价值的情况如下：日志移动和模型移动的代价值均为1，而同步移动和不可见移动的代价值为0。

带里程碑活动的业务过程对齐方法，包括以下步骤：

步骤1，将给定迹中活动映射到Petri网的变迁，构建日志模型。

根据对计算机系统中文件的操作情况构建过程模型N

模型N

在给定过程模型的基础上，指定过程模型中一些特定的活动为里程碑活动。例如，指定该事件过程中活动a和b为里程碑活动。里程碑活动的指定在该流程中的含义为不允许系统中找不到所需文件，而且一个合理的观察流程中必须包含打开文件和解析文件两个操作。因为里程碑活动之间的先后发生顺序是一定的，所以在表示里程碑活动时采用序列的形式，既记录了所有的里程碑活动，也说明了活动之间的顺序关系。

定义里程碑活动序列，合理的里程碑活动序列是过程模型的一个完整变迁引发序列映射的活动序列的子序列；给定A是一个活动集合，N＝(P,T；F,α,m

定义说明，合理的里程碑活动序列应该是过程模型的一个完整变迁引发序列映射的活动序列的子序列。如本例中，里程碑活动包含a和b，其可构成序列Y

给定迹σ

定义AwMA标准，给定A是一个活动集合，σ∈A

AwMA标准是考察事件日志中的迹能否采用AwMA方法进行对齐的依据，是对对齐条件判断的形式化描述。当给定的迹符合AwMA标准时，采用AwMA方法对其进行对齐；否则，将给定迹作为噪音从事件日志中清除。例如，迹

接下来，将迹σ

模型N

步骤2，考察日志模型与过程模型中标记为里程碑活动的变迁，进行同步合成运算，对于任意里程碑活动，在生成AwMA模型时，首先确定其在迹和过程模型中对应的变迁，将两个变迁视作相同变迁，进行同步合成运算，同步合成运算即将两个变迁合成为一个变迁，新生成变迁的前集为原变迁前集的并集，后集为原变迁后集的并集。

对照业务过程的里程碑活动序列，比对过程模型与日志模型之间的活动，发现二者之间的活动存在以下几种情况：(1)里程碑活动；(2)日志活动；(3)模型活动；(4)同名活动；(5)不可见活动。其中，日志活动、模型活动、同名活动和不可见活动均为非里程碑活动。显然，里程碑活动属于同步移动。另外，除了里程碑活动外，还有一类活动，其可能既存在于日志模型中也存在于过程模型中，但在实际对齐时二者却未必能够同步，在此将这类活动称之为同名活动。不可见活动是过程模型中所特有的一种活动，不可能出现在日志模型中，因此其运算规则和模型活动相同。

针对不同的活动，在生成AwMA模型时，应该采取不同的处理措施。接下来，根据给定过程模型和日志模型，针对不同的活动类型，描述二者之间的AwMA模型的生成过程。

通常情况下，日志模型记作N

(1)里程碑活动

里程碑活动是指既必须在迹中观察到的活动，又必须由过程模型同步模拟的活动。该类活动在对齐结果中必然对应着同步移动。指定的里程碑活动序列中的所有活动，均为里程碑活动。对于任意里程碑活动，在生成AwMA模型时，首先确定其在迹和过程模型中对应的变迁，将两个变迁视作相同变迁，进行同步合成运算即可。所谓同步合成运算，就是将两个变迁合成为一个变迁。新生成变迁的前集为原变迁前集的并集，后集为原变迁后集的并集。该同步合成操作示意图如图4所示。

迹与过程模型中活动a属于里程碑活动的判断条件为：

算法1：里程碑活动的同步合成运算。

输入：里程碑活动a；

输出：新生成变迁及其流关系。

1.T

2.α

3.

4.

步骤3，找出日志模型与过程模型中其他具有相同活动的变迁，进行乘积运算；比对迹和过程模型中的非里程碑活动，若某活动只能在迹中被观察到，而不能在过程模型中被模拟，则该类活动为日志活动，日志活动在对齐结果中只能对应着日志移动，在生成AwMA模型时，该类活动对应的变迁也就直接转化为日志变迁。

比对迹和过程模型中的非里程碑活动，若某活动不能在迹中被观察到，但能在过程模型中被模拟，则该类活动为模型活动，模型活动在对齐结果中只能对应着模型移动，过程模型中的不可见变迁上的移动，称之为不可见活动，不可见活动在对齐结果中只能对应着不可见移动。

在生成AwMA模型时，模型活动对应的变迁转化为模型变迁；不可见活动对应的变迁就转化为不可见变迁。

比对迹和过程模型中的非里程碑活动，若某活动既能在迹中被观察到，又能在过程模型中被模拟，则该类活动为同名活动，在生成AwMA模型时，迹中活动需与模型中活动进行乘积运算，以保证所有可能对齐结果都考虑到在生成AwMA模型时，迹中活动需与模型中活动进行乘积运算，以保证所有可能对齐结果都考虑到。

根据日志模型、过程模型和里程碑活动序列生成AwMA模型。

比对迹和过程模型中的非里程碑活动，若某活动只能在迹中被观察到，而不能在过程模型中被模拟，则该类活动为日志活动。日志活动在对齐结果中只能对应着日志移动。在生成AwMA模型时，该类活动对应的变迁也就直接转化为日志变迁。其生成日志变迁示意图如图5所示。

迹与过程模型中活动属于里日志活动的判断条件为：

算法2：日志活动的转换运算。

输入：日志活动a；

输出：新生成变迁及其流关系。

1.T

2.α

3.

4.(t

比对迹和过程模型中的非里程碑活动，若某活动不能在迹中被观察到，但能在过程模型中被模拟，则该类活动为模型活动。模型活动在对齐结果中只能对应着模型移动。过程模型中的不可见变迁上的移动，称之为不可见活动。不可见活动在对齐结果中只能对应着不可见移动。

注意：虽然模型移动和不可见移动在形式和运算规则上相同，但是二者的实际含义有很大的区别。模型移动是一类只能在过程模型中建模并应该被记录下来，但是无法在迹中观察到的行为；而不可见移动是一类在过程模型中建模也不会被记录下任何活动的行为，因此这类行为根本无法存在于迹中，而且即使无法在迹中观察到也是拟合的一种行为。

在生成AwMA模型时，模型活动对应的变迁也就直接转化为模型变迁；不可见活动对应的变迁就直接转化为不可见变迁。其生成模型变迁示意图如图6所示。

迹与过程模型中活动属于里模型活动的判断条件为：

算法3：模型活动及不可见活动的转换运算。

输入：模型活动或不可见活动a；

输出：新生成变迁及其流关系。

1.T

2.α

3.

4.(>>,t

比对迹和过程模型中的非里程碑活动，若某活动既能在迹中被观察到，又能在过程模型中被模拟，则该类活动为同名活动。同名活动虽然在迹和过程模型中都存在，但是二者在发生时未必是同步的。因此，同名活动在对齐结果中可能对应着日志移动、模型移动或者同步移动中的一个或多个。在生成AwMA模型时，迹中活动需与模型中活动进行乘积运算，以保证所有可能对齐结果都考虑到。其生成进行乘积运算的示意图如图7所示。

迹与过程模型中活动属于里同名活动的判断条件为：

算法4：同名活动的转换运算。

输入：同名活动a；

输出：新生成变迁及其流关系。

1.CALL Algorithm 1；//生成新的同步变迁，并确定其流关系

2.CALL Algorithm 2；//生成新的日志变迁，并确定其流关系

3.CALL Algorithm 3；//生成新的模型变迁，并确定其流关系

对迹与过程模型中不同活动进行分类分析，并描述不同活动在生成AwMA模型时应采取的处理方式后，给出根据给定日志模型、过程模型和里程碑活动序列生成AwMA模型的整个过程，见算法5。

算法5：根据日志模型、过程模型和里程碑活动序列生成AwMA模型。

输入：日志模型N

输出：AwMA模型N

该算法主要包含两个顺序的最外层循环，其中第一个循环是对里程碑活动进行处理。该部分的执行时间主要用来确定里程碑活动在日志模型和过程模型中分别对应的变迁，其时间复杂度为O(|T

以图2所示的过程模型N

模型N

步骤4，给出算法在新生成的模型中查找迹与过程模型之间基于给定代价函数的最优对齐。

加权Petri网中查找代价值最小的变迁引发序列，采用了最直观的查找方式，在查找过程中采用了宽度优先的搜索算法，本算法是NP-hard问题，其时间复杂度与Petri网的复杂情况及其可达状态数有关。

给定迹与过程模型，根据算法5可以得到迹对应的日志模型与过程模型之间的AwMA模型。通过该模型的构建，可以将迹中活动的观察情况、过程模型中活动的建模情况以及二者之间所有可能的比对结果都体现在了AwMA模型的变迁上。AwMA模型的变迁可以分为四类，分别为同步变迁，形如(t

本文采用标准代价函数作为衡量不同移动代价的标准，即日志移动和模型移动的代价值为1，而同步移动和不可见移动的代价值为0。AwMA模型中的变迁与移动之间满足一一对应的关系，可以将移动的代价函数作用到变迁。即日志变迁和模型变迁的代价值为1，而同步变迁和不可见变迁的代价值为1。这样，AwMA模型就演化为带代价函数的模型。

AwMA模型中变迁一旦关联了代价值后，每当变迁引发时，便会产生一个代价值。将模型从初始标识运行到结束标识的引发序列中所有变迁的代价值叠加起来，可以得到一个完整变迁引发序列的代价值。该值就是迹与过程模型之间一个对齐的代价值。迹与过程模型之间的最优对齐的查找就转化为在AwMA模型中搜索代价值最小的引发序列的问题，有效解决方法就是状态空间搜索法。而计算最小代价引发序列可以采用计算最短路径的思路进行求解。基于AwMA模型，计算最优对齐的具体过程见算法6。

算法6：根据AwMA模型，计算迹与过程模型之间的一个最优对齐。

输入：AwMA模型N

输出：一个最优对齐γ。

算法6的主要算法思想为在加权Petri网中查找代价值最小的变迁引发序列。本算法采用了最直观的查找方式。为了保证得到的第一个完整变迁引发序列就是代价最小的，在查找过程中采用了宽度优先的搜索算法。本算法是NP-hard问题，其时间复杂度与Petri网的复杂情况及其可达状态数有关。

以图8所示的AwMA模型N

根据算法6，在考察AwMA模型的可达状态时，最后一个结点包含的可达状态为模型的结束状态，其意味着找到了一个最优对齐。该结点的代价值就是最优对齐的代价值，该结点的变迁引发序列就是最优对齐对应的变迁序列。如图9所示，在给定Y

另外，要注意当过程模型中存在完全由不可见变迁及库所组成的循环时，可能会造成算法6进入死循环。此时，有效的解决方案是修正标准似然代价函数，为不可见移动赋一个比较小的数为其代价值，不再为其赋0值。但该值要远小于日志移动和模型移动的代价值，以免在对齐时放弃不可见变迁而选择日志变迁或模型变迁，保证其对有效路径不会造成致命的影响，如0.1等。

给定过程模型、迹、里程碑活动序列和代价函数，可以得到一个AwMA模型及一个最优对齐。在众多的对齐方法中，考虑了里程碑活动对对齐影响的方法，最经典的是MTCG方法。但是该方法在求解过程中要计算Petri网的可达状态图，导致该方法无法计算复杂模型的对齐，而且具有较高的复杂度。对于解决实际问题的迹与过程模型的对齐，MTCG方法具有一定的局限性。

除此之外，AwMA方法和其他传统的对齐方法的区别在于考虑了里程碑活动对齐对齐过程及结果的影响。尤其，当里程碑活动数为0时，即不指定里程碑活动时，AwMA方法无需进行里程碑活动对应变迁的同步合成运算。只需对日志模型与过程模型中的活动进行比对，然后对其进行乘积运算即可。在这种情况下，AwMA算法的执行过程和A*对齐方法一样。因此，A*对齐方法是AwMA方法的一种特殊情况。

以某煤矿系统的斜巷运输业务流程为例，人工构建过程模型。为了提高煤矿运输的安全性，分析了一种基于PLC的煤矿斜巷分布式控制系统。并采用Petri网建立系统模型，模拟煤矿斜巷进路的建立过程。过程模型N

熟悉业务过程后，可以得到相应的事件日志。根据过程模型生成包含活动数不同的完全拟合的迹，之后加入噪音形成不完全拟合的迹。噪音是通过随机添加、删除迹中的活动而引入的。噪音比noise＝d/|σ

本发明主要根据过程模型N

表1

本实例分析中共生成4个事件日志，每个事件日志中包含5条不同的迹。4个事件日志中5条迹的平均长度分别为10、15、20、25。考察里程碑活动数分别为0、1、2、3、4、5时，AwMA模型中库所数、变迁数以及流关系数的变化情况，分别如表2-4所示。

表2

表3

表4

从表2中可以看出，当迹的平均长度相同时，无论指定的里程碑活动个数为多少，AwMA模型的库所数都保持不变。在迹的平均长度相同的情况下，使用的是同一事件日志集。也就是，即使指定的里程碑活动数在变化，但是参与运算的迹都是一样的。表2中显示的结果和算法5的基本算法思想是一致的。即无论里程碑活动的个数为多少，AwMA模型的库所集合是日志模型与过程模型库所集合的并集。

从表3中可以看出，当迹的平均长度相同时，随着指定里程碑活动个数的增加，AwMA模型的库所数逐渐减小，而且其变化的幅度符合线性递减的规律。该变化规律同样可以根据算法5中进行解释。当一个活动既可以在迹中观察到，也可以在过程模型中进行模拟时，该活动极有可能对应着一个同步移动。如果将其作为里程碑活动处理，那么日志模型和过程模型中对应的变迁要做同步合成运算，该运算结果在AwMA模型中增加一个同步变迁，而删除一个日志变迁和一个模型变迁，因此最终使得AwMA模型中的变迁数减1。反之，如果不将其作为里程碑活动处理，则活动为同步活动，日志模型和过程模型中对应的变迁要做乘积运算，该运算结果在AwMA模型中增加一个同步变迁，不删除任何变迁，因此最终使得模型中的变迁数加1。综上所述，同一条迹与过程模型在计算AwMA模型时，指定的里程碑活动数越多，则AwMA模型中的变迁数越少。而且随着里程碑活动数的增加，AwMA模型中变迁数线性递减。

从表4中可以看出，当迹的平均长度相同时，随着指定里程碑活动个数的增加，AwMA模型的流关系数逐渐减小，而且其变化的幅度同样符合线性递减的规律。产生这一结果的原因不仅和算法5的运算特点有关系，而且和图10中给出的过程模型N

综上所述，基于给定代价函数计算同一条迹和过程模型之间的最优对齐时，指定的里程碑活动数越多，AwMA方法生成的搜索空间越小。搜索空间的减小，势必会提高最优对齐的计算效率。当指定的里程碑活动数为0时，AwMA方法退化为A*对齐方法。因此，AwMA方法比A*对齐方法的效率更高、适用范围更广，性能优于A*对齐方法。

合规性检查在信息管理系统中扮演着越来越重要的角色。对齐是最先进和最全面的合规性检查之一。通过对齐方法，可以得到基于代价函数的迹与过程模型之间的最优对齐。最优对齐的结果可以应用于过程挖掘的各个方面。然而，现有的对齐方法产生的搜索空间过大，严重影响了最优对齐的搜索效率。业务过程中里程碑活动的引入，为对齐方法效率的提高带来了新的希望。通过里程碑活动不仅可以有效去除事件日志中的噪音，而且可以进一步约束过程模型中合法变迁的引发。

本文提出一种带里程碑活动的业务过程对齐方法，简称为AwMA方法。通过约束迹与过程模型中里程碑活动的同步发生，很大程度了提高了计算最优对齐的效率。本文给出了AwMA方法的详细算法，并通过一个例子对该方法的具体执行过程进行了描述。最后，通过对一个煤矿斜巷进路建立的实例的分析，说明了该方法的优越性。另外，本方法和MTCG方法等比较，无需生成Petri网的可达图，因此不存在状态空间爆炸的问题。

在今后的工作中，将进一步对该方法进行分析及应用，拓展该方法的应用领域。将要开展的工作主要包括：①AwMA方法在生成新模型时，借助了Petri网的同步合成运算和乘积运算，这两种运算的性质已有大量文献进行了证明。但生成AwMA模型时，同时运用两种运算，还能否保证其活性、有界性、无死锁等性质，还有待进一步研究。AwMA模型的活性及无死锁性是AwMA方法正常运行的保障，应该给出理论证明；②该方法可以进一步进行优化，因为里程碑活动的引入，导致过程模型中有些变迁永远都不可能引发，因此在使用AwMA方法前，可以先对过程模型进行预处理，将不包含里程碑活动的分支进行修剪，从而进一步减小搜索空间，提高计算最优对齐的效率；③可以进一步对算法6进行拓展，提出一种基于AwMA模型计算迹与过程模型之间所有最优对齐的算法，并对所有最优对齐进行分类，从而研究迹与过程模型之间偏差的情况。

当然，上述说明并非是对本发明的限制，本发明也并不仅限于上述举例，本技术领域的技术人员在本发明的实质范围内所做出的变化、改型、添加或替换，也应属于本发明的保护范围。