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

摘要

本发明公开了一种基于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中顺序结构进行过程模型修复。