刘云峰， 高俊涛

(东北石油大学 计算机与信息技术学院， 黑龙江 大庆 163318)

0 引言

业务过程管理是管理、分析、控制和改进企业产生经营过程的系统化与结构化方法，帮助企业提升管理体系的关键。越来越多的企业开始建立自己的业务过程模型、运行和部署过程模型，并通过对运行流程的检测以及历史数据的分析来逐步优化企业流程。业务过程评价的重要指标是时间，剩余时间预测是业务过程的一项核心任务。研究及时准确的剩余时间预测方法不仅可以帮助企业调整生产计划和服务流程，还有助于缓解用户因长时间的等待而产生的焦虑。

1 研究现状

流程监控的对象主要包括流程的周转时间、资源占用情况、成本开销等流程性能指标。预测方法可以归结为分析型方法和比较型方法两类。

典型的分析型预测方法包括Rogge-Solti于2015年提出基于随机Petri网的预测方法[1]和Dumas于2017年提出的基于流分析(Flow Analysis)技术的预测方法[2]。

比较型预测方法包括SVM[3]、决策树[4]和聚类[5]在内的多种数据挖掘模型和算法分析影响监控指标的企业流程因素和外部环境因素。2011年，Wil van der Aalst等[6]提出了基于变迁系统的剩余时间预测方法，该方法用变迁系统描述事件日志中流程实例的所有可能状态，并在状态上标记时间信息，以便根据当前流程实例所处的状态预测其剩余执行时间。

除了采用传统数据挖掘方法进行类比预测外，将深度学习技术应用于业务流程预测也是近年来流程管理领域一个新涌现的研究热点[7]。

本文在前人研究的基础上，以数据纯度作为重点，提出一种基于模型数据纯度高低选择合适预测模型的剩余时间预测方法。该方法采用搜寻历史相似数据的方式，适用于现在主流的XES和CSV格式事件日志。

2 基本概念

2.1 算法基础概念

业务过程实例的剩余时间预测需要先从历史事件日志中获取时间戳及相关信息。为了叙述方便，首先对业务过程的相关概念进行定义。

定义1(轨迹) 轨迹是一种有限非空线性集合，即σ∈ε*。在任意一个轨迹中，每个事件只发生一次并且时间是非递减的。

定义2(事件日志) 一个事件日志L={σ1,σ2,…}是多条日志轨迹的集合，每个事件在整个日志中最多只出现一次。

定义3(变迁系统) 变迁系统是一个三元组TS=(S,E,T)，其中S为状态集合;E为活动集合;T∈S×E×S为转移集合。

传统TS预测方法采用带时间标注的变迁系统预测业务过程的剩余时间。其方法采用序列、集合、多重集中某一种抽象机制构建预测模型，并根据模型预测剩余时间。如果构建预测模型的抽象机制发生了变化，剩余时间的预测结果可能不一样。事件日志片段案例如表1所示。

表1 事件日志片段

对表1所示的事件日志片段，采用序列和集合抽象分别得到2个模型,如图1所示。

(b) 基于set抽象的变迁系统

以轨迹前缀〈A,C,B〉为例，采用序列抽象的剩余时间预测值为7，采用集合抽象的预测值为5.3。因此序列抽象预测结果的MAE为1，集合抽象预测结果的MAE为1.7。

定义4(预测模型) 本文在TS预测方法的基础上，将原来只包含单一抽象机制的变迁系统扩展为包含3种抽象机制的复合变迁系统。预测模型M是一个集合，其元素为三元组(C,E,V)。其中,C为预测状态编码;E为剩余时间观察值的均值;V为观察值的标准差。

3 基于数据纯度的预测算法

本节在预测模型M的基础上，介绍在实际企业业务过程的部分轨迹已知的情况下，对其剩余时间进行预测的算法。算法1描述了在输入部分已知轨迹θ和模型M的情况下，根据观察值的标准差V进行选择，返回预测值的过程。

算法1 基于数据纯度的剩余时间预测算法输入:预测模型M,前缀轨迹θ输出:剩余时间预测值^tFunction Predict(M,θ)1. l=len(θ)2. maxpur f=0 //最大纯度3. while (l>0)4. Foreach abs in {hdl(θ),bag(hdl(θ)),set(hdl(θ))}5. Foreach m in {m∈M|mcode=abs}6. If pur f(m)>maxpur f7. ^t←mE-(e|θ|-el)8. return ^tEndFunction

3.1 状态选择

传统TS方法每次预测只能使用一种抽象机制，而且在实际业务过程中需要根据人工经验来判断选择哪种抽象机制，这与智能制造的宗旨不符。因此,本文将实际业务过程中的部分已知轨迹θ在预测模型M中根据历史相似数据进行匹配，记录下每个匹配成功的结果作为备选预测值。然后我们假设样本数据纯度越高，样本预测值可能越接近真实值，在这种假设情况下通过式(1)纯度函数purf:State→Pre评价每一个预测值的纯度，基于纯度高低智能选择纯度最高的预测值作为最终预测值,如式(1)。

purf(s)=-sV

(1)

为了计算方便，式(1)采用样本的标准差作为数据纯度的反向指标。

4 实验设计与分析

回归任务的主要误差评估标准是平均绝对误差(MAE)和均方根误差(RMSE)。由于事件之间的时间差值往往变化很大，大多在不同的数量级上，并且由于RMSE对异常数据点的错误非常敏感，所以我们使用MAE对误差进行评估。

本文实验采用真实业务过程的公开事件日志数据集，它们均可以在4TU Center for Research Data下载。日志的具体统计信息如表2所示。

表2 事件日志的统计信息

我们将实验日志切分为2部分，第1部分包括前2/3的轨迹，作为训练集；剩余1/3轨迹作为第2部分测试集。我们从大小为1的轨迹前缀开始，预测并评估每个通过事件的剩余时间。本文将传统TS方法作为基准方法进行对比,对比结果如图2所示。

Helpdesk

(a)

(a) 基于sequence抽象的变迁系统

Bpi12_w

Environment permit

Sepsis

图2显示了本文的纯度方法与传统TS方法在不同前缀长度上的平均绝对误差(MAE)。从图中可以看出，本文的纯度方法在绝大多数情况下要优于传统TS方法。在实际业务过程中，本文方法可以代替人工选择，自动的选择数据纯度最高的抽象机制进行剩余时间预测。并且在业务过程运行的中后期，基于数据纯度的预测方法候选空间变大，预测精度明显提高。

5 总结

本文提出了一种基于复合变迁系统的业务过程剩余时间预测方法，改变了传统预测方法每次预测只能使用单一抽象机制的预测方式。融合了多种抽象机制，基于观测值的数据纯度智能选择最优抽象机制进行剩余时间预测。在4个公开事件日志上进行了实验，结果显示该方法在可解释性、预测准确率方面具有一定优势。目前，该方法只基于观测值的纯度进行抽象选择，结合观测值的样本规模或增加感受野抽象机制，有望进一步提高预测的准确率。