基于加权BPMN模型的流程相似性方法.pdf
《基于加权BPMN模型的流程相似性方法.pdf》由会员分享,可在线阅读,更多相关《基于加权BPMN模型的流程相似性方法.pdf(4页珍藏版)》请在咨信网上搜索。
1、第 3 期 王倩倩,邵叱风,司中伟:基于加权 BPMN 模型的流程相似性方法 7 第 40 卷第 3 期 萍乡学院学报 2023 年 6 月 Vol.40 NO.3 Journal of Pingxiang University Jun.2023 基于加权BPMN模型的流程相似性方法 王倩倩1,邵叱风2,司中伟1(1.安徽科技学院 信息与网络工程学院,安徽 蚌埠 233000;2.安徽理工大学 数学与大数据学院,安徽 淮南 232000)摘 要:文章针对现有流程相似性计算方法缺失模型结构考量的问题,提出了一种基于 WBPMN 模型的流程相似性方法。首先,对边进行分类,定义并给出不同边的执行概率
2、计算方法;其次,由边的执行概率引出 WBPMN 模型的概念,并给出 WBPMN 模型的编辑距离;最后给出相似性计算方法整体架构。实验给出一个计算实例并与其他方法进行对比,验证了算法的可行性。关键词:WBPMN 模型;并行关系;相似性;执行概率 中图分类号:TP301 文献标志码:A 文章编号:2095-9249(2023)03-0007-04 0 引言 业务流程管理是一个成熟的领域,旨在实现业务流程的自动化,并已广泛应用于许多领域,如电子科学、医疗保健、搜索和信息整合等1。业务流程从公司各种业务中析出,其作为流程管理的核心描述了活动之间逻辑顺序以及依赖关系。为了适应不断变化的业务规范,业务流程
3、也在不断地更改,这样就会出现相似的流程,而比较流程的相似性在业务流程管理中具有重要的应用,如流程合并,流程预测等。因此,计算流程的相似性具有重要意义。目前,对于流程相似性的计算,多数是从流程模型的行为、语义或者结构等方面进行。对于行为相似性,Meilicke 等2人利用马尔可夫逻辑选择最优的匹配方法来识别两个流程模型中活动之间的关系以计算相似性。对于语义相似性,Sun 等3人提出了一种基于包含领域知识的重要语义任务邻接关系的语义工作流行为相似性度量方法。对于结构相似性,Dijkman 等4人提出了一种基于图编辑距离(GED)的流程相似性度量,但忽略了网关,不考虑并行关系(XOR、OR 和 AN
4、D),可能会导致流程模型之间的相似性测量不太准确。Montani等5人提出了一种基于扩展图形编辑距离的流程相似性度量,此时网关被认为是节点,这会使得流程模型之间所需的编辑距离太远,同时还会影响相似性测量的正确性。现有的距离相似性计算方法如曼哈顿距离、契比雪夫距离、余弦距离6等,在对比具有不同并行关系的模型时也无法进行区分。综合分析上述方法,发现相似性的计算方法,对于网关的处理,要么直接忽略了,要么看成节点,但这两种处理结果都无法区分并行关系,距离相似性计算方法也无法区分并行关系。因此,为了区分并行关系,提高计算流程模型相似性的精度,文章提出了基于加权业务流程建模标注(WBPMN)模型的流程相似
5、性方法。通过为边添加特定的属性,即边的类型以及执行概率来改进BPMN 模型得到 WBPMN 模型,然后用 WBPMN 模型的编辑距离来衡量两个 WBPMN 模型的相似性。1 基本概念 业务流程中的信息可以由活动工作流7的图形表示,即用顺序关系(Sequence)和并行关系(XOR、OR 和AND)表示。Sequence 是将一个活动连接到另一个活动的关系;当流程模型中的活动有分支并且只执行一个活动时,就会发生 XOR;当一个活动有分支并且必须执行多个分支时,使用 OR 关系;当一个活动有几个分支并且必须执行所有分支时,使用 AND 关系。如果 XOR、OR和AND关系中选择的活动是其他活动的先
6、前活动,则在关系的控制流模式中给出“Split”;如果 XOR、OR和 AND 关系中选择的活动是其他活动的下一个活动,则在关系的控制流模式中给出“Join”。可以使用特定的运算符来表示并行关系。例如,在BPMN8中 XOR、OR 和 AND 由三个网关表示,即分别为+、O 和 X。除了 BPMN 之外,还有其他命令式模式,如 Petri 网9、工作流语言(YAWL)10和事件驱动过投稿日期:2022-06-02 基金项目:安徽省教育厅重点项目“基于 Petri 网的业务流程推荐研究”(2022AH051638),“不平衡数据的重采样与分类算法研究及在农业大数据中的应用”(2022AH0516
7、51);安徽科技学院科研项目“基于服从性的协作流程变化域传播分析方法研究”(2021zryb31)作者简介:王倩倩(1993),女,安徽涡阳人,助教,硕士,研究方向:Petri 网理论及应用。8 萍乡学院学报 2023 年 程链(EPC)11。文章采用 BPMN 模型来表示 XOR、OR和 AND 关系,如图 1 所示。再根据网关类型,以及节点间的发生关系,对边进行分类,为边添加相应的类型属性,得到定义 1。abcdeabcdeabcde(网关XOR)模型P1(网关AND)模型P2(网关OR)模型P3 图 1 带有并行关系的模型 定义 1(边的类型)在 BPMN 模型中,对连接两个节点的边按照
8、两个节点的发生关系即顺序关系和并行关系进行分类,分成 7 类,分别为:Sequence,AND_Split,AND_Join,OR_Split,OR_Join,XOR_Split 和 XOR_Join。为使后面公式看上去更加简洁,对边的类型进行简化,见表 1。表 1 边的类型简化 边的类型 简记 边的类型 简记 AND_Split A_S OR_ Join O_J AND_Join A_J XOR_Split X_S OR_Split O_S XOR_Join X_J 定义 2(边的执行概率)节点 ni和 nj通过边连接,边的执行概率受边的类型以及分支数量 m(m2)的影响,顺序关系是必须执行
9、的,则执行概率为 1。对于 AND 网关,则任意分支 mi的执行概率为:()()()_1iimASmk mASmmASmmQmPPmQmP=。对于 XOR 网关,则任意分支 mi的执行概率为:()()()()_1111!1!iiXSmXSmmXSkmQmPmmQmmPm=。对于 OR 网关,则任意分支 mi的执行概率为:()()()()()11_1_1iimmkOSmkOSmmmOSmkkk PQmPmQmP=。定义 3(WBPMN 模型)WBPMN 模型是一个七元组(N,E,L,P),其中:1)N 为节点集;2)E NN 为边集;3)为边的类型;4)L 为标签集;5):NL 为将节点映射到标
10、签的函数;6):E 为将边映射到边的类型的函数;7)P:ER 为将边映射到执行概率的函数。定义 4(节点相似度)令 WG1=(N1,E1,1,L1,1,1,P1)和 WG2=(N2,E2,2,L2,2,2,P2)为两个 WBPMN 模型,n1N1,n2N2,则 n1和 n2的相似度为()()()()()()()1122121122,1max,sednnNsim n nnn=定义 5(WBPMN 模型编辑距离)令 WG1=(N1,E1,1,L1,1,1,P1)和 WG2=(N2,E2,2,L2,2,2,P2)为两个WBPMN 模型,其中 M:N1N2为将 WG1中节点映射到WG2中 节 点 的
11、部 分 单 射 函 数,其 中()()112,dom Mnn nM=是M的 定 义 域,()()221,cod Mnn nM=为 M 的值域,则基于 M 的WBPMN 模型编辑距离(WGED)为:()12,min()MMWGEDWG WGskipnskipesubnsube=+其中:|skipn|插入和删除节点的操作成本,即插入和删除节点的个数,|skipn|=|skipn|;|skipe|插入和删除边的操作成本,即插入和删除边的执行概率之和:()()1112221122eskipe eEeskipe eEskipeP eP e=+;|subn|替换节点的操作成本:()()()1212,21,
12、n nMsubnNsim n n=;|sube|替换边的操作成本,当边的类型不同时:()()121e subesubeP eP e=+,当边的类型相同时:()()12e subesubeP eP e=。定义 6 (WBPMN 模型相似性)令 WG1=(N1,E1,1,L1,1,1,P1)和 WG2=(N2,E2,2,L2,2,2,P2)为两个WBPMN 模型,M:N1N2将 WG1中的部分节点与 WG2中部分节点建立对应关系使得到的编辑距离最小,则两个 WBPMN 模型的相似性为()12,1sim WG WGwskipn fskipnwskipe fskipewsubn fsubnwsube
13、fsubewskipnwskipewsubnwsube=+其中:fskipn 插入和删除节点操作代价比,fskipe 插入和删除边的操作代价比,fsubn 替换节点的操作代价比,第 3 期 王倩倩,邵叱风,司中伟:基于加权 BPMN 模型的流程相似性方法 9 fsube 替换边的操作代价比,12skipnfskipnNN=+()()()()111222112211221122eskipe eEeskipe eEeEeEP eP efskipeP eP e+=+;()()(),21,n mMsim n mfsubnsubn=;当边的类型不同时,()()121e subeP eP efsubesu
14、be+=,当边的类型相同时,()()12e subeP eP efsubesube=。2 算法分析 算法 1:WBPMN 模型间的相似性算法 输入:两个 BPMN 模型 M 和 M;输出:两个 WBPMN 模型 WG 和 WG的相似性;Step1:输入两个 BPMN 模型 M 和 M;Step2:根据边的类型概念对 M 和 M的边进行分类;Step3:按照定义 2 为 M 和 M的边添加执行概率;Step4:将 M 和 M转化为 WBPMN 模型 WG 和 WG;Step5:按照定义5计算操作成本|skipn|、|skipe|、|subn|、|sube|;Step6:计 WG 和 WG的相似性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 加权 BPMN 模型 流程 相似性 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。