【过程发现算法2】Inductive Miner-InFrequency(基于频次的归纳式挖掘算法)

本文主要是介绍【过程发现算法2】Inductive Miner-InFrequency(基于频次的归纳式挖掘算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Inductive Miner-Infrequency(基于频次的归纳式挖掘)是在上一节Inductive Miner的基础上进行改进的算法,由sander改进并完善,接下来,我们将详细地介绍这个算法。

1. 背景介绍

关于infrequent的解释:在大多数现实生活中的事件日志中,一些轨迹很少被采用,或者轨迹的不同之处仅在于不经常发生的活动。

如果模型中包含不常见的行为,可能会牺牲简单性(simplicity),如果模型中排除不常见的行为,可能会牺牲适合性(fitness)。幸运的是,帕累托原则(the Pareto principle,也称为8020规则)通常适用于事件日志。通常,80%的观察到的行为可以用一个模型来解释,这个模型只占描述所有行为所需模型的20%80%模型展示了过程中的“高速公路”。

为了获得80%的模型,传统的方法是在发现模型之前对日志进行全局过滤

在本文中,我们提出了这种方法的扩展,称为Inductive Miner - infrequent (IMi),旨在快速发现一个合理的80%模型。我们IM的所有步骤中引入了不常见行为过滤器(infrequent behaviour filters),这样就可以在本地过滤不常见的行为

2.算法介绍

具体做法:通过在IM的所有步骤中添加不常见的行为过滤器来引入IMi

轨迹和事件的频率被IM忽略,但被IMi考虑在内,以区分频繁和不频繁的行为.

参数:K表示用户定义的介于01之间的阈值,用于区分频繁和不频繁的行为

1.操作符上的过滤器和切割选择步骤;

2.基本案例上的过滤器

3.日志分割上的过滤器

2.1  操作符上的过滤器和切割选择步骤

(1)启发式方法过滤

  L1=[<a, b, c, a, b, e, >50, <a, b, f, e >100, <d, e, f >100, <d, f, e >100, <d, e, d, f >1]

 说明

IMi过滤只包含最频繁边的直接跟随图。如图a所示,与e的其他输出边相比,边(ed)相对不频繁,所以边<e,d>被过滤掉。如果一个节点的输出边的频率小于该节点最强输出边的频率的k倍,则该节点的输出边太不频繁在切割×、→和循环之前,在IMi中过滤掉所有不常见的边缘被过滤掉

(2) 最终跟随关系图

  L2=[<a, c, d, e, b>, <a, b, a, e , d, c>, <a, e, c, b, d>, <a, d, b, c, e >]

说明:如下图b所示, 由于b的所有输出边缘都具有频率1,因此k的任何值都不能过滤边(ba)

若采用图c的最终跟随图,则能有效地过滤掉边<b,a>。

类似于弱序关系,IMi使用最终跟随图,这是直接跟随关系的传递闭包:当且仅当a后面跟b在日志中的某处时,才存在边(ab)

2.2 基本案例上的过滤器

(1) 单个活动

说明:如图所示, 分割的子过程L1和L2重演一个过程模型,则存在如下问题:

L1中,所有的轨迹都很频繁,(flower model)花型模型显然是最好的选择。然而,在L2中,只有<a>是频繁的,a最能代表频繁的行为。

选择任一选项都会影响质量维度:若选择<a>,L1会牺牲fitness,若选择一个花型模型,L2会牺牲精度precision。只有当日志每个轨迹中a的平均出现次数足够接近1(取决于相对阈值k)时,IMi才会发现a

(2) 空轨迹

说明:事件日志L通过分割运算符得到三个子日志L1,L2,L3,子日志L2中存在一条空轨迹,其频次远远小于其他的轨迹的频次,如果不采用过滤,将会影响模型精度。 

2.3 日志分割上的过滤器

 说明:在日志上进行的分割,四个符号依次表示:选择、顺序、并发、循环,在日志层面四种切分运算符满足的格式如图中所示。

3.工具插件

(1)使用prom6运行的插件svn下载地址:prom - Revision 46111: /Packages/InductiveMinerDeprecated/Trunk (tue.nl)

运行插件界面图:

(2)使用pm4py调用Inductive Miner算法的链接地址:

PM4Py - Process Mining for Python (fraunhofer.de)

 4.总结

IMi通过引入了不常见行为过滤器,将轨迹和事件的频次考虑在内,区分频繁和不频繁的行为,在三个层面上应用了行为过滤器,相比于基础的Inductive Miner,更能精准地发现过程模型。

参考文献:Leemans S J J, Fahland D, Van Der Aalst W M P. Discovering block-structured process models from event logs containing infrequent behaviour[C]//International conference on business process management. Springer, Cham, 2013: 66-78.

下一讲将介绍最基础的过程挖掘算法Heuristic Miner(启发式挖掘算法)。

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

这篇关于【过程发现算法2】Inductive Miner-InFrequency(基于频次的归纳式挖掘算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot项目注入 traceId 追踪整个请求的日志链路(过程详解)

《SpringBoot项目注入traceId追踪整个请求的日志链路(过程详解)》本文介绍了如何在单体SpringBoot项目中通过手动实现过滤器或拦截器来注入traceId,以追踪整个请求的日志链... SpringBoot项目注入 traceId 来追踪整个请求的日志链路,有了 traceId, 我们在排

Spring Boot 3 整合 Spring Cloud Gateway实践过程

《SpringBoot3整合SpringCloudGateway实践过程》本文介绍了如何使用SpringCloudAlibaba2023.0.0.0版本构建一个微服务网关,包括统一路由、限... 目录引子为什么需要微服务网关实践1.统一路由2.限流防刷3.登录鉴权小结引子当前微服务架构已成为中大型系统的标

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Java中对象的创建和销毁过程详析

《Java中对象的创建和销毁过程详析》:本文主要介绍Java中对象的创建和销毁过程,对象的创建过程包括类加载检查、内存分配、初始化零值内存、设置对象头和执行init方法,对象的销毁过程由垃圾回收机... 目录前言对象的创建过程1. 类加载检查2China编程. 分配内存3. 初始化零值4. 设置对象头5. 执行

SpringBoot整合easy-es的详细过程

《SpringBoot整合easy-es的详细过程》本文介绍了EasyES,一个基于Elasticsearch的ORM框架,旨在简化开发流程并提高效率,EasyES支持SpringBoot框架,并提供... 目录一、easy-es简介二、实现基于Spring Boot框架的应用程序代码1.添加相关依赖2.添

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程

《SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程》本文详细介绍了如何在虚拟机和宝塔面板中安装RabbitMQ,并使用Java代码实现消息的发送和接收,通过异步通讯,可以优化... 目录一、RabbitMQ安装二、启动RabbitMQ三、javascript编写Java代码1、引入

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》:本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程

redis群集简单部署过程

《redis群集简单部署过程》文章介绍了Redis,一个高性能的键值存储系统,其支持多种数据结构和命令,它还讨论了Redis的服务器端架构、数据存储和获取、协议和命令、高可用性方案、缓存机制以及监控和... 目录Redis介绍1. 基本概念2. 服务器端3. 存储和获取数据4. 协议和命令5. 高可用性6.

PLsql Oracle 下载安装图文过程详解

《PLsqlOracle下载安装图文过程详解》PL/SQLDeveloper是一款用于开发Oracle数据库的集成开发环境,可以通过官网下载安装配置,并通过配置tnsnames.ora文件及环境变... 目录一、PL/SQL Developer 简介二、PL/SQL Developer 安装及配置详解1.下