基于上下文感知的多角度业务流程在线异常检测方法

孙笑笑，侯文杰，沈沪军，应钰柯，俞东进+

(1.杭州电子科技大学 计算机学院，浙江 杭州 310018；2.复杂系统建模与仿真教育部重点实验室，浙江 杭州 310018)

0 引言

随着业务流程的日益复杂化，传统严格约束的结构化业务流程管理方法逐渐无法应对一些复杂的、任务执行需要依赖人力决策的应用场景，如医院诊断流程、保险理赔流程等[1]，为此部分企业启用了约束较为宽松的柔性业务流程管理技术来应对这类知识密集型的业务。柔性业务流程管理中的限制相对宽松，确保了业务流程管理系统的灵活性，但同时也导致流程执行风险的增加，给业务流程的目标实现带来更多风险[2]。通过异常检测技术[3-4]可以有效检测流程执行中的异常，帮助相关人员及早发现潜在的执行风险，进而采取相应的措施，对业务流程管理具有重要意义。

近年来，业务流程管理的重心不再局限于对事件日志进行线下分析，而更加关注如何为业务流程的执行提供在线支持。但对正在执行的流程实例进行在线异常检测并非易事，需要从多个流程角度进行考虑，例如控制流角度[5-7](当前实例中活动的执行顺序是否正常)、时间角度[8](活动的执行时间是否异常，流程实例的总执行时间是否超过预期等)等。目前，大多数异常检测的方法多从单一视角开展检测，存在异常检测不全面的问题。此外，大部分现有方法结果仅简单报告当前实例的执行是否异常，缺乏足够的解释信息帮助相关人员了解异常发生原因。

针对以上问题，本文提出一种基于上下文感知的多角度业务流程在线异常检测方法。为了让相关人员详细了解当前异常发生的原因，本文将业务流程中的异常情况分为行为异常、时间异常和属性异常3类。其中：行为异常从控制流视角出发，主要关注活动执行顺序的正确性，如流程执行过程中由于某个错误的操作而导致活动被重复执行；时间异常从时间视角出发，主要关注活动的持续时间以及实例总的执行时间是否合理，如当活动执行的持续时间是平时的几倍或实例的总执行时间超过预期等；属性异常从实例的其他属性值出发，主要关注属性状态是否正常，如从资源属性上看，若活动a被从未执行过它的资源r执行，这就属于偏离原有预设的行为，将被视为属性异常情况。此外，为了更好地模拟当前实例的真实执行环境，本文借助重演技术从事件日志中捕获了当前实例执行的行为上下文和数据上下文，并将其与深度学习方法相结合，建立了实时异常检测模型，有效提高了异常检测的性能。

1 相关工作

传统的业务流程异常检测通常借助一致性检查技术[5-7]来实现，即通过将日志中记录的执行轨迹与标准的参考流程模型进行对齐，进而检测是否存在异常。该类方法需要借助一个标准的参考流程模型，用来表征流程中全部的正常执行情况。如果不存在标准模型，则需要借助流程发现技术从事件日志中挖掘流程模型，但因为真实应用场景下的日志中通常包含异常执行信息，所以挖掘得到的模型并不完全标准，这限制了该类方法的应用。BEZERRA等[9]提出3种改进的异常检测方法：阈值算法、迭代算法和采样算法。其中：阈值算法通过设置一个异常阈值，并将一致性低于阈值的轨迹归为异常轨迹来实现异常检测；迭代算法则通过多次迭代并在每次迭代中删除一致性最低的轨迹来达到过滤异常的效果；采样算法通过采样来减少日志中包含异常轨迹的可能性，这一方法基于一个朴素的假设即日志中所包含的异常数据是少量的，因此通过采样得到的数据可以近似看成是不包含异常的，最后通过从采样日志中挖掘参考模型进行下一步的一致性检查。但以上3种方法都需要人为设置相关参数，因此方法的通用性不强。此外，一致性检查技术大都只能从控制流的角度观察异常，其目标是确保流程的执行没有偏离，即流程中活动的执行顺序没有出现异常，而忽略了存储在日志中大量的其他相关数据，这些数据可能存在某些不易发现的潜在风险。

不同于上述方法，ROGGE-SOLTI等[8]提出一种基于贝叶斯模型的异常检测方法，但该方法关注活动执行时间的异常检测，并未考虑流程执行中可能出现的其他异常。MANNHARDT等[10]提出一种利用多种成本函数实现的多角度一致性检查技术，可以检测活动执行顺序和活动部分属性的异常情况，但该方法需要借助一个标准的参考模型来实现异常检测。NGUYEN等[11]分别比较了使用决策树、K最近邻(K-Nearest Neighbor，KNN)和神经网络3种方法来检测异常的精度，但其效果衡量指标只有一种，实验结果并不全面。对于其他领域的异常检测工作，PIMENTEL等[12]对近年来提出的异常检测方法进行了详细的介绍和比较，并将其分为5类方法：基于概率论的检测方法、基于距离的检测方法、基于重构的检测方法、基于领域的检测方法和基于信息论的检测方法。其中：基于概率论的检测方法是基于对数据生成概率密度函数的估计；基于距离的检测方法包括聚类或最近邻方法；基于重构的检测方法可以在没有先验假设的情况下对数据分布进行建模，其思想是训练一个能够重建正常行为但不能重建异常行为的模型；基于领域的检测方法在不依赖于训练集中数据分布的属性的情况下，仅使用最接近的数据来确定新颖性边界的位置；基于信息论的检测方法一般会假设数据的潜在分布，基于信息论的新颖性检测方法往往要用一个敏感的度量来检测出数据集中新点的影响，如何选取信息理论测量方法是该类方法的主要缺点。

2 相关定义

2.1 事件日志

事件日志是由轨迹组成的一个集合，其中每条轨迹代表业务流程的一次执行，每条轨迹又由多个事件构成，每个事件记录流程执行某一活动的全部信息。业务流程事件日志中的相关概念的形式化定义如下：

定义1事件。 事件是事件日志中的最小单位，通常使用元组e=(a,caseID,eventID,ts,te,r,attr1,…,attrm)表示，其中：a为该事件对应的活动属性，caseId为该事件所属实例的id属性，eventID为事件id属性，ts为事件的开始时间戳属性，te为事件的结束时间戳属性，r是事件的执行资源属性，attr1,…,attrm为事件所拥有的一些额外属性，这些属性通常随着流程的不同有所区别。日志中的全部事件构成事件集E。

定义3前缀轨迹。 前缀轨迹是流程轨迹σ=的前l个事件构成的有序序列，其形式表达为PTr(σ,l)=，其中l表示截取事件在流程轨迹中的下标，也代表前缀轨迹的长度。

2.2 Petri网

Petri网是二部图的一个子类，由库所和变迁两类节点组成。其中：库所节点用圆圈表示，变迁节点用矩形表示，两种节点之间使用有向弧连接。

定义5输入集合，输出集合。 对于PN中的任意节点o(变迁节点或库所节点)，使用Upost(o)={j|(o,j)∈Arc}来表示其输出节点集合，使用Upre(o)={j|(j,o)∈Arc}来表示其输入节点集合。其中：库所节点的输入和输出集合中只包含变迁节点，变迁节点的输入和输出集合中只包含库所节点。

定义6使能状态，点火规则。 如果一个变迁满足其输入集合中的库所均含有至少一个托肯，则该变迁节点处于使能状态，公式如下：

∀pj∈Upre(ti),m(pj)≥1#。

(1)

处于使能状态的变迁可以被触发，触发后该变迁的输入集合中所有库所的托肯数量减一，输出集合中所有库所的托肯数量加一，该规则即点火规则。

2.3 长短期记忆网络

作为循环神经网络[13](Recurrent Neural Networks，RNN)的一种变体，长短期记忆网络[14](Long Short-Term Memory network , LSTM)成功地克服了RNN存在的部分缺陷，被广泛应用于语音识别、图片描述、自然语言处理等领域。如图1所示，在t时刻，LSTM单元的输入有3个：当前时刻的输入值xt、上一时刻LSTM单元的输出值ht-1以及上一时刻的单元状态Ct-1；LSTM单元的输出有两个：当前时刻LSTM单元输出值ht和当前时刻的单元状态Ct。LSTM之所以能克服远距离依赖是其利用3个门实现了对长期状态的控制。其中，遗忘门(forget gate)决定了上一时刻的单元状态将有多少保留到当前时刻；输入门(input gate)决定了当前时刻输入中将有多少有用信息被保存到单元状态中；输出门(output gate)用来控制单元状态中有多少将被输出作为当前的输出值。通过这3个门控，远距离的重要信息将被保存下来并作用到当前的输出值运算中。

3 方法描述

本文提出一种基于上下文感知的多角度异常检测方法(Multi-perspective online Anomaly Detection method based on Context awareness，MADC)，利用流程发现、轨迹重演、深度学习等相关技术得到一个最终的检测模型，实现对行为异常、时间异常和属性异常3类异常的在线检测。MADC的整体框架如图2所示，主要包括4个阶段：预处理阶段、上下文提取阶段、模型训练阶段和异常检测阶段。下面对每个阶段进行详细阐述。

3.1 预处理阶段

在预处理阶段，事件日志将被划分为训练集和测试集。本文将日志中发生时间较早的80%案例数据选为训练集，剩余的20%案例数据选为测试集，值得注意的是训练集中是包含异常执行案例的。

预处理阶段首先对训练集使用过程发现技术Split Miner[15]挖掘出用Petri网表示的流程模型。Split Miner是近年来新提出的一种流程发现算法，可以利用事件日志自动挖掘出完备的Petri网模型来表征业务流程。Split Miner相较现有的流程发现技术在性能上有较大的提升，其操作简单、执行时间快，是目前从事件日志中自动获取具备较高适应性和精度的流程模型的最佳算法之一[16]。预处理阶段获得的Petri网模型将在后面的阶段被使用。

3.2 上下文提取阶段

在上下文提取阶段，本文对日志中的上下文进行了初步细化，大体划分为两类：

(1)行为上下文，它考虑的是流程中活动执行顺序的上下文信息，即从控制流的视角观察到的当前活动执行的上下文信息。本文中行为上下文又包括局部行为上下文和全局行为上下文，其中局部行为上下文用来表示实例当前的状态，全局上下文用来表示流程当前的执行状态。

(2)数据上下文，它囊括了所有非控制流视角观察到的活动上下文信息，主要通过日志中的事件属性获取得到。数据上下文有效地弥补了行为上下文信息的单一性，本文主要考虑从组织视角和时间视角观察到的数据上下文信息。

3.2.1 行为上下文

行为上下文的提取主要借助于第一阶段获得的Petri网模型结合轨迹重演方法来实现。具体地，首先使用两个长度为(|P|+1)的向量vlbc和vgbc分别表示局部行为上下文和全局行为上下文。其中向量vlbc和vgbc中的第i位对应于PN中第i个库所中托肯的数量分布情况。不同的是vlbc表示的是单个实例独立执行时托肯在PN中的分布情况，而vgbc表示当前流程中所有一同执行的实例所产生的托肯分布情况。|P|+1位是用于接收未知活动执行产生的托肯，因为测试数据中可能包含了训练数据中未曾出现的活动。此外，本文对Petri网的点火规则进行了调整，即使用新的规则完成轨迹的重演过程。具体地，改变了使能状态的条件，当变迁节点对应的活动被执行，就认为该变迁节点已经是使能状态，而并不需要严格满足式(1)。随后将执行点火规则完成库所中托肯的转移，并得到轨迹在当前活动执行完之后的状态(即下一活动开始执行的行为上下文)。此外，本文允许vlbc和vgbc对应位置的托肯数量为负整数。

算法1行为上下文提取。

输入: 事件日志L,Petri网PN=;

输出: Elist//包含行为上下文信息的事件集。

01:As=getStartActivity(PN);Ae=getEndActivity(PN); APN=getActivitySet(PN)

02:Elist=SortEventByStartTime(L); vgbc=zeros(|P|+1)

03:FOREACH event e in ElistDO

04:T=getCurrentTraceByID(e.c)

05: IF e.a in AsDO

06:vlbc=zeros(|P|+1); Spre=Upre(F(e.a)); Spost=Upre(F(e.a))

07: FOREACH place p in SpreDO

08: Ip=getPlaceIndex(p);vlbc[Ip]=vlbc[Ip]+1; vgbc[Ip]=vgbc[Ip]+1

09: e.lbc=vlbc; e.gbc=vgbc; T.lastState=vlbc

10: ENDFOREACH

11: FOREACH place p in SpostDO

12: Ip=getPlaceIndex(p); vlbc[Ip]=vlbc[Ip]+1; T.nextState=vlbc

13:ENDFOREACH

14: ELSE IF e.a in APNDO

15: vlbc=T.nexState; vgbc=vgbc+T.nextState-T.lastState

16: e.lbc=vlbc; e.gbc=vgbc

17: Spre=Upre(F(e.a)) ; Spost=Upre(F(e.a))

18: FOREACH place p in SpreDO

19: Ip=getPlaceIndex(p); vlbc[Ip]=vlbc[Ip]-1;

20: ENDFOREACH

21: FOREACH place p in SpostDO

22: Ip=getPlaceIndex(p); vlbc[Ip]=vlbc[Ip]+1;

23: ENDFOREACH

24: T.lastState=T.nextState; T.nextState=vlbc

25: ELSE DO

26: vlbc=T.nextState; vgbc=vgbc+T.nextState-T.lastState

27: e.lbc=vlbc; e.gbc=vgbc; vlbc[|P|+1]=vlbc[|P|+1]+1

28: T.lastState=T.nextState; T.nextState=vlbc

29: ENDIF

30: IF e.a in AeDO

31: vgbc=vgbc-T.lastState

32: ENDIF

33:ENDFOREACH

34:RETURN Elist

依次遍历Elist中的每个事件并根据事件的实例ID属性找到其所属的轨迹T。然后对Elist中的每个事件执行以下迭代过程：对当前事件执行的活动进行判断，并根据判断结果执行不同的操作。

最后，迭代结束，返回包含行为上下文属性的事件集Elist。

3.2.2 数据上下文

由于行为上下文仅从控制流视角观察当前实例的执行，而事件日志中还记录了许多其他的信息，这些信息也可以为异常检测提供重要指示。例如时间属性可以帮助相关人员检测超时异常、资源属性可以帮助相关人员检测非法执行异常等。

本文提出的数据上下文主要包括时间上下文和属性上下文。通常事件的时间属性仅提供一个时间戳，因此本文对活动发生的时间戳进行了分析和处理，使其时间信息更加丰富，得到当前执行活动的时间上下文e.tcv=[h,m,d,weekday,tsct,td]。其中：h,m,d,weekday分别表示该时间戳对应的小时、月份、天以及星期的信息；tsct表示当前时间戳距该实例开始时间戳的时间间隔，其计算需要当前实例第一个执行活动的开始时间戳；td表示当前时间戳距当天凌晨的时间间隔。对于事件的其余属性，如常见的活动名、资源等，根据其属性值是否为数值划分为类别属性和数值属性。其中类别属性使用one-hot编码技术对其进行编码进一步转换为由0和1构成的向量，并与数值属性构成的向量合并得到属性上下文e.dcv。

3.3 模型训练阶段

为便于模型训练，需要对日志数据进行相应的编码。对于日志中的每个事件，使用一个向量来表示其完整的上下文信息，该向量由上一阶段获得的e.lbc(局部行为上下文)、,e.gbc(全局行为上下文)、e.tcv(时间上下文)、e.dcv(属性上下文)共4个向量级联而成。相应地，日志中的每条(前缀)轨迹都由一个二维矩阵表示，其中轨迹矩阵的每一行均由其拥有的事件所对应的事件向量构成。此外，由于(前缀)轨迹的长度各异，将统一设置长度来限制轨迹矩阵的行数(通常使用最长的轨迹的长度)。对于短的轨迹，本文使用仅包含0的事件向量对其进行填充，这些0数据将在模型训练的过程中被忽略。由于本文使用的是监督学习方法，这意味着需要对训练数据进行标记。对于训练数据中的每个(前缀)轨迹矩阵，其3个标签分别对应行为异常、时间异常以及属性异常。训练数据集可以表示如下：

D={(xtr1,[lb1,lt1,la1]),…,(xtrn,[lbn,ltn,lan])|n∈}。

(2)

式中：xtri是第i条轨迹对应的轨迹矩阵；lbi,lti,lai∈(0,1)是其对应的异常标签(即行为异常、时间异常和属性异常)，若lbi,lti,lai的值为1则表明当前轨迹拥有此类异常，若lbi,lti,lai的值为0则说明没有此类异常。这些训练数据将用于拟合一个最终的异常检测模型，当有新的输入信息输入该异常检测模型时，将输出其异常检测结果。

本文使用LSTM构建异常检测模型，包含两种架构方式：第一种架构是分别单独训练这3种异常的检测模型；第二种架构是则是让这3个异常检测模型共享隐藏层，但拥有各自独立的输出层。如图4所示，单一模型和共享模型的输入均是上文提到的轨迹矩阵，其包含当前执行轨迹的上下文信息，且所有模型的隐藏层都由多个LSTM单元堆叠构成。图4中flb、flt和fla分别对应3类异常结果的输出，flb用于行为异常检测，flt用于时间异常检测，fla用于属性异常检测。若输出结果为1，表示当前执行出现了该类异常；若输出结果为0，表示当前执行过程中不存在该类异常情况。本文将分别尝试这两种架构方式。此外，为解决训练集中类别样本不平衡的问题，本文采用文献[17]中的方法，使用加权交叉熵函数作为模型的损失函数。

3.4 异常检测阶段

在异常检测阶段，首先需要对待检测的轨迹进行上下文提取，然后将其编码为相应的数据形式并输入到由第三阶段训练得到的异常检测模型中。最后，检测模型的输出结果将被发送给相关人员用于决策，同时最终的判决结果和当前轨迹数据将被保存下来用于检测模型的增量更新，以提高检测模型的准确性。

4 实验分析

为验证本文提出的基于上下文感知的多角度业务流程在线异常检测方法的效果，本章将使用真实日志进行实验，并对实验结果进行分析和评估。为验证本文提出方法的有效性，本文选择常用的4个指标：准确率、精确率、召回率以及F1分数来衡量检测的性能。

4.1 实验设置

本文实验配置如下：操作系统：Ubuntu 18.04；处理器：英特尔©酷睿 i9-7900X (3.30GHz，64GB，10核)；GPU: GeForce GTX 1080 Ti；TensorFlow版本：1.15.0；Keras版本：2.2.4。对于LSTM模型训练中的超参选择使用的是随机搜索法[18]，各个参数的选择范围如表1所示。

4.2 数据集

本文选取4个真实的业务流程的历史日志作为验证实验的数据集(来源于4TU Centre for Research Data(https://data.4tu.nl/repository))。4个数据集的统计信息如表2所示，相关介绍如下：

(1)Helpdesk。该数据集来源于意大利某软件公司服务台的票务管理流程。

(2)BPIC2012。该数据集来源于荷兰某财政机构，记录了申请贷款业务的流程的相关信息。它是3个相互交织的子流程的合并，因而该日志又可以进一步分为3个日志BPIC2012_A，BPIC2012_O，BPIC2012_W。

表1 LSTM模型的超参数取值范围

本文利用以上4个真实流程的执行日志和人为生成的异常来评估异常检测性能和本文所提出方法的可行性。由于真实日志中未提供有关实际异常的信息，有必要人为生成异常。为此本文执行了以下操作来生成异常数据。对于行为异常执行以下两种突变操作:①活动插入：随机选择一个活动插入到当前轨迹中；②调整活动执行顺序：将当前轨迹中的一个活动随机移动至轨迹的另一个位置。对于时间异常执行以下两种标记：①活动执行时间异常：对同一类活动，将对事件日志中该类活动的执行时间进行统计，得到其分布图，并选择其中执行时间最久的部分事件进行异常标记；②实例执行时间异常：首先根据实例中执行活动的种类对实例进行分类(即拥有相同执行活动集合的实例将被划分为同一类)，然后分别统计出每一类中执行时间最久的部分实例进行异常标记。对于属性异常我们从日志中随机选择事件并对其执行资源进行替换，新的执行资源在原有日志中从未执行过该类活动。本文对每个数据集使用上述异常生成方法人工生成异常，每类异常的占比为20%，其中某一实例中可能同时包含多种异常。

表2 数据集信息统计表

4.3 结果分析

为验证两种LSTM异常检测模型架构的性能，对两种模型架构方案的检测结果进行了对比。SingleM表示第一种模型架构方案(单一模型)，ShareM表示第二种模型架构方案(共享模型)。此外，为验证本文提出的基于重演提取的行为上下文对检测结果的影响，本文为训练模型分别生成了两类数据样本。其中第一类样本(withBC)包含本文提出的行为上下文信息和数据上下文信息，而第二类样本(withoutBC)仅包含数据上下文(以往的研究工作只使用数据上下文信息)。实验结果如图5所示。对于两种模型架构方案，由图可见，共享模型(shareM)在大部分情况下检测效果比起单一模型(sirgleM)的检测效果略好，这是因为通过共享隐藏层，可以让模型学习到3类异常之间的一些内部联系。此外，由图5可以看到，加入本文提出的行为上下文信息(withBC)后，3类异常检测精度均有不同程度的提高，这证明了本文提出的基于重演技术的行为上下文提取对异常检测十分有效。具体地，因为基于重演的方法借助Petri网的状态来表征实例执行时的上下文信息对日志中复杂的行为结构(如并行结构)有很好的表现能力，所以能为行为异常的检测提供更多精确的信息。对于时间异常，行为上下文的加入也能提高其精度，因为全局行为上下文能在一定程度上反映出当前流程的工作负载，而在当前流程的工作负载越大时出现时间异常的概率也越大。属性异常的检测效果在加入行为上下文之后也得到了较好的提升，这是由于属性的异常与其对应的活动关系密切，活动执行的上下文信息能在某种程度上反映活动的类型。综合实验结果来看，时间异常检测在3类异常检测中表现效果最差，这是由于本方法输入数据中时间相关信息总体不够丰富，此外不同活动的持续时间过于分散也导致其精度数据变化不明显。

另外，由于现有的异常检测方法类型单一，且异常划分方法各异，无法将其与本文的异常检测方法展开比较，因此本文选用通用的分类模型支持向量机(Support Vector Machines, SVM)[12]，KNN[19]和决策树(Decision Tree,DT)[20]作为对比算法来进一步证明本文提出方法的有效性。在本次对比实验中，选择上一轮实验中(即图5中)效果最佳的检测模型，即包含行为上下文信息的共享模型ShareM(withBC)进一步与SVM、KNN、DT三种算法进行比较。此外，本次仅使用两个重要的指标召回率和F1分数作为衡量指标。其中召回率衡量在全部异常案例中被检测到的异常案例所占的比例，而F1分数则综合平衡准确性和召回率两个指标。实验结果如表3所示，其中最佳结果以粗体标记。从表中可以看出，本文方法在F1分数上均取得最好效果。这是因为LSTM可以学习同一实例中活动之间的远程依赖关系，并保留之前执行的重要信息，从而充分利用上下文信息进行异常判断。在召回率上，本文方法对行为异常的检测均取得了最佳的效果，这是由于本文方法利用了重演技术提取的行为上下文，使得检测模型得到的信息更加全面。而在时间异常和属性异常的检测上，本文方法仅在大部分数据集上取得了最优效果。本文方法未在这两类异常的检测上取得最佳效果，其原因是属性异常和时间异常都属于点异常，它们与实例中执行活动的相关属性紧密相关，而过长的执行轨迹可能导致一部分重要信息被忽视，进而影响检测结果。

表3 异常检测结果对比表

5 结束语

针对流程执行过程中的异常检测问题，本文提出一种基于上下文感知的多角度在线异常检测方法。该方法利用重演技术捕获当前实例执行的行为上下文信息，并将其与事件的数据上下文信息结合输入神经网络模型中来实现对当前正在执行实例的异常情况的检测。此外，为了帮助相关人员更好地理解异常发生的原因，本文将异常情况细化为3类异常，即行为异常、时间异常和属性异常。最后，采用真实日志对算法进行仿真实验，实验结果表明本文提出的方法在召回率上比SVM、KNN和DT分别提高了18.5%、19.8%和8.4%；在F1分数上分别提高了15.9%、25.4%和8.4%。

在未来的工作中，将尝试把复杂的人力资源因素(如员工的工作负载、员工的技能熟练度、员工的搭配等)作为上下文信息融入检测模型。此外，还考虑实现异常情况的可视化分析，并对流程异常的风险等级展开更细致的评定。