（计算机软件与理论专业论文）基于日志的流程挖掘算法研究.pdf

山东大学硕士学位论文 摘要 当今的信息系统大多都是精确流程模型驱动的。工作流管理系统，还有e r p 、 c r m 和b 2 b ，都是基于任务的工作流模型配置的。实现一个工作流设计是一个 耗时间的复杂过程，而且经常在实际的工作流程和管理的工作流之间存在差异。 本文给出了一个新的建模方法以支持精确流程建模，我们称这种建模方法为“基 于日志的流程挖掘”，即从已经存在的业务流程执行过程产生的日志中挖掘出我 们需要的工作流模型。我们用到的日志叫做“事件日志”，该日志将流程中的每 个任务作为一个原子事件来处理。 本文首先介绍了工作流技术最新的发展状况，以及w f m c 的工作流参考模 型，然后文章总结了当前工作流建模的主要方法，提出了工作流建模领域存在的 机遇和挑战。在详细讨论流程挖掘方法前，文章对与挖掘有关的技术和理论进行 了描述，包括日志的数学表达模型，p e t r i 网和工作流网的相关属性，p e t r i 网到 工作流网的映射关系等。 本文讨论了最具有挑战性的问题一非结构化流程挖掘，主要是非自由选择结 构的挖掘。其中分为两个部分：流程挖掘算法和流程挖掘算法的改进。在第一部 分，文章给出了一种基于日志的新的流程挖掘算法，给出了算法的j a v a 实现。 算法分两步，首先根据日志中任务间的先后顺序，确定流程中各任务间的连线， 从而得到流程图的结构，进一步分析流程日志确定顺序，选择，并行，循环等关 系。在第二部分，在此算法的基础上进行改进，实现了非自由选择结构的挖掘。 其基本思想是，采用“默认存在的思想，即对于日志的每一条执行轨迹中所有 的不相邻任务，其相连的可能性都看成是存在的，然后根据对日志的分析排除不 可能相连的任务对，确定选择线。该种方法得到的流程图是合理的，安全的，并 且是容易理解的。 最后，通过运行模拟日志获得足够的实验数据，对该算法的挖掘质量进行了 检验分析，证明该算法在复杂流程的挖掘方面具有明显优势。 关键词：流程挖掘；事件日志；非自由选择结构；工作流网；p e t r i 网 山东大学硕士学位论文 a b s t r a c t a tp r e s e n t ，m o s ti n f o r r m t i o ns y s t e n na r ed r i v e nb ye x p l i c i tp r o c e s sm o d e ls w o r k f l o wm a n a g e r m n ts y s t e m , a n de r p ，c r m , b 2 ba r ea l lc o n f i g u r e dw i t h w o r k f l o wm o d e l sb a s e do l lt a s k s d e s i g n i n gap r o c e s sm o d e li sac o m p l i c a t e dt i m e - c o n s u m i n gp r o c e s s ，a n d l h e r ea l ea l w a y ss o 脚ed i s c r e p a n c i e sb e t w e e nt h ea c t u a l w o r k f l o wa n dt h em o d e lw ec r e a t e d i nl i f t sp a p e r , 、阮p r e s e n tan e wm e t h o df f l a t s u p p o r tt 1 e e x a c tw o r k f l o wd e s i g n w ec a l l l h i sw o r k f l o wm o d e l i n gm e t h o da s p r o c e s sm i n i n gf r o ml o g ，w h i c hu s et h ed a t ad i r e c t l yr e l a t e dt ol h ee v e n t sh a p p e n e d d u r i n gl t a ee x e c u t i o no fe x i s t i n gp r o c e s st os u p p o r tw o r k f l o wm o d e l i n g t h eb g u s e di ni b i sp a p e ri sas oc a l l e d e v e n tl o g ，w h i c hc o n s i d e re v e r yt a s ki nt h ep r o c e s s 嬲a na t o m i ce v e n t t h ep a p e rb e g i nw i t hf i l ei n t r o d m t i o no fn e w e s td e v e l o p m e n to fw o r k f l o w t e c h n o l o g y ，a l s ot h er e f e r e n c em o d e lo fl h ew f m c ( w o r k f l o wm a n a g e m e n tc o a l i t i o n ) t h e nl h ep a p e rr m k eac o n c l u s i o mo nd i f f e r e n tk i n d so fm o d e l i n gm e t h o do fp r o c e s s ， a n dg i v et h ec h a l l e n g e sa n dc h a n c e sw ef a c e di nt h ew o r k f l o wm o d e l i n gf i e l d s b e f o r ed i s c u s s i n gt h em i i l i i 玛m e t e d ，l h ep a p e rd e s e r t ss o m et e c h n o l o g ya n d l i a e o r yr e l a t e dt op r o c e s sm i n i n g ，i n c l u d i n ga l g e b r ae x p r e s so fb ga n dd e f i ni t i o na i 】d p r o p e r t yo fp e t r in e ta n dw o r k f l o wn e t , c r e a t i n g 曲r m p p i n gr e l a t i o n s h i pb e t w e e n p e t r in e ta n dw 硎( f l o wn e t a f t e rt h a t , i tc o l r e sf o rt 1 ep a p e rt od i s c u s st h em o s tc h a l l e n g e so fi b i sa r t i c l e 一 n o n - s t r u c t u r a lp r o c e s sm i n i n g ，e s p e c i a l l yn o n - f r e ec h o i c e i ti n c l u d e st w os e c t i o n s ： p r o c e s sm i n i n ga l g o r i t h ma n di m p r o v e m e n to fp r o c e s sm i n i n ga l g o r i t h m i nt h ef i r s t s e c t i o n , an o wp r o c e s sm i n i n ga l g o r i t h mb a s e do nb g si sb r o u g h tu p ，a n dl h e i m p l e m e n tw i t hj a v af o r 恤a l g o r i t h mi sg i v e r tt h ea l g o r i t h mh a s 咖s t e p s f i r s t l y , a c c o r d i n gt ol t a es e q u e n c eo ft a s k si nl o g s ，t h ec o n n e c t i o na m o n g t a s k so fl h ep r o c e s s i s i d e n t i f i e d , r e s u l t i n gi nas t r u c t u r eo ft h ep r o c e s sg r a p ks e c o n d l y , f i l e r e l a t i o m i n c l u d i n gs e q u e n c e ，c h o i c e ，p a r a l l e la n dc y c l es h o u l db ec o n f i r m e db ya n a l y z i n g 位 p r o c e s sl o g s i nt h es e c o n ds e c t i o n , w ei m p r o v et h ea l g o r i t h mt or e a l i ml l 硷m i n i n go f n o n - f r e ec h o i c es l r u c t u r e t h eb a s i ci d e ai st h a tv v eu s et h e “d e f a u l te x i s t ”i d e a ，f o ra l l i i 山东大学硕士学位论文 t a s k su h a td on o ta d j a c e n ti ne v e r yt r a c ko fb g s ，t h ep o s s i b i l i t yf f l a tt h e y a r el i n k e d e x i s t s t h e n , a c c o r d i n gt o 惋a n a l y s i so fl o g s ，w ee l i m i n a t el h et a s k st h a ta r e i m p o s s i b l et ob el i n k e d , a n dd e t e r m i n el h ec h o i c el i n e u s i n go u rm i n i n ga l g o r i t h m ，w ec a ng e tar e a s o m b l ea n ds e c u r i t yo fm o d a l h lt h ee n d , w eg e te n o u g hb gt h r o u g hr u n n i n g1 l eb g _ p r od u c ep r o g r a m ，a n du s e 廿h e s eb gi no u rn e wa l g o r i t h m t h r o u g ht h ea n a l y s e so ft h ee x p e r i m e n tr e s u l t s ，w e l e a r n e d1 】a to u rn e wa l g o r i t h mh a sa no b v i o u sa d v a n t a g ei ng e t t i n gl h er e a s o m b l e ， s e c u r i t ya n du n d e r s t a n d a b l em o d a l k e yw o r d s ：p r o c e s sm i n i n g ；e v e n t l o g ；n o n - f l e ec h o i c e ；w f _ n e t ；p e l r in e t i i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：霉主耋 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：至筝呈一导师签名埤日 山东大学硕士学位论文 第1 章绪论 随着工作流技术的发展和工作流管理系统功能的完善，对工作流技术的研究 也正在向更深层次发展。工作流技术的研究目前有两个方向【l 】：一是工作流管理 系统实现理论的研究，即针对工作流模型和语义的形式化表示方法、工作流模型 的验证与分析等工作；另一方向是探讨如何利用先进的技术来提高工作流管理系 统的性能，这方面的研究方向主要有：模型仿真技术、运行时的监控与事务处理、 异常处理和错误恢复、企业业务系统的集成、流程运行数据挖掘等。本文研究的 主要内容是属于后者中的流程运行数据挖掘。 概括地说，流程挖掘就是：假设日志中记录了流程实例的实际活动执行次序， 我们根据日志中记录的这些信息，来重构出一个工作流模型，并使得日志中记录 的任一实例都符合这个工作流模型中的一个轨迹 2 1 。本文就是试图寻求一种从流 程日志中挖掘工作流模型的方法。 1 1 课题提出的背景和意义 在最近的十年中，工作流管理的概念和技术已经广泛应用到企业信息系统 中。工作流管理系统如s t a f f w a r e ，i b mm q s e r i e s ，c o s a ，等都有为结构化业务 流程给出通用建模和定制的能力 2 k 6 。通过实施图形化的流程定义，即描述典型 案例的生命周期模型，用户能够配置这些系统以支持业务流程。除了纯粹的工作 流系统，许多其他的软件系统也采取了工作流技术。比如企业资源管理规划( e r p ) 系统，像s a p ，p e o p l e s o f t ，b a a n 和o r a c l e ，客户关系管理系统( c r m ) 软件， 供应链管理( s c m ) 系统，b 2 b 应用等等，都嵌入了工作流技术旧。 尽管许多系统给予了承诺，但当真正应用工作流技术时仍会遇到许多的问 题。一个问题是这些系统都需要工作流的设计，即设计器需要建立详细的描述工 作路由的精确模型。工作流建模绝不是一件简单的工作：它需要深厚的工作流知 识和与操作人员详细和深入的交流。另一个问题是为存在的流程建模往往受主观 的影响，比如模型常被标准化成为应该做什么而没有真实的描述实际的流程。结 果，创建的模型往往变得非常主观【2 】。 一种更客观的建模方法是使用与实际发生的事件相关联的数据( 注意到流程 第l 页 山东大学硕士学位论文 挖掘不受主观和惯性思维的影响) ，这就是基于日志的流程挖掘技术。流程日志 的作用是相当大的，它真实地记录了工作流管理系统的运行情况，基于日志的建 模比事前仿真在某些方面更有说服力。 流程挖掘的另一个重要意义在于，通常在理想的情况下，描述业务流程的工 作流模型总是被预先用建模工具加以定义，然后部署到工作流引擎之上加以执 行；当业务规则发生变化的时候，重新设计工作流模型。但是在某些情况下，可 能原有的工作流模型不存在或者某些局部分支丢失，存在的只是业务执行过程中 留下了的大量的执行实例和产生的轨迹。这时使用日志进行挖掘来重建工作流模 型，便是一个快捷有效的方法。另外流程挖掘可用于做d e l t a 分析，即将挖掘 出来的流程模型和原先部署在引擎之上的流程模型进行比较，分析原有的模型中 存在哪些问题，以便进行改进。流程挖掘导致一个“运行后一流程模型可用来与 “运行前 流程模型进行比较。 流程挖掘这个题目与业务流程重组( b p r ) ，业务智能( b i ) ，业务流程分析 ( b p a ) ，持续流程改进( c p i ) 和知识管理( 1 ( m ) 相关联。流程挖掘可以被看作 b i ，b p a 和脚趋势的一部分。而且，流程挖掘可以被看作b p r 和c p i 活动的输入。 应该注意的是流程挖掘被用在b p r 上比c p i 更适合。回想b p r 元素的一个基本特 征是它很激进并且不受目前状况的限制。也应注意到流程挖掘不是一个重新设计 流程的工具。它的目标是获得流程真正完成的任务。尽管流程挖掘不是设计流程 的工具，但对已存在的流程进行深入理解和掌握是对重新设计流程非常重要的。 我们认为有必要在流程挖掘方面进行我们的研究课题，提出可行的解决办法。其 中结构化挖掘方法就是我们的研究成果之一，它很好的解决了从日志中发掘出合 理、安全、容易理解的工作流模型。 1 2 国内外研究进展情况 流程挖掘是b p m ( b u s i n e s sp r o c e s sm a n a g e m e n t ) 【6 】的一部分，其思想直到 最近才被提出来。在这方面的研究有代表性的有：从流程日志中挖掘出工作流模 型【3 6 】：通过对工作流执行历史数据进行分析来确定工作流模型参数及系统瓶颈 【3 7 】；通过数据仓库和联机分析处理技术的工作流执行数据分析郾】等。c o o k 和 w o l f 在软件工程流程领域已经研究了相关问题。在 1 5 中他们描述了流程发现 第2 页 山东大学硕士学位论文 的三种方法：一种是使用神经网络，一种是使用纯数学方法，一种是m a r k o v i a n 方法。纯数学方法建立了一个有限状态机( f s m ) ，m a r k o v i a n 方法使用算法与统 计方法的混合，能够处理干扰。c o o k 和w o l f 扩展了他们的工作到并行流程。他 们提交了指定的测量项( 事件类型读数，周期，因果关系) 并用这些测量项从事 件流中发现方法。然而，他们没有提供一种生成精确流程的模型网。c o o k 和w o l f 提供了一种测量方法对流程模型和实际行为进行测量。将流程挖掘技术用到工作 流管理系统中的想法首先是在 11 中见到。已经有很多学者在这一领域做了研究 工作，例如a g r a w a l 、g u n o p u l o s 和l e y m a n n ，h e r b s t 和k a r a g i a n n is ， 以及g r e c o 、g u z z o 等人。随着工作流模型理论的发展，因为p e t r i 网具有 比较严格的数学理论基础，有利于工作流模型的形式化验证和分析，所以越来越 趋向于用p e t r i 网的理论来描述工作流。这方面的研究主要有，针对工作流模 型中“非唯一任务名问题，即多个模块可能包含同一个任务，j h e r b s t 等人 提出了归纳挖掘法，包括归纳和转换两个步骤，并基于此理论开发了i n w o l v e 挖 掘工具；g s c h i m m 等人研究了基于块结构的工作流挖掘，该方法将挖掘出的工 作流模型看作一棵树，其叶子是任务，结点是操作符，并相应开发了p r o c e s s m i n e r 工具。但目前已有的针对p e t r i 网模型的流程挖掘算法主要还是a a l s t 等人提出的q 算法以及对该算法的一些扩展。这类算法主要根据引擎日志中记 录的活动间发生的顺序关系来进行挖掘工作。但是目前针对p e t r i 网模型的算 法还有一些问题不能够很好的解决，主要是工作流流程模型中的某些网结构，算 法不能够正确的进行挖掘，例如重复活动、非可见活动、循环、隐式库所和同步 汇聚等，而这些结构在业务流程模型中是常见的，另外，算法得出的工作流模型 往往非常难以理解，特别是在日志相对复杂的情况下。 1 。3 本文主要研究内容和特色 1 论文研究的主要内容 本文主要研究了如何从日志中挖掘工作流模型的方法。文章首先对工作流挖 掘的对象一一日志进行了定义，这儿用到的日志是一种事务型日志，即将流程中 的每项任务作为一种原子事件来看待。因此，文章探讨了如何对日志进行预处理 和定义的相关问题，并对事务型日志的相关属性进行了研究。 第3 页 山东大学硕士学位论文 之后，文章讨论了最具有挑战性的问题一非结构化流程挖掘，主要是非自由 选择结构的挖掘。其中分为三个部分：日志预处理，流程挖掘和合理性验证。在 第一部分，讨论了如何完成日志的过滤和噪音去除。第二部分是挖掘工作的核心。 文章给出了一种基于日志的新的流程挖掘算法，给出了算法的j a v a 实现。这种 算法的基本思想是，首先根据日志中任务间的先后顺序，确定流程中各任务间的 连线，从而得到流程图的结构，进一步分析流程日志确定顺序，选择，并行，循 环等关系。然后，在此算法的基础上进行改进，实现了非自由选择结构的挖掘。 其基本思想是，采用默认存在的思想，即对于日志的每一条执行轨迹中所有的不 相邻任务，其相连的可能性都看成是存在的，然后根据对日志的分析排除不可能 的连线，确定选择线。该种方法得到的工作流网是合理的，安全的，并且是容易 理解的。 最后，我们用j a v a 实现了一个基于日志的流程挖掘软件系统，并通过运行 一系列流程实例，演示了该算法的运行过程。同时通过生成和运行一定数量的实 验数据，对该算法的挖掘质量进行了检验分析，证明该算法在挖掘方面具有明显 优势。 2 研究的主要特色， ( 1 ) 基于事件型日志的工作流挖掘观念，提高工作流建模速度和准确性。 ( 2 ) 采用“默认不存在”的思想，通过寻找并行任务对，分别确定流程图 结构和任务间关系的方法来实现流程挖掘。 ( 3 ) 非结构化流程挖掘是流程挖掘的难点。本文巧妙地同时运用“默认不 存在和“默认存在的思想，解决了简单的包含非自由选择结构的流程挖掘。 ( 4 ) 在提出算法的基础上，我们用j a v a 语言实现了算法，进一步证明了算 法的可用性和高效性。 第4 页 山东大学硕士学位论文 第2 章工作流技术介绍 本章对当前工作流技术进行简要介绍的基础上，提出工作流领域面临的机遇 和挑战，指出流程挖掘在工作流研究新领域bpm 中的地位。 2 1 工作流的定义 1 9 9 3 年，工作流管理联盟( w o r k f l o wm a n a g e m e n tc o a l i t i o n ，w f m c ) 的成 立标志着工作流技术进入了一个相对成熟的阶段。它是一个由很多知名学术研究 机构和软件供应商组成的非盈利性组织，一直致力于工作流技术的推广和标准 化，它给出的工作流的定义是【3 】；工作流是一类能够完全或者部分自动执行的经 营流程，它根据一系列流程规则，使得文档、信息或任务能够在不同的执行者之 间进行传递与执行。此定义即说明了，工作流管理系统是一个软件系统，它完成 工作流的定义和管理，并按照在计算机中预先定义好的工作流逻辑推进工作流实 例的执行。 2 2 工作流参考模型 为了能够统一工作流技术研究和开发领域的相关工作，从而更好地支持企业 经营流程建模、分析和实施，以适应世界市场的多元化趋势，w 伽c 提出了图 2 1 所示的工作流参考模型【3 】。该模型实现了工作流技术的标准化和开放性，支 持异构工作流管理系统与产品之间的互操作，并且使得其它的应用可以使用该结 构和定义好的通用a p i ( 应用编程接口) 访问不同的工作流管理系统提供的服务， 实现快速高效的集成。该参考模型定义了一些组件( c o m p o n e n t ) ，包括流程定 义工具、工作流机、工作流管理工具、工作流客户应用和工作流直接调用的应用 以及这些组件之间通信的5 类接口( i n t e r f a c e ) 4 1 。 第5 页 山东大学硕士学位论文 接口l伞 2 3 工作流建模方法 图2 - iw f m c 的工作流参考模型 工作流模型是对工作流的抽象表示，也就是对经营流程的抽象表示。在工作 流系统正式运行前，必须先对系统进行建模。这个流程是将实际业务的流程规则 及相关资源表示成计算机能够执行的形式。工作流建模主要包括流程建模、功能 建模、资源建模、组织建模和信息建模【s 田。其中最主要的是流程建模，它是整 个建模工作的核心，其它模型都是依附于它。下面着重介绍一下流程建模的内容。 目前流程建模的方法很多，文献【7 】将各种流程建模方法分为基于会话的和 基于活动的两类。文献【8 】进一步将其分为4 类：基于任务流的、基于状态转换 的、基于关系捕获的和基于通信的方法。从表现形式来看，流程模型大致可以分 为非形式化和形式化方法两类。前者一般基于图的形式，容易读懂、含义丰富， 然而缺乏分析方法，包括活动网络图【9 】【l o 】、e p c 模型【1 1 】、语言行为模型 1 2 1； 后者包括p e t r i 网【1 3 】【1 4 】【”】、流程代数1 6 1 1 1 7 1 1 8 等方法，能够精确地刻画流程逻辑， 但表达能力不够丰富，而且对用户的建模能力要求高。目前工作流产品一般使用 网络图模型进行建模，而流程分析方面的研究工作往往基于p e t r i 网、流程代数 等数学工具。单独使用图模型或者形式化方法都无法解决工作流系统中的流程建 模、执行和分析的问题，目前的研究的热点是一方面为基于图的流程模型寻找理 第6 页 山东大学硕士学位论文 论基础，另一方面从数学模型出发，力图丰富其表现形式。本文研究的工作流模 型便是以p e t r i 网为基础的流程建模。 2 4 工作流模型验证与分析 性能分析的目的是评价流程是否能够满足预定的性能要求指标，包括吞吐 量、服务时间、资源利用率等。性能分析的方法主要有三种 2 0 1 2 1 1 ，分别是基于 仿真的，基于模型分析和基于历史数据的。 工作流模型仿真利用离散事件驱动的仿真引擎模拟工作流程中各项活动的 执行，在执行流程中记录相关数据( 如时间、成本和利用率等) ，进而通过这些 数据来分析业务流程的各项性能。目前工作流仿真可以使用专为业务流程仿真设 计的工具【2 2 1 ，基于p e t r i 网的仿真工具瞄，冽，或离散事件动态系统仿真工具【2 5 】。 目前对模型的性能分析主要利用各种随机p e t r i 网【2 6 】，根据系统的状态变化 流程建立对应的同构连续时间马尔可夫链( c o n t i n u o u st i m em a r k o vc h a i n ) 模型 或排队论模型，进而，基于马尔可夫流程的稳态概率或排队论的相关理论求解系 统的性能参数【27 2 8 】。相关研究还基于随机p e t r i 网的工作流系统的顺序、并行、 选择、循环四种基本模型，并推导了这四种基本模型下的工作流性能参数，给出 定量分析工作流系统性能的通用方法。 基于历史数据的性能分析属于工作流数据挖掘的范畴，其基本思想是将数据 挖掘和数据仓库的方法用于对工作流运行历史数据的分析，用于流程模型的重 构，流程知识的挖掘等。本研究组在现有基于历史数据的事后分析的基础上，利 用e c a 规则，通过构建实时流程仓库对企业业务流程性能管理体系进行了重新 构架，使得企业能对实时性能进行快速准确的闭环控制。基于p e t r i 网的理论研 究目前已非常成熟，本文研究的工作流网模型许多都是以p e t r i 理论为基础的。 2 5b p m 在证券业中的应用研究 国际著名评估机构a i r 断言，业务流程管理( bpm ) 已经成为今后企业 面临的重点课题之一。在中国，企业信息化的先锋联想与海尔都在进行公司层面 的核心业务流程的梳理和再造。作为拥有高度网络化和自动化交易系统的证券 业，如何在多系统、异构的网络交易环境下解决交易数据的高度分散性、系统间 第7 页 山东大学硕士学位论文 的兼容性、以及各业务部门间的活动相互割裂、缺乏横向协同、流程被固化在系 统中等一系列问题，如何构建一个既能保护现有信息资源投资成果，又能实现在 现有数据分析基础之上的业务流程高效管理和执行，bpm 将是证券业信息化之 后的一个选择。 从系统层次上讲，bpm 是建立在应用层之上的业务逻辑管理系统，它通过 对业务流程进行建模，并迅速应用到实际业务中。证券业的流程是一个高度依赖 业务综合数据的流程，在其中的每一步都可能涉及对数据的综合查询和对各种业 务系统的调用。在这种环境下的bpm 系统，必然是建立在数据仓库及各种应用 中间件之上的业务流程管理系统。同时，企业为适应快速的市场变化，业务模式 的不确定性很强，对工作流程的变更比较频繁，因此需要不断地对流程的性能进 行分析，对流程进行调整和改进工作。调整和改进之后的流程被重新应用到工作 中并进一步接受检验，这是一个循环的流程。图2 - 2 是bpm 实施的总体框架。 图2 - 2 证券业bpm 实施的总体框架 随着工作流技术应用不断的普及，以及工作流相关理论研究的长足进步，如 图论、数据库、人工智能、数据挖掘、分布式系统等多个领域的研究内容的日益 丰富，工作流的相关研究也在不断深入。文献 1 将工作流研究问题分为两个方 面的内容：一是为工作流技术的发展解决理论上存在的问题，探讨工作流模型和 语义的形式化表示方法等；二是从工作流技术实现的角度探讨利用先进的技术提 第8 页 山东大学硕士学位论文 皇! 曼! ! ! ! ! ! ! ! ! ! 曼! 曼i i i ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 苎! ! 皇 高工作流管理系统的性能和可靠性。文献 1 9 将工作流研究问题分为三个方面： 技术方面，管理和组织方面，市场、经济和社会方面。另外，文献 1 9 还将技术 方面的问题进一步分为构建时和运行时两类。下面对以上文献中提及的理论研究 方向做一些介绍。 第9 页 山东大学硕士学位论文 第3 章流程挖掘相关技术的数学定义 在本章中，我们将围绕流程挖掘概念提出相关的定义和定理，主要是流程挖 掘概念、流程日志的数学表示、流程模型的p e t r i 网表示及结构化工作流网概念， 并给出相关的数学描述，为后面流程挖掘算法的提出打下基础。 3 1 流程挖掘概念的引入 在提出流程挖掘概念之前，我们先来比较一下流程挖掘和传统的工作流设计 和制作方式的不同，请参照图3 1 的工作流生命周期模型。工作流生命周期由四 个阶段组成：( a ) 工作流设计( b ) 工作流配置( c ) 工作流执行和( d ) 工 作流诊断。在传统的方式中，设计阶段是建立一个工作流模型。这通常通过业务 磋商来实现，通过提高手头上的业务流程管理的思想来驱动。如果设计完成，工 作流系统( 其他系统也叫“流程控件”) 按指定的要求进行配置。在配置阶段， 必须处理好正在使用的工作流管理系统的限制和特殊性。在执行阶段，工作流实 例按照设计阶段的要求和配置阶段实现的配置被工作流系统处理。基于运行的工 作流，就可以收集诊断信息，这些信息在诊断阶段被用来分析诊断。诊断阶段又 为设计阶段提供输入，由此完成一个工作流生命周期 2 0 x 2 1 。在传统的方法中将 重点放在设计和配置阶段，几乎没有组织来系统的收集运行数据进行分析，以便 为重新设计提供输入( 即诊断阶段经常被放弃) 【2 2 】。 流程挖掘则是将流程反转，收集运行数据以支持工作流设计和分析t 2 3 】。应引 起注意的是大多数情况下，在一个工作流系统建立起来之前，流程就实际上已经 存在了。也应注意到大多数信息系统中事务数据是被记载下来的( 如e r p 系统 的事务日志) 。在运行期间收集的信息能够被用来创建一个模型来解释记录的事 件。这个模型既可用于诊断阶段也可用设计或重设计阶段。因此，流程挖掘就是 指从一个真实执行的流程日志中挖掘出结构化的流程模型( 描述) ，以用于工作 流设计、重设计或诊断阶段。因为这些方法凝聚在案例驱动的流程中，这些流程 被当前的工作流系统所支持，因此我们也称作工作流挖掘。 第l o 页 山东大学硕士学位论文 r ”侍境方法 图3 1 流程挖掘在工作流生命周期图中的表示 3 。2 流程挖掘的对象流程日志 前面提到了，流程挖掘是在一个真实执行的流程日志中进行的，流程日志都 有哪些内容呢? 流程日志记录了工作流系统所执行的所有流程的真实轨迹，比 如：人员的登入登出时刻、任务的开始和完成时刻、任务相关数据的输入输出、 当前人员和物资的情况等等。可以说，流程日志综合了包括流程、组织、资源、 信息等大量工作流运行状态数据( 包括历史数据和实时数据) ，从而使得日志成 为工作流性能分析的很好的数据源。基于流程日志库进行相关分析成为有别于仿 真的企业业务分析和诊断，它是一种事后的诊断与优化 2 4 1 2 5 。 我们假设流程日志能够记录以下类型的事件：( i ) 每个事件指向一个任务( 任 务是流程中定义好的步骤) ，虹) 每个事件指向一个实例( 即工作流实例) ，( i i i ) 事件是有序的。任何使用事务系统的信息系统如e r p ，c i u 讧或工作流管理系统 都将以各种形式给出这些信息。需要注意的是由于我们现在还没有得到某一流程 的工作流管理系统，我们作的唯一的假设是我们现在可以收集流程日志。这些流 程日志将被用来创建流程。 流程日志有以下三个特点： 一是流程日志可能会很大，比如，如果有选择和并行路由，流程日志不可能 包含所有的可能路径。如果有1 0 个任务并行，则可能的路径应有l o ! = 3 6 2 8 8 0 0 如果将这些路径都体现在日志中是不现实的。而且，一些路径是不太可能发生的。 二是流程日志中可能包含干扰，也就是说一部分日志是不完整的，不正确的， 或者导致异常中止。事件由于人工或技术问题可能记录错误。因为任务由手工操 第1 l 页 山东大学硕士学位论文 作或者被另一个系统和组织控制而导致丢失的事件常常发生。 三是日志中记录的信息是多种多样的，如事件类型、事件发生时间、事件的 属性等。要想充分的利用所有的信息是流程挖掘面临的一个重要的挑战。 3 3 流程日志的数学表示 本文中，我们将研究的日志假设成：( i ) 每一个任务都是一个原子的事件， 省去时间、日期和事件等类型因素，( ) 任务是按发生的顺序排列的，( ) 不 考虑组织机构。我们定义流程日志如下： 定义3 1( 流程路径，流程日志) 设t 是任务的集合，o p 是一个流程 路径，w p ( p ) 是流程日志。其中p ( t ) 是r 的幂集，即w p 【2 】 表3 1 中日志记录包含了5 个案例的信息( 即工作流实例) ，日志显示了在 其中的4 个案例中，包含a ，b ，c 和d 四个任务。第5 个案例只有三个任务执 行：任务a ，e 和d 。每个案例由执行a 开始，执行d 结束。如果b 执行，则 任务c 就被执行。然而，一些隋况下c 在b 前执行。基于表3 1 所显示的信息 并假设日志相对完整的( 即假设案例有代表性且是一个关于所有能被观测到的执 行序列的一个最大子集) ，我们可以导出图3 2 所示的流程模型。这个流程用p e t r i 网表示。p e 血 i 网中任务a 开始，结束于任务d 。这些任务用变迁表示。执行完 a 后面临着并行执行b 和c ，或只执行任务e ，为了并行执行任务b 和c ，a n d - s p l i c t 和a n d - j o i n 被加到模型中。在本日志中，如果两个任务被按任意顺序执行， 我们就假设两个任务是并行任务。通过区分任务的开始时间和结束时间，我f 门能 够精确的确定并行事件。 在表3 1 中案例l 的工作流路径是a b c d 。表3 1 对应的流程日志是 a b c d ， a c b d ，a e d ) ，在此我们将相同的案例进行了合并。很显然一个案例的一致性 和属性是与流程挖掘有关的，然而，为了本文的理论结果，我f 门可以作一些抽象。 同样的原因我们从工作流路径的频率中作一些抽象。在表3 1 中工作流路径 a b c d 出现了两次( 案例1 和案例3 ) ，工作流路径a c b d 也出现了两次( 案例2 和案例4 ) ，工作流路径a e d ( 案例5 ) 只出现了一次。流程日志 a b c d ，a c b d ， a e d ) 中没有反映工作流路径的频率。在处理流程日志中的噪音时，频率是一个 非常重要的信息。但目前我们暂时不考虑噪音。因此，这些抽象有利于使符号简 第1 2 页 山东大学硕士学位论文 单化。 c a b oi d e n 七i f i e rt a g ki 应e n 乞i f i e r c & g e1t a 8 ka c a g e2 屯a 8 ka c a g e3t & 8 k 矗 c a 8 母3 t a 8 k8 c ；e l l s ；e量 乞a 8 kb c a l 8 e1屯& 8 kc c a s e2t & 8 kc c a 8 e4 t & 8 ka c a 8 e2 屯a b kb c a s e2乞哉8 kd c a 8 e5乞铋k c 警u s e4 乞a b kc c a s eit a 8 kl c a l 8 e3屯a j 量kc c a 8 e3乞a b kd c a 母e4t 毳8 kb c a 8 e5乞a s ke c a b e5乞a b kl c a j 墨e4乞a 滔kd 表3 1 一个流程日志实例 图3 - 2 与流程日志相对应的流程模型 表3 1 包含了我们假设的任务的最小信息。在许多应用中，流程日志包含每 个事件的时间邮戳，这个信息可被用来提取额外的因果信息。另外，个典型的 日志也包括事件类型的信息，如一个启动事件( 一个人从工作列表中选择任务) ， 一个完成事件( 一项任务的完成) ，一个撤销事件( 一个安排好的任务被取消) 等等。另外，我们也对案例属性之间的关系和实际被案例执行的路由感兴趣。 在介绍了一些基本的概念后，我f 门回到本文的主题：流程挖掘。流程挖掘的 目的是从流程日志中找到一个工作流模型( 本文是一个w f 网) 。为了从流程 日志中发现工作流，日志应该进行因果依赖分析，比如，一个任务总是在另一个 任务完成后出现，则二者之间可能存在因果关系。为了分析这种关系，我f 】给出 第1 3 页 山东大学硕士学位论文 下面的流程日志的一些重要定义和属性。 定义3 2 ( 基于日志的次序关系) 设w 是任务集合t 上的流程e l 志，即 w p ( 1 峰) ，流程日志是一个四元组w _ ( t w ，o w 如，t 们) ，t w = t - i l i ，t w o ，t 1 ，q ，其 中t _ l r i 是流程日志的起始节点，t w 。是流程日志的结束节点，o w = w ，如# w ，1 1 w 是元素之间的关系。1 3 1 设a , b t ： ( 1 ) a wb 当且仅当存在一个路径o = t t t 2 t 3 t n 1 ，i e 1 , 2 ，n - 2 ，满足o w 且t i = a ，t i + l = b ( 2 ) a 、b 当且仅当a wb 且b 牛w a ( 3 ) a # wb 当且仅当a 牛。b 且b 牛wa ( 4 ) a1 1 w b 当且仅当a wb 且b w a 考虑表3 - 1 中所示的流程日志w = a b c d ，a c b d ，a e d 。关系 w 描述了 哪些是顺序关系( 一个任务跟在另一个任务后面) 。很显然，a 。b ，a wc ， a 。e ，b wc ，b wd ，c w d ，c wb ，e wd 。从 w 的关系中我们能够 计算出流程日志w 的、关系，即因果( 直接) 关系：a 飞b ，a 飞c ，a 飞e b - wd ，c - wd ，e _ wd 。注意b 与c 之间不是因果关系，因为c 。b 关系| 1 w 表示潜在的并行关系。在w 中，任务b 和c 表现出并行关系，o p b l l wc ， c 1 1 w b 。如果两个任务以任意顺序相互连接并存，他们非常可能是并行关系。关 系# 。表示一对变迁从不相互直接连接。这表示他们很可能没有因果关系和并行 关系。 属性3 1 设w 是任务集合t 上的流程日志，任意a , b e t ：a - b 或者b 飞a 或者a # wb 或者a0 wb 。此外，_ w ，飞一，# w 和1 1 w 互斥且分割t x t 。( 其中 飞1 是- w 的对称关系，即一w 。1 = ( y ，x ) t 田h w y 尸 这一属性很容易被证明。由定义可知：飞= ( w 、 w 。1 ) ，飞。1 = ( w _ 1 w ) ，# w = 仃1 ) ( wu w 1 ) ，| | w = ( wt 3 w 。1 ) 因此，t t u _ w du# wu如果不会引起混乱的话，今后将w 隐掉。 为了简化日志和顺序，我们介绍下面附加的符号： 定义3 3 ( ，f i r s t , l a s t )设a 是一个集合，a e 八o = a l a 2 a n e a * 是a 上的长度为n 的序列，、f i r s t 、1 a s t 定义如下：a e o 当且仅当a efa 1 ，a 2 a n 第1 4 页 山东大学硕士学位论文 丘酬。户a 1 ，如果l 仑l 且 l a s t ( o 户a n 如果n _ l t 3 为了阐明流程挖掘算法的质量我们需要假设日志的完整性。作为一个复杂的 流程，十几个路径往往不足以发掘出真实的流程。关系飞，飞。1 ，# w 和 i l w 将为任何形式的流程挖掘算法提供重要的信息。因为这些关系都是从 w 中派 生出来的，我们假设日志是完整的并遵守这些关系。 定义