基于分解循环结构的流程模型挖掘方法.pdf
《基于分解循环结构的流程模型挖掘方法.pdf》由会员分享,可在线阅读,更多相关《基于分解循环结构的流程模型挖掘方法.pdf(13页珍藏版)》请在咨信网上搜索。
1、第 49卷 第 11期2023年 11月Computer Engineering 计算机工程基于分解循环结构的流程模型挖掘方法王康1,刘聪1,2,王路3,曾庆田1(1.山东科技大学 电子信息工程学院,山东 青岛 266590;2.山东理工大学 计算机科学与技术学院,山东 淄博 255000;3.山东科技大学 计算机科学与工程学院,山东 青岛 266590)摘要:模型挖掘作为流程挖掘的热点领域之一,旨在从事件日志中生成描述业务流程的模型。事件日志包含具有可分解循环依赖关系的活动,此类活动既无法使用过滤非频繁活动的方式将其过滤,也不能当作混沌活动处理,导致流程模型精确度较低。现有方法不能在含有噪声
2、的情况下根据有无循环结构划分事件日志,进而无法在无循环结构子日志上正确识别具有可分解循环依赖关系的活动,且需要依赖活动属性。为克服现有方法的不足,提高挖掘模型质量,提出分离循环结构和可分解循环依赖关系的分解流程模型挖掘框架。首先基于启发式方法将事件日志根据有无循环结构划分为两部分,在无循环结构事件日志中根据活动间可达关系频率和直接跟随关系频率识别具有可分解循环依赖关系的活动,进而将具有可分解循环依赖关系的活动从有循环结构事件日志中过滤,以识别事件日志的循环结构并投影得到子日志集合。然后使用现有流程模型挖掘方法挖掘子模型并基于边界活动分支结构关系合并子模型。实验结果表明,该方法基于 ProM 平
3、台实现,并基于公开事件日志与直接使用 Inductive Miner、基于最大划分框架和基于阶段的业务流程模型挖掘方法相比,精确度提高了 0.080.42,复杂度降低了3.8645.92。关键词:分解流程挖掘;模型挖掘;启发式挖掘;可分解循环依赖关系;模型质量开放科学(资源服务)标志码(OSID):源代码链接:https:/ J.计算机工程,2023,49(11):94-105,114.英文引用格式:WANG K,LIU C,WANG L,et al.Process model mining method based on decomposed cycle structure J.Comput
4、er Engineering,2023,49(11):94-105,114.Process Model Mining Method Based on Decomposed Cycle StructureWANG Kang1,LIU Cong1,2,WANG Lu3,ZENG Qingtian1(1.School of Electronic Information Engineering,Shandong University of Science and Technology,Qingdao 266590,Shandong,China;2.School of Computer Science
5、and Technology,Shandong University of Technology,Zibo 255000,Shandong,China;3.College of Computer Science and Engineering,Shandong University of Science and Technology,Qingdao 266590,Shandong,China)【Abstract】Model miningone of the hot areas of process miningaims to generate models describing busines
6、s processes from event logs.Event logs may contain activities with decomposable cyclic dependencies,which cannot be filtered by filtering infrequent activities nor treated as chaotic activities and can lead to low precision of process models.The existing methods cannot divide the event logs accordin
7、g to the presence or absence of cyclic structures in the presence of noise and thus cannot correctly identify activities with decomposable cyclic dependencies on sub-logs without cyclic structures,and the use of the existing methods is dependent on activity attributes.To overcome the shortage of exi
8、sting methods and improve the quality of mining models,a decomposable process model mining framework that separates the cyclic structure and decomposable cyclic dependencies is proposed.First,the event log is divided into two parts on the basis of heuristics,and the activities with decomposable cycl
9、ic dependencies are identified in the event log with no cyclic structure according to the frequency of inter-activity reachable relations and direct following relations.Then,the activities with decomposable cyclic dependencies are filtered from the event log with a cyclic structure to identify the c
10、yclic structure of the event log and to project the set of sub-logs.Finally,existing process model mining techniques are used to mine sub-models and merge sub-models according to the boundary activity branch 基金项目:国家自然科学基金(61902222);山东省泰山学者工程专项基金(ts20190936,tsqn201909109);山东省自然科学基金优秀青年基金(ZR2021YQ45);
11、山东省高等学校青创科技计划创新团队项目(QC2021948080);教育部人文社会科学研究青年基金项目(20YJCZH159);山东省自然科学基金青年基金(ZR2022QF020)。作者简介:王 康(1998),男,硕士研究生,主研方向为流程挖掘;刘 聪,教授、博士;王 路(通信作者),讲师、博士;曾庆田,教授、博士。收稿日期:2022-11-14 修回日期:2023-01-05 Email:人工智能与模式识别文章编号:1000-3428(2023)11-0094-12 文献标志码:A 中图分类号:TP301第 49卷 第 11期王康,刘聪,王路,等:基于分解循环结构的流程模型挖掘方法stru
12、cture relationship.The proposed method is implemented using the ProM platform,and its performance is quantitatively compared with that of the maximal based framework,stage-based discovery of business process model methods,and the direct use of Inductive Miner to mine models based on public event log
13、s.Experiments indicate that compared with the other methods,the precision of the proposed method is 0.08-0.42 higher,and the complexity is reduced by 3.86-45.92.【Key words】decomposed process mining;model mining;heuristic mining;decomposable cyclic dependencies;model qualityDOI:10.19678/j.issn.1000-3
14、428.00662580概述 流程挖掘1-2作为数据挖掘与业务流程管理之间的桥梁,其目的是通过从事件日志中提取有价值的信息,从而发现、监控和改进实际业务流程3。事件日志可以从 ERP、CRM、BPM 等信息系统中提取。模型挖掘是流程挖掘的起点,旨在不使用任何先验信息从事件日志中挖掘流程模型。通过对模型分析,可以了解系统真实运行情况,发现用户行为模式,进而帮助管理者完善业务流程,提升系统服务和用户体验。因此,为解决实际问题,越来越多的模型挖掘算法被提出,例如直接扫描事件日志挖掘活动间关系的 系列挖掘算法4-5和基于启发式的挖掘算法6,通过创建初始模型不断迭代获得最终模型的遗传挖掘算法7-8,通过
15、构造初始 Petri网并基于语言区域添加库所构造模型的基于语言的区域挖掘算法9以及可以实现流程模型自适应简化的模糊挖掘算法10等。然而,随着信息时代的发展和用户需求的多元化,业务流程日趋复杂,因此事件日志规模呈指数增长,以及事件日志随之产生的复杂性越来越高的特点使模型挖掘面临新的挑战,对挖掘效率和模型质量提出了更高要求。活动间依赖关系是许多模型挖掘方法的基础,例如 算法定义的直接跟随关系、因果关系、平行关系 和 不 相 关 关 系。Heuristic Miner11、Inductive Miner12、Split Miner13、基于不完备日志的块状并发过程挖掘算法14等利用活动依赖关系挖掘流
16、程模型,为提高模型质量,这类模型挖掘方法通过计算活动依赖关系频率,过滤事件日志中不频繁发生的活动或活动关系,以提高流程模型的精确度。然而,事件日志中可能包含混沌活动,这些活动的发生与流程状态无关,因为这些活动的发生频率较高,所以无法通过过滤不频繁活动的方式将其过滤。因此,文献 15 提出根据直接跟随比率等方法过滤混沌活动。混沌活动的本质是具有非常复杂的可分解循环依赖关系的活动,然而相对于混沌活动而言,事件日志中可能包含在一定程度上反映实际流程执行情况的具有可分解循环依赖关系的活动,其存在有利于业务流程分析,但也会使流程模型质量降低。上述流程模型挖掘方法都无法在可分解循环依赖关系的事件日志中提高
17、挖掘模型的质量。文献 16提出一种基于同步核的具有可分解循环依赖关系的模型挖掘方法,该方法根据案例有无循环划分事件日志,利用案例属性和决策树学习技术从无循环案例中识别可分解循环依赖关系,根据可分解循环依赖关系继续划分案例,进而基于同步核得到无循环结构的流程模型,最后在有循环结构的案例中基于返回核得到循环结构流程模型。如果事件日志包含噪声,该方法无法正确划分事件日志,进而无法识别循环结构,而且在识别具有可分解循环依赖关系的活动时需要依赖事件属性,因此该方法不具有通用性。针对上述问题,本文对存在具有可分解循环依赖关系的活动的事件日志,提出一种基于分解循环结构的流程模型挖掘框架。根据事件日志轨迹是否
18、包含循环结构划分子日志,在无循环结构事件日志中根据活动间可达关系频率和直接跟随关系频率识别具有可分解循环依赖关系的活动,并将具有可分解循环依赖关系的活动从有循环结构事件日志中过滤,以识别循环结构并投影循环结构对应的子日志。最终使用现有流程模型挖掘方法挖掘子模型,并基于边界活动分支结构关系合并子模型。1相关工作 根据日志分割方法的不同,现有分解流程模型挖掘方法主要分为基于水平分割日志和基于垂直分割日志的分解流程模型挖掘方法。基于水平分割日志的分解流程模型挖掘方法主要用于解决现有流程挖掘算法处理大规模事件日志时间效率较低的问题。目前一种集合划分方法是挖掘因果关系构造因果依赖图,对因果依赖图进行划分
19、得到重叠活动集合。最大划分技术17和 RPST(Refined Process Structure Tree)技术18都成功地应用于划分因果依赖图,得到重叠活动集合,进而实现基于事件日志水平分割的分解流程模型挖掘。最大划分技术最初目的是分解 Petri网,该技术将连接同一库所、同一内部变迁和同名变迁的边划分为同一集合17。文献 19-20 将最大划分应用于划分因果依赖图,最大划分本质上是更细粒度的Passage划分,最大划分即为部分重叠的活动集合划分。最大划分技术解决了 Passage 技术21活动集合划分不均匀的问题,使得挖掘模型时间效率再次提高。文献 22 提出最大划分扩展,旨在衡量活动分
20、组质量的指标,如内聚度和耦合度,以便预先在因果依赖图划分阶段评价最大划分质量。文献 23 提出分解流程模型挖掘框架,并将最大划分技术嵌入框952023年 11月 15日Computer Engineering 计算机工程架。文献 18 提出基于 RPST 的启发式分解并行模型挖掘框架,RPST技术将有向图划分为树状层次结构,从而得到部分重叠的活动集合。同时,该框架使用多线程和 Spark框架,使得模型挖掘效率明显高于基于最大划分框架。最大划分技术和 RPST 技术虽然成功地应用于分解流程模型挖掘,解决了现有流程挖掘算法处理大规模事件日志时间效率较低的问题,但是最大划分技术和 RPST技术在处理
21、活动关系复杂的事件日志时存在无法有效划分活动子集和最终模型相对不精确的问题。基于阶段的业务流程模型挖掘方法24和基于图聚类的流程分解方法25可以部分解决上述两种分解流程模型挖掘方法得到的模型不精确的问题。基于阶段的业务流程模型挖掘方法和基于图聚类的流程分解方法相同之处都是在活动直接跟随关系图上找到流量较多的节点,再使用图聚类技术划分得到活动子集。不同之处是为提高模型质量,前者提出了基于精确度计算的活动间关系检测方法修改子日志,以提高子日志中活动关系与原始日志中活动关系的一致性,并使用修改后的子日志重新挖掘并合并子模型;后者提出基于节点影响力和边影响力的方法,将不精确的点和边从最终模型中删除。基
22、于垂直分割日志的分解流程模型挖掘方法将事件日志中案例分组以达到划分事件日志的目的,其返回结果是从子日志集合中挖掘的一组子模型,轨迹聚类是将事件日志中案例分组划分事件日志的方法,目前主要用于改进模型挖掘的结果。例如:文献 26-27 提出基于距离的聚类方法;文献 28-29 提出基于模型驱动的轨迹聚类方法;文献 30 提出基于距离驱动和模型驱动相结合的轨迹聚类方法。文献 16 提出一种基于同步核的具有可分解循环依赖关系的模型挖掘方法,该方法根据案例是否包含循环划分事件日志,再根据可分解循环依赖关系划分无循环事件日志,这些步骤属于垂直分割事件日志。该方法分别挖掘事件日志中循环结构和其他结构对应的流
23、程模型,因此可以提高流程模型的精确度,降低流程模型的复杂度。但是,该挖掘方法无法在包含噪声的事件日志中根据有无循环结构划分子日志,进而无法识别可分解循环依赖关系,此外识别可分解循环依赖关系时构造的决策树需要将较完整的活动属性作为输入,因此该方法不具备通用性。2基础知识 本节给出分解流程挖掘相关概念,如轨迹投影、因果矩阵和因果依赖图等,具体如下:定义 1(多集)多集是元素可以多次出现的集合。B(A)表示集合 A 上的所有多集的集合,多集m B(A),元素 a A,m(a)表示活动 a 在多集 m 中出现的次数。例如,令集合 A=a,b,c ,则 m=a,b,b,c,a 是 集 合 A 上 的 一
24、 个 多 集,记 为:a2,b2,c,其 中,m(a)=m(b)=2,b(c)=1。定 义 2(序 列)序 列 是 元 素 的 有 序 集 合,令S(A)表示集合 A 上所有序列的集合,则 =S(A)表示在 A 上长度为 n 的序列,(i)表示序列 中的第 i个元素。定义 3(事件日志)令 A 表示活动集合,S(A)表示活动集合 A 上所有轨迹的集合,则事件日志 L B(S(A)是活动集合 A上轨迹的多集。例如,L1=(a,b,c)5,(a,b,c,b,c)5 是一个事件日志,包含 10个案例,共有 35+55=40个事件。定义 4(投影)21 令 A 是一个活动集合,Q A是活动集合 A 的
25、子集,S(A)表示 A 上所有事件轨迹的集合,则 Q s(A)S(Q)是一个投影函数,递归的定 义 如 下:1)Q=;2)对 于 S(A)和a A。()Q=Qa Q Qa Q 其中:Q称作轨迹 在活动子集 Q上的投影。例如(a,b,c,d,e,f,c,b)b,c,d=(b,c,d,c,b)。定义 5(标记 Petri 网)31 标记 Petri 网是一个四元组 PN=(P,T,F,l),满足:1)P T=,P T ,其中,P 是库所集合,T是变迁集合。2)F (PT)(TP)是流关系。3)l:T 是变迁标记函数,其中,是标记集合,表示不可见标记。定义 6(前集,后集)32 设 PN=(P,T;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 分解 循环 结构 流程 模型 挖掘 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。