（计算机软件与理论专业论文）工作流模型若干挖掘算法研究.pdf

复q 人学硕士学位论文 摘竖 摘要 信息系统的建立对于企业的日常业务运作、决策等起着至关重要的作用。工作 流管理系统是利用计算机技术来自动化地执行组织机构中业务流程部分或全部的一 种技术，能大大提高业务流程的处理效率和执行质量。由于流程的不确定性，大大 增加了工作流建模的难度。而工作流挖掘技术则颠覆工作流模型牛命周期过程，并 收集工作流模型运行阶段的信息并支持模型的再设计，因此工作工作流挖掘在工作 流领域中显得日益重要。 在分析工作流挖掘技术起源和发展的基础上，对其研究现状进行了总结、指出 现有的工作流工作流挖掘技术的一些不足。针对存在的问题，提出了一种新的工作 流模型挖掘算法。首先给出了工作流模型直接依赖矩阵的定义，并利用工作流日志 建立直接依赖矩阵的算法，设计了一种基于直接依赖矩阵的模型自动牛成算法，通 过实例说明这种算法在提高模型准确率与描述能力等方面的优势。此外，为了提高 工作流对动态不确定因素的适应能力，引入了工作流频繁模式。对频繁模式给i 叶| 了 定义，并在a p r i o r i 算法基础上提出了一种工作流频繁模式挖掘算法。该频繁模式以 工仁滤管理系统日志为基础，可以量化活动间逻辑关系的强弱，在关键活动处提供 上辱流后续走势预测以及商业决策和风险预测等方面支持。 关键词：工作流管理系统，工作流挖掘，角色，工作流频繁模式，矩阵 1 1 1 复q 人学硕+ 学位论文a b s t r a c t a b s t r a c t s e t t i n gu pac o m p l e xi n f o r m a t i o ns y s t e mh a sb e c o m eav e r yi m p o r t a n tf a c t o rf o rt h e d a i l yo p e r a t i o na n dd e c i s i o n m a k i n go ft h ee n t e r p r i s e s w o r k f l o wi sat e c h n o l o g yi m p o s i n g c o m p u t e rt e c h n i q u et oe x e c u t ep a r t so fo rt h ew h o l eb u s i n e s sp r o c e s sw i t h i no r g a n i z a t i o n a u t o m a t i c a l l y t h r o u 曲t h ed i s p o s i n ge f f i c i e n c ya n de x e c u t i n gq u a l i t yo fp r o c e s sc a nb e i m p r o v e dg r e a t l y h o w e v e r , t h ec o m p l e x i t yo ft h ew o r k f l o wm a n a g e m e n ts y s t e mi n c r e a s e s t h ed i f f i c u l t yo ft h ew o r k f l o wm o d e l i n g t h eg o a lo fw o r k f i o wm i n i n gi st or e v e r s et h e p 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 da n a l y s i s s ow o r k f l o w m i n i n gt e c h n o l o g yw h i c hc a ni m p r o v ee f f i c i e n c ya n dr a t i o n a l i t yi nw o r k f l o wm a n a g e m e n t s y s t e mb e c o m em o r ea n dm o r ei m p o r t a n ti nt h ew o r k f l o wm e t h o d o l o g y b a s e do nc u r r e n tr e s e a r c ho nw o r k f l o wm i n i n gt e c h n o l o g y , o r i g i no f w o r k f l o wm i n i n g t e c h n o l o g ya n dr e l a t e de v o l u t i o n ，s o m es h o r t c o m i n g sn e e d e dt ob eo v e r c o m ei nt h i sf i e l di s p o i n t e do u t t op r o v i d eas o l u t i o nf o rs o m eo f t h ep r o b l e m st h a ta r ed e s c r i b e da b o v e ，a n dt o i m p r o v et h ew o r k f l o wm o d e lm i n i n gt e c h n o l o g yo na c c u r a c y ，an e wa l g o r i t h mf o rm i n i n g w o r k f l o wm o d e l si s p r o p o s e d f i r s t ，t h e d e f i n i t i o no fw o r k f l o w m o d e ld i r e c t d e p e r , d m a t r i x ( w d m ) i sp r o p o s e d ，a n da na l g o r i t h mi sd e s i g n e dt os e tu pw d m f r o mw o r k f l o w l o g s ，a tt h es a m et i m e ，a n o t h e ra l g o r i t h mi sd e s i g n e dt oa u t o m a t et h em o d e l i n gb a s e do i l w d m a n da c c o r d i n gt ot h eg i v e ne x a m p l e ，t h es i g n i f i c a n ta d v a n t a g eo f t h i sa l g o r i t h mw i l l b ef o u n di ni m p r o v i n ga c c u r a c y , e n h a n c i n gd e s c r i p t i o na b i l i t y i na n t h o rs i d eo fp r o c e s s m i n g i n gt e c h n o l o g yt oi m p r o v ew o r k f l o wf o ra d a p t i n gt ot h eu n c e r t a i n t y ，t h ew o r k f l o w l a r g ep a n e mi su s e d f i r s t ，t h el a r g ep a t t e r nd i s c o v e r yp r o b l e mi sd e f i n e d ，a n dal a r g e p a r e r nm i n i n ga l g o r i t h mb a s e do na p f i o r ia l g o r i t h mi sp r o p o s e d t h el a r g ep a t t e r nc a r l q u a n t i f yt h es t r e n g t ho fl o g i c a lr e l a t i o n sb e t w e e na c t i v i t i e s a n dt r n df o r e c a s ta n dc r u c i a l b u s i n e s sd e c i s i o n m a k i n gc a nb es u p p o r t e db yl a r g ep a t t e r n si nk e ya c t i v i t i e s k e yw o r d s ：w o r k f l o wm a n a g e m e n ts y s t e m ；w o r k f l o wm i n i n g ；r o l e ；w o r k f l o wp a r e m ； m a t r i x v 复口人学硕十学位论文第一章引言 第一章引言 随着企业间竞争日益激烈，提高企业工作效率，优化企业工作流程无疑是至关 重要的，而工作流管理系统正是在这种形势下应运而牛的。工作流管理作为一个被 业界广泛应用并迅速发展的技术，其丰要特点是使处理过程自动化，使人以及各种 应用工具相互之间协调工作，以完成某项工作。如今工作流管理在各种行业( 如保 险业、金融业、制造业和服务业) 已经得到了广泛的应用。 工作流管理系统是由企业预先建立的工作流模型所驱动，根据模型设计或重组 工作流程，并通过计算机来自动实施业务流程。工作流技术中，最关键问题之一是 为工作流过程建模，即对业务过程的抽象表示，工作流模型的好坏对于整个工作流 管理系统性能意义重大。因此，对工作流建模的研究具有极大的意义，优秀的建模 方法能够极大地提高企业工作流模型的效率与精确性，从而提高企业工作效率和业 务重组过程，增强企业的竞争力。 为了克服传统工作流技术的不足，同时考虑到工作流系统在实际执行过程中产 生的日志信息量巨大，其中蕴涵了工作流在实际执行过程中的一些规律，所以将数 据挖掘技术引入工作流技术中而形成了一个新的分支一工作流挖掘技术。工作流挖 掘技术有如下几个方面的重要意义： 1 、工作流挖掘技术与传统工作流建模技术专注目标不同 考虑如图1 1 所示的工作流生命周期模型，工作流的生命周期分为四个阶段：工 作流模型设计阶段、工作流模型实施阶段、工作流模型运行阶段和工作流模型再造 阶段。在传统的工作流技术中，设计阶段主要是由管理者或者商业顾问根据经验建 立工作流模型：在这个阶段之后，工作流管理系统将按照预先建立好的模型进行配 置，也就是工作流模型实施阶段，同时由于各种工作流管理系统的特性和局限性， 在这个阶段还需要将模型进行相应的调整【l 捌；在运行阶段，模型中的各个实例将按 照工作流管理系统的配置运行：根据工作流管理系统的不同，运行阶段模型的实际 运行信息将被收集起来在模型再造阶段进行分析，并将分析结果用于模型再造：最 后模型再造阶段的结果将反馈于模型设计阶段，自此为一个完整的工作流生命周 期。传统的工作流技术主要集中于周期的前两个阶段，即模型设计与实施阶段，而 模型运行阶段以及再造阶段相对关注较少，也很少有企业系统的将模型运行时的数 据收集、整理、分析，以用于模型的优化、再造方面。 2 用于工作流模型的差异分析 同样在工作流生命周期中，工作流挖掘技术可以用于模型的差异分析。一方面 复且人学硕十学位论文 第一章 引 言 由于工作流技术中，对于工作流变化以及异常处理正朝着更弹性的方式发展1 3 - 5 】，操 作人员在实际操作中有可能偏离模型设计阶段的设计结果，管理者希望能够对这样 的偏差进行监控；另一方面，由于实施阶段的原因可能造成设计阶段的结果与运行 阶段的实际模型不一致。工作流模型可以用于模型间的差异分析，如图1 1 所示，通 过监控工作流管理系统运行中事件的实际发生情况可以检测出设计阶段所设计的模 型与运行阶段实际运行的模型之间的差异，为模型实施阶段的结果进行反馈。 f ：作 模技术 图1 1 ：i ：作流生命周期 3 对模型中活动关系分析 传统的工作流建模方法通过对活动间的逻辑关系等层面进行抽象处理建立工作 流模型，一般是由商业顾问或管理者完成，致使大多数工作流模型仅对可预见、可 预先定义的流程进行管理，对流程动态变化因素缺乏支持，同时也难以反映活动间 逻辑关系的强弱。为了应对流程的多变性，需要实时地对企业流程进行监控。现实 中工作流模型巨大，含有大量的活动及复杂的关系，发生局部变化时难以发现实例 与原模型间的差异。而工作流管理系统日志中包含了活动实际执行的信息，可以利 用这些信息挖掘活动问逻辑关系性。工作流频繁模式是体现活动间逻辑关系强弱的 重要工具，利用工作流模型频繁模式能够在流程发生变化时及时地发现现有的模型 变化及趋势，并量化活动间逻辑关系的强弱，在企业决策方面，利用频繁模式可以 实时监控工作流管理系统运行，在关键的决策点可以提供后续活动走势预测、提供 商业决策和风险预测等方面支持【6 】。 4 作为商业智能和知识管理的有力补充 除了为商业流程再造( b u s i n e s sp r o c e s sr e e n g i n e e r i n g ，b p r ) ，商业流程分析 2 复口人学硕士学位论文第章引言 ( b u s i n e s sp r o c e s sa n a l y s i s ，b p a ) 提供支持以外，工作流挖掘也可以视为商业智能 ( b u s i n e s si n t e l l i g e n c e ，b 1 1 和知识管理( k n o w l e d g em a n a g e m e n t ，k m ) 的一部分。企业 应用商业智能的目的是让企业信息系统中的各种数据转变为有用的信息，达到充分 利用企业信息资源、辅助决策的目的【7 j 。以往的商业智能只是注重于对企业的数据信 息进行分析，而忽视了企业实际运作信息的工作流管理系统日志。通过将数据 挖掘技术应用于工作流模型，将工作流管理系统日志数据转换为工作流管理系统运 t 作信息，为企业的运作、决策提供支持，是企业商业智能领域的一个崭新的方向。 工作流挖掘作为发现流程模型以及工作流流模式的项重要技术，为工作流技 术的柔性变化和诊断提供了很好的解决方案。同时通过与智能管理软件的集成，为 企业业务再造工程提供了全面的支持。对于工作流挖掘的未来发展趋势，从技术的 发展来看，可以做得更好的是提高可视化程度，管理者更清楚流程的执行过程。更 好地与智能工具相结合，提高流程的柔性变化和决策能力。在流程日志变化时的迭 代挖掘能处理得更好，令新旧衔接不会导致更多的损失。 1 1 工作流挖掘技术现状 工作流软件产品经历了8 0 年代的萌芽期到9 0 年代的发展期。目前工f ；乍流产品 基本上确定了它在计算机应用软件市场上的独立位置。同时，根据所实现的业务过 程，现有的工作流管理系统逐步演化为四类f 8 】：管理型工作流、设定型工作流、防垮 型工作流、生产型工作流。 由于工作流管理系统广泛的应用，因此也越来越收到业界的关注。目前，工阵 流管理领域的研究热点主要集中于：工作流建模过程、基于w c b 的工作流、工作流 管理中的移动计算以及分布式工作流以及工作流事务管理【9 j 。其中以工作流建模过程 最为重要，因为建模技术直接决定着企业工作流模型的质量。工作流建模技术包括 工作流过程模型和过程描述语言方面的研究，前者是对业务流程的计算化描述，概 括了实现流程所需的各种必要信息：如流程开始和结束条件、组成该过程的各个步 骤、步骤闻的信息传递规则以及所需调用的应用工具等等。模型一般通过文本圆形 化的过程描述语言来表现 i o l 。而工作流挖掘技术就是以工作流管理系统为基础的数 据挖掘技术。在电子商务发展初期，企业的经营者们就有意识地把经营过程记录下 来，这样当企业新进员工时可以把这些记录作为参考的资料，或者当业务在执行中 出现问题时可以通过执行记录来发现出错的环节。随着电子商务的蓬勃发展，企业 更加重视这种信息的保存。如今，在大多数先进的管理软件中，如企业资源规划系 统( e n t e r p r i c er e s o u r c ep l a n n i n g ，e r p ) 、客户关系管理系统( c l i n e tr e l a t i o n s h i p m a n a g e m e n t ，c r m ) 、供应链管理系统( s u p p l yc h a i nm a n a g e m m t ，s c m ) 和工作流管 理系统等都可以自动生成日志来代替早期的手工记录，而这些日志是对所有业务执 复丑人学硕士学位论文第一章引言 行的真实记录。工作流挖掘就是通过对业务流程运行产生的日志进行分析，来重现 企业业务流程的真实过程】。 工作流挖掘最早是应用于软件工程领域产生的，早期的软件设计者们对软件需 求和软件分析阶段所涉及的业务认知来自业务顾问和管理者，使得他们对业务流程 的理解存在片面的因素，同时对实际运行中可能出现的意外无法预先处理，直接影 响了应用软件的整体设计。因此如何正确掌握业务流程的真正执行过程成为软件设 计者们追求的目标。c o o k ：f l w o l 佐研究中发现流程日志的记录是基于一个个完整的 事件，那么只要找到一种对日志分析的算法，在软件设计时就可以直接利用流程运 行的真实记录，客观地重现流程，从而避免由于业务顾问和管理者的丰观原因导致 的失败软件设计。因此他们提出了从纯理论、纯算法到理论和算法相结合的三种流 程发现的方法，利用记录的活动属性来自动发现活动之间的关联，从而来以此分析 软件的运行过程1 1 2 】。 总的来说，工作流挖掘的基本思想是提供一种有效的分析方法和工具，从工作 流管理系统、e r p 系统或者其他信息系统的日志文件中提取知识( 包括工作流中的数 据，控制信息，工作流的组织信息，角色信息等) ，利用这些知识对工作流进行分 析、优化等。工作流挖掘是数据挖掘技术在工作流领域的一种全新的应用。 1 2 工作流挖掘技术的不足 经过工作流产品供应商与工作流研究人员十几年的不懈努力使得工作随疆：安 由最初的萌芽逐步发展起来，并取得了相当的成果。目前，国外许多公司推出j 。备 自的工作流管理系统，比较成功的有i b m 公司的m q s e f i c s ，s t a f f w a r e 公司的 s t a f f w a r e 等【1 3 】。但是从工作流系统的实际应用状况来看，工作流技术本身还存在 些不成熟之处，主要体现在三个方面： 1 、在工作流的仿真评价方面 在工作流的仿真以及评价尚处于一种几近空白的状态。在缺乏仿真方法与仿真 工具支持的情况下，整个工作流系统是不完善的【1 4 】。因为人们难以预料所部署的工 作流过程将有可能出现怎样的结果，它有哪些不合理的地方，其性能指标如何。 2 、缺乏客观性 现有的工作流建模方法一般是由商业顾问和管理者根据经验进行设计，他们对 模型的理解往往会影响模型的质量，模型的质量往往缺乏客观的保证“”。 3 、工作流模型改进或者再造方面 由于外部环境的急剧变化，现代企业流程充满了不确定性和多变性，为了提高 4 复口1 人学硕十学何论文 第一章引言 工作流管理系统应对流程变化的能力，需要持续的对模型进行改进。现有的工作流 建模方法通过对活动间的逻辑关系等层面进行抽象处理建立工作流模型，仪对可预 见、可预先定义的流程进行管理，对流程动态变化因素缺乏支持，同时也难以反映 活动问逻辑关系的强弱o j 。 近几年，工作流技术在管理软件的设计中起到举足轻重的作用【l ”，但是专家们逐 渐发现上述几个方面正成为工作流技术发展的瓶颈f j ”。原先早期的建模技术和早期 的软件设计一样，存在模型设计和实际业务的分离，并且缺乏柔性。因此1 9 9 8 年 a g r a w a l 第一次把工作流挖掘用于工作流管理中，他通过判断活动之间的先后关系， 来构造活动的依赖性，从而构造出有向无循环图来表示流程中不同活动之间的关联 【l ”。紧接着h e r b s t 和k a r a g i a n n i s 在工作流管理系统中提出了一种隐藏的m a r k o v 方法来 构造活动间的并行和串行操作。这些算法的提出为建立完整的工作流网奠定了基 础，但它们都只涉及活动之间关联的发现，没有进一步考虑是否可以构造出一个可 以直接操作的可视化模型。 进入2 1 世纪，工作流挖掘得到了迅速的发展，a a l s t 、w e i j t e r 、s c h i m m 、h e r b s t 等人提出了不同的算法来解决工作流挖掘早期发展中存在的问题。他们通过建立数 据仓库来保存和分析流程日志，以建立完整的工作流网为目标，实现了挖掘模型的 可视化表示和流程运行的及时监控，使得工作流挖掘与工作流管理紧密结合，实现 挖掘模型在工作流管理系统的直接应用【2 0 l 。当然，用工作流挖掘来建模仍然处于发 展阶段，难免存在一些问题，但是工作流挖掘可以对不断增加的运行日志进行盼 控，用反复迭代( 递增) 的手段来提高模型的柔性变化【2 ”。利用工作流管理系统日 志挖掘工作流模型的方法最早由a f r a w a l 等提出，他们利用有向非循环图表示工作流 模型，并提出了模型挖掘的目标：满足完整性、正确性以及最小性。但算法将每个 活动作为一个原子事件，没有考虑每个活动从开始事件到结束事件之间的时间间 隔，导致活动间的并行关系不完整【翘。p i n t e r 等人在此基础上对算法进行了扩展， 考虑了活动的时间周期，但算法只能处理活动间逻辑串行和并行关系，并不能处理 活动之间的逻辑或关系 2 3 1 。h w a n g 等人也提出种通过考查活动间的依赖与交迭关 系来挖掘模型的方法，该方法可以处理活动间的串行、并行和循环关系，但该算法 同样不能处理活动间的逻辑或关系，并且该方法在处理活动间并行关系时忽略了两 个活动在不同的实例中存在不同的时序关系的情况，使并行关系存在缺陷【2 ”。 s c h i m m 贝l j 采用块状结构图表示工作流模型，重点分析了模型挖掘的过程，以及该过 程中所遇到的其他相关问题，如日志数据处理、噪音、活动名不唯一以及模型中活 动与资源的关系等【2 5 】。a a l s t 等人采用了p e t r i 网的一个子类一工作流网络( w o r k f l o w n e t ，w f n ) 来表示工作流模型，提出了a 算法，该算法将日志中活动之间的时序关 系分为四类，在此基础上得到最终的工作流模型【2 6 1 ，与文献【2 4 】类似，a 算法将每个 复口人学硕十学位论文第一章引言 活动作为一个原子事件，同时p e t r i 网中的一些经典的问题也出现在了w f n 中。而 h e r b s t 等人的挖掘算法则采用随机活动图( s t o c h a s t i c a c t i v i t yg r a p h ，s a g ) 表示模型 2 7 1 。 a g r a w a l 等人最早提出了串行模式挖掘方法，该方法事先定义阈值，利用a p r i o r i 算法挖掘串行实例中不小于阈值的极大串行序列作为串行模式，并且对算法进行了 优化2 8 0 9 1 。m a n n i l a 等人利用窗口方法，最终目的是找到序列的集合，集合中的每个 序列都被足够多的窗口所包含到【3 。但是文献【2 8 ，2 9 】中挖掘方法只将每个活动作为 一个原子事件，没有考虑每个活动从开始事件到结束事件之间的时间间隔，所以只 能处理串行的工作流模式序列。 1 3 本文的主要工作 本文分析了现有的工作流挖掘技术的发展与现状，在此基础之上对现有的挖掘 方法的不足进行了讨论，针对这些不足在工作流挖掘的活动、角色、频繁模式等纬 度提出了新的算法，解决了上述挖掘方法中存在的问题。 在活动维度，首先提出了依赖的概念，同时为了提高挖掘模型的准确性与最小 性，提出了直接依赖的定义，并以此定义了直接依赖矩阵。随后提出了一种基于矩 阵的工作流模型挖掘方法( m a t r i xb a s e dw o r k f l o wm i n i n ga l g o r i t h m ，m w m a ) ，以扩 展有向图f e x t e n d e dd i r e c t e dg r a p h ，e d g ) 表示基于模型工作流模型。模型中：专要区分 以下三种活动问逻辑关系：活动问依赖关系、活动间逻辑或选关系和活动喇逻辑并 行关系，与其他算法相比算法相比，在处理模型最小性，处理逻辑并、或以及基本 循环等关系上更具有优势。 在角色维度，首先在基于活动的工作流模型中，用户、角色、权限、活动之间 构成了四层的访问控制模型 u r p a ( u s e r - r o l e p e r m i s s i o n a c t ) 模型基础上提出了 u s r p a ( u s e r - s u b r o l e - p e r m i s s i o n a c t ) 模型。在四层的u r p a 模型中，用户与权限存在多 对多的关系，使得层与层的关系相当复杂。而在u s r p a 模型中，角色一子角色之间 是一对多的关系，即一个角色可以有多个子角色，而一个子角色只对应一个上层角 色，同样在角色一权限，权限一活动层之间也是如此。与u r p a 模型相比，u s r p a 模 型将层次间的网状结构转化为树状结构，层次关系更清晰，在基于角色的模型挖掘 过程中有更好的表达效果。然后利用角色与活动的关系，提出了一种基于角色活动 集的角色模型挖掘方法，在基于活动的工作流模型挖掘技术的基础之上，以块状结 构图表示基于角色的工作流模型。从角色的角度刻画出模型的层次概念，并且最终 建立的模型满足u s a 访问控制模型需要。 在工作流频繁模式方面，工作流频繁模式可以为流程动态变化因素提供解决的 基础，同时可以为工作流管理系统中重要的商业决策、风险预测等提供支持，也为 6 复口 人学硕十学位论文 第一章引肓 工作流模型优化提供依据。丰要通过扩展经典的a p f i o f i 算法挖掘工作流频繁模式。 a p f i o n 算法中频繁项集仪是一个事务中项的集合，没有顺序关系，但在工作流频繁 模式挖掘算法中活动间有先后顺序，而且还存在并行结构，所以采用活动间依赖关 系作为频繁项集和候选项集的项，即每个实例表示为形如d 尹n ( n = l ，0 ，一1 ) 的依赖矩阵 元素集合，通过函数c o m p m a t r i x p a t t e r n s 计算频繁项集，再通过函数c o m p p a t t e r n s 得到最终的工作流频繁模式集合。此外，a 讲o r i 算法中对频繁项没有要求，但在工 作流模型中，依赖矩阵口包含活动集合爿双d ) 中任意活动间的依赖关系，其表示的 模型才具有意义，所以工作流模式挖掘中，要求项集频繁且完整。与其他工作流模 式挖掘方法相比，本算法以活动间依赖关系为频繁模式项集，解决了其他算法不能 处理的活动间交叠关系，能够处理具有串、并行关系的工作流模型，更具优越性。 i 4 本文的章节安排 、本文分析了现有的工作流挖掘技术的发展与现状，在此基础之上对现有的挖掘 方法的不足进行了讨论，针对这些不足在工作流挖掘的活动、角色、频繁模式等纬 度提出了新的算法。具体来说，本文各章节的安排如下： 木文共分为五个章节，第一章介绍了首先详细地探讨了工作流技术的现状和以 及工作流技术存在的问题，同时引出了工作流挖掘技术研究背景和意义； 工作流挖掘进行的综述则放在了第二章进行讨论，对工作流挖掘技术的两个重 要方向一工作流模型挖掘技术和模式挖掘技术的基本理论进行了讨论，为后续的内 容提供了理论上的铺垫； 在对现有的工作流模型挖掘算法的不足之处进行分析的基础之上，在第三章本 文中提出了两个新的工作流模型挖掘方法，两种方法分别从活动与角色的角度利用 工作流系统日志挖掘工作流模型，同时以某企业售后部门投诉受理模型为例进行了 讨论与验证，并与其他的工作流模型挖掘技术进行对比。 对于工作流挖掘的另一个重要组成部分，在分析其他模式挖掘算法的缺陷基础 上，第四章提出了一种工作流频繁模式挖掘算法，以某企业售后部门投诉受理模型 为例进行了讨论与验证，并与其他的工作流模型挖掘技术进行对比： 在最后对全文进行了总结并对后续工作做了展望，这部分内容放在了全文的结 束部分。 复口人学硕十学位论文第一章引言 第二章工作流挖掘技术基础 工作流挖掘技术是工作流技术与数据挖掘技术的交叉领域，工作流挖掘方法讨 论之前，有必要先工作流技术与数据挖掘技术进行简要介绍。 2 1 工作流的概念 在工作流技术发展的几十年间，不同的研究者对工作流分别提出了不同的定 义，以非形式化语言对工作流所进行的描述。通过这些这些定义可见，工作流是针 对企业实际工作中具有固定程序的常规活动提出的一个以一个计算机实现为基础的 概念，这些活动之间存在着一定的逻辑关系，这些关系决定了企业实际工作的执行 过程。在实际情况中可以更广泛地把凡是由计算机软件系统( 工作流管理系统) 控制其 执行的过程都称为工作流。同时，从上述定义可见工作流模型包含了描述能够由工 作流执行服务执行的过程所需要的所有信息。这些信息构成了工作流模型的所有要 素，包括：过程的开始和完成条件；构成过程的活动以及进行活动间导航的规则： 执行活动的用户：用户所需要完成的任务、可能被调用的应用；工作流弓 擎的引用 关系，以及所有与工作流相关数据的定义【”j 。 工作流管理联盟定义了一个过程定义的基本元模型( m e t am o d e l ) ，妇鹫2 1 所 示。所谓元模型，一般是指描述性的模型。这里的工作流模型的元模型是用来描述 工作流模型内在联系以及工作流模型基本元素的模型。它用于描述工作流模型内部 包含的各个对象、对象之间的关系及对象的属性【3 “。 复口人学硕十学位论文 第二章1 ：作流挖掘技术基础 图2 1 i ：作流模型基本元模型 工作流模型中元素的定义和重要属性包括： 1 、活动 完成工作流的一个逻辑步骤。重要属性包括活动名称、活动类型、前后活动条 件、其他调度约束等。 2 、转移条件 从当前活动到下一活动流转或状态转移的规则，丰要参数包括过程条件、执行 条件、通知条件等。 3 、工作流相关数据 被工作流管理系统用作决定个工作流实例状态转移的数据，重要属性包括数据 名称或路径、数据类型等。 4 、角色 把参与者与一系列活动相联系的机制，重要属性包括名称、组织实体等。 5 、被调用的应用程序 应用主要描述用于完成业务过程所采用的工具和手段，重要属性包括类型或名 称、执行参数、位置或存取路径等。 从图2 1 中可以看出，工作流模型的核心是活动，活动直接或者间接( 通过应用 程序) 调用与之相关的数据，而工作流过程定义与活动、工作流相关数据之间是一 对多的关系，即一个工作流定义由多个活动与多个工作流相关数据组成。角色作为 调动活动的元素在模型中起着重要的作用，但角色与活动是多对多的对应关系。 如：一个活动可以引用多个角色、使用多个工作流相关数据，同样，一个角色可以 被多个活动引用，一个工作流相关数据可以被多个活动使用。从另一个角度来说， 工作流执行服务可以看作是一个状态变迁机器，过程或者活动的实例在响应外部事 件、工作流机负责的控制判断后，其状态发生改变。为了表达活动的生命周期，引 入活动的状态跃迁图，在活动的状态跃迁模型中，表达了活动在各种事件发生时其 状态的变化，同时也反映出了活动所具有的生命周期。图2 2 描述了过程实例的基 本状态变迁方案： 1 、初始化 过程实例被创建，包括与过程状态相关的日期、工作流相关数据，但是过程还 没有满足条件，不能执行。 9 复h 人学硕十学位论文 第二章i ：作流挖鼎技术基础 2 、运行 过程实例已经执行，过程中的活动如果条件满足就可以执行。 3 、激活 过程中的一个或者多个活动已经被执行。 4 、挂起 过程实例被静止，并且过程中的活动不能执行，直到过程返回到r u n n i n g 状 态。 5 、结束 过程实例满足结束条件；所有的完成后操作都将被执行f 例如记录日志、或者统 计信息) ，并且销毁过程实例。 。 6 、终止 过程实例在正常结束前被停止；所有的完成后操作都将被执行( 例如记录错误信 息、或者恢复数据) ，并且销毁过程实例。 图2 2 活动状态跃迁图 在企业的实际应用中，虽然工作流的概念相对于企业的物流、资金流、信息流 等概念更抽象一些，但工作流实际上是在更高层次上对物流、资金流、信息流以及 相关过程的总括，为企业的三流实现过程集成、业务过程自动化提供了有效的途径 【3 ”。工作流技术的核心是工作流模型，工作流模型中定义了各种活动之间的相互关 系，企业业务过程的集成与业务过程自动化也正是按照工作流模型中定义的活动关 0 复口人学硕十学位论文 第二章i ：作流挖捌技术基础 系来实现的。工作流模型中，无论是物流、资金流还是信息流都可以用工作流模型 的基本元素一活动进行描述，而活动间的有向边反映了活动间的逻辑关系，即活动 问的控制关系，以及执行的顺序。 2 2 工作流挖掘核心问题 2 3 1 工作流挖掘的数据表述 工作流模型的基本单位是活动，而工作流挖掘中输入数据的基本单位是事件。 如图2 3 所示，事件是活动状态跃迁的标志。在作为工作流挖掘的输入数据的情况 下，事件必须具备以下的属性： 1 、工作流模型 工作流属性表明事件属于具体的某个工作流模型。工作流模型如2 1 节中讨论 示。在工作流挖掘中，工作流模型可以表示为二元组集合g = ，其中 h g ) 是模型中所有活动的集合，耳g ) 是表示活动间的依赖关系。 2 、活动 工作流模型巾每个活动都对应多个事件，事件的活动属性表明事件所噙的活名 称，是与其他活动区分的唯标志。如图2 。2 所示，事件是活动状悉跃迁的稿：志，两 活动所对应的事件和状态有很多种，在工作流挖掘的输入数据中，关注的主要有两 种：开始事件和结束事件。所以在工作流挖掘过程中，可以将图2 2 所示的活动状态 跃迁图简化为一个更为简单的有限状态机，如图2 3 所示。简化后的有限状态机包括 以下几种状态： ( 1 ) 未激活过程实例中的活动已经被创建，但是还没有激活( 例如，活动的进入 条件没有满足) ，并且没有任务需要处理 ( 2 ) 激活创建好的任务，分配这个活动来处理 ( 3 ) 挂起活动实例被静止，并直到活动返回到i n a c t i v e i 戕态，才能为其分配任务 ( 4 ) 结束活动实例执行完成 在挖掘过程中，以开始事件和结束事件分别作为活动周期开始和结束的标致。 复口人学硕十学位论文 第二章i ：作流挖掘技术基础 始 图2 3 简化的活动生命周期幽 3 、实例 实例是工作流模型的一个子集，对于工作流模型表示的二元组集合g ，实例是集 合g 的一个诱导子集，而且该子集必须包含工作流模型中的初始活动和结束活动。 4 、事件类型 如图2 4 所示，事件类型包括：开始、挂起、重新开始、激活、结束等类型 5 、时间戳 时间戳标志每个事件发生的时间 6 、其他信息 如活动的角色调用信息，应用程序调用信息，相关数据使用信息等 根据上述讨论，可以将工作流管理系统日志定义为：所有属于同一个工作流模 型所发生的事件集合，称为该工作流的实例集合。根据2 5 1 节中的讨论，假设y = ( a l ，a 2 ，幽) 表示日志中所有活动的集合，则工作流管理系统日志是五元组s o = ( w o r k f l o w ，l n s n o ，a i ，e v e n t t y p e ，e v e n t t i m e ) 的集合，其中w o r k f l o w ，l n s n o ，a j ， e v e n t t y p e ，e v e n t t i m e 表示事件所属的工作流模型、实例号、活动号、事件类型，事 件发生时间。 2 3 2 工作流模型描述 工作流过程模型的描述方法有两种：形式化描述和非形式化描述。非形式化工 具采用图形符号表示活动和活动之间的约束关系。这种方法简单直观，在用户建 模、测览时，提供图形用户界面是必要的，大多数工作流产品都支持图形化用户界 面描述业务过程。形式化描述采用工作流描述( s p e c i f i c a t i o n ) 语言，即使用某种语 复口人学硕+ 学位论文第二章：i ：作流挖掘技术基础 言符号来表示过程模型中的各种元素：活动和业务处理规则。工作流过程模型形式 化的描述方式丰要有两种： 1 、用类似解释程序的计算机语言描述活动、数据和逻辑关系，这种工作流过程 模型描述可以直接被工作流引擎解释执行或被转化为其它形式再执行。 2 、采用面向对象技术分析活动及其逻辑关系，确定对应的对象属性和方法。通 常把活动和关系都视为对象。 而基于非形式化得描述方式丰要有以下几种： 1 、基于p e t ri 网工作流模型表述方法 p e t r i 网是既有严格数学基础的形式定义，又有直观的图形表示描述系统动态行为 的方法。尽管传统的p e t r i 网还难以直接用于工作流过程模型的建立，但它的高级变 种工作流网却能描述和分析复杂的过程 3 4 1 。工作流网w f n e t 是满足一定条件的 p e t r i 网，对应的形式化表述语言为p ? v 三( 墨t 用存在2 个特殊位置i 和0 ，其中i 表示源 ( s o u r c e ) ，o 表示漏( s i n k ) 如果在t 中添加一个变迁t ，在f 中增加元素( d ，f + ) 和( 产，砂得 至d j p n * ，卿j p n * 是强连通的。同时p e t r i 网中的元素与工作流模型中元素存在对应关 系：任务变迁，状态付位置和令牌h 工作流的某个状态。图2 4 所示为一个基于工 作流网表述语言的工作流模型 l i m eo u l 图2 4 基于工作流网表述的工作流模型 2 、基于有向图的工作流模型表述语言 类似与普通的有向连通图【3 5 】，其转换为形式化语言描述为形式化描述： ( i n s n o ，a ，d ，i n s n o 为过程的名字，a 为活动集合，f c _ axax c ，( c ，d c ，其 中c 为一布尔表达式，e 为多个命名表达式构成的集合。网中的元素与工作流模型中 复口人学硕士学位论文第二章i ：作流挖掘技术基础 元素存在对应关系：节点h 活动，有向边h 活动之间的先后关系。图2 5 所示为一个 基于有向图表述语言的工作流示例模型 图2 5 基于l ：作流网表述的i ：作流模璎 总之，工作流非形式化模型向形式化模型的转化，可以弥补前者分析能力的不 足。两者的结合，是许多工作流过程模型的选择。 2 ，3 工作流挖掘方法概念 利用工作流挖掘建立模型实现了建模过程的自动化和智能化。对于挖掘算法建 立的模型，采取不同的建模语言，其模型结构也存在差异，对不同规模的流程也需 要考虑选择合适的模型结构。工作流挖掘方法主要有以下几种： 1 、基于a d o n i s 的建模方法 a d o n i s 模型直观、容易理解，一般情况下图中的节点表示工作流中的活动或者 状态，而联接各个活动的有向弧则表示活动问的依赖关系：可以在有向图的基础上 清楚地表示活动间存在的a n d s p l i t 和a n d - j o i n 关系，使活动之间的选择、并行结构 清楚地呈现在使用者的眼前。基于a d o n i s 模型的工作流挖掘算法一般适用于规模适 中的流程，可以处理在工作流实例中具有重复活动的情况。 在实际情况中存在许多实例，它们对同一个活动有时要执行多次，如对购买设 备的批阅、密码确认的重复输入等，使得工作流挖掘需要考虑流程实例中存在同一 活动执行多次的情况，这无疑增加了建模的难度。h e r b s t 等人针对上述问题提出了一 种解决方法，分成引导和转换两个阶段。在引导阶段首先进行分离操作，即把具有 相同名称的活动用不同的名称来代替，如同时存在两个活动a ，则第二个活动a 易名 成a ，以此类推。然后采用随机活动图把活动之间的关联表示出来。在转换阶段通过 a d o n i s 模型语言把并行、选择结构清晰地呈现在使用者面前，有利于实现可视化的 设计。这里的分离操作与早期a g r a w a l 的方法大致相同，只是a g r a w a l 的方法没有构造 1 4 复人学硕+ 学位论文 第二章l ：作流挖捌技术基础 出一个完整的模型，另外它们对活动依赖性的定义不同，前者认为只有相邻的活动 之间才存在依赖性，而后者把递推关系( 活动a 一 b ，b c 贝, i j a c ) 也认为具有依赖 关系。 2 、基于工作流网的建模方法 v a n d e ra a l s t 在p e t r i 网的基础上提出了w f n e t ( w o r k f l o wn e t ) ，即工作流网。它实 际上是p e t r i 网的个延伸。w f n e t 同p e t r i 网一样具有规范化的语法定义，具有直观 性，并且易于与最终用广进行交流。同时它的模型语言表达能力，可以为大多数流 程结构建模。基于工作流网的工作流挖掘算法一般适用于规模较大，结构较复杂的 流程，对于挖掘的原始数据要求较高，并且分析的时间也较长。口算法是基于这种 模型结构的挖掘算法，可以处理工作流挖掘的噪音数据和不完整日志，使流程模型 更加精确。 当然去除噪音数据也是研究的一个重点，通常使用肩发式方法。此方法分为三 个步骤：首先建立一个活动依赖频率表( d f t a b l e ) ，对每个活动发牛的频率、与另 一活动存在依赖的频率等都在这张表中体现出来。其次挖掘d f t a b l e 中的活动之间的 关联，通过一个阈值对d f t a b l e 进行处理，对于小于阈值的依赖关系都不予考虑。最 后利用口算法来发现工作流网中不同活动的相互关系，其中口算法基于四种活动关 系：先后关系( 两个活动之间的顺序是一个紧接着另一个) 、依赖关系( 两个活动之 问的先后关系不能对调) 、选择关系( 两个活动之间不存在先后关系) 租并行关系 ( 两个活动之间的先后关系可以对调) 。用这凹种关系就可融解释流