Predictive monitoring of business processes

A REPORT ON Predictive Monitoring Of Business Processes:

1 INTRODUCTION Process mining techniques allow the extraction of useful information from the event logs and historical data of business processes (BPs) [60]. This information can help to improve the processes and is generally extracted after the process has been finished. How- ever, the interest to apply process mining to running process instances is increasing.

Predictive monitoring of BPs [56] is one of the sub- fields of process mining and aims to provide timely information that enable proactive and corrective ac- tions to improve process performance and mitigate risks. It can be defined as the set of runtime methods aimed at generating predictive models [23] that can be used for the prediction of a particular value of a process instance given its ongoing trace and the event log of historical traces as inputs. As input of these methods, the event log provides the necessary characteristics which define the process for the pre- diction. Additionally, a complete process model, such as a Petri net (PN), or contextual attributes have been optionally considered as input data. As output of the methods, a predicted value for each running process instance or collection of them is obtained. This value belongs to a given domain, and may be boolean, categorical or numerical depending on the object of prediction, e.g. the remaining time of a process (numeric) or the fulfillment of a certain goal (boolean). Thus, the development of mechanisms to predict these values based on the runtime processing

• A.E. Márquez-Chamorro. Dpto. de Lenguajes y Sistemas Informáticos, University of Seville,Spain. E-mail: amarquez6@us.es

of the event streams exchanged between different information systems is very appealing from a practical standpoint. These predicted values can be metrics or process indicators evaluating the performance of a BP in terms of efficiency and effectiveness, or help to evaluate risks or predict possible service level agreement (SLA) violations.

In the last six years, a variety of different ap- proaches for predictive monitoring have appeared. They have been developed to predict different kinds of metrics, have faced the problem from different angles and have been applied to different domains. However, despite their differences, they all share many commonalities. Therefore, a joint analysis of all these approaches can provide an overall view of them as well as identify new challenges in this field. This is the main goal of this survey, which collects and analyzes a compilation of runtime monitoring prediction approaches on BPs. These relevant and ul- timate methods include techniques based on machine learning approaches, statistical methods, annotated transition systems and hybrid methods. Furthermore, from this analysis, we identify the most relevant con- cepts that compose a predictive monitoring approach and discuss the ways the different approaches are tackling each of them.

Two other issues closely related to the predictive monitoring has received a lot of attention in recent years. First, process deviance mining aims at explain- ing the deviance cases of a process instance [38]. Deviance mining techniques use both normal and deviant traces as input, and returns a set of rules to give the reasons of the possible deviations. Two are the main differences with respect to predictive monitoring, namely: 1) whereas the prediction is per-

1939-1374 (c) 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2017.2772256, IEEE Transactions on Services Computing

2

formed for an ongoing process instance in real time, the deviance analysis is performed after the execution of processes; 2) whereas predictive monitoring uses incomplete ongoing traces for the prediction, deviance mining analyses the complete traces of normal and deviant cases. In the latter case, detection of failures of software systems has been previously considered in [48]. Both approaches, predictive monitoring and detection of failures, have similarities since the input data and the output can be similar for some cases. However, they have two main differences. First, de- spite the similarities in the input data, they are applied to different domains (software systems and BPs) with different characteristics. Second, each approach has aspects not covered by the other. Specifically, predic- tive monitoring also considers other possible objects of prediction such as time predictions, probability of a risk or prediction of the next event, among others that are not relevant for the detection of failures of software systems, whereas the detection of failures of software systems include aspects such as failure tracking and undetected error auditing that are not applicable as is in predictive monitoring of BPs.

Our study can be used to support future efforts of practitioners and researchers in the predictive moni- toring field. On the one hand, practitioners can use the concepts identified as a framework on which a predictive monitoring system for BPs can be built. Furthermore, the discussion on the approaches de- scribed can help to identify the techniques from which they can choose to implement the one that better suites their needs. On the other hand, researchers will obtain twofold support from this analysis. First, the concepts identified and the overall view provided may help guide research efforts on new predictive models that improve the performance of current ap- proaches. Second, new researchers in this area will get a global overview on what is done currently in the field and which are the open challenges that require more research.

The rest of the paper is organized as follows. Section 2 summarizes some basic concepts in the area of predictive process monitoring. In Section 3, the most relevant techniques are described. Section 4 discusses how the current techniques deal with the different steps involved in predictive process monitoring. Fi- nally, Section 5 concludes the paper and identify open challenges in this field.

2 PRELIMINARY CONCEPTS In this section, several useful concepts in the area, as well as the review method considered for the survey, are explained. The general methodology for the predictive monitoring of BPs used in the majority of the papers is presented in Section 2.2. An introduc- tion of input data for the prediction, databases, en- coding, checkpoints and the experimental validation

are shown in Sections 2.3 to 2.6 respectively. Finally, Sections 2.7 and 2.8 introduces the different objects of prediction according to different dimensions (Section 2.7) and, specifically, according to their application domain (Section 2.8).

2.1 Review method

Existing literature in predictive monitoring of BPs was searched in the online repositories of the main technical publishers, including Scopus, Web of Sci- ence (WOS) and Google Scholar. As inclusion criteria, we have incorporated those papers since 2010 that addresses any topic related predictive monitoring of BPs, have been cited at least 5 times (this number of cites have been considered in other surveys to indi- cate relevant papers), and were published in indexed journals, relevant conferences1 and other books and conferences in the area. The 5-cited constraint was omitted for those works published between 2015 and 2017, assuming that, due to a shorter period of time, they have not yet achieved this number of cites. As exclusion criteria, we have excluded those papers not related to the computer science field, not written in English, or not accessible on the Web.

Specifically, we collected computer science papers since 2010 that have either ”predictive monitoring” AND ”business process” (search string 1) or ”business process” AND ”prediction” (search string 2) in their keywords, title or abstract. We have chosen these search strings because these keywords appear consis- tently in the most relevant related work on predictive monitoring. SCOPUS provided 10 results using the search string 1: TITLE-ABS-KEY ( ”business process” AND ”predictive monitoring” ), and 195 results using using the search string 2: TITLE-ABS-KEY ( ”business process” AND ”prediction” ). Filtering by number of cites, we have obtained 37 works from SCOPUS. Additionally, using the same search settings, WOS returns 4 results for search string 1 and 166 results for the search string 2. Only 35 works has more than or equal to 5 authors2. Finally, the same searches were reproduced in Google Scholar, obtaining 199 results for the search strings and considering only the ten first pages for our work. After filtering by the required topic and removing the repeated papers in the different searches, a total of 41 publications were finally considered on the scope of our review. Next, we examined the abstracts of the papers identified in the previous step and filtered them according to the predicted values and types of the different methods.

Figure 1 shows the percentage of published paper from 2010 to 2016. A general upward trend in the number of publications in this area is observed. Two

1. The CORE ranking of conferences has been considered (http://www.core.edu.au/conference-portal)

2. Results of SCOPUS and WOS searches are collected in: goo.gl/r3Qdu7

1939-1374 (c) 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2017.2772256, IEEE Transactions on Services Computing

3

works published in 2017 were also collected in this survey. The distribution of the papers according the publication venue was also considered. A 51, 85% of the presented papers belong to indexed journals. The relevant conferences represent the 37, 03% of the total of papers. A percentage of 11, 11% corresponds to books and other conferences.

Fig. 1. Percentage of published papers per year.

2.2 Predictive monitoring methodology

This section describes a general methodology for the predictive monitoring of BPs. Several differences exist between predictive monitoring and other types of prediction tasks, we point out the following. First of all, process-aware methods are clearly distinct because they use techniques based on the process structure, such as annotated transition and graph-based sys- tems. Second, predictive monitoring is carried out at real-time during the execution of the process instances in a certain period. This implies that the prediction is made at a certain point of the execution, which is named checkpoint. This also affects other factors, such as the evaluation and the creation of the predictive models. Different selection strategies to define the checkpoints have been considered [21], [37]. Finally, even if general machine learning techniques are used such as decision trees (DTs), an adequate encoding of the event log must also be considered. Encoding usually involves a feature engineering task which is always specific to the concrete process and hinder the initial stages of the predictive monitoring process.

Stage 1 of Figure 2 represents the learning phase. In this stage, the event log of a process and, optionally a process model and additional external information will constitute the input data of the predictive mon- itoring method. These input data are then generally encoded in feature vectors that can be interpreted by the predictive algorithm. Then, the predictive method is executed and generates a prediction model as out- put data, based on the knowledge of the traces of the event log. This model is evaluated to asses its validity, using the different traces of process instances as a test set, by means of quality metrics.

Fig. 2. Experimental procedure of a general predictive monitoring method.

Stage 2 of Figure 2 represents the prediction phase for a typical predictive monitoring method. At run- time, the generated model is applied to ongoing instances in a given moment of the execution.Then, the predictive model will determine the value of the predicted outputs for this process instance. It should also be noted that the majority of predictive monitoring techniques collected here consists of an offline and an online component that corresponds to Stage 1 and Stage 2, respectively. In many cases, the offline component, which deals with the generation of the predictive model, is computationally expensive, but the online component (Stage 2), which addresses the predictions based on the the generated model is fast. Figure 2 presented the general stages of a predictive monitoring process that are common to most approaches. However, for specific approaches, each step can be decomposed in more detail. For instance, [33] provides a detailed methodology of predictive monitoring processes based on machine learning approaches.

2.3 Input data The main input data for the predictive monitoring methods is the event log. Table 1 represents a general log of a process where each row represents the execu- tion of an activity of the process and its information. Typically, this information consists of the identifier of the process instance and event and the timestamp where the event was executed. Additional information can also be included in the log, such as the name of the resource who execute the activity or the cost of the activity.

These event logs are generally provided by in- formation systems that record traces about process executions. Massive amounts of information can be generated by one of these systems which are stored in event logs. As a consequence, it is necessary to acquire the more relevant process characteristics for the data management following the classification de- scribed in [14], according to four different perspec-

1939-1374 (c) 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2017.2772256, IEEE Transactions on Services Computing

4

case id event id timestamp ev. resource cost

1

107561 12-12-2016:12.15 A Lucas 100 107562 12-12-2016:14.55 B Lucas 300 107563 12-12-2016:17.30 C Paul 200 107564 13-12-2016:12.15 D Laura 400

2 108631 14-12-2016:10.00 A Fred 100 108632 14-12-2016:12.52 D Fred 200 108633 14-12-2016:13.27 E Barney 100

3 108945 15-12-2016:10.32 B Alan 100 108946 16-12-2016:09.18 E Sylvia 300

TABLE 1 Event log example.

tives. First, the control-flow perspective, related to the order of the activities performed in the process. Second, the data-flow perspective which involves the different attributes attached to the events. Third, the time perspective which is related to various types of duration in the process, such as the duration of an activity or the remaining time of a process. Finally, the resource/organization perspective related to the resource that executes a determined event. These per- spectives can be appreciated in the different columns of the log example (Table 1): an event id, which is a unique identifier of each event, a timestamp (time perspective), that indicates the time and date of the execution of an activity, the name of this activity (control-flow perspective), the resource or person who executes the activity (organization perspective), the cost of the activity and other useful information about the event (data-flow perspective). Some of the gath- ered works [46], [61] also include as input data, a complete process model, represented by for example, a Petri net. However, this does not mean that the process model has to be provided by the user, the model can also be discovered automatically using process mining techniques like in [28]. External or contextual attributes have been also considered as input data (e.g. the weather).

2.4 Encoding

Before building the model, it is necessary to describe an encoding which stores enough information of the process, that will be used as input for the technique employed to build the model. Generally, the encoding for a trace includes only the flow perspective. The data-flow perspective is also incorporated in some encodings, considering the information data of the events and not only the sequence flow. The encoding usually represents the events and their associated in- formation. Different sizes of the historic of events can be considered in the encoding, e.g. some approaches take into account only the last event, a few number of events or the complete process. In addition, in some cases, metrics such as the number of resources involved in a process instance, are computed from the events to provide additional information for building

the model. Finally, this step also includes the com- putation of the value of the metric to be predicted. This value is computed according to the existing attributes of the historical traces, e.g., as a result of a combination or arithmetic operation between two or more properties or as the evaluation of a LTL formula.

2.5 Building the model Several predictive models can be considered accord- ing to the type of object to be predicted. Three examples are cited in the following: A decision or regression tree can be useful to determine a discrete or continuous value of a particular output. Decision or association rules can show different situations for the risk predictions. An annotated transition system can be valid for the prediction of the time completion of a process.

The methods used for building the model can be classified according to its process awareness. A predictive model is process-aware if it exploits an explicit representation of the process model to make the prediction (e.g. an annotated transition system, or a stochastic Petri net). Instead, a non-process-aware predictive model do not use an explicit representation of the process model (e.g. DTs). The process model used in process-aware methods are either provided as input or obtained using a process discovery technique from the event log.

Furthermore, some models need the indication of checkpoints [30], where the prediction is carried out. These points are necessary for machine learning ap- proaches but not for the annotated transition system, because they gather the information about the com- plete process. Each one of the checkpoints should be established before an activity in a BP. For each checkpoint, a predictive model has to be generated for the predictive method. Some of the strategies for the selection could be the choice of checkpoints after each executed decision activity or to establish a check- point for each activity that exceed the mean execution time. Selection strategies to define the checkpoints is considered in [67].

2.6 Evaluation of the model For the accuracy assessment of predictive methods, works in the area have considered the type of method for the prediction (classification or regression) de- pending on the object of prediction. In the case of classification methods, for the prediction of boolean or categorical values, it is natural to use classification measures: Precision represents the number of cor- rectly predicted process instances, while recall reflects the proportion of predicted process instances divided by the total number of instances. Thus, precision =

T P T P +F P

and recall = T P T P +T N

where TP is the number of correct predictions (true positives), FP is the num- ber of predicted false positives and FN represents

1939-1374 (c) 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2017.2772256, IEEE Transactions on Services Computing

5

the number of false negatives. Therefore, TP + FN represents the total number of process instances and TP +FP reflects the total of predicted instances. Some works also determine the accuracy of the methods where accuracy = T P +T N

T P +F P +T N+F N . Accuracy rep-

resents the proportion of correctly classified results (both positive and negative). Furthermore, other re- liable indicator is AUC (Area Under Curve). AUC provides a single measure of a classifier performance and allows the visualization of the trade-off between the true positives rate (recall) and the false positive rate. False positive rate (FPR) is equal to FP/FP+TN and represents the cost of the algorithm. In a AUC diagram, the diagonal line represents a random clas- sifier. Points above the diagonal represent good classi- fication results (better than random). Points below the diagonal represent poor classification results (worse than random). AUC is more resilient to class imbal- ance and takes into account the likelihood scores. The AUC provides a single measure of a classifier performance for evaluating which model is better on average. It allows the visualization of the trade-off between the true positives rate and the false positive rate

In the case of regression methods, for the pre- diction of numerical values, measures of quanti- tative deviance are employed, such as Root-mean Squared Error (RMSE), which calculates the error between the real and the predicted values. Finally, other authors utilised Mean Absolute Error (MAE) which implies more resilience to outliers. Thus, the formulas of RMSE and MAE are, respectively: RMSE=

√ 1 n

∑n t=1(yi −y

′ i)

2 and MAE= 1 n

∑n t=1(yi −

y′i), where y represents the real value, y ′ represents

the predicted value, and n indicates the total number of instances. In this sense, other variations of the cited measures are applied in the literature, such as Root- mean square percentage error (RMSPE), Square root of the mean square error (sRMSE) or Mean absolute error (MAE).

2.7 Predictions

The predictions obtained are any kind of value that can be computed from the event log. Some examples are the next activity that is executed in the process instance, the fulfillment of linear temporal logic (LTL) constraints, the remaining time of the process in- stance, or a risk associated to the appearance of a specific value in a data object of the process instance. These predictions can be classified attending to three dimensions.

Attending to the prediction value, predictions can be classified into two broad categories depending on whether the object of prediction is a categorical or a numerical value. This classification is useful because the methods employed to build the model and the

metrics to evaluate the model usually depend on these categories.

Attending to the scope of the prediction, the value predicted can refer only to one process instance, e.g., the remaining time of the process instance, or it can be an aggregation of several process instances, e.g., the average cycle time of all process instances that finished this month. Only two proposals in the col- lected works deal with aggregations, the other focus on predictions for one process instance.

Finally, attending to the domain to which the pre- diction is applied, the collected works cover four dif- ferent domains: performance indicators, risk predic- tions, SLA violation predictions and other predicted values.

2.8 Application domains

As we have stated in the previous section, we can classify the different predictions according to its appli- cation domain, i.e. performance indicators, risk predic- tions, SLA violation predictions, and other predicted values.

Performance requirements of a BP are specified through process performance indicators (PPIs). In general, PPIs are defined as ”quantifiable metrics that allow us to evaluate the efficiency and effectiveness of a process” [15]. They are aimed to control and improve the process. A PPI reflects the ”critical suc- cess factors of a BP defined within an organisation, in which its target value reflects the objectives pur- sued by the organisation with that BP” [16]. We can consider the categories defined in [15]: time, count, data, state or derived indicators. Time is one of the most valuable indicators during the execution of a BP. Generally, time indicators measure the processing time from a start point to an end point of the process execution. The duration of an activity, the average life- time or the time to completion of a process [39], [62] are other time indicators predicted in the literature. Since time is a continuous value, regression meth- ods are employed for its prediction. Regarding the literature, process-aware systems are mostly used for the forecasting of time. In addition RMSE is the most commonly evaluation metric to asses the performance of the time prediction methods.

A risk prediction provides information about an specific risk and is used as a warning system for future actions. These statistics or measurements are revised periodically to alert the company about the changes that may indicate possible risks. Among the possible risks of a running instance of a process we can consider an abnormal execution time or multiple activity repetitions. In these cases, the training data is often very unbalanced, due to the fact that normal instances are much more usual than abnormal ones. AUC and F-score which provide a trade-off between the true positives rate and the false positive rate

1939-1374 (c) 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2017.2772256, IEEE Transactions on Services Computing

6

should be used for evaluations. Classification meth- ods are used for the prediction of risks, since these predicted values are often discrete values.

Service level agreements (SLAs) define a contract of a determined service between a provider and a customer. SLA violations must be avoided to prevent penalty payments and to enhance the customer satis- faction [30]. The predictions are then used to identify whether a SLA will be violated. Classification meth- ods are generally employed for the SLA predictions.

Other predicted values, such as the abnormal ter- mination or the prediction of the next event of a BP running instance, does not fit into any of the previous categories. However, they provide relevant information for the BP management and are also considered in the survey. Specifically, next event pre- diction appears commonly in predictive monitoring works. Statistical methods, as prediction techniques, and accuracy and precision, as evaluation measures, are generally applied in the literature for this type of prediction.

It is important to remark that the type of pre- diction value and the scope of the prediction have an influence on the method used and the predictive model built. However, this is not the case for the prediction domain. Many proposals in the literature are not tailored to a specific prediction domain, but they can be applied to many different domains if the value predicted (categorical or numerical) is the same. For instance, an approach that relies in DTs can predict any categorical value regardless of whether it is the next event, or the fulfilment of a performance indicator, or the chance a risk appears.

3 METHODS Existing techniques for predictive BP monitoring have been classified according to the process-awareness of the methods, i.e. whether the methodology exploits an explicit representation of the process model to make the prediction or not, and the type of problem, i.e. classification or regression, based on the type of predicted value (categorical or numerical).

3.1 Process-aware approaches

All the process-aware methods and their achieved results are summarized in Table 2. First columns indicates the author, year and the name of the pro- posal (if exists). Second column shows the reference of the work. Third and forth columns represent the quality assessment value and the quality measure. Fifth column shows a description of the dataset for the experimentation. Finally, sixth and seventh columns present the type of methodology for each proposal and the problem which try to solve (type of predic- tion), respectively. This table structure is also followed in the rest of subsections.

3.1.1 Regression methods Among the process-aware regression methods, 3 pro- posals are based on machine learning and 8 are based on annotated transition systems (ATS) and statisti- cal methods. In the majority of cases (7/11) they use RMSE as quality measure and best results are achieved by [9]. Real scenario datasets are employed in 9/11 cases, and public datasets are used in [36] and [46]. Finally, the software of 2 proposals are available ([61] and [52]).