基于混合型事件日志的容噪过程挖掘方法
专利摘要:本发明公开了一种基于混合型事件日志的容噪过程挖掘方法,以可能含有声的、既有点事件又有区间事件的混合型事件日志为输入,以挖掘得到的过程模型作为输出;为了挖掘出正确的模型,首先从事件日志的每条事件序列中挖掘低层次事件关系,称为序列级事件关系;然后,利用序列级事件关系及出现的频数,创建启发式规则,推导出高层次事件关系,称为日志层事件关系;最后,调用α算法中基于日志层事件关系的模型生成算法获得Petri网模型。本发明能从含有噪声的混合型事件日志中有效挖掘出正确的过程模型,相较于已有挖掘方法,本方法挖掘所得模型具有较高的有效性和可靠性。
专利说明:
基于混合型事件日志的容噪过程挖掘方法
[0001] 技术领域
[0002] 本发明属于数据挖掘领域,具体涉及一种基于混合型事件日志的容噪过程挖掘方法。
[0003] 背景技术
[0004] 随着互联网技术的不断发展,信息系统的业务过程也变得越来越复杂。从传统的自动化办公系统、组织业务管理系统到服务组合和云环境下的大数据应用等,很多应用的业务逻辑都可以被抽象成过程。如何挖掘出这些应用的业务过程模型成为一项重要技术。
[0005] 作为传统的手工建模的一种补充,自动化的过程挖掘技术受到了越来越多关注,它的目标是从信息系统产生的事件日志中,挖掘出有用的过程知识,对这些知识进行一系列处理,形成系统对应的业务过程模型。这种挖掘技术产生的过程模型更加贴近实际业务过程,能够为业务过程重构、优化提供重要参考意见,推动了如软件回归测试等计算机相关技术的发展。
[0006] 事件日志,是计算机信息系统的重要的一部分,记录了系统执行中发生的事件,及事件对应的时间、操作者和生命周期等相关信息,对理解复杂系统的活动至关重要,具有很大的价值。事件日志由多条事件序列组成,每条事件序列记录了一次系统执行的相关信息,具有真实性和客观性的特点。然而由于系统问题、手动记录错误以及资源限制等,现实中的事件日志往往包含噪声,如出现事件丢失、冗余及乱序的情况,对过程模型进行容噪过程挖掘成为一项重要的技术。
[0007] 现有的容噪过程挖掘方法中多数需要终端用户输入阈值,然而由于多数用户对于终端的过程不太了解,因此此种方式不能很好的适用于所有用户。
[0008] 发明内容
[0009] 本发明的目的在于提供一种基于混合型事件日志的容噪过程挖掘方法,在事件日志为可能含噪声的混合型事件日志的情况下,挖掘出该事件日志对应的过程模型。
[0010] 实现本发明目的的技术解决方案为:一种基于混合型事件日志的容噪过程挖掘方法,用于挖掘混合型事件日志的过程模型,以可能含噪声的混合型事件日志为输入,以挖掘所得过程模型为输出结果,该方法步骤如下:
[0011] 步骤1,基于事件序列挖掘序列级事件关系,扫描混合型事件日志的每一条事件序列,获取基于事件序列的序列级事件关系,包括直接先于关系、相交关系、相离关系和共同存在关系;
[0012] 步骤2,推导基于事件日志的日志层事件关系,利用序列级事件关系及出现的频数,结合Tukey’s fences,并创建启发式规则,从而推导出日志层面的事件关系,包括因果关系、交织关系和独立关系;
[0013] 步骤3,获取过程模型,调用α算法中基于日志层事件关系的模型生成算法,获得最终的过程模型。
[0014] 本发明与现有技术相比,其显著优点为:本发明所提方法能够从含噪声的混合型事件日志中有效挖掘出对应的过程模型,不需要终端用户提供阈值,挖掘所得过程模型具有有效性和可靠性。
[0015] 附图说明
[0016] 图1是本发明提供的基于混合型事件日志的容噪过程挖掘方法的流程图。
[0017] 图2是以XES格式描述的事件日志文件示意图。
[0018] 图3是含噪声的事件日志序列集合示意图。
[0019] 图4是最终挖掘所得过程模型示意图。
[0020] 具体实施方式
[0021] 本发明基于混合型事件日志的容噪过程挖掘方法,其整体流程如图1所示。首先,解析混合型事件日志,求出基于事件序列的序列级事件关系;然后,根据序列级事件关系,创建启发式规则,推导出整个日志层面的事件关系;最后,调用α算法中基于日志层事件关系的模型生成算法获得Petri网过程。具体方法如下:
[0022] 第一步,求基于事件序列的序列级事件关系的集合。混合型事件序列的类型如σ=e1 e2 e3…en包含n个事件,e1…en表示n个事件,其中ei=x表示事件ei是点事件x,ej=ys表示事件ej是区间事件y的开始事件,ej=ye表示ej是区间事件y的结束事件,求序列级事件关系的具体过程如下:
[0023] (1)解析混合型事件日志,获取日志中所有事件序列的集合,所述事件序列集合是指日志中事件可能发生的先后顺序的排序组合;
[0024] (2)扫描集合中的每一条序列,获得每条序列中包含的序列级事件关系。对于任意一条混合型事件序列σ=e1 e2 e3…en,其中包含两个事件x和y,根据事件发生的先后顺序,求解x和y之间的关系,具体包括:
[0025] a.直接先于关系,符号表示为>:当序列内两个事件ei和ej同时满足以下五个条件:①ei=x或ei=xe;②ej=y或ej=ys;③不存在p,i<p<j,ep=z;④不存在k,i<k<l<j,ek=zs,el=ze;则x>y;
[0026] b.相交关系,符号表示为︱:当序列内几个事件ei,ej,ep,eq满足以下两个条件中的任意一个:①ei=xs,ej=xe,ep=ys,eq=ye,且p<i<q或i<p<j;②ei=ys,ej=ye,ek=x,且i<k<j;则x︱y,y︱x;
[0027] c.相离关系,符号表示为若日志中两个事件x和y,满足且则
[0028] d.共同存在关系,符号表示为若两个事件x和y出现在同一条事件序列,则
[0029] 第二步,求基于日志的事件关系的集合,具体步骤如下:
[0030] (1)用|L|表示事件日志L包含的事件序列数量,用表示x和y的共同存在频数,对集合采用Tukey’s fences,过滤掉集合Sco异常值,令异常值对应的两个事件x和y的其中,Tukey’s fences判断异常值的方式如下:
[0031] 对于一组数据构成的集合,Q1表示集合中下四分位数,Q3表示集合中上四分位数,IOR=(Q3-Q1)表示集合的四分位距,将集合中小于Q1-1.5IQR和大于Q3+1.5IQR的数值识别为异常值
[0032] (2)日志层面的事件关系包括因果关系、交织关系和独立关系。用|x>y|、|x︱y|和分别表示关系x>y、x︱y和出现的频数,推导日志层面的事件关系所采用的启发式规则如下:
[0033] 启发式规则1:假设x,y∈T,若则称x和y是因果关系,符号表示为x→y;若且 则称x和y是交织关系,符号表示为x||y;若则称x和y是独立关系,符号表示为x#y。
[0034] 启发式规则2:根据“所有活动相连接”的规则,每一个不是开始节点的活动都应该有其他活动作为其前驱活动,每一个不是结束节点的活动都应该有其他活动作为其后继活动。假设非开始节点的活动y缺少前驱活动,则从与y构成直接先于关系的所有活动x中,选择|x>y|的值最大的,且作为y的前驱,即x和y关系为x→y;假设非结束节点的活动a缺少后继活动,则从与a构成直接先于关系的所有活动b中,选择|a>b|的值最大的,且作为a的后继活动,即a和b关系为a→b。
[0035] 第三步,根据第二步求得的日志层事件关系,调用α算法基于日志层事件关系的模型生成算法,获取最终模型中变迁之间的关系,并在变迁间添加库所,产生最终的Petri网模型。
[0036] 下面结合实施例和附图对本发明进行详细说明。
[0037] 实施例
[0038] 本发明为一种基于混合型事件日志的容噪过程挖掘方法。通过对可能含有噪声的混合型事件日志进行挖掘,生成对应的过程模型,具体挖掘流程如图1所示。首先挖掘基于事件序列的序列级事件关系,然后创建启发式规则,根据序列级事件关系推导出日志层面的事件关系,最后调用α算法中基于日志层事件关系的模型生成算法,获取模型中变迁之间的关系,并在变迁间添加库所,生成过程模型。
[0039] 结合实例,该方法包括:
[0040] 步骤1,求序列级事件关系。解析事件日志、获取事件日志中每条事件序列包含的序列级事件关系,具体步骤如下:
[0041] 步骤1-1,解析事件日志。如图2为某混合型事件日志的部分展示,图3为该事件日志的部分序列集合,该事件日志为XES格式文件,可通过解析标签获取所需的信息,其中log标签表示事件日志,trace标签表示事件序列,event代表事件,每个log中可包含多条trace,每条trace可包含多个event。
[0042] 步骤1-2,遍历事件序列集合,根据每一条事件序列获得其包含的序列级事件关系。
[0043] 该事件日志共包含8个事件,根据具体实施方式第一步的定义,图3事件序列集合包含的序列级事件关系如下:
[0044] (1)直接先于关系:t1>t2,t2>t6,t2>t3,t3>t4,t3>t5,t4>t7,t5>t7,t7>t8,t4>t6,t5>t6,t6>t8,t2>t4,t2>t5,t5>t4,t5>t8,t4>t8。
[0045] (2)相交关系:t4|t5,t5|t4,t2|t3,t3|t2,t7|t5,t5|t7。
[0046] (3)相离关系:
[0047] (4)共同存在关系:
[0048] 步骤2,利用步骤1获得的序列级事件关系及其出现的频数,推导日志层事件关系,具体步骤如下:
[0049] 步骤2-1,对事件日志对应的集合Sco采用Tukey’s fences检测异常值,求得事件t6和t7对应的在集合Sco中为异常值,因此令
[0050] 步骤2-2,根据启发式规则1和启发式规则2,求日志层面的关系,如对于事件t4和t8,则t4和t8之间的关系为t4#t8,最终可以求得所有日志层事件关系如下:
[0051] 因果关系:t1→t2,t2→t3,t2→t7,t7→t8,t3→t4,t3→t5,t4→t6,t5→t6,t6→t8;
[0052] 交织关系:t4||t5,t5||t4;
[0053] 独立关系:t1#t1,t1#t6,t6#t1,t1#t8,t8#t1,t1#t3,t3#t1,t1#t4,t4#t1,t1#t5,t5#t1,t1#t7,t7#t1,t2#t2,t2#t8,t8#t2,t2#t4,t4#t2,t2#t5,t5#t2,t2#t7,t7#t2,t6#t6,t6#t3,t3#t6,t6#t4,t4#t6,t6#t5,t5#t6,t6#t7,t7#t6,t8#t8,t8#t3,t3#t8,t8#t4,t4#t8,t8#t5,t5#t8,t3#t3,t3#t7,t7#t3,t4#t4,t5#t5,t7#t7。
[0054] 步骤3,根据步骤2所得的日志层事件关系,调用α算法中基于日志层事件关系的模型生成算法,生成实例对应的过程模型如图4所示。
权利要求:1.一种基于混合型事件日志的容噪过程挖掘方法,其特征在于,用于挖掘混合型事件日志对应的过程模型,以可能含噪声的、既有点事件又有区间事件的混合型事件日志为输入,以挖掘出所得过程模型为输出结果,该方法包括以下步骤:
步骤1,基于事件序列挖掘序列级事件关系,扫描混合型事件日志的每一条事件序列,获取基于事件序列的序列级事件关系,包括直接先于关系、相交关系、相离关系和共同存在关系;
步骤2,推导基于事件日志的日志层事件关系,利用序列级事件关系及出现的频数,结合Tukey’s fences,并创建启发式规则,从而推导出日志层面的事件关系,包括因果关系、交织关系和独立关系;
步骤3,获取过程模型,调用α算法中基于日志层事件关系的模型生成算法,获得最终的过程模型。
2.根据权利要求1所述的基于混合型事件日志过程挖掘方法,其特征在于,步骤1中,混合型事件序列σ=e1 e2 e3…en包含n个事件,e1…en表示n个事件,其中ei=x表示事件ei是点事件x,ej=ys表示事件ej是区间事件y的开始事件,ej=ye表示ej是区间事件y的结束事件,求序列级事件关系的具体过程如下:
步骤1-1,解析混合型事件日志,获取日志中所有的事件序列的集合,所述事件序列集合是指日志中事件可能发生的先后顺序的排序组合;
步骤1-2,扫描集合中的每一条序列,获得每条序列中事件间的关系;对于任意一条混合型事件序列σ=e1 e2 e3…en,其中包含两个事件x和y,根据事件发生的先后顺序,求解x和y之间的关系,具体包括:
(1)直接先于关系,符号表示为>:当序列内两个事件ei和ej同时满足以下四个条件:①ei=x或ei=xe;②ej=y或ej=ys;③不存在p,i<p<j,ep=z;④不存在k,l,i<k<l<j,ek=zs,el=ze;则x>y;
(2)相交关系,符号表示为︱:当序列内几个事件ei,ej,ep,eq满足以下两个条件中的任意一个:①ei=xs,ej=xe,ep=ys,eq=ye,且p<i<q或i<p<j;②ei=ys,ej=ye,ek=x,且i<k<j;则x︱y,y︱x;
(3)相离关系,符号表示为若日志中两个事件x和y,满足且则
(4)共同存在关系,符号表示为若两个事件x和y出现在同一条事件序列,则
3.根据权利要求1所述的基于混合型日志过程挖掘方法,其特征在于,步骤2中,具体包括以下步骤:
步骤2-1,用|L|表示事件日志L包含的事件序列数量,用表示x和y的共同存在频数,对集合采用Tukey’s fences,检测集合Sco中的异常值,令异常值对应的两个事件x和y的其中,Tukey’s fences检测异常值的方式如下:
对于一组数据构成的集合,Q1表示集合中下四分位数,Q3表示集合中上四分位数,IOR=(Q3-Q1)表示集合的四分位距,将集合中小于Q1-1.5IQR和大于Q3+1.5IQR的数值识别为异常值;
步骤2-2,日志层面的事件关系包括因果关系、交织关系和独立关系;用|x>y|、|x︱y|和分别表示关系x>y、x︱y和出现的频数,推导日志层面的事件关系所采用的启发式规则如下:
启发式规则1:假设x,y∈T,若则称x和y是因果关系,符号表示为x→y;若且 则称x和y是交织关系,符号表示为x||y;若则称x和y是独立关系,符号表示为x#y;
启发式规则2:根据“所有活动相连接”的规则,每一个不是开始节点的活动都应该有其他活动作为其前驱活动,每一个不是结束节点的活动都应该有其他活动作为其后继活动;假设非开始节点的活动y缺少前驱活动,则从与y构成直接先于关系的所有活动x中,选择|x>y|的值最大的,且作为y的前驱,即x和y关系为x→y;假设非结束节点的活动a缺少后继活动,则从与a构成直接先于关系的所有活动b中,选择|a>b|的值最大的,且作为a的后继活动,即a和b关系为a→b。
4.根据权利要求1所述的基于混合型日志过程挖掘方法,其特征在于:步骤3中,根据步骤2求得的日志层事件关系,调用α算法基于日志层事件关系的模型生成算法,获取最终模型中变迁之间的关系,并在变迁间添加库所,产生最终的Petri网模型。
公开号:CN110597686
申请号:CN201910761362.5A
发明人:宋巍 尚庆民 戴汪洋 肖芳雄
申请人:南京理工大学
申请日:2019-08-18
公开日:2019-12-20