基于多视角关联规则的事件日志异常分析及过滤方法
2023-06-22胡伟
摘 要:事件日志的预处理是过程挖掘的第一步,事件日志中存在的大量噪音、低频行为对过程挖掘造成了极大的困扰。以往的研究大多是从控制流角度出发,只考虑了活动之间的发生顺序,较少涉及活动所包含的数据属性。由此提出了在控制流关联规则的基础上进行数据流关联规则的挖掘方法,首先基于Apriori算法挖掘出具有高度依赖关系的活动集合,再从数据流角度对事件日志进行过滤。具体的实例分析和仿真实验验证了方法的有效性。
关键词:过程挖掘;关联规则;Apriori
中图分类号:TP391.9 文献标识码:A 文章编号:2096-4706(2023)02-0069-05
Event Log Anomaly Analysis and Filtering Method Based on Multi-View Association Rules
HU Wei
(School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan 232001, China)
Abstract: The preprocessing of event log is the first step of process mining. A lot of noise and low-frequency behavior in event log cause great trouble to process mining. From the perspective of control flow, most of the previous studies only consider the sequence of occurrence among activities, and rarely involve the data attributes contained in activities. Thus this paper puts forward the mining method of data flow association rules based on control flow association rules. Firstly, based on Apriori algorithm, it mines the set of activities with high degree of dependency relationship. Then it filters the event log from the perspective of the data flow. The effectiveness of the method is verified by the actual example analysis and simulation experiments.
Keywords: process mining; association rule; Apriori
0 引 言
關联规则(Association Rules)反映了多个数据项之间的相互关系和依赖性,如最著名的“啤酒和尿布”营销案例,就是利用了两件商品之间的相互依赖关系,时至今日,关联规则已成为数据挖掘领域的一个重要技术。而过程挖掘就是对事件日志中的知识进行提取、挖掘,从而去发现、监控、优化实际流程。在实际应用中,过程挖掘所用到的事件日志往往不是完备的,常常包含大量的低频行为、噪音、异常,这对发现过程模型造成了严重的困扰,如何过滤掉事件日志中的噪音、无效低频行为是过程挖掘研究的热点。文献[1]提出一种名为“日志自动机”的技术来自动过滤低频行为。文献[2]提出了一种利用关联规则和模糊关联规则的方法对异常行为进行检测,判断其是欺诈行为的可能性。文献[3]则是从三个不同的视角控制流(活动)、时间(时间戳)、资源(活动执行资源)出发,检测事件日志中的异常行为。文献[4]重点从医疗领域的一系列实际流程出发,从数据流和控制流两个角度将事件日志与模型进行对齐,分析和分类了数据预期目的和数据使用环境相关的偏差,并提供了一种新的算法来识别不一致的用户行为。文献[5]采用了一种将过程挖掘和关联规则挖掘相结合的混合方法,通过关联规则算法产生的正负规则与事件日志进行一致性检查来判断异常行为,与单纯的过程挖掘方法相比,混合方法具有更低的错误发现率和更高的准确度,在该方法中,最佳的准确度取决于一定的置信阈值。
本文将活动的名称、资源、时间戳视为活动自带的内部属性,通过探索属性之间的关联规则筛选出合法活动与异常活动。本文不仅考虑单个活动是否符合流程规则,更进一步地考虑活动与活动之间的关联规则,并通过根据Apriori算法计算出的关联规则区分出合法行为和异常行为,并以此对事件日志进行过滤。
1 基本概念
定义1(事件日志):业务流程的执行以事件日志的形式记录下来,设一个事件日志L是一组执行迹的集合,日志迹t=
(1)ea:事件的执行活动,这里用活动名称表示。
(2)er:事件的执行资源,表示活动是由特定角色或系统执行。
(3)et:事件执行所需的时间,由活动的开始时间戳、结束时间戳以及相关的隶属度函数确定。
(4)es:活动执行的开始时间戳,任意eies>0∩
eies∈R。
(5)ec:活动执行的结束时间戳,任意eiec>0∩
eiec∈R。
例如表一中的迹t1中的事件e1=(A,Tom,0,5,Low),A代表e1执行的活动,Tom表示A活动是由Tom执行,0、5表示A活动的开始时间戳与结束时间戳,因为时间属性属于模糊数,为了方便定义与后续的计算,本文将时间分为三个等级,通过相关的隶属度函数确定其等级,Low表示该活动执行所需的时间等级为低。
图1中横坐标表示活动的执行所需的总时间,由ec-es计算所得。纵坐标表示隶属度。
根据图1的隶属度函数可以确定活动执行时间的等级,使用三种不同颜色的曲线表示三种不同的等级(Low,Middle,High),通过隶属度的不同确定其归属的等级。如表1中事件e1es=0,e1ec=5,事件e1的活动执行所需时间为5,通过隶属度函数可知e1et=Low,其隶属度为0.25。
定义2(规则):设R=(rc,rd)为关联规则的集合,其中rc=(rcea1,rcea2,…,rcean)代表控制流的关联规则,即只涉及活动与活动之间的关联规则。rd=(rdea,rder,rdet)代表数据流(包含资源er、时间et)的关联规则,用rdet∈{Tom,Eve,…,Mike,Alan}表示数据流规则包含的资源属性et,用rdet∈{Low,Middle,High}表示数据流规则包含的时间属性et。其中rc满足以下条件:
(1)rcea1是rcea2的前继活动,如对于迹L1={A,B,C},rcea1=A,则rcea2=B。
(2)对于一个规则rc,当且仅当n≥2是成立。
对于数据流规则rd,满足以下条件:
(1)rdea≠?且唯一。
(2)同一规则的资源和时间属性都归属于同一活动。
即单个数据流规则只考虑单个活动的内部属性之间的关联,而控制流规则更多是考虑多个活动(至少两个活动)之间的关联。
2 基于关联规则的异常分析
流程挖掘是一个新兴领域,专门用于从事件日志中记录的实际数据中获取知识[6]。但是事件日志中往往存在异常或者偏差,即噪音,噪音的存在会影响业务流程的结构。事件日志存储有关流程的重要信息。反过来,对这些信息的分析可以让公司追踪其系统中记录的实际数据和事件[7]。本文通过对控制流和数据流两个不同角度的关联规则分析活动与活动之间以及活动与资源、时间等属性的特定关系,首先在控制流角度挖掘出满足最小支持度(最小支持度根据实际结果人为设置)的频繁项集,计算其置信度是否达到设置的阈值(最小置信度)。对于达到最小置信度的规则将其称为合规规则[8],而对于只包含合规规则的事件日志还需对日志进行数据流的关联规则挖掘,从而将事件日志中的噪音进行过滤。
关联规则学习是一种无监督的数据挖掘方法,旨在发现大量数据中项与项之间相关关系[9]。在这里,本文将关联规则学习应用于过程挖掘领域,将多个相关联的事件中的活动集合视作一个项集,利用先验算法[10]满足阈值(最小置信度)的频繁项集,具体方法流程通过一个实际案例展示。
2.1 控制流关联规则挖掘
控制流描述了流程的执行顺序,是判断流程是否合规的第一步,首先给出支持度与置信度的相关定义。
定义3(支持度):支持度表示事件日志中该项集所占的比例,X代表一组活动集合(项集)中的前继活动,Y代表X的后继活动。对于项集(A,B)其支持度表示活动A、B共同在事件日志中出现的比例。
Support(X,Y)=P(X∪Y)
定义4(置信度):置信度表示前继活动出现后期后继活动出现的概率,项集(A,B)的置信度表示在A活动发生之后B活动发生的概率。
算法1 控制流关联规则挖掘方法:
输入:事件日志L={t1,t2,t3,…,tn},最小支持度Min_Supt和最小置信度Min_Conf;
输出:控制流关联规则;
步骤1:对事件日志L={t1,t2,t3,…,tn}进行预处理,计算日志中所有活动的出现次数,将活动出现的次数除以日志所包含的迹的总数,得到每个活动的支持度,大于等于最小支持度的活动作为初始的频繁一项集。
步骤2:将步骤1中得到的频繁一项集进行两两组合,组成不相同的二项集,再分别计算每个二项集的支持度,保留大于或等于最小支持度的二项集作为频繁二项集。
步骤3:不断重复步骤2的操作,将上个步骤得到的频繁K项集两两组合得到频繁K+1项集,如果频繁K+1项集为空则算法返回频繁K项集,如果频繁K+1项集只有一项,直接返回頻繁K+1项集,计算其置信度,大于等于最小置信度的频繁K+1项集作为算法结果返回,算法结束。
下面是其伪代码:
Algorithm 1 控制流关联规则挖掘算法
Input:事件日志L={t1,t2,t3,…,tn},最小支持度Minsupport,最小置信度Minconfidence
Output:控制流关联规则集合Rc={rc1,rc2,…,rcn}
1:for m = 1 → M do //m 表示迭代次数
2: C ? Findfrequentitem //初始化项集
3: for i = 1 → n do //循环遍历项集
4: supportCi ? Support(Ci) //计算当前项集的支持度
5: if then supportCi ≤ Minsupport
6: Item1 ? Item1 ∪ {Ci} //将低于最小支持度的项集划分到相应的集合
7: else
8: Item2 ? Item2 ∪ {Ci}
9: end if
10: end for
11: Cditem = cd1,cd2,…,cdn ? CandidateItem() ? RanAssort(Item2) //将频繁项集随机组合成频繁候选集
12: for i = 1 → n do
13: Confidcdi ? Confidence(cdi)//计算其置信度
14: if then Confidcdi ≤ Minconfidence //判断是否小于最小置信度
15: break Rc ? Rc ∪ {cdi}
16: return Rc //输出结果
2.2 数据流关联规则挖掘
由算法1得到的控制流规则从事件日志中提取出了相互关联、相互依赖的活动集合,在实际的应用流程中,如信贷申请流程中接受申请活动往往与核实申请人信息活动绑定在一起,又比如在医疗领域流程中病人在接受检查之后医生才能为其指定治疗方案。但控制流关联规则只能挖掘活动与活动之间的依赖关系,而对于流程中出现的数据流异常却无能为力,如在信贷申请流程中,大额贷款的申请需要经理同意才能得到批准,这就对活动的执行资源进行了限制,数据流关联规则针对活动与资源、时间等属性的依赖关系进行挖掘,有效解决了事件日志中数据流的异常行为。
算法 2 数据流关联规则挖掘方法:
输入:算法1得到的控制流关联规则,事件所包含的所有属性(资源er,活动ea,时间et);
输出:数据流关联规则;
步骤1:将控制流关联规则所包含的事件的所有属性作为初始的三项集,即包含活动ea、资源er、事件et的三项集。
步骤2:分别计算由不同资源和时间执行同一活动的事件的支持度,与算法1类似,保留大于等于最小支持度的三项集作为频繁项集。
步骤3:再通过计算频繁项集的置信度得到数据流关联规则,作为算法结果返回,算法结束。
下面是其伪代码:
Algorithm 2 数据流关联规则挖掘算法
Input:事件日志L={t1,t2,t3,…,tn},最小支持度Minsupport,最小置信度Minconfidence,活动ea,资源er,开始时间es,结束时间ec,数据流项集,df
Output:数据流关联规则集合Rd={rd1,rd2,…,rdn}
1:for m = 1 → M do //m 表示迭代次数
2: C ? Findfrequentitem //初始化项集
3: for i = 1 → n do //循环遍历项集
4: et ? Membership(es,ec) //通过隶属度函数确定执行时间 et 的级别
5: supportdf ? Support(ea,er,et) //计算当前项集的支持度
6: if then supportdf ≤ Minsupport
7: Item1 ? Item1 ∪ {df } //将低于最小支持度的项集划分到相应的集合
8: else
9: Item2 ? Item2 ∪ {df }
10: end if
11: end for
12: Df Cditem = cd1,cd2,…,cdn ? CandidateItem() ? RanAssort(Item2) //将频繁项集随机组合成频繁候选集
13: for i = 1 → n do
14: Confidcdi ? Confidence(cdi)//计算其置信度
15: if thenConfidcdi ≤ Minconfidence //判断是否小于最小置信度
16: break Rd ? Rd ∪ {cdi}
17: return Rd //输出结果
3 实例分析及仿真实验
为验证上述方法的可行性,以银行信贷申请流程为例,首先客户提交贷款申请,银行在收到贷款申请之后会核实客户的个人信息,检查其申请资料是否完整合格,申请通过之后客户需办理担保手续,将抵押物抵押给银行,银行会根据抵押物品类、价值的不同决定贷款金额的大小,而大额贷款的同意往往需要经理同意才能签订贷款合同,合同签订完银行才会发放贷款资金到客户的账号上。表2是给出的一个事件日志实例,其中e1表示提交贷款申请,e2表示核实客户信息,e3表示检查申请资料,e4表示根据贷款金额选择抵押品类,e5表示房屋抵押贷款,e6表示车辆抵押贷款,e7表示股权抵押贷款,e8表示评估抵押品的价值,e9表示办理担保手续,e10表示检查手续是否合规,e11表示贷款交由经理处理,e12表示贷款交由职员处理,e13表示签订贷款合同,e14表示检查贷款合同是否合规,e15发放贷款金额,e16表示拒绝贷款请求。
表2中的事件日志已按频数从大到小进行排序,首先对事件日志应用算法1进行控制流关联规则的挖掘,对于事件日志中所有的事件{e1,…,e16},将单个事件作为一项集,由定义3计算支持度,如二项集{e1,e4}的支持度为:
这里最小支持度设为0.15,大于等于最小支持度的予以保留,得到频繁一项集。再根据算法1将得到的频繁一项集两两组合成二项集,通过定义3计算二项集的支持度,剔除小于最小支持度的二项集得到频繁二项集。不断重复以上操作,可以得到频繁K项集,直到算法终止如图2所示。由于篇幅原因,这里只计算到频繁三项集,对于频繁三项集,通过定义4计算三项集{e7,e9,e10}的置信度,此处将e7视作X,(e9,e10)视作Y
同样的,此处将最小置信度设为0.2,关联规则(e7,(e9,e10))的置信度为0.55,即在事件e7发生之后(e9,e10)发生的概率为0.55,大于最小置信度,说明两者之间关联度较高,在控制流上具有很强的相互依赖性。
在对事件日志應用完算法1之后,对得到的控制流关联规则应用算法2,为了方便计算演示,只对关联规则(e7,(e9,e10))应用算法二,而包含该关联规则只有t3,表3给出了部分事件日志所包含的数据流属性。
表3还给出了规则中的事件在不同的执行资源和执行时间下所对应的支持度,最小支持度设为0.15,由表3可知,(e7,Eve,Hgih)的支持度远远小于最小支持度,这在实际应用中表现为往常股权抵押贷款是由Tom负责,而某次股权抵押贷款负责人不是Tom,变成了由Eve负责,这种异常行为控制流无法检测,因为在控制流角度其事件的执行顺序并无异常,只是事件的执行资源出现异常,而通过对数据流规则的挖掘,能够在控制流正常的情况下发现其属性异常。对于(e10,Alan,High),其执行时间出现了异常,因此其支持度也不满足条件。
为了验证本文提出的方法的有效性,将本文提出的方法与启发式挖掘方法的适合度进行了比较,适合度指的是流程模型重现事件日志所包含的流程行为的能力,适合度测量值为0表示无法重现日志中记录的任何行为,而值为1表示能够重现所有记录的行为。由图3的一致性度分析结果可知,本文提出的方法在事件日志实例数较多的情况下有着更好的表现。
由以上可知,通过对事件日志中控制流和数据流两个角度关联规则的挖掘,在基于发生频率的基础上计算不同规则(项集)的支持度以及置信度,通过对阈值(最小支持度、最小置信度)的设置,可以筛选出符合要求的事件日志。
4 结 论
本文在基于以往的研究基础上,给出了从控制流以及数据流两个角度进行关联规则挖掘对事件日志进行过滤和异常分析的方法,首先基于流程中活动的发生顺序以及频率挖掘事件日志中具有紧密关联的活动集合(项集),通过计算其支持度,也就是在事件日志中发生的概率,找出在事件日志中一起频繁发生的活动集合,即控制流关联规则。再对控制流关联规则中所包含的单个事件的活动、资源、时间等属性进行数据流关联规则的挖掘,这里的时间通过时间戳以及隶属度函数确定,从而解决了单一控制流规则无法发现属性异常的缺陷,有效减少了事件日志中的噪音对过程挖掘的影响。
本文是从两个不同角度对事件日志进行过滤,未来还要对过滤后的事件日志应用过程挖掘算法挖掘过程模型,再对挖掘出的过程模型与事件日志进行控制流与数据流两种角度对齐操作,从而更好的验证对模型精度的提升。
参考文献:
[1] CONFORTI R,LA ROSA M,HOFSTEDE A H M. Filtering out infrequent behavior from business process event logs [J].IEEE Transactions on Knowledge and Data Engineering,2016,29(2):300-314.
[2] SARNO R,SINAGA F,SUNGKONO K R. Anomaly detection in business processes using process mining and fuzzy association rule learning [J].Journal of Big Data,2020,7(1):1-19.
[3] B?HMER K,RINDERLE-MA S. Association rules for anomaly detection and root cause analysis in process executions [C]//International Conference on Advanced Information Systems Engineering.Cham:Springer,2018:3-18.
[4] ALIZADEH M,Lu X,FAHLAND D,et al. Linking data and process perspectives for conformance analysis [J].Computers & Security,2018,73:172-193.
[5] SARNO R,DEWANDONO R D,AHMAD T,et al. Hybrid Association Rule Learning and Process Mining for Fraud Detection [J].IAENG International Journal of Computer Science,2015,42(2):59-72.
[6] LEE C K H,TSE Y K,HO G T S,et al. Fuzzy association rule mining for fashion product development [J].Industrial Management & Data Systems,2015,115(2):383-399.
[7] DENISOV V,FAHLAND D,VAN DER AALST W M P. Repairing event logs with missing events to support performance analysis of systems with shared resources [C]//International Conference on Applications and Theory of Petri Nets and Concurrency. Cham:Springer,2020:239-259.
[8] NOLLE T,LUETTGEN S,SEELIGER A,et al. Binet:Multi-perspective business process anomaly classification [J/OL].Information Systems,2022,103:1-12[2022-06-20].https://arxiv.org/pdf/1902.03155.pdf.
[9] FANI SANI M,ZELST S J,VAN DER AALST W M P. Repairing outlier behaviour in event logs [C]//International Conference on Business Information Systems.Cham:Springer,2018:115-131.
[10] TAGHIABADI E R,GROMOV V,FAHLAND D,et al. Compliance checking of data-aware and resource-aware compliance requirements [C]//OTM Confederated International Conferences" On the Move to Meaningful Internet Systems". Berlin:Springer,2014:237-257.
作者簡介:胡伟(1997—),男,汉族,安徽安庆人,硕士在读,研究方向:过程挖掘。
收稿日期:2022-07-26
基金项目:国家自然科学基金项目(61572035,61402011)