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

1、Workflow GroupI.S.ESoftware SchoolCFS：一种基于完整触发序列集合的流程模型行为相似性算法董子禾，闻立杰，黄浩未，王建民Workflow GroupI.S.ESoftware School目录1Workflow GroupI.S.ESoftware School目录2Workflow GroupI.S.ESoftware School研究背景 企业和公用管理机构使用流程模型形式化内部业务流程 业务流程管理有助于企业和组织的正常运转、决策变更、改革创新、提升敏捷性和执行效率 流程模型的相似性计算是业务流程管理的应用中不可缺少的任务3Workflow GroupI

2、.S.ESoftware School研究背景 流程模型的相似性计算是业务流程管理的应用中不可缺少的任务流程模型相似性计算新建业务流程用户需求变更模型仓库管理组织合并4Workflow GroupI.S.ESoftware School研究背景 模型相似性度量算法基于执行语义的相似性度量算法-CF、TAR、BP、PTS、SSDT基于拓扑结构的相似性度量算法基于标签的相似性度量算法5Workflow GroupI.S.ESoftware School研究背景 PTS算法分析标签Petri网覆盖树三类主变迁序列模型相似度Add Your TextAdd Your TextAdd Your Text

3、分开考虑循环分开考虑循环结构与非循环结构与非循环结构，结构，打破完整行为语义打破完整行为语义对主变迁序列集合相似性的计算缺少对主变迁序列集合相似性的计算缺少必要必要加权加权因素因素衡量序列与集合相似度时未考虑集合的整体情况衡量序列与集合相似度时未考虑集合的整体情况6Workflow GroupI.S.ESoftware School目录7Workflow GroupI.S.ESoftware School研究思路1. 计算Petri网的执行语义覆盖树2. 从覆盖树中得到完整的触发序列集合3. 衡量完整触发序列集合之间的相似度4. 通过实验证实该方法有效性并与其它方法对比8Workflow Gr

4、oupI.S.ESoftware School目录9Workflow GroupI.S.ESoftware School 算法流程 - CFS循环的识别和计数方案完整触发序列构造算法完整触发序列集合间映射构造算法模型相似性计算算法设计计算模型相似性 从覆盖树构造完整触发序列10Workflow GroupI.S.ESoftware School 循环的识别和计数方案算法设计11Workflow GroupI.S.ESoftware School 完整触发序列构造算法算法设计old节点，同一循环集合执行次数超过上界值-丢弃old节点，同一循环集合执行次数未超过上界值-移动至anchor节点dea

5、d-end节点-完整触发序列12Workflow GroupI.S.ESoftware School算法设计13Workflow GroupI.S.ESoftware School算法设计1:XYY 2:XWY 1:XYZ 14Workflow GroupI.S.ESoftware School算法设计15Workflow GroupI.S.ESoftware School算法设计16最大值Workflow GroupI.S.ESoftware School算法设计 完整触发序列集合间单射构造算法A*搜索算法 17Workflow GroupI.S.ESoftware School算法设计18

6、Workflow GroupI.S.ESoftware School算法设计19Workflow GroupI.S.ESoftware School目录20Workflow GroupI.S.ESoftware School实验分析 实验模型集 在实际模型集的基础上衡量三角不等式的满足率用以确定算法参数值，当同一循环集合的执行次数上界k取2、相似性公式中的n取103时，对应的三角不等式满足率最高。模型集模型数唐车(TC)业务过程模型124东锅(DG)业务过程模型115SAP业务流程参考模型592BeehiveZ自动生成的模型20021Workflow GroupI.S.ESoftware Sc

7、hool实验分析 A*算法剪枝策略实验 -空间角度。衡量应用剪枝策略前后A*算法可执行完毕的模型对儿比率，即在程序结束前计算的模型对儿数与模型总对儿数的比值22Workflow GroupI.S.ESoftware School实验分析 A*算法剪枝策略实验 -时间角度。以应用剪枝策略前A*算法可执行完毕模型对儿作为数据基础，测量每个模型对儿的平均执行时间23Workflow GroupI.S.ESoftware School实验分析 PTS+算法与主流模型行为相似性算法对比 -性质对比 性质性质SSDTPTSTARCFBPCFS互斥结构漂移不变性跨度负相关性无关递减性循环序列长度负相关性顺序

8、结构漂移不变性24Workflow GroupI.S.ESoftware School实验分析 新的性质 -业务行为分布的不平衡性 算法SSDTPTSTARTARCFBPCFSCFS相似性0.840.830.330.860.680.2925Workflow GroupI.S.ESoftware School实验分析26CFSWorkflow GroupI.S.ESoftware School目录27Workflow GroupI.S.ESoftware School 本文提出了一种基于执行语义的过程模型相似性算法-PTS+算法 利用完整触发序列表达模型行为，可应用于包含循环结构的模型，能有效处理Petri网中各类结构 设计有效的剪枝策略提升了A*搜索算法的运行效率 在衡量过程模型相似性算法方面提出了新的性质工作总结 28Workf