基于Petri网基本结构的过程模型修复方法

摘要

本发明公开了一种基于Petri网基本结构的过程模型修复方法。该修复方法主要通过对原有数据进行处理，使其成为符合规范的事件日志；之后对其使用归纳挖掘算法挖掘出对应的过程模型；通过将扩大的事件日志与挖掘得到的过程模型进行校准，发现过程模型中存在的偏差；最后提出了不同结构下过程模型的修复方案，旨在修复过程模型，增强过程模型的一致性。在选择结构中，对日志动作和模型动作相邻这种情况进行了特殊修复，提出的修复算法在保证拟合度、精确度的同时，也提高了过程模型的简化度。

说明书

技术领域

本发明涉及一种基于Petri网基本结构的过程模型修复方法。

背景技术

过程挖掘是在1998年由R.Agrawal等人提出的。目前国际上比较认可的过程挖掘定义 为“过程挖掘是指那些从实际执行集合中提取出结构化过程描述的方法”。

在过去的十年里，事件数据越来越容易获得，过程挖掘技术正在趋于成熟。过程挖掘也 成为了业务过程管理(BPM)研究的热门课题之一。下面利用BPM生命周期来定位过程挖 掘。BPM生命周期说明了一个业务过程的7个阶段，分别是(重)设计、分析、实现、(重) 配置、执行、调整和诊断。(重)设计阶段，将会创建一个新的过程模型或者修改一个已经存 在的过程模型。分析阶段对候选模型和其它可选模型进行分析。在此之后，模型在实现阶段 得以实现。一个已存在的系统将会在(重)配置阶段得以重新配置。在执行阶段，设计好的 过程模型将会被执行和监测。在调整阶段，过程不会被重新设计，也不会生成新的软件。在 诊断阶段，被执行的过程得到分析，此阶段的输出可能会触发一次新的(再)设计阶段。过 程模型在(重)设计、配置和实现阶段扮演主导角色，而数据在实现、执行和诊断阶段扮演 主导角色。过程挖掘提供了一种真正“闭合”BPM生命周期的可能性。

从过程挖掘的定义中可以看出过程挖掘的目的是从日志数据中抽取信息，并且建立清晰 的过程模型，同时要保证构建的过程模型与实际的执行过程保持一致。过程挖掘的起点是事 件日志。所有的过程挖掘技术均假设能够连续地记录事件，每个事件代表一个活动，而且每 个事件和一个特定的案例相关。另外，事件日志可能存储了关于事件的额外信息。

事件日志可以被用于三种类型的过程挖掘场景。第一类过程挖掘场景是“过程发现”，即 根据一个事件日志生成一个模型，并不使用任何先验信息，其主要内容是过程挖掘算法的研 究。第二类过程挖掘场景是“一致性检测”，将一个已知的过程模型与这个模型的事件日志进 行对比，一致性检测可以用来检查记录在日志中的实际情况是否符合这个模型。第三种类型 的过程挖掘场景是“过程增强”，其理念是利用实际过程产生的事件日志来扩展或改进一个已 存在的过程，与一致性检测不同，第三种过程挖掘场景的目的在于改进和扩展已知模型。

随着过程挖掘技术的升温，国内外的很多学者都致力于研究过程挖掘算法。过程挖掘算 法最早是由Cook和Wolf提出的，目标是从软件过程的事件日志中自动发现过程模型，并随 之做了大量的后继工作。1998年，AGRAWAL使用基于有向图的方法最早提出了业务过程挖 掘模型，此后又进行了一系列扩展性的研究。此后国内外的学者陆陆续续地提出了大量的数 据挖掘算法。比如，Aalst提出的基于活动顺序关系产生的α算法以及闻立杰、王建民提出的 其衍生算法，基于语义技术提出的区域挖掘和ILP挖掘等等。本发明所使用的过程挖掘方法 是在2013年S.J.JLeemans提出的归纳挖掘。

在一致性检测和过程增强技术方面，目前最大的挑战就是在过程模型上进行重演，来发 现事件日志中观察到的行为的最优路径。AryaAdriansyah提出了基于事件日志的校准方法， 不仅能够对事件日志进行重演，还能够解决在重演过程中出现的诸如重复变迁，不可见变迁， 复杂的控制过和循环此类问题。另外，对于过程模型中出现的偏差，校准也能够发现偏差出 现的地点，并提供偏差的诊断信息。进一步地，通过对不同偏差赋予不同程度的严重性，可 以利用校准来实现不同角度的分析。

发明内容

本发明的目的在于提出一种基于Petri网基本结构的过程模型修复方法，其采用如下方案：

基于Petri网基本结构的过程模型修复方法，包括如下步骤：

a利用归纳挖掘算法从事件日志中挖掘出对应的过程模型

a1过程树

定义过程树

设Σ是一个有限活动集，⊕是给定的符号集，τ是隐式变迁；

(1)a∈Σ∪{τ}是一个过程树；

(2)设M₁，…，M_n均是过程树，n>0，则⊕(M₁,…,M_n)也是过程树；

对于操作符，有如下几种：

操作符×代表着选择关系，该操作符对应的子树只有一个会发生；

操作符→代表着顺序关系，该操作符对应的子树会顺序发生；

操作符代表着循环关系，M₁代表循环体，M₂,…,M_n代表循环路径，对于n≥2；

操作符∧代表着并行关系；

为描述过程树的语义，对于过程树定义一个循环单调函数；对于过程树的操作符，分别 定义其结合函数⊕1：

对于a∈Σ；

对于操作符×，$\times 1(L_1,...,L_n)=\underset{1\le i\le n}{\cup }{L}_i;$

对于操作符→，$\to 1(L_1,...,L_n)=\{t_1·t_2...t_n|\forall i\in 1...n:t_i\in L_i\};$

对于操作符

为描述操作符∧，引入符号集这个符号集代表着t₁...t_n的交错；

其中，f是一个双射函数，将t中每一个事件映射到t_i中的一个事件，t(i)代表着t中第i 个元素；使用这种符号定义，下面来定义操作符∧：

每一个过程树的操作符都有一个直接的形式化地对应到一个稳固块结构的工作流网中；

a2确定操作符和选择切割

四种操作符×，→，∧每一种都有着典型的形式来进行分割；事件日志会根据选定的 操作符进行分割，被分割的事件日志会继续递归进行分割；

定义选择切割

存在一个紧邻图G，对其进行选择切割，产生了不相交的集合Σ₁,…,Σ_n，有：

定义顺序切割

存在一个紧邻图G，对其进行顺序切割，产生了不相交的集合Σ₁,…,Σ_n，有：

定义并行切割

存在一个紧邻图G，对其进行并行切割，产生了不相交的集合Σ₁,…,Σ_n，有：

定义循环切割

存在一个紧邻图G，对其进行选择切割，产生了不相交的集合Σ₁,…,Σ_n，有：

$Start\left(G\right)\cup End\left(G\right)\subseteq {\Sigma }_1;$

a3切割日志

在确定操作符并选择对应的切割后，需要对事件日志进行分离；不同的切割对应不同的 切割函数，下面列出对应的切割函数：

定义顺序切割函数

输入：事件日志L和顺序切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个顺序切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

定义选择切割函数

输入：事件日志L和选择切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个选择切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

定义并行切割函数

输入：事件日志L和并行切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个并行切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

其中，t|_x是一个映射函数，它将迹t投射到活动x之中，这样所有在t|_x中存在的事件均 在事件x中；

定义循环切割函数

输入：事件日志L和循环切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个循环切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

在分别定义了各个切割的分离日志函数后，下面给出归纳挖掘的核心算法，其输入为事 件日志，输出为过程树：

定义归纳挖掘核心算法

输入：事件日志L；

输出：过程树；

步骤1：判断并选择最为重要且最大的切割方法；

步骤2：若选择的切割方法为选择切割，则调用选择切割函数，得到切割后的事件日志 L₁,···,L_n，并返回{(×,((L₁,0),...,(L_n,0)))}；

步骤3：若选择的切割方法为顺序切割，则调用顺序切割函数，得到切割后的事件日志 L₁,···,L_n，并返回{(→,((L₁,0),...,(L_n,0)))}；

步骤4：若选择的切割方法为并行切割，则调用并行切割函数，得到切割后的事件日志 L₁,···,L_n，并返回{(∧,((L₁,0),...,(L_n,0)))}；

步骤5：若选择的切割方法为循环切割，则调用循环切割函数，得到切割后的事件日志 L₁,···,L_n，并返回

步骤6：若事件日志为空集或事件日志只含有一个元素，返回

通过上述归纳挖掘算法从事件日志中挖掘出对应的过程树，进而得到相应的过程模型；

b将扩大的事件日志与挖掘得到的过程模型进行校准，发现过程模型中存在的偏差

定义移动队列

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri 网；迹σ和模型N之间的移动队列γ∈(A^＞＞×T^＞＞)*必须满足：

π₁(γ)_↓A≤σ，表示移动队列γ第一项在A上的投影，即迹中的移动序列是迹的前缀；

存在一个完全发生队列有即模型中的移动序列是完全发生 序列的前缀；

对于所有的移动队列里的二元组(a,t)∈γ，规定如下几种移动：

若a∈A且t＝＞＞，则称之为日志动作；

若a＝＞＞且t∈T，则称之为模型动作；

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

其他类型称之为非法动作；

所有的日志动作、模型动作和同步动作都是合法动作；一个移动队列如果只包含合法动 作，那么它就是合法移动队列；在移动队列定义的基础上，对校准进行定义：

定义校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri 网；迹σ和模型N之间的校准γ∈(A^＞＞×T^＞＞)*是满足以下条件的移动队列：

π₁(γ)_↓A＝σ，即迹中的移动序列产生了这条迹；

即模型中的移动序列产生一个完全发生序列；

是迹σ和模型N之间所有校准的集合；

定义最优校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的简 单稳固Petri网，函数lc:A^＞＞×T^＞＞→IR是移动的可能性代价函数；

迹σ和模型N之间的校准是一个最优校准当且仅当

是可能性代价函数为lc的情况下，迹σ和模型N之间的最优校准集合；

定义标准可能性代价函数

设是活动集，N＝(P,T,F,α,m_i,m_f)是基于活动集A的简单稳固Petri网；标准可能性 代价函数lc:A^＞＞×T^＞＞→IR将所有的移动映射到实数集上，对于所有的(x,y)∈A^＞＞×T^＞＞：

当x∈A，y∈T并且x＝α(y)，或者x＝＞＞，y∈T并且α(y)＝τ时，lc((x,y))＝0；

当x∈A，y∈T并且x≠α(y)，或者x＝y＝＞＞时，lc((x,y))＝+∞；

其他情况下，lc((x,y))＝1；

c不同结构下过程模型的修复方法

对过程模型先进行分块，每一个分块都是一个单一结构，通过对每个块结构修复之后， 再将修复之后的块结构进行合并，进而完成整体的过程模型的修复；

每个块结构为并行、选择、循环和顺序四种结构中的一种；具体修复方法如下：

对于顺序结构类的块结构，利用c1方法进行修复；

对于选择结构类的块结构，利用c2方法进行修复；

对于并行结构类的块结构，利用c3方法进行修复；

对于循环结构类的块结构，利用c4方法进行修复；

c1顺序结构的过程模型修复算法

定义扩展校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri 网；迹σ和模型N之间的扩展校准γ∈(A^＞＞×T^＞＞×P)*是满足以下条件的移动队列：

π₁(γ)_↓A＝σ，即迹中的移动序列产生了这条迹；

即模型中的移动序列产生一个完全发生序列；

π₃(γ)＝(π₂(γ)_↓A)^·，即模型中变迁发生后托肯所在库所的位置；

定义最优扩展校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的简 单稳固Petri网，函数lc:A^＞＞×T^＞＞→IR是移动的可能性代价函数；

迹σ和模型N之间的扩展校准是一个最优扩展校准当且仅当

是可能性代价函数为lc的情况下，迹σ和模型N之间的最优校准集合；

日志动作的出现，说明日志中出现了过程模型并未存在的活动；需要过增加这个活动来 保证过程模型的一致性，下面给出该情形下的过程模型修复算法：

算法1部分不可重演日志的日志动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个变迁π₁(γ[i])；

步骤2:在Petri网库所集P中添加一个库所p_π1(γ[i])；

步骤3:在Petri网弧集F中添加一个弧(p_π1(γ[i]),(π₃(γ[i]))^·)；

步骤4:删除Petri网弧集F中的弧(π₃(γ[i]),(π₃(γ[i]))^·)，并添加新的弧(π₃(γ[i]),π₁(γ[i]))和 (π₁(γ[i]),p_π1(γ[i]))；

步骤5:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

模型动作的出现，说明了事件日志中不存在这种活动；需要对这一活动进行删除来满足 模型的一致性，下面给出该情形下的过程模型修复算法：

算法2部分不可重演日志的模型动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中删除变迁π₂(γ[i])；

步骤2:在Petri网库所集P中删除库所π₃(γ[i])；

步骤3:在Petri网弧集F中添加一个弧(^·(π₂(γ[i])),(π₃(γ[i]))^·)；

步骤4:删除Petri网弧集F中的弧(^·(π₂(γ[i])),π₂(γ[i]))，(π₂(γ[i]),π₃(γ[i]))和(π₃(γ[i]), (π₃(γ[i]))^·)；

步骤5:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

日志动作的出现，说明事件日志中出现了过程模型中不存在的活动，而原有的迹仍旧存 在，原有的过程模型是正确的，不能更改原有的结构，只能在原有的过程模型上进行扩展， 只要在相应的库所处添加一个自环变迁就能够满足这种要求；下面给出该情形下的修复算法：

算法3扩展日志的日志动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个变迁π₁(γ[i])；

步骤2:在Petri网弧集F中添加弧(π₃(γ[i]),π₁(γ[i]))和(π₁(γ[i]),π₃(γ[i]))；

步骤3:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

模型动作的出现，说明事件日志中不存在这种活动，而原有的迹仍然存在，就不能将其 删掉，而是添加一个不可见变迁来扩展模型，使其符合扩展后的的事件日志；下面给出该情 形下的过程模型修复算法：

算法4扩展日志的模型动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个不可见变迁τ；

步骤2:在Petri网弧集F中添加弧(^·(π₂(γ[i])),τ)和(τ,π₃(γ[i]))；

步骤3:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

c2选择结构的过程模型修复

c21部分不可重演日志的过程模型修复

日志动作的出现，说明日志中出现了过程模型并未存在的活动；因此需要在这条分支下 增加这个活动来保证过程模型的一致性，因为将修复的部位放在了分支的内部，其原理和方 法跟顺序结构下修复一致，其修复算法与步骤c1中算法1相同；

c22扩展日志的过程模型修复

日志动作的出现，说明事件日志中出现了过程模型中不存在的活动，而原有的迹仍旧存 在，说明原有的过程模型是正确的，不能更改原有的结构，方法与顺序结构中的方案一致， 添加一个自环，其修复算法与步骤c1中算法3相同；

c23模型动作修复

模型动作的出现，需要运用步骤c1中算法4对过程模型添加一个不可见变迁；

c24对过程模型和事件日志进行校准，如果出现了日志动作和模型动作相邻的情况，且 最优校准模型动作部分是选择结构的分支，那就要添加一个选择分支，分支的活动就是日志 动作的内容；通过如下算法来添加这个分支：

算法5添加选择结构分支

输入：扩展校准γ，日志动作出现的位置i和模型动作出现的位置j；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个变迁π₁(γ[i])；

步骤2:在Petri网弧集F中添加弧(π₃(γ[i]),π₁(γ[i]))和(π₁(γ[i]),π₃(γ[j]))；

步骤3:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

c3并行结构的过程模型修复

日志动作的出现，说明事件日志中出现了新的活动，而过程模型中并不存在；因而使用 步骤c1中的算法3对过程模型进行修复；

模型动作的出现，说明事件日志中不存在这种活动，而原有的迹仍然存在，同样的方法， 对其添加一个不可见变迁，采用步骤c1中的算法4对过程模型进行修复；

c4循环结构的过程模型修复

按照过程树部分对过程模型进行分解，将其分解成循环体和循环部分得到两个顺序结构， 然后按照步骤c1中顺序结构进行过程模型修复。

本发明具有如下优点：

本发明主要通过对原有数据进行处理，使其成为符合规范的事件日志；之后对其使用归 纳挖掘算法挖掘出对应的过程模型；通过将扩大的事件日志与挖掘得到的过程模型进行校准， 发现过程模型中存在的偏差；最后提出了不同结构下过程模型的修复方案，旨在修复过程模 型，增强过程模型的一致性。在选择结构中，对日志动作和模型动作相邻这种情况进行了特 殊修复，提出的修复算法在保证拟合度、精确度的同时，也提高了过程模型的简化度。

附图说明

图1为事件日志L的紧邻图；

图2为简单的顺序结构模型图；

图3为修复无法重演日志下的日志动作的示意图；

图4为修复无法重演日志下的模型动作的示意图；

图5为修复扩展日志下的日志动作的示意图；

图6为修复扩展日志下的模型动作的示意图；

图7为简单的选择结构模型图；

图8为选择结构分离后的一条分支的示意图；

图9为修复无法重演日志下的日志动作后的分支的示意图；

图10为修复无法重演日志下的日志动作的示意图；

图11为修复扩展日志下的日志动作的示意图；

图12为修复模型动作后的过程模型的示意图；

图13为特殊情形下模型修复后的过程模型的示意图；

图14为简单的并行结构示意图；

图15为修复扩展日志下的日志动作的示意图；

图16为修复扩展日志下的模型动作的示意图。

具体实施方式

下面结合附图以及具体实施方式对本发明作进一步详细说明:

基本概念

定义Petri网(PetriNet)

设是活动集，Petri网是一个多元组N＝(P,T,F,α,m_i,m_f)。其中，P是库所集，T是 变迁集，F:(P×T)∪(T×P)→IN是边的权重值，α:T→A∪{τ}是一个从变迁映射到标签的函数。

标识(Petri网的状态)是一个库所的多重集。m_i，m_f∈B(P)分别是多元组N的初始标识 和终止标识。

变迁t∈T在标识m∈B(P)下是使能的，当且仅当记作(N,m)[t>。

代表着网N中使能变迁t的发生，从原有的标识m变化成新的标识m’，并且满 足${\forall }_{p\in P}{m}^{,}\left(p\right)=m\left(p\right)-F(p,t)+F(t,p).$

下面来描述下发生队列和完全发生队列的概念。

定义发生队列，完全发生队列(FiringSequence,CompleteFiringSequence)

队列代表着从m到m’的变迁发生序列，并且有即

本发明用(N,m)表示是从标识m开始的发生序列。

队列是一个完全发生序列，当且仅当

Petri网的行为可以通过标识的可达性来分析，下面来形式化Petri网中的标识的可达性。

定义标识可达性(MarkingReachability)

设是活动集，多元组N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri网。若在Petri网N 上m’∈B(P)是可达的，则存在一个队列使得RS(N,m)代表着所有从m到m’ 的可达标识集。其中

对于Petri网而言，仍然存在那些不可接受的错误行为，比如死锁与活锁。本发明只讨论 那些能够从初始节点到达终止节点的Petri网，称之为简单稳固Petri网。

定义简单稳固Petri网(EasySoundPetriNet)

设是活动集，多元组N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri网。N是简单稳固 Petri网当且仅当m_f∈RS(N,m_i)。

工作流网

当使用Petri网对业务流程进行建模的时候，通常会考虑Petri网的一个子类--工作流网 (WorkflowNet)。一个工作流网，是一个有着明确的起始库所和终止库所的Petri网，过程从 起始库所开始并在终止库所结束。此外，所有的结点都在从起始库所到终止库所的路径上。

定义工作流网

设是活动集，多元组N＝(P,T,F,α,m_i,m_f,r,i)是一个基于A的重置/抑制网。N是一个 工作流网当且仅当：

存在一个初始库所p_i∈P，有

存在一个终止库所p_s∈P，有

p_i和p_s分别是网的初始标识和终止标识；

每个节点都在从p_i到p_s的路径上；

不存在重置弧与终止库所，

目前，人们已经提出了多种正确性评价指标。其中，最为广泛使用的评价标准是Aalst提 出的稳固性(soundness)。

定义稳固性

设是活动集，多元组N＝(P,T,F,α,m_i,m_f,r,i)是一个基于活动集A的工作流网，工作 流网N是稳固的当且仅当：

终点可以到达，${\forall }_{m\in RS(N,mi)}{m}_f\in RS(N,m);$

能够正确地到达终点，${\forall }_{m\in RS(N,mi)}{m}_f\le m\Rightarrow m=m_f;$

无死变迁，

基于Petri网基本结构的过程模型修复方法，包括如下步骤：

a利用归纳挖掘算法从事件日志中挖掘出对应的过程模型

a1过程树

过程树是一个对块状工作流网严密的抽象表示。过程树的根节点是事件活动，其他的节 点是操作符。操作符是用来表示他的子树是如何结合在一起的。

定义过程树

设Σ是一个有限活动集，⊕是给定的符号集，τ是隐式变迁；

(1)a∈Σ∪{τ}是一个过程树；

(2)设M₁，…，M_n均是过程树，n>0，则⊕(M₁,…,M_n)也是过程树；

对于操作符，有如下几种：

操作符×代表着选择关系，该操作符对应的子树只有一个会发生；

操作符→代表着顺序关系，该操作符对应的子树会顺序发生；

操作符代表着循环关系，M₁代表循环体，M₂,…,M_n代表循环路径，对于n≥2；

操作符∧代表着并行关系；

为描述过程树的语义，对于过程树定义一个循环单调函数；对于过程树的操作符，分别 定义其结合函数⊕1：

对于a∈Σ；

对于操作符×，$\times 1(L_1,...,L_n)=\underset{1\le i\le n}{\cup }{L}_i;$

对于操作符→，$\to 1(L_1,...,L_n)=\{t_1·t_2...t_n|\forall i\in 1...n:t_i\in L_i\};$

对于操作符

为描述操作符∧，引入符号集这个符号集代表着t₁...t_n的交错；

其中，f是一个双射函数，将t中每一个事件映射到t_i中的一个事件，t(i)代表着t中第i 个元素；使用这种符号定义，下面来定义操作符∧：

每一个过程树的操作符都有一个直接的形式化地对应到一个稳固块结构的工作流网中。

a2确定操作符和选择切割

归纳挖掘算法的核心思想就是基于事件日志中活动的顺序来分离事件日志。紧邻关系 (directly-followsrelation)，也应用于α算法中，描述了两个事件在过程中是紧密相邻的。这种 关系可以通过事件日志的紧邻图(directly-followsgraph)来表示，记作G(L)。若(a,b)∈G(L)， 当且仅当在事件日志中存在<…,a,b,…>。紧邻图的初始节点就是事件日志中的初始节点，紧 邻图的终止节点就是事件日志中的终止节点。以一个事件日志L＝{<a,b,c>,<a,c,b>,<a,d,e>, <a,d,e,f,d,e>}为例，可以得到该事件日志的紧邻图G(L)为图1所示。

四种操作符×，→，∧每一种都有着典型的形式来进行分割；事件日志会根据选定的 操作符进行分割，被分割的事件日志会继续递归进行分割。

首先，需要定义符号代表着在紧邻图a到b存在一条有向边。

定义选择切割

存在一个紧邻图G，对其进行选择切割，产生了不相交的集合Σ₁,…,Σ_n，有：

定义顺序切割

存在一个紧邻图G，对其进行顺序切割，产生了不相交的集合Σ₁,…,Σ_n，有：

定义并行切割

存在一个紧邻图G，对其进行并行切割，产生了不相交的集合Σ₁,…,Σ_n，有：

定义循环切割

存在一个紧邻图G，对其进行选择切割，产生了不相交的集合Σ₁,…,Σ_n，有：

$Start\left(G\right)\cup End\left(G\right)\subseteq {\Sigma }_1;$

a3切割日志

在确定操作符并选择了对应切割后，需要对事件日志进行分离。不同的切割对应了不同 的切割函数，所有的函数输入为事件日志与分割方法，输出为分割之后的事件日志。

下面列出了对应的切割函数：

定义顺序切割函数

输入：事件日志L和顺序切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个顺序切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

定义选择切割函数

输入：事件日志L和选择切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个选择切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

定义并行切割函数

输入：事件日志L和并行切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个并行切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

其中，t|_x是一个映射函数，它将迹t投射到活动x之中，这样所有在t|_x中存在的事件均 在事件x中；

定义循环切割函数

输入：事件日志L和循环切割集合(Σ₁,...,Σ_n)；

输出：切割后的事件日志L₁,···,L_n；

依次遍历每一个循环切割集合，每一个集合会将原有的事件日志切割出与其对应的事件 日志，有：

在分别定义了各个切割的分离日志函数后，下面给出归纳挖掘的核心算法，其输入为事 件日志，输出为过程树：

定义归纳挖掘核心算法

输入：事件日志L；

输出：过程树；

步骤1：判断并选择最为重要且最大的切割方法；

步骤2：若选择的切割方法为选择切割，则调用选择切割函数，得到切割后的事件日志 L₁,···,L_n，并返回{(×,((L₁,0),...,(L_n,0)))}；

步骤3：若选择的切割方法为顺序切割，则调用顺序切割函数，得到切割后的事件日志 L₁,···,L_n，并返回{(→,((L₁,0),...,(L_n,0)))}；

步骤4：若选择的切割方法为并行切割，则调用并行切割函数，得到切割后的事件日志 L₁,···,L_n，并返回{(∧,((L₁,0),...,(L_n,0)))}；

步骤5：若选择的切割方法为循环切割，则调用循环切割函数，得到切割后的事件日志 L₁,···,L_n，并返回

步骤6：若事件日志为空集或事件日志只含有一个元素，返回

通过上述归纳挖掘算法从事件日志中挖掘出对应的过程树，进而得到相应的过程模型；

上述归纳挖掘算法的优点在于：能够在较短的时间内创建一个稳固的过程模型。就目前 来看，所有的过程挖掘方法都无法让所有的判断标准都有较高的值，但是归纳挖掘在某些方 面上，能够更快速地挖掘出一个80％模型。

b将扩大的事件日志与挖掘得到的过程模型进行校准，发现过程模型中存在的偏差

以一个过程模型作为参考，活动在执行过程没有偏离模型，意味着在当前状态下活动是 被模型所允许的。也就是说，给定一个无任何偏差的事件日志，活动是完全按照模型的顺序 来执行的。基于这种思路，Adriansyah定义了校准这一概念，用以比较事件日志中的活动与 模型上的活动。显而易见地，过程模型的一个实例，不能够直接影响相同过程下的其它实例。 因此，对于校准来说，每一个实例都要对应一个校准。校准由迹中活动与模型中允许的变迁 两部分组成，这种成对的队列称之为移动队列。下面给出移动队列的形式化定义：

定义移动队列

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri 网；迹σ和模型N之间的移动队列γ∈(A^＞＞×T^＞＞)*必须满足：

π₁(γ)_↓A≤σ，表示移动队列γ第一项在A上的投影，即迹中的移动序列是迹的前缀；

存在一个完全发生队列有即模型中的移动序列是完全发生 序列的前缀；

对于所有的移动队列里的二元组(a,t)∈γ，规定如下几种移动：

若a∈A且t＝＞＞，则称之为日志动作；

若a＝＞＞且t∈T，则称之为模型动作；

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

其他类型称之为非法动作；

所有的日志动作、模型动作和同步动作都是合法动作；一个移动队列如果只包含合法动 作，那么它就是合法移动队列；在移动队列定义的基础上，对校准进行定义：

定义校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri 网；迹σ和模型N之间的校准γ∈(A^＞＞×T^＞＞)*是满足以下条件的移动队列：

π₁(γ)_↓A＝σ，即迹中的移动序列产生了这条迹；

即模型中的移动序列产生一个完全发生序列；

是迹σ和模型N之间所有校准的集合。

给定一个迹和一个Petri网，可能会存在多个校准。在实际过程中，偏差的可能性会随着 活动的不同，人为制定的不同而产生不同的影响。

例如，可以认为日志动作产生的偏差要大于模型动作产生的偏差。为了能够产生最有可 能的校准，需要对每一个移动赋予一个可能性代价值。根据制定的可能性代价函数，能够找 到可能性代价值最低的校准，这种校准称之为最优校准。

定义最优校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的简 单稳固Petri网，函数lc:A^＞＞×T^＞＞→IR是移动的可能性代价函数；

迹σ和模型N之间的校准是一个最优校准当且仅当

是可能性代价函数为lc的情况下，迹σ和模型N之间的最优校准集合。

可能性代价函数能够提供一个更加灵活的决策，用来寻找基于迹σ和模型N之间的最优 校准。本发明更加关注于辨别迹和模型之间的偏差，因此，本发明人为地确定了一个标准可 能性代价函数，下面给出其形式化定义：

定义标准可能性代价函数

设是活动集，N＝(P,T,F,α,m_i,m_f)是基于活动集A的简单稳固Petri网；标准可能性 代价函数lc:A^＞＞×T^＞＞→IR将所有的移动映射到实数集上，对于所有的(x,y)∈A^＞＞×T^＞＞：

当x∈A，y∈T并且x＝α(y)，或者x＝＞＞，y∈T并且α(y)＝τ时，lc((x,y))＝0；

当x∈A，y∈T并且x≠α(y)，或者x＝y＝＞＞时，lc((x,y))＝+∞；

其他情况下，lc((x,y))＝1。

校准和最优校准能够将事件日志和过程模型关联起来，并且最有校准能够处理过程模型 中的不可见变迁、复杂的控制流和循环等。当偏差出现时，校准能够展示出偏差所在的位置， 并且为进一步的研究提供诊断信息。可能性代价函数则为校准提供了一种严重度的度量方式。

c不同结构下过程模型的修复方法

通过上述内容可知，校准可以发现事件日志与过程模型之间的偏差。通过对事件日志和 过程模型进行校准，能够确定偏差出现的位置。在确认位置之后，需要对过程模型的结构和 最优校准进行综合的分析，以确定一个方案来对过程模型进行适当的修改。当然，过程模型 的修改是需要一个评价指标的，对于过程模型的指标，上述内容已经简单说明。对于过程模 型来说，最为重要的指标就是拟合度。因此，对过程模型的修改要尽量使得模型有着较高的 拟合度，在保证高拟合度的前提下，再尽量去满足其他维度的指标。

实际的过程模型往往不可能是简单的结构，过程模型往往是并行、选择、循环和顺序等 结构结合起来构成的。因此，对过程模型先进行分块，每一个分块都是一个单一结构，这样 就能够方便地对过程模型进行修复。对每个块结构修复之后，在将修复之后的块结构进行合 并，这样就能够完成整体的过程模型的修复。过程模型的分块可以参考上述过程树，通过 对过程模型构造过程树能较好的展示出过程模型里的各个块结构。本发明研究的重点是如何 对各种结构下出现的偏差进行修复，并提出相应的过程模型修复算法。

每个块结构为并行、选择、循环和顺序四种结构中的一种；具体修复方法如下：

对于顺序结构类的块结构，利用c1方法进行修复；

对于选择结构类的块结构，利用c2方法进行修复；

对于并行结构类的块结构，利用c3方法进行修复；

对于循环结构类的块结构，利用c4方法进行修复。

c1顺序结构的过程模型修复算法

定义扩展校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的Petri 网；迹σ和模型N之间的扩展校准γ∈(A^＞＞×T^＞＞×P)*是满足以下条件的移动队列：

π₁(γ)_↓A＝σ，即迹中的移动序列产生了这条迹；

即模型中的移动序列产生一个完全发生序列；

π₃(γ)＝(π₂(γ)_↓A)^·，即模型中变迁发生后托肯所在库所的位置。

类似的，最优校准也需要进行这种形式的扩展。

定义最优扩展校准

设是活动集，σ∈A*是基于活动集A的迹，N＝(P,T,F,α,m_i,m_f)是基于活动集A的简 单稳固Petri网，函数lc:A^＞＞×T^＞＞→IR是移动的可能性代价函数；

迹σ和模型N之间的扩展校准是一个最优扩展校准当且仅当

是可能性代价函数为lc的情况下，迹σ和模型N之间的最优校准集合。

对于事件日志来说，事件日志可能无法在过程模型中重演，也可能是事件日志进行了扩 展，出现了新的迹，原有的迹仍然存在。

由于顺序结构的特殊性，这两种情况，前者修复最为合理的方法是对顺序结构中活动进 行增添或者删除。后者最为合理的方案则是需要适当的改变顺序结构。

日志动作的出现，说明日志中出现了过程模型并未存在的活动；需要过增加这个活动来 保证过程模型的一致性，下面给出该情形下的过程模型修复算法：

算法1部分不可重演日志的日志动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个变迁π₁(γ[i])；

步骤2:在Petri网库所集P中添加一个库所p_π1(γ[i])；

步骤3:在Petri网弧集F中添加一个弧(p_π1(γ[i]),(π₃(γ[i]))^·)；

步骤4:删除Petri网弧集F中的弧(π₃(γ[i]),(π₃(γ[i]))^·)，并添加新的弧(π₃(γ[i]),π₁(γ[i]))和 (π₁(γ[i]),p_π1(γ[i]))；

步骤5:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)。

下面以一个例子来说明，图2表示了一个简单的顺序结构，假设事件日志L＝ {<a,d,b,c>¹⁰⁰}；对这个事件日志进行校准，得到如下结果：

对其按照算法1进行修复之后将会得到这样一个模型，如图3所示。

模型动作的出现，说明了事件日志中不存在这种活动；需要对这一活动进行删除来满足 模型的一致性，下面给出该情形下的过程模型修复算法：

算法2部分不可重演日志的模型动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中删除变迁π₂(γ[i])；

步骤2:在Petri网库所集P中删除库所π₃(γ[i])；

步骤3:在Petri网弧集F中添加一个弧(^·(π₂(γ[i])),(π₃(γ[i]))^·)；

步骤4:删除Petri网弧集F中的弧(^·(π₂(γ[i])),π₂(γ[i]))，(π₂(γ[i]),π₃(γ[i]))和(π₃(γ[i]), (π₃(γ[i]))^·)；

步骤5:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)。

同样以图2为例，事件日志L’＝{<a,c>¹⁰⁰}，对这个事件日志进行校准，得到如下结果：

对其按照修复函数进行修复之后将会得到这样一个模型，如图4所示。

日志动作的出现，说明事件日志中出现了过程模型中不存在的活动，而原有的迹仍旧存 在，原有的过程模型是正确的，不能更改原有的结构，只能在原有的过程模型上进行扩展， 只要在相应的库所处添加一个自环变迁就能够满足这种要求；下面给出该情形下的修复算法：

算法3扩展日志的日志动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个变迁π₁(γ[i])；

步骤2:在Petri网弧集F中添加弧(π₃(γ[i]),π₁(γ[i]))和(π₁(γ[i]),π₃(γ[i]))；

步骤3:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)。

同样以图2为例，一开始的事件日志为L＝{<a,b,c>¹⁰⁰}，随着业务流程的改变，事件日志 逐渐演变成L’＝{<a,b,c>¹⁰⁰,<a,d,b,c>²⁰}，事件日志中第一条迹是符合过程模型的，不对其进 行校准，第二条迹明显存在一个偏差，对其校准后，结果如下：

事件日志变化后，事件日志中出现了原本不存在于过程模型的活动，又其原有的迹仍符 合过程模型，所以对其按照算法3进行修复之后将会得到这样一个模型，如图5所示。

模型动作的出现，说明事件日志中不存在这种活动，而原有的迹仍然存在，就不能将其 删掉，而是添加一个不可见变迁来扩展模型，使其符合扩展后的的事件日志；下面给出该情 形下的过程模型修复算法：

算法4扩展日志的模型动作修复算法

输入：扩展校准γ和日志动作出现的位置i；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个不可见变迁τ；

步骤2:在Petri网弧集F中添加弧(^·(π₂(γ[i])),τ)和(τ,π₃(γ[i]))；

步骤3:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)。

同样以图2为例，一开始的事件日志为L＝{<a,b,c>¹⁰⁰}，随着业务流程的改变，事件日志 逐渐演变成L’＝{<a,b,c>¹⁰⁰,<a,c>²⁰}，事件日志中第一条迹是符合过程模型的，不对其进行校 准，第二条迹明显存在一个偏差，对其校准后，结果如下：

事件日志变化后，事件日志中丢失了原来存在于过程模型上的活动，又其原有的迹仍符 合过程模型，所以对其按照算法4进行修复之后将会得到这样一个模型，如图6所示。

c2选择结构的过程模型修复

选择结构下，一个发生队列只会发生一个分支，其他的分支不会发生。因而，对于选择 结构来说，事件日志中迹的个数就是过程模型分支的条数。选择结构下，各个分支内部的结 构是顺序结构，在此讨论时，并不对选择结构分支内部偏差做讨论，因为完全可以按照顺序 结构的方法进行修复。

对于选择结构下的事件日志，仍然存在原有的事件日志无法重演和事件日志中出现了扩 展这两种情形。因为选择结构的特殊性，事件日志中不可能只存在一条单一的迹，如果所有 的迹都被替换的话，可以认为这种替换的改变是巨大的，并不适合运用模型修复技术。

c21部分不可重演日志的过程模型修复

日志动作的出现，说明日志中出现了过程模型并未存在的活动；因此需要在这条分支下 增加这个活动来保证过程模型的一致性，因为将修复的部位放在了分支的内部，其原理和方 法跟顺序结构下修复一致，其修复算法与步骤c1中算法1相同。

图7展示了一个简单的选择结构模型。其事件日志L＝{<a,f,b,e>⁵⁰,<a,c,e>⁵⁰,<a,d,e>⁵⁰}， 显然，只有事件日志中第一条迹出现了偏差，对其进行校准：

对于该分支结构，由于变化的只有第一个分支，可以单独对其进行考虑，故将其分离， 如图8所示。分离之后，就产生了一个顺序结构，再对其按照顺序结构的方法进行修复，可 以获得修复后的模型，如图9所示。再将其合并到原有的选择结构中，就能够得到最终的修 复模型，如图10所示。

c22扩展日志的过程模型修复

日志动作的出现，说明事件日志中出现了过程模型中不存在的活动，而原有的迹仍旧存 在，说明原有的过程模型是正确的，不能更改原有的结构，方法与顺序结构中的方案一致， 添加一个自环，其修复算法与步骤c1中算法3相同。

同样以图7为例，一开始事件日志为L＝{<a,b,e>⁵⁰,<a,c,e>⁵⁰,<a,d,e>⁵⁰}，随着业务流程的 改变，事件日志逐渐演变成L’＝{<a,b,e>⁵⁰,<a,c,e>⁵⁰,<a,d,e>⁵⁰,<a,f,b,e>⁵⁰}，事件日志中第四 条迹存在偏差，对其进行校准：

在p₂处添加自环后过程模型如图11所示。

c23模型动作修复

模型动作的出现，无论事件日志如何变化，都需要运用步骤c1中算法4来对过程模型添 加一个不可见变迁，唯一的区别就是是否要删除一个分支。

同样以图7为例，事件日志L₁’＝{<a,b,e>⁵⁰,<a,c,e>⁵⁰,<a,d,e>⁵⁰,<a,e>⁵⁰}或者L₂’＝ {<a,b,e>⁵⁰,<a,c,e>⁵⁰,<a,e>⁵⁰}区别就是选择结构的活动d这一分支是否应该删除。对迹t₃＝<a,e> 做校准，其最优校准有三个：

通过最优校准发现在同一位置有三个不同的模型动作，这就说明校准的这条迹对应的过 程模型是一个选择结构，这三个活动对应了各个分支的活动。通过校准，就能够确定需要添 加不可见变迁的位置。以L₁’为例，对于添加了不可见变迁之后的过程模型如图12所示。

c24特殊情形的过程模型修复算法

对于选择结构来说，存在一种特殊的情况，当日志动作和模型动作不是相邻时，可以按 照原有的方法分步进行。一旦日志动作和模型动作相邻时，分别对其进行修复得到的模型会 降低模型的简化度和精确度。因而，需要将它们综合考虑，进行模型修复。

对过程模型和事件日志进行校准，如果出现了日志动作和模型动作相邻的情况，且最优 校准模型动作部分是选择结构的分支，那就要添加一个选择分支，分支的活动就是日志动作 的内容；通过如下算法来添加这个分支：

算法5添加选择结构分支

输入：扩展校准γ，日志动作出现的位置i和模型动作出现的位置j；

输出：修复后的Petri网N＝(P,T,F,α,m_i,m_f)；

步骤1:在Petri网变迁集T中添加一个变迁π₁(γ[i])；

步骤2:在Petri网弧集F中添加弧(π₃(γ[i]),π₁(γ[i]))和(π₁(γ[i]),π₃(γ[j]))；

步骤3:输出修复后的Petri网N＝(P,T,F,α,m_i,m_f)。

同样以图7为例，一开始事件日志为L＝{<a,b,e>⁵⁰,<a,c,e>⁵⁰,<a,d,e>⁵⁰}，随着业务流程的 改变，事件日志逐渐演变成L’＝{<a,b,e>⁵⁰,<a,c,e>⁵⁰,<a,d,e>⁵⁰,<a,f,e>⁵⁰}，对第四条迹t₄＝<a,f,e> 进行校准，可以得到三个最优校准：

通过最优校准可以知道，日志动作和模型动作是相邻的，所以需要添加一条分支，分支 的活动是f，图13是修复后的模型。

c3并行结构的过程模型修复

并发结构下，所有的分支都会发生一次，假设分支数为n，对于过程模型的发生队列来说， 一共有n！种情形。所以对于事件日志来说，若某些分支无法得到重演，也就意味着若想保 证过程模型仍然是并发关系，事件日志所有的迹都无法的到重演，因而，目前不去考虑某些 分支无法得到重演这种情况。本发明着重考虑的是事件日志中出现新的迹这类情况。

日志动作的出现，说明事件日志中出现了新的活动，而过程模型中并不存在；因而使用 步骤c1中的算法3对过程模型进行修复；对于并发关系来说，托肯的位置可能有多个，所以 任意选择一个托肯作为添加自环的点即可。

图14展示了一个简单的选择结构。一开始的事件日志为L＝ {<a,b,c,d,e>⁵⁰,<a,b,d,c,e>⁵⁰,<a,c,b,d,e>⁵⁰,<a,c,d,b,e>⁵⁰,<a,d,b,c,e>⁵⁰,<a,d,c,b,e>⁵⁰}，随着业务流 程的改变，事件日志逐渐演变成L’＝{<a,b,c,d,e>⁵⁰,<a,b,d,c,e>⁵⁰,<a,c,b,d,e>⁵⁰,<a,c,d,b,e>⁵⁰, <a,d,b,c,e>⁵⁰,<a,d,c,b,e>⁵⁰,<a,f,b,c,d,e>²⁰}，显然，事件日志中出现了一条新的迹t₇＝<a,f,b,c,d,e>， 对其进行校准，其最优校准为：

通过校准，发现了一个日志动作，只要在(p₂,p₄,p₆)中选择一个库所，在选定出进行模型修 复，修复后的模型如图15所示。

模型动作的出现，说明事件日志中不存在这种活动，而原有的迹仍然存在，同样的方法， 对其添加一个不可见变迁，采用步骤c1中的算法4对过程模型进行修复。

同样以图14为例，一开始的事件日志为L＝{<a,b,c,d,e>⁵⁰,<a,b,d,c,e>⁵⁰,<a,c,b,d,e>⁵⁰,< a,c,d,b,e>⁵⁰,<a,d,b,c,e>⁵⁰,<a,d,c,b,e>⁵⁰}，随着业务流程的改变，事件日志逐渐演变成L’＝{< a,b,c,d,e>⁵⁰,<a,b,d,c,e>⁵⁰,<a,c,b,d,e>⁵⁰,<a,c,d,b,e>⁵⁰,<a,d,b,c,e>⁵⁰,<a,d,c,b,e>⁵⁰,<a,c,d,e>²⁰}，显 然，事件日志中出现了一个新的迹t₇＝<a,c,d,e>，对其进行校准，其最优校准为：

通过校准，可以发现一个模型动作，只要在指定位置添加一个不可见变迁模型即可修复， 修复后的模型如图16所示。

c4循环结构的过程模型修复

循环结构类似于顺序结构，只需要按照过程树部分对过程模型进行分解，将其分解成循 环体和循环部分得到两个顺序结构，然后按照步骤c1中顺序结构进行过程模型修复即可。

当然，以上说明仅仅为本发明的较佳实施例，本发明并不限于列举上述实施例，应当说 明的是，任何熟悉本领域的技术人员在本说明书的教导下，所做出的所有等同替代、明显变 形形式，均落在本说明书的实质范围之内，理应受到本发明的保护。