一种基于完整触发序列集合的流程模型行为相似性算法

CFS：一种基于完整触发序列集合的流程模型行为相似性算法董子禾，闻立杰，黄浩未，王建民目录研究背景研究思路算法设计实验分析总结与展望1目录研究背景研究思路算法设计实验分析总结与展望2研究背景企业和公用管理机构使用流程模型形式化内部业务流程业务流程管理有助于企业和组织的正常运转、决策变更、改革创新、提升敏捷性和执行效率流程模型的相似性计算是业务流程管理的应用中不可缺少的任务3研究背景流程模型的相似性计算是业务流程管理的应用中不可缺少的任务流程模型相似性计算新建业务流程用户需求变更模型仓库管理组织合并4研究背景

模型相似性度量算法基于执行语义的相似性度量算法--CF、TAR、BP、PTS、SSDT基于拓扑结构的相似性度量算法基于标签的相似性度量算法5研究背景PTS算法分析标签Petri网覆盖树三类主变迁序列模型相似度AAddYourTextAddYourTextAddYourText分开考虑循环结构与非循环结构，打破完整行为语义对主变迁序列集合相似性的计算缺少必要加权因素衡量序列与集合相似度时未考虑集合的整体情况BC6目录研究背景研究思路算法设计实验分析总结与展望7研究思路1.计算Petri网的执行语义——覆盖树2.从覆盖树中得到完整的触发序列集合3.衡量完整触发序列集合之间的相似度4.通过实验证实该方法有效性并与其它方法对比8目录研究背景研究思路算法设计实验分析总结与展望9算法流程--CFS循环的识别和计数方案完整触发序列构造算法完整触发序列集合间映射构造算法模型相似性计算算法设计计算模型相似性

从覆盖树构造完整触发序列

10循环的识别和计数方案算法设计11完整触发序列构造算法算法设计old节点，同一循环集合执行次数超过上界值-----丢弃old节点，同一循环集合执行次数未超过上界值-----移动至anchor节点dead-end节点-----完整触发序列12算法设计

13算法设计

σ1':XYY

σ2':XWY

σ1:XYZ

14

算法设计15算法设计

16最大值算法设计完整触发序列集合间单射构造算法—A*搜索算法

17算法设计

18

算法设计

19

目录研究背景研究思路算法设计实验分析总结与展望20实验分析实验模型集在实际模型集的基础上衡量三角不等式的满足率用以确定算法参数值，当同一循环集合的执行次数上界k取2、相似性公式中的n取103时，对应的三角不等式满足率最高。模型集模型数唐车(TC)业务过程模型124东锅(DG)业务过程模型115SAP业务流程参考模型592BeehiveZ自动生成的模型20021实验分析A*算法剪枝策略实验----空间角度。衡量应用剪枝策略前后A*算法可执行完毕的模型对儿比率，即在程序结束前计算的模型对儿数与模型总对儿数的比值22实验分析A*算法剪枝策略实验----时间角度。以应用剪枝策略前A*算法可执行完毕模型对儿作为数据基础，测量每个模型对儿的平均执行时间23实验分析PTS++算法与主流模型行为相似性算法对比----性质对比

性质SSDTPTSTARCFBPCFS互斥结构漂移不变性√√√√跨度负相关性√√√无关递减性√√√√√循环序列长度负相关性√√√顺序结构漂移不变性√√√√√24实验分析新的性质----业务行为分布的不平衡性

算法SSDTPTSTARCFBPCFS相似性0.840.830.330.860.680.2925实验分析

26CFS目录研究背景研究思路算法设计实验分析总结与展望27本文提出了一种基于执行语义的过程模型相似性算法--PTS++算法利用完整触发序列表达模型行为，可应用于包含循环结构的模型，能有效处理Petri网中各类结构设计有效的剪枝策略提升了A*搜索算法的运行效率在衡量过程模型相似性算法方面提