基于后继任务的工作流挖掘方法

摘要

基于后继任务的工作流挖掘方法，基于事件日志的工作流挖掘，它以事件日志为输入，以Petri网描述的工作流模型为输出结果；该方法引入事件类型使得工作流日志中含有当前任务的后继任务，后继任务是指当前任务执行完成后将执行权限转交给的任务的集合；包含以下步骤：(1)设置要挖掘的工作流过程模型初值；(2)分析事件日志W，计算出任务集TW、起始任务TI和结束任务TO；(3)调用relationPreprocess过程获得因果关系矩阵M2和潜在并发关系与并发关系矩阵M3；(4)根据矩阵M2和M3，计算出初始任务关系集XW；本发明组成完整的基于后继任务的工作流挖掘方法。

说明书

技术领域

本发明属于工作流技术领域，尤其是工作流技术领域中的工作流挖掘技术， 是用于从工作流日志中挖掘工作流过程模型的技术。

背景技术

工作流过程被定义为根据一系列的程序或规则将文件、信息或活动从一个参 与者传输到另一个参与者的整个或部分业务过程。工作流系统是一个用于集中管 理工作流程的自动化系统。现在，大多数信息系统使用已定义的工作流模型描述 任务关系并维护整个业务过程。但随着业务过程越来越多、单个业务过程越来越 复杂，工作流模型不可避免会有低效，甚至是出错的问题。为此对业务过程进行 监控并加以改进是很有必要的，而这些需求都需要获得工作流模型的真实行为。

工作流挖掘技术旨在解决上述问题。工作流挖掘技术通过对工作流执行过程 中累积的大量数据进行有效的分析，获得真实场景人员和工作流过程的运行情 况，为后期的工作流模型的监控和分析提供支持。工作流挖掘技术通过分析事件 日志，反向推导出与之对应的工作流过程模型。本发明只考虑事件日志信息完整 且不存在噪声的情况，不考虑事件日志信息可能的不完备和信息错误的情况。

工作流挖掘是从事件日志(执行序列)中反推出过程模型的技术，然后用一 定的方式将任务间的关系表达出来(当前，一般使用Petri网描述整个工作流模 型)。事件日志是事件轨迹的集合，每条轨迹由多个事件组成。工作流挖掘技术 分析事件日志并从中计算出任务间关系，主要是因果关系、选择关系和并发关系。

目前，工作流网是工作流过程建模领域比较流行的一种建模方法，工作流网 是一类特殊的Petri网。Petri网能很清晰地描述过程模型中的顺序、选择、循环、 以及并发与同步结构，在描述过程模型方面，具有一些优点：形式化的语义，直 观的图形表示，易于理解，坚实的数学理论基础和成熟的分析技术等，因此Petri 网是比较成熟和流行的过程建模工具。Petri网从结构上来讲，Petri网是一个三 元组PN＝(P，T，F)，其中P是库所(place)集合，T是变迁(transition)集合，且P∩T＝φ， F＝(P×T)∪(T×P)是库所与变迁之间的弧线集合，·x＝{y∈P∪T|(y，x)∈F}表示一 个库所或者变迁的前集，x·＝{y∈P∪T|(x，y)∈F}表示一个库所或者变迁的后集。

工作流网与普通Petri网相比较，有两个特殊条件：一是在工作流网中有两 个特殊的库所，分别称为起始库所i与结束库所o，起始库所没有输入，结束库 所没有输出；第二个条件是在库所o与库所i之间添加一个辅助变迁t^*，构成的 扩展模型PN＝(P，T∪{t^*}，F∪{(o，t^*)，(t^*，i)})是强连通的。这里，变迁表示工作 流的活动，库所与token的分布表示工作流的执行状态，Petri网的点火条件表示 活动的执行条件，总的来讲，工作流网能够通过Petri网结构清楚表达工作流的 业务过程的逻辑。在工作流网中，变迁(transition)代表工作流中的任务，任务之 间的依赖关系通过和库所的连接来表示，托肯(token)在库所集中的分布情况表示 过程模型的状态。

依据Petri网理论，工作流网中的一个任务(变迁表示)的可执行条件为， 该任务所对应的变迁的前置库所中都各有一个托肯(token)，称为可点火条件，有 时又称为使能条件(enabled)。一个任务(变迁表示)的点火规则是：从发生点火 的变迁的所有输入库所中各移除一个托肯，向发生点火的变迁的所有输出库所各 添加一个托肯。对应到工作流系统中，一个任务的执行步骤是：判断前置条件， 执行任务，设置后置条件。前置条件是指一个任务能够执行的前提条件，即任务 的可执行条件，一个任务只有在获得了所有的可执行条件的情况下，该任务才能 执行。后置条件是指一个任务完成后，在该任务结束之前，该任务所做的一些善 后处理，它可能告知整个过程的结束，也可能为其后继任务设置前置条件。因此， 工作流引擎在分析过程定义和决定任务的执行时，可以记录当前即将结束的任务 的所有后继任务。

工作流挖掘是从事件日志(执行序列)中反推出过程模型的技术，如果反推 出来的过程模型工作流网描述，那么工作流挖掘的本质就是事件日志(执行序列) 方向构造工作流网的技术，在工作流网中三元组结构PN＝(P，T，F)中，其中变迁 集合直接由工作流日志(执行序列)中的任务集合组成，因此挖掘工作就变为挖 掘其中的库所集以及库所集与变迁集之间的连接弧线，这个反推技术需要借助任 务关系(relation)的分析，现有的α方法，α⁺方法，α⁺⁺方法和β方法都是基于这种 思路设计的。

目前，基于事件日志的工作流挖掘方法主要有α方法，α⁺方法，α⁺⁺方法和β 方法。其中α方法，α⁺方法和α⁺⁺方法日志中的事件只是简单的任务名称，β方法 日志中的事件含有任务的开始和结束信息。α方法只能处理SWF网结构约束的 过程模型，不能处理短循环结构、隐式因果依赖结构和隐式库所结构；α⁺方法扩 展了α方法的挖掘能力，它能够挖掘短循环结构；α⁺⁺方法进一步扩展α方法的挖 掘能力，它能够挖掘出大部分的隐式因果依赖结构；β方法引入新的事件类型， 它能够挖掘符合SWF网结构约束的过程模型、短循环结构，但不能处理隐式因 果依赖结构和隐式库所结构。

虽然大部分已知的工作流挖掘方法都会考虑一些事件类型，例如时间戳、操 作人员等，但现有工作流挖掘方法都是通过分析事件日志中的任务紧邻关系挖掘 任务间的因果关系和并发关系，进而挖掘任务间的选择关系。这些方法虽然可以 挖掘出一部分工作流模型，但对于像隐式因果依赖和隐式库所却很难挖掘，甚至 不能挖掘。在上述的基于事件日志的工作流挖掘方法中，α⁺⁺方法的挖掘能力是 最强的，该方法虽然能挖掘出SWF结构、短循环结构、大部分隐式因果依赖结 构，但不能处理隐式库所结构，并且α⁺⁺方法在挖掘隐式因果依赖结构时需要采 用复杂的逻辑任务关系分析，这大大提高了该方法的复杂度。

发明内容

本发明要解决的技术问题是：提供一种基于后继任务(从当前任务获得执行 权限的任务的集合)的工作流挖掘方法，该方法不仅能扩展工作流挖掘方法的可 挖掘范围，而且能简化挖掘工作流模型中的因果依赖关系和潜在并发关系。

本发明的技术方案为：基于后继任务的工作流挖掘方法，首先通过分析事件 日志中任务，包括对工作流的事件日志中后继任务进行分析；它以事件日志为输 入，以Petri网描述的工作流模型为输出结果；后继任务是当前任务执行完成后， 它将执行权限转交给的任务的集合。该方法引入事件类型使得工作流日志中含有 当前任务的后继任务，该挖掘方法整体流程如图1所示。包含步骤(如图2所示)：

(1)初始化该流程的返回值N(Petri网描述的工作流模型)，依据Petri网的 结构定义，N由库所集P_W、任务集T_W和弧线集F_W构成。

(2)分析事件日志W，计算出任务集T_W、起始任务T_I和结束任务T_O；

(3)调用relationPreprocess过程获得因果关系矩阵M₂和潜在并发关系与并发 关系矩阵M₃；

(4)根矩阵M₂和M₃，计算出初始任务关系集X_W；

(5)对初始任务关系集X_W进行修正，计算出修正任务关系集X′_W；

(6)去除修正任务关系集X′_W中的冗余元素，计算出最终任务关系集Y_W；

(7)根据Y_W，计算出库所集P_W；

(8)根据Y_W和P_W，计算出弧线集F_W；

(9)返回Petri网描述的工作流过程模型N。

在以上的流程中，使用到relationPreprocess过程计算出矩阵M₂和M₃， relationPreprecess的步骤如下：

(1)将顺序关系应用于事件日志W，计算出顺序关系矩阵M₁；

(2)使用因果依赖关系(含显式因果依赖关系与隐式因果依赖关系)，再依据 顺序关系矩阵M₁，划分显式因果依赖关系和隐式因果依赖关系，从而计 算出因果依赖关系矩阵M₂；

(3)使用潜在并发关系、并发关系和顺序关系矩阵M₁，计算出潜在并发关系 与并发关系矩阵M₃。

在该方法的relationPreprocess中，需要对日志中的任务关系进行预处理，计 算出日志中所有任务间的任务关系。日志中的任务间关系预处理方法(如图3 所示)包括：顺序关系、因果依赖关系、潜在并发关系、显式因果依赖关系、隐 式因果依赖关系、并发关系、不相关关系和非并发关系。通过分析事件的先后关 系可获得顺序关系，而通过分析事件日志中的事件，即当前任务和后继任务，直 接获得任务间的因果依赖关系和潜在并发关系。顺序关系、因果依赖关系和潜在 并发关系是所有任务关系的基础，其它任务关系都从这三种关系推导出来。具体 的预处理过程为：从任务的顺序关系获得任务顺序关系矩阵M₁，该矩阵记录了 所有任务间的顺序关系；然后，通过分析事件集获得任务间的因果依赖关系并生 成因果依赖关系矩阵，并通过隐式因果依赖关系区分因果依赖关系矩阵中的显式 依赖关系和隐式因果依赖关系，计算出修正后的因果依赖关系矩阵M₂(该矩阵 中1表示显式因果依赖，2表示隐式因果依赖)；再通过分析事件集获得任务间 的潜在并发关系矩阵，通过并发关系往该矩阵中，最终得到潜在并发关系与并发 关系矩阵M₃(该矩阵中1并发关系，2表示潜在并发关系)。在预处理中，因果 依赖关系和潜在并发关系都是从事件日志中以直接的方式获得的。

通过分析因果关系矩阵M₂和潜在并发关系与并发关系矩阵M₃，获得初始任 务关系集X_W，初始任务关系集X_W的每个元素由前驱任务集和后继任务集构成， 前驱任务集中的每个任务都与后继任务集中的每个任务存在因果依赖关系，而前 驱任务集和后继任务集中的元素之间存在非并发关系。

对初始任务关系集X_W进行修正，计算出修正任务关系集该发明属于工作流 领域中的工作流挖掘技术，工作流挖掘是从事件日志(执行序列)中反推出过程 模型的技术，在反推流程中要对任务关系进行分析和处理，然后依据任务关系反 推过程模型的结构。

针对初始任务关系集X_W中包含的显式因果依赖关系和隐式因果依赖关系的 元素需要进一步分析。如果删除该元素与隐式因果依赖关系有关的所有任务之 后，该元素的前驱任务集不为空而后继任务集为空，就说明该元素过度合并，需 要将显式因果依赖关系和隐式因果依赖关系分割开来，具体的分割方式为：将前 驱任务集的隐式因果依赖关系的任务与显式因果依赖关系的任务划分为两个任 务集，然后分别与该元素的后继任务集重组以形成两个新的任务关系元素。

本发明的有益效果是：该方法不仅提升了工作流挖掘方法的挖掘能力(能够 挖掘出隐式库所结构)，而且简化挖掘因果依赖关系和潜在并发关系的过程。因 为隐式库所不影响工作流模型的行为，所以当前所有的过程挖掘方法都不关注这 一特殊结构。但隐式库所显示出任务间的冗余关系，这在某种程度上会有性能和 安全隐患。该方法第一次关注了隐式库所结构，它可以挖掘出部分的隐式库所结 构，这可以为工作流模型的分析、验证和监控提供更好的支持。

本发明与现有方法相比：通过在工作流日志中引入后继任务，设计基于后继 任务的关系预处理流程和方法，并组成完整的基于后继任务的工作流挖掘方法， 该方法不仅能扩展工作流挖掘方法的可挖掘能力，而且能简化挖掘工作流模型中 的因果依赖关系(含显式因果依赖关系与隐式因果依赖关系)和潜在并发关系。

附图说明

图1为基于后继任务的工作流挖掘方法的流程图。

图2为基于后继任务的工作流挖掘方法的主要流程。

图3为任务间关系预处理方法。

图4为本发明实例中获得的任务间顺序关系矩阵。

图5为本发明实例中获得的任务间因果关系矩阵(含显式因果依赖关系与隐式因 果依赖关系)。

图6为本发明实例中获得的任务间潜在并发关系与并发关系矩阵。

图7为本发明实例挖掘出的工作流过程模型。

图8为本发明实例能挖掘的工作流模型，该模型包含隐式库所。

具体实施方式

本发明主要是使用新的事件类型并通过任务间关系预处理获得日志中的所 有任务间关系，以及在α方法的基础上添加了对任务关系集的修正步骤。该挖掘 方法整体流程如图1所示。其具体实施如下：

1、该方法的主要流程如图2上半部分所示。

(1)第1步，初始化该流程的返回值N(Petri网描述的工作流模型)，依据 Petri网的结构定义，N由库所集P_W、任务集T_W和弧线集F_W构成。

(2)第2步，分析事件日志计算出任务集T_W(日志中所包含的所有名称不同 的任务)，每个执行轨迹σ的起始任务集T_I和结束任务集T_O。

(3)第3步，调用relationPreprocess过程对任务关系进行预处理，该过程返 回因果依赖关系矩阵和潜在并发关系与并发关系矩阵。

(4)第4步，根据relationPreprocess生成的因果依赖关系矩阵M₂和潜在并发 关系与并发关系矩阵M₃生成初始任务关系集X_W，其元素可表示为<前驱 任务集，后继任务集>。

(5)第5步，检测初始关系任务集中同时包含显式因果依赖关系与隐式因果 依赖关系的元素并在必要时做出相应的修正，以生成修正任务关系集 X′_W。将前驱任务集PS和后继任务集SS分别分割成PS′、PS″和SS′、SS″， 若PS′和PS″非空而SS″为空，则说明该元素存在过度合并的情况，需要 将该元素分割成<PS′，SS>和<PS″，SS>。

(6)第6步，通过删除X′_W中冗余的元素，计算出最终的任务关系集Y_W。

(7)第7步，计算出工作流模型的库所集P_W，其元素为Y_W中的元素、起始 库所和结束库所的集合。

(8)第8步，根据P_W和Y_W获得工作流模型的变迁弧集F_W。

(9)最后一步，返回工作流模型N。

2、该方法的relationPreprocess过程如图2下半部分，该过程应用图3所描 述的任务间关系预处理方法。

(1)第1步，应用顺序关系，分析事件日志并获得顺序关系矩阵M₁。

(2)第2步，首先，应用因果依赖关系分析事件日志中的所有事件，获得因 果依赖关系矩阵M₂；然后，应用隐式因果依赖关系和M₁往矩阵M₂中加 入隐式因果依赖关系，使得M₂矩阵可以区分显式因果依赖和隐式因果依 赖。

(3)第3步，首先，应用潜在并发关系分析事件日志中的所有事件，计算出 潜在并发关系与并发关系矩阵M₃；然后，应用并发关系和M₁往矩阵M₃中加入并发关系，使得M₃矩阵含有真实存在并发关系的任务信息。

下面通过具体的实例来说明本发明的实施。

本发明的实例将从事件日志中挖掘出图7的工作流模型，该模型由11个库 所、11个变迁构成。表1为实验程序的事件日志，该事件日志将作为本发明实 例的输入数据。

表1实验程序的事件日志

 σ₁  t₁[t₂]，t₂[t₄t₉]，t₄[t₈]，t₈[t₉]，t₉[t₁₁]，t₁₁[]  σ₂  t₁[t₂]，t₂[t₄t₉]，t₄[t₅t₈]，t₅[t₅]，t₅[t₈]，t₈[t₉]，t₉[t₁₁]，t₁₁[]  σ₃  t₁[t₂]，t₂[t₄t₉]，t₄[t₆t₈]，t₆[t₇]，t₇[t₆]，t₆[t₇]，t₇[t₈]，t₈[t₉]，t₉[t₁₁]，t₁₁[]  σ₄  t₁[t₂]，t₂[t₄t₉]，t₄[t₅t₆]，t₅[t₅]，t₆[t₇]，t₅[t₅]，t₇[t₈]，t₅[t₈]，t₈[t₉]，t₉[t₁₁]，t₁₁[]  σ₅  t₁[t₃]，t₃[t₄t₁₀]，t₄[t₈]，t₈[t₁₀]，t₁₀[t₁₁]，t₁₁[]  σ₆  t₁[t₃]，t₃[t₄t₁₀]，t₄[t₅t₈]，t₅[t₅]，t₅[t₈]，t₈[t₁₀]，t₁₀[t₁₁]，t₁₁[]  σ₇  t₁[t₃]，t₃[t₄t₁₀]，t₄[t₆t₈]，t₆[t₇]，t₇[t₆]，t₆[t₇]，t₇[t₈]，t₈[t₁₀]，t₁₀[t₁₁]，t₁₁[]  σ₈  t₁[t₃]，t₃[t₄t₁₀]，t₄[t₅t₆]，t₅[t₅]，t₆[t₇]，t₅[t₅]，t₇[t₈]，t₅[t₈]，t₈[t₁₀]，t₁₀[t₁₁]，t₁₁[]

对于该实例，我们将采用如下步骤实施该方法：

1.初始化返回值N(Petri网描述的工作流模型，依据Petri网的结构定义， N由库所集P_W、任务集T_W和弧线集F_W构成)，使得P_W＝T_W＝F_W＝φ。

2.从事件日志中获得事件任务集T_W＝{t₁，t₂，t₃，t₄，t₅，t₆，t₇，t₈，t₉，t₁₀，t₁₁}，获得起始 任务集T_I＝{t₁}和结束任务集T_O＝{t₁₁}。

3.调用relationPreprocess过程，计算出因果依赖关系矩阵M₂和潜在并发关 系与并发关系矩阵M₃，其具体过程如下：

(1)通过任务的顺序关系计算出任务的顺序关系矩阵M₁，该矩阵记录了 任务间的顺序关系，如图4所示。

(2)通过事件日志、顺序关系矩阵M₁并应用因果依赖关系和隐式因果依 赖关系计算出因果关系矩阵M₂，该矩阵记录了任务间的因果依赖关 系，如图5所示(该矩阵中1表示显式因果依赖，2表示隐式因果依 赖)。

(3)通过事件日志、顺序关系矩阵M₁并应用潜在并发关系和并发关系计 算出因果关系矩阵M₃，该矩阵记录了任务间的潜在并发关系，如图 6所示(该矩阵中1并发关系，2表示潜在并发关系)。

4.将矩阵M₂和M₃应用于主流程的步骤4，该方法获得初始任务关系集X_W， 该初始任务关系集为：{({t₁}，{t₂，t₃})，({t₂}，{t₄})，({t₂}，{t₉})，({t₃}，{t₄})， ({t₃}，{t₁₀})，({t₄}，{t₅，t₈})，({t₄}，{t₆，t₈})，({t₅}，{t₅，t₈})，({t₆}，{t₇})，({t₇}，{t₆，t₈})， ({t₈}，{t₉，t₁₀})，({t₉}，{t₁₁})，({t₁₀}，{t₁₁})，({t₂，t₃}，{t₄})，({t₄，t₅}，{t₅})， ({t₄，t₇}，{t₆})，({t₄，t₅}，{t₈})，({t₄，t₇}，{t₈})，({t₂，t₈}，{t₉})，({t₃，t₈}，{t₁₀})， ({t₉，t₁₀}，{t₁₁})，({t₄，t₅}，{t₅，t₈})，({t₄，t₇}，{t₆，t₈})}。

5.根据主流程的步骤5，对初始任务关系集X_W进行修正，该方法获得修正 任务关系集X′_W，该例子中是对元素({t₂，t₈}，{t₉})和({t₃，t₈}，{t₁₀})进行修正。 该修正任务关系集X′_W为：{({t₁}，{t₂，t₃})，({t₂}，t₄})，({t₂}，{t₉})，({t₃}，{t₄})， ({t₃}，{t₁₀})，({t₄}，{t₅，t₈})，({t₄}，{t₆，t₈})，({t₅}，{t₅，t₈})，({t₆}，{t₇})，({t₇}，{t₆，t₈})， ({t₈}，{t₉，t₁₀})，({t₉}，{t₁₁})，({t₁₀}，{t₁₁})，({t₂，t₃}，{t₄})，({t₄，t₅}，{t₅})， ({t₄，t₇}，{t₆})，({t₄，t₅}，{t₈})，({t₄，t₇}，{t₈})，({t₈}，{t₉})，({t₈}，{t₁₀})， ({t₉，t₁₀}，{t₁₁})，({t₄，t₅}，{t₅，t₈})，({t₄，t₇}，{t₆，t₈})}。

6.根据主流程的步骤6，删除修正任务关系集X′_W中冗余的元素而获得最终 任务关系集YW，该最终任务关系集为：{({t₁}，{t₂，t₃})，({t₂}，{t₉})，({t₃}，{t₁₀})， ({t₂，t₃}，{t₄})，({t₄，t₅}，{t₅，t₈})，({t₄，t₇}，{t₆，t₈})，({t₆}，{t₇})，({t₈}，{t₉，t₁₀})， ({t₉，t₁₀}，{t₁₁})}。

7.根据方法的步骤7和最终任务集Y_W，该方法可以获得库所集P_W，该库所 集为：其 中iw和ow分别为起始库所和结束库所。

8.根据主流程的步骤8并应用库所集P_W和任务集Y_W，该方法获得弧线集 F_W，该弧线集为：

9.至此，该方法就完整获得了由Petri网描述的工作流模型N＝(P_W，T_W，F_W)。

以上步骤获得了工作流模型N，通过Petri网图形表示工具可获得如图7所表 示的工作流模型。虽然该模型包含了SWF结构、短循环结构，甚至是隐式因果 依赖结构，但该方法都能正确挖掘，即该方法能正确的挖掘SWF结构、短循环 结构和隐式因果依赖结构。当然，该方法也能挖掘出如图8所示的工作流模型， 该模型含有隐式库所结构P₁。