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

基于结构化工作流网的隐含任务挖掘方法摘 要 过程挖掘是一种客观、自动化的过程分析技术，它通过挖掘过程日志来得到业务过程的结构模型，是传统过程分析手段的重要补充。如何正确挖掘包含隐含任务的不完整过程日志，是过程挖掘需要解决的难题之一。现有的一些算法如基因算法、#算法等解决了部分类型隐含任务的挖掘问题，但仍有许多类型的隐含任务无法被正确挖掘。针对这一问题，本文在#算法的基础上提出了一种基于结构化工作流网的挖掘算法，该算法能够较为完整地挖掘各类包含隐含任务的结构化工作流网模型。通过理论分析和实验验证，该算法的正确性和有效性得到了证明。关键词 过程挖掘；结构化工作流网；隐含任务；改进算法doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 07. 025中图分类号 tp391 文献标识码 a 文章编号 1673 - 0194（2012）07- 0048- 04 引 言面对激烈的市场竞争和市场环境的快速变化，现代企业必须能够随时对核心业务过程做出适当的调整以适应新的需要。这不但需要管理者能够掌握外部环境的变化，也需要管理者能够对企业业务过程的实际情况有清晰的了解。传统的过程分析手段，如调查、访谈、建模分析和模拟等，费时费力，而且受用户的主观性影响很大，容易出现偏差，因此越来越难以满足用户的需要。过程挖掘是一种自动化的过程分析技术，通过对业务过程日志的挖掘，自动生成业务过程的执行流模型，从而帮助用户更好地理解业务过程的内在执行逻辑。由于其分析的依据业务过程日志是企业在实际业务运行过程中生成的客观记录，因此该技术客观性强、费用低、速度快，有效地弥补了传统过程分析手段的各种缺陷，并已经在政府公共工程、医院和供应链管理等实际领域中取得了一定的成功应用。对包含错误、隐含任务等的不完整日志的挖掘是过程挖掘面临的难题之一。因为实际中用于挖掘的日志主要来源于企业的信息系统的自动生成，因此日志中包含错误的情况并不常见，不完整日志问题基本上都是由于包含隐含任务造成的。现有的大多数过程挖掘算法在处理包含隐含任务的日志时都无法得到正确的结果。少数几种能够处理隐含任务的算法，如基因算法、算法等，但只能挖掘部分类型的隐含任务，未能完全解决隐含任务的挖掘问题。针对这一问题，本文尝试提出一种基于算法和结构化工作流网的过程挖掘算法，该算法能够比较全面地挖掘结构化工作流网模型中的各类隐含任务。通过理论分析和实验验证，该算法的正确性得到了证明。 问题说明过程挖掘通过对日志信息的分析来构造过程模型。为了保证挖掘算法能够最大限度地适用于各种形式的日志，绝大多数挖掘算法仅要求日志中包含下列3项内容：事件所属的工作实例；执行事件的业务单元（任务标识）；事件发生的顺序（处理时间）。因此，在分析过程挖掘算法时，为了简便起见，通常直接将日志写成诸如，的形式，其中每个字母代表一个任务，每个逗号隔开的字母序列代表一条日志实例。对该日志实例用算法进行过程挖掘，就可以得到如图（）所示的结构化工作流网过程模型。在现实中，由于很多信息系统只对进行实际业务操作的业务单元活动进行记录，以及系统采用的过程建模工具本身的特性等各种原因，一些过程任务往往没有被记录在日志中。这种过程任务就是所谓的“隐含任务”。现有的大多数算法无法正确处理包含隐含任务的日志。例如，假设图（）中过程的任务是一个隐含任务，则得到的日志是，。用算法挖掘将得到如图（）所示的模型，它不是一个合法的结构化工作流网模型，而且相比原始模型，其结构复杂，不容易为用户所理解。现有少数算法能够挖掘部分类型的隐含任务，但都无法完全挖掘所有类型的隐含任务。例如，图给出了 算法能够挖掘的几种隐含任务，其中黑色方块表示隐含任务。但它无法挖掘图（）类型的隐含任务。因此，本文在综合现有各种隐含任务挖掘方法的基础上，结合结构化工作流网本身的特性，提出了一种基于算法和结构化工作流网的过程挖掘算法，该算法能够比较全面地挖掘结构化工作流网模型中的各类隐含任务。 结构化工作流网中的隐含任务 结构化工作流网过程挖掘通过深入分析过程日志来构造出过程模型。显然，算法所使用的建模语言决定了算法能够成功挖掘的过程及其日志的特性。目前，绝大多数过程挖掘算法都采用工作流网或者其子集作为建模语言，它是网的一个子集，具体定义如下：定义（工作流网） 工作流网为五元组（，）。其中，为全体库所集合，t为全体变迁集合，为全体边集合，为输入库所，为输出库所。 为工作流网的初始配置。结构化工作流网是工作流网的各类子集中研究最多最深入的一种，其特点是不包含非自由选择结构，结构相对简单，但仍能满足大多数实际应用的需要。其定义如下：定义（结构化工作流网） 工作流网（，）是一个结构化工作流网，当且仅当：（）对任意满足（，）的和，有：；（2）对任意满足（，）的p和t，有：tp；（）p中不存在隐含库所。 隐含任务定义隐含任务就是在过程中存在并且被执行，但是始终不会被记录在过程日志中的任务。定义（隐含任务） 已知结构化工作流网n（，），w=t*是其对应的日志。则称tt是隐含任务，当且仅当不存在日志实例lw，使tl。n的全部隐含任务的集合记为h。隐含任务问题的本质是日志中的信息缺失。显然，只有那些导致模型结构出现缺陷的隐含任务才有可能被发现，其他隐含任务在不引入其他知识的条件下是无法通过日志分析的方法来发现的。例如，图中的几种隐含任务都不会导致挖掘模型出现结构缺陷，都是无法被发现的。因此，本文只讨论会导致结构化工作流网的结构出现缺陷的那些隐含任务。 隐含任务分类按照在模型中的位置及其特点，可以将结构化工作流网中的隐含任务分成起始结束点型、隐含路径型、结构转换点型和子分支点型四大类。起始结束点型对应于 算法中的类型，是由出现在模型起始位置的与分支点和出现在模型结束位置的与汇合点形成的隐含任务，如图（）和（）所示。其定义如下：定义（起始结束点型隐含任务） 已知结构化工作流网（，）。当隐含任务th满足下列条件之一时，称其为起始结束点型隐含任务：隐含路径型对应于 算法中的和类型，是单独组成过程中的某条执行路径分支的隐藏任务，如图（）和（）所示。其定义如下：定义（隐含路径型隐含任务） 已知结构化工作流网（，）。称隐含任务th为隐含路径型隐含任务，当?埚，a?劢t，?奂。结构转换点型是由选择结构和并行结构之间的转换点形成的隐含任务。图是结构转换点型隐含任务的几种情况，其中左边是原始过程，右边是用算法挖掘对应的日志得到的模型。其定义如下：定义（结构转换点型隐含任务） 已知结构化工作流网（，）。当隐含任务th满足下列条件之一时，称其为结构转换点型隐含任务：子分支点型是由选择分支里的并行分支点形成的隐含任务。图是结构转换点的几种情况，其中左边是原始过程，右边是用算法挖掘对应的日志得到的模型。其定义如下：定义（子分支点型隐含任务） 已知结构化工作流网（，）。称隐含任务th为子分支点型隐含任务，当其满足下列条件之一： 隐含任务的发现在上一节中定义了几种隐含任务，它们的共同特点是会导致结构化工作流网的结构出现缺陷。因此，通过检测挖掘模型中的结构缺陷，就能够发现这些隐含任务的存在，并加以弥补。本文采用算法中次序关系作为检测模型结构缺陷的工具，其定义如下：定义（次序关系） （，）是合理工作流网，w是n的一个日志，即wt*，则有： 当且仅当?埚，：wti=ati+1=b；awb 当且仅当?埚t1t2tn，i1，：wti=ti+2a=ati+1=b；awb 当且仅当awbbwa；awb 当且仅当a（）；a#wb 当且仅当awbbwa；根据次序关系，就可以针对各类隐含任务的不同特点，分别找出它们的发现方法。因为 算法中已经给出了起始结束型和隐含路径型的隐含任务的检测方法，因此本文只讨论结构转换点型和子分支点型隐含任务的发现方法。 结构转换点型隐含任务的发现结构化工作流网中的结构转换点型隐含任务可以根据下面的定理发现：定理 已知结构化工作流网（，），w是其满足w和w关系完备性的日志。则n中存在结构转换点型隐含任务，当且仅当下列条件之一被满足：（）?埚， ， ， ， ， ， ；（）?埚， ， ， ， ， ， ；（）?埚， ， ， ， ， ， 。根据结构化工作流网的定义和图，很容易证明该定理的正确性。详细证明从略。 子分支点型隐含任务的发现结构化工作流网中的子分支点型隐含任务可以根据下面的定理发现：定理 已知结构化工作流网（，），w是其满足 和 关系完备性的日志。则n中存在子分支点型隐含任务，当且仅当下列条件之一被满足：（）?埚， ， ， ， ， ，；（2）?埚， ， ， ， ， ， b。根据结构化工作流网的定义和图，很容易证明该定理的正确性。详细证明从略。 隐含任务的检测顺序由于过程可能同时存在多种类型的隐含任务，一种隐含任务的存在可能会对另一种隐含的发现造成影响。因此各隐含任务的检测必须符合一定的顺序。由于起始结束点型隐含任务存在于模型的两端，其他类型隐含任务的发现可能会依赖于它的正确发现，因此应该先进行起始结束点型隐含任务的检测。结构转换点型的隐含任务本身是选择结构或者并行结构的起始点或者结束点，而子分支点型隐含任务的检测依赖于选择结构的起始点或结束点的存在。因此，结构转换点型隐含任务的检测必须先于子分支点型隐含任务。隐含路径型隐含任务的正确检测依赖于选择结构或者并行结构的正确结束，因此应该最后进行。 基于结构化工作流网的挖掘算法 子分支点型隐含任务发现算法根据前面的讨论，子分支点型隐含任务的发现算法 如下：定义（ 算法） 已知结构化工作流网（，），w是其满足w和w关系完备性的日志，rw是从w得到的所有次序关系集合。则子分支点型隐含任务的发现算法是：（）?埚，（）（，）|ab?奂tw（?坌bba）（?坌， ）（?埚（?坌）（）2（，b|a?奂twbtw（?坌aa a）（?坌a1，a2aa1|w a2）（?埚cb（?坌aa a）（）x=x1x2（）ty=ty|?埚yy（）r1=awty|?埚，（，），（）r2=tywb|?埚，（，），bb（）ry=r1r2（）tw=twty（）rw=rwry 结构转换点型隐含任务发现算法根据前面的讨论，结构转换点型隐含任务的发现算法 如下：定义（ 算法） 已知结构化工作流网n （p，t，f，i，0），w是其满足和关系完备性的日志，rw是从得到的所有次序关系集合。则结构转换点型隐含任务的发现算法是：（）?埚，（）（a，）|ab?奂（?坌，）（?坌， ）（?坌，2b1|2）（）2（，b）a?奂twbtw（?坌aa，bbawb）（?坌a1，a2aa1|w a2）（?坌b1，b2bb1b2）（4）3（，b）a?奂twbtw（?坌aa，bbawb）（?坌a1，a2aa1|w a2）（?坌b1，b2bb1b2）（5）x=x1x2x3（7）ty=ty|?埚yy（8）r1=awty|?埚，（，），（9）r2=tywb|?埚，（，），bb（10）ry=r1r2（1）tw=twty（2）rw=rwry3 基于结构化工作流网的隐含任务挖掘算法最终得到的基于结构化工作流网的隐含任务发现算法如下：定义（基于结构化工作流网的隐含任务发现算法） 已知结构化工作流网（，），w是其满足和w关系完备性的日志。则基于结构化工作流网的隐含任务发现算法是：（）?埚，（）构造rw（）（，）（，）（）（，）（，）（）（，）（，）（）（，）（，）（）n（，）其中， 和 分别是前面定义的子分支点型和结构转换点型隐含任务发现算法，和分别是算法中定义的起始结束点型和隐含路径型隐含任务发现算法，（，）是使用算法构造过程模型。 实验评估本文使用语言在平台上实现了提出的基于结构化工作流网的隐含任务发现算法，并对其进行了实验验证。实验使用了个手工构造的过程实例进行。图显示了实验中所使用的一个实例，其中，图（）是原始模型，图（）是使用算法挖掘的结果。使用本文提出的算法，挖掘出的模型与图（）中的模型完全相同。对其他实例的实验也得到了类似的结果，从而证明了算法的正确性。 结 论现有的过程挖掘算法大多无法正确挖掘包含隐含任务的过程日志，少数几种能够挖掘隐含任务的算法也不够完善，往往导致挖掘出来的过程模型过分复杂，难以分析和理解。针对这一缺陷，本文通过深入分析研究结构化工作流网过程模型中可能出现的各类隐含任务及其特点，提出了一种基于结构化工作流网的挖掘算法，可以较好地挖掘包含隐含任务的结构化工作流网过程日志，因此能够更好地帮助用户分析和理解过程执行流结构。作为一种自动化的建模工具，该算法适用于需要应用过程分析和建模的各类场合。本文通过实验评估验证了算法的可行性和有效性。接下来的研究方向是在现有算法的基础上继续深入扩展其适用的建模语言范围，从而进一步提高算法的实用性。主要参考文献b f ，a k ， ： m/k jensen, w m p van der aalst（）. ， ，：w m p ， ， p m： i a ， ， （）： t ，n ， m v a s ， ， （）： h c w ，g t s ， p m s s k d s c n ， ， （）： w m p ，b