基于引发序列的流程模型修正

王 路 杜玉越 祁宏达

(山东科技大学计算机科学与工程学院 山东青岛 266590) (wanglu253@126.com)

随着大数据 [1-2] 时代的到来,业务过程管理(business process management, BPM)必将得到进一步的改善.近年来,企业信息系统(enterprise infor-mation systems, EIS)通过集成提高了企业业务流程的功能 [3] ,产生了大量的事件日志(event logs),并且这些日志被记录并存储在了系统中 [4] .流程挖掘(process mining)可以从记录的这些数据中提取出与流程相关的信息并发现流程模型(process model) [5-6] .

事件日志通常作为流程挖掘的输入数据,是流程模型在执行过程中产生的事件序列集合.日志中的每一个事件对应于一个活动,并与一个特定的实例相关.事件日志记录的实例中的一条事件序列称为一条迹(trace).除了活动,事件日志同样包含其他信息,比如初始资源(initial resources)、事件的时间戳(timestamp)等.现有的流程挖掘技术有流程发现(process discovery)、合规性检查(conformance checking)、流程改进(process enhancement) [4-7] .流程发现是通过挖掘日志中流程的主要步骤来创建 流程模型.合规性检查是将流程模型的行为与事件日志中记录的行为进行对比,从而找到建模的行为与记录的行为之间的共性和差异.流程改进是根据事件日志对流程模型进行改进或扩展.通过这3种流程挖掘技术可以进行瓶颈分析与延迟预测等.

目前,存在很多从控制流角度描述流程模型的形式化语言,比如业务流程建模标记法(business process modeling notation, BPMN) [8] 、因果网(causal nets) [4] 、事件驱动流程链(event-driven process chains, EPCs) [9] 、Petri网 [10] 等.Petri网 [10] 能够作为分布式系统建模和分析的工具,并且具有严格的数学定义以及强大的图形表达能力.Petri网不仅能够描述流程的静态结构,还可以模拟流程运行过程中的动态行为.对于具有并行、并发、异步、分布和不确定性等性质的信息系统,可以利用Petri网对其进行有效地描述和分析 [11-15] ,因此,本文用Petri网来描述流程模型.

如果现在有流程模型不能够重演(replay)对应的实例,原则上要用流程发现来得到一个新的流程模型.但是,重新发现的模型通常与原模型没有相似度并且丢弃了原模型的优势,特别是在原模型通过手工创建的情况下,丢失掉的优势显得由为重要.对于不能重演实例的流程模型,一个比较好的方法是对原模型进行修正,从而使模型可以重演(大多数)事件日志并且尽可能保留原模型的优势.本文介绍了一种新的流程挖掘技术——模型修正.该技术将流程模型 N 与日志 L 中的异常活动作为输入.如果模型 N 符合日志 L ,就没有必要修正 N .但是如果 N 中的部分模型不能重演 L 中的某些活动,那么就需要对该部分模型进行修正.与流程发现不同,模型修正可以将流程模型中能够重演事件日志的部分保留下来.得到的修正模型 N ′ 可以看作是原模型 N 及事件日志 L 的一个协同(synergy)部分.模型修正技术保证了修正模型与原模型的相似度.

1 相关工作

本文提出的模型修正技术主要与2个方面的研究方向相关:模型合规性检查与模型发现.

如果模型可以重演事件日志中的活动行为,则该模型的拟合度比较好,如果模型可以重演日志中的所有迹,则该模型的拟合度为1.0 [4] . 如今已经提出了很多合规性检查的方法.基于托肯(token)的重演 [16] 就是检测事件日志与Petri网之间一致性的方法.将日志中的每条迹分别在模型上进行重演,根据迹中的活动顺序,网中的变迁可以被依次引发.在流程执行的过程中可以计算产生(produced)、消耗(consumed)、丢失(missing)和剩余(remaining)的token,然后通过这些token的数目计算日志与模型之间的拟合度.Petkovic等人以BPMN的描述形式提出了流程与日志合规性检查的框架 [17] .

当已有的模型与流程的执行过程不一致时,可以通过流程发现(process discovery)技术得到一个新的流程模型.根据活动的次序关系发现流程模型的技术有Alpha算法 [18] 及其衍生算法 [19-20] ,这种技术可以保证模型的同构-再发现(isomorphic-rediscover)能力 [21] ,但是不能保证模型的拟合性与健壮性.基于语义(semantics-based)的发现技术有基于语言的区域挖掘(language-based region miner) [22-23] 、基于状态的区域挖掘(state-based region miner) [24] 和ILP挖掘(integer linear programming) [25] ,这种发现技术可以保证模型的拟合性,但是不能保证模型的健壮性与再发现能力.

2 基础知识

本节中简单地回顾了多重集与Petri网的定义,并介绍了事件日志与流程模型的概念.在本文中, 表示一个自然数集合, S 是一个有限集合.

定义1 . S 上的多重集 Z 是一个映射 Z S .B( S )表示集合 S 上的所有多重集.

多重集 Z =[ a 3 , b , c 2 ]表示集合 S 上的1个多重集,其中 a , b , c S Z ( a )=3, Z ( b )=1, Z ( c )=2. Z 1 , Z 2 ∈B( S )是2个多重集.2个多重集的和是 Z 3 = Z 1 Z 2 ,其中 Z 3 ∈B( S ),对于所有的 a S Z 3 ( a )= Z 1 ( a )+ Z 2 ( a ).2个多重集的差是 Z 4 = Z 1 - Z 2 ,对于所有的 a S Z 4 ( a )=max{0, Z 1 ( a )- Z 2 ( a )}.如果∀ a S Z 1 ( a )≤ Z 2 ( a ),则 Z 1 Z 2 .比如:[ b , c ]≤[ a 3 , b , c 2 ],但[ b 2 ] [ a 3 , b , c 2 ].

定义2 . S * 表示集合 S 上所有有限序列的集合, ε 表示一个空序列.序列 σ =〈 σ [1], σ [2],…, σ [ n ]〉,其中 σ [ i ]表示序列的第 i 个元素,〈 σ [ i ], σ [ i +1]〉表示2个相邻接的元素,| σ |= n 表示序列 σ 的长度.对于∀ a S σ ( a )表示 a σ 中出现的次数. σ sub 表示 σ 的子序列, σ ( σ sub )表示子序列 σ sub σ 中出现的次数.

定义3 . Z 是集合 S 上的一个多重集, Q S 是集合 S 的一个子集, σ S * . σ | Q 表示 σ Q 上的投影, Z | Q 表示 Z Q 上的投影.

比如:如果 σ = aabc Q ={ a , b }, Z =[ a 3 , b , c 2 ].则 σ | Q = aab Z | Q =[ a 3 , b ].

定义4 . v =( a 1 , a 2 ,…, a n )∈ S ×…× S 是集合 S 上的一个向量. π i ( v )表示 v 的第 i 个元素,其中1≤ i n .

比如 v =( a , b )∈ S × S ,则 π 1 ( l )= a π 2 ( l )= b .可以将该定义扩展到序列中,比如 σ ∈( S × S ) * π i ( σ )=〈 π i ( σ [1]), π i ( σ [2]),…, π i ( σ [| σ |])〉, i =1,2.

定义5 [9] . N =( P , T ; F )为一个网,其中:

1) P 是库所有限集合;

2) T 是一个变迁有限集合,并且 P T ≠∅, P T =∅;

3) F ⊆( P × T )∪( T × P )是一个流关系集合.

定义6 [9] . 设 N =( P , T ; F )为一个网.对于 x S T ,记:

x ={ y | y S T ∧( y , x )∈ F },

x ={ y | y S T ∧( x , y )∈ F },

x x 的前集或输入集, x x 的后集或输出集.称 x x 为元素 x 的外延.前集/后集可以嵌套表示,比如 ( x )表示 即元素 x 前集中各元素的前集 [26-27] .

顺序、并行、选择和循环结构是工作流和流程模型的4种基本结构,如图1所示.流程所有的执行过程都可以由这4种结构组合而成.

Fig. 1 Four basic structures of Petri nets
图1 工作流的4种基本结构

定义7 [28] . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型,其中:

1) N =( P , T ; F ) 是一个网,有唯一的开始库所 b start P b start =∅,唯一的终止库所 b end P ∅.每一个节点 x P T 是在从 b start b end 的一条路上;

2) α : T A τ 是变迁到活动的映射函数;

3) α -1 : A τ T α 的逆函数,是活动到变迁的映射函数;

4) m i 是初始标识, m f 是终止标识.

除非特别指出,只有可见变迁可以标记为活动.假设 τ A 表示所有的不可见变迁.为方便起见, A τ = A ∪{ τ } 表示 A 与{ τ }的并集.

定义8 [4] . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型,每一个变迁 t T 对应于流程执行中的一个活动.模型 N s 的一条活动序列 l A * ,或空序列是活动的一条有限序列,即迹. L ∈B( A * )是一个事件日志,即迹的一个多重集. ξ 表示一个空事件日志.

由于不同的实例可能有相同的迹,因此一个事件日志是一个迹的多重集.如果不关心迹的发生频数,可以将一个日志看成一个迹的集合,即 L ={ l 1 , l 2 ,…, l n }.在定义8中,一个事件是指一个活动.通常,事件日志还记录了事件的其他信息,比如时间戳、资源和附加数据元素等.

Fig. 2 An example of an engineering drawing process N d
图2 工程图设计流程N d

图2给出了汽车制造厂的工程图设计流程.在这个模型中, A ={Submit,Design,…,Archive}, α ( t 1 )=Submit, α -1 (Insulation Proof)= t 4 . l =〈Submit,Design,Electrician Proof,Check Inventory,Evaluate,Archive〉是该模型的一条迹,对应的引发序列是 σ =〈 t 1 , t 2 , t 4 , t 5 , t 6 , t 7 〉.对于 l σ ,有 α ( σ )= l α -1 ( l )= σ .

如果一条迹缺少活动或者存在不同于模型的活动,则该迹不能被流程模型正确地重演.为了确定活动序列是否被完整地记录在事件日志中,给出了引发序列的概念.

定义9 [26-27] . N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型,则 N s 的一条引发序列及其后集可递归定义为:

1) 空序列 ε 是一条引发序列,且 ε * ={ b start };

2) 如果 σ 是一条引发序列, t i T (1≤ i ≤| T |)是一个变迁且 t i σ ,那么 σ t i 也是一条引发序列且( σ t i ) =( σ )-(

如果 σ 是模型 N s 的一条引发序列且 σ ={ b end },则称序列 σ 符合流程模型,记为 σ N s .如果 σ 不符合 N s ,则记为 σ / N s .

定义10 [5] . A 表示一个活动集,迹 l A * 是一个活动序列.&( l )是一个多重集,包含迹 l 的所有活动.

比如,如果 l ′=〈 a , b , h , i , k , s , m , o , m , o , t , p , r 〉,那么&( l ′)={ a , b , h , i , k , s , m 2 , o 2 , t , p , r }.

定义11 . A 表示一个活动集, L ∈B( A * )是一个事件日志, e A L 有一个活动,

e ={ a |∀ l L a A ∧〈 a , e 〉∈ l },

e ={ a |∀ l L a A ∧〈 e , a 〉∈ l },

e e 的前活动集, e e 的后活动集.

e e 表示 e 的外延活动.比如, =〈 a , b , h , i , k , s , m , o , m , o , t , p , r 〉, =〈 a , c , h , j , k , s , m , o , t , p , r 〉.在这种情况下, h ={ b , c }, h ={ i , j }.

3 模型修正

本节主要基于引发序列给出一种模型修正的方法.通常,可以通过对流程模型进行移除活动与增加活动的方式对流程模型进行修正.移除活动是将活动从流程模型中移除,增加活动是在合适的位置对流程模型增加活动.模型修正的目标是使修正的流程模型可以重演其(大多数)事件日志.

定义12 . N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型, L N s 的一个事件日志.如果∀ l L : l N s ,则称 N s 可以执行中 L 的每一个实例,即 N s 可以重演 L .如果∀ l L : l / N s ,则称 N s 不能够重演 L .

如果模型 N s 不能够重演其对应的事件日志 L

则需要将 N s 修正为 .∀ l L : l ,并且 N s 尽可能相似.

3 . 1 移除活动

当序列 σ t 在实际情况下可以发生,但对于模型来说, t σ 时,则需要在模型中将 σ t 之间的变迁移除.如果模型中描述活动从来没有记录在事件日志中时,则需要将该活动从模型中删除,如果模型中描述有活动被记录但是只有记录在部分事件日志中时,则需要在模型执行的过程中跳过该活动.模型中的活动可以通过2种方式移除:跳过变迁、删除变迁.

定义13 . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型. l = l k e N s 的一条迹,且 α -1 ( l )= α -1 ( l k e )= α -1 ( l k ) α -1 ( e )= σ k t i (1≤ i ≤| T |).如果 t i 是在 σ k t i 之间至少跳过一个变迁的间隔(gap).

间隔表明迹 l k e 可以在实际情况下执行,但是 l k e 不符合流程模型的描述规则.换句话说,在实际运行过程中, l k e 之间跳过了一些活动.

定义14 . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型, L ∈B( A * )是 N s 的一个事件日志.如果∃ t i T (1≤ i ≤| T |), α ( t i )= e ,但 L 中从来没有记录 e ,则称活动 e 是一个删除的活动.

定义14指出, N s 描述了活动 e ,但是在流程实际运行过程中, e 从来没有发生过,那么需要在 N s 中删除活动 e .

定理1 . N =( P , T ; F )是一个网,对于∀ t i T ,包含 t i 的结构可以通过 t i 确定.

证明.

对于 t i T ,如果∃ t i 在顺序结构中.

对于 t i T ,如果∃ 且∃ t k T t k = t i ,则 t i 在选择结构中.

对于 t i T ,如果∃ t j T ( t j )= ( t i ),则 t i 在并行结构中.

所以,可以通过 t i 确定包含 t i 的结构.

证毕.

给定流程模型 N s 和需要从 N s 移除的活动 e ,算法1给出了将 e 移出 N s 的方法.

算法1 . 从模型 N s 中移除活动 e .

Function RemoveActivity ( N s , e )

= N s ;

T 是变迁集合, T =transitions set;

i =1;

④ while ( i ≤| T |) do

⑤ if ( α ( t i )= e )

⑥ break;

⑦ end if

i ++;

⑨ end while

⑩ if ( t i 是可跳过变迁)

中添加 τ ,使 τ = t i , τ

t i τ 、从 τ 添加弧;

end if

if ( t i 是删除的变迁)

if ( JudgeStructure ( N s , e )=sequential)

t i =

t i 添加弧;

t i t i 、从 t i 删除弧;

中删除 t i

end if

if ( JudgeStructure ( N s , e )=choice)

t i t i 、从 t i 删除弧;

中删除 t i ;

end if

if ( JudgeStructure ( N s , e )=parallel)

( t i )到 t i 、从 t i t i 、从 t i 删除弧;

中删除 t i ;

end if

end if

return .

在算法1中,首先判断 e 是可跳过的活动,还是删除的活动.当 e 是可跳过的活动时,可以加入不可见变迁 τ .在流程执行的过程中,可以在 e τ 之间进行选择.如果 e 是删除的活动时,需要确定包含 e 的结构.如果 e 在顺序结构中,需要加入从 ( α -1 ( e ))到(( α -1 ( e )) ) 的弧,删除变迁 α -1 ( e )及库所( α -1 ( e )) ,同时要删除连接 α -1 ( e )与( α -1 ( e )) 的弧.对于 e 在选择结构或并行结构中,可以类似的处理.需要删掉连接 α -1 ( e )的弧与库所.根据算法1可以将一个活动从 N s 中移除.如果有连续的活动需要在 N s 中移除时,可以根据算法1将对应这些连续活动的一个子模型从 N s 移除.函数 DetermineStructure ( N s , e )可以用来确定包含 e 的结构,在算法2给出了该函数的实现方法.

算法2 . 确定活动 e 所在的结构.

Function DetermineStructure ( N s , e )

T 是变迁集合, T =transitions set;

S =null;

i =1;

④ while ( i ≤| T |) do

⑤ if ( α ( t i )= e )

j =1;

⑦ while ( j ≤| T |) do {

k = j +1;

⑩ while ( k ≤| T |) do {

if ( t k = t i )

S =choice;

break;

end if

S =sequential;

break;

end if

k ++;

end while

break;

end if

if ( ( t j )= ( t i ))

S =parallel;

break;

end if

j ++;

end while

break;

end if

i ++;

end while

return S .

在算法2中,包含 e 的结构可以通过 t i 确定.在每层循环中需遍历所有的变迁,算法2中有3层循环.| T |表示流程模型中的变迁数目,所以算法2的复杂度为 O (| T | 3 ).

对于图3的非正确模型 N 1 ,假设事件日志中包含2条迹: l 2 =〈 B , C , D , E , F , I 〉和 l 3 =〈 B , C , E , D , F , G , I 〉.对于 l 2 =〈 B , C , D , E , F , I 〉,〈 B , C , D , E , F 〉是引发序列,且〈 B , C , D , E , F ={ b 6 },对于活动 I I ={ b 8 } B , C , D , E , F .因此,〈 B , C , D , E , F 〉与 I 之间存在间隔.对于 l 3 =〈 B , C , E , D , F , G , I 〉,〈 B , C , E , D , F , G 〉是引发序列,且〈 B , C , E , D , F , G ={ b 7 }, I ={ b 8 } B , C , E , D , F , G .〈 B , C , E , D , F , G I 之间跳过了活动 K .

活动 G 记录在 l 3 中,但是没有记录在 l 2 中,如果要修正 N 1 ,需要在模型中跳过活动 G .如果要跳过 G ,可以添加不可见变迁 τ τ = G τ = G .同时要添加从 b 6 τ 及从 τ b 8 的弧.活动 K 即没有记录在 l 2 中也没有记录在 l 3 中,因此需要在 N 1 中删除 K .从 N 1 可以看出, K 是在顺序结构中.要删除 K ,需要加入从 G b 8 的弧,且删除库所 b 7 ,删除从 b 7 K 及从 K b 8 的弧. N 1 的修正模型如图4所示.

Fig. 3 An incorrect process model N 1
图3 非正确模型N 1

Fig. 4 The repaired model of N 1
图4 流程模型N 1 的修正模型

3 . 2 添加活动

通过在流程模型中插入额外的活动来添加活动.但是,在插入活动 e 时,需要在模型中确定 e 的插入位置(定义为 loc ( e )). e 并不会在每一条迹中都发生,因此,需要确定 e e e 之间的关系.如果插入的位置以及关系类型都已确定,则可以通过添加活动对模型进行修正.

通常有2个插入额外活动的位置,1个是 e 之后的最后一个活动,另一个是 e 之前的第1个活动,现在还没有办法确定这2个位置中的哪一个.因此,这2个位置都需要检查,然后评价模型的质量,选择使模型质量高的位置.

定义15 . A 表示一个活动集, L ∈B( A * )是 N s 的一个事件日志, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型. l = l k el m N s 的一条迹,如果 t i T (1≤ i ≤| T |): α ( t i )= e .则称活动 e 是一个额外的活动.

定义15表明迹 l 可以在实际情况下执行,但是有些活动在实际执行的过程中发生了,没有在 N s 中描述,因此,需要将这些额外的活动添加到模型中.

定理2 . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型. L 是关于 N s 的一个事件日志, e 对于 N s 是一个额外活动.当在 N s 中插入 e 时,可以通过 e e 确定 loc ( e ).

证明. 假设 t | T |+1 N s 的一个额外变迁并且 α ( t | T |+1 )= e .对于∀ l L ,如果 e ∈&( l ),则 e 应该在顺序结构中或并行结构中.如果对于∀ l L ,有 e ={ α ( t i )}且 e ={ α ( t j )}.那么 t | T |+1 ( α ( t | T |+1 )= e )应该插入到 t i t j 之间,并满足 如果对于∀ l L e e ≠∅.对于 α ( t k )∈ e e ,需要用并行结构连接 t | T |+1 α ( t k ),并满足 ( t | T |+1 )= ( t k )且( t | T |+1 ) 如果∀ l L , e ∈&( l )且∃ l ′∈ L , e ∉&( l ′),则 e 应该在选择结构中.如果∃ α ( t i )∈&( l ′), α ( t i )= e α ( t i ) = e (即 α ( t i )与 e 有相同的外延),则需要用选择结构连接 t | T |+1 t i ,并满足 t | T |+1 = t i t | T |+1 因此,可以通过 e e 确定 loc ( e ).

证毕.

定理2表明在流程模型中, loc ( e )可以由 e e 确定.由定理2可以确定 e 与模型中其他活动的关系.

给定流程模型 N s 和模型 N s 的额外活动 e ,算法3给出了将 e 插入 N s 的方法.

算法3 . 在模型 N s 中添加活动 e .

Function AddActivity ( N s , e )

= N s ;

T 是变迁集合, T =transitions set;

t | T |+1 是额外活动, 即 α ( t | T |+1 )= e ;

α ( t k )∈ e ;

α ( t m )∈ e ;

⑥ if ( DetermineActivitiesRelationship ( e ,

α ( t m ))=sequential)

⑦ 在 中添加变迁 t | T |+1 使

⑧ 添加库所 t | T |+1 使 t m = t | T |+1 ;

⑨ 从 t | T |+1 、从 t | T |+1 t | T |+1 、从 t | T |+1 t m 添加弧;

⑩ end if

if ( DetermineActivitiesRelationship ( e ,

α ( t m ))=choice)

中添加变迁 t | T |+1 使 t | T |+1 = t m , t | T |+1

t m t | T |+1 、从 t | T |+1 添加弧;

end if

if ( DetermineActivitiesRelationship ( e ,

α ( t m ))=parallel)

α ( t m )= d ;

if ( JudgeStructure ( N s , d )=parallel)

中添加变迁 t | T |+1 使 ( t | T |+1 )=

( t m ),( t | T |+1 )

添加库所 t | T |+1 t | T |+1 使 t | T |+1

( t m ), t | T |+1

( t m )到 t | T |+1 、从 t | T |+1 t | T |+1 、从 t | T |+1 t | T |+1 、从 t | T |+1 添加弧;

else

中添加变迁 t | T |+1 使 ( t | T |+1 )=

( t m ),( t | T |+1 )

添加库所 t | T |+1 使( ( t m )) =

{ t | T |+1 , t m };

添加库所 t | T |+1 使

{ t | T |+1 ,

( t m )到 t | T |+1 、从 t | T |+1 t | T |+1 、从 t | T |+1 t | T |+1 、从 t | T |+1 添加弧;

end if

end if

return .

在算法3中, e N s 的一个额外活动时, t | T |+1 是一个额外变迁,满足 α ( t | T |+1 )= e α ( t k )∈ e α ( t m )∈ e .当 t k t | T |+1 t m 在顺序结构中时, t | T |+1 可以插入到 t k t m 之间,并且要加入必要的库所与弧.如果 t k t | T |+1 t m 不在顺序结构中,那么 t | T |+1 t k / t m 应该在选择结构或并行结构中.算法3给出了 t | T |+1 t m 在选择结构或并行结构的情况, t | T |+1 t k 在选择结构或并行结构的情况可以类似的处理.当 t | T |+1 t m 在选择结构中时, t | T |+1 插入到 N s 中应该满足 t | T |+1 = t m t | T |+1 并加入必要的弧.当 t | T |+1 t m 在并行结构中时,需要确定 t m 是否在并行结构中,如果 t m 在并行结构中时, t | T |+1 插入到 N s 中应该满足 ( t | T |+1 )= ( t m )且( t | T |+1 ) 并加入必要的库所和弧.如果 t m 不在并行结构中,需要构建一个包含 t | T |+1 t m 的并行结构,然后将该并行结构插入到 N s 中.算法3给出在 N s 中添加1个活动的方法.如果有连续的多个活动需要插入到 N s 中时,假设 Λ 为一个流程发现算法,通过 Λ 可以为任意日志返回一个拟合的模型.可以用 Λ 发现1个子模型,然后用算法3将该子模型插入到 N s 中.函数 DetermineActivitiesStructure ( a , b )可以确定包含 a b 的结构,在算法4给出了该函数的实现方法.

算法4 . 确定活动 a b 的关系.

Function DetermineActivitiesStructure ( a , b )

A 是活动集合, A =activities set;

L 是一个事件日志, L ∈B( A * );

R =null;

④ if ( a A b A )

⑤ for ( i =0; i ≤| L |; i ++)

⑥ if ( a ∈&( l i ))

⑦ if ( b ∈&( l i ))

⑧ if ( a b 的顺序是〈 a , b 〉)

j = i +1;

⑩ while ( j ≤| L |)

if ( a b 的顺序是〈 b , a 〉)

R =parallel;

break;

else j ++;

end if

end while

if ( j =| L |)

R =sequential;

end if

end if

else R =choice;

end if

else if ( b ∈&( l i ))

R =choice;

else

return null;

end if

end for

else

return null;

end if

return R .

在算法4中,当 a b 记录在一条迹中时,那么它们应该在顺序结构中或并行结构中.如果在每条迹中,它们的顺序总是〈 a , b 〉,则它们在顺序结构中.如果在一些迹中,它们的顺序是〈 a , b 〉,在其他迹中,它们的顺序是〈 b , a 〉,则 a b 在并行结构中.如果 a 包含在一条迹中,但 b 不能被记录在该迹中.类似地,如果 b 包含在一条迹中,但 a 不能被记录在该迹中.则 a b 在选择结构中.算法4需要遍历日志 L 中的所有迹,在算法4中包含2层循环.| L | 表示日志 L 中迹的数目.因此,算法4的复杂度是 O (| L | 2 ).

对于图5的非正确模型 N 2 ,假设事件日志中包含2条迹: l 4 =〈 B , C , D , E , F , G , I 〉和 l 5 =〈 B , C , E , D , F , G , J 〉.对于 l 4 =〈 B , C , D , E , F , G , I 〉,在变迁集 T 中不存在 t i t j (1≤ i , j ≤| T |),有 α ( t i )= D α ( t j )= I .因此, D I 是额外活动,需要插入到 N 2 中.同样,对于 l 5 =〈 B , C , E , D , F , G , J 〉, D 是一个额外活动.

Fig. 5 An incorrect process model N 2
图5 非正确模型N 2

Fig. 6 The repaired model of N 2
图6 流程模型N 2 的修正模型

l 4 =〈 B , C , D , E , F , G , I 〉与 l 5 =〈 B , C , E , D , F , G , J 〉中, D D ={ E }.因此, D E 在一个并行结构中,并且并行结构可以正确的重演这2条迹.由 N 2 可以看出, E 是在一个顺序结构中.因此,需要构建一个包含 D E 的并行结构,将该并行结构插入到 N 2 中.

l 4 =〈 B , C , D , E , F , G , I 〉包含 I 但不包含 J . l 5 =〈 B , C , E , D , F , G , J 〉包含 J 但不包含 I .这意味着迹中只能包含这2个活动中的1个.因此,只有包含 I J 的选择结构可以正确的重演这2条迹. N 2 的修正模型如图6所示:

3 . 3 改变子流程

通过在模型中添加活动或删除活动可以改变模型的行为,但通过改变模型的子流程同样可以改变模型的行为.如果迹中的一些活动关系不能被模型中相应的子流程描述,则需要在模型用可以描述活动关系流程将相应的子流程替换.换句话说,如果迹中存在异常活动,则需要改变模型中的子流程.下面给出了替换模型子流程的方法.

如果迹中存在异常活动 e ,则必定存在包含 e 的子日志 L a .模型中对应于 L a 的子流程 N a 不能重演

L a .假定 Λ 是流程发现算法,且 = Λ ( L a ),则可以用 替换 N a .因此,如果改变子流程,首先要在迹中确定异常活动.

定义16 . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型. l = l s l j l k el m l n l u N s 的一条迹,且 α -1 ( l )= α -1 ( l s l j l k el m l n l u )= α -1 ( l s ) α -1 ( l j ) α -1 ( l k ) α -1 ( e ) α -1 ( l m ) α -1 ( l n ) α -1 ( l u )= σ s σ j σ k t i σ m σ n σ u (1≤ i ≤| T |).如果 t i 或者 σ n ,则称 e ( α ( t i )= e )是一个异常活动.

给定流程模型 N s 和异常活动 e ,算法5给出了改变子流程的方法.

算法5 . 改变 N s 中包含 e 的子流程.

Function ChangeBehavior ( N s , e )

= N s ;

N a =null;

T 是变迁集合, T =transitions set;

l a = DetermineSubtrace ( e );

L a = DetermineSublog ( l a );

= Λ ( L a );

的初始库所;

的终止库所;

σ a = α -1 ( l a );

⑩ for ( i =0; i ≤| T |; i ++)

if ( t i ∈&( σ a ))

N a 中添加 t i , t i

end if

end for

b s N a 的初始库所;

b e N a 的终止库所;

= b s ;

、从 b 添加弧;

return .

在算法5中, e 是一个异常活动.函数 Determine - Subtrace ( e )确定了包含 e 的子迹 l a .根据 l a ,函数 DetermineSublog ( l a )确定了不能在 N s 上重演的子日志 L a .通过流程发现算法 Λ ( L a )得到了子流程 .然后根据 l a 中活动可以在 N s 中找到对应于 L a 的子流程 N a .最后可以用重新发现在的 替换模型中的 N a .算法6给出了根据 e 查找子迹 l a 的方法 DetermineSubtrace ( e ).算法7给出了根据 l a 查找子日志的方法.

算法6 . 确定 N s 不能重演的子迹.

Function DetermineSubtrace ( e )

A 是活动集合, A =activities set;

L 是一个事件日志, L ∈B( A * );

t = α -1 ( e );

l a = e ;

⑤ for ( i =0; i ≤| L |; i ++)

σ i = α -1 ( l i );

⑦ if ( t ∈&( σ i ))

j = σ i ( t );

k = σ i ( t );

⑩ if ( α ( ( t ))∉ l a )

l a = α ( ( t )) l a ;

j = j -1;

while ( j ≥0)

if ( α ( ( t j ))∉ l a )

if ( α ( ( t j ))∉&( l a ))

l a = α ( ( t j )) l a ;

end if

j --;

else

break;

end if

end while

end if

if ( α ( t ) )∉ )

l a = l a α (( t ) );

k = k +1;

while ( k ≤| σ i |)

)

∉&( l a ))

end if

k ++;

else

break;

end if

end while

end if

end if

end for

return l a .

算法6首先判断 e 中的活动是否与 ( t )( t = α -1 ( e ))相同,将不同的活动添加到 l a 中.然后迭代的判断 l a 中的活动,将所有不同的活动添加到 l a 中. e 中的活动查找完之后,对 e 中的活动进行相同的操作.在每一次的循环中需要对日志 L 中的所有迹进行遍历,需要遍历每条迹中的所有活动.| l |表示 L 中最长迹的长度,因此,算法6的复杂度是 O (| L |×| l |).

算法7 . 确定需要重新发现的子日志.

Function DetermineSublog ( l a )

A 是活动集合, A =activities set;

L 是一个事件日志, L ∈B( A * );

L a ={ l a };

④ for ( i =0; i ≤| L |; i ++)

= ε ;

⑥ for ( j =0; j ≤| l i |; j ++)

⑦ if ( l i [ j ]∈&( l a ))

= l i [ j ];

⑨ end if

⑩ end for

end for

L a = L a + ;}

return L a .

算法7首先定义了只包含 l a 的子日志 L a ,然后遍历日志 L 中的所有迹.对于每条迹来说,如果子迹 包含的活动与 l a 相同,则将 添加到 L a 中.最后,可以得到不能被模型描述的子日志 L a .

对于图7的非正确模型 N 3 ,假设事件日志中包含2条迹: l 6 =〈 B , C , D , E , F , G , I 〉和 l 7 =〈 B , C , E , D , F , H 〉. l 6 =〈 B , C , D , E , F , G , I 〉中的活动可以按 N 3 的执行,而在 l 7 =〈 B , C , E , D , F , H 〉存在一个异常活动 E .在 l 7 中, E 前边的活动是 C ,但在 N 3 中, α ( t 5 )= E ( t 5 )= t 4 α ( t 4 )= D E 后边的活动是 D ,而 因此,子迹 l a =〈 C , E , D , F 〉不能被 N 3 描述 .在 l 6 中,相应的子迹为 =〈 C , D , E , F 〉.

根据 l a ,可重新发现可以正确描述 D E 关系的子模型.通过 l a 可以确定, D E 在平行结构中,但在 N 3 中, D E 在顺序结构中.因此需要将 N 3 中的顺序结构替换为并行结构. N 3 的修正模型如图8所示.

Fig. 7 An incorrect process model N 3
图7 非正确模型N 3

Fig. 8 The repaired model of N 3
图8 流程模型N 3 的修正模型

3 . 4 修正循环结构

在修正有循环结构的模型时,需要确定迹中重复的子迹,在模型中找到可以描述该子迹的子模型,在迹中确定“redo”活动,通过在模型中添加“redo”活动,使模型可以重演重复的子迹 [28] .因此,在修正模型时需要在模型中确定循环体,并在模型添加“redo”活动.

定义 17 . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型. l = l s l b e l b l u N s 的一条迹. l b e 是一条循环子迹,且 l ( l b )- l ( e )=1.如果 N s 可以重演 l b ,但 t i T (1≤ i ≤| T |): α ( t i )= e ,则称 l b 为循环体, e 为“redo”活动.

定义17表明迹 l 可以在实际情况下执行,但是 N s 中不存在“redo”活动 e ,因此只能重演第1次出现的子迹 l b ,其他重复的子迹 l b 不能重演.为了修正 N s 可以重演其他的 l b ,需要在模型中添加活动 e .

定理3 . A 表示一个活动集, N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型. L 是关于 N s 的一个事件日志, e 对于 N s 是一个额外活动,且∃ l L : l ( e )>1.那么可以通过 e 确定迹中的重复子迹.

证明. e N s 的一个额外活动,且∃ l L : l ( e )>1.对于 l ( e )>1,那么在 l e 至少迭代了2次.那么在这第1次 e 与第2次 e 之间存在一条子迹 l b ,且 l ( l b )- l ( e )=1.因此 e 是“redo”活动, l b 是重复子迹.

证毕.

给定流程模型 N s 和“redo”活动 e ,算法8给出了发现和添加循环结构的方法.

Fig. 9 An incorrect process model N 4
图9 非正确模型N 4

算法8 . 在模型 N s 发现并添加循环结构.

Function AddLoops ( N s , e )

= N s ;

N b =null;

T 是变迁集合, T =transitions set;

t | T |+1 是额外活动, 即 α ( t | T |+1 )= e ;

l b = DetermineLoopbody ( e );

σ b = α -1 ( l b );

⑦ for ( i =0; i ≤| T |; i ++)

⑧ if ( t i ∈&( σ b ))

⑨ 在 N b 中添加 t i , t i

⑩ end if

end for

b s N b 的初始库所;

b e N b 的终止库所;

b s = t | T |+1 ;

b e = t | T |+1 ;

b e t | T |+1 、从 t | T |+1 b s 添加弧;

return .

在算法8中, e 是1个“redo”活动.函数 Determine - Loopbody ( e )确定了重复子迹 l b .根据 l b 中的活动,可以找到对应该于 l b 的子模型 N a .在 N s 中添加活动 e 之后, N s 可以重演其他迭代的 l b .在本文中,假设循环体可以正确重演第1次迭代的 l b ,然后用算法8修正有循环结构的模型.如果循环体不能重演 l b ,就用前面提到的方法对循环体进行修正.有些情况下,迹中只包含重复子迹,没有“redo”活动,那么在修正模型时需要加入不可见变迁作为“redo”活动.函数 DetermineLoopbody ( e )可以确定重复子迹 l b ,在算法9中给出了其实现方法.

算法9 . 确定重复子迹.

Function DetermineLoopbody ( e )

A 是活动集合, A =activities set;

L 是一个事件日志, L ∈B( A * );

l b = ε ;

④ for ( i =0; i ≤| L |; i ++)

⑤ if ( e ∈&( l i ))

⑥ for ( j =0; j ≤| l i |; j ++)

⑦ if ( l i ( l i [ j ])>1且 l i [ j ]∉&( l b ))

l b = l b l i [ j ];

⑨ end if

⑩ end for

end if

end for

return l b .

在算法9中,需要确定活动 e 是否在 l i .如果 e 存在于 l i 中,则可以通过 l i ( l i [ j ])确定重复的活动.其中 l i [ j ]表示 l i 中的第 j 个活动, l i ( l i [ j ])表示在 l i l i [ j ]的发生次数. l i ( l i [ j ])>1表示 l i [ j ]是重复活动, l i [ j ]应该在重复子迹 l b .| l |表示日志 L 中最长迹的长度,在每次循环中需要遍历 L 中的每一条迹,对于迹 l i 需要遍历迹中的每一个活动,因此,算法9的复杂度是 O (| L |×| l |).

对于图9的非正确模型 N 4 ,假设事件日志中包含2条迹: l 7 =〈 A , B , C , D , E , G , B , D , C , E , G , B , C , D , E , F , I 〉和 l 8 =〈 A , B , D , C , E , G , B , C , D , E , H 〉.

B , C , D , E , G 〉或〈 B , D , C , E , G 〉是2条迹中的重复子迹. N 4 不能描述活动 G ,且 l 7 (〈 B , D , C , E 〉)>1, l 8 (〈 B , D , C , E 〉)>1.因此, G 是“redo”活动,〈 B , D , C , E 〉是循环体. N 4 可以正确重演〈 B , D , C , E 〉,在 N 4 中添加活动 G G ={ b 6 }, G ={ b 1 }. N 4 的修正模型如图10所示:

Fig. 10 The repaired model of N 4
图10 流程模型N 4 的修正模型

3 . 5 完整修正

如果流程模型 N s 可以重演日志 L ,则不需要对模型进行修正.如果 N s 不能重演 L ,则需要根据 L N s 修正.对于 L 中的迹,需要判断能否在模型重演,如果不能重演,则要找出迹与模型之间的偏差,然后根据偏差的类型,对模型进行相应的修正.根据日志 L ,算法10给出了对模型 N s 的修正方法.

算法10 . 根据日志 L 对模型 N s 修正.

Function ModelRepair ( N s , L )

= N s ;

② for ( i =0; i ≤| T |; i ++)

③ if ( Replayed ( , l i ))

④ break;

⑤ else

DE = LocateDeviation ( , l i );

⑦ for ( j =0; j <| DE |; j ++)

⑧ if ( d j 是移除的活动)

= RemoveActivity ( N s , d j );

⑩ end if

if ( d j 是额外的活动)

if ( d j 是“redo”活动)

= AddLoops ( N s , d j );

else

= AddActivity ( N s , d j );

end if

end if

if ( d j 是错位的活动)

= ChangeBehavior ( N s , d j );

end if

end for

end if

end for

return .

在算法10,遍历了 L 中的每条迹,通过 Replayed ( , l i )判断 l i 是否可以 上重演.如果 可以很正常 l i ,则进入下一次循环.否则通过 LocateDeviation ( , l i )查找 l i 之间的偏差.根据不同的偏差,应用算法1、算法3、算法5或算法8对 进行相应的修正.函数 Replayed ( , l i )是判断 能否重演 l i ,如果可以,则返回true,否则返回false.函

LocateDeviation ( , l i )查找 l i 之间的偏差,返回值是偏差的集合,记录了偏差类型以及出现偏差的位置.这2个函数在接下来的工作中给出了相应的实现方法.

定理4 . N s =( P , T ; F , α , α -1 , m i , m f )是一个流程模型, L 是关于 N s 的一个事件日志.根据日志 L

通过算法10对 N s 进行修正,得到的修正模型 可以重演日志中每条迹.

证明. 假设∃ l L 不能重演迹 l .如果 不能重演 l ,则 Replayed ( , l i )的返回值是false,所以算法会通过函数 LocateDeviation ( , l ),查找 l 之间存在的偏差.如果偏差是移除活动,则通过 RemoveActivity ( N s , d j )在流程中移除该活动.如果偏差是额外的活动,需要判断该活动是否为“redo”活动,如果是,则通过 AddLoops ( N s , d j )在流程中添加循环结构,否则通过 AddActivity ( N s , d j )在流程中添加该活动.如果偏差是异常活动,则通过 ChangeBehavior ( N s , d j )改变流程的子流程.由此可见,通过修正 可以重演 l ,与假设是矛盾的.所以,根据日志 L ,通过算法10对 N s 进行修正,得到的修正模型 可以重演日志中每条迹.

证毕.

4 仿真实验

对本文提出的模型修正方法进行了手工模拟,对重新发现的挖掘方法与增加子流程的修正方法在ProM 6(process mining toolkit)上进行了验证.运行ProM的计算机需要是64位的Win7系统,3.20 GHz的处理器及1 GB的Java虚拟内存.在本节,给出了模型修正方法的实验评价.

4 . 1 实验数据

在这部分,根据青岛某三甲医院信息系统的流程模型与事件日志给出了2个实验,实验结果表明了本文方法的正确性与实用性.医院信息系统的住院流程模型如图11所示.但是由于每个医生和病人在执行流程时,根据不同的需求会有不同的处理方式.因此,在医院观察到的实际流程会与参考模型(reference model)存在偏差.

Fig. 11 A process model of hospitalization in a hospital
图11 医院的住院流程模型

从医院信息系统中提取了5个未加工的日志( L 1~ L 5).从这些日志中,通过删除明显不拟合参考模型的案例得到了5个过滤的日志( L 1 f L 5 f ),比如,删除缺少开始活动或不完整的日志.表1显示了这10个日志的一些属性,会在接下来的内容讨论.在这个表中列出了迹的数目、最小和最大长度,利用过滤的日志( L 1 f L 5 f )进行手工修正时添加的变迁和库所的数目以及移除的变迁数目.

Table 1 10 Logs from Hospital to a Reference Model and the Properties of Manual Repaired Models

表1 医院信息系统的10个日志与手工修正模型的属性

LogEventLogManualRepairTracesLengthAddedRemove|T||P||T|SkippedDeletedL13431~41L23061~61L33511~42L45211~41L53174~41L1f2199~413712L2f1789~614822L3f2419~423641L4f3399~415532L5f2899~417424

4 . 2 手工修正

为了获得指导模型修正的最优标准,我们得到了专家用手工修正的参考模型.根据日志 L 1 f 手工修正的模型如图12所示,对参考模型进行改变:添加了4个活动、跳过了1个活动、删除了2个活动、模型的修正部分由虚线圆标出.参考模型中有64个库所、68个变迁、149条弧,表1给出了根据每个过滤日志通过手工修正得到的模型与参考模型之间的差别.根据日志 L 5 f 修正,对模型的改变最大,因为需要添加子流程,跳过一些变迁并删除一些变迁.根据 L 1 f L 2 f 的修正,对移除活动的改变比较少.根据 L 4 f 的修正,添加的活动与移除的活动相等.

Fig. 12 Manually repaired model for log L1f
图12 根据日志L1f手工修正的流程模型

4 . 3 实验对比

对于给定的日志与流程模型,第3节给出了模型修正的方法,使修正的流程模型符合给定的事件日志.函数 RemoveActivity ( N s , e )可以识别跳过的活动与删除的活动,并将这些活动从流程模型中移除.函数 AddActivity ( N s , e )可以识别额外的活动,并将这些活动添加到流程模型中.函数 Change - Behavior ( N s , e )可以识别不能被模型描述的子日志,并用重新发现的子流程替换模型中的相应部分.函数 AddLoops ( N s , e )可以识别日志中的“redo”活动,并在模型中添加循环结构.函数 ModelRepair ( N s , L ),可以根据日志 L ,对模型 N s 进行整体修正.

根据提取的5个过滤日志,手工模拟本文提出的修正方法,对参考模型进行了修正.对于每个过滤日志,通过ProM 6上的Repair Model [29] 插件完成了增加子流程方法对参考模型的修正,利用ProM 6中Alpha Miner [18] 插件得到了重新挖掘的流程模型.为了评价论文中提出的模型修正技术,我们进行实验对比.

4.3.1 模型相似度

由定义11可知,修正的模型要与参考模型尽可能相似.图编辑相似度(graph edit similarity) [30] 大致地表明了参考模型与修正/重新发现模型(repaired/rediscovered model)之间的差异部分,即1.0表示模型完全相同.为了证明基于引发序列修正的流程模型(process model repair via alignment)的有效性,根据文献[30]中的图编辑相似度公式,手工计算了参考模型与基于引发序列修正的模型之间的相似度、手工修正的模型与参考模型之间的相似度、增加子流程修正的模型(add sub-processes repaired model) [29] 与参考模型之间的相似度以及Alpha算法 [18] 发现模型与参考模型之间的相似度,其结果如图13所示:

Fig. 13 Similarity on different repair methods
图13 对于每个日志不同修正模型之间的相似度

由图13可知,手工修正模型、基于引发序列的修正模型、增加子流程的修正模型都与参考模型非常相似,因为其相似度值基本在0.9以上.手工修正的模型较基于校对序列修正的模型相似于参考模型,比如对于日志 L 2 f 来说,基于引发序列修正模型与参考模型的相似度是0.952 4,手工修正模型与参考模型的相似度是0.958 7.在有些情况下,基于引发序列修正的模型比增加子流程修正的模型更相似于参考模型,比如对于日志 L 3 f 来说,基于引发序列修正模型与参考模型的相似度是0.924 7,增加子模型修正模型与参考模型的相似度是0.880 9.但有些情况下,增加子流程修正的模型比基于引发序列修正的模型更相似于参考模型,比如对于日志 L 4 f 来说,增加子模型修正模型与参考模型的相似度是0.946 0,基于引发序列修正模型与参考模型的相似度是0.922 3.这是由于有些情况下,基于引发序列的修正方法会改变参考模型的子流程,而增加子流程的修正方法会在参考模型中加入一个结构比较复杂的子流程.通过Alpha算法重新挖掘得到的模型与参考模型之间的相似度比较差,其相似度基本都小于0.9,这是因为根据日志重新挖掘得到的模型可能会改变参考模型的结构.

4.3.2 迹的完全重演率

模型修正的目的是使修正的流程模型可以重演(大多数)相应的事件日志.迹的完全重演率指的是模型可以完全重演的迹所占日志中迹的百分比.通过迹的完全重演率可以证明修正方法的正确性,即100%意味着模型可以完全重演日志中的所有迹.为了检测基于引发序列模型修正的正确性,通过ProM中的Replay a Log on Petri Net for All Optimal Alignment插件,计算日志 L 1 f L 5 f 在参考模型,增加子流程修正模型与Alpha算法发现模型上的所有最优校准,并统计了日志在各模型上重演得到的最优校准(即校准序列中只有同步动作,没有日志动作或模型动作)的条数,以此作为日志可以在模型完全重演迹的条数.对于基于引发序列修正模型,通过模拟迹在模型上的重演,统计了日志在模型上完全重演迹的条数.修正或重新发现模型上迹的完全重演率如图14所示:

Fig. 14 Replayed trace percentages of different repair methods for logs
图14 对于每个日志不同修正模型上迹的完全重演率

从迹的重演率上可以看出,手工修正模型可以完全重演过滤的5个日志中的所有迹,因为迹的重演率都是100%.基于引发序列修正的模型基本可以完全重演日志中80%以上的迹.而参考模型的迹重演率基本都在80%以下,由此可以证明本文所提修正方法的正确性.而通过Alpha算法挖掘发现模型的迹重演率不稳定,比如对于 L 2 f 来说,迹的重演率是85.95%;而对 L 3 f 来说,其结果是31.53%,这是由于重新挖掘的模型不一定能够解决现有模型存在的问题.而增加子流程修正模型的迹重演百分率都比较低,这是由于增加子流程的修正方法不能修正模型中的选择分支结构,而参考模型中存在多个选择分支.根据日志 L 1 f L 5 f ,通过增加子流程修正的模型都将参考模型中的一条正确分支上所有活动修正为不可见变迁,这导致在求模型与日志的所有最优准时,将日志中的相应活动当作了日志动作.日志与模型最优校准的条数会相应减少,导致修正模型的迹重演率严重降低.

5

本文给出了一种流程模型的修正方法.在模型修正的过程中,主要考虑模型的拟合度.对于日志中从来没记录的活动,给出了将这些活动移除流程模型的方法.对于流程模型没有描述的活动,给出了在模型的合适位置添加子流程的方法.对于迹中活动关系与模型中相应的子流程描述不一致的,给出了改变模型子流程的方法.该模型修正方法目的是使得到的修正模型可以重演(大多数)相应的事件日志,并尽可能地与参考模型相似.最后通过相似度与迹的完全重演率证明了所提方法的有效性与正确性.

未来工作是如何修正存在循环结构的流程模型,并在模型修正的过程中参考模型的其他符合性标准,比如泛化度与精确度等.

参考文献

[1] Manyika J, Chui M, Brown B. Big data: The next frontier for innovation, competition and productivity[EB/OL]. (2011-07-01)[2015-05-20]. http://www.mckinsey.com/insights/business-technology/big_data_the_next_frontier_for_innovation

[2] Li Guojie. The scientific value of big data research[J]. Communications of the CCF, 2012, 8(9): 8-15 (in Chinese)(李国杰. 大数据研究的科学价值[J]. 中国计算机学会通讯, 2012, 8(9): 8-15)

[3] Olson D L, Kesharwani S. Enterprise Information Systems: Contemporary Trends and Issues[M]. River Edge, NJ: World Scientific, 2009: 13-16

[4] van der Aalst W M P. Process Mining: Discovery, Conformance and Enhancement of Business Processes[M]. Berlin: Springer, 2011: 1-10

[5] Wang Lu, Du Yuyue, Liu Wei. Aligning observed and modelled behaviour based on workflow decomposition[J]. Enterprise Information Systems, 2017, 11(8): 1207-1227

[6] Wang Lu, Du Yuyue. An alignment-based identifying method of the problem areas within process models[J]. Journal of Shandong University of Science and Technology: Nature Science, 2015, 34(1): 42-46,53 (in Chinese)(王路, 杜玉越. 一种基于校准的模型问题域识别方法[J]. 山东科技大学学报:自然科学版, 2015, 34(1): 42-46,53)

[7] Du Yuyue, Sun Yanan, Liu Wei. Petri nets based recognition of model deviation domains and model repair[J]. Journal of Computer Research and Development, 2016, 53(8): 1766-1780 (in Chinese)(杜玉越, 孙亚男, 刘伟. 基于Petri网的模型偏差域识别与模型修正[J]. 计算机研究与发展, 2016, 53(8): 1766-1780)

[8] Rodrguez A, Fernndez-Medina E, Piattini M A. BPMN extension for the modeling of security requirements in business processes[J]. IEICE Trans on Information and Systems, 2007, 90(4): 745-752

[9] van der Aalst W M P. Formalization and verification of event-driven process chains[J]. Information and Software Technology, 1999, 41(10): 639-650

[10] Murata T. Petri nets: Properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4): 541-580

[11] Du Yuyue, Qi Liang, Zhou Mengchu. A vector matching method for analyzing logic Petri nets[J]. Enterprise Information Systems, 2011, 5(4): 449-468

[12] Du Yuyue, Qi Liang, Zhou Mengchu. Analysis and application of logical Petri nets to e-commerce systems[J]. IEEE Trans on Systems, Man, and Cybernetics: Systems, 2014, 44(4): 468-481

[13] Du Yuyue, Jiang Changjun, Zhou Mengchu. A Petri net-based model for verification of obligations and accountability in cooperative systems[J]. IEEE Trans on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2009, 39(2): 299-308

[14] Du Yuyue, Jiang Changjun, Zhou Mengchu, et al. Modeling and monitoring of e-commerce workflows[J]. Information Sciences, 2009, 179(7): 995-1006

[15] Du Yuyue, Wang Lu, Qi Man. Constructing service clusters based on service space[J]. International Journal of Parallel Programming, 2017, 45(4): 982-1000

[16] Rozinat A, van der Aalst W M P. Conformance checking of processes based on monitoring real behavior[J]. Information Systems, 2008, 33(1): 64-95

[17] Petkovic M, Prandi D, Zannone N. Purpose control: Did you process the data for the intended purpose?[C] //Proc of the 8th VLDB Int Conf on Secure Data Management. Berlin: Springer, 2011: 145-168

[18] van der Aalst W M P, Weijters A J M M, Maruster L. Workflow mining: Discovering process models from event logs[J]. IEEE Trans on Knowledge and Data Engineering, 2004, 16(9): 1128-1142

[19] Wen Lijie, van der Aalst W M P, Wang Jianmin, et al. Mining process models with non-free-choice constructs[J]. Data Mining & Knowledge Discovery, 2007, 15(2): 145-180

[20] Wen Lijie, Wang Jianmin, Sun Jiaguang. Invisible tasks from event logs[G] //Advances in Data and Web Management. Berlin: Springer, 2007: 358-365

[21] Badouel E. On the α-reconstructibility of workflow nets[G] //Application and Theory of Petri Nets. Berlin: Springer, 2012: 128-147

[22] Bergenthum R, Desel J, Lorenz R, et al. Process mining based on regions of languagesn[C] //Proc of the 5th Int Conf on Business Process Management. Berlin: Springer, 2007: 375-383

[23] Bergenthum R, Desel J, Mauser S, et al. Synthesis of Petri nets from term based representations of infinite partial languages[J]. Fundamenta Informaticae, 2009, 95(1): 187-217

[24] Cortadella J, Kishinevsky M, Lavagno L, et al. Deriving Petri nets from finite transition systems[J]. IEEE Trans on Computers, 1998, 47(8): 859-882

[25] van der Werf J M E M, Dongen B F V, Hurkens C A J, et al. Process discovery using integer linear programming[J]. Fundamenta Informaticae, 2008, 94(3): 368-387

[26] Wang Jianmin, Song Shaoxu, Zhu Xiaochen, et al. Efficient recovery of missing events[J]. Proceedings of the VLDB Endowment, 2013, 6(10): 841-852

[27] Wang Jianmin, Song Shaoxu, Lin Xuemin, et al. Cleaning structured event logs: A graph repair approach[C] //Proc of the 31st IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2015: 30-41

[28] van der Aalst W M P. The application of Petri nets to workflow management[J]. The Journal of Circuits, Systems and Computers, 1998, 8(1): 21-66

[29] Fahland D, van der Aalst W M P. Model repair-aligning process models to reality[J]. Information Systems, 2015, 47(1): 220-243

[30] Dijkman R M, Dumas M, Garcabauelos L. Graph matching algorithms for business process model similarity search[C] //Proc of the 7th Int Conf on Business Process Management. Berlin: Springer, 2009: 835-842

Process Model Repair Based on Firing Sequences

Wang Lu, Du Yuyue, and Qi Hongda

( College of Computer Science and Engineering , Shandong University of Science and Technology , Qingdao , Shandong 266590)

Abstract When business processes are mostly supported by information systems, the availability of event logs generated from these systems and the requirements of appropriate process models are increasing. However, some events cannot be correctly identified because of the explosion of the amount of event logs. Conformance checking techniques can be used to detect and diagnose the differences between observed and modeled behavior, but they cannot repair the actual model. The information from conformance checking can be used for model repair. By means of the firing sequences of event logs, process models can be repaired from three aspects: removing behavior, adding behavior and changing behavior. The structure with deleted activity in process model, the relationship between additional activities and adjoin activities, and the nonconformance sub-process in process model should be identified when the process model need repairing. It is obtained that the repaired model can replay (most of) event logs based on the proposed techniques, and it is as similar to the original model as possible. The methods in this paper are simulated manually. A real-world process model of hospitalization in a hospital and the corresponding event logs are employed to evaluate the proposed approaches. The correctness and effectiveness of the proposed methods are illustrated through experiments.

Key words process mining; conformance checking; firing sequence; model repair; replay

摘 要 随着信息系统在业务流程中的广泛应用,对事件日志与业务流程的需求也随之增加.由于事件日志的爆炸式增长,有些事件日志不能被流程模型正确地重演.通过合规性检查可以检测与诊断模型与日志之间存在的差异.但是,合规性检查技术不能对流程模型做出正确的修正.基于事件日志中的引发序列,从移除活动、增加活动及改变模型子流程3个方面解决了流程模型的修正问题.在进行模型修正时,需要确定移除的活动在模型中所在的结构、增加的活动与相邻活动的关系以及需要改变的子流程.流程模型修正的目的在于使修正的流程模型可以重演(大多数)的事件日志,并且使得到的修正模型尽可能与原模型相似.通过仿真模拟提出的修正方法,实验验证了该方法的正确性与实用性.

关键词 流程挖掘;合规性检查;引发序列;模型修正;重演

中图法分类号 TP18; TP311.13

收稿日期: 2016-11-15;

修回日期: 2017-05-23

基金项目: 国家自然科学基金项目(61170078,61472228);山东省泰山学者建设工程专项基金项目;山东省自然科学基金项目(ZR2014FM009);山东科技大学科技创新项目(SDKDYC170222);山东省重点研发计划项目(2016GGX101031)

This work was supported by the National Natural Science Foundation of China (61170078, 61472228), the “Taishan Scholar” Construction Project of Shandong Province, the Natural Science Foundation of Shandong Province of China (ZR2014FM009), the Science and Technology Innovation Project of Shandong University of Science and Technology (SDKDYC170222), and the Key Research and Development Project of Shandong Province (2016GGX101031).

通信作者: 杜玉越(yydu001@163.com)

Wang Lu , born in 1989. PhD candidate. Her main research interests include process mining, workflow and Petri nets.

Du Yuyue , born in 1960. PhD. Professor. His main research interests include process mining, workflows and Petri net application.

Qi Hongda , born in 1993. Master candidate. His main research interests include process mining, workflows and Petri nets (hongda_qi@hotmail.com).