基于结构化工作流网的隐含任务挖掘方法

《基于结构化工作流网的隐含任务挖掘方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于结构化工作流网的隐含任务挖掘方法０引言　　面对激烈的市场竞争和市场环境的快速变化，现代企业必须能够随时对核心业务过程做出适当的调整以适应新的需要。这不但需要管理者能够掌握外部环境的变化，也需要管理者能够对企业业务过程的实际情况有清晰的了解。传统的过程分析手段，如调查、访谈、建模分析和模拟等，费时费力，而且受用户的主观性影响很大，容易出现偏差，因此越来越难以满足用户的需要。　　过程挖掘是一种自动化的过程分析技术，通过对业务过程日志的挖掘，自动生成业务过程的执行流模型，从而帮助用户更好地理解业务过程的内在执行逻辑［１

2、］。由于其分析的依据――业务过程日志是企业在实际业务运行过程中生成的客观记录，因此该技术客观性强、费用低、速度快，有效地弥补了传统过程分析手段的各种缺陷，并已经在政府公共工程、医院和供应链管理等实际领域中取得了一定的成功应用［２－４］。　　对包含错误、隐含任务［５］等的不完整日志的挖掘是过程挖掘面临的难题之一。因为实际中用于挖掘的日志主要于企业的信息系统的自动生成，因此日志中包含错误的情况并不常见，不完整日志问题基本上都是由于包含隐含任务造成的。现有的大多数过程挖掘算法在处理包含隐含任务的日志时都无法得到正确的结果。

3、少数几种能够处理隐含任务的算法，如基因算法［６］、α＃算法［７］等，但只能挖掘部分类型的隐含任务，未能完全解决隐含任务的挖掘问题。　　针对这一问题，本文尝试提出一种基于α算法［８］和结构化工作流X［９］的过程挖掘算法，该算法能够比较全面地挖掘结构化工作流X模型中的各类隐含任务。通过理论分析和实验验证，该算法的正确性得到了证明。　　１问题说明　　过程挖掘通过对日志信息的分析来构造过程模型。为了保证挖掘算法能够最大限度地适用于各种形式的日志，绝大多数挖掘算法仅要求日志中包含下列3项内容：①事件所属的工作实例；②执行事件的

4、业务单元（任务标识）；③事件发生的顺序（处理时间）。因此，在分析过程挖掘算法时，为了简便起见，通常直接将日志写成诸如ＡＢＣＤＥ，ＡＢＣＤＦ，ＡＣＢＤＥ，ＡＣＢＤＦ的形式，其中每个字母代表一个任务，每个逗号隔开的字母序列代表一条日志实例。对该日志实例用算法进行过程挖掘，就可以得到如图１（ａ）所示的结构化工作流X过程模型。　　在现实中，由于很多信息系统只对进行实际业务操作的业务单元活动进行记录，以及系统采用的过程建模工具本身的特性等各种原因，一些过程任务往往没有被记录在日志中。这种过程任务就是所谓的“隐含任务”。现有的大

5、多数算法无法正确处理包含隐含任务的日志。例如，假设图１（ａ）中过程的任务Ｄ是一个隐含任务，则得到的日志是ＡＢＣＥ，ＡＢＣＦ，ＡＣＢＥ，ＡＣＢＦ。用α算法挖掘将得到如图１（ｂ）所示的模型，它不是一个合法的结构化工作流X模型，而且相比原始模型，其结构复杂，不容易为用户所理解。　　现有少数算法能够挖掘部分类型的隐含任务，但都无法完全挖掘所有类型的隐含任务。例如，图２给出了α＃算法能够挖掘的几种隐含任务，其中黑色方块表示隐含任务。但它无法挖掘图１（ａ）类型的隐含任务。　　因此，本文在综合现有各种隐含任务挖掘方法的基础上，结合

6、结构化工作流X本身的特性，提出了一种基于算法和结构化工作流X的过程挖掘算法，该算法能够比较全面地挖掘结构化工作流X模型中的各类隐含任务。　　２结构化工作流X中的隐含任务　　２．１结构化工作流X　　过程挖掘通过深入分析过程日志来构造出过程模型。显然，算法所使用的建模语言决定了算法能够成功挖掘的过程及其日志的特性。目前，绝大多数过程挖掘算法都采用工作流X［１０］或者其子集作为建模语言，它是ＰｅｔｒｉX的一个子集，具体定义如下：　　定义１（工作流X）工作流XＮ为五元组（Ｐ，Ｔ，Ｆ，ｉ，ｏ）。其中，Ｐ为全体库所集合，T为全体

7、变迁集合，Ｆ为全体边集合，ｉ为输入库所，ｏ为输出库所。Ｍｏ＝｛ｉ｝为工作流X的初始配置。　　结构化工作流X是工作流X的各类子集中研究最多最深入的一种，其特点是不包含非自由选择结构，结构相对简单，但仍能满足大多数实际应用的需要。其定义如下：　　定义２（结构化工作流X）工作流XＮ＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ）是一个结构化工作流X，当且仅当：　　（１）对任意满足（ｐ，ｔ）∈Ｆ的ｐ和ｔ，有：｜ｐ・｜＞１→｜・ｔ｜＝１；　　（2）对任意满足（ｐ，ｔ）∈Ｆ的p和t，有：｜・t｜＞１→｜p

8、2539;｜＝１；　　（３）P中不存在隐含库所［９］。　　２．２隐含任务定义　　隐含任务就是在过程中存在并且被执行，但是始终不会被记录在过程日志中的任务。　　定义３（隐含任务）已知结构化工作流XN＝（Ｐ，Ｔ，Ｆ，ｉ，ｏ），W=T*是其对应的日志。则称t∈T是隐含任务，当且仅当不存在日志实例L∈W，使t∈L。N的全部隐含任务的集合记为H。　　隐含