【合规性检查-Fitness】基于Token重演的拟合度评估方法

2023-11-09 19:59

本文主要是介绍【合规性检查-Fitness】基于Token重演的拟合度评估方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

我们继续对合规性检查的质量维度fitness进行介绍,本次介绍最为经典的拟合度指标计算方法-基于Token重演的拟合度指标检测方法。

 1.背景

        上节我们介绍了基于完全解析的拟合度计算评估方法,基于完全解析的拟合度计算评估方法存在轨迹层面的解析只能简单地判断轨迹是否符合模型,事件层面的解析相较于轨迹层面的能更大程度地判断轨迹的符合程度,但是前序事件对后续事件的判断有很大的影响等问题,为此提出了基于Token重演的拟合度评估方法,该方法是由A. Rozinat,和W.M.P. van der Aalst在2008年提出的方法,该方法是基于Petri网的引发规则进行的。

在介绍此方法之前,我们先简单地介绍下Petri网的引发规则。

上图中只有start库所中有token(图中的小黑点),一个带标识的Petri网的动态行为可以用所谓的发生规则(fire rule)来定义。如果一个变迁的所有输入库所都含有托肯,那么这个变迁是使能的。一个使能的变迁可以发生(fire) ,此时从每个输入库所中消耗一个托肯,并在所有输出库所中生产一个托肯。

因此,变迁a在标识[start]使能,将托肯转移到标识[p1,p2],注意减少一个托肯的同时增加了两个托肯。在标识[p1,p2]上,变迁a不再使能。然而,变迁b,c,d使能,从标识[p1,p2]经变迁b发生,将得到标识[p2,p3].此时,d仍然使能,但b和c不再使能。由于含有变迁f的循环结构存在,该Petri网有无穷多个由[start]开始并在[end]终止的发生序列。

2.相关案例介绍

2.1 示例事件日志

给定一个事件日志L,包含的信息如下表所示,L中共有1391条轨迹,21条轨迹变体(不重复的轨迹数)。例如,在轨迹1=<a,c,d,e,h>中有455个案例,在轨迹2=<a,b,d,e,g>中有191个案例等。

2.2 示例流程模型

给定四个对应的流程模型,如下图所示,各Petri网模型的具体情况如下所示:

Petri网N1是对上述示例日志L应用基础α算法发现的流程模型

Petri网N2相对于N1是一个顺序模型,需要在活动d前进行活动b或者活动c,有些示例日志L中的轨迹不能被表示;

Petri网N3中没有选择结构,即要求总是被拒绝,在示例日志L中的大部分轨迹不能被表示出来;

Petri网N4是一个“花型模型”的变体:只要求轨迹以a开始,以g或h结束,很明显,示例日志L中的所有轨迹都能够被N4表示。

3.轨迹在模型上的Token重演拟合度过程

为了解释这一思想,我们引入了四个计数器:p(产生的托肯)、c(消耗的托肯)、m(缺失的托肯),r(遗留的托肯)我们举2个例子来具体说明此方法。

3.1 轨迹1在模型N1上的重演步骤(完全重演)

首先我们先对上述事件日志L中的轨迹1=<a,c,d,e,h>在模型N1上进行重演,请注意,轨迹1是可以完全被重演,也就是拟合度为1。

我们逐步分析重演的步骤,先关注p(产生的托肯)和c(消耗的托肯)。

(1)开始时,p=c=0且所有库所是空的,接着环境(一般Petri网有一个初识标记用于触发规则)为开始库所start产生一个托肯,所以此时p的计数器增长:p=1。

(2)现在我们需要重演轨迹1=<a,c,d,e,h>,首先触发变迁a,这是可能的,因此变迁a消耗了一个托肯并产生了2个托肯,c计数器增长1,且p计数器增长2,。所以,在触发变迁a后p=3,且c=1。 

(3)下一步,我们重演第二个事件(c),触发变迁c,导致p=4且c=2。

(4)在重演第三个事件(d)后,p=5且c=3。

(5)在重演第四个事件(e)后,p=6且c=5。

(6)重演最后一个事件(h),触发产生的结果是p=7且c=6,。最后,环境从终止库所中消耗了一个托肯。因此,最终的结果是p=c=7且m=r=0.

很明显,当重演轨迹1时没有问题,即没有缺失或者遗留的托肯(m=r=0)

因此,在模型N上的一条轨迹为\sigma的拟合度定义如下:

fitness(\sigma ,N)=\frac{1}{2}\left ( 1-\frac{m}{c} \right )+\frac{1}{2}\left ( 1-\frac{r}{p} \right )

式子中,第一部分计算的是缺失的托肯(m)与消耗的托肯(c)的数量比,如果没有缺失的托肯(m=0),则1-m/c=1;如果所有消耗的托肯都缺失(m=c),则1-m/c=0。同样,如果没有遗留的托肯,则1-r/p=1;如果所有生产的托肯实际上都没有被消耗,则1-r/p=0。我们对缺失和遗留的托肯使用相等的惩罚。根据定义:0\leqslant fitness(\sigma ,N)\leq 1

用上述公式计算fitness(\sigma1,N1)=1/2(1-0/7)+1/2(1-0/7)=1,因为没有缺失或遗留的托肯。

接下来,我们考虑不能够被适当重演的轨迹。

3.2 轨迹3在模型N2上的重演步骤(不完全重演)

下面我们介绍在工作流网N2上重演轨迹3=<a,d,c,e,h>的过程。

(1)开始,p=c=0且所有库所都是空的。然后环境为开始库所生成一个托肯,且p计数器被更新:p=1。

 (2) 第一个事件(a)能够被重演,在触发a之后,计数器为p=2、c=1、m=0且r=0.

 

(3) 接着,我们试着重演第二个事件,这是不可能的,因为变迁d没有被使能,为了触发d,需要在库所p2中加入一个托肯,并记录缺失的托肯,也就是说,m计数器值增加,p和c计数器像平常一样被更新。因此,触发d之后,计数器值为p=3、c=2、m=1、r=0。我们也标记库所派p2来记录缺失了一个托肯。

 

 (4) 然后,我们重演接下来的3个事件(c、e、h)。与之符合的变迁被使能,所以我们只需要更新p和c计算器。在重演完最后一个事件后,有p=6、c=5、m=1且r=0.

(5)在最后状态[p2,end],环境从终止库所消耗了托肯,1个托肯遗留在库所p2中,所以库所p2被标记,r计算器增长。所以最终p=c=6,且m=r=1。

有一种情况,d发生了,但是依据模型(m标签)不能发声;有一种情况是d应该发生,但依据日志(r标签)却没发生,此外,我们能够依据p、c、m和r从而计算工作流网N2上的轨迹3的拟合度:

fitness(\sigma2,N2)=1/2(1-1/6)+1/2(1-1/6)=0.8333

同理,fitness(\sigma2,N3)=0.6

4.整个事件日志对于模型的重演指标计算

上述说明了怎么具体分析一条轨迹的拟合度,而相同的方法可以推广到用于分析一个由多条轨迹组成的事件日志的拟合度。简而言之,就是计算所有产生的、消耗的、缺失的和遗留的托肯数总和,并且应用相同的公式。

fitness(L,N)=\frac{1}{2}\left ( 1-\frac{\sum_{\sigma \in L}^{}L(\sigma )\times m_N,\sigma }{\sum_{\sigma \in L}^{}L(\sigma )\times c_N,\sigma } \right )+\frac{1}{2}\left ( 1-\frac{\sum_{\sigma \in L}^{}L(\sigma )\times r_N,\sigma }{\sum_{\sigma \in L}^{}L(\sigma )\times p_N,\sigma } \right )

依照上述公式,我们计算出事件日志L和上述对应的4个流程模型的拟合度表示如下:

fitness(L,N1)=1,            fitness(L,N2)=0.9504

fitness(L,N3)=0.8797,    fitness(L,N4)=1

正如预期的一样,N1和N4可以没有任何问题地重演L(即拟合度为1)。fitness(L,N2)=0.9504,直观来看,L中有大约95%的事件可以在N2上被正确重演。可以从两方面理解:

1.事件日志L有0.9504的拟合度,也就是说,大约5%的事件是偏离的;

2.流程模型N2有0.9504的拟合度,也就是说,模型不能够解释观察到的行为中的5%。

第一种的角度是被用于模型被认为是规范和正确的时候,(即“现实不符合模型”)

第二种的角度是被用于模型是描述性的时候(即“流程模型不符合现实”)

5.结论

在流程模型上重演事件日志不仅仅局限于Petri网,任何包含可执行语义的流程模型表示法都允许重演,但当重演有静默活动的变迁或者重复任务的变迁时,通常会导致状态空间爆炸,因此需要更高级的重演技术。

下一讲我们将介绍基于对齐(Alignment)的重演技术-fitness。

参考文献:

1.《流程挖掘:业务过程的发现、合规和改进》,Wil van der Aalst著,王建民、闻立杰等译;

2.A. Rozinat, W.M.P. van der Aalst, Conformance checking of processes based on monitoring real behavior, Inf. Syst. 33 (1) (2008) 64–95.

如需进行相关的了解或者交流,欢迎私信或者加入QQ群:

这篇关于【合规性检查-Fitness】基于Token重演的拟合度评估方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/378211

相关文章

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

CentOS 7部署主域名服务器 DNS的方法

《CentOS7部署主域名服务器DNS的方法》文章详细介绍了在CentOS7上部署主域名服务器DNS的步骤,包括安装BIND服务、配置DNS服务、添加域名区域、创建区域文件、配置反向解析、检查配置... 目录1. 安装 BIND 服务和工具2.  配置 BIND 服务3 . 添加你的域名区域配置4.创建区域