基于深度迁移学习的业务流程实例剩余执行时间预测方法*

图1 剩余时间预测总体框架

Fig.1 Framework of Remaining Time Prediction

首先,指定实例前缀长度范围[min,max],采用公式(3)的训练数据生成方式,并将训练集进行划分,每个训练集分别对应不同长度的实例前缀;之后,在各个训练集上分别训练针对不同长度实例前缀的剩余时间预测模型。

由于不同长度实例前缀在数量和剩余时间不确定性上的差异,相比于利用所有实例前缀训练单一预测模型,采用多个预测模型能够有效提升剩余时间预测的针对性^[14]。然而,在各个训练集上单独训练剩余时间预测模型往往存在很多困难。

（1）根据前缀长度将训练集进行划分后会导致各个训练集内的实例前缀数量大大降低,特别是在现实事件日志中,流程实例数量随着其长度呈现不断下降的趋势,这导致较长前缀长度的训练集将更小,而深度学习方法往往需要较大数量的训练数据,故在各个训练集上难以单独得到准确的预测模型;

（2）不同前缀长度的训练集可以互为补充,长度为n的实例前缀包含所有长度小于n的实例前缀,故较短实例前缀的预测模型能够对训练较长实例前缀的预测模型提供有益信息,在各个训练集单独训练模型则忽视了不同长度实例前缀之间的内在关联。

因此,采用迁移学习方法训练多个剩余时间预测模型：首先在数量最多的最短实例前缀（长度为min）上训练模型;之后在训练更长实例前缀的模型时,将短实例前缀模型的参数作为初始值,通过精调的方式利用长实例前缀数据进行模型训练,直至训练得到最长实例前缀（长度为max）上的模型。这种基于迁移学习的模型训练方式能够充分利用相近长度实例前缀的内在关联,克服长实例前缀数据量少的问题,同时能够加快模型训练的收敛速度。

4.2 多层循环神经网络模型

在基于迁移学习的剩余时间预测框架下,应用多层循环神经网络（Multi-layers Recurrent Neural Networks, Multi-layers RNN）构建针对各个前缀长度的剩余时间预测模型,基本网络结构如图2所示,本文具体采用了双层RNN。

图2

图2 双层循环神经网络基本结构

Fig. 2 Architecture of Bi-layer RNN

该模型以轨迹前缀 $σ^{(k)} = < e_{1}, \dots e_{k} >$ 作为输入,每个事件 $e_{t} (1 \leq t \leq k)$ 的向量表示输入至第一层RNN的各个神经元。RNN神经元的基本功能是接收轨迹前缀当前时刻的事件向量以及上一时刻神经元输出的隐向量作为输入,对其进行非线性变换后得到当前时刻输出的隐向量。第二层RNN的结构与第一层相同,主要区别在于其每个神经元以第一层RNN中对应神经元输出的隐向量作为输入。LSTM^[15]和GRU (Gated Recurrent Unit)^[16]是RNN神经元的两种常见实现方式。一些研究者在多个序列建模任务上对LSTM和GRU等RNN神经元方式进行了对比实验^[17],结果表明GRU和LSTM在大多数任务上的效果没有显著差异,但是由于GRU对LSTM的门机制进行了简化,因此在训练时间上更有优势。

以第二层RNN最后一个神经元的输出作为双层RNN的最终输出,可以将其看作对整个实例前缀的编码。双层RNN之后接一个多层感知机（Multilayer Perceptron, MLP）作为回归模型计算输入实例前缀的剩余时间。

4.3 基于事件表示学习的预训练

在自然语言处理领域中,研究者发现词的向量表示对于深度学习模型的训练效果有直接的影响^[9,18],因此提出预训练的概念,目标是为深度学习模型事先训练高质量的词向量表示。与自然语言处理领域类比,业务流程管理领域中的流程实例与自然语言处理领域中的句子均是一种序列数据,事件类似于单词,是流程实例的组成单元。可以认为,事件表示的质量同样会影响剩余时间预测模型的效果。因此,本文提出一种事件表示学习方法,为事件日志中的每个事件得到高质量的向量表示,作为剩余时间预测模型的预训练输入。

根据事件的定义,事件相关的活动及其执行时间是事件的必备属性,故将事件执行的活动及其执行时间作为事件的标识,在此基础上计算事件向量。由于事件执行时间是连续值,因此需先对其进行离散化处理,基本思想是对事件对应活动所有可能的执行时间进行等分。假设划分数量为 $N$ ,离散化后的事件 $e$ 执行时间如公式（6）所示。

(6)

\tilde{t} (e) = ⌊\frac{e . time - \min (e . activity)}{\max (e . activity) - \min (e . activity)} \times N⌋

其中, $e . time$ 是事件e的连续值执行时间, $\max (e . activity)$ 和 $\min (e . activity)$ 分别表示活动 $e . activity$ 在事件日志中可能的最长执行时间和最短执行时间。

因此,事件表示学习的目标是对于业务系统中的所有活动 $a \in A$ 及其离散化执行时间 $t \in \{1,2, \dots, N\}$ ,得到向量 $θ^{〈a, t〉} \in R^{d}$ 。

借鉴自然语言处理领域中基于负采样的Skip-Gram词向量学习方法^[19],基本思想是在事件日志中频繁出现在同一实例的事件具有相似的向量表示。给定事件日志L,事件向量表示学习问题可以被抽象为优化问题,如公式（7）所示。

(7)

\max O (L) = \log \prod_{σ \in L} \overset{| σ |}{\prod_{t = 1}} (\prod_{e' \in context (e_{t})} p (e' | e_{t}) \cdot \prod_{e' \in neg (e_{t})} (1 - p (e' | e_{t})))

优化目标的现实含义是根据当前事件 $e_{t}$ 预测上下文事件 $e' \in context (e_{t})$ 的概率尽可能高,即具有相似的向量表示。同时为增强事件向量的辨识能力,要求预测非上下文事件 $e' \in neg (e_{t})$ 的概率尽可能低。 $neg (e_{t})$ 表示对事件 $e_{t}$ 进行负采样得到的事件集合,通常可在事件全集中进行随机采样获得。 $context (e_{t})$ 表示事件 $e_{t}$ 在所在轨迹 $σ$ 中的上下文事件,给定窗口长度参数l,可表示如公式（8）所示。

(8)

context (e_{t}) = {e_{t - l}, \dots, e_{t - 1}, e_{t + 1}, \dots, e_{t + l}}

事件间的条件概率由对应事件向量点积的Sigmoid函数计算,如公式（9）所示。

(9)

p (e' | e) = \frac{1}{1 + \exp (- θ^{{〈e . a, \tilde{t} (e)〉}^{T}} \cdot θ^{〈e' . a, \tilde{t} (e')〉})}

公式(7)所示优化问题可使用随机梯度下降法求解,其主要优势是具有较快的收敛速度,且对于海量日志具有较好的可扩展性。随机梯度下降法采用迭代求解方式,事件日志中的任一事件e和它的一个上下文事件或负采样事件 $e'$ 产生一次迭代,在每次迭代中,计算优化目标关于e和 $e'$ 中的活动向量和时间间隔向量的梯度,之后根据梯度更新相应向量。具体而言,针对特定事件对 $〈e, e'〉$ ,优化目标的梯度计算如公式（10）和公式（11）所示。其中,上下文事件为“+”,负采样事件为“-”。

(10)

\frac{\partial O (〈e, e'〉)}{\partial θ^{〈e . a, \tilde{t} (e)〉}} = p (e' | e) (1 - p (e' | e)) θ^{〈e' . a, \tilde{t} (e')〉}

(11)

\frac{\partial O (〈e, e'〉)}{\partial θ^{〈e' . a, \tilde{t} (e')〉}} = \pm p (e' | e) (1 - p (e' | e)) θ^{〈e . a, \tilde{t} (e)〉}

5 实验研究

5.1 实验数据

本文实验使用来自4TU Center for Research Data^①(①https://data.4tu.nl/repository/collection:event_logs_real.)的公开事件日志数据集,分别是：

（1）BPIC2012_A：某财政机构贷款申请审批日志。

（2）BPIC2012_O：同数据集（1）,但仅包含贷款审批状态变更记录。

（3）BPIC2012_W：同数据集（1）,但仅包含贷款审批涉及资源的状态变更记录。

（4）Helpdesk：来源于某票务管理系统的后台日志。

（5）Hospital_Billing：来源于某医院ERP系统中记录的出院结算流程日志。

这5个数据集的统计信息如表1所示。

表1 数据集统计信息

Table 1 Statistics of Datasets

数据集	轨迹数量	事件数量	活动数量	轨迹最大长度	轨迹最小长度
BPIC2012_A	13 087	73 022	10	10	3
BPIC2012_O	5 015	41 728	7	39	4
BPIC2012_W	9 658	147 450	6	153	1
Helpdesk	3 804	13 710	9	14	1
Hospital_Billing	100 000	451 359	18	217	1

新窗口打开| 下载CSV

5.2 对比实验

（1）基准方法

选择经典的流程模型驱动方法和数据驱动方法作为基准方法。流程模型驱动方法选择基于变迁系统的方法^[2]（分别使用集合、多重集和序列对变迁系统的状态进行抽象表示,简称TS-set、TS-multiset和TS-sequence）和文献[4]提出的基于随机Petri网的方法（简称SPN）。数据驱动方法选择文献[8]提出的基于LSTM深度神经网络的方法（简称LSTM）。多项研究已证实在剩余时间预测任务中LSTM优于其他传统机器学习方法,故不再与基于传统机器学习的方法进行对比。此外,对文献[7]中的方法进行改进,使用GRU替代LSTM作为循环神经网络的实现（简称GRU）。对于本文方法,分别使用LSTM和GRU作为多层循环神经网络中神经元的实现。

基于变迁系统的方法使用ProM 5.2实现,基于随机Petri网的方法使用ProM 6.8实现,本文方法与各种基于循环神经网络的方法均使用PyTorch 1.1实现。

对各种基于循环神经网络的方法进行基本调参,调参范围为：

①输入事件向量维度：{3,5,7,10};

②神经元隐向量维度：{3,5,7,10};

③学习率：{0.01,0.1}。

其他参数设置方案为：迭代轮数为150轮,优化算法为Adam。

（2）评价指标

使用平均绝对误差（Mean Absolute Error, MAE）作为各个方法的评价指标,通过计算各个实例前缀剩余执行时间的真实值和预测值之间差值的绝对值来度量剩余时间预测的准确性。较高的MAE表示较高的剩余时间预测质量。对于某剩余时间预测模型 $f$ ,MAE值计算方法如公式（12）所示。

(12)

MAE (f) = \sum_{(σ^{(k)}, R (σ^{(k)})) \in D} |f (σ^{(k)}) - R (σ^{(k)})|

采用5折交叉验证的评估方式,即将数据集随机分成5等份,每次选择4份作为训练数据,1份作为测试数据,重复5次实验,各次实验MAE值的平均值作为最终评估结果。

（3）实验结果

本文方法与对比方法在各个数据集上的MAE评测结果如表2所示。

表2 对比实验结果

Table 2 Experiment Results

方法	BPIC2012_A	BPIC2012_O	BPIC2012_W	Helpdesk	Hospital_Billing
TS-set	7.505	8.429	7.392	6.283	51.456
TS-multiset	7.488	8.691	7.203	6.167	51.507
TS-sequence	7.488	8.619	9.612	6.192	51.504
SPN	8.880	8.516	6.385	6.337	78.018
LSTM	3.588	8.021	7.993	3.542	42.050
GRU	3.895	7.324	6.153	3.303	36.691
本文方法(LSTM)	3.489	5.858	5.826	3.357	33.201
本文方法(GRU)	3.512	7.306	6.338	2.677	32.227

新窗口打开| 下载CSV

①基于深度学习的各种方法在各个数据集上均优于基于变迁系统和随机Petri网的方法,这印证了深度学习在剩余时间预测任务上的优势。这一现象的主要原因在于循环神经网络强大的序列建模能力,特别是真实事件日志往往具有海量、高噪音的特点,较强形式化的流程模型（如变迁系统、Petri网等）难以有效描述整个事件日志的特征,而循环神经网络能够更好地处理海量事件日志,且鲁棒性更强,从而可以取得更优的预测效果。

②对比LSTM和GRU两种循环神经网络,经典的单层GRU略优于单层LSTM,本文使用的多层LSTM则略优于多层GRU。整体而言,LSTM与GRU在预测效果上没有显著区别。考虑到GRU在训练时间上的优势,可以认为GRU要比LSTM更为适合剩余时间预测任务,这说明将GRU应用于剩余时间预测任务是一次有益的尝试。

③对比经典的单层LSTM/GRU和本文使用的多层LSTM/GRU,多层网络在大多数情况（除GRU在BPIC2012_W数据集上）取得了比单层网络更优的预测质量,这说明适度增加循环神经网络的深度能够在一定程度上提升剩余时间预测效果。

④本文方法（以双向LSTM/GRU作为基础模型,引入迁移学习框架和事件表示学习预训练方法）在5个数据集均取得了最优的预测效果。具体而言,在LSTM和GRU两种循环神经网络神经元实现上,本文方法在所有数据集上的MAE值平均下降约16%和7%,验证了本文方法的优越性。

5.3 迁移学习效果分析

在本实验中,以双层GRU为基础模型训练面向不同前缀长度的剩余时间预测模型,采用如下三种训练方式：

（1）在所有长度实例前缀数据集上训练一个统一模型（简称Uni-2layer-GRU）;

（2）在各个长度实例前缀数据集上分别独立训练多个模型（简称Sep-2layer-GRU）;

（3）在本文迁移学习框架下训练多个模型（简称Trans-2layer-GRU）。

三种方法在不同长度轨迹前缀数据上的MAE值如图3所示。

图3

图3 迁移学习效果对比

Fig. 3 Results of Transfer Learning

可以发现,Trans-2layer-GRU的 MAE值在大多数情况下低于Uni-2layer-GRU和Sep-2layer-GRU,特别是在较长实例前缀上具有更为明显的优势,这证实了迁移学习机制能够有效利用不同长度的实例前缀之间的关联性,克服较长长度实例前缀数据稀缺的问题。进一步对比Uni-2layer-GRU和Sep-2layer-GRU可以发现,两者在整体上具有相当的预测效果,其中在较短实例前缀上Uni-2layer-GRU优势较大,在较长实例前缀上Sep-2layer-GRU优势较大,这在一定程度上证实了不同长度的实例前缀之间确实存在一定差异。此外,随着实例长度的增加,剩余时间预测的MAE值在整体上呈现不断下降的趋势,这一现象也和已有研究一致,主要是由于随着流程实例的不断执行（即实例前缀不断增长）,剩余时间的不确定性在不断降低。

5.4 事件表示学习效果分析

在本实验中,以Uni-2layer-GRU为基础模型训练剩余时间预测模型,其输入的事件向量分别为独热编码的向量（简称Uni-2layer-GRU）和本文提出的事件表示学习方法学习得到的向量（简称Pretrain-Uni-2layer-GRU）。这两个方法在各个数据集上的MAE值如图4所示。可以发现,Pretrain-Uni-2layer-GRU在各个数据集上均取得了比Uni-2layer-GRU更低的MAE值,特别是在数据集BPIC2012_O上取得超过7%的改进,因此可以认为基于事件表示学习的预训练机制对于提升剩余时间预测效果具有非常重要的作用。

图4

图4 预训练效果对比

Fig.4 Results of Pre-training

6 结语

本文设计了一种基于深度迁移学习的业务流程实例剩余执行时间预测方法。与已有研究使用LSTM循环神经网络训练单一预测模型不同,本文引入迁移学习机制构建面向不同实例长度的多个剩余时间预测模型,提升剩余时间预测的针对性。此外,设计了事件表示学习方法为神经网络模型提供预训练事件向量输入。在5个真实事件日志数据上开展了实验研究,结果证实本文方法能够取得比基于业务流程模型和LSTM循环神经网络的方法更优的剩余时间预测效果。

深度学习技术已在剩余时间预测任务中展示出巨大的应用潜力,然而现有基于深度学习的剩余时间预测方法大多完全依赖于历史事件日志,如何将形式化流程模型有机融合至深度神经网络模型中是进一步提升剩余时间预测效果的重要途径。

作者贡献声明:

刘彤：论文起草及修改;

倪维健：提出研究思路,设计研究方案;

孙宇健：采集、清洗和分析数据,进行实验;

曾庆田：论文最终版本修订。

利益冲突声明:

所有作者声明不存在利益冲突关系。

支撑数据:

支撑数据由作者自存储,E-mail: niweijian@gmail.com。

[1] 倪维健. deep_trans.py. 剩余时间预测程序.

[2] 倪维健. bpic2012a.csv. BPIC_2012_A数据集预测结果.

[3] 倪维健. bpic2012o.csv. BPIC_2012_O数据集预测结果.

[4] 倪维健. bpic2012w.csv. BPIC_2012_W数据集预测结果.

[5] 倪维健. helpdesk.csv. Helpdesk数据集预测结果.

[6] 倪维健. hospital_billing.csv. Hospital_Billing数据集预测结果.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

van der Aalst

Process Mining: Discovery, Conformance and Enhancement of Business Processes

[M]. Springer, 2011.

[2]

van der Aalst

, Schonenberg M

, Song

Time Prediction Based on Process Mining

[J]. Information Systems, 2011,36(2):450-475.

[本文引用: 4]

[3]

赵海燕, 李帅标, 陈庆奎 , 等.

面向业务过程的时间预测方法

[J]. 小型微型计算机系统, 2019,40(2):280-286.

( Zhao

Haiyan

, Li

Shuaibiao

, Chen

Qingkui

, et al.

Method of Time Prediction for Business Process

[J]. Journal of Chinese Computer Systems, 2019,40(2):280-286.)

[4]

Rogge-Solti

, Weske

Prediction of Business Process Durations Using Non-Markovian Stochastic Petri Nets

[J]. Information Systems, 2015,54:1-14.

[本文引用: 4]

[5]

Verenich

, Nguyen

, La Rosa

, et al.

White-box Prediction of Process Performance Indicators via Flow Analysis

[C]//Proceedings of the 2017 International Conference on Software and System Process. ACM, 2017: 85-94.

[6]

Tax

, Verenich

, La Rosa

, et al.

Predictive Business Process Monitoring with LSTM Neural Networks

[C]//Proceedings of the 29th International Conference on Advanced Information Systems Engineering. Springer, 2017: 477-492.

[7]

Navarin

, Vincenzi

, Polato

, et al.

LSTM Networks for Data-Aware Remaining Time Prediction of Business Process Instances

[C]//Proceedings of the 2017 IEEE Symposium Series on Computational Intelligence. IEEE, 2017: 1-7.

[8]

Verenich

, Dumas

, La Rosa

, 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): Article No. 34.

[本文引用: 3]

[9]

Polato

, Sperduti

, Burattin

, et al.

Time and Activity Sequence Prediction of Business Process Instances

[J]. Computing, 2018,100(9):1005-1031.

[10]

Jimenez-Ramirez

, Barba

, Fernandez-Olivares

, et al.

Time Prediction on Multi-Perspective Declarative Business Processes

[J]. Knowledge and Information Systems, 2018,57(3):655-684.

[11]

Senderovich

, Weidlich

, Gal

, et al.

Queue Mining for Delay Prediction in Multi-Class Service Processes

[J]. Information Systems, 2015,53:278-295.

[12]

Bevacqua

, Carnuccio

, Folino

, et al.

A Data-driven Prediction Framework for Analyzing and Monitoring Business Process Performances

[C]//Proceedings of the 15th International Conference on Enterprise Information Systems. Springer, 2013: 100-117.

[13]

Senderovich

, Di Francescomarino

, Ghidini

, et al.

Intra and Inter-Case Features in Predictive Process Monitoring: A Tale of Two Dimensions

[C]//Proceedings of the 15th International Conference on Business Process Management. Springer, 2017: 306-323.

[14]

Leontjeva

, Conforti

, Di Francescomarino

, et al.

Complex Symbolic Sequence Encodings for Predictive Monitoring of Business Processes

[C]//Proceedings of the 13th International Conference on Business Process Management. Springer, 2015: 297-313.

[15]

Hochreiter

, Schmidhuber

Long Short-Term Memory

[J]. Neural Computation, 1997,9(8):1735-1780.

[16]

Cho

, Van Merriënboer

, Bahdanau

, et al.

On the Properties of Neural Machine Translation: Encoder-Decoder Approaches

[OL]. arXiv Preprint, arXiv:1409.1259.

[17]

Chung

, Gulcehre

, Cho K

, et al.

Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling

[OL]. arXiv Preprint, arXiv:1412.3555.

[18]

Radford

, Narasimhan

, Salimans

, et al.

Improving Language Understanding with Unsupervised Learning

[R]. OpenAI, 2018.

[19]

Mikolov

, Sutskever

, Chen

, et al.

Distributed Representations of Words and Phrases and Their Compositionality

[C]//Proceedings of the 26th International Conference on Neural Information Processing Systems. 2013: 3111-3119.