基于混合人工免疫算法的流程挖掘事件日志融合方法-徐杨 , 袁峰 , 林琪 , 汤德佑 , 李东.pdf

上善若水

183

21页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2018,29(2):396−416 [doi: 10.13328/j.cnki.jos.005253] http://www.jos.org.cn

基于混合人工免疫算法的流程挖掘事件日志融合方法

∗

徐

杨

袁

峰

林

琪

汤德佑

李

东

(华南理工大学软件学院,广东广州 510006)

(广州中国科学院软件应用技术研究所,广东广州 511458)

通讯作者: 李东, E-mail: cslidong@scut.edu.cn

摘要: 流程挖掘是流程管理和数据挖掘交叉领域中的一个研究热点.在实际业务环境中,流程执行的数据往往

分散记录到不同的事件日志中,需要将这些事件日志融合成单一事件日志文件,才能应用当前基于单一事件日志的

流程挖掘技术.然而,由于流程日志间存在着执行实例的多对多匹配关系、融合所需信息可能缺失等问题,导致事件

日志融合问题具有较高的挑战性.对事件日志融合问题进行了形式化定义,指出该问题是一个搜索优化问题,并提出

了一种基于混合人工免疫算法的事件日志融合方法:以启发式方法生成初始种群,以人工免疫系统的克隆选择理论

作为基础,通过免疫进化获得“最佳”的融合解,从而支持包含多对多的实例匹配关系的日志融合;考虑两个实例级别

的因素——流程执行路径出现的频次和流程实例间的时间匹配关系,分别从“量”匹配和“时间”匹配两个维度来评

价进化中的个体;通过设置免疫记忆库、引入模拟退火机制,保证新一代种群的多样性,减少进化早熟几率.实验结

果表明:该方法能够实现多对多的实例匹配关系的事件日志融合的目标,相对于随机方法生成初始种群,启发式方法

能够加快免疫进化的速度.另外,针对利用分布式技术提高事件日志融合性能,探讨了大规模事件日志分布式融合中

的数据划分问题.

关键词: 事件日志融合;流程挖掘;人工免疫系统;日志预处理

中图法分类号: TP181

中文引用格式: 徐杨,袁峰,林琪,汤德佑,李东.基于混合人工免疫算法的流程挖掘事件日志融合方法.软件学报,2018,29(2):

396−416. http://www.jos.org.cn/1000-9825/5253.htm

英文引用格式: Xu Y, Yuan F, Lin Q, Tang DY, Li D. Merging event logs for process mining with a hybrid artificial immune

algorithm. Ruan Jian Xu e Bao/Jou rnal of Software, 2 018,29(2 ):396−416 (in Chinese). http://www.jos.org.cn/1000-9825/5253.ht m

Merging Event Log s for Process Mining with a Hybrid Artificial Immune Algorithm

XU Yang

, YUAN Feng

, LIN Qi

, TANG De-You

, LI Dong

(School of Software Engineering, South China University of Technology, Guangzhou 510006, China)

(Institute of Software Application Technology, Guangzho u & Chinese Acad e my of Sciences, Guangzhou 511458, Ch in a )

Abstra ct : Process mining is an active research topic in the cross field of process management and data mining. In an actual business

environment, the recorded data of a process execution that may be supported by different computer systems is scattered into different

event log files. It is necessary to merge the scattered data into one single event log file wh en appl ying curr ent process mining techniques

∗ 基金项目: 国家自然科学基金(71090403); 广东省科技计划(2014B090901001, 2015B010103002, 2016B090918062, 2016B050

502001); 广州市科技计划(201604010127); 华南理工大学软件学院 985 学科建设基金(x2rjD615015III)

Foundation item: National Natural Science Foundation of China (71090403); Science and Technology Planning Projects of

Guangdong Province (2014B090901001, 2015B010103002, 2016B090918062, 2016B050502001); Science and Technology Planning

Projects of Guangzhou City (201604010127); Special Funds on “985 Project” Disciplinary Construction in School of Software

Engineering of South China University of Technology (x2rjD615015III )

收稿时间: 2016-10-10; 修改时间: 2016-12-12; 采用时间: 2017-01-07; jos 在线出版时间: 2017-03-24

CNKI 网络优先出版: 2017-03-24 17:09:33, http://kns.cnki.net/kcms/d etail/11.2560.TP.20170324.1709.012.html

徐杨等:基于混合人工免疫算法的流程挖掘事件日志融合方法

397

and tools for process mining. This mission is still challenging, however, because of the complex relationships between cases in two logs

and the possible lack of information for the merging. In this paper, event log merging for process mining is regard as a type of search and

optimization problems based on the formal definition, and a merging approach with a hybrid artificial immune algorithm is presented in

order to achieve the event log merging with many to many relationship between cases in the two event logs . In the merging approach, the

clonal selection principle is selected as its underlying principle, which requires the matching process to undergo iterations of clonal

selection, hypermutation and receptor editing in order to get the best solution. The algorithm starts from an initial population produced

with a heuristic approach. Two factors, occurrence frequency and temporal relation, are designed in the affinity function to evaluate the

individuals in the population. In addition, immunological memory and simulated annealing are exploited to make the artificial immune

merging jumping out from the t rap of local op tima. Experimental r esults show that th e hybrid algorithm has good performance in merging

logs with complex cases relationships, and the heuristic approach for initial population can speed the process of the evolution. This paper

also discusses the data dis tribution methods in which th e log merging problems can b e distribu ted.

Key words: event log merging; process mining; artificial immune system; log preprocessing

随着 Web 服务技术、Web 2. 0 技术和云计算技术的广泛应用,组织的业务变得越来越灵活,业务流程的执行

路径根据变化的业务需求、客户需求和人员技能在运行时动态地变化,不能通过建模方法预先明确,业务流程

越来越呈现非结构化和半结构化的特性. 目前,大多数流程分析研究工作都假设流程是结构良好(well-

structure d) 的.这种情形下,流程的理解和流程执行数据的分析变得十分困难

[1]

.流程挖掘(process mining)

[2]

结合

流程建模分析技术和数据挖掘技术,将信息系统执行过程中产生的流程日志看作是一个事件网,从这个事件网

中抽取流程知识,从而发现流程模型,识别流程执行的瓶颈,提供对流程执行的量化理解,为流程分析提供了一

条新的途径

[3]

在企业实际业务环境中,信息系统往往用于支撑流程的执行.但大部分情况下,这些信息系统并不管理整个

业务流程,而是处理流程中的某些活动.因此,流程执行数据被分散记录到不同的日志中,结果是日志数据逐渐

呈现出大数据的特性:物理分布的广泛性、数据格式的多样性、数据模型的非标准化以及语义的异构性等

[4]

然而,当前的流程挖掘技术或工具,比如 Heuristics Miner

[5]

、Generic Miner

[6]

、Distributed Process Mining

[7]

和

Conformance Checking

[8]

都是基于单个事件日志文件的.因此,对于分散在不同信息系统的日志数据,需要将其

集成为能够完整描述整个业务流程的单一日志数据文件,才能应用这些研究成果进行流程分析.

流程挖掘技术是以事件日志(event log)作为输入.在事件日志中,一个事件(event )表示流程中一个活动的执

行,每个事件都归属于某个流程执行实例,而且流程执行实例中的事件是有序的.一个事件日志包含而且仅包含

与某一个流程相关的事件.从数据源获得的原始流程日志需要经过事件抽取、实例识别等操作转换成事件日

志.事件日志的融合就是将多个事件日志文件融合成单一日志文件的过程,主要步骤包括:识别出不同日志中记

录的两个执行实例是不是属于同一业务流程的执行实例(本文称为全局流程执行实例),如果属于同一全局流程

执行实例,则根据流程执行实例中活动发生的时间先后顺序合并成一个全局流程执行实例,并将其写入新的日

志文件中.其中的关键是如何识别两个流程执行实例是不是属于同一全局流程执行实例,即如何在给定两个流

程执行实例集合上建立执行实例之间的匹配关系.

直观上看,可以通过比较某个或几个两个执行实例的属性来判断是否具有匹配关系,比如通过比较执行实

例的标识是否相同来确定;或者通过比较执行实例中活动属性,比如活动的时间戳来决定流程实例间是否存在

匹配关系.然而,实际情况要复杂得多.

事件日志融合问题复杂性的一个重要表现就是,实际的业务流程本身的灵活性导致两个日志中的执行实

例的匹配关系不是简单的一对一关系.表 1 是一个简化了的 IT 事件管理系统的日志片断 log1.在 IT 事件管理流

程中,IT 系统的用户向 IT 事件管理系统提交 IT 事件(incident ),IT 事件经过登记、分析后,就分派给 1 个或多个

IT 运维任务进行处理.运维任务分派后就被纳入任务管理系统进行管理.表 2 是一个简化了的任务管理系统的

日志片断 lo

g2.一个任务在其生命周期中经历新建、分配、执行、完成、评价及关闭多个阶段.

在 IT 事件管理流程中,通过分析,登记的不同 IT 事件如果产生的原因相同,则会将这些事件合并分派给同

一个任务来处置.表 1 中 IT 事件 I NCID201 60601 02(“ 无法访问邮件系统”)和 INCI D201 6 060113(“无法登录某业

of 21

免费下载

软件学报计算机技术

关注

评论