基于前缀树的业务流程增强预测方法_孙大志.pdf

引言对企业而言，找到一种能够预测业务流程的未来行为的技术非常重要，企业需要在流程实例运行之前识别出不符合标准的异常事件，以便能够根据相应的信息及时找到应对措施来避免损失，而预测性流程监控1主要从事件日志中训练模型，用来预测一个正在进行的案例在未来的执行情况，可以为企业提供所需预测技术，是目前业务流程管理领域的一个研究热点。针对不同的预测任务，对预测性流程监控技术的分类有所不同，现有预测性流程监控技术论文主要分为三类：第一类侧重于时间方面的预测，Aalst等人通过从事件日志中构建带注释的变迁系统来预测流程的剩余时间2。Rogge-Solti等人使用了一种特定类型的随机Petri网，它可以捕获任意持续时间的分布，以此来预测一个案件的剩余时间3。Aburomman等人提出了一种新的基于向量和基于ATS的预测业务流程中的剩余时间方法，该方法考虑了与过程执行相关的结构特征或属性，如频率、重复、周期等4。Verenich等人将预测分解为更基本的向量，在活动的级别上预测性能指标，以一种透明的白盒方法预测正在进行的过程实例的剩余周期时间。第二类侧重于预测活动的结果。这类方法目标在于产生预测和建议的方法，以减少风险5。Conforti等人提出了一种技术，以支持过程参与者做出风险知情的决策，目的是降低过程风险。通过遍历从过去流程执行日志中生成的决策树来预测风险6。Pika等人通过识别和利用事件日志中可观察到的统计指标来预测与时间相关的过程风险，这些指标强调了超过最后期限的可能性7。Teinemaa等人将结构化数据和非结构化数据结合以尽早预测出违约客户无法在合理期限内支付任何款项的情况8，Maggi等人提出了一个框架，根据给定情况下执行过的活动序列和案例中最后执行过的活动的数据属性值来预测案例（正常与异常）的结果1。第三类侧重于预测未来事件的延续。Lakshmanan等人提出了一个马尔可夫预测模型来建立一个特定于实例的概率模型，该模型可以预测给定一个运行过程实例的实例中特定事件的概率9。Polato等人提出了使用简单回归、上下文信息回归和数据感知转换系统来预测剩余时间和未来活动的序列10。Evermann等人提出了一个其中有两个通过反向传播训练的隐藏层的循环神经网络（Recurrent NeuralNetwork，RNN）11,12，而Tax等人利用长短期记忆（Long Short Term Memory，LSTM）和一个基于活动和时间戳的编码用来预测事件的延续13。Taymouri等人提出了一种对抗性训练框架通过同时训练两个神经网络,一个作为生成器，一个作为鉴别器，让他们相互对抗学习使得生成器能够更好地解决下一个事件预测的问题14。Lin L等人设计了一个组基于前缀树的业务流程增强预测方法孙大志（安徽理工大学数学与大数据学院，安徽淮南232001）收稿日期：2022-09-27基金项目：国家自然科学基金(61402011)摘要：预测性业务流程监控主要利用已经发生的流程执行的数据，目前的主流方法是通过建立深度学习模型预测在线流程的执行情况。现有的流程预测深度学习方法主要利用历史事件日志数据来学习模型进行预测，较少考虑日志间的行为关系，本文通过挖掘流程执行期间日志之间的行为关系,以帮助提高预测模型的质量。将挖掘出的日志间的行为关系使用前缀树进行表示，并使用现有的基于深度学习的业务流程预测模型，在结果预测阶段通过前缀树结构筛选符合行为关系的预测结果提供决策支持，以此提高预测结果的精确度，并在事件日志中与基线方法进行比对，在预测下一个活动以及预测后缀方面，预测精度均有所提高。关键词：业务流程监控；深度学习；信息挖掘；前缀树；决策支持中图分类号：TP391.9文献标识码：A文章编号：1673-260X（2023）02-0044-06Vol.39 No.2Feb.2023赤 峰 学 院 学 报（自 然 科 学 版）Journal of Chifeng University(Natural Science Edition)第39卷第2期2023年2月44-DOI:10.13398/ki.issn1673-260 x.2023.02.013件调制器来定制事件及其属性表示的权重对于每个预测任务，使用不同的调制器同时进行下一事件及其属性的预测并最终预测事件序列后缀15。宫子优等人使用时间卷积网络将业务流程中的事件及其属性作为输入,在业务流程的执行场景中预测流程的下一个事件和剩余流程16。黄晓芙等人提出了一种基于频繁活动集的序列编码处理日志中的低频活动，并通过搜寻历史相似数据进行预测下一个活动17。上述预测方法都是根据已发生事件日志中活动的执行顺序，时间戳以及已执行活动中的数据属性值训练预测模型后进行预测。事实上，现有绝大多数预测性业务流程监控方法只考虑利用活动以及活动属性值训练模型进行预测，并未考虑日志中隐藏的行为信息，本文通过挖掘算法挖掘流程执行期间日志之间的行为关系并用来提供决策支持增强业务流程预测质量。本文使用文本挖掘算法将日志活动的行为关系用前缀树表示，提出了一种将深度学习模型与前缀树结合的预测方法。在训练好的预测模型中利用前缀树增强预测正在进行的案例的未来执行情况。本文以LSTM模型13作为所提出方法的基础，在四个事件日志中预测了正在执行的案例的下一个活动及后缀，并与基线LSTM方法进行比较。结果表明相比只使用预测模型进行预测的方法，使用前缀树提供决策支持进行增强业务流程预测的方法精度有所提升。1基本概念定义1迹一个迹=A*是一个有限的事件序列，由定义在活动集A上的一系列活动组成。定义2事件日志一个事件日志是活动集A上的多组迹的集合。定义3前缀迹一个迹的前缀迹是它的从头开始的子序列，例如，给定一个迹=A*，它的长度为k的前缀迹prefk()=A*，其中1kn。定义4下一活动预测给定一个前缀迹prefk()=A*以及预测函数f，则给定前缀的下一个活动为ak+1=f(prefk()。定义5后缀迹一个迹的后缀迹是其前缀迹的剩余部分的子序列，例如，给定一个迹=A*，它的长度为k的后缀迹为suffk()=A*。2业务流程预测方法2.1循环神经网络与LSTM人工神经网络是一种基于模仿大脑神经网络结构和功能而建立的一种信息处理系统(简称神经网络)，在分类任务中作用非常显著18。人工神经网络主要架构是由神经元、层和网络三个部分组成。整个人工神经网络包含一系列基本的神经元、通过权重相互连接。神经元是人工神经网络最基本的单元。单元以层的方式组，每一层的每个神经元和前一层、后一层的神经元连接，共分为输入层、输出层和隐藏层，三层连接形成一个神经网络。输入层神经元经过权重加权之后得到的输出作为隐藏层神经元的输入，隐藏层神经元经过权重加权之后得到了输出层的输入。输出层经过激活函数的激活就可以进行分类任务的判别。其中每层神经元加权的权重通过基于梯度的优化进行反向传播从训练数据中学习得到。RNN是神经网络的其中一个子类，它的展开之后的结构如下。一个循环神经网络可以看作多个神经网络的连接，如虚线所示，对于任意的时间步长t，在这个时间步的执行就相当于一次神经网络的执行，Xt是输入层，ht是隐藏层，yt是输出层,此时ht包含所有时间步长到t时所提取的信息。在不同的时间步中输入不同的数据，通过当前时间步上的隐藏状态的激活以及输出层的激活，得到在此时间步在各个预测活动上的概率分布进行分类预测。在RNN中不同时间步的权重Wh,Wx,Wy是共享的。RNN已经被证明非常适用于序列化建模，(A.:Sequence Mod-eling:Recurrent and Recursive Nets.)，例如，自然语言处理(Natural Language Processing,NLP)任务中，I like eating apple和The Apple is a greatcompany。为apple打上标签，第一句中apple指代水果，而在第二句中apple指代一个公司，这种分类预测任务不仅与当前状态的输入有关，同时也取决于目前已经发生过的输入，正常的全连接网络单独的训练apple这个单词的标签，无法结合上下文去训练模型，循环神经网络可以通过不同时刻的参图1循环神经网络展开结构计算机与大数据科学45-数共享，使得在时间步t可以获得前面t-1个时间步的状态信息来帮助进行预测。现实任务同样如此，下一个活动的发生不仅取决于当前的活动，同时取决于先前已发生的活动，因此，把预测任务看作是NLP任务，把迹中的每个活动看作是NLP任务中的单词，可以使用循环神经网络进行序列化建模。但对于基本的RNN来说，它只能够处理一定的短期依赖，并不能处理长期依赖关系，因此通过对RNN的隐藏层网络结构进行修改，产生了LSTM19,它与基本的RNN相比引入了输入门、遗忘门、输出门三种门来保持和控制信息，能够长时间保存隐藏状态的信息，解决了RNN无法处理长期依赖关系的问题。2.2LSTM算法实现目前已有许多预测过程监控方法使用带有LSTM单元的RNN。本文采用Tax等人提出的LSTM方法13，它的执行方法依赖于活动序列编码，使用最为常用的one-hot编码，对于一个给定的活动集合A=a,b,c,d，需要创建一个索引函数，确定活动在集合中所处的位置，索引函数为index:A=a,b,c,d，有index(a)=1,即活动a在集合A中所处位置为第1个，活动b在集合A中所处位置为第2个。对活动序列进行编码时，为每个活动ai创建一个长度为|A|的向量Ai，当前活动所处的索引值位置为1，其他位置均为0。迹的编码方式将迹中所有活动获得的向量组合成一个矩阵。训练阶段，使用编码好的迹训练LSTM模型，预测阶段，使用一个正在进行的活动序列(进行one-hot编码)进行预测监控。具体算法如下：该算法输入一个已经训练好的LSTM模型，一个给定的最大迭代次数max，以及一个正在进行的活动序列prefk()，通过迭代的预测下一个活动来预测后缀，当max=1的时候只迭代一次，即预测当前活动序列的下一个活动，max1进行后缀预测。3使用前缀树增强预测方法预测性业务过程监控使用存储在事件日志中的过去的迹来构建模型对未来进行预测，在某些场景非常有用，例如在医疗场景中，需已知患者执行了哪些活动从而对患者进行下一步的治疗方案进行决策，但现实中进行后续序列预测仍然存在很大的挑战，随着活动事件持续发生，预测后面序列越发困难，现有方法只考虑使用历史事件日志中的迹训练深度学习预测模型，并利用训练完成的模型预测未来活动的序列，忽略了历史事件日志中隐藏的行为关系。通过挖掘日志间的行为关系以流程图、前缀树、后缀树等形式进行表达，并结合深度学习预测模型可以帮助预测模型提高未知事件预测的质量。3.1从迹中学习对历史事件日志的迹挖掘信息有多种方式，第一种为流程挖掘方法，通过流程挖掘方法获得活动的流程图，常见的几种流程图类型如下：(1)Petrinets(也叫petri网)；(2)流程树(Process Tree，PT)；(3)业 务 流 程 建 模 标 记(Business Process ModelingNotation，BPMN)；(4)直接跟随图（Directly FollowGraph，DFG）。上述方法能够展现活动之间的直接跟随关系。对于Petri nets,流程树以及BPMN模型，不仅可以确定活动间的直接跟随关系，同时可以展现活动之间的行为轮廓关系，例如两个活动之间相互排斥，两个活动相互严格顺序执行以及两个活动是并发执行，已知两个活动a和b是并发的，即a发生b一定发生，发生的顺序不定，预测时利用行为轮廓关系剔除不符合活动关系的迹，从而使得预测结果更贴近真实的结果，这些行为轮廓关系不止可以为深度学习模型预测提供决策支持，同时可考虑在训练模型阶段将行为轮廓关系编码作为输入属性进行预测模型的训练，这些工作在未来是我们尝试的方向。第二种信息挖掘方式为数据挖掘，本文基础LSTM算法即是数据挖掘主要方法中的一类，属于预测模型方法，其余预测模型算法包括决策树、支持向量机等。第三种信息挖掘