2022, Vol. 48
, 2. 同济大学 嵌入式系统与服务计算教育部重点实验室, 上海 200092
2. The Key Laboratory of Embedded System and Service Computing of Ministry of Education, Tongji University, Shanghai 200092, China
开放科学（资源服务）标志码（OSID）：
预测型流程监控[1]作为业务流程管理领域中的主要研究内容，旨在对当前正在运行的流程实例进行有效地分析，从而预测在今后一段时间内流程实例出现的行为状态，例如可能发生的活动、实例所需的执行时间等[2]。相较于现有监控形式的方法，预测型流程监控是在过程感知信息系统的基础上对历史数据加以记录[3]，不仅能有效规避偏差、信息缺失等风险，而且还可以防止因流程实例持续执行而带来资源冲突等情况的发生。
业务流程剩余时间预测[4]作为预测型流程监控中重要的预测任务，采用合理的方式准确预测流程实例需要执行的剩余时间。而传统的剩余时间预测方法是基于业务系统中产生的事件日志挖掘形式化变迁系统[5]、随机Petri网[6]等可描述模型，并通过该模型对剩余时间进行有针对性的预测。随着深度学习技术的发展，研究人员将其与剩余时间预测相结合，并取得较优的预测效果，特别是文献[7]提出的预测方法，相较于传统方法的预测效果得到显著提升。
轨迹聚类利用相似性度量方式对事件日志中的轨迹进行分组，以更好地发现过程模型[8]。在轨迹聚类中使用的相似性度量因结构相似性和性能相似性不同而异[9]，同时不同集群会为结构和行为变化提供更加细致的表示。此外，轨迹聚类还可以有效减少事件日志中冗余数据，从而降低事件日志复杂度[10]。
为降低异质事件日志（如多变体、多流程实例）对业务流程剩余时间[11]预测准确度的影响，本文利用聚类方式为异质事件日志中不同长度的轨迹建立集群，以降低事件日志复杂度及细化结构，同时设计基于注意力机制的卷积准循环神经网络（Convolutional Quasi-Recurrent Neural Network，CQRNN）模型，有效地捕获对剩余时间预测任务有决定性影响的时间和空间特征信息，进一步改进剩余时间预测效果。
1 相关工作 1.1 聚类方法在预测型流程监控任务中，异质事件日志会影响业务流程剩余时间的预测效果，而合理的聚类方法在一定程度上可以解决该问题。文献[12]利用聚类方法在事件日志中检测业务流程存在的变种，通过回归技术在不同变种流程实例上构建剩余时间预测模型。文献[13]提出一种数据与聚类相结合的方法用于预测剩余时间，该方法主要是根据逻辑规则来表示聚类模型，以加强对上下文分析的适应能力。文献[14]提出利用聚类方法为业务流程场景配备预测模型的流程挖掘算法，以预测业务流程剩余时间。文献[15]构建预测型流程监控框架，该框架首先根据控制流信息对事件日志中的轨迹进行聚类，然后针对每个集群建立不同的分类器，最后将正在运行的案例映射到集群并应用相应的分类器进行剩余时间预测。文献[16]提出以聚类为基础的原因分析方法，该方法对事件日志进行预处理，并对其进行聚类，同时通过决策树检测事件日志中检索超时故障的原因，其中事件日志包含时间、延迟等丰富信息。文献[17]提出将事件日志分组到同质子集的方法，该方法利用聚类捕获过程模型，在过程模型中构建预测器，从而对业务流程剩余时间预测任务进行有针对性的预测。
1.2 业务流程剩余时间预测方法业务流程剩余时间预测方法[11]有助于企业开展流程控制以及传递高质量服务，因此受到国内外研究人员的广泛关注。文献[4]提出基于变迁系统的剩余时间预测方法，该方法主要是在事件日志中挖掘变迁系统，通过变迁系统记录流程实例可能发生的状态，利用流程实例的状态预测剩余时间。文献[6]是在事件日志中挖掘Petri网，利用Petri网模拟当前流程实例执行的状况，根据结果预测剩余时间。然而，由于传统流程挖掘方法存在一定的局限性，因此在处理大量事件日志时不能很好地展现出预测效果。随着机器学习技术的发展，其被有效地应用到业务流程剩余时间预测任务中。文献[18]在文献[4]的基础上提出数据感知变迁系统，在该系统中是采用朴素贝叶斯分类方式为各个状态节点建立模型，同时，利用支持向量机进行剩余时间预测。文献[19]将业务流程抽象为流程树，并在每个流程树的节点上训练回归模型以预测剩余时间。近年来，在深度学习技术得到大范围应用的背景下，研究人员将长短期记忆网络作为剩余时间预测任务中的关键方法。文献[20]利用长短期记忆神经网络和嵌入方式对变量进行分类，进而实现对业务流程剩余时间的预测。文献[21]采用生成对抗网络在生成事件后缀的同时预测业务流程的剩余时间。文献[22]设计一种基于注意力机制的高级表示学习方法，解决业务流程剩余时间预测任务中不能很好地捕捉输入序列长期依赖关系，达到对业务流程剩余时间有效预测的目标。
2 预备知识 2.1 基本概念本文介绍与业务流程剩余时间预测任务相关的基本概念，并给出形式化描述。
定义1（事件） 事件是业务系统中活动的运行实例，以多元组e={Caseid，a，Time，p{1，2，…，n}}表示。其中：Caseid为事件所属案例的ID；a为事件执行活动的名称；Time为事件执行时间，即Time=事件结束时间EndTime-事件开始时间StartTime；p{1，2，…，n}为事件其余属性，包括资源、执行代价等信息。
定义2（轨迹） 轨迹是一个非空且有限的事件序列，表示为σ={e1，e2，…，e|σ|}（1 ≤ i ≤ |σ|）。其中：ei表示第i个事件；|σ|表示轨迹σ中事件数量。
定义3（轨迹前缀） 轨迹前缀是轨迹σ中前U个事件，记作σ（U） ⊆{e1，e2，…，eU}。
定义4（轨迹前缀剩余时间） 轨迹前缀剩余时间是轨迹σ中未执行事件e的执行时间总和，可以表示为RT（σ（U））=eU+1.Time+eU+2.Time+…+e|σ|.Time。
定义5（流程实例） 流程实例是业务系统从开始到结束一次有效的运行过程，以元组Q={Cid，σ，q{1，2，…，m}}表示。其中：Cid表示轨迹σ的案例ID；σ表示流程实例中的轨迹；q{1，2，…，m}表示流程实例中其他属性。
定义6（事件日志） 事件日志描述了业务系统历史运行情况，以L = {Q1，Q2，…，Q|l|}表示。
定义7（剩余时间预测） 在业务系统中，假设事件空间为T，则轨迹和轨迹前缀空间记为T*，剩余时间预测旨在利用映射函数对轨迹前缀剩余时间进行预测，即f = T* → R+。
本文仅关注流程实例中轨迹基本信息（即事件、活动、执行时间），并开展剩余时间预测任务。
2.2 业务流程剩余时间预测任务本文在利用深度学习技术开展业务流程剩余时间预测任务时，可分为训练阶段和应用阶段。训练阶段的主要目标是通过事件日志中详细描述的历史流程实例对剩余时间预测函数f进行学习，应用阶段则是利用训练阶段获得的函数f对业务流程中流程实例（即轨迹前缀）的剩余执行时间进行预测。
在训练阶段，需将事件日志L转化为深度学习可使用的数据集。因此，本文利用轨迹聚类的方式将事件日志L划分为不同集群（集群内部轨迹相似，不同集群轨迹不相似），在集群中设定截取轨迹前缀范围u∈N*，并将其作为训练集，如式（1）和式（2）所示：
| $ {D}_{\mathrm{C}\mathrm{l}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\_\sigma }=\\ \left\{\left.{\sigma }^{\left(U\right)}, \mathrm{R}\mathrm{T}\left({\sigma }^{\left(U\right)}\right)\left|\sigma \subseteq \left\{{e}_{1}, {e}_{2}, \cdots , {e}_{\left|\sigma \right|}\right\}\right.\in L, U < \left|\sigma \right|\right\}\right. $ | (1) |
| $ {D}_{\mathrm{C}\mathrm{l}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}}={D}_{\mathrm{C}\mathrm{l}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\_\sigma \left(1\right)}\bigcup {D}_{\mathrm{C}\mathrm{l}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\_\sigma \left(2\right)}\bigcup \cdots \bigcup {D}_{\mathrm{C}\mathrm{l}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}\_\sigma \left(u, u\in U\right)} $ | (2) |
应用阶段是利用生成的训练数据集DCluster对业务流程剩余时间模型f进行学习，为了防止出现过拟合的现象，利用正则项的方式加以克服，如式（3）所示：
| $ f\mathrm{*}=\underset{f\in F}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}{\sum\limits _{\left({\sigma }^{\left(U\right)}, \mathrm{R}\mathrm{T}\left({\sigma }^{\left(U\right)}\right)\right)\in {D}_{\rm{Cluster}}}\left(f\right(\sigma )-t)}^{2}+{\mathit{\Omega }}\left(f\right) $ | (3) |
本文提出的基于轨迹聚类的剩余时间预测方法流程如图 1所示。
|
Download:
|
| 图 1 本文方法流程 Fig. 1 Procedure of the proposed method | |
该方法采用轨迹间相似度的聚类方式为事件日志建立Cluster{1，2，…，n}集群，根据式（1）和式（2）对Cluster{1，2，…，n}集群设定所要截取的轨迹前缀范围，并生成训练数据集{1，2，…，n}，将生成的训练数据集{1，2，…，n}依次输入到基于注意力机制的卷积准循环神经网络中进行迭代训练，获得Cluster{1，2，…，n}各集群的剩余时间，并将结果加权平均，从而得到最终剩余时间。本文将该方法应用于业务流程剩余时间预测任务后，剩余时间预测效果得到显著提升。
3.1 轨迹聚类在过程挖掘领域中，已有很多文献提出不同的轨迹聚类方法，而大多数轨迹聚类方法是基于数据挖掘聚类方法对事件日志进行更深入的转换与处理，通过已有的聚类方法开展有效的聚类任务。现有轨迹聚类方法分为3类：1）向量空间方法，将事件日志中具有代表性的特征向量化，并抽象为特征矩阵，利用传统距离度量计算事件日志中轨迹之间的距离，同时，通过传统聚类方法进行轨迹聚类；2）上下文感知的轨迹聚类，在当前轨迹聚类方法的基础上以上下文感知的方式对其进行补充与扩展；3）基于模型的序列聚类，利用过程模型对事件日志中的轨迹进行聚类处理。因此，本文使用上述3种代表性的轨迹聚类方法对业务流程信息系统产生的事件日志进行处理，从而比较不同轨迹聚类方法对剩余时间预测结果影响的差异性。
3.1.1 向量空间方法文献[23]提出向量空间的概念，将轨迹中的活动构建成活动向量空间模型，保证聚类事件日志中的相似轨迹处于同一集群中，经聚类后生成的子事件日志尽可能地分离工作流，以达到发现更加简单过程模型的目的。文献[24]分析了事件日志中轨迹的行为特征，为轨迹构建完整的向量空间模型，与文献[23]不同，文献[24]主要利用大量的配置文件以确定与每个过程实例相关联的向量。此外，该方法还提出一系列距离度量方法和聚类方法，用于对配置文件进行后续操作。在本文实验部分对应的轨迹聚类方法为K-Means。
3.1.2 上下文感知的轨迹聚类方法文献[25-26]描述了一种以上下文感知为基础的轨迹聚类扩展方法。上下文感知仅考虑事件日志中轨迹的控制流属性（如活动序列），并不考虑事件日志的资源属性、时间戳属性等。文献[25]提出一种通用编辑距离技术[27]，该技术利用编辑操作量化了从一条轨迹转换为另一条轨迹所用的距离，通过传统轨迹聚类方法进行聚类处理。文献[26]通过不同长度子序列对上下文感知的轨迹聚类原理进行扩充，并定义了极大、超极大和接近超极大重复概念，以创建、确定事件日志中轨迹向量特征集，从而更精确地表示轨迹的行为特征。在本文实验部分对应的轨迹聚类方法为Guide Miner Tree。
3.1.3 基于模型的序列聚类方法文献[28]提出一种不同以往方法的轨迹聚类方法。受文献[29]的启发，研究人员针对混合一阶马尔科夫模型以期望最大化算法的方式进行学习，从而实现聚类轨迹的目标。文献[30]以模型为基准的轨迹聚类方法被完整地应用于服务器日志中，进一步验证该方法在生活中的有效性与可用性。文献[31]提出基于目标拟合度的轨迹聚类方法，该方法的主要原理是在已有的轨迹集合中添加一条新的轨迹，若添加后的轨迹集合拟合度大于原来拟合度，则将该轨迹添加到当前轨迹集合中，以此循环迭代，最终每个集合表示一个聚类集群。相比现有轨迹聚类方法，该方法在每次选择的轨迹中可以更好地适合特定的过程模型。在本文实验部分对应的轨迹聚类方法为ActiTrac。
3.2 基于注意力机制的卷积准循环神经网络 3.2.1 事件向量表示训练数据集DCluster是由不同长度的轨迹前缀σ（U）组成，因此本文将轨迹前缀σ（U） ⊆{e1，e2，…，eU}作为网络模型的输入。由于轨迹前缀σ（U）包含众多不同事件，每个事件又具有活动、执行时间等多种离散和连续属性，因此本文将轨迹前缀中各个事件表示为网络模型可接受的事件向量xt。对于事件中存在的离散属性（如活动），利用One-Hot编码将其表示为0/1向量；对于事件中存在的连续属性（如活动执行时间），首先对其进行离散化处理，然后利用One-Hot编码将其转化为0/1向量；而事件向量xt为离散属性向量与连续属性向量拼接的结果，并将xt作为卷积准循环神经网络模型中卷积神经网络的输入。
3.2.2 卷积神经网络卷积神经网络（Convolutional Neural Network，CNN）[32]作为一种前馈神经网络，可以有效捕捉局部重要信息，因此，在许多研究领域中得到广泛应用。在CNN中，每个卷积层之间的神经元采用部分连接，通过特征信息组合形成高级特征，从而减少网络模型参数量并降低网络模型训练的复杂度。
卷积层作为CNN的关键模块，通过与序列数据向量维度为m×n的矩阵P进行卷积运算，得到新输出特征oi，如式（4）所示：
| $ {\boldsymbol{o}}_{i}=\mathrm{R}\mathrm{e}\mathrm{l}\mathrm{u}\left(w\times {P}_{j:j+\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{s}\_\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}-1}+b\right) $ | (4) |
其中：j表示第j个特征值；w表示滤波器；windows_size表示滑动窗口；b表示偏置值；Pj：j+windows_size-1表示选择向量矩阵P中第j行到j+windows_size-1行的局部序列数据。在本文实验中，卷积核大小为3×3，windows_size为2。同时，滑动窗口被应用于各局部序列数据向量矩阵，经计算后得到的特征向量O如式（5）所示：
| $ \boldsymbol{O}=\left({\boldsymbol{o}}_{1}, {\boldsymbol{o}}_{2}, \cdots , {\boldsymbol{o}}_{m-\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{s}\_\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}+1}\right) $ | (5) |
池化层作为CNN另一个重要模块，旨在提取卷积层中输出的特征图信息，在减少神经网络参数的同时，保留有用的特征信息。本文采用最大池化的方法，以选择池化区域中最大特征值，如式（6）所示：
| $ {\boldsymbol{O}}_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{P}\mathrm{o}\mathrm{o}\mathrm{l}\left({\boldsymbol{o}}_{i}\right) $ | (6) |
然后，将CNN中池化层得到的特征值组合在一起。为了避免过拟合现象的出现，本文利用Dropout减少网络权重连接，同时将Dropout输出的向量作为双向准循环神经网络的输入。
3.2.3 准循环神经网络长短期记忆神经网络（Long Short-Term Memory，LSTM）和门控循环单元（Gated Recurrent Unit，GRU）处理序列数据时依赖上一时间步的输出，消耗较多的时间且不能很好地处理长序列数据。而准循环神经网络（Quasi-Recurrent Neural Network，QRNN）[33]利用交替卷积层神经序列建模方法，在输出过程中充分利用输入序列的顺序信息，实现对序列数据跨时间步长的并行处理。
QRNN由卷积层和池化层组成。在序列数据X=（x1，x2，…，xT）作为QRNN的输入后，卷积层会通过数量为k的滤波器对输入的序列数据进行卷积处理，得到新序列Z=（z1，z2，…，zT）。如果将卷积层中滤波器的宽度设置为可变长度h，那么经卷积后得到zt宽度为xt-h+1~xt，其中zt是新序列Z一个向量。QRNN卷积层的计算如式（7）所示：
| $ \boldsymbol{Z}=\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}\left({\boldsymbol{W}}_{\boldsymbol{z}}\mathrm{*}X\right) $ | (7) |
其中：
此外，QRNN利用门函数计算序列向量，并将其作为池化层的输入，同时QRNN在内部结构上将LSTM线性操作转化为卷积操作且使用了遗忘门F和输出门O[34]。QRNN门函数计算如式（8）和式（9）所示：
| $ F=\sigma \left({\boldsymbol{W}}_{f}\mathrm{*}X\right) $ | (8) |
| $ O=\sigma \left({\boldsymbol{W}}_{o}\mathrm{*}X\right) $ | (9) |
其中：
QRNN池化层主要提取卷积层中全部的输出特征信息，以减少特征数目。同时，QRNN池化层结构与LSTM相似，为进一步确保序列数据在时间变化上进行有效建模，达到维持序列数据上下文相关性的目的，不同时刻记忆单元状态Ct的更新方式如式（10）所示：
| $ {\boldsymbol{C}}_{t}={\boldsymbol{f}}_{t}\odot {\boldsymbol{C}}_{t-1}+{\boldsymbol{i}}_{t}\odot {\boldsymbol{z}}_{t} $ | (10) |
其中：ft、it分别为遗忘门、输入门在t时刻的序列信息；Ct‒1为上一时刻记忆单元状态；⊙为不同向量之间按位相乘。
QRNN模型的最终输出ht由t时刻的输出门Ot和记忆单元状态Ct计算而得，如式（11）所示：
| $ {\boldsymbol{h}}_{t}={\boldsymbol{O}}_{t}\odot {\boldsymbol{C}}_{t} $ | (11) |
其中：Ot为输出门在t时刻的序列信息；ht为网络输出。
在业务流程剩余时间预测任务中，每条轨迹前缀所含的事件之间都具有一定的关联性，若仅利用单向QRNN处理此类序列数据，不仅忽略了下文事件信息对上文事件信息的影响，而且并不能达到提升预测效果的目的。因此，本文在单向QRNN的基础上引入双向机制，即双向QRNN（Bi-QRNN），以有效地提取上文事件中有用的特征信息，从而捕捉下文特征信息，进一步提升网络模型预测效果。Bi-QRNN由一条正向QRNN和一条反向QRNN组成，若正向QRNN和反向QRNN在t时刻获得的输出隐向量为
| $ {\boldsymbol{h}}_{t\_\mathrm{Q}\mathrm{R}\mathrm{N}\mathrm{N}}=\left(\overrightarrow{{\boldsymbol{h}}_{t\_\mathrm{Q}\mathrm{R}\mathrm{N}\mathrm{N}}}, \overleftarrow{{\boldsymbol{h}}_{t\_\mathrm{Q}\mathrm{R}\mathrm{N}\mathrm{N}}}\right) $ | (12) |
注意力机制是基于资源分配原理，旨在关注重要内容。本文引入注意力机制主要是为了更好地学习轨迹前缀中每个事件的权重，以识别不同事件对业务流程剩余时间预测任务的重要程度。将Bi-QRNN的输出ht_QRNN作为注意力机制输入，则：
| $ {\boldsymbol{u}}_{t}=\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}\left(\boldsymbol{W}\cdot {\boldsymbol{h}}_{t\_\mathrm{Q}\mathrm{R}\mathrm{N}\mathrm{N}}+b\right) $ | (13) |
| $ {a}_{t}=\mathrm{S}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}\left({\boldsymbol{u}}_{t}^{\mathrm{T}}\boldsymbol{M}\right) $ | (14) |
| $ \boldsymbol{v}=\sum \limits_{t}{a}_{t}\cdot {\boldsymbol{h}}_{t\_\mathrm{Q}\mathrm{R}\mathrm{N}\mathrm{N}} $ | (15) |
其中：W表示权重矩阵；b表示偏置值；ut是ht_QRNN隐藏层表示；at表示权重值；M表示上下文矩阵。
基于注意力机制的卷积准循环神经网络结构如图 2所示。
|
Download:
|
| 图 2 基于注意力机制的卷积准循环神经网络结构 Fig. 2 Structure of convolutional quasi-recurrent neural network based on attention mechanism | |
在过程挖掘领域中，因事件日志的异质性特点，传统剩余时间预测方法（如文献[4, 6]）难以对整个事件日志的基本特征进行描述。本文提出的剩余时间预测方法利用神经网络强大的序列数据建模能力以及较强的鲁棒性处理事件日志，因此本文方法相较于传统剩余时间预测方法具有一定优势。此外，相比利用深度学习技术开展剩余时间预测任务的预测方法（如文献[11, 20]），本文方法首先利用轨迹聚类的方式合理地解决了事件日志的异质性问题，降低了异质事件日志对剩余时间预测结果的影响；其次通过将CNN与QRNN相结合，并引入双向机制和注意力机制，以捕获和增强对剩余时间预测任务有决定性影响的时间和空间特征信息，从而克服了循环神经网络在空间维度的局限性。因此，本文提出基于轨迹聚类的剩余时间预测方法具有一定的可行性与有效性。
4 实验与结果分析 4.1 实验数据集本文实验使用7个来自4TU Center for Research的公开事件日志数据集：BPIC_2012_A[35]、BPIC_2012_O[35]、BPIC_2012_W[35]、Helpdesk[36]、Hospital_Billing[37]、Sepsis_Cases[38]、Prepaid_Travel_Costs[39]。其中BPIC_2012_A、BPIC_2012_O、BPIC_2012_W来源于某财政机构贷款申请审批日志；Helpdesk来源于某票务管理系统后台日志；Hospital_Billing来源于某医院EPR中出院结算流程日志；Sepsis_Cases来源于医院败血症病历事件日志；Prepaid_Travel_Costs来源于某机构差旅费报销事件日志。事件日志数据集的相关信息如表 1所示。
|
下载CSV 表 1 事件日志数据集的基本信息 Table 1 Basic information of event log datasets |
本文以平均绝对误差（
| $ {M}_{\mathrm{M}\mathrm{A}\mathrm{E}}\left(f\right)=\sum \limits_{({\sigma }^{\left(U\right)}, \mathrm{R}\mathrm{T}({\sigma }^{\left(U\right)}\left)\right)\in {D}_{\mathrm{C}\mathrm{l}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}}}\left|f\left({\sigma }^{\left(U\right)}\right)-\mathrm{R}\mathrm{T}\left({\sigma }^{\left(U\right)}\right)\right| $ | (16) |
除此之外，本文采用5折交叉验证的方式评估预测模型，即将事件日志数据集通过随机的方式划分为5等份，其中4份作为训练集，1份作为测试集，并重复5次，将得到的
为验证以CQRNN为基准的网络模型（即CQRNN、引入双向机制的Bi-CQRNN、引入双向机制和注意力机制的Att-Bi-CQRNN）相较于其他网络模型在剩余时间预测任务上的有效性，本文将CQRNN、Bi-CQRNN、Att-Bi-CQRNN与LSTM、Bi-LSTM、Att-Bi-LSTM、GRU、Bi-GRU、Att-Bi-GRU、QRNN、Bi-QRNN、Att-Bi-QRNN神经网络的预测效果进行对比。同时，为进一步验证轨迹聚类方法在剩余时间预测任务中的可行性，本文将轨迹聚类方法分别应用在以LSTM、GRU、QRNN、CQRNN为基准的网络模型中，并与其他网络模型对比剩余时间预测结果。
上述网络模型均采用2层顺序结构，神经元隐向量维度为10，Batch_size为512，学习率为0.01，迭代150轮，使用Adam优化算法。本文实验是基于PC Intel Core i5-10400F 2.90 GHz、NVIDIA GeForce RTX 2070 SUPER环境，使用Pytorch框架。
4.3 实验结果 4.3.1 基于轨迹聚类的剩余时间预测效果分析本节主要分析基于轨迹聚类的剩余时间预测效果。为进一步获得最优集群和集群类别，本文在实验过程中使用3.1节所描述的3种轨迹聚类方法（ActiTrac、Guide Miner Tree、K-Means），并将余弦相似度作为区分不同集群间轨迹相似性和轨迹聚类方法优劣的评价指标。
余弦相似度是指将事件日志转化为对应矩阵后，通过计算得到的行向量夹角余弦值来评估它们之间的相似度。具体地，将轨迹聚类后得到的事件日志转换为相应的矩阵，并以行向量的方式进行表示，通过计算不同事件日志间行向量的余弦相似度，并对结果加权，从而得到经轨迹聚类后各事件日志的相似度，计算过程如式（17）所示：
| $ \mathrm{s}\mathrm{i}\mathrm{m}\left(\boldsymbol{X}, \boldsymbol{Y}\right)=\frac{\boldsymbol{X}\times \boldsymbol{Y}}{‖\boldsymbol{X}‖\times ‖\boldsymbol{Y}‖}=\frac{\sum\limits _{i=1}^{n}{x}_{i}\times {y}_{i}}{\sqrt{\sum \limits_{i=1}^{n}{x}_{i}}\times \sqrt{\sum \limits_{i=1}^{n}{y}_{i}}} $ | (17) |
其中：X、Y分别表示事件日志转化为矩阵后对应的每个行向量。利用式（17）对生成的事件日志进行评价后，获得事件日志之间余弦相似度越小，说明事件日志之间越不相似，而事件日志之间的不相似性也进一步反映了所使用的轨迹聚类方法的聚类质量。因此，本文通过分析事件日志数据集中轨迹数量的差异性，将不同轨迹聚类方法的聚类集群类别分别设置为K=3、K=4、K=5，并依次计算在利用轨迹聚类方法处理后获得的子事件日志之间余弦相似度，随后将结果加权平均得到不同聚类方法和不同聚类集群的余弦相似度，从而获得最优轨迹聚类方法和集群。在不同数据集上，各轨迹聚类方法的不同聚类集群的余弦相似度对比如表 2所示。
|
下载CSV 表 2 不同轨迹聚类方法的余弦相似度对比 Table 2 Cosine similarity comparison among different trajectory clustering methods |
由表 2可以看出，在7个事件日志数据集上ActiTrac轨迹聚类方法在经加权平均后获得的余弦相似度相较于其他两种轨迹聚类方法更低，说明使用ActiTrac轨迹聚类方法获得的子事件日志之间不相似程度高，从而验证了该方法可以有效区分事件日志中存在的轨迹。因此，本文选择ActiTrac轨迹聚类方法对事件日志数据集进行轨迹聚类。当K=3时，在BPIC_2012_A、BPIC_2012_W、Sepsis_Cases数据集上ActiTrac轨迹聚类方法的余弦相似度均优于K=4和K=5的余弦相似度，说明K=3可以准确地将这3个事件日志数据集中相似性高的轨迹划分到一个子类中。因此，本文在BPIC_2012_A、BPIC_2012_W、Sepsis_Cases事件日志数据集中选取K=3的集群。此外，当K=4和K=5时，在BPIC_2012_O、Helpdesk、Hospital_Billing、Prepaid_Travel_Costs数据集上，ActiTrac轨迹聚类方法余弦相似度较低，因此，对于BPIC_2012_O、Helpdesk、Hospital_Billing、Prepaid_Travel_Costs事件日志数据集，本文选取了K=4和K=5的集群。最后，针对BPIC_2012_W、Hospital_Billing事件日志数据集中部分轨迹聚类方法无结果的情况，其原因为BPIC_2012_W、Hospital_Billing事件日志数据集复杂度过高。
合理的轨迹聚类方法可以有效地解决异质事件日志的问题，在降低事件日志整体复杂度的同时，实现提升预测效果的目标。因此，本文在Att-Bi-LSTM、Att-Bi-GRU、Att-Bi-QRNN、Att-Bi-CQRNN的基础上尝试增加轨迹聚类方法（即C-Att-Bi-LSTM、C-Att-Bi-GRU、C-Att-Bi-QRNN、C-Att-Bi-CQRNN），并且将其与其他网络模型进行对比，相关设置如下：
1）对事件日志数据集不做任何处理，利用式（1）和式（2）生成的训练数据集DCluster作为网络模型的输入，以此对预测模型进行迭代训练，并获得剩余时间预测结果。
2）对事件日志数据集进行轨迹聚类，将得到的集群利用式（1）和式（2）生成训练数据集DCluster，并将其作为网络模型的输入，以此对预测模型进行迭代训练，并获得剩余时间预测结果。
不同预测模型在7个事件日志数据集上的实验结果如图 3所示。从图 3可以看出，相比以LSTM、GRU、QRNN、CQRNN为基准的网络模型，利用轨迹聚类方法的C-Att-Bi-LSTM、C-Att-Bi-GRU、C-Att-Bi-QRNN、C-Att-Bi-CQRNN剩余时间预测模型在各数据集中均取得了较优的预测结果，同时在预测准确度方面，使用轨迹聚类方法比不使用轨迹聚类方法的MAE值平均下降了约30%，证明了轨迹聚类方法有助于解决异质事件日志的问题，在降低事件日志整体复杂度的同时，进一步提升剩余时间预测效果，因此，基于轨迹聚类方法在剩余时间预测任务具有一定优势。
|
Download:
|
| 图 3 不同预测模型的剩余时间预测效果对比 Fig. 3 Effect of the remaining time prediction comparison among different prediction models | |
本节主要是验证本文方法在业务流程剩余时间预测任务中的有效性，并对业务流程剩余时间平均绝对误差进行对比分析。在7个事件日志数据集上不同预测模型的平均绝对误差对比如表 3所示。
|
下载CSV 表 3 不同预测模型的平均绝对误差对比 Table 3 Mean absolute errors comparison among different prediction models |
从表 3可以看出，在不增加任何机制的前提下，CQRNN模型在剩余时间预测任务中相较于LSTM、GRU和QRNN取得了较优的预测结果。因此，CQRNN模型在对序列数据进行处理时，相比于LSTM、GRU和QRNN可以更好地捕获和联系时间与空间特征信息，使得剩余时间预测效果得到一定提升。因此，本文将CQRNN模型应用于剩余时间预测任务具有一定的可行性。在引入双向机制后，相较于LSTM、GRU、QRNN、CQRNN模型，Bi-LSTM、Bi-GRU、Bi-QRNN、Bi-CQRNN剩余时间平均绝对误差分别减少约3%、4%、7%、9%，说明融入双向机制可以有效地提升模型对上文事件特征信息的提取以及捕获下文特征信息的能力，以提高业务流程剩余时间预测准确度。同时，本文进一步验证了单向的LSTM、GRU、QRNN、CQRNN在对序列数据进行处理的过程中不能充分考虑上下文信息之间的联系，并且在构建剩余时间预测模型时存在局限性问题。
此外，单向和双向QRNN相较于单向和双向LSTM、GRU在剩余时间预测效果上提高了约3%~ 5%，说明QRNN利用交替卷积层的神经序列建模方法，可以充分使用输入序列顺序信息的结果。而在QRNN的基础上加入卷积神经网络是因为QRNN只能捕获对剩余时间预测任务有决定性影响的时间特征信息，加入卷积神经网络后（CQRNN）可以更充分地获取对剩余时间预测任务有影响的空间特征信息。因此，CQRNN预测效果优于不加入卷积神经网络的QRNN，同时证明了本文提出的模型在剩余时间预测任务中存在一定优势。
在预测模型中引入注意力机制，Att-Bi-LSTM、Att-Bi-GRU、Att-Bi-QRNN、Att-Bi-CQRNN剩余时间平均绝对误差相较于LSTM、GRU、QRNN、CQRNN模型分别降低了约5%、1%、2%、2%，说明注意力机制通过计算不同位置的序列信息权重，以区分每个事件对剩余时间预测任务的重要程度，达到提取重要事件信息的目的，从而降低无用事件信息对剩余时间预测效果的影响。
综合分析各预测模型在不同事件日志数据集上的实验结果，在LSTM、GRU、QRNN、CQRNN模型的基础上引入双向和注意力机制后，剩余时间预测准确度都得到不同程度提升，从而进一步说明双向机制和注意力机制的引入提高了模型对序列数据的建模能力，加强了上下文事件信息之间的关联性，更好地捕获到对剩余时间预测任务有决定性影响的特征信息，达到提升剩余时间预测质量的目
标。此外，相比以LSTM、GRU、QRNN为基准的9种模型，CQRNN在同级比较的前提下取得较优的预测效果，表明在QRNN基础上加入卷积神经网络可以弥补QRNN模型在获取空间特征信息的不足。此外，不同预测模型的参数量对比如表 4所示。本文模型的参数量与同级QRNN参数量相差较少，但明显低于LSTM和GRU模型，说明本文模型在参数量未明显增加的条件下提升了剩余时间的预测性能。
|
下载CSV 表 4 不同预测模型的参数量对比 Table 4 Parameter quantity comparison among different prediction models |
综上所述，在业务流程剩余时间预测任务中，本文提出的基于轨迹聚类的业务流程剩余时间预测方法相较于传统预测方法在全部事件日志数据集上预平均绝对误差（MAE）平均降低约20%，表明该方法具有一定的可行性。
5 结束语本文提出一种基于轨迹聚类的业务流程剩余时间预测方法。根据余弦相似度，通过对事件日志中的轨迹进行聚类，以降低事件日志的复杂度。设计基于注意力机制的卷积准循环神经网络，在为不同集群构建剩余时间预测模型的同时，捕获和增强集群中对剩余时间预测结果起决定性作用的时间和空间特征信息。在事件日志数据集上的实验结果表明，本文方法具有有效性，能够改进剩余时间预测效果。由于在面对更加复杂的业务流程场景中的剩余时间预测任务时，高效的事件日志采样方式可以提升事件日志质量[40]，因此后续将采样技术应用于剩余时间预测任务中，进一步改进业务流程剩余时间预测效果。
| [1] |
TEINEMAA I, DUMAS M, ROSA M L, et al. Outcome-oriented predictive process monitoring: review and benchmark[J]. ACM Transactions on Knowledge Discovery from Data, 2019, 13(2): 17. |
| [2] |
TAX N, VERENICH I, ROSA M L, et al. Predictive business process monitoring with LSTM neural networks[C]//Proceedings of International Conference on Advanced Information Systems Engineering. Berlin, Germany: Springer, 2017: 477-492.
|
| [3] |
DUMAS M, AALST W M P, HOFSTEDE A H. Process-aware information systems: bridging people and software through process technology[M]. New York: John Wiley and Sons, 2005.
|
| [4] |
AALST W M P, SCHONENBERG M H, SONG M. Time prediction based on process mining[J]. Information Systems, 2011, 36(2): 450-475. DOI:10.1016/j.is.2010.09.001 |
| [5] |
王潇潇. 基于深度学习的多元时间序列预测研究[D]. 重庆: 重庆邮电大学, 2021. WANG X X. Research on multivariate time series forecasting based on deep learing[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2021. (in Chinese) |
| [6] |
ROGGE-SOLTI A, WESKE M. Prediction of business process durations using non-Markovian stochastic Petri nets[J]. Information Systems, 2015, 54: 1-14. DOI:10.1016/j.is.2015.04.004 |
| [7] |
NAVARIN N, VINCENZI B, POLATO M, et al. LSTM networks for data-aware remaining time prediction of business process instances[C]//Proceedings of IEEE Symposium Series on Computational Intelligence. Washington D.C., USA: IEEE Press, 2017: 1-7.
|
| [8] |
OIRSCHOT V. Using trace clustering for configurable process discovery explained by event log data[D]. Eindhoven, The Netherlands: Eindhoven University of Technology, 2014.
|
| [9] |
REINHARTZ-BERGER I, GULDEN J, NURCAN S, et al. Enterprise, business-process and information systems modeling[M]. Berlin, Germany: Springer, 2017.
|
| [10] |
DE LEONI M, AALST W M P, DEES M. A general process mining framework for correlating, predicting and clustering dynamic behavior based on event logs[J]. Information Systems, 2016, 56: 235-257. DOI:10.1016/j.is.2015.07.003 |
| [11] |
倪维健, 孙宇健, 刘彤, 等. 基于注意力双向循环神经网络的业务流程剩余时间预测方法[J]. 计算机集成制造系统, 2020, 26(6): 1564-1572. NI W J, SUN Y J, LIU T, et al. Business process remaining time prediction using bidirectional recurrent neural networks with attention[J]. Computer Integrated Manufacturing Systems, 2020, 26(6): 1564-1572. (in Chinese) |
| [12] |
BEVACQUA A, CARNUCCIO M, FOLINO F, et al. A data-driven prediction framework for analyzing and monitoring business process performances[C]//Proceedings of International Conference on Enterprise Information Systems. Berlin, Germany: Springer, 2014: 100-117.
|
| [13] |
FOLINO F, GUARASCIO M, PONTIERI L. Mining predictive process models out of low-level multidimensional logs[C]//Proceedings of International Conference on Advanced Information Systems Engineering. Berlin, Germany: Springer, 2014: 533-547.
|
| [14] |
PRAVILOVIC S, APPICE A, LANZA A, et al. Mining cluster-based models of time series for wind power prediction[C]//Proceedings of International Symposium on Methodologies for Intelligent Systems. Berlin, Germany: Springer, 2014: 9-20.
|
| [15] |
FRANCESCOMARINO C D, DUMAS M, MAGGI F M, et al. Clustering-based predictive process monitoring[J]. IEEE Transactions on Services Computing, 2019, 12(6): 896-909. DOI:10.1109/TSC.2016.2645153 |
| [16] |
SURIADI S, OUYANG C, AALST W M P, et al. Root cause analysis with enriched process logs[C]//Proceedings of International Conference on Business Process Management. Berlin, Germany: Springer, 2012: 174-186.
|
| [17] |
VERENICH I, DUMAS M, LA ROSA M, et al. Survey and cross-benchmark comparison of remaining time prediction methods in business process monitoring[J]. ACM Transactions on Intelligent Systems and Technology, 2019, 10(4): 34. |
| [18] |
POLATO M, SPERDUTI A, BURATTIN A, et al. Time and activity sequence prediction of business process instances[J]. Computing, 2018, 100(9): 1005-1031. DOI:10.1007/s00607-018-0593-x |
| [19] |
VERENICH I, NGUYEN H, LA ROSA M, et al. White-box prediction of process performance indicators via flow analysis[C]//Proceedings of International Conference on Software and System Process. New York, USA: ACM Press, 2017: 327-388.
|
| [20] |
EVERMANN J, REHSE J R, FETTKE P. A deep learning approach for predicting process behaviour at runtime[C]//Proceedings of International Conference on Business Process Management. Berlin, Germany: Springer, 2016: 327-388.
|
| [21] |
TAYMOURI F, ROSA M. Encoder-decoder generative adversarial nets for suffix generation and remaining time predication of business process models[EB/OL]. [2021-10-08]. https://arxiv.org/abs/2007.16030.
|
| [22] |
BUKHSH Z A, SAEED A, DIJKMAN R M. Process transformer: predictive business process monitoring with transformer network[EB/OL]. [2021-10-08]. https://arxiv.org/abs/2104.00721v1.
|
| [23] |
GRECO G, GUZZO A, PONTIERI L, et al. Discovering expressive process models by clustering log traces[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1010-1027. DOI:10.1109/TKDE.2006.123 |
| [24] |
SONG M, GÜNTHER C W, VAN DER AALST W M P. Trace clustering in process mining[C]//Proceedings of International Conference on Business Process Management. Berlin, Germany: Springer, 2008: 109-120.
|
| [25] |
BOSE R P J C, AALST W M P. Context aware trace clustering: towards improving process mining results[C]//Proceedings of SIAM International Conference on Data Mining. Philadelphia, USA: Society for Industrial and Applied Mathematics, 2009: 401-412.
|
| [26] |
BOSE R P J C, VAN DER AALST W M P. Trace clustering based on conserved patterns: towards achieving better process models[C]//Proceedings of International Conference on Business Process Management. Berlin, Germany: Springer, 2010: 170-181.
|
| [27] |
LEVENSHTEIN V. Binary codes capable of correcting deletions, insertions, and reversals[J]. Doklady.Akademii.Nauk SSSR, 1965, 10(8): 845-848. |
| [28] |
FERREIRA D, ZACARIAS M, MALHEIROS M, et al. Approaching process mining with sequence clustering: experiments and findings[C]//Proceedings of International Conference on Business Process Management. Berlin, Germany: Springer, 2007: 360-374.
|
| [29] |
CADEZ I, HECKERMAN D, MEEK C, et al. Model-based clustering and visualization of navigation patterns on a web site[J]. Data Mining and Knowledge Discovery, 2003, 7(4): 399-424. DOI:10.1023/A:1024992613384 |
| [30] |
VEIGA G M, FERREIRA D R. Understanding spaghetti models with sequence clustering for ProM[C]//Proceedings of Business Process Management Workshops. Berlin, Germany: Springer 2010: 92-103.
|
| [31] |
DE WEERDT J, BROUCKE S, VANTHIENEN J, et al. Active trace clustering for improved process discovery[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(12): 2708-2720. |
| [32] |
周飞燕, 金林鹏, 董军. 卷积神经网络研究综述[J]. 计算机学报, 2017, 40(6): 1229-1251. ZHOU F Y, JIN L P, DONG J. Review of convolutional neural network[J]. Chinese Journal of Computers, 2017, 40(6): 1229-1251. (in Chinese) |
| [33] |
BRADBURY J, MERITY S. Quasi-recurrent neural networks. [EB/OL]. [2021-10-08]. https://arxiv.org/pdf/1611.01576.pdf.
|
| [34] |
王栋, 李业刚, 张晓, 等. 基于准循环神经网络的中文命名实体识别[J]. 计算机工程与设计, 2020, 41(7): 2038-2043. WANG D, LI Y G, ZHANG X, et al. Chinese name entity recognition based on quasi-recurrent neural networks[J]. Computer Engineering and Design, 2020, 41(7): 2038-2043. (in Chinese) |
| [35] |
DONGEN V. Bpi2012[EB/OL]. [2021-10-08]. https://doi.org/10.4121/uuid:3926db30-f712-4394-aebc-75976070e91f.
|
| [36] |
VERENICH I. Helpdesk[EB/OL]. [2021-10-08]. https://mendeley.figshare.com/articles/dataset/Helpdesk/8951084.
|
| [37] |
MANNHARDT F. Hospital Billing[EB/OL]. [2021-10-08]. https://data.4tu.nl/artic-les/dataset/Hospital_Billing_Event_Log/12705113.
|
| [38] |
MANNHARDT F. Sepsis_Cases[EB/OL]. [2021-10-08]. https://data.4tu.nl/articles/dataset/Sepsis_Cases_Event_Log/12707639.
|
| [39] |
DONGEN B V. Prepaid_Travel_Costs[EB/OL]. [2021-10-08]. https://data.4tu.nl/articles/dataset/BPI_Challenge_2020_Prepaid_Travel_Costs/12696722.
|
| [40] |
苏轩, 刘聪, 张帅鹏, 等. 面向日志完备性的事件日志采样方法[J/OL]. 计算机集成制造系统: 1-16[2021-10-08]. http://kns.cnki.net/kcms/detail/11.5946.TP.20211108.1420.014.html. SU X, LIU C, ZHANG S P, et al. Event log sampling approach towards log completeness[J/OL]. Computer Integrated Manufacturing Systems: 1-16[2021-10-08]. http://kns.cnki.net/kcms/detail/11.5946.TP.20211108.1420.014.html. (in Chinese) |