（计算机软件与理论专业论文）从事件日志中挖掘工作流模型：结构化挖掘方法研究.pdf

山东大学硕士学位论文 摘要 当今的信息系统大多都是精确流程模型驱动的。工作流管理系统，还有 e r p , c r m , 和b 2 b ，都是基于任务的工作流模型配置的。实现一个工作流设计是一 个耗时间的复杂过程，而且经常在实际的工作流程和管理的工作流之间存在差异。 本文给出了一个新的建模方法以支持精确流程建模，这种建模方法称为“基于日 志的流程挖掘”，即从已经存在的业务流程执行过程产生的日志中挖掘出需要的工 作流模型。文中用到的日志叫做“事件日志”，该日志将流程中的每个任务做为一 个原子事件来处理。 文章首先介绍了工作流技术最新的发展状况，以及w 伽c 的工作流参考模型， 然后文章总结了当前工作流建模的主要方法，提出了工作流建模领域存在的机遇 和挑战。在详细讨论流程挖掘方法前，文章对与挖掘有关的技术和理论进行了描 述，包括日志的数学表达模型，p e t r i 网和工作流网的相关属性，p e t r i 网到工作流 网的映射关系等。 之后，文章讨论了最具有挑战性的问题结构化流程挖掘。其中分为三个部 分：日志预处理，流程挖掘和合理性验证。在第一部分，讨论了如何完成日志的 过滤和噪音去除。第二部分是挖掘工作的核心。文章首先定义了能够被挖掘的工 作流模型一结构化工作流网模型( s w f ) ，并给出了s w f 定义。由于s w f 是由四 种基本结构即顺序、并行、选择和循环结构组成，因此如何从日志中将这四种基 本结构挖掘出来是成功的关键。文章给出了一种新的基于流程结构的挖掘方法， 这种方法的基本思想是对四种基本结构进行分析的基础上，从日志中找出具有这 些结构的模块，并用结点来替换每个模块。通过循环使用四种模块挖掘方法进行 挖掘和替换，最后得到一个最小的日志，该日志用上面的方法不能再挖掘出新的 模块，再用a 算法实现最终挖掘。将挖掘结果用前面得到的模块进行替换后，得 到一个容易理解的工作流网模型。最后一部分，证明用该种方法得到的工作流网 山东大学硕士学位论文 是合理的，安全的，并且是容易理解的。 在第五章，本文对日志中可能出现的噪音和不完整的日志进行了分析，提出 了一种基于启发式规则的解决噪音的手段。 最后，我们用c 语言基于该算法编写了一个日志结构化挖掘系统，通过运行 模拟日志获得足够的实验数据，对该算法的挖掘质量进行了检验分析，证明该算 法在复杂流程的挖掘方面具有明显优势。 关键词：流程挖掘；事件目志；p o t r i 网：工作流网：噪音 l i 山东大学硕士学位论文 a b s t r a c t t o d a y , m o s ti n f o r m a t i o ns y s t e m sa l ed r i v e nb ye x p l i c i tp r o c e s sm o d e l s w o r k f l o w m a n a g e m e n ts y s t e m , a n de r 只c r m , b 2 ba r ea l ic o n f i g u r e d 、析t l lw o r k f l o wm o d e l s b a s e do nt a s k s ，d e s 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 dt h e r ea r ea l w a y ss o m ed i s c r e p a n c i e sb e t w e e nt h ea c = t i l a lw o r k f l o wa n dt h em o d e l w ec r e s t e d , i nt h i sp a p e r , w ep r e s e n tan e wm e t h o dt h a ts u p p o r tt h ee x a c tw o r k f l o w d e s i g n w ec a l lt 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 h u s et h ed a t ad i r e c t l yr e l a t e dt ot h ee v e n t sh a p p e n e dd u r i n gt h ee x e c u t i o no fe x i s t i n g p 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 el o gu s e di nt h i sp a p e r i sas oc a l l e d e v e n t l 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 sa sa n a t o m i ce v e n t ， t h ep a p e rb e g i nw i t l lt h ei n t r o d u c 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 ft 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 nt h ep a p e rm a k e sac o n c l u s i o n so 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 n i n gm e t h o d s ，t h ep a p e rd e s c r i b ss o m et e c h n o l o g ya n d t 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 na n 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 gt h em a 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 o r k f l o wn e t a f t e rt h 札i tc o m e sf o rt h e p 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 ft h i s a r t i c l e 一一s t r u c t u r a lp r o c e s sm i n i n g i ti n c l u d e st h r e es e c t i o n s ：p r e _ p r o c e s s i n go fl o g ， p r o c e s sm i n i n gp r o c e s sa n dr e a s o n a b l e v a l i d a t i o no fm o d e l i nt h ef i r s ts e c t i o n ，l i a e l o gi sf i l t e r e da n dn o i s e r e m o v e dt op r o v i d eap u r ea n ds i m p l el o g t h es e c o n d s e c t i o ni st h ec o r es t e po fm i n i n g t h ep a p e rf i r s td e f i n e dw h a tk i n d so fw o r k f l o wc a n b er e d i s c o v e r i e d , t h a ti so n l ys t r u c t u r a lw b r k f l o 叫s w d a ss w fa r ec o m b i n e dw i l l l f o u r k i n d so fb a s i cs t r u c t u r e s ：s e q u e n c e ，p a r a l l e l ，a h e m a t i v ea n dl o o p ，s oh o wt o r e d i s c o v e r yt h e mf r o mt h el o gp r o d u c e db ys w f i st h ek e yo fas o c c e s sm i n i n g 1 h e p a p e rp r e s e n tan e wm i n i n gm e t h o db a s e do np r o c e s ss t r u c t u r e t h eb a s i ct h i n k i n go f t h i sm e t h o di st h r o u g ht h ea n a l y s i so ff o u rk i n d so fs t r u c t u r e se x i s t e di nt h ep r o c e s s , w e i l l 山东大学硕士学位论文 g e ts t r u c t u r em o d u l e sa n dr e p l a c et h el o gw i mam o d u l e t h e n 。w eb e g i nt h ew o r ko f l o o p i n gu s eo f4k i n d so fm i n i n gm e t h o dt om i n eb a s i cs t r u c t u r ef r o mp r o c e s sl o g , a t l a s t ，w eg e tal o gm i n i m a le n o u g ht h a tw ec a nn o tg e tb a s i cs t r u c t u r ef r o mi t t h e nw e u q e aa r i t h m e t i ct or e a l i z et h el a s tm i n i n gf r o mt h e l e a v i n gl o ga f t e ra l lt h a tw o r k h a db e e nd o n e ，w eu s et h em o d u l e sw eg e tt or e p l a c et h et a s k sn o d e s ，s ot h a tw eg e ta n u n d e r s t a n d a b l ew o r k f l o wn e t i nl a s ts e c t i o n ，w eu s et h r e ec o n d i t i o n st op r o v et h a tu s i n g o u r m i n i n gm e t h o d ，w i ge a r lg e tar e a s o n a b l ea n ds e c u r i t yw o r k f l o wm o d e l i nc h a p t e r5 ，w et a l ka b o u th o wt od e a l 晰t i ln o i s e si nt h el o g , a n dh o wt od e a l 谢t l l i n c o m p l e t el o g ，a n dp r e s e n tam e t h o dt os o l v et h en o i s ea n di n c o m p l e t el o gt h r o u g h h e u r i s t i ca p p r o a c h , d e p e n d i n go nd e p e n d e n c y f r e q u e n c yt a b l e i nt h ee n d , w ep r o d u c eap r o g r a mu s i n gv cp r o g r a mb a s e do nf l a i st h e o r y , a n d g e te n o u g hl o g st h r o u g hr u n n i n gt h el o g _ _ p r o d u e ep r o g r a m ，a n du s ot h e s el o g si no u r p r o g r a 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 sa no b v i o u sa d v a n t a g ei ng e t t i n gt h er e a s o n a b l e ，s e c u r i t ya n d u n d e r s t a n d a b l em o d e l k e yw o r d o ：p r o o o l i l lm i n i n i t ；e v o n ti o i r ；p e t r in 砒：f n e t ：n o i 8 e 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：乏女叠当 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丑垒瘟导师签名：日期：丝皇! ：! 坐 山东大学硕士学位论文 第1 章绪论 随着工作流技术的发展和工作流管理系统功能的完善，对工作流技术的研究 也正在向更深层次发展。工作流技术的研究目前有两个方向【1 1 ：一是工作流管理系 统实现理论的研究，即针对工作流模型和语义的形式化表示方法、工作流模型的 验证与分析等工作；另一方向是探讨如何利用先进的技术来提高工作流管理系统 的性能，这方面的研究方向主要有：模型仿真技术、运行时的监控与事务处理、 异常处理和错误恢复、企业业务系统的集成、流程运行数据挖掘等。本文研究的 主要内容是属于后者中的流程运行数据挖掘。 概括地说，流程挖掘就是：假设日志中记录了流程实例的实际活动执行次序， 根据日志中记录的这些信息，来重构出一个工作流模型，并使得日志中记录的任 一实例都符合这个工作流模型中的一个轨迹f 2 】。本文就是试图寻求一种从流程日志 中挖掘工作流模型的方法。 1 1 课题提出的背景和意义 在最近的十年中，工作流管理的概念和技术已经广泛应用到企业信息系统中。 工作流管理系统如s t a f f w a r e ，i b gm q s e r i e s ，c o s a ，等都有为结构化业务流程给 出通用建模和定制的能力 2 1 【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 ) 软件，供应链 管理( s 例) 系统，b 2 b 应用等等，都嵌入了工作流技术【6 】。 尽管许多系统给予了承诺，但当真正应用工作流技术时仍会遇到许多的问题。 一个问题是这些系统都需要工作流的设计，即设计器需要建立详细的描述工作路 由的精确模型。工作流建模绝不是一件简单的工作：它需要深厚的工作流知识和 与操作人员详细和深入的交流。另一个问题是为存在的流程建模往往受主观的影 山东大学硕士学位论文 响，比如模型常被标准化成为应该做什么而没有真实的描述实际的流程。结果， 创建的模型往往变得非常主观 2 1 。 一种更客观的建模方法是使用与实际发生的事件相关联的数据( 注意到流程 挖掘不受主观和惯性思维的影响) ，这就是基于日志的流程挖掘技术。流程日志的 作用是相当大的，它真实地记录了工作流管理系统的运行情况，基于日志的建模 比事前仿真在某些方面更有说服力。 流程挖掘的另一个重要意义在于，通常在理想的情况下，描述业务流程的工 作流模型总是被预先用建模工具加以定义。然后部署到工作流引擎之上加以执行； 当业务规则发生变化的时候，重新设计工作流模型。但是在某些情况下，可能原 有的工作流模型不存在或者某些局部分支丢失，存在的只是业务执行过程中留下 了的大量的执行实例和产生的轨迹。这时使用日志进行挖掘来重建工作流模型， 便是一个快捷有效的方法。另外流程挖掘可用于做d e l t a 分析，即将挖掘出来的 流程模型和原先部署在引擎之上的流程模型进行比较，分析原有的模型中存在哪 些问题，以便进行改进。流程挖掘导致一个“运行后”流程模型可用来与“运行 前”流程模型进行比较。 流程挖掘这个题目与业务流程重组( b p r ) ，业务智能( b i ) ，业务流程分析 ( b p a ) ，持续流程改进( c p i ) 和知识管理( 脚) 相关联。流程挖掘可以被看作b i ，b p a 和硒趋势的一部分。而且，流程挖掘可以被看作b p r 和c p i 活动的输入。应该注 意的是流程挖掘被用在b p r 上比c p i 更适合。回想b p r 元素的一个基本特征是它 很激进并且不受目前状况的限制。也应注意到流程挖掘不是一个重新设计流程的 工具。它的目标是获得流程真正完成的任务。尽管流程挖掘不是设计流程的工具， 但对已存在的流程进行深入理解和掌握是对重新设计流程非常重要的。认为有必 要在流程挖掘方面进行研究课题，提出可行的解决办法。其中结构化挖掘方法就 是研究成果之一，它很好的解决了从日志中发掘出合理、安全、容易理解的工作 流模型。 2 山东大学硕士学位论文 1 2 国内外研究进展情况 流程挖掘是bpm ( b u s i n e s sp r o c e s sm a n a g e m e n t ) 【6 】的一部分，其思想直 到最近才被提出来。在这方面的研究有代表性的有：从流程日志中挖掘出工作流 模型1 3 6 1 ；通过对工作流执行历史数据进行分析来确定工作流模型参数及系统瓶颈 【3 7 l ：通过数据仓库和联机分析处理技术的工作流执行数据分析0 8 1 等。c o o k 和w o l f 在软件工程流程领域已经研究了相关问题。在 1 5 中他们描述了流程发现的三种 方法：一种是使用神经网络，一种是使用纯数学方法，一种是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 扩展了他们的工作到并行流程。他们提交了指定 的测量项( 事件类型读数，周期，因果关系) 并用这些测量项从事件流中发现方 法。然而，他们没有提供一种生成精确流程的模型f 6 】。c o o k 和w o l f 提供了一种测 量方法对流程模型和实际行为进行测量。将流程挖掘技术用到工作流管理系统中 的想法首先是在 1 1 中见到。已经有很多学者在这一领域做了研究工作，例如 a g r a w a l 、g u n o p u l o s 和l e y i 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 等人研究 了基于块结构的工作流挖掘，该方法将挖掘出的工作流模型看作一棵树，其叶子 是任务，结点是操作符，并相应开发y p r o c e s sm i n e r i z 具。但目前已有的针对 p e t r i 网模型的流程挖掘算法主要还是a a l s t 等人提出的a 算法以及对该算法 的一些扩展。这类算法主要根据引擎日志中记录的活动间发生的顺序关系来进行 挖掘工作。但是目前针对p e t r i 网模型的算法还有一些问题不能够很好的解决， 主要是工作流流程模型中的某些网结构，算法不能够正确的进行挖掘，例如重复 山东大学硕士学位论文 活动、非可见活动、循环、隐式库所和同步汇聚等，而这些结构在业务流程模型 中是常见的，另外，算法得出的工作流模型往往非常难以理解，特别是在日志相对 复杂的情况下。 1 3 本文主要研究内容和特色 1 论文研究的主要内容 本文主要研究了如何从日志中挖掘工作流模型的方法。文章首先对工作流挖 掘的对象一日志进行了定义，这儿用到的日志是一种事务型日志，即将流程中的 每项任务作为一种原子事件来看待。因此，文章探讨了如何对日志进行预处理和 定义的相关问题，并对事务型日志的相关属性进行了研究。 之文章提出了一种从事务型日志中挖掘出工作流网( w f 网) 的方法：基于结 构化的挖掘方法。其中分为三个部分：日志预处理，流程挖掘和合理性验证。在 第一部分，主要完成日志的过滤和噪音去除工作，提供出一种规范化的日志格式。 第二部分是挖掘工作的核心工作流挖掘。文章首先定义了能够被挖掘的工作流 的基本要求，即结构化工作流模型( s w f ) ，并给出了s w f 定义。由于s w f 是 由四种基本结构即顺序、并行、选择和循环结构组成，因此如何从日志中将这四 种基本结构挖掘出来是成功的关键。文章给出了一种新的基于流程结构的挖掘方 法，这种方法的基本思想是对四种基本结构进行分析的基础上，从日志中找出具 有这些结构的模块，并用结点来替换每个模块。通过循环使用四种模块挖掘方法 从日志中挖掘和替换，日志不断收缩，如果最后得到的日志是一个点，只须进行 一次逆变换，即将前面得到的模块按照相反的顺序依次代入到工作流模型中。如 果最后得到的不是一个点，而是一个最小的日志，该日志用上面的方法不能再挖 掘出新的模块，即日志不能再收缩，则用a 算法实现最终挖掘，再将挖掘结果 用前面得到的模块进行逆变换。这样得到一个容易理解的基于工作流网的w f 网 模型。最后一部分，证明用该种方法得到的工作流网是合理的，安全的。在对顺 序任务和选择任务进行挖掘的过程中，考虑到来自其他并行任务的干扰，文章采 4 山东大学硕士学位论文 用了并行任务等价类概念，即首先从日志中划分出并行任务等价类，再依次搜索 各等价类，挖掘出其中的顺序和选择任务，从而很好的解决了并行任务对结构化 挖掘的干扰问题。 在第五章，还对日志中可能出现的噪音进行了分析，提出了一种基于启发式 规则的解决噪音的手段，其基本思想是，对日志中的事件发生的因果关系进行概 率统计，并根据确定的一个合理的阀值，从干扰中找出真正的因果关系，重新修 正日志。再用结构化挖掘算法进行挖掘。挖掘后的日志再进行噪音处理，再进行 挖掘，循环上面的过程，直到不能再收缩日志为止。 最后，我们用v c 实现了一个基于结构化挖掘的软件系统，并通过运行一个证 券业典型的案例数据，演示了该算法的运行过程。同时通过生成和运行一定数量 的实验数据，对该算法的挖掘质量进行了检验分析，证明该算法在复杂流程的挖 掘方面具有明显优势。 2 技术创新点t ( 1 ) 采用结构化的挖掘方法，基于工作流模型的四种基本结构( 顺序、并行、 选择和循环) 对流程日志进行挖掘，使挖掘出的工作流模型满足合理性和安全性 的同时，具有可读性和容易理解的特点。 ( 2 ) 并行结构挖掘是流程挖掘的难点。本文采用了划分并行任务等价类的方 法，解决了并行任务对挖掘算法的干扰，使并行任务中存在的顺序、选择等其他 结构得以有效挖掘。 3 研究的主要特色： ( 1 ) 基于事件型日志的工作流挖掘观念，提高工作流建模速度和准确性。 ( 2 ) 挖掘算法设计过程中，采用循环挖掘，收缩日志的方法，避免了重复分 析，提高了效率，整个算法在多项式时间内完成。 ( 3 ) 对日志的噪音处理采用循环修正日志加上结构化挖掘的方法，实现渐近 式的处理噪音方法。 ( 4 ) 挖掘算法产生的工作流网模型是基于p e 仃i 网的，有广泛的理论支持。 山东大学硕士学位论文 第2 章工作流技术介绍 本章对当前工作流技术进行简要介绍的基础上，提出工作流领域面临的机遇 和挑战，指出流程挖掘在工作流研究新领域一bp m 中的地位。 2 1 工作流的定义 1 9 9 3 年。工作流管理联盟( w o r k f l o w m a n a g e m e n tc o a l i t i o n ，w f i m c ) 的成立 标志着工作流技术进入了一个相对成熟的阶段。它是一个由很多知名学术研究机 构和软件供应商组成的非盈利性组织，一直致力于工作流技术的推广和标准化， 它给出的工作流的定义是1 3 】：工作流是一类能够完全或者部分自动执行的经营流 程，它根据一系列流程规则，使得文档、信息或任务能够在不同的执行者之间进 行传递与执行。此定义即说明了，工作流管理系统是一个软件系统，它完成工作 流的定义和管理，并按照在计算机中预先定义好的工作流逻辑推进工作流实例的 执行。 2 2 工作流参考模型 为了能够统一工作流技术研究和开发领域的相关工作，从而更好地支持企业 经营流程建模、分析和实施，以适应世界市场的多元化趋势，w f m 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 】。 6 山东大学硕士学位论文 工作流管理 工具 接口5 接口2 2 3 工作流建模方法 工作f f t a p i 与交换格式 工作流客户 应用 接n 4 图2 - 1w f m c 的工作流参考模型 其它工作流 执行服务 工作流模型是对工作流的抽象表示，也就是对经营流程的抽象表示。在工作 流系统正式运行前，必须先对系统进行建模。这个流程是将实际业务的流程规则 及相关资源表示成计算机能够执行的形式。工作流建模主要包括流程建模、功能 建模、资源建模、组织建模和信息建榭5 1 6 1 。其中最主要的是流程建模，它是整个 建模工作的核心，其它模型都是依附于它。下面着重介绍一下流程建模的内容。 目前流程建模的方法很多，文献【7 】将各种流程建模方法分为基于会话的和基 于活动的两类。文献【8 】进一步将其分为4 类：基于任务流的、基于状态转换的、 基于关系捕获的和基于通信的方法。从表现形式来看，流程模型大致可以分为非 形式化和形式化方法两类。前者一般基于图的形式，容易读懂、含义丰富，然而 缺乏分析方法，包括活动网络图研【、e p c 模型“】、语言行为模型【”i 等；后者包 括p e t r i 网【1 3 】【14 】1 1 ”、流程代数1 1 6 】1 1 7 1 1 8 l 等方法，能够精确地刻画流程逻辑，但表达能 7 山东大学硕士学位论文 力不够丰富，而且对用户的建模能力要求高。目前工作流产品一般使用网络图模 型进行建模，而流程分析方面的研究工作往往基于p e 研网、流程代数等数学工具 单独使用图模型或者形式化方法都无法解决工作流系统中的流程建模、执行和分 析的问题，目前的研究的热点是一方面为基于图的流程模型寻找理论基础，另一 方面从数学模型出发，力图丰富其表现形式。本文研究的工作流模型便是以p e t r i 网为基础的流程建模。 2 4 工作流模型验证与分析 性能分析的目的是评价流程是否能够满足预定的性能要求指标，包括吞吐量、 服务时间、资源利用率等。性能分析的方法主要有三种口o j 2 ”，分别是基于仿真的， 基于模型分析和基于历史数据的。 工作流模型仿真利用离散事件驱动的仿真引擎模拟工作流程中各项活动的执 行，在执行流程中记录相关数据( 如时间、成本和利用率等) ，进而通过这些数据 来分析业务流程的各项性能。目前工作流仿真可以使用专为业务流程仿真设计的 工具 2 2 1 ，基于p e r u 网的仿真工具t 2 3 1 2 4 ，或离散事件动态系统仿真工具瞄j 。 目前对模型的性能分析主要利用各种随机p e t d 网瞄】，根据系统的状态变化流 程建立对应的同构连续时间马尔可夫链( c o n 觚u o u st i m em , a r k o vc h a i n ) 模型或 排队论模型，进而，基于马尔可夫流程的稳态概率或排队论的相关理论求解系统 的性能参数阶2 ”。相关研究还基于随机p e t r i 网的工作流系统的顺序、并行、选择、 循环四种基本模型，并推导了这四种基本模型下的工作流性能参数，给出定量分 析工作流系统性能的通用方法。 基于历史数据的性能分析属于工作流数据挖掘的范畴，其基本思想是将数据 挖掘和数据仓库的方法用于对工作流运行历史数据的分析，用于流程模型的重构， 流程知识的挖掘等。本研究组在现有基于历史数据的事后分析的基础上，利用e c a 规则，通过构建实时流程仓库对企业业务流程性能管理体系进行了重新构架，使 得企业能对实时性能进行快速准确的闭环控制。基于p e t r i 网的理论研究目前已非 山东大学硕士学位论文 常成熟，本文研究的工作流网模型许多都是以p e t r i 理论为基础的。 2 5bp m 在证券业中的应用研究 国际著名评估机构a m r 断言，业务流程管理( bpm ) 已经成为今后企业面临的 重点课题之一。在中国，企业信息化的先锋联想与海尔都在进行公司层面的核心 业务流程的梳理和再造。作为拥有高度网络化和自动化交易系统的证券业，如何 在多系统、异构的网络交易环境下解决交易数据的高度分散性、系统间的兼容性、 以及各业务部门间的活动相互割裂、缺乏横向协同、流程被固化在系统中等一系 列问题，如何构建一个既能保护现有信息资源投资成果，又能实现在现有数据分 析基础之上的业务流程高效管理和执行，bpm 将是证券业信息化之后的一个选 择。 从系统层次上讲，bpm 是建立在应用层之上的业务逻辑管理系统，它通过 对业务流程进行建模，并迅速应用到实际业务中。证券业的流程是一个高度依赖 业务综合数据的流程，在其中的每一步都可能涉及对数据的综合查询和对各种业 务系统的调用。在这种环境下的bp m 系统，必然是建立在数据仓库及各种应用 中间件之上的业务流程管理系统。同时，企业为适应快速的市场变化，业务模式 的不确定性很强，对工作流程的变更比较频繁，因此需要不断地对流程的性能进 行分析，对流程进行调整和改进工作。调整和改进之后的流程被重新应用到工作 中并进一步接受检验，这是一个循环的流程。图2 _ 2 是bpm 实施的总体框架。 9 山东大学硕士学位论文 图2 2 证券业bpm 实施的总体框架 随着工作流技术应用不断的普及，以及工作流相关理论研究的长足进步，如 图论、数据库、人工智能、数据挖掘、分布式系统等多个领域的研究内容的日益 丰富，工作流的相关研究也在不断深入。文献 1 将工作流研究问题分为两个方面 的内容：一是为工作流技术的发展解决理论上存在的问题，探讨工作流模型和语 义的形式化表示方法等：二是从工作流技术实现的角度探讨利用先进的技术提高 工作流管理系统的性能和可靠性。文献i t 9 将工作流研究问题分为三个方面：技 术方面，管理和组织方面，市场、经济和社会方面。另外，文献 1 9 还将技术方 面的问题进一步分为构建时和运行时两类。下面对以上文献中提及的理论研究方 向做一些介绍。 山东大学硕士学位论文 第3 章流程挖掘相关技术的数学定义 在本章中，将围绕流程挖掘概念提出相关的定义和定理，主要是流程挖掘概 念、流程日志的数学表示、流程模型的p e t r i 网表示及结构化工作流网概念，并 给出相关的数学描述，为后面流程挖掘算法的提出打下基础。 3 1 流程挖掘概念的引入 在提出流程挖掘概念之前，先来比较一下流程挖掘和传统的工作流设计和制 作方式的不同，请参照图3 - 1 的工作流生命周期模型。工作流生命周期由四个阶段 组成：( a ) 工作流设计( b ) 工作流配置( c ) 工作流执行和( d ) 工作流诊断。 在传统的方式中，设计阶段是建立一个工作流模型。这通常通过业务磋商来实现， 通过提高手头上的业务流程管理的思想来驱动。如果设计完成，工作流系统( 其 他系统也叫“流程控件”) 按指定的要求进行配置。在配置阶段，必须处理好正在 使用的工作流管理系统的限制和特殊性。在执行阶段，工作流实例按照设计阶段 的要求和配置阶段实现的配置被工作流系统处理。基于运行的工作流，就可以收 集诊断信息，这些信息在诊断阶段被用来分析诊断。诊断阶段又为设计阶段提供 输入，由此完成一个工作流生命周期 2 0 1 1 2 1 1 。在传统的方法中将重点放在设计和配 置阶段，几乎没有组织来系统的收集运行数据进行分析，以便为重新设计提供输 入( 即诊断阶段经常被放弃) 阎。 流程挖掘则是将流程反转，收集运行数据以支持工作流设计和分析咧。应引 起注意的是大多数情况下，在一个工作流系统建立起来之前，流程就实际上已经 存在了。也应注意到大多数信息系统中事务数据是被记载下来的( 如e r p 系统的事 务日志) 。在运行期间收集的信息能够被用来创建一个模型来解释记录的事件。这 个模型既可用于诊断阶段也可用设计或重设计阶段。因此，流程挖掘就是指从一 个真实执行的流程日志中挖掘出结构化的流程模型( 描述) ，以用于工作流设计、 重设计或诊断阶段。因为这些方法凝聚在案例驱动的流程中，这些流程被当前的 山东大学硕士学位论文 工作流系统所支持，因此也称作工作流挖掘。 t 1 甘鸭霹舞诲? 图3 1 流程挖掘在工作流生命周期图中的表示 3 2 流程挖掘的对象一流程日志 前面提到了，流程挖掘是在一个真实执行的流程曰志中进行的，流程日志都 有哪些内容呢? 流程日志记录了工作流系统所执行的所有流程的真实轨迹，比如： 人员的登入登出时刻、任务的开始和完成时刻、任务相关数据的输入输出、当前 人员和物资的情况等等。可以说，流程日志综合了包括流程、组织、资源、信息 等大量工作流运行状态数据( 包括历史数据和实时数据) ，从而使得日志成为工作 流性能分析的很好的数据源。基于流程日志库进行相关分析成为有别于仿真的企 业业务分析和诊断，它是一种事后的诊断与优化 2 4 1 1 2 5 1 。 假设流程日志能够记录以下类型的事件：( i ) 每个事件指向一个任务( 任务是 流程中定义好的步骤) ，( ) 每个事件指向一个实例( 即工作流实例) ，( ) 事件 是有序的。任何使用事务系统的信息系统如e r p ，c r m 或工作流管理系统都将以 各种形式给出这些信息。需要注意的是由于现在还没有得到某一流程的工作流管 理系统，因此作的唯一的假设是现在可以收集流程日志。这些流程日志将被用来 创建流程。 流程日志有以下三个特点： 山东大学硕士学位论文 一是流程日志可能会很大，比如，如果有选择和并行路由，流程日志不可能 包含所有的可能路径。如果有l o 个任务并行，则可能的路径应有1 0 ! = 3 6 2 8 8 0 0 如果将这些路径都体现在日志中是不现实的。而且，一些路径是不太可能发生的。 二是流程日志中可能包含干扰，也就是说一部分日志是不完整的，不正确的， 或者导致异常中止。事件由于人工或技术问题可能记录错误。因为任务由手工操 作或者被另一个系统和组织控制而导致丢失的事件常常发生。 三是日志中记录的信息是多种多样的，如事件类型、事件发生时间、事件的 属性等。要想充分的利用所有的信息是流程挖掘面临的一个重要的挑战。 3 3 流程日志的数学表示 本文中，将研究的日志假设成：( i ) 每一个任务都是个原子的事件，省去时 间、日期和事件等类型因素，( ) 任务是按发生的顺序排列的，( 1 1 1 ) 不考虑组织 机构。定义流程日志如下： 定义3 1 ( 流程路径，流程日志) 设t 是任务的集合，o t + 是一个流程路径， w p ( t + ) 是流程日志。其中p ( t + ) 是t 的幂集，即w t + 嘲 表3 1 中日志记录包含了5 个案例的信息( 即工作流实例) ，日志显示了在其 中的4 个案例中，包含a ，b ，c 和d 四个任务。第5 个案例只有三个任务执行： 任务a e 和d 。每个案例由执行a 开始，执行d 结束。如果b 执行。则任务c 就被执行。然而，一些情况下c 在b 前执行。基于表3 - l 所显示的信息并假设日 志相对完整的( 即假设案例有代表性且是一个关于所有能被观测到的执行序列的 一个最大子集) ，可以导出图3 2 所示的流程模型。这个流程用p e t f i 网表示。p e t r i 网中任务a 开始，结束于任务d 。这些任务用变迁表示。执行完a 后面l 临着并行 执行b 和c ，或只执行任务e ，为了并行执行任务b 和c ，a n d s p l i c t 和a n d - j o i n 被加到模型中在本日志中，如果两个任务被按任意顺序执行，就假设两个任务 是并行任务。通过区分任务的开始时间和结束时间，能够精确的确定并行事件。 在表3 一l 中案例1 的工作流路径是a b c d 。表3 1 对应的流程日志是 a b c d ， 山东大学硕士学位论文 a c b d ，a e d ，在此将相同的案例进行了合并。很显然一个案例的一致性和属性 是与流程挖掘有关的，然而，为了本文的理论结果，可以作一些抽象。同样的原 因从工作流路径的频率中作一些抽象。在表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 中没有反映 工作流路径的频率。在处理流程日志中的噪音时，频率是一个非常重要的信息。 但目前暂时不考虑噪音。因此，这些抽象有利于使符号简单化。 c a 8 ei d e n u i f i , e t 3 l -t a 8 ki d 衄t i f i e r c 氧8 ei -t ka c 1 日e21 ：目l 8 1 ca , c ：b 旧t o3 t g a _ 8 ka c 矗尊3t a 8 kb c a 6 t e ti -t a b k8 c 丑嚣曩量七a 8 kc c a 8 e2t a 8 kc c 磊b e4t a s k 盘 c a 。 ：z u a s k8 c a 暑e2t 矗8 kd 4 0 1 l t j $ o5t a 。s ：ka c 赢8 e4 t 赢g kc c a 8 e 生- i e a s kd c ；& 1 5 , g i t3 七a b kc c & 0 e3t a 8 kd c 赢b e4乞鱼g kb c a ；t a 8 ke c i t s e5t 氆墨kd c a 量e4t 鱼b kd 表3 - 1 。一个流程日志实例 图3 - 2 与流程日志相对应的流程模型 表3 1 包含了假设的任务的最小信息。在许多应用中，流程日志包含每个事件 1 4 山东大学硕士学位论文 的时间邮戳，这个信息可被用来提取额外的因果信息。另外，一个典型的日志也 包括事件类型的信息，如一个启动事件( 一个人从工作列表中选择任务) ，一个完 成事件( 一项任务的完成) ，个撤销事件( 一个安排好的任务被取消) 等等。另 外，也对案例属性之间的关系和实际被案例执行的路由感兴趣。 在介绍了一些基本的概念后，回到本文的主题：流程挖掘。流程挖掘的目的 是从流程日志中找到一个