基于Petri网的分层业务过程挖掘方法

刘 聪,程 龙,曾庆田,闻立杰,欧阳春

(1.山东理工大学 计算机科学与技术学院, 山东 淄博 255000;2.都柏林大学 计算机学院,爱尔兰 都柏林D04 V1W8;3.山东科技大学 电子信息工程学院,山东 青岛 266590;4.清华大学 软件学院,北京 100084,5.昆士兰科技大学 信息系统系, 澳大利亚 布里斯班QLD 4000)

0 引言

过程挖掘作为业务过程管理[1](Business Process Management，BPM)领域的一个新的研究热点，旨在构建传统的模型驱动方法(如业务过程建模和模型正确性验证)和新型的数据驱动方法(如数据挖掘和机器学习)之间的桥梁。具体而言，过程挖掘的目标是从事件日志中抽取出有用的信息，来为企业业务过程的理解、改进和重构提供事实依据[2-6]。所谓事件日志，是指业务过程管理系统在运行的过程中所积累、收集的事件执行数据，通常包括过程的实际执行信息，如活动名称、时间戳、活动的执行者等。过程挖掘的一个主要方面是发现过程的控制流结构，即通过分析事件日志中记录的活动执行信息，自动构造一个能够描述活动间因果依赖关系的过程模型，这里的过程模型可以用Petri网[8]、EPC(event-driven process chain)[9]、BPMN(business process model notations)[10]等来描述。为了评估挖掘模型的质量，需要对事件日志和模型之间的合规性进行度量。当今，最常用的合规性度量指标为契合度(fitness)[11]，它量化了日志中轨迹可以被过程模型从头到尾重演(replay)的比例。其他常用的模型质量度量指标还包括准确性(precision)[12]和一般性(generalization)[13]。

已有的大多数过程挖掘技术，如Alpha Miner[14]、Tsinghua-Alpha Miner[15]、Split Miner[16], Inductive Miner[17]等，通过挖掘活动之间的顺序、并发、分支和循环依赖关系，进而构造一个扁平过程模型(flat process model)来描述日志中的行为。给定一个业务外包过程，其中一个组织将自己的部分业务过程外包给另外一个组织。外包的业务过程可以被看作原来过程的一个子过程，即过程之间存在层级调用关系。然而，针对扁平过程模型的传统过程挖掘方法，无法支持跨组织外包场景中对子过程与父过程活动之间调用关系的挖掘。而且，已有的过程模型合规性度量指标，如契合度、准确性、一般性和复杂性等，也都是针对扁平过程模型定义的。然而，这些指标对于包含父过程与子过程活动之间调用关系的分层过程模型与事件日志的质量评估并不适用。

本文提出一种从带有生命周期事件日志中挖掘分层业务过程模型的方法，并在挖掘得到分层模型的基础上，给出了质量度量指标。基于仿真日志数据和真实日志数据，比较了本文方法与已有过程挖掘方法挖掘得到模型的质量，进一步验证了所提方法的有效性。

1 相关工作

业务过程挖掘技术能够从现代信息系统普遍产生的事件日志中抽取有用信息，该技术为各应用领域中的过程发现、监测和改进提供了新的手段[6]。Van Der Aalst教授[18]指出，过程挖掘日益受到关注主要有以下两方面原因：①越来越多的事件得以记录，从而可以提供业务过程历史执行的详细信息；②在飞速变化的环境中改善和更好地支持业务过程的执行这一需求日益突显。作为过程挖掘技术的核心，过程发现是指通过分析事件日志中记录的活动执行信息，自动构造一个能够描述活动间因果依赖的过程模型(如Petri网或BPMN)。总体来讲，过程发现技术可以分为4类：①直接从活动执行轨迹中分析活动之间的顺序、冲突、并发等依赖关系，进而构造业务过程模型，该类方法的典型代表有Alpha Miner[14]、Tsinghua-Alpha Miner[15]、Split Miner[16], Inductive Miner[17]和Heuristic Miner[19]等；②基于计算智能的挖掘算法，这类算法首先设立一个种子模型，然后根据日志中实际执行轨迹与模型行为的差别不断调整模型，使其成为一个符合要求的过程模型，该类方法主要包括Genetic Miner[20]和Evolution Tree Miner[21]；③两阶段过程发现算法，第一阶段是从事件日志出发构造出描述过程行为的一个“低级”模型，如自动机模型，第二阶段将“低级”模型转换为能表达并发等复杂过程控制语义的“高级”模型，该类方法的代表是文献[22]中提出的基于区域的过程挖掘算法；④声明式过程规则挖掘算法，主要是针对日志中频繁出现的模式规则进行挖掘，其挖掘目的并不是完整的过程模型，如文献[23]中的Declare Miner和以Declare规则挖掘为基础的OCBC(object-centric behavioral model)挖掘方法[24]。

以上方法仅限于扁平过程模型的挖掘，接下来讨论面向子过程模型的挖掘方法。Weber教授在文献[25]中分析了子过程的概念，并以云资源管理过程为例，提出一种可以发现并挖掘子过程模型的方法，然而该方法的子过程识别方法依赖于特定应用领域，因此应用场景有限，且挖掘的过程模型采用分层有向图模型来描述，缺少严格的执行语义。Conforti教授在文献[26-27]中提出BPMN Miner来支持子过程的挖掘，然而该方法依赖于数据库表中主键与外键的信息来识别子过程，这些信息在传统事件日志中并不常见，因此，该方法也不具备很好的通用性。清华大学王建民教授团队[28]针对已有方法在挖掘子过程中存在的问题，提出了两种新的挖掘方法，这两种方法的主要区别在于实例执行图(instance graph)的构造上，第一种方法依赖于先验的活动执行者和后继信息，虽然相较于第二种方法效果更好，但是需要依赖于额外的活动属性，影响了方法的通用性；另一种方法不需要额外的先验信息，仅通过分析事件的开始和结束时间来构造实例执行图。然而，在一些特殊情况下，如一个轨迹中同时存在多个结束时间相同的事件时，第二种方法得到的实例执行图质量无法保证。此外，以上方法[25-28]都不能很好地处理带噪声的事件日志，且挖掘得到的模型(如BPMN模型和有向图模型)缺少严格的形式化执行语义，无法对模型的正确性进行验证。

为了评估挖掘模型的质量，需要对事件日志和模型之间的合规性进行度量。合规性检查的基础是实现事件日志中轨迹与模型的对齐(alignment)。寻找模型与轨迹最优对齐的过程，本质上是一个优化问题。当前普遍使用的对齐方法是Van der Aalst教授[13]提出的通过构造业务过程的Petri网模型与轨迹对应Petri网模型的product net，然后构造product net的可达图，这样最优对齐的计算问题就转化为在可达图里搜索从初始状态到终止状态的最优路径问题，进而采用A*搜索算法进行求解。找到最优对齐后，契合度[11]指标用来量化模型和轨迹中未对齐的活动。如果日志中所有轨迹都可以与模型完全对齐，则契合度值为1。其他常用的质量评价指标还包括准确性[12]、一般性[13]和复杂性[6]。Buijs博士[29]详细讨论了这4个度量指标之间的关系以及对模型质量评估的重要性。然而，以上合规性评价指标均定义在扁平过程模型的基础上，对于包含子过程行为的模型并不适用。针对该问题，文献[30]提出了基于BPMN模型的合规性检查算法Acorn，该方法在BPMN模型基础上对子过程、多实例等复杂模式进行了语义分析，设计了对齐算法，并在A*算法基础上计算了最优校准代价，最后给出了契合度指标计算方法。

2 基础知识

假设S是一个集合，用∅表示空集，|S|表示集合S中的元素个数。定义在S上的超集(powerset)记为(S)={S′|S′S}，定义在S上的多集(mutli-set)是一个允许S中元素出现多次的集合。例如，m=[p3,q2]是定义在集合S={p,q}上的多集，其中m(p)=3，m(q)=2。B(S)表示集合S所有多集的集合。

f:XY是一个函数，其中dom(f)是其定义域，cod(f)={f(x)|x∈dom(f)}是其值域。定义在集合S上长度为n的序列(sequence)是一个函数σ:{1,2,…,n}S。如果σ(1)=a1,σ(2)=a2,σ(3)=a3,…，σ(n)=an，记为σ=a1,a2,a3,…,an。|σ|表示序列σ的长度，包括空序列||=0。S*表示定义在集合S上所有任意长度有限序列的集合。

给定两个序列u,v∈S*，其连接运算σ=u·v，定义为σ：{1,2,…,|u|+|v|}S满足：①σ(i)=u(i)，若1≤i≤|u|；②σ(i)=v(i-|u|)，若|u|+1≤i≤|u|+|v|。

给定集合X，Q⊆X是其子集。Q∈X*Q*是一个投影函数，其迭代定义如下：①Q=；②∀σ∈X*,x∈X:(x·σ)Q=σQ，若x∉Q;(x·σ)Q=x·(σQ)，若x∈Q。

定义1标记Petri网[8]。标记Petri网为一个4元组，记为：PN=(P,T,F,l)，满足：①P∩T=∅，P∪T∅，其中P是库所集合，T是变迁集合；②F⊆((P×T)∪(T×P))是流关系；③l:TΓ是变迁标记函数，其中Γ为标记集合，τ∈Γ表示不可见标记。

将Petri网的状态记为标识(marking)，是定义在库所集合上的多集，记为m∈B(P)，描述每个库所中所包含token的数量。如图1所示，[source]是其初始标识。x∈P∪T，记·x={y|y∈P∪T∧(y,x)∈F}是x的前集(pre-set)，x·={y|y∈P∪T∧(x,y)∈F}是x的后集(post-set)。在一个标识(m)下使能的变迁(t)可以引发(firing)并产生新的标识，记为m′=m-·t+t·。如图1所示，变迁a在标识[source]使能，引发变迁a后产生新的标识[p1,p2]。

3 分层业务过程挖掘

本章介绍分层业务过程挖掘方法，首先对方法进行概述。然后，给出带有任务生命周期事件日志的形式化描述。进而，给出嵌套任务关系挖掘方法。

最后，介绍如何构造分层事件日志和挖掘分层模型。

3.1 方法概述

分层业务过程挖掘的起点是带有生命周期信息的事件日志。如图2所示为本文方法的基本工作原理，主要包括如下4个阶段：

(1)任务嵌套关系挖掘 以生命周期事件日志为输入，首先进行任务之间嵌套关系挖掘。其输出结果是一个任务嵌套关系树，描述了事件日志中任务之间可能存在的所有嵌套关系。

(2)分层事件日志构造 以生命周期事件日志和任务嵌套关系树为输入，通过分析任务之间的嵌套关系，构造分层事件日志。

(3)分层业务过程模型挖掘 在得到分层事件日志后，可以挖掘得到分层业务过程模型。由于分层事件日志中已有层级关系(即任务之间的嵌套关系)，只需要遍历每个层级的子日志，然后从每个子日志中挖掘其对应的过程模型。

(4)合规性检查 在挖掘得到分层业务过程模型后，进一步对挖掘模型和输入日志做合规性检查来评估模型的质量。

3.2 生命周期事件日志

广义的事件日志是一个事件的集合。每个事件除了任务属性，还包括其他属性，如时间戳、资源、生命周期信息等。下面形式化定义了事件和属性。

定义2事件和属性。对于任意事件e∈ε，其中：ε表示事件集，N代表事件属性集合，对于n∈N，#n(e)表示属性n的值。

分层业务过程模型挖掘方法的输入是一个带有生命周期信息的事件日志。UC表示案例集，UA表示任务集，UL表示生命周期类型集，UT表示时间集。对于生命周期日志，假设每个事件e∈ε都包含如下属性：

(1)#case(e)∈UC表示事件e所属的案例，每个事件仅属于一个独立的案例；

(2)#act(e)∈UA表示事件e的任务名；

(3)#trans(e)∈UL表示事件e的生命周期信息；

(4)#time(e)∈UT表示事件e的时间戳。

任务的执行需要时间，通常涉及到多个不同的生命周期状态，如开始、挂起和结束等。对于挖掘嵌套关系，开始(start)和结束(complete)信息已经可以满足，因此本文只考虑这两个状态。

定义3案例和日志。定义在事件集合ε上的案例是一个有限的事件序列σ∈ε*，满足：①每个事件仅出现一次，即1≤i

定义4分类器。分类器被定义为一个函数C:εUA×UL，将事件映射到任务名和生命周期的组合，作为该事件的名字。对于e∈ε，C(e)=(#act(e),#trans(e))就是事件e的名字。

本文用任务名和生命周期的组合作为事件的分类器。如(a,start)写成as，(a,complete)写成ac。基于该分类器，给出生命周期事件日志的简化定义。

定义5生命周期事件日志。生命周期事件日志L∈B((UA×UL)*)是案例的多集，一个案例σ∈(UA×UL)*是一个有限的带有生命周期信息的任务序列。

例如，L1=[as,ac,bs,bc2]表示一个包含两个轨迹的生命周期事件日志，每个轨迹有4个事件。描述了如下执行过程：任务a开始执行，然后结束，任务b开始执行，然后结束。

考虑案例σ=as,bs,bc，它表示任务a开始执行，但是没有结束，这可能是结束任务(ac)丢失或者该案例还没有结束。类似情况还有bs,bc,ac，即as丢失的情况。为了保证生命周期事件日志的质量，假设本文讨论的日志中每个案例都符合一致性(consistency)，即每个开始事件都对应一个结束事件，反之亦然。更多关于日志一致性的讨论，请参见文献[32]。

3.3 任务嵌套关系挖掘

已有的过程挖掘算法，首先根据事件日志构造任务的紧邻(directly-follow)关系，在此基础上挖掘诸如顺序、并发、分支等任务关系。然而，已有方法都是考虑普通事件日志，并没有充分考虑日志中的生命周期信息。包含生命周期信息的日志，可以挖掘出更复杂的任务关系。

图3给出了某一生命周期事件日志中，两个任务a和b可能产生的执行足迹(footprint)。具体而言，图3a和图3b表示两个任务部分重合(partially overlap)，图3c和图3d表示两个任务紧邻(directly-follow)执行，图3e和图3f表示两个任务执行区间相互包含(containment)。

为了进一步区分这些关系，形式化定义如下3种基本关系：紧邻(directly-follow)、重合(overlapping)和包含(containment)。

定义6基本关系。L∈B((UA×UL)*)是一个生命周期事件日志，对于a,b∈UA,σ∈L，定义如下基本次序关系：

(1)在轨迹σ中a紧邻b，记为a>b，如果存在i∈{1,…,|σ|-1}:#act(σ(i))=a∧#trans(σ(i))=complete∧#act(σ(i+1))=b∧#trans(σ(i+1))=start；

(2)在轨迹σ中a与b重合，记为aΔb，如果存在i,j,k,l∈{1,…,|σ|}∧i

(3)在轨迹σ中a包含b，记为aΩb，如果存在i,j,k,l∈{1,…,|σ|}∧i

定义>、Δ、Ω等基本次序关系后，定义任务嵌套关系(nesting)。与因果关系(causality)、选择关系(choice)和并发关系(concurrency)相比，嵌套关系也是一种派生关系。他们之间最主要的区别在于，嵌套关系是针对分层过程模型定义的，其他关系则是针对扁平过程模型。基于嵌套关系，可以挖掘带有层级(子过程)的分层过程模型。

定义7嵌套关系。L∈B((UA×UL)*)是一个生命周期事件日志，对于a,b∈UA，a与b满足嵌套关系，记为aΘb，如果(aΩb)∧¬(bΩa)∧¬(a>b)∧¬(b>a)∧¬(aΔb)∧¬(bΔa)。

根据定义7，两个任务a与b满足嵌套关系，当且仅当日志中仅包含…as,bs,bcac…；反之，a与b则不满足嵌套关系。

在介绍具体挖掘方法之前，讨论针对噪声数据的处理。因为在真实的业务系统运行过程中，很难保证收集的日志是完全干净没有噪声的。为了说明这一点，给出如下例子:

L2=[as,bs,bcac100,as,bs,ac,bc1]表示一个包含101个轨迹的生命周期事件日志。如果不考虑噪声和低频轨迹，根据定义6可以得到任务a和b之间存在如下基本关系：aΔb和aΩb。进一步，可以根据定义7，得到a与b不满足嵌套关系。然而，如果把as,bs,ac,bc看作是低频行为按噪声过滤，则得到aΩb。进一步得到a与b满足嵌套关系，即aΘb。

为提高挖掘方法的灵活性及结果的切实性，引入噪声处理机制。具体而言，定义基本任务关系的频次和频率，并引入噪声阈值来过滤低频关系。

定义8基本关系频次。L∈B((UA×UL)*)是一个生命周期事件日志，a,b∈UA，定义：

(1)|a>b|=σ∈L|{i∈{1,…,|σ|-1}|#act(σ(i))=a∧#trans(σ(i))=complete∧#act(σ(i+1))=b∧#trans(σ(i+1))=start}|是a紧邻b的频次；

(2)|aΔb|=σ∈L|{{i,j,k,l}⊆{1,…,|σ|}|#act(σ(i))=a∧#trans(σ(i))=start∧#act(σ(j))=b∧#trans(σ(j))=start∧#act(σ(k))=a∧#act(σ(k))=complete∧#act(σ(l))=b∧#act(σ(k))=complete∧i

(3)|aΩb|=σ∈L|{{i,j,k,l∈{1,…,|σ|}|#act(σ(i))=a∧#trans(σ(i))=start∧#act(σ(j))=b∧#trans(σ(j))=start∧#act(σ(k))=b∧#act(σ(k))=complete∧#act(σ(l))=a∧#act(σ(k))=complete∧i

基于基本关系频次，定义基本关系的频率。

定义9基本关系频率。L∈B((UA×UL)*)是一个生命周期事件日志，a,b∈UA，定义：

(1)F(a>b)=|a>b|/(|a>b|+|b>a|+|aΔb|+|bΔa|+|aΩb|+|bΩa|+1)是a与b紧邻关系的频率；

(2)F(aΔb)=|aΔb|/(|a>b|+|b>a|+|aΔb|+|bΔa|+|aΩb|+|bΩa|+1)是a与b重合关系的频率；

(3)F(aΩb)=|aΩb|/(|a>b|+|b>a|+|aΔb|+|bΔa|+|aΩb|+|bΩa|+1)是a与b包含关系的频率。

定义10嵌套任务集。L是一个生命周期事件日志，A是其任务集合，NA(L)={a∈A|∃b∈A:aΘb}。

考虑L3=[as,bs,ds,dc,bc,ac,cs,cc99,cs,as,bs,cc,ds,dc,bc,ac96,as,cs,bs,ds,dc,bc,ac,cc86,as,bs,ds,cs,dc,bc,ac,cc78,as,bs,ds,dc,cs,bc,ac,cc79,as,bs,ds,dc,bc,cs,ac,cc82,as,cs,bs,ds,cc,dc,bc,ac,98,as,bs,cc,ds,dc,bc,cc,ac85,as,bs,cs,ds,cc,dc,bc,ac,cc100]。其嵌套任务集合是{a,b}。接下来定义一个树结构来描述从生命周期事件日志中挖掘得到的全部任务嵌套关系。

定义10任务嵌套关系树。L是一个生命周期事件日志，A是其任务集合。定义(A,rootAct,η)为L对应的任务嵌套关系树，满足：

(1)rootAct⊆A是根节点任务集，满足：

(2)η:A|(A) ootAct是一个偏函数，将任务映射到其嵌套任务集合，满足：

日志L3对应的任务嵌套关系树如图4所示，其中：①a和c是根节点；②a和b满足嵌套关系；③b和d满足嵌套关系。只考虑任务之间的直接嵌套关系，而不考虑任务之间的传递或者间接嵌套关系。例如，a和d同样满足嵌套关系，但是由于已经有了a和b，b和d的嵌套关系，a和d的嵌套关系将被删除。

3.4 分层事件日志构造

根据生命周期事件日志和任务嵌套关系树，本节构造分层事件日志。其形式化描述如下：

定义11分层事件日志。L是一个生命周期事件日志，A是其任务集合，(A,rootAct,η)为L对应的任务嵌套关系树。(L)=(rootLog,HL(rootlog))是L对应的分层事件日志，其中：

(1)rootLog=∪σ∈Lσ↑rootAct是L的根节点日志。

(2)HL(rootLog)是rootLog的子日志，满足：

1)若NA(rootLog)=∅,则HL(rootLog)=∅;

2)否则HL(rootLog)={(na,NLogna,HL(NLogna))|na∈NA(rootLog)}，其中NLogna=∪σ∈Lσ↑η(na)是L中嵌套任务na对应的子日志。

根据定义11，以生命周期事件日志和任务嵌套关系树为输入，可以迭代构造分层事件日志。以L2为例，其根日志是rootLog=[as,ac101]，其嵌套任务集合NA(rootLog)={a}。嵌套任务a对应的子日志是NLoga=[bs,bc100]。

3.5 分层过程模型挖掘

得到分层事件日志后，可以挖掘得到分层业务过程模型。为了描述分层业务过程模型，定义分层Petri网。

定义12带嵌套变迁的Petri网。带嵌套变迁的Petri网是一个2元组，记为：PNN=(PN,)，其中：①PN=(P,T,F,l)是一个标记Petri网；②:T{A,N}是嵌套变迁函数，满足∀t∈T,(t)=A表示t是普通变迁，(t)=N表示t是嵌套变迁。

给定一个带嵌套变迁的Petri网PNN，Ta={t∈T|(t)=A}表示普通变迁集合，Tn={t∈T|(t)=N}表示嵌套变迁集合。特别地，用Ta0和Tn0表示PNN0普通变迁集合和嵌套变迁集合。图5给出了一个带嵌套变迁的Petri网，其中嵌套变迁(如b)用双线矩形表示，普通变迁(如a)用单线矩形表示。

定义13分层Petri网。分层Petri网是一个2元组=(PNN0,HPN(PNN0))，其中：

(1)PNN0是根节点，即顶层带嵌套变迁的Petri网。

(2)HPN(PNN0)=∅是PNN0对应的子模型，满足：

1)若Tn0=∅,则HPN(PNN0)=∅;

2)否则HPN(PNN0)={(ti,PNni,HPN(PNni))|tiTn0}，其中PNni是嵌套任务ti对应的带嵌套变迁的Petri网。

由于分层事件日志中已有层级关系，只需遍历每个层级的子日志，然后为每个子日志挖掘其对应的扁平过程模型(包括嵌套变迁)。理论上讲，可以用任何已有的过程挖掘技术。图6给出了一个分层Petri网的例子，顶层Petri网包含3个普通变迁和一个嵌套变迁a，嵌套变迁a对应子过程模型PNN1，子过程模型中包含一个嵌套变迁b，嵌套变迁b对应子过程模型PNN2。

值得注意的是，本文选择Inductive Miner[19]来进行子日志过程模型挖掘，其优势在于可以确保挖掘得到模型的正确性(soundness)，进而保证挖掘得到分层Petri网的正确性。

4 工具实现与实验评估

本章对分层业务过程挖掘方法的有效性和可用性进行实验评估。具体而言，首先介绍挖掘方法的工具实现。然后，基于仿真日志和真实日志将本文方法与已有过程挖掘方法进行数值比较。

4.1 支持分层业务过程挖掘的ProM工具实现

在开源业务过程挖掘平台ProM(http://promtools.org)下，对本文提出的分层业务过程挖掘方法进行了实现，开发了Hierarchical Process Miner(HPM)工具(该工具源代码参见：https://svn.win.tue.nl/repos/prom/Packages/CongLiu/)。具体而言，HPM以带有生命周期信息的XES事件日志和用户输入的噪声阈值为输入，挖掘得到一个分层Petri网模型。

4.2 噪声阈值评估

首先使用一组仿真数据集来评估噪声阈值的有效性以及对挖掘结果的影响。

LE1=[m1s,m1c,m2s,m4s,m4c,m2c100,m1s,m1c,m3s,m3c50]。

以LE1为输入日志，设置噪声阈值为1，即所有轨迹都考虑，日志中无噪声。图7给出了HPM挖掘得到的分层Petri网模型。顶层Petri网包含两个普通变迁(m1和m3)和一个嵌套变迁(m2用带阴影的矩形表示)，嵌套变迁m2对应的子过程模型在虚线矩形框内。

进一步在LE1中加入噪声，构造LE2如下：

LE2=[m1s,m1c,m2s,m4s,m4c,m2c100,m1s,m1c,m2s,m4s,m2c,m4c,m1s,m1c,m3s,m3c50]。

以LE2为输入日志，设置噪声阈值为1，图8给出了HPM挖掘得到的Petri网模型。变迁m2和m4是并发关系，而不是嵌套关系。这是因为设置的噪声阈值为1，即所有轨迹都被视为频繁行为。具体而言，有

若设置嵌套阈值为0.9，即过滤掉10%的低频行为，得到m2和m4是嵌套关系。

基于此，可以发现通过引入嵌套阈值并对其进行合理的设置，本文分层过程模型挖掘方法可以从带有噪声的事件日志中准确识别任务之间的嵌套关系。

4.3 对比实验设计与评估

为评价本文提出的分层业务过程挖掘方法的有效性，基于仿真事件日志和真实事件日志将本文方法与已有过程挖掘方法进行定量比较。接下来依次介绍实验数据、基准挖掘方法、评价指标和实验结果与分析。

4.3.1 测评数据与基准挖掘方法

分层业务过程挖掘方法的输入数据记录了生命周期和子过程信息的事件日志，选取2个仿真事件日志和4个真实事件日志作为本文的评测数据。日志的基本统计信息如表1所示。

表1 事件日志的基本统计信息

为保证评测日志的质量，本文对以上数据进行了预处理，确保日志中每个案例都符合一致性的定义，即每个开始事件都对应一个结束事件。

本节将选择如下已有过程挖掘算法来与本文提出的分层过程挖掘发方法进行比较，选取标准如下：①所选取的挖掘方法需要能够处理带生命周期的事件日志；②需要确保挖掘得到模型的正确性(soundness)，否则无法定量比较模型挖掘的质量；③所选择挖掘方法需要有可获取的原型系统实现。基于以上条件，比较如下挖掘方法：

(1)IM(inductive miner)[17]。需要设置其挖掘classifier为任务名和生命周期的组合，即每个任务在挖掘模型中表示为开始任务和结束任务。

(2)IMlc(inductive miner lifecycle)[7]。挖掘结果是一个扁平Petri网模型。

(3)SW(statechart workbench)[32]。挖掘结果是一个分层流程树/分层Petri网。

(4)HPM(hierarchical process miner)。挖掘结果是分层Petri网，在实验中设置噪声阈值为0.9。

值得注意的是，虽然Tsinghua-Alpha Miner[15]也可以处理带生命周期的事件日志，但是由于其不能够保证挖掘模型的正确性，本文对该方法不作比较。

4.3.2 评价指标

为衡量挖掘模型的质量，需要以模型与日志为输入来进行合规性度量。本小节选取最常用的合规性度量指标：契合度(fitness)和准确性(precision)。具体而言，契合度量化了日志中案例可以被过程模型从头到尾重演(replay)的比例。如果日志中所有案例都可以被模型完全重演，则契合度值为1。准确性量化了模型能够产生的案例不在日志中出现的比例。如果模型所产生的所有案例都包含在日志中，则契合度值为1。

契合度与准确性之间往往存在一个平衡，有时候通过某些设置可以使得契合度小幅下降的同时导致准确性大幅提升。为了统一这两个指标，引入F-值，

由于契合度与准确性都是定义在扁平过程模型的基础上，而且生命周期事件日志中包含了任务的开始和结束时间，需要将挖掘得到的分层Petri网模型等价转换成扁平Petri网才能进行量化。如图9所示为针对两类变迁的转换规则，具体而言：

(1)针对嵌套变迁和子过程 包括：①一个嵌套变迁t被转换成两个普通变迁ts和tc；②增加库所pe；③增加流关系(ts,pe)、(pe,tc)、(ts,ps)和(pc,tc)来连接嵌套变迁与子过程。

(2)针对普通变迁 包括：①一个嵌套变迁t被转换成两个普通变迁ts和tc；②增加库所pe；③增加流关系(ts,pe)和(pe,tc)。

如图10所示为图6中分层Petri网对应的扁平Petri网模型。每个嵌套变迁被转换成两个普通变迁。如，嵌套变迁a转换成as和ac，as表示变迁a的开始，ac表示变迁a结束。

4.3.3 实验结果与分析

介绍完实验数据、基准挖掘方法、评价指标及模型转换规则后，本小节给出具体的实验结果，并根据实验结果进行深入分析。

根据表2中的实验结果，对4种方法进行对比分析，得到如下结论：

表2 实验结果

续表2

(1)对于IM，与其他3种方法不同的是本文设置其分类器为任务名与生命周期的组合，其挖掘模型中每个任务对应开始和结束两个变迁，导致模型更复杂不易于理解。虽然IM可以保证契合度为1，但是通常情况会过度泛化模型行为，导致对于较复杂的事件日志，如NASA Log和BPI Challenge 2017数据集，其准确性远低于HPM。

(2)对于以上6组数据，HPM方法得到的F-值比IMlc和SW方法的都要高(至少是等于)。通常情况下，F-值越高表明模型的质量越好。之所以HPM方法得到的F-值比这两种方法都高，是因为HPM方法通过嵌套关系挖掘和子过程识别，可以有效地识别任务的嵌套关系，从而在保证模型契合度的前提下，大幅提高挖掘模型的准确性。

(3)对于IMlc方法，它并不能准确地识别任务之间的嵌套关系，只是简单地将其归类为并发关系。因此，IMlc方法挖掘得到模型的准确性要比HPM方法低。

(4)SW方法可以发现日志中嵌套关系和子过程，如它从Hotel booking log中挖掘的分层模型准确性为1。然而，当子过程与并发任务混合到一起时，SW方法就不能够精确地区分并发关系和嵌套关系。如，它从BPI Challenge 2017数据集中挖掘模型的准确性会非常低。

接下来测试比较以上4种方法的挖掘性能，具体而言，针对表1中的6个事件日志，分别用每种方法重复执行5次，记录其执行时间，详细的性能比较如图11所示。

根据图11的实验结果，下面对4种方法进行对比分析，可以得到如下结论：

(1)与其他3种方法相比，IM通常具有最好的挖掘效率，即时间性能最优。值得注意的是，对于小规模的事件日志，如Synthetic log 1-2，4种挖掘方法所用挖掘时间差别不大。

(2)随着日志规模变大，即案例数量和任务数量增长，本文所提出的HPM方法的挖掘效率与其他3种方法的差距越来越大。这是因为HPM方法需要遍历日志中的所有案例来识别两两任务之间是否满足嵌套关系，该嵌套关系挖掘所需时间与任务数量和案例数量成正比。

5 结束语

本文提出一种从包含任务生命周期信息的事件日志中挖掘分层业务过程模型的方法，并在挖掘得到分层模型的基础上，给出了模型质量度量方法。与已有过程挖掘方法不同，本文提出的方法能够有效地挖掘任务之间的嵌套关系，进而构造分层业务过程模型。基于仿真日志数据和真实日志数据，比较了本文方法与已有过程挖掘方法挖掘得到模型的质量，进一步验证了本文方法针对挖掘分层业务过程模型的优势。

本文方法只是针对分层过程挖掘方法的初步尝试，未来在该方法基础上可以做如下扩展和改进：

(1)本文所提出的分层过程模型挖掘方法，仅适用于单一过程实例的模型和日志。在本文方法的基础上，可以进一步给出针对多实例子过程的形式化描述方法和挖掘方法。

(2)目前方法的噪声阈值设置还缺乏系统的方案，未来将通过定量评估噪声阈值对挖掘模型质量的影响，针对不同日志给出优化的噪声阈值设置。

(3)针对大规模事件日志，本文方法的挖掘性能还有待提高。未来将通过分布式数据处理平台(如文献[33])来进一步优化挖掘算法的性能。

(4)本文只是从理论上给出了通用的分层业务过程模型挖掘方法，未来将把本文方法应用在实际的业务场景中，如突发事故应急处置流程[34]，服务流程[35]，医疗业务流程[36]，软件过程[37]等。