（计算机软件与理论专业论文）基于遗传方法的流程挖掘技术的研究.pdf

山东大学硕士学位论文 摘要 工作流是一种反映业务流程的计算机化的模型，是为了在先进计算机环境 支持下实现经营过程集成与经营过程自动化而建立的、可由工作流管理系统 执行的业务模型。工作流的生命周期包括工作流设计、工作流配置、工作流 执行、工作流诊断四个阶段。工作流挖掘技术不是一个工作流设计的工具， 但它对充分理解现有业务过程执行情况有很大的帮助。工作流挖掘的目标 是：倒转过程，收集和利用运行数据，从而支持工作流设计和分析。 本文首先介绍了工作流技术最新的发展状况，以及w f m c 的工作流参考模 型，然后文章总结了当前工作流建模的主要方法，提出了工作流建模领域存 在的机遇和挑战。在详细讨论流程挖掘方法前，文章对与挖掘有关的技术和 理论进行了描述，包括日志的数学表达模型，p e t r i 网和工作流网的相关 属性，p e t r i 网到工作流网的映射关系等。然后文章描述目前流程挖掘领 域较为完善的d 一算法，指出了a 一算法在挖掘某些结构上的不足和限制。 本文针对现有的流程挖掘算法中存在的不足和缺陷，以及鉴于遗传算法具有 自适应性、全局优化性、隐含并行性和形式简单明了等特点，提出了利用遗 传方法进行流程挖掘。在介绍使用遗传方法去挖掘流程模型前，我们定义了： 内部描述形式、适应度函数、遗传算子。内部描述形式定义了遗传算法的搜 索空间，能够支持在流程模型中除了重复任务所有常见的结构( 包括顺序， 并行，选择，循环，非自由选择，不可见任务) ；适应度函数能够根据事件 日志，正确的评价已创建的流程模型( 即遗传个体) 的适应度；遗传算子确 保覆盖内部描述形式定义的全局搜索空间内的所有的点。它们为将要提出的 遗传算法做好了理论上的准备。 最后我们提出了基于遗传算法的流程挖掘，该算法是从包含若干遗传个体 的初始种群开始的。每个遗传个体对应一个流程模型，并且用适应度函数去 记录它的优劣，即能够评价遗传个体重现事件日志的能力。通过适应度函数 来反映遗传个体与事件日志的拟合程度，同时利用遗传算子重组遗传个体以 山东大学硕士学位论文 产生新的流程模型。 最后，通过运行模拟日志获得足够的实验数据，对该算法的挖掘质量进行 了检验分析，证明该算法在流程挖掘方面具有明显优势，有效解决了d 一算 法在挖掘某些结构上的不足和限制。 关键字：流程挖掘；事件日志；遗传算法；因果矩阵；适应度函数；遗传算子 i i 山东大学硕士学位论文 a b s t r a c t w o r k f l o wa r ear e f l e c t i o no ft h ec o m p u t e r i z e dm o d e l ，a r ea ta l la d v a n c e dc o m p u t e r e n v i r o n m e n ti no r d e rt os u p p o r tt h ei m p l e m e n t a t i o no fb u s i n e s sp r o c e s si n t e g r a t i o n a n db u s i n e s sp r o c e s sa u t o m a t i o na n dt h es e tu pb yt h ew o r k f l o wm a n a g e m e n ts y s t e m t oi m p l e m e n tt h eb u s i n e s sm o d e l t h ew o r k f l o wl i f ec y c l ec o 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 x e c u t i o na n dw o r k f l o w d i a g n o s i s t h ep r o c e s sm i n i n gi sn o tj u s tat o o lo fw o r k f l o wd e s i g n ，b u ti ti sv e r y u 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 t h eg o a lo fp r o c e s sm i n i n gi st o r 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 n t i m et os u p p o r tw o r k f l o wd e s i g na n d a n a l y s i s t h i sp a p e rf i r s t l yi n t r o d u c e dt h el a t e s tw o r k f l o wt e c h n o l o g yd e v e l o p m e n t ，a sw e l l a st h ew f m cw o r k f l o wr e f e r e n c em o d e l ，a n dt h e ni ts u m m a r i z e st h em a i nw o r k f l o w m o d e l i n gm e t h o d , o p p o r t u n i t i e sa n dc h a l l e n g e se x i s t i n gi nt h ef i e l do fw o r k f l o w m o d e l i n g b e f o r ed i s c u s s i n gt h em i n i n gm e t h o d ，t h ep a p e rd e s c r i b e ss o m et e c h n o l o g y a n dt h 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 fl o ga n dd e f i n i t i o n a n dp 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 gt h em a p p i n gr e l a t i o n s h i p b e t w e e np e t r in e ta n dw o r k f l o wn e t p a p e rt h e nd e s c r i b e st h ec u r r e n tp r o c e s sm i n i n g f i e l do fr e l a t i v e l yp e r f e c ta a l g o r i t h m , p o i n t i n go u ts h o r t c o m i n g sa n dl i m i t a t i o n so f a - a l g o r i t h mo nt h em i n i n go fs o m es t r u c t u r e s d u et ot h ed e f i c i e n c i e sa n dd r a w b a c ko ft h ee x i s t i n gp r o c e s sm i n i n ga l g o r i t h m ，嬲 w e l la st h ec h a r a c t e r i s t i c so fg e n e t i cm e t h o di n c l u d i n gs e l fa d a p t i v e ，g l o b a l o p t i m i z a t i o n ，t h ei m p l i c i tp a r a l l e l i s ma n dt h ef o r mo fe a s yt ou n d e r s t a n d ， w e i n t r o d u c eg e n e t i cm e t h o dt op r o c e s sm i n i n g b e f o r et h ei n t r o d u c t i o no ft h eg e n e t i c p r o c e s sm i n i n g ，w ed e f i n e ：i n t e r n a lr e p r e s e n t a t i o n ，f i t n e s sm e a s u r ea n dg e n e t i c o p e r a t o r t h ei n t e m a lr e p r e s e n t a t i o nd e f i n e st h es e a r c hs p a c eo fag e n e t i ca l g o r i t h m t h ei n t e m a lr e p r e s e n t a t i o nt h a tw ed e f i n es u p p o r t sa l lt h ep r o b l e m a t i cc o n s t r u c t s ， e x c e p tf o rd u p l i c a t et a s k s t h ef i t n e s sm e a s u r ee v a l u a t e st h eq u a l i t yo fap o i n t ( i n d i v i d u a lo rp r o c e s sm o d e l ) i nt h es e a r c hs p a c ea g a i n s tt h ee v e n tl o g g e n e t i c i i i 山东大学硕士学位论文 o p e r a t o r s e n s u r et h a ta l l p o i n t s i nt h es e a r c h s p a c ed e f i n e db yt h ei n t e m a l r e p r e s e n t a t i o nm a yb er e a c h e dw h e nt h eg e n e t i ca l g o r i t h mr u n s t h ea b o v et h r e e d e f i n i t i o n sp r e p a r ef o rt h ef u r t h e r i n t r o d u c t i o no fg e n e f i cp r o c e s sm i n i n g f i n a l l yw ep r o p o s et h ep r o c e s sm i n i n gb a s e do ng e n e t i ca l g o r i t h m t h i sa l g o r i t h m s t a r t sw i ma ni n i t i a lp o p u l a t i o no fi n d i v i d u a l s e v e r yi n d i v i d u a li sa s s i g n e daf i t n e s s m e a s u r et oi n d i c a t ei t sq u a l i t y a ni n d i v i d u a li sap o s s i b l ep r o c e s sm o d e la n dt h e f i t n e s si sf u n c t i o nt h a te v a l u a t e sh o ww e l la ni n d i v i d u a li sa b l et or e p r o d u c et h e b e h a v i o ri nt h el o g p o p u l a t i o n se v o l v eb ys e l e c t i n gt h ef i t t e s ti n d i v i d u a l sa n d g e n e r a t i n gn e w i n d i v i d u a l su s i n gg e n e t i co p e r a t o r i nt h ee n d ，w eg e ts u f f i c i e n tl o gt h r o u g hr u n n i n gt h el o gp r o d u c ep r o g r a m , a n d u s et h e s el o g si 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 el e a r n e dt h a to u rn e w a l g o r i t h mh a so b v i o u sa d v a n t a g ec o m p a r i n gw i ma - a l g o r i t h m i nt h em i n i n go fs o m es t r u c t u r e s k e y w o r d s ：p r o c e s sm i n i n g ；e v e n tl o g ；g e n e t i ca l g o r i t h m ；c a u s a lm a t r i x ； f i t n e s sm e a s u r e ；g e n e t i co p e r a t o r s i v 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：益塑一。一 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：辑导师签名： 山东大学硕士学位论文 第1 章绪论 随着工作流技术的发展和工作流管理系统功能的完善，对工作流技术的研究 也正在向更深层次发展。工作流技术的研究目前有两个方向【l 】：一是工作流管理 系统实现理论的研究，即针对工作流模型和语义的形式化表示方法、工作流模型 的验证与分析等工作；另一方向是探讨如何利用先进的技术来提高工作流管理系 统的性能，这方面的研究方向主要有：模型仿真技术、运行时的监控与事务处理、 异常处理和错误恢复、企业业务系统的集成、流程运行数据挖掘等。本文研究的 主要内容是属于后者中的流程运行数据挖掘。 概括地说，流程挖掘就是：假设日志中记录了流程实例的实际活动执行次序， 我们根据日志中记录的这些信息，来重构出一个工作流模型，并使得日志中记录 的任一实例都符合这个工作流模型中的一个轨迹【2 】。本文就是试图寻求一种从流 程日志中挖掘工作流模型的方法。 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 ，等都有为结构化业务 流程给出通用建模和定制的能力1 2 1 6 1 。通过实施图形化的流程定义，即描述典型 案例的生命周期模型，用户能够配置这些系统以支持业务流程。除了纯粹的工作 流系统，许多其他的软件系统也采取了工作流技术。比如企业资源管理规划 ( e r p ) 系统，像s a p 、p e o p l e s o f l 和o r a c l e ，客户关系管理系统( c r m ) 软件， 供应链管理( s c m ) 系统，b 2 b 应用等等，都嵌入了工作流技术 6 1 。 尽管许多系统给予了承诺，但当真正应用工作流技术时仍会遇到许多的问 题。一个问题是这些系统都需要工作流的设计，即设计器需要建立详细的描述工 作路由的精确模型。工作流建模绝不是一件简单的工作：它需要深厚的工作流知 识和与操作人员详细和深入的交流。另一个问题是为存在的流程建模往往受主观 的影响，比如模型常被标准化成为应该做什么而没有真实的描述实际的流程。结 果，创建的模型往往变得非常主观 2 1 。 一种更客观的建模方法是使用与实际发生的事件相关联的数据( 注意到流程 山东大学硕士学位论文 挖掘不受主观和惯性思维的影响) ，这就是基于日志的流程挖掘技术。流程日志 的作用是相当大的，它真实地记录了工作流管理系统的运行情况，基于日志的建 模比事前仿真在某些方面更有说服力。 流程挖掘的另一个重要意义在于，通常在理想的情况下，描述业务流程的工 作流模型总是被预先用建模工具加以定义，然后部署到工作流引擎之上加以执 行：当业务规则发生变化的时候，重新设计工作流模型。但是在某些情况下，可 能原有的工作流模型不存在或者某些局部分支丢失，存在的只是业务执行过程中 留下了的大量的执行实例和产生的轨迹。这时使用日志进行挖掘来重建工作流模 型，便是一个快捷有效的方法。另外流程挖掘可用于做d e l t a 分析，即将挖掘 出来的流程模型和原先部署在引擎之上的流程模型进行比较，分析原有的模型中 存在哪些问题，以便进行改进。流程挖掘导致一个“运行后”流程模型可用来与 “运行前 流程模型进行比较。 当前流程挖掘比较完善的主要是仅算法，这种算法以及它的扩展简单易懂， 对于常见特定类型的工作流，该算法可能找到完全正确或行为等价的工作流模 型，但是洳算法主要针对结构化的工作流网，能够成功的挖掘出不包含一步和两 步循环的结构化工作流网，但是对于循环，重复任务，非可见任务和同步汇聚等 结构，而这些结构在业务过程模型中是常见的。此外由于日志中的噪音会影响活 动间的基本关系的推导，因此该算法的鲁棒性也较低。 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 ) 1 6 1 的一部分，其思想直到 最近才被提出来。在这方面的研究有代表性的有：从流程日志中挖掘出工作流模 型【3 6 】；通过对工作流执行历史数据进行分析来确定工作流模型参数及系统瓶颈 【3 7 】；通过数据仓库和联机分析处理技术的工作流执行数据分析1 3 翻等。c o o k 和 w o l f 在软件工程流程领域已经研究了相关问题。在【”1 中他们描述了流程发现的 三种方法：一种是使用神经网络，一种是使用纯数学方法，一种是m a r k o v i 锄方 法。纯数学方法建立了一个有限状态机( f s m ) ，m a r k o v i a n 方法使用算法与统 计方法的混合，能够处理干扰。c o o k 和w o l f 扩展了他们的工作到并行流程。他 们提交了指定的测量项( 事件类型读数，周期，因果关系) 并用这些测量项从事 2 山东大学硕士学位论文 件流中发现方法。然而，他们没有提供一种生成精确流程的模型【6 】。c o o k 和 w o l f 提供了一种测量方法对流程模型和实际行为进行测量。将流程挖掘技术用 到工作流管理系统中的想法首先是在【】中见到。已经有很多学者在这一领域做了 研究工作，例如a g r a w a l 、g t m 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 i s ，以 及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 sm i n e r 工具。 但目前已有的针对p e t r i 网模型的流程挖掘算法主要还是a a l s t 等人提出的哥 算法以及对该算法的一些扩展。这类算法主要根据引擎日志中记录的活动间发生 的顺序关系来进行挖掘工作。但是目前针对p e t r i 网模型的算法还有一些问题不 能够很好的解决，主要是工作流流程模型中的某些结构，算法不能够正确的进行 挖掘，例如重复任务、非可见任务、循环、隐式库所和同步汇聚等，而这些结构 在业务流程模型中是常见的，另外，算法得出的工作流模型往往非常难以理解， 特别是在日志相对复杂的情况下。 目前，虽然在流程挖掘方面做了很多的工作，有的技术可以挖掘不可见任务， 有的可以挖掘重复任务，但是没有一个技术可以一次性的挖掘出全部的结构，而 且由于噪音的存在也会对挖掘结构的正确性产生影响。 1 3 本文研究内容和组织结构 1 3 1 论文研究的内容 本文主要研究了如何从日志中挖掘工作流模型的方法。文章首先对工作流挖 掘的对象日志进行了定义，这儿用到的日志是一种事务型日志，即将流程中 的每项任务作为一种原子事件来看待。因此，文章探讨了如何对日志进行预处理 和定义的相关问题，并对事务型日志的相关属性进行了研究。 之后，文章讨论了基于遗传方法的流程挖掘。其中分为三个部分：内部描述 山东大学硕士学位论文 形式、适应度函数、遗传算子。接着文章给出了基于遗传方法的流程挖掘算法， 其的基本思想是，是从包含若干遗传个体的初始种群开始的。每个遗传个体对应 一个流程模型，并且用适应度函数去记录它的优劣，即能够评价遗传个体重现事 件日志的能力。通过适应度函数来反映遗传个体与事件日志的拟合程度，同时利 用遗传算子重组遗传个体以产生新的流程模型。 最后，我们用j a v a 实现了一个基于遗传方法的流程挖掘系统，并通过运行一系 列流程实例，演示了该算法的运行过程。同时通过生成和运行一定数量的实验数 据，对该算法的挖掘质量进行了检验分析，证明该算法在挖掘方面具有明显优势。 1 3 2 论文的组织结构 本论文分为五章，结构如下： 第一章为引言，介绍当前国内外在流程流挖掘方面的研究现状，指出了各种 算法的特点和不足之处，并介绍了本文的主要工作。 第二章介绍业务流程管理的基本概念和框架体系，指出了流程挖掘研究的现 实意义。 第三章围绕流程挖掘概念提出相关的定义和定理，主要是流程挖掘概念、流 程日志的数学表示、流程模型的p c t r i 网表示及结构化工作流网概念，并给出相 关的数学描述，并介绍了目前流程挖掘领域较为完善的a 算法及其相关概念，另 外指出了a 算法在挖掘某些结构上的不足和限制。 第四章为本论文的主要工作，详细介绍了基于遗传方法的流程挖掘算法。解决了 使用遗传方法需要解决的三个主要问题：内部描述形式、适应度函数、遗传算子， 最后给出了完整的算法，此后验证了算法的正确性，并对本论文所做的工作进行 了总结，并指出了下一步的研究方向。 4 山东大学硕士学位论文 第2 章业务流程管理介绍 本章对当前业务流程管理进行简要介绍的基础上，提出工作流领域面临的机 遇和挑战，指出流程挖掘在现实中的应用。 2 1 业务流程管理的概念 在今日高度竞争的市场环境中，有效地实施企业战略已经成为企业生存的必 需。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 ) i e 是在这种背景下应运而生，这一概念自 2 0 世纪末提出以来迅速成为管理界的热门话题之一【1 1 。据权威调查显示2 0 0 3 年 底大约2 0 的大企业拥有b p m 解决方案，至u 2 0 0 5 年这个比例将提升至u 4 0 。 2 0 0 3 年由主要b p m 产品和服务提供商i b m 和s a p ，以及各研究机构i d c 、m e t a g r o u p 成立了b p m 标准组织，并在2 0 0 5 年对b p m 业务流程管理做出了如下的定义 2 1 ：业务流程管理( b p m ) 提供了优化企业战略执行的方法论，它由一套整合的、 闭环的、分析性的流程组成，这些流程由能够处理财务和运营数据的技术进行支 持。业务流程管理使得企业能够根据自身的战略目标来定义、考评和管理绩效表 现。业务流程管理的核心流程包括了计划、合并和报表、分析以及在整个组织内 部实施相关的关键绩效指标。 学者们也提出了类似的b p m 的定义，如业务流程管理( b 聊田帮助企业确立 战略目标，然后根据这些目标来考评和管理绩效【3 】。又如，业务流程管里( b p i v i ) 可以被描述为一系列的业务流程和应用系统，这些业务流程和应用系统被设计用 来优化企业战略的制定和实施【4 】。 综合以上各家的定义，我们可以看到业务流程管理既代表一种管理思想和方法， 同时也代表了运用这种思想和方法的信息系统，它整合了流程、i t 技术和人员3 个要素，通过监控和管理战略的实施，有效地保证企业战略目标的实现。 2 2 业务流程管理框架体系 我们将给出业务流程管理的框架体系，这个框架体系有助于理解b p m 的设 计、实施和管理。框架体系由4 个核心过程构成【2 】：( 1 ) 战略规划；( 2 ) 计划：( 3 ) 监 山东大学硕士学位论文 控和分析；( 4 ) 校正。前面2 个过程代表了企业战略目标的形成，后面2 个过程代 表了企业战略目标的修正和实施。这4 个步骤组成了一个闭环的整体过程，用来 根据战略指导日常运营。 下面简单地描述这4 个过程。 a 战略规划。 在这一阶段里，企业必须通过一系列活动来确定想要达到的目标，然后寻找 帮助实现这些既定战略目标的价值驱动因素，最后建立绩效指标来衡量企业在各 个时间段的业绩表现。比如，一家企业一旦确立了“客户为中心”的企业战略， 那么它很可能将高的客户满意度作为企业价值驱动因素，然后客户满意度被分解 为若干细致的绩效指标来实时衡量企业战略的实施情况。 通过确立企业整体战略和价值驱动因素相一致的关键绩效指标( k p i ) ，战略 规划这一过程正式确立了组织的使命。战略规划过程规定了b p m 下面3 个过程中 的活动，所以该过程是b p m 框架中最为重要的一个过程。 b 计划。 这一过程允许各个职能部门的经理人员根据企业战略制定目标、策划项目和 确定预算。这一过程的最主要的成果是制订一个详细的资源分配计划，以保证企 业战略目标的最终实现。 各个职能部门制订计划来实现在战略计划过程中制订的关键绩效指标 ( k p i ) 。部门计划必须说明该部门将对整体战略目标的实现做何贡献，或者是该 部门将会如何影响整体战略目标的实现。这要求各个职能部门在制订计划的过程 中始终从企业全局出发，密切留意自身计划对企业其他部门的影响。对于职能交 叉的领域，必须由各个部门的人员共同参与计划的制定，以确保整体的协调，减 少各个部门之间的冲突。从全局出发制定的关键绩效指标使得职能部门能够保持 全局的视野，从而避免计划过程中的不必要的重叠和冲突。 c 监控和分析。 监控和分析是b p m 框架体系中的第3 个过程。在这个过程里，b p m 实施的影 响和好处变得明朗化，对照标准指标数量，企业能够对各个绩效结果实施持续的 监控。通过为企业各个层面提供丰富的运营和战略分析报告的工具，这一过程帮 山东大学硕士学位论文 助评估职能部门和个人的业绩表现。而且，通过提供进一步的详细信息，该过程 能够帮助人们采取适当的行动来改善结果。 从技术层面上来说，这一过程广泛地应用了商务智f l 邑( b i ) 基础架构和其他分 析工具。利用数据仓库技术，来自多个交易处理系统的历史数据和实时数据被汇 总在一起，通过能够实现简单查询和多维数据分析的各种应用程序，企业的各级 人员可以分析绩效表现，并将实际结果与目标进行比较。目前，商务智能( b i ) 基 础架构和分析工具增长最快的应用领域正是b p m 领域【5 】。 d 校正。 这一过程是整个b p m 框架体系的第4 个过程。这一过程将对监控和分析过程 中没有涉及到的绩效的改变做出及时的反应。这一过程的活动不仅可以就潜在的 问题向用户发出警告，而且可以就如何应对问题为用户提供一套方针和建议。所 以，用户通过校正过程中的及时行动，可以有效地避免问题的升级。 综上所述，b p m 沟通了战略的制定和实施，通过4 个核心过程，它推动企业的 每位成员向着同一个方向前进。它使得企业得以专注在能带来商业价值的核心流 程上，同时忽略那些对企业长期健康发展并无益处的众多流程。 2 3 业务流程管理的应用 虽然流程挖掘发展的时间不长，但它并不只注重理论研究，业务流程管理从 一开始就与实际相结合解决流程管理问题。 国际著名评估机构a m r 断言，业务流程管理( b p m ) 已经成为今后企业 面临的重点课题之一。从上世纪九十年代开始，工作流管理系统在企业中受到了 极大的关注，但是工作流建模成为它发展的一大瓶颈，因此有学者利用流程挖掘 建模技术的客观性，使之与工作流技术充分结合。第一个和流程挖掘建模技术相 结合的是m m 公司的f l o w m a r k 工作流管理系统。但限于当时流程挖掘技术的不 完美，不能直接为f l o w m a r k 提供完整的工作流模型。目前，通过工作流管理系 统产生的日志转化为x m l 格式，直接作为流程挖掘工具的输入，而类似 i n w o l v e 、p r o c e s sm i n e r 和e m i t 等流程挖掘工具的模型也可以直接用工作流语 言( w o r k f l o wp r o c e s sd e f i n i t i o nl a n g u a g e ，w p d l ) 来表示，作为工作流管理系统 的直接输入模型两】【l o 】【1 4 】。 7 山东大学硕士学位论文 考虑到流程挖掘可以对流程执行中的变化进行监控，工作流厂商们逐渐把流 程挖掘结合到业务流程管理系统( b u s i n e s sp r o c e s sm a n a g e m e n ts y s t e m ，b p m s ) 中，解决了b p m 中的流程模拟、监控和诊断等工作，即流程分析( b u s i n e s sp r o c e s s a n a l y s i s ，b p a ) 。业务活动监控( b u s i n e s sa c t i v i t ym o n i t o r i n g ，b a m ) 的目的是 用流程日志来诊断可操作流程，这正属于流程挖掘的范畴，而b a m 是b p a 的 重要组成部分，其中一个成功的应用是a r i s 流程行为管理( p r o c e s sp e r f o r m a n c e m a n a g e r ，p p m ) t t l 。在e r p 系统中也可把流程挖掘和商务智能( b u s i n e s sp r o c e s s i n t e l l i g e n c e ，b p i ) 相结合，实现对流程的分析、预测、监控和优化，惠普公司 的流程管理就是这一技术的典型应用。遇上这些应用都不仅仅把流程挖掘局限于 建模的功能上，而是更注重对流程的分析和监型9 1 。 从系统层次上讲，b p m 是建立在应用层之上的业务逻辑管理系统，它通过 对业务流程进行建模，并迅速应用到实际业务中。证券业的流程是一个高度依赖 业务综合数据的流程，在其中的每一步都可能涉及对数据的综合查询和对各种业 务系统的调用。在这种环境下的b p m 系统，必然是建立在数据仓库及各种应用 中间件之上的业务流程管理系统。同时，企业为适应快速的市场变化，业务模式 的不确定性很强，对工作流程的变更比较频繁，因此需要不断地对流程的性能进 行分析，对流程进行调整和改进工作。调整和改进之后的流程被重新应用到工作 中并进一步接受检验，这是一个循环的流程。图2 1 是b p m 实施的总体框架。 图2 1b p m 实施的总体框架 山东大学硕士学位论文 随着工作流技术应用不断的普及，以及工作流相关理论研究的长足进步，如图论、 数据库、人工智能、数据挖掘、分布式系统等多个领域的研究内容的日益丰富， 工作流的相关研究也在不断深入。文献【l l 将工作流研究问题分为两个方面的内 容：一是为工作流技术的发展解决理论上存在的问题，探讨工作流模型和语义的 形式化表示方法等；二是从工作流技术实现的角度探讨利用先进的技术提高工作 流管理系统的性能和可靠性。文献【1 9 1 将工作流研究问题分为三个方面：技术方面， 管理和组织方面，市场、经济和社会方面。另外，文献 1 9 1 还将技术方面的问题 进一步分为构建时和运行时两类。 9 山东大学硕士学位论文 第3 章流程挖掘相关技术的数学定义 在本章中，我们将围绕流程挖掘概念提出相关的定义和定理，主要是流程挖 掘概念、流程日志的数学表示、流程模型的p e t r i 网表示及结构化工作流网概念， 并给出相关的数学描述，并介绍了目前流程挖掘领域较为完善的0 【算法及其相关 概念，另外指出了伍算法在挖掘某些结构上的不足和限制。 3 1 流程挖掘概念的引入 在提出流程挖掘概念之前，我们先来比较一下流程挖掘和传统的工作流设计 和制作方式的不同，请参照图3 1 的工作流生命周期模型。工作流生命周期由四 个阶段组成：( a ) 工作流设计( b ) 工作流配置( c ) 工作流执行( d ) 工作流 诊断。在传统的方式中，设计阶段是建立一个工作流模型。这通常通过业务磋商 来实现，通过提高手头上的业务流程管理的思想来驱动。如果设计完成，工作流 系统( 其他系统也叫“流程控件”) 按指定的要求进行配置。在配置阶段，必须 处理好正在使用的工作流管理系统的限制和特殊性。在执行阶段，工作流实例按 照设计阶段的要求和配置阶段实现的配置被工作流系统处理。基于运行的工作 流，就可以收集诊断信息，这些信息在诊断阶段被用来分析诊断。诊断阶段又为 设计阶段提供输入，由此完成一个工作流生命周期口0 1 1 2 1 1 。在传统的方法中将重 点放在设计和配置阶段，几乎没有组织来系统的收集运行数据进行分析，以便为 重新设计提供输入( 即诊断阶段经常被放弃) 2 2 1 ，即使在流程分析设计阶段，分 析设计人员大都是外部咨询师，并不是企业实际管理者或者内部员工，不能深入 全面了解企业的整个流程，而且在时间比较短，经费有限的情况下，对企业流程 的分析设计通常不能令人满意，所构造的流程模型与实际情况仍存在一定的偏 差，于是我们引入了工作流挖掘技术。 流程挖掘则是将流程反转，收集运行数据以支持工作流设计和分析1 2 3 1 。应引 起注意的是大多数情况下，在一个工作流系统建立起来之前，流程就实际上已经 存在了。也应注意到大多数信息系统中事务数据是被记载下来的( 如e r p 系统 的事务日志) 。在运行期间收集的信息能够被用来创建一个模型来解释记录的事 1 0 山东大学硕士学位论文 件。这个模型既可用于诊断阶段也可用设计或重设计阶段。因此，流程挖掘就是 指从一个真实执行的流程日志中挖掘出结构化的流程模型( 描述) 以用于工作 流设计、重设计或诊断阶段。因为这些方法凝聚在案例驱动的流程中，这些流程 被当前的工作流系统所支持因此我们也称作工作流挖掘。 r * 址 注 圈3 - 1 流程挖掘在工作流生命周期图中的表示 3 2 流程日志- 流程挖掘的起点 流程挖掘的目标是从业务过程的事务日志中抽取信息，也就是说日志是流程 挖掘的输入。所以流程挖掘的第一步是要收集与发生的业务过程有关的信息。不 仅足工作流管理系统，包括e r p 、c r m 等任何基于事务的信息系统都可以以某 种形式提供满足下列条件的过程流程日志： ( 1 ) 每一件发生的事件( e v e n t ) 都对应于系统中定义好的一项任务f r a s k ) ； ( 2 ) 每一件发生的事件都属于一个执行实例( c a s e ) ： ( 3 ) 事件是有序的，即使是并行发生的事件也会被顺序地记录下来。 流程日志综合了包括流程、组织、资源、信息等人量工作流运行状态数据( 包 括历史数据和殳时数摒) ，从而使得日志成为工作流性能分析的很好的数据源。 流程同志作为工作流挖掘引擎的输入，通过并种流程挖掘技术或者工具的处理， 挖掘出实际运行的工作流模型，然后将其与期望的过程模型或者预先设计好的过 程模型进行致性测试，并且将测试的结果用以改进流程设计，使过程模型适应 不断变化的企业需求。基，流程日志库进行相关分析成为有别于仿真的企业业务 分析和诊断，它是一种事后的诊断与优化“幡l 。 流程日志有以下三个特点： 一、是流程日志可能会很大，比如，如果有选择和并行路由，流程口志不 山东大学硕士学位论文 可能包含所有的可能路径。如果有l o 个任务并行，则可能的路径应有1 01 = 3 6 2 8 8 0 0 。如果将这些路径都体现在日志中是不现实的。而且，一些路径是不太 可能发生的。 。 二、是流程日志中可能包含干扰，也就是说一部分日志是不完整的，不正确 的，或者导致异常中止。事件由于人工或技术问题可能记录错误。因为任务由手 工操作或者被另一个系统和组织控制而导致丢失的事件常常发生。 三是日志中记录的信息是多种多样的，如事件类型、事件发生时间、事件的属性 等。要想充分的利用所有的信息是流程挖掘面临的一个重要的挑战。 3 3 流程日志的数学表示 本文中，我们将研究的日志假设成：( i ) 每一个任务都是一个原子的事件， 省去时间、日期和事件等类型因素，( ) 任务是按发生的顺序排列的，( i i d 不考虑组织机构。我们定义流程日志如下： 定义3 1 ( 流程路径，流程日志) 设t 是任务的集合，仃t 母是一个流程路 径，矽p 仃奉) 是流程日志。其中p ( p ) 是丁掌的幂集，即w t 牛w 。【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 t r i 网中任务a 开始，结束于任务d 。这些任务用变迁表示。执行完a 后面临着并行 执行b 和c ，或只执行任务e ，为了并行执行任务b 署 i c ，a n d s p l i t , l a n d - j o i n 被 d n 至j j 模型中。在本日志中，如果两个任务被按任意顺序执行，我们就假设两个任 务是并行任务。通过区分任务的开始时间和结束时间，我们能够精确的确定并行 事件。 在表3 1 中案例1 的工作流路径是b , 正i c d 。表3 1 对应的流程日志是f a b c d ， a c b d ，a e d i ，在此我们将相同的案例进行了合并。很显然一个案例的一致性 和属性是与流程挖掘有关的，然而，为了本文的理论结果，我们可以作一些抽象。 山东大学硕士学位论文 同样的原因我们从工作流路径的频率中作一些抽象。在表3 1 中工作流路径a b c d 出现了两次( 案例l 和案例3 ) ，工作流路径a c b d 也出现了两次( 案f f i j 2 和案例4 ) ， 工作流路径a e d ( 案例5 ) 只出现了一次。流程日志 a b c d ，a c b d ，a e d ) 中没 有反映工作流路径的频率。在处理流程日志中的噪音时，频率是一个非常重要的 信息。 表3 - 1 一个流程日志实例 用例任务 c a s e1t a s k a c a s e 2t 舔ka c a s e3t a s ka c a s e3t a s k b c a s e1t a s k b c a s e1t a s k c c a s e2t a s k c c a s e 4t a s k a c a s e 2t a s k b c a s e 2t a s k d c a s e5t a s k a c a s e4t a s kc c a s elt a s k d c a s e3t a s k c c a s e3t a s k d c a s e4t a s k b c a s e5t a s k e c a s e5t 舔k d c a s e 4t 舔kd 表3 - 1 包含了我们假设的任务的最小信息。在许多应用中，流程日志包含每 个事件的时间戳，这个信息可被用来提取额外的因果信息。另外，一个典型的日 志也包括事件类型的信息，如一个启动事件( 一个人从工作列表中选择任务) ， 一个完成事件( 一项任务的完成) ，一个撤销事件( 一个安排好的任务被取消) 等等。另外，我们也对案例属性之间的关系和实际被案例执行的路由感兴趣。 o 廿 一回_ o 图3 - 2 与流程日志相对应的