（计算机软件与理论专业论文）基于动态工作流网的工作流过程挖掘研究.pdf

山东大学硕士学位论文 摘要 工作流是一种反映业务流程的计算机化的模型，是为了在先进计算机环境 支持下实现经营过程集成与经营过程自动化而建立的、可由工作流管理系统执 行的业务模型。工作流的生命周期包括工作流设计、工作流配置、工作流执行、 工作流诊断四个阶段。传统工作流管理方法存在的一个问题是：设计阶段工作 通常由业务专家具体执行，并力求体现企业管理层改进当前业务流程的思想。 实践证明，建立一个工作流过程模型是一项复杂和耗费时间的工作；不仅如此， 建立的过程模型往往不能与实际过程完全相符。 工作流挖掘技术不是一个工作流设计的工具，但它对充分理解现有业务过 程执行情况有很大的帮助。工作流挖掘的目标是：倒转过程，收集和利用运行 数据，从而支持工作流设计和分析。通过多年的信息化建设工作，很多组织都 拥有或大或小的传统信息化管理工具，如管理信息系统( m i s ) 、企业资源计划 ( e r p ) 、客户关系管理( c m 田等。大多数信息系统都能够记录事务数据，这些运 行数据记录了长时间的业务过程具体执行情况，可以用来生成一个描述业务过 程的模型。 工作流挖掘的起点是收集和处理工作流日志。本文对工作流日志定义是任 务序列( - - 元组) 的集合。本文提出的定义在保留必要日志信息的基础上，简化了 工作流日志的形式。本文还对日志相关概念做出了定义。 目前，工作流挖掘技术的一个难点是：怎样挖掘出更多有价值的过程信息。 对于一组工作流日志，以往挖掘算法的处理方法均是对其整体进行挖掘处理。 而在实际生产生活中，很多业务过程往往会随时间变化、环境变化、业务变动 而发生变化。 针对以往工作流挖掘技术对日志动态特性缺乏分析的缺点，本文提在工作 流网模型的基础上提出动态工作流网( d w f - n e t ) 。d w f - n e t 由动态变迁、动态库 所和它们之间的有向弧组成。动态变迁具有一个属性二元组( s ，d ) ，s 表征动态 变迁在工作流日志中出现的频率，也称为动态变迁的支持因素，当支持因素满 足指定条件时，动态变迁被认为是“真实的”；d 描述动态库所支持因素s 的变 i l l 山东大学硕士学位论文 i 化情况，称为支持因素s 的“动态描述”。动态库所也具有一个属性二元组( c ， d ) ，c 表示置信因素，d 表示置信因素c 的“动态描述”。本文同时给出了d w f n a 及其组件的定义，进行了合理性分析，并给出了生成动态工作流网的算法。 d w f n e t 能够充分挖掘工作流日志中的信息，获取日志中业务变化的情况，并 在挖掘得到的工作流模型中描述变化的情况。 生成动态工作流网，首先要求得d w f - n e t 的结构，然后计算d w f n e t 中各 元素的动态描述。本文首先介绍了这两步工作的思路，然后给出了算法描述， 并对算法时间复杂度进行了分析。 原型系统d w f g e n e r a t o r 实现了本文描述的动态工作流网生成算法。该系统 是基于m a t l a b 6 5 开发的。该系统能够对符合本文工作流日志定义的工作流日志 进行挖掘，输出动态工作流网。 关键词：工作流；过程建模；动态工作流网；过程挖掘算法 i v 山东大学硕士学位论文 a b s t r a c t t h ew o r k f l o wl i f ec y c l ee n n s i s t so ff o u rp h a s e s ：w o r k f l o wd e s i g n , w o r k f l o w c o n f i g u r a t i o n , w o r k f l o w e n a c t m e n ta n dw o r k f l o wd i a g n o s i s i nt h et r a d i t i o n a l a p p r o a c ht h ed e s i g np h a s ei su s e df o rc o n s t r u c t i n gaw o r k f i o wm o d e l t h i si s t y p i c a l l yd o n eb yab u s i n e s sc o n s u l t a n ta n di sd r i v e nb yi d e a so fm a n a g e m e n to n i m p r o v i n gt h eb u s i n e s sp r o c e s s e s a th a n d c r e a t i n gaw o r k f l o w d e s i g ni s a c o m p l i c a t e d t i m e - c o n s u m i n g p r o c e s sa n d t y p i c a l l y t h e r ea r e d i s c r e p a n c i e s b e t w e e n t h ea c t u a lw o r k f l o wp r o c e s s e sa n dt h ep r o c e s s e sa sp e r c e i v e db yt h em a n a g e m e n t t h ew o r k f l o wm i n i n gt e c h n o l o g yi sn o t j u s tat o o lo f w o r k f i o wd e s i g n , b u ti ti s v e r yu s e f u lf o ru n d e r s t a n d i n gt h ec u r r e n tb u s i n e s sp r o c e s s e s t h eg o a lo fw o r k f i o w ， m i n i n gi st or e v e r s et h ep r o c e s sa n dc o l l e c td a t aa tr u m i m et os u p p o r tw o r k f l o w d e s i g na n da n a l y s i s s i n c et h ei n f o r m a t i o nc o n s t r u c t i o nh a sb e e nc a r r i e do ni nm a n y o r g a n i z a t i o n sf o rs e v e r a ly e a r s ，t h eo r g a n i z a t i o n sh a v et h e i ro w n i n f o r m a t i o ns y s t e m s 。 s u c ha sm i s e r po rc r m i nm o s ti n f o r m a t i o ns y s t e m st r a n s a c t i o n a ld a t ai s r e g i s t e r e d t h ei n f o r m a t i o nc o l l e c t e da lr u n - t i m ec a nb eu s e dt od e r i v eam o d e l e x p l a i n i n gt h ee v e n t sr e c o r d e d t h eb e g i n n i n go fw o r k f l o wm i n i n gi st oc o l l e c ta n df o r m a tt h ew o r k f l o wl o g w ed e f i n e dt h ew o r k f l o wl o ga sas e to ft a s ks e r i e s t h a td e f i n i t i o nc o n t a i n st h e n e c e s s a r yi n f o r m a t i o no ft h el o gw i t has i m p l ef o r m a t w ea l s od e f m e dt h er e l a t e d c o n c e p t i o n s i ti sac h a l l e n g et oe x p l o i tm o r ei n f o r m a t i o ni nas e to f w o r k f l o wl o g t h ef o r m e r w o r k f l o w m i n i n g m e t h o d s t y p i c a l l y t a k e t h e w o r k f l o w a s aw h o l e b u t i n p r a c t i c e m a n yb u s i n e s sp r o c e s s e sc a nv a r yw i t ht h ec h a n g eo f t i m e ，e n v i r o n m e n t i nt h i sp a p e rw et a k ead i f f e r e n tp e r s p e c t i v ew i t hr e s p e c tt ot h ep r o b l e m sr e l a t e d t ot h ed y n a m i ci n f o r m a t i o ni nw o r k f l o wl o g d y n a m i cw o r k f l o wn e t ( d w f - n e t ) i s p r o p o s e db a s e d o nt h ec o n c e p t i o no fw f - n e t d w f - n e tc o n s i s t so fd y n a m i c t r a n s a c t i o n s ，d y n a m i cp l a c ea n dd i r e c t e da r c sb e t w e e nt h e m t h ed y n a m i ct r a n s a c t i o n 山东大学硕士学位论文 h a st w oa t t r i b u t e s ：( s ，d ) sm e a n st h ef r e q u e n c yo f t h ed y n a m i ct r a n s a c t i o np r e s e n tt o t h ew o r k f l o wl o g i ti sa l s ot h es u p p o r tf a c t o r w h e nss a t i s f i e st h ea l l o c a t e dc o n d i t i o n ， t h ed y n a m i ct r a n s a c t i o ni sr e g a r d e da s r e a l ”dd e s c r i b e st h ev a r i e t yo fsa n di s c a l l e d “d y n a m i cd e s c r i p t i o n ”o fs t h ed y n a m i cp l a c ea l s oh a st w oa t t r i b u t e s ：( c ，d ) c i sb e l i e v a b l ef a c t o ra n ddi s “d y n a m i cd e s c r i p t i o n o fs ht h i sp a p e rt h ed e f i n i t i o no f t h er o u t e sa n dt h ep r o o f o f t h es o u n d n e s so f d w f n e ti sp u tf o r w a r d w ed e s i g n e dt h ea l g o r i t h mo f g e n e r a t i n gad w f n e tf r o mw o r k f l o wl o g t h e f i r s ts t e pi st og e tt h es t r u c t u r eo ft h ed w f n e t t h es e c o n di st o g e tt h ed y n a m i c d e s c r i p t i o n s h lt h i sp a p e rt h ei d e aa n dt h ed e t a i l so fa l g o r i t h mi sb o t hi n t r o d u c e d t h e c o m p l e x i t yi sa n a l y z e da sw e l l d w f g e n e r a t o ri sap r o t o t y p e ，w h i c hr e a l i z e st h ed w f n e tg e n e r a t e o na l g o r i t h m t h es y s t e mi sm a i n l yd e v e l o p e do nm a l t l a b 6 5 i tc a nm i n et h ew o r k f l o wl o g ，w h i c h s a t i s f i e st h ef o r m a tp r o p o s e di nt h i sp a p e ra n dg e t st h ed w f - n e t k e yw o r d s ：w o r k f l o w ；p r o c e s sm o d e l i n g ；d y n a m i cw o r k f l o wn e t ；p r o c e s s m i n i n ga l g o r i t h m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文储缝国迅日规! 迦盟! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅； 本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 一一：躯一名：涮一 山东大学硕士学位论文 第一章绪论 1 1 工作流定义及相关基本概念 1 1 1 工作流及工作流管理系统 工作流的概念起源于办公自动化和制造业，它是针对日常工作中具有相对固 定程序的活动而提出的一个概念。工作流管理联盟( w f m c ) 给出的工作流定义1 1 l ： 工作流是一类能够完全或者部分自动执行的业务过程，它根据一系列过程规则、 文档、信息或任务能够在不同的执行者之间进行传递与执行。 这个定义说明【2 j ：1 、工作流是业务过程的一个计算机实现，工作流管理系 统就是这一实现的软件环境；2 、使用工作流作为业务过程的实现技术首先要求 工作流系统能够反映业务过程中的几个问题，即业务过程是什么、怎么做、由谁 来做、做得怎样。 工作流模型是一种反映业务流程的计算机化的模型，是为了在先进计算机环 境支持下实现经营过程集成与经营过程自动化而建立的可由工作流管理系统执 行的业务模型。 3 1 工作流管理系统( w 蹦s ) 是支持企业业务过程高效执行并监控其执行过程的 计算机软件系统。 3 1 1 1 2 工作流模型 工作流模型是对工作流的抽象表示，也就是对业务过程的抽象表示；工作流 模型是整个工作流管理系统的基础。文献【3 提出了三个模型设计原则： ( 1 ) 面向企业用户，以简单、直观、容易掌握为前提。 ( 2 ) 过程描述能力强，能够定义可能发生的各种过程逻辑：这一原则对模型 的过程语义提出了较高的要求。模型在简单化的同时，必须要兼顾其自身的描述 能力。除了常见的由w f m c 定义的基本原语( 如“与分支”、“或连接”等) 外， 过程中还可能出现更复杂的逻辑关系如“a 活动的执行不能早于b 活动”，“a 与 b 互斥，但其具体的选择机制则依赖于外界的，是随机的”等等，这些情况也同 样要求模型提供相应的概念予以支持。 ( 3 ) 应该体现企业这一复杂系统的多视图特性：工作流模型应该是一种综合 山东大学硕士学位论文 性的模型，不仅能够描述一个经营过程“是什么”的问题，而且还应该能描述“由 谁做”、“怎么做”等方面的问题。 在以上三条原则的约束下，工作流模型由四部分组成，分别是过程模型、组 织模型、资源模型以及工作流相关数据。其中，组织模型用来定义企业人员的组 织结构；资源模型用来定义企业资源的组织结构；工作流相关数掘用束定义工作 流执行过程中需要用到的数据。 过程模型用来定义工作流的过程逻辑，包括组成工作流的所有活动以及活动 之间的依赖关系。它是整个工作流模型的基础与核，i l , ，其他模型均为其提供支持。 在很多情况下，“工作流模型”指的就是“过程模型”。如果没有特别指出，本文 所说的“工作流模型”均指“过程模型” 1 1 3 工作流建模 工作流建模是利用一个或多个建模方法及其相应的建模工具，完成实际的业 务过程到计算机可处理的形式化定义的转化，所得到的过程定义称为“工作流模 型”，或者“过程模板”、“过程元数掘”。 有多种工作流建模方法啪，如基于活动网络模型、基于事件驱动的过程链 ( e p c ) 模型、基于语言行为理论( i p o ) 模型、基于p e t r i 网模型和基于在p e t r i 网模 型基础上提出的工作流网( w f - n e f ) 模型等等。本文将主要使用基于w f - n e t 的建 模方法。 1 1 4 工作流生命周期 l ：柞流 i ：作流 设汁 。i 作流 配诧 图1 1 工作流生命周期示意图 工作流的生命周期包括工作流设计、工作流配置、工作流执行、工作流诊断 四个阶段钔。设计阶段的主要任务是构建工作流模型。配置阶段主要是根据设计 2 山东大学硕士学位论文 好的工作流模型，在工作流管理系统中进行具体配置，以使系统按照业务模型执 行。在执行阶段，工作流实例被系统执行；同时，工作流系统还可以生成记录业 务过程运转情况的系统日志。诊断阶段可以为设计阶段提供输入，从而使工作流 生命周期成为一个循环的过程。 传统工作流管理方法存在的一个问题是：设计阶段工作通常由业务专家具体 执行，并力求体现企业管理层改进当前业务流程的思想。实践证明，建立一个工 作流过程模型是一项复杂和耗费时间的工作；不仅如此，建立的过程模型往往不 能与实际过程完全相符。 存在的另一个问题是：生命周期的重点往往集中在设计和配置两个阶段，很 少有组织收集其工作流系统的运行数据进行诊断，并作为再设计的输入。 1 2 工作流挖掘的概念 “过程挖掘( p r o c e s sm i n i n g ) ”及类似的概念“过程发现( p r o c e s sd i s c o v e r y ) ” 的出现比“工作流挖掘( w o r k f l o w m i n i n g ) ”更早，其目标是利用已有的过程信息， 使用过程挖掘技术获得过程模型。过程挖掘在软件工型s 】等领域的工作被引入工 作流挖掘，并且获得发展。 虽然工作流挖掘技术不是一个工作流设计的工具，但它是对充分理解现有过 程执行情况有很大的帮助。 工作流挖掘的目标是：倒转过程，收集和利用运行数据，从而支持工作流设 计和分析e 4 。通过多年的信息化建设工作，很多组织都拥有或大或小的信息化管 理工具。如管理信息系统m i s ) 、企业资源计划但r p ) 、客户关系管理( c 鼢田等。 大多数信息系统都能够记录事务数据，这些运行数据记录了长时间的业务过程具 体执行情况，可以用来生成一个描述业务的模型。 将工作流挖掘应用到工作流建模过程中可以提高模型准确性。对一个已有的 过程建模，会受到建模者个人理解的影响，比如，模型常常会在某种程度上成为 他们认为应该的过程，而不是描述实际过程。其结果就是使模型变得主观。使用 与实际发生过的业务过程相关的数据会使建模方法更加客观。工作流挖掘是一个 不受个人意识影响的行为。当然，如果人们通过某种方式，不按照系统正常情况 执行业务过程，那么运行数据会偏离实际业务过程。比较人工分析得到的模型与 工作流挖掘的得到的模型会对建模有益。【4 丙，7 - 8 】 山东大学硕士学位论文 利用工作流挖掘技术可以进行系统d e l t a 分析，也就是说在工作流执行阶段 发现在设计阶段构建的工作流模型与实际运行时记录的数掘之间的矛盾。目的， 工作流技术向更加灵活的方向发展，工作流系统力求能够简单灵活地处理工作流 模型的动态变化。这就在一定程度上允许操作人员在业务过程中改变原先的模型 设计，那么这些改变就需要被系统的管理人员发现和分析。工作流挖掘技术就可 以用于工作流诊断阶段的d e l t a 分析，用来发现随着环境变化，系统所产生的缺 陷。1 4 , 6 , 7 工作流挖掘技术与一些管理趋势有密切联系。工作流挖掘本身可以看作商业 智能( b i ) 、业务过程分析( b p a ) 、和知识管理( k m ) 的一部分，也可以作为业务过 程重组0 3 1 r ) 和持续过程改进( c p i ) 的输入。【4 6 7 】 1 3 工作流过程挖掘的研究现状和面临的主要问题 c o o k 和w o l f 在软件工程过程领域对过程挖掘进行了研究。在文献 4 】中提出 了三种过程挖掘方法，分别使用了神经网络、有限状态机、马尔科夫过程。作者 认为后两种方法是有前途的。其中马尔科夫方法结合了统计方法，从而能够处理 数据中的噪声。但是这些方法仅能处理串行活动。文献 1 0 ，1 1 将他们的工作扩展 到了并行活动中；提出具体的度量，如熵、事件类型统计、周期、依赖关系，并 使用这些度量在事件流中发现模型。但是他们没有给出生成具体过程模型的方 法。文献 1 2 】给出一个衡量过程模型与实际运行数据之间矛盾程度的方法。 文献 1 3 】最早把过程挖掘的思想与工作流管理相结合。他们基于工作流图， 提出两个问题：l 、获得一个能够生成与工作流日志中事件相符的事件序列的工 作流图：2 、获得工作流图边条件的定义。文中给出了处理第一个闯题的具体算 法。由于工作流图不区分“与”分支和“或”分支，所以这个算法与其它算法不 同。另外，工作流图不支持有环图。该文也没有给出生成具体模型的算法。 文献 1 4 ，1 5 】描述了一个过程挖掘工具，该工具能够挖掘层次结构的工作流过 程。但是它需要过程中s p l i t 和j o i i l 是平衡的。文献 1 6 e p 的算法使用了随机任务 图作为模型的过渡描述工具。最终生成的工作流模型用a d o n o s 建模语言描述。 与其它算法相比一个显著的不同是：同一个任务可以在过程中出现多次。生成图 的算法与 1 7 】相似。文献【1 8 的工作重点在于挖掘工作流过程中的并发活动。 文献 1 8 】提出的启发式方法是基于“依赖频率表”的，这种方法能够处理工 4 山东大学硕士学位论文 作流日志中的噪音数据。文献【1 9 】总结了过程中可能出现的不正常情况及处理方 法。文献【2 0 】提出了f l e x i b l et 作流网模型，可以对不确定和不完整业务过程信 息建模。 文献 1 7 磷 出a 算法并证明，该算法说明对于满足一定条件的日志集合，能 够挖掘出正确的工作流模型。在文献 2 1 】中，a 算法被扩展到可以处理时间信息 【4 1 。随后，d 算法中增加了处理业务过程中出现的短环的算澍2 2 1 。 文献 2 3 ，2 4 ，2 5 ，2 6 分别介绍了工作流挖掘工具在移动通信系统、医院管理系 统工作流建模中的应用。 对于一组工作流日志，以上挖掘算法的处理方法均是对其整体进行挖掘处 理，研究的重点均在于识别工作流日志整体所体现的工作流模型的结构。 目前，工作流挖掘技术的一个难点是：怎样挖掘出更多有价值的过程信息 1 4 , 2 7 2 s 1 。在实际生产生活中，很多业务过程往往会随时间变化、环境变化、业务 变动而发生变化。比如某些电力部门的工作流程会随着电力负荷的紧张程度变化 而变化，而电力负荷情况又与季节有很大关系。所以，如果仅仅简单的对工作流 日志进行整体的处理，会损失大量的过程信息，而无法把握工作流过程模型的变 动规律，同时也会影响过程挖掘的准确性。 1 4 本文所做的主要工作 第一，给出了“工作流日志”明确定义； 第二，对a j j m w e i j t e t s 提出的基于依赖频率表的工作流挖掘技术进行了 总结提炼，给出算法描述； 第三，针对现有工作流挖掘技术对日志中动态信息关注不足的缺点，提出动 态工作流网模型，给出形式化定义，并进行了合理性证明； 第四，根据动态工作流网的定义，提出动态工作流网的生成算法： 第五，开发了原型系统d w f g e n e r a t o r ，实现了本文提出的动态工作流网生 成算法。 1 5 本文的组织结构 第一章介绍工作流定义及相关基本概念，包括工作流及工作流管理系统、工 作流模型、工作流建模、工作流生命周期、工作流挖掘的概念，分析工作流过程 山东大学硕士学位论文 挖掘的研究现状和面临的主要问题，并介绍了本文所做的主要工作； 第二章讨论工作流日志，给出一种简单的日志描述形式和本文对工作流日志 的定义： 第三章首先介绍了基于p e t r i 网的概念工作流网( w f - n e t ) 模型，然后着重介绍 了基于依赖频率表( d f 表) 的工作流挖掘方法； 第四章提出动态工作流网模型的定义，并对动态工作流网进行了合理性分 析，同时给出了动态工作流网的基本组件的定义； 第五章探讨了动态工作流网的生成算法，并介绍了实现该算法的原型系统 d w f g e n e r a t o r 第二章工作流日志 2 1 工作流日志：工作流挖掘的起点 工作流挖掘的目标是从业务过程的事务日志中抽取信息，也就是说日志是工 作流挖掘的输入。所以工作流挖掘的第一步是要收集与发生的业务过程有关的信 息。任何基于事务的信息系统( 如e r p 、c r m 等，并不要求是工作流管理系统) 都可以以某种形式提供满足下列条件的过程工作流日刹1 8 l ： ( 1 ) 每一个发生的事件饵v c n t ) 都对应于系统中定义好的一项任务( t 勰k ) ； ( 2 ) 每一件发生的事件都属于一个执行实例( c a s e ) ； ( 3 ) 事件是有序的，即使是并行发生的事件也会被顺序地记录下来。 需要注意的是，业务执行实例与业务模型之间的关系是具体与抽象的关系， 任务与事件之间也是具体与抽象的关系。 图2 - 1 是一个简单的业务过程模型示例。表2 1 是工作流管理系统s 湎a r e 生成的、按照图2 一l 中业务过程执行的日志片断。在s t a f f w a r e 系统中每个实例 的事件被分组列出第一列是任务描述，第二列是事件类型，第三列是触发事件 的用户，第四列是一个时间戳标志。 图2 - 1 业务过程模型示例1 4 】 。一 山东大学硕士学位论文 c a 5 口1 0 d i r e c t i v ed e s c r i p t i o ne v e n t u s e r y y y y i d dh h ：m h 班s t e z r e g i s t e r s e n dq u e s t l o u a i r e e v a l u a t e s e n dq u e s r i o n n a l r e r e c e i v eq u e s t a o n n a i r e b c e i v eq u e ；t a o n n a ；r e e v a l u a t e a r c h i v e a r c h = r e s t a r t p r o c e s e dt o r e l e a s e db y f r o t j 表示) ，t j 是t 七 。 的k 次后继( 用t l t j 表示) ，t j 是t 的直接后继( 用t l 0 对，c 2 获得托肯，因而活动b 将执行；当x o 时，c 3 获得托肯，活动c 将执行。由于从图中可以明确地看出分支中的哪一个活动将被执行，因而被称为 “显式或分支”。在这里b 与c 的选择结果是由活动a 决定的，也就是说，当a 执行完毕后，b 与c 哪一个将被执行也就确定了。 c 3 图3 - 4 显式或分支 ( 4 ) 循环组件：循环组件用来定义需要重复执行多次的活动，它用一个“显 式或分支”的执行原语，如图3 5 所示。 p l p 2p 3 p 4 图3 - 5 循环组件 山东大学硕士学位论文 在图3 5 中，b 是被反复执行的活动，而c 可以理解为一个起控制作用的任 务，用来检验b 的执行结果，以决定是把托肯移到p 4 还是移回p 2 。如果托肯被 移到p 4 ，则b 不再被执行，而是继续推进流程进度；如果托肯被移回p 2 ，则b 将被重复执行。 在图3 - 6 的工作流网中包含了这四种结构。 图3 - 6 w f n e t 图例 3 2 基于依赖，频率表( d f 表) 的工作流挖掘方法 该方法的目标1 1 8 】： 对于给定工作流日志w l ，挖掘得到一个合理的工作流网模型，这个模型： ( 1 ) 能够生成w l 中所有事件序列； ( 2 ) 尽可能的不生成w l 之外的事件序列： ( 3 ) 能够发现并发活动； ( 4 ) 结构尽可能简洁。 该方法的输入工作流日志w l 符合第二章第2 节描述的工作流日志结构。 可以把挖掘过程分为三步进行：建立依赖频率表，从d f 表获取基础关系 表，生成工作流网，下面分别详述。在方法描述中，使用了定义1 1 中的术语。 3 2 1 建立依赖频率表表 挖掘的第一步是建立依赖频率表( d e p e n d e n c y f r e q u e n c y 表，简称d f 表) 。 对于每个事件a ，需要从工作流日志w l 中获取以下信息： ( 1 ) 事件a 出现的频数，用f r q ( a ) 表示； ( 2 ) 事件a 作为另一个事件b 的直接后继的频数，用f l q ( b 8 ) 表示； t ( 4 ) 事件a 作为另一个事件b 的k 次后继的频数，用丘q ( b b ) 表示，k 0 ( 6 ) 事件a 与b 之间依赖关系的度量值，用c ( a b ) 表示。 对于事件a ，在一个实例的事件序列中查找它的k 次后继任务b 对，当遇 到另一个事件a 或第二个事件b 时，本次查找结束。例如： t 对于一个实例的事件序列b ，c ，a ，d ，e ，f , d , a ，c ，当计算b a 时，可以 16 得到f r q ( b 舢= 1 ，不能得到f r q ( b b ) 一q ( b b ) 一f r q ( b “ b ) - 且葡万一 式3 - 1 根据式2 1 ，随着事件a 与事件b 在工作流日志中相隔的距离增大，对两个 事件之间依赖关系的影响减小，这是通过将求得的k 次后继或k 次前驱的频数乘 以衰减因数实现的。 依赖频率表是一个m m x ( l + 2 ) 三维表：第一维是任务a ，其中数据是在 工作流同志中出现的所有任务：第二维是任务b 。其中数掘也是在工作流日志中 l- - 2 出现的所有任务；第三维结构为( f r q ( b ) ，f r q ( b a ) ，蜘( b a ) ，靠q ( b b ) ，的( a l - 2 b ) ，c ( a _ b ) ) 。表中元素为： 山东大学硕士学位论文 it d f ( t ，置，的( b a ) ) = 蜘( t j b ) ) a n d ( f r q ( b _ f f q ( a ) a n d ( f r q ( a a ) e ) t h e n b r ( a ，b 1 = 1 式3 - 4 ( 3 ) i f ( ( c ( a 寸b ) e ) a n d ( 的( a b ) ) a n d ( f r q ( b b ) e ) a n d ( ( 丘q ( b b ) ) e a n d ( 警2 ( 知( a 南b ) f f q ( a ) ，) t h e n b r ( a ，b 1 = 1 式3 5 其中，e 【o ，1 ) 为噪音因子，噪音因子c 的取值可以根据工作流日志中噪 音数据的含量变化，也可以根据数据试验的情况进行调整；式3 4 中，c ( a b ) e 表明任务a 与任务b 之间的依赖值需要大于噪音因子，否则不能确定他们 之间关系的真实性；当e 取值为0 时，表示工作流日志中没有噪音数据。 为门 限因子， 的计算公式为式2 6 。 山东大学硕士学位论文 a = 1 + r 。u n d ( - 鲁) 式3 - 6 根掘式3 4 能够判断出绝大多数任务之间的邻接关系，但是不能识别图3 2 中的短环式3 4 能够补充识别图3 2 中( 1 ) 的情况，式3 5 能够补充识别图3 2 e o ( 2 ) 的情况。 ， f i 迨 图3 7 短环 3 2 3 生成工作流网 得到基础关系表就得到了所有任务之间存在的连接关系，也就是说可以得到 一个由任务和弧组成的图。但是这个图中没有表示条件的库所，也就没有区别分 支之间的“与”和“或”，所以需要进一步的处理才能得到w f - n e t 。 如果基础关系表中，b r ( a ，b ) = b r ( a ，c ) = 1 ，这意味着，a 既是b 的直 接前驱，又是c 的直接前驱。为判断b 与c 之间是“与”关系还是“或”关系， 需要参考d f 表中的数据。根据“与分支”的定义，如果b 与c 之间是与关系， 那么事件序列中，b c 和c , b 的情况都是合理的，所以丘q ( b c ) 和f r q ( c b ) 的值都是显著的。如果是或分支，那么两种情况只有一种是显著的。 另外，在复杂的情况下，有的分支结构中有三个或更多分支，那么允许部分 分支之间是“与”关系，部分分支之间是“或”关系。 图3 - 8 分支判定算法示意图 s e t l s e t k 金 山东大学硕士学位论文 图3 - 8 ( 1 ) 中有任务a 和a 的直接后继b 1 ，b 。，这是可以从基础关系表中得 出的。算法3 - 1 的功能是将b l ，b 。分组：把符合“或”关系的任务集中到一个 集合中，不符合“或”关系的任务放在不同的集合中。 算法3 1 分支判定算法 输入：基础关系表b r ，设任务b 。b n 是任务a 的直接后继；s e t j ，s e t 是空集合： 输出：s e t l ，s e t 。所有集合内部的任务之间是或关系，集合之间是与关系； f o r i ：= 1t o n d o b e g i n f o r j ：= lt o n d o b e g i n o k ：= f a l s e ； r e p e a t i fv x s 【( 的( b 。 殉 b ) ) 】t h e n ，判断任务之间是否符合“或”关系 b e g i n s 鸭：- - - s e bu b ，) ； 如果满足“或”关系，并入该集合 o k ：- - t r u e ； e n d ； u n t i lo k ： e n d 0 ) ； e n d ( i ) 3 3 本章小结 本章首先介绍了一种重要的工作流建模方法：工作流n ( w f - n c t ) 模型。 w f - n e t 着力于对工作流模型的核心过程模型的描述。基于依赖频率表 ( d f 表) 的工作流挖掘方法使用w f - n e t 作为建模方法。 本章在前人工作的基础上，总结、提炼了基于d f 表的工作流挖掘方法，给 出明确描述基于d f 表的工作流挖掘方法以符合2 2 节描述的工作流日志为输 2 l 山东大学硕士学位论文 入，根据日志建立d f 表，在d f 表的基础上得到基础关系表：按照3 个启发式 规则由d f 表和基础关系表的数据，挖掘得到工作流网。 山东大学硕士学位论文 第四章动态工作流网 在实际生产生活中，很多业务过程往往会随时间变化、环境变化、业务变动 而发生变化。比如某些电力部门的工作流程会随着电力负荷的紧张程度变化而变 化，而电力负荷情况又与季节有很大关系所以，如果仅仅简单的对工作流日志 进行整体的处理，会损失大量的过程信息，而无法把握工作流过程模型的变动规 律，同时也会影响过程挖掘的准确性。 为了提高过程挖掘所获得的信息量，并对信息进行充分描述，本文提出动态 工作流网( d w f - n c t ) 。d w f - n e t 能够描述以工作流日志为输入数据，根据d w f - n e t 挖掘算法得到的工作流过程模型的动态变化情况。 4 1 动态工作流网( d y n a m i cw f - n e t ) 定义 定义4 - 1d w f - n e t 挖掘算法 d w f - n c t 挖掘算法是以工作流日志l 为输入数据，输出d w f - n c t 的算法。 对于一组工作流日志，挖掘目标不同的d w f - n c t 挖掘算法所得到的d w f - n e t 可能不相同。 定义4 - 2 动态变迁，支持因素，动态描述 动态变迁表示工作流过程中的任务；动态变迁具有一个属性二元组( s ，d ) ， 这是一般变迁不具备的。s 表征动态变迁在工作流日志l 中出现的频率，也称为 动态变迁的支持因素，当支持因素满足d w f - n e t 挖掘算法指定条件6 时，动态 变迁被认为是“真实的”；d 描述动态库所支持因素s 的变化情况，称为支持因 素s 的“动态描述”。动态变迁用方框表示。 定义4 - 3 动态库所，置信因素 动态库所对应于一个动态变迁有序对，表示变迁间的条件；动态库所具有一 个属性二元组( c ，d ) ，这是一