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

2019-02-15赵海燕李帅标陈庆奎

小型微型计算机系统 2019年2期

赵海燕，李帅标,陈庆奎,曹健

1(上海市现代光学系统重点实验室,光学仪器与系统教育部工程研究中心,上海 200093) 2(上海交通大学计算机科学与技术系,上海 200030)

1 引言

业务流程管理对企业正在起着越来越重要的作用.各种信息系统在业务运行过程中会记录大量的信息，导致企业积累了大量的过程数据.同时，企业资源系统、工作流管理系统等以结构化的方式记录发生在工作流程中的事件.一方面为了防止数据资源浪费，另一方面，为了寻找有价值的信息提高企业的竞争力，对过程日志数据进行分析吸引越来越多的研究人员投入其中.

时间是业务过程的重要因素.一方面，缩短时间本身就是业务目标的一部分，另一方面，成本、风险等都与时间密切相关，准确的时间管理可以提高企业运营的效率.因此，近年来，企业对时间方面的要求越来越苛刻[1].除了需要对时间进行计划、检测外，对未来的时间进行预测对业务过程管理具有更大的价值，它不仅能保证企业正常运行，还对企业的决策有指导意义，例如提高企业的服务效率，降低运行成本，预防违规活动发生，使得企业利润最大化等.因此，怎样实现准确的业务过程时间预测成为了国内外关注的研究课题.

虽然目前不少学者提出了对业务过程时间进行预测的方法，但这个问题还面临着不少的技术挑战，其中包括影响因素的多维性、上下文相关性以及不确定性：多维性指的是在预测过程中要考虑多个维度信息(如任务类型、执行者、可用的资源等)，因为实际业务中众多的特征或因素都会对时间有所影响，如何选择合适的特征具有一定的挑战；上下文相关性指的是在预测的过程中，对于同一业务过程，前序活动的相关信息对当前活动会有所影响，对于时间因素而言，对当前活动的时间影响最大的因素是前一个活动或前几个活动的情况，显然，如果在过程的早期进行预测，则时间预测的误差增大；不确定性指的是业务过程在执行过程中可能会因为环境、技术、人为因素以及突发事件等导致过程发生不确定变化，增加了时间预测的挑战.

时间预测可根据不同的应用场景分为多种情况：第一种情况是预测业务过程的剩余执行时间，比如，告知客户过程大概在什么时候完成；第二种情况是预测业务过程中某一个活动的时间(开始时间或执行时间)；第三种则是根据时间预测判断正在执行的业务过程是否将来会出现违规情况.上述三种类型的预测结果可帮助管理者预防性能问题或违规行为，对系统内部而言，可及时进行资源调度提高资源利用率.

2 业务过程时间预测的数据基础

数据的准备是业务过程时间预测的前提.数据可以通过过程的事件日志进行提取[2].过程事件日志是一种记录业务过程执行情况的结构化文本文件，它可以存储事件的时间戳、执行或启动活动的资源(人或设备等)信息，或与该事件一起记录的其他业务数据信息.由于业务过程事件日志是获取数据的重要途径，下面将介绍事件日志的定义以及数据获取的相关挑战.

2.1 业务过程执行的事件日志

业务过程是一个活动的集合，它接受一个或多个输入，创建对客户有价值的输出[7].一个过程实例的执行会在信息系统中留下一系列被执行的活动的踪迹，因此通常被称为业务过程实例(踪迹).一个事件日志是踪迹的多重集，就执行活动而言，每条踪迹代表一个业务过程实例的生命周期[3].

近几年来，XES(可扩展事件流)[4]已经成为存储，交换和分析业务过程事件日志的标准.在这个标准中，每个事件指的是特定的过程实例中的一个活动(即某个过程中明确定义的步骤)[5,6].属于一个实例的事件是有序的，它们形成了过程的执行轨迹(通常被称为事件的踪迹).

2.2 业务过程数据获取面临的挑战

数据的广泛存在性使得数据越来越多地散布于不同的数据管理系统中[8]，致使业务过程数据获取面临一些技术挑战.一方面，事件数据规模快速增长；另一方面，为了满足符合性、效率和用户服务相关的需求，获取可用的日志文件需要克服以下一些困难：

1) 数据可能分布在多个数据源上，需要将信息关联与合并以提取合适的日志文件；

2) 事件数据可能是不完整的，也可能包含称为噪音的异常数据；

3) 日志可能会包括不同粒度与级别的事件，比如，时间戳精度范围从毫秒级别到天、周级别；

4) 有些事件日志的规模特别大，以至于难以处理，有的事件日志规模特别小，以至于没有足够的可用数据来得出可信的结论.

3 业务过程时间预测算法

近年来，业务过程的时间预测问题已经被很多学者所研究，他们根据不同应用场景提出了不同的方法.本节对近几年来提出方法进行分类归纳.首先，时间预测可根据不同的应用场景分为以下几种情况：预测业务过程的剩余执行时间；预测某一个活动的执行时间；预测业务过程是否可能会出现时间方面的违规情况.在不同的应用场景下，又有不同的算法.

用于预测业务过程时间的算法有很多，大致可以分为基于描述性统计的方法和基于模型的方法两类.描述性统计使用均值、标准差以及分布等总结历史记录数据.基于模型的方法从历史数据中发现模型，并采用模型进行时间的预测，由于这是一个典型的回归问题，因此回归模型是经常采用的方法，它基于输入变量、响应变量之间的关系预测响应变量的结果.

3.1 业务过程剩余执行时间的预测

预测业务过程实例剩余时间是如下的一个问题：给定一个事件日志，其中包含多个该业务过程实例执行的历史记录，对于一个正在进行的过程实例，预测目前到整个过程结束还有多少剩余时间.

业务过程剩余执行时间预测根据实现的方法可分为三类，即基于统计学的模型、黑盒模型以及白盒模型.

3.1.1 基于统计学的模型

基于统计学的模型是通过测定、收集、整理、归纳和分析等步骤得到数据的统计信息，如通过统计，可以得到每个活动的平均时间及其概率分布，从而达到预测时间的目的.

在文献[9]中，Aalst等人通过一种合适的抽象机制来学习历史事件日志信息并构建了带有标注的变迁系统(An Annotated Transition System)，为了预测业务过程的剩余完成时间，使用状态表示函数将到目前为止执行的活动序列映射到变迁系统中的一个状态，并通过基于类似状态下的较早的过程实例的平均完成时间来进行预测.该方法的缺点是需要大量的日志信息，如果日志包含的信息较少，则对预测结果影响较大，同时在构建模型的过程中只考虑了工作流结构，对预测的准确度有一定的限制.在文献[10]中，作者根据历史信息构建了分布式变迁随机Petri网(Distributed Transition Stochastic Petri Net).对于正在执行的业务过程，获取当前状态，然后收集给定数量n个模拟结果(完成时间)，数量n是根据模型产生的，表示从当前状态直到过程结束的模拟过程实例样本数量的下限.剩余时间的最大似然估计值通过模拟样本的均值获得，其预测准确度取决于样本的数量以及样本内时间信息的标准偏差.

Rogge-Solti等人在文献[11]中通过历史踪迹计算每个变迁活动的持续时间，以此统计时间信息.以这种方式收集的统计信息可以用于拟合统计分布.对正在运行的过程，根据其当前活动的执行时间从原始分布的截断分布中抽样，收集所有样本模拟延续的完成时间，返回这些样本值的平均值作为最后的剩余预测时间.Bolt等人则提出一种称为查询目录的新方法[12]，为了计算新的部分踪迹尾部(Partial Trace Tail)的剩余时间，将其与查询目录(Query Catalogs)中存储的部分踪迹尾部进行比较，将匹配的部分踪迹尾部的平均剩余时间作为剩余时间预测值.该方法的缺点是需要日志文件中包含大量不同形式的过程踪迹，否则对于未出现过的部分踪迹尾部，其预测准确度较低.

3.1.2 黑盒预测模型

黑盒模型方法是通过模型或机器学习等技术直接对剩余执行时间进行预测，在给定当前过程实例信息的情况下，将剩余执行时间的整体预测作为单个标量值，而不是试图通过预测过程的具体执行情况来对预测的结果进行解释.

文献[13]中，Polato等人使用了一种ε-SVR机器学习算法进行剩余执行时间的预测.该方法使用业务过程的历史踪迹训练ε-SVR模型，并通过编码技术将部分踪迹的特征转换为适合ε-SVR输入的格式，模型输出的值即为估计的剩余执行时间.该模型是通过训练历史数据所得，因此数据的处理对模型具有重要作用.作者在文献[14]中首先使用FAST挖掘算法通过序列树(Sequence Trees)的方式获取频繁队列；然后通过学习到的部分过程模型，构建一个嵌套的预测模型；最后使用嵌套模型树M5回归算法进行完成时间的预测.该方法的优点在于具有鲁棒性，而且不易产生过拟合的问题.在[15]中，Navarin等人提出了一种基于长短期记忆神经网络(Long Short-Term Memory，LSTM)模型对剩余时间预测的方法，其特点是学习长期的依赖关系[16].它将历史完整踪迹中各活动信息通过编码技术转换为支持LSTM输入的特征向量进行模型的训练，最后将未完成的踪迹信息输入模型之中进行时间的预测.该方法的优点在于考虑各活动的附加属性信息.在文献[17]中，作者从事件日志中抽取活动的发生频率、活动持续时间、过程实例属性以及数据属性四种类型，并构造相应的核函数(Kernel Function).通过核函数、带宽参数与活动时间测量相结合的方式构造预测剩余执行时间的非参数回归模型.实验结果表明后两种类型对剩余时间预测具有很好的效果.在此方法中，作者只假设数据属性变量为无序变量，并未考虑数据属性变量为有序或者连续的情况.

3.1.3 白盒预测模型

基于白盒模型的方法，在预测业务过程的剩余时间方面考虑到具体的执行方式，即通过当前活动状态预测到达下一个活动状态的概率和时间，直到业务过程执行到最后一个活动，然后将所预测的各活动时间间隔求和作为最终的剩余时间预测值.

在文献[13]中，Polato等人利用了[9]中相同的思想,基于历史信息构建了一个基于变迁的预测系统，与文献[9]的主要区别是该方法使用历史数据所有属性进行训练，为每个状态添加朴素贝叶斯分类器，为每个变迁添加支持向量回归器.朴素贝叶斯(Navie Bayes，NB)[18]是一个基于贝叶斯定理的概率分类器，支持向量回归(Support Vector Regression，SVR)[19]是基于支持向量机(Support Vector Machine，SVM)的预测时间的回归分析方法.NB可以用来获得从状态s0到达状态s1的转换概率；SVR用来预测下一个状态是s1的剩余时间是多少.对于未完成的部分踪迹，根据可能到达状态的NB和SVR的值加权求和得到部分踪迹的剩余执行时间，实验结果表明考虑所有属性能够对预测结果产生积极影响.文献[20]中，Pandey等人提出了一种基于隐马尔可夫模型(Hidden Markov Model)的方法，在当前踪迹的最后一个活动使用模型计算选择下一活动的概率，并结合[9]中每个活动的平均剩余时间计算加权平均值进行当前活动剩余时间的预测.实验结果表明该方法的预测结果与[9]中的结果相比较更为准确.

表1 业务过程剩余执行时间预测方法Table 1 Business process remaining execution time prediction method

Tax等人将历史数据训练集中每一个事件通过编码技术转换为特征向量作为LSTM模型的输入.利用LSTM可以对下一个活动预测函数和时间预测函数进行建模来预测下一个活动以及其时间戳.活动预测函数输出最有可能的到达状态.将时间预测函数的目标设置为下一活动和当前活动之间的时间差，根据当前活动的时间戳，计算下一活动的时间戳.对未完成的部分踪迹，通过迭代运用活动预测函数和时间预测函数直到案例结束，从而可得到后续的活动以及各活动的时间戳.对所有的最有可能选择的后续活动，根据其时间戳与当前时间相减，最后求和得到最终的剩余周期时间预测[21].该模型所需的预测时间比文献[15]中多，因为该方法需要对可能到达状态的每个(预测)活动执行一次时间预测，而[15]中只需进行一次时间的预测.

Verenich等人在文献[22]中提出了一种基于"控制流分析"技术来预测运行过程实例剩余时间的白盒方法."控制流分析"的概念是考虑这些活动之间的关系汇总活动层面估计值来估算过程层面的绩效指标.其原理通过估计单个活动的周期时间，实现整个实例剩余时间的估计.对于正在执行的过程实例，通过回溯算法(Backtracking Algorithm)将现有的部分前缀踪迹与历史踪迹相匹配，然后使用控制流分析公式来计算过程实例的剩余周期时间，计算中所需的单个活动的周期时间和从当前执行状态到可能的决策点的分支概率可从历史数据中训练得到的回归和分类模型来预测.该方法同时需要大量历史信息，这样提高预测精度有很大帮助.对业务过程剩余执行时间预测方法的总结见表1所示.

3.2 活动执行时间的预测

预测活动的执行时间包含预测活动执行持续的时间以及活动执行的开始时间.

在文献[23]中，作者提出了基于贝叶斯网络的称为CRAFFT的活动预测方法.在预测下一个活动的基础上，作者提出了一种方法来预测下一个活动的相对开始时间，通过提取数据集中每两个连续活动之间的时间偏移，并使用期望最大化算法(Expectation Maximization Algorithm)对它们进行聚类，以构建时间偏移的正态混合模型.对于特定的两个活动，根据时间偏移所建立的模型，估计后一活动的开始执行之间.Minor等人在文献[24]中根据原始事件数据，使用活动识别(Activity Recognition)算法标记每个事件及其相应的活动类别，并提出一种循环预测器的模型，该模型的优点是将活动和时序结构之间的关系作为上下文特征进行编码，通过模仿损失函数的形式训练模型，然后根据当前活动特征预测下一活动相对发生时间.实验结果表明该方法可以提供高度准确的预测结果.另外，文献[21]中将时间预测函数的目标设置为下一活动和当前活动之间的时间差，通过已知当前活动的时间戳，计算下一活动的开始执行时间.

Aalst等人在文献[9]中使用历史活动的持续时间的平均值作为估计未来活动执行时间的预测值.Maleshkova等人提出了一种在过程数据中利用语义信息的方法[25]，利用相关性分析，选择对活动持续时间有影响的变量，通过将筛选之后的数据集的活动持续时间的平均值作为活动执行时间的估计值.该方法虽然比基于历史数据的平均值作为估计的准确率高，但是其整体模型的预测结果并未达到预期效果.在另一个相关的工作中[26]，作者为了计算活动的执行持续时间，将执行时间分成多个部分，例如，资源准备时间和排队时间等，并对各部分提出由均值和方差作为参数组合构成的回归函数用于计算各部分执行时间，均值和方差通过历史活动数据拟合，最后将各部分执行时间汇总以估计活动的执行时间.在文献[27]中，Wombacher等人对每一个活动开始时间通过同一过程的前一个活动的完成时间来估计，一个活动的持续时间是观察到的完成时间与估计的开始时间的差值，通过对同一活动的所有持续时间取平均值的方法估计该活动的持续时间，该方法的缺点是需要大量的数据信息才有较好的预测效果.另外，我们提出了一种基于张量分解的服务调用活动的时间预测方法，能够预测不同时间段中执行活动所需要的时间[28].

3.3 预测延迟风险

过程预测是运行时过程管理的一个重要方面，它可以帮助过程管理者识别出可能延迟或异常终止的过程实例，并尽早干预以降低业务风险[29].对延迟预测的兴趣是由对等待客户满意度的负面影响的心理洞察所驱动的[30].预测业务流程中的延误和最后期限违规的问题已有一系列的研究.一般情况下，企业可能会签订服务水平协议(Service Level Agreement，SLA)，这些协议是关于预期提供的服务质量[31]的具有法律约束力的协议.对于服务提供商来说，尽可能地防止违反SLA的行为至关重要,因为可以提高客户满意度并避免赔偿.

预测延迟根据实现的方法也可分为两种类型：基于统计学模型和基于黑盒模型的预测.

3.3.1 基于统计学模型

在文献[32]中，Folino等人利用了上下文感知性能预测模型(Context-Aware Performance Prediction Model，CA-PPM)提供预测"超时故障"的能力,对于某一业务过程的"超时故障"的预测是基于完成处理的时间不超过最长等待时间的可能性函数进行计算的，通过对每一个活动剩余执行时间的预测判断该过程是否会出现"超时故障"，而活动剩余执行时间的预测使用[9]中的预测方法.其中对可能发生超时故障的过程触发警报，从而让管理人员提出合理的安排.作者在文献[10]对于正在运行的业务过程，根据预测的剩余执行时间和最后期限时间相结合求出超出最后期限时间的概率.剩余执行时间在第3.1.1小节中已经介绍.超时概率定义为历史实例完成时间超过最后期限样本数量与样本总数量之比的统计值.通过概率判断最终结果是否会超出最后期限时间.

Pika等人定义了一系列过程风险指标(Process Risk Indicators)，通过对日志文件中活动持续时间遵循对数正态分布的假设，并使用统计学技术确定阈值，对于一个给定的活动实例，将其持续时间取对数之后与计算的阈值进行比较实现对活动执行时间异常的检测[33].该方法的缺点需要大量历史活动信息才能提高异常执行时间检测的准确率.

3.3.2 基于黑盒模型

文献[34]中所签订的SLA规定过程的持续时间不会超过最长周期时间(Maximum Cycle Time).作者提出的方法使用了基于软件传感器的体系结构，当传感器判断其风险条件为真，即估计超时概率值超过限定的边界值，传感器则会向管理人员发出通知，管理人员通过该警报实现早期风险检测，从而能够采取适当的补救措施.其中，超时风险概率值的计算是将当前流程执行的时间和使用文献[17]中的方法计算得到的剩余周期时间相结合计算出的.Leitner等人[35]根据记录的历史数据，使用WEKA机器学习框架来构建回归模型.对于正在运行的业务过程，将可用的特征信息输入预测回归模型，输出即为预测的SLA值.通过与规定的SLA值相互比较判断是否超时.

Conforti等人在文献[36]中通过使用历史信息训练函数估计器，根据历史流程中最大的持续时间(最后一个事件和第一个事件的时间戳差值)和SLA规定的流程最大周期时间进行超时错误严重性的测量.对正在执行过程，使用基于决策树的估计器估计当前活动的超时错误概率，并对超出概率风险阈值的活动做出风险通知决定，此方法考虑了执行过程活动中的参与者因素.另外，Suriadi等人将事件日志转换成适合分类技术分析的形式, 使用基于规则的RIPPER分类算法将转换形式之后的日志文件作为输入，输出结果为预测实例是"准时"还是"超时".虽然该文章的目的是找出产生超时的根本原因，但在实现过程中判断实例是否超时则是根据实例的执行时间是否超过规定的阈值[37].

综上所述，对业务过程延迟预测方法进行汇总，具体见表2所示.

表2 业务过程延迟预测方法Table 2 Business process violate prediction method

4 预处理技术

对于复杂的业务过程进行准确的时间预测具有很大挑战，为了减少预测误差，对日志信息进行预处理成为越来越重要的部分.一般来说，提高过程模型精度的一种方法是通过特定的聚类方法对日志进行分割[38，39]，并为每个聚类找到一个(更精确的)模型，将后者应用到一个特殊的过程执行场景[32].下面介绍与事件日志预处理相关的方法.

Hendrik等人在文献[40]中首先将历史日志实例划分为不同的场景(集群)，然后将相应聚类的预测结果作为新实例的预测结果.其思想是同一集群的实例之间的较高相似性将有助于得出更准确的预测值.在文献[41]中，Folino等人首先对数据集进行预处理，通过使用预测聚类树(Predictive Clustering Tree)的形式将与上下文有关的不同执行场景进行预测聚类；然后对于产生的每一个簇，产生一个特定的过程性能模型(Process Performance Mode，PPM)，并通过上下文感知性能预测模型进行剩余时间的预测.此方法对减少预测结果的误差评价指标有很大帮助.基于相同的思想，作者在文献[34]中也充分利用了踪迹的上下文信息，通过对属性进行聚类提高预测的结果.Song等人在文献[38]中也提出了一种对日志轨迹聚类的通用方法，将日志分成更小、更均匀的轨迹子集，可以有效地解决与多样性有关的问题，从而提高预测的准确度.Kang等人[42]也利用SVM技术对正确和不正确的历史踪迹进行分类的预处理方法.在文献[43]中，作者为了解决对异常实例的预测以及预防的问题，介绍了一种基于马尔可夫聚类算法的踪迹聚类技术，该算法能够从多个视角对实例进行聚类，并在对应的聚类中发现实例出现异常的原因.Ferreira等人提出基于一阶马尔可夫链的简单序列聚类算法，序列聚类是一组旨在将许多序列划分为有意义的聚类或类似序列组的方法，可以对不同的行为进行聚类，聚类之后的每个类别都有其独特的特征.此种预处理方法对了解相应聚类行为的基本结构有很大帮助[44].

在原始日志文件上，由于人为或者机械等原因会对数据造成一定程度的损坏[45].为了提高模型预测的结果，需要对文件中一些不完整的、冗余的、错误的数据进行处理[46].预处理技术通过处理缺失值、噪音以及使用聚类或决策树等技术对数据进行预先处理，最终目的是将处理好的数据作为预测模型的输入，使其预测结果更加准确高效.

5 预测效果的评估方法

时间预测效果的评估方法根据其应用的场景不同可分为两类：第一类是预测活动执行时间和过程实例的剩余执行时间(基于回归)；另一类是通过时间预测判断过程实例是否会出现超时情况(基于分类).第一类时间预测质量评估是根据预测结果与实际结果的误差关系决定的，在这里介绍几个主要常用的评估时间预测所使用的度量指标，它们是平均绝对误差(Mean Absolute Error，MAE)，对称平均绝对误差百分比(Symmetric Mean Absolute Percentage Error，SMAPE)，均方误差(Mean Squared Error，MSE)和均方根误差(Root Mean Squared Error，RMSE).第二类时间预测质量评估是根据正确率进行判断的，主要的度量指标包括正确率和召回率.上述具体定义如下：

MAE：它是预测值与实际测量值之间差异的量度，它能更好地反映预测值误差的实际情况.计算方式见公式(1).

(1)

SMAPE：它是MAE的替代方法，因为与传统的误差测量相比，它对零值或接近零值的影响更为稳健.计算方法见公式(2).

(2)

MSE：它是指预测值与实际测量值之差平方的期望值；它可以评价数据的变化程度，其值越小，说明预测模型描述实验数据具有更好的精确度.计算方式见公式(3).

(3)

RMSE：它计算实际观测值与预测值之间的标准差.RMSE可以惩罚更多的异常值或对异常值更敏感.RMSE在预测模型中通常被用作预测结果的度量.计算方式见公式(4).

(4)

正确率：在二分类问题中，如果将一个正例判为正例，那么就可以认为产生了一个真正例(True Positive，TP)；如果对一个反例正确地判为反例，则认为产生了一个真反例(True Negative，TN).相应地，另外两种情况则分别称为伪反例(False Negative，FN)和伪正例 (False Positive，FP)，正确率即预测为正例的真实正例占所有真实正例的比例[47].计算方式见公式(5).

Precision=TP/(TP+FP)

(5)

召回率：即预测为正例的真实正例占所有真实正例的比例.计算方式见公式(6).

Recall=TP/(TP+FN)

(6)

如果同样的数据集即用于训练模型，也用于评估预测的质量，则会导致模型过拟合，为了解决这一问题，需要使用交叉验证技术，交叉验证是将样本数据集划分为两个子集的统计学实践，使得一个子集用于执行分析，而另一个子集用于验证.交叉验证中使用更多的是K折交叉验证(K-fold cross-validation)，其中整个数据集被分割成大小相等的K个集合.在K个集合中，选择一个集合作为测试集合，而其他K - 1集合的集合作为训练集合.然后将交叉验证过程重复K次(折叠)，对产生的K次结果进行平均(或以其他方式组合)以产生单个估计[48].这种方法的优点除了每个数据集都被用作测试和训练数据之外，它还能够提供更准确的模型结果[49]，有助于防止模型出现过拟合，对预测的准确性提高有很大作用.

本节根据时间预测的应用场景不同将评价指标分为两个部分进行阐述，以上评价指标可归纳为预测准确度范畴，预测准确度度量一个预测模型预测时间的能力，是最重要的离线评测指标.因为该指标可以通过离线实验计算，所以方便很多研究人员进行研究.由于时间预测的研究方向不同，采用不同的预测准确度指标，故在本节中总结了多数研究人员使用的预测准确度指标.