2010年12月第36卷第24期计算机工程December 2010 Computer Engineering 文章编号100←-3428(2010)2~033-()3文献标识码A中图分类号TP31l·软件技术与数据库·流程挖掘在业务流程分发中的应用徐彰杰，葛琦(西北大学软件工程研究所，西安710127)摘要:对SOA中业务流程引擎按活动分解业务流程执行语言流程，针对此类活动封装到代理中时产生代理数量过多的情况，提出一个基于流程挖掘的智能流程分发方法，该方法。能在3个方面提高系统的性能:改善业务流程在运行时的自适应'性;根据检测相关性最强的活动封装到代理中选择最优代理;远过减少代理数量和改善代理信息的方式减少资源的使用。关键词:流程挖掘;业务流程执行语言;面向服务架构Application of Process Mining in Business Process Distribution XU Zhang-jie, GE Wei (Software Engineering Institute, Northwest University, Xi’an 710127, China) (Abstract) In SOA, there are severa1 decentra1ized orchestralion engines and their pU/pose is decomposing a BPEL process ro severa] software agents. As these process distribution methods break a BPEL process to ils building activities and encapsulate each activity in one agent, il resulls in producing a lot of agent马Thispaper proposes an Intelligent Proce% Distribution(JPD) approach based on process mining. The recommended IPD approach can improve three aspects of system quality: the amelioralio口。fbusiness process adaptabi]ity with nm-time environment, choosing the best agent granularity based on detecting most relevant activities and encapsulating them in agents and decreasing of resource usage due 10 reduced and improved number of produced agents and mcssages (Key words] process mining; BPEL; SOA 布式业务流程引擎。在引擎中几个代理执行一个流程的一部1 概述当前，许多学者在研究流程挖掘，通过流程日志文件挖分，协作完成一个完整的流程。在ReSpecT系统中使用相同掘有用的信息，然后通过这些有用的信息寻找流程中最相关的方法分发工作流。文献[5J提出了一种将一个业务流程分解的部分，画出该流程运行时的Petrì网模型，发现关系网络，的机制，从而使不同的参与者有不同的分区。上述所有方法这些关系网络可以为运行时环境查找出最合适的业务流程提对产生的代理在数量上没有进行任何控制，也没有适应运行供重要信息。本文通过对己执行流程的分析减少资源利用，时环境的代理细度。而智能流程分发(JntellìgentProcess 提高业务流程的适应性。Oistr bution, IPO)方法使用流程挖掘方法发现最好的模式来提供合适的代理。IPD方法使用独立于消息中间件的模型，2 背景知识所以，本文模型中的代理可以使用任何其他类型的中间件来 业务流程执行语言(BPEL)BPEL作用于若干Web服务(称为伙伴)之上，将其编排交豆。为能够完成特定任务的业务流程。BPEL本质上是包含了执3 智能流程分发系统行活动等元素的容器。其中，执行活动大体分为基本活动和本节着重论述如{可使用流程挖掘实现智能BPEL流程的结构化活动。分发。该方法从全局的角度使用挖掘模式发掘最密切相关的 施程捷报活动，然后将这些最密切相关的活动封装到代理中。IPO方流程挖掘能从流程日志中自动发现模型，监控和分析业法将按照最合适的细度产生代理，从而产生更多合适的代理，务流程发生的变化。使用流程挖掘监控流程的改变建~在所减少运行时产生代理的数量和消息。有流程改变都被系统记录在日志中这个假设的基础之上。文 IPD系统架构献flJ介绍了一个以变化的日志为基础的流程挖掘方法。文IPO系统的架构如因1所示。ProcessAgent是一个封装献[2]介绍了一个基于日志的数据挖掘算法。本文论述的方法最密切相关活动的代理。LogFile随执行时参与节点的数量同样使用流程挖掘的方法挖掘流程日志信息，查找一个流程而变化。BPELCornpile支持传统BPEL编译器，但它还要根中相关性最大的活动，通过这个结果类分发业务流程，提高据代理检测模式(将在下一节讨论)将一个流程分解成一些代质量。理。Middleware是给所有代理交换信息。Learningdataset在 BPEL分解和交互中间件挖掘结果集为空时用于启动引擎，开发者可以使用Learning文献[3J提到的NJNOS系统使用发布-订阅消息服务系统处理代理的交互。另J种著名的代理通信的方法是使用Tuple作者筒介:徐彰杰(1984一九男，硕士研究生，主研方向:工作流系Space。文献[4]提到的ReSpecT系统使用二个扩展的Tuple统;葛琼，副教授般稿日期2010-05-20E-mail: xuzhangjie25@ Space实现代理协作。NINOS系统中使用一个基于代理的分-33-一
Dataset改善系统初始化。ProcessMining Result Set流程挖掘假设通过本文介绍的流程挖掘检测到路径Activityl，结果集，用于存储从日志文件中提取的挖掘模式。Ifl、Activity2和Activity3被经常走过，那么可以把流程转换成3个代理，见图2(b)。这时其总的时间为:t’oml = PX(t+t+t+tAJ)+(I一p)(t川t+t+t)+t+t+ A1 if A2 ifc A4c A5 px4t+(1-P )(3t+马)+t+tc A A A显然，按完全分布式的方法，增加活动的数量会导致通信的增加。图2(c)比较了2种方法的效果。 while活动BPEL规范中有3种循环结构，本文以while结构为例。因3(a)给出了一个简单的while活动。根据文献[3-4]，while 活动将被转换成一个代理。假设执行n遍循环体的概率为p，不满足循环条件的概率为l-p，那么整个执行时间为:图1系统架构t’o"l = t+tc + P川x(tw + tc + t A2 + tc + t AJ + tc ) + (1-p) A1 日志文件的结构(tw +先)+弘=2t+tc + pxnx(3t+ 3t) +(1-P )(tA +tc) A A c本文把日志文件结构分成如下6个部分ProcessTypleld而使用IDP方法，按照图3(b)所示，while结构中的活动流程类型号表示一个特定类型的BPEL流程Process按照它们之间的亲密关系将被封装到3个代理中。所以，使Versionld流程版本号表示一个编译好的流程版本;Instanceld 用IDP方法后总的执行时间为:实例号表示一个流程实例的代号;Activity Id活动号表示一个t’otal = pxnx(4t)+(I-p)(2t)+t+tAAA c 正在运行的活动NextActivityld表示下一个将被选择运行结果表明，使用IDP方法明显能比使用全分布模型得到的活动号;ElapsedTime表示一个活动运行开始后过去了多少更好的结果。对于while活动，本文实验设定n为100，使用时间。这2种方法的结果比较见图3(c)。 代理检测模式由于一个流程的大量活动都是密切联系的，因此一个流程的活动会调用它们的邻居活动。本文将考虑所有活动的平均执行时间(tA)和通信时间(tc)。消息通信的时间将远远大于平均执行时间，即(tC>>tA)。调用、接收和应答外部Web服务的活动要除外。本文假定tc旦1000 tAo if(switch)活动if(switch)活动是一个结构活动。根据文献[3-4]，图2(a)中的BPEL流程示例将被转换成6个代理。假设执行casel的概率为p，执行case2的概率为l-p，那么执行该if活动的时间如下:t= t+t+tif + px(tc +t+t+t)+(I-p)(tc +t)+ ooml A1 c A2 c A3A4tc + t A5 = 4t A + 3t+ P x (tA + tc ) c (a)末使用IDP方法(b)使用IDP方法50000 40000 - IPD --0-圭分布式E\句AυAυOO 军」3EU饨，《的4υυ艘，四10000 10 20 30 40 50 60 70 80 9Q 100 概率pl(%)(c)结果比较(a)末使用IDP方法(b)使用IDP方法4500 图3while使用的2种方法及结果t 4 0 0 o J 500 pick活动J 000 ;g 2500 pick活动是流程等待直到某一个事件被触发。图4(a)给!E 2000 ,,.. J回15ω出了一个简单的pick活动。根据文献[3-4]，它将被转换成司1000 4个活动。假定运行onMessage的概率为p，然后在其他情况500 下将执行onAlarm事件，那么执行该pick活动的时间为:10 20 30 40 50 60 70 80 9Q 100 概事1(%)tωtal = 3t AI + 2tc + p (t A + tc ) (c)结果比较假定使用流程挖掘方法发觉Activityl，Pickl、Activity2图2if活动使用的2种方法及结果和Activity3是OnMessage事件中最相关的，使用IDP可将-34
该pick活动封装到2个代理中，如图4(b)所示，那么其运行密切的活动。使用文献[6J中的算法挖掘出相关联的活动，因结果为:此，一个与BPEL流程相关联的活动将以一个Petri网模型表示。(4)萃取代理。通过上一步产生的挖掘结果，用代理检测I= px4乌+(1-p)(3I+Ic) total A 模式从规范流程中提取代理。伪码形式如下:图4(c)是pick活动使用2种方法的比较结果。for each entry e in mining result set { //例如Set= {activity 1, activity5, activity6}是一个entryTravers the BPEL specification of process and for each activity ac { if the ac is always marked and ac E Set { if (minSupport(e )>minSupport( c) II( minSupport( e) =minSupport( ac )&& minConfidence(e )>minConfidence(a c))) mark the ac with i; else if( c E Set&&ac is not already marked ) mark the ac with i ; store minSupport and minconfidence of Set for ac; Compiling{ Encapsulated the activities which are juxtaposed(a ccording to the agent detection patterns) and marked with the same tag in one agent; (a)末使用IDP方法(b)使用IDP方法说明:第2个if语句表示，如果一个活动己被标记就说3500 明它可以被封装到多个代理中，所以这个选择代理很模糊。3000 本文定义优先选择rninSupport值高的，其次考虑mm~ 2500 Confidence值高的。如果两者的值一样高，则选择第l个方@ 2000 i&’ 法选择的代理来封装活动。l羊15001\<1 4 结束语吗1000500 本文提出使用挖掘的方法增加业务流程的适应性和减少资源使用的智能流程分发概念，给出了在流程分发中使用流。1020 30 40 50 60 70 80 90 100 程挖掘的想法，论述了BPEL几个重要活动的挖掘模式，展概率p!(%)示了如何通过前面已执行的业务流程产生代理，以伪码的形(c)结果比较式示出了执行该方法的步骤。下一步的主要工作是设计一个基于流程时间调用的挖掘算法，进而提供流程挖掘工具。困4对pick活动使用的2种方法及结果 scope活动、Compensate活动和Fault活动参考文献根据文献[3-4]，一个scope活动将被转化为一个代理，[1] van der Wil A, Christian G, Jan R, et al. Using Process Mining to 而且这个代理将通过发布-订阅机制或者一个tuplespace中Analyze and Improve Process Flexibility-position Paper[C]// 间件与它内部包含的活动以及Compensate活动和Fault活动Proceedings of the 18th International Conference on Advanced 进行联系。而从IPD的观点来看，一个scope活动将被看作Information Systems Engineering. [S. 1.]: IEEE Pr，四s，2006: 为一个独立的活动或者可能将它与Compensate活动和Fault168-177. 活动封装到一起。[2]崔伟，刘建伟，张其善IDS日志数据挖掘的改进算法[J] IPD原理计算机工程，2007，33(6):53-55. 3, 初始化阶段如果在初始化时没有流程挖掘结果或者学习集，那么先[3] Li Guoli, Hans-Arno J. NINOS: A Distributed Service Oriented 根据传统的方法启动系统。等系统启动后，流程挖掘模块将Architecture for Business Process Execution[Z]. Middleware 工作进而产生合适的代理;如果有学习集，则根据流程模拟Systems Research Group, 2007-07 产生的学习集启动系统，这样系统的编译器将把BPEL梳程[4] Mirkov-Viroli E D, Ricci A. Engineering a BPEL Orchestration 编译成相关代理，然后根据代理的行为决定哪些活动是最密Engine as a Multi-agent System[M]. [S. 1.]: Elsevier, 2007. 切相关的，将这些活动一起封装到代理中。[5] Rania-Khalaf F L. Role-based Decomposition of Businesses Using 流程挖掘和分发阶段BPEL[C]/lProc. ofIEEE International Conference on Web Se凹ices.流程挖掘和分发阶段主要分成4步:(1)合并日志文件数[S. 1.]: IEEE Press, 2006. 据。系统中所有由代理提供的日志文件需要合并在一起。日[6] Han Jiawei, Kamber M. Data Mining: Concepts and Techniques[M]. 志文件数据是在编译时使用的，因此，合并操作并不影响运[.]: Academic Press, 2001. 行。(2)预处理。剔除日志文件中无用的数据。(3)挖掘关联最编辑张正兴35一
