Source-linked AI summary
Clustering-Based Predictive Process Monitoring
Chiara Di Francescomarino, Marlon Dumas, Fabrizio Maria Maggi, Irene Teinemaa
TL;DR
The paper addresses the need to predict whether running business-process cases will satisfy predicates while reducing the runtime overhead of model construction. It proposes offline clustering of trace prefixes followed by cluster-specific data classifiers applied online, and reports comparable accuracy with improved response times, high earliness, and low failure rates in a hospital-log evaluation.
Problem
Predictive monitoring must use event sequences and associated data to estimate predicate fulfillment, but the prior runtime model-building approach incurred seconds- or minutes-long overhead on large logs.
Method
The framework clusters historical trace prefixes by control flow offline, builds a classifier for each cluster using event data, and applies the matching classifier to a running case at runtime.
Results
The framework achieved comparable accuracy with significantly improved response times, high earliness, and low failure rates in experiments on a cancer-treatment event log.
Takeaways & Limitations
Offline cluster-specific models provide a practical way to deliver early predictions with low runtime overhead for running business-process cases.
Takeaways & Limitations
Because the experiments use a single log, the results have low generalizability across application domains.
Abstract
from arXiv · showhide
Business process enactment is generally supported by information systems that record data about process executions, which can be extracted as event logs. Predictive process monitoring is concerned with exploiting such event logs to predict how running (uncompleted) cases will unfold up to their completion. In this paper, we propose a predictive process monitoring framework for estimating the probability that a given predicate will be fulfilled upon completion of a running case. The predicate can be, for example, a temporal logic constraint or a time constraint, or any predicate that can be evaluated over a completed trace. The framework takes into account both the sequence of events observed in the current trace, as well as data attributes associated to these events. The prediction problem is approached in two phases. First, prefixes of previous traces are clustered according to control flow information. Secondly, a classifier is built for each cluster using event data to discriminate between fulfillments and violations. At runtime, a prediction is made on a running case by mapping it to a cluster and applying the corresponding classifier. The framework has been implemented in the ProM toolset and validated on a log pertaining to the treatment of cancer patients in a large hospital.
1 Introduction
Predictive process monitoring uses event logs and associated data to estimate whether running cases will satisfy specified predicates. The proposed framework moves model construction offline, clustering trace prefixes by control flow and applying cluster-specific classifiers at runtime to reduce prediction overhead.
- Motivation: Predictive process monitoring estimates how uncompleted business-process cases will unfold and whether specified predicates will hold at completion.Predicates may be expressed in temporal logic or other languages and evaluated over completed traces.
- Motivation: 18 The growing availability of heterogeneous event and attribute data creates opportunities for more accurate monitoring but requires balancing accuracy against efficiency.The framework targets efficient prediction for multiple pending cases while maintaining suitable accuracy.
- Problem: The previous approach built classification models at runtime from similar completed-trace prefixes, causing seconds- or minutes-long overhead on large logs.Although accurate, that approach was unsuitable for high-throughput settings or instantaneous responses.
- Contribution: The proposed framework clusters historical prefixes by control flow offline, trains one data-based classifier per cluster, and applies the matching classifier to estimate predicate fulfillment online.It supports temporal, execution-time, or any boolean predicate evaluated on completed traces.
- Implementation: The framework was implemented in ProM, whose Operational Support environment connects runtime workflow event streams with online analysis providers.The introduction states that the paper also reports implementation variants, real-life experiments, related work, and conclusions.
2 Background
The background introduces clustering and classification as the main techniques underlying the framework. Clustering groups similar unlabeled data, while classifiers assign predefined labels using features such as data attributes.
- Clustering: Clustering organizes unlabeled data into groups whose members are more similar to one another than to members of other groups.The similarity relation is defined through a distance or similarity measure.
- Clustering: Model-based clustering assumes data are generated by a model and iteratively assigns points to the highest-density cluster before recomputing cluster parameters.The method uses cluster means and covariance matrices and requires the number of clusters as input.
- Clustering: DBSCAN groups density-connected points within a radius threshold and minimum point count, while leaving isolated points as noise.Cluster expansion proceeds through dense neighborhoods until each density-connected cluster is complete.
- Classification: Classification learns a function that assigns data to predefined class labels, with decision trees and random forests presented as typical classifiers.Decision trees predict a target from input features using internal decision nodes and class-labeled leaves.
- Classification: A decision-tree leaf represents a class for the feature-value path leading to it, with class probability based on correctly classified training examples along that path.Random forests instead combine votes from multiple independently trained trees using randomized feature selection to reduce correlation and improve robustness to noise.
3 Predictive Monitoring
The framework predicts predicate fulfillment from evolving traces by combining control-flow similarity, event-data encoding, clustering, and classification. It contrasts with an on-the-fly baseline by preparing models offline and querying them during execution.
- Predictive Monitoring: The framework requires a compliance model that classifies completed historical traces as compliant or non-compliant with an evaluable predicate.The experiments use Linear Temporal Logic on finite traces translated into finite-state automata.
- Predictive Monitoring: Historical traces are compared with a running trace using both control-flow characteristics and globally visible data snapshots.A data snapshot records the values of the global process attributes after an activity and all preceding activities.
- On-the-fly Monitoring: The on-the-fly baseline filters historical traces by prefix edit-distance similarity, encodes predicate outcomes with data snapshots, and trains a decision tree at runtime.A similarity threshold controls how many less-similar traces enter the training set; missing data can prevent a prediction.
- On-the-fly Monitoring: The resulting decision tree predicts from the current trace's data snapshot: internal nodes test attributes, arcs represent values, and leaves represent predicate outcomes with support counts.For example, a matching snapshot can yield formula satisfaction when two training examples support the path and one does not.
- Clustering-Based Monitoring: The proposed framework avoids constructing decision trees during execution by clustering historical prefixes with similar control flow and performing data-based classification within each cluster.At runtime, the current partial trace is assigned to a cluster and its associated classifier is used for prediction.
- Clustering-Based Monitoring: The framework selects only some historical prefixes, supporting efficiency and early predictions, then encodes prefixes for clustering using event sequences or pattern frequencies.The number of selected prefixes and the event gap are user-specified, and clustered prefixes are subsequently analyzed from the data perspective.
4 Implementation
The framework is implemented through interchangeable clustering and supervised-learning modules, integrated into ProM as an online predictive-monitoring provider.
- The clustering module supports frequency-based and sequence-based trace encodings together with multiple clustering algorithms.
- The supervised-learning module uses decision trees and random forests to construct predictive classifiers.
- Different framework instances result from combining the available encoding, clustering, and supervised-learning techniques.
- The implementations are integrated into ProM as a Predictive Monitoring Framework operating as an OS provider.
- At runtime, the predictive monitor receives incoming event streams after the clustering and supervised-learning modules process them.
5 Evaluation
The evaluation uses a cancer-treatment event log and compares predictive-monitoring configurations across accuracy, failure rate, earliness, and runtime. The framework can achieve high accuracy or useful accuracy–failure-rate trade-offs, while substantially reducing prediction-time costs relative to the on-the-fly baseline.
- The evaluation uses 1,143 cases and 150,291 events from a cancer-treatment process in a large Dutch academic hospital.
- Predictions are generated every 5 events and accepted only when class support and probability exceed thresholds, with s = 6 and prob ∈ {0.6, 0.7, 0.8, 0.9}.Replay stops when a satisfactory prediction is achieved or the trace ends, in which case the prediction is uncertain.
- Model-based clustering with decision-tree classification reaches accuracy of 0.98 at minConf = 0.9, but the failure rate is 0.64.With failure rate below 0.25, the best accuracy values range from 0.85 to 0.93 across the four predicates.
- DBSCAN with decision-tree classification reaches accuracy of 0.96 with failure rate 0.56; under failure rate below 0.25, best accuracy ranges from 0.82 to 0.91 for three predicates and is about 0.68 for the first.
- Random-forest framework instances have accuracy and corresponding failure rates comparable to or higher than the on-the-fly baseline, while also offering accuracy–failure-rate trade-offs.Across configurations, the framework provides either very high accuracy with high failure rates or good trade-offs at early events.
6 Related Work
Prior predictive process-monitoring approaches emphasize time, risk, abnormal termination, or forecasting perspectives. The proposed framework differs by combining control-flow and event-data information in a general, customizable monitoring framework.
- Existing approaches use annotated transition systems to check conformance, predict remaining processing time, or recommend activities during execution.
- Other methods predict process risks using decision trees, statistical indicators, or fault-detection algorithms applied to historical execution data.
- The proposed technique considers both control-flow and data perspectives when making runtime predictions.
- Unlike narrower approaches, the framework is general and customizable, supporting implementations with different tools and techniques.
7 Conclusion
The paper presents a predictive-monitoring framework that uses historical control-flow and event-attribute data to estimate predicate fulfillment for running cases. Offline cluster-specific models support runtime prediction, with comparable accuracy, faster response times, early predictions, and low failure rates, while evaluation on one log limits generalizability.
- The framework estimates whether a predicate will be fulfilled when a running business-process case completes, using control flow and event-associated data attributes.
- Classification models are constructed offline, with one model per cluster of historical trace prefixes, to reduce runtime overhead.
- At runtime, the system matches a running case to a cluster and applies its classification model for prediction.
- Compared with runtime model construction, the framework achieves comparable accuracy and significantly improved response times, with high earliness and low failure rates.
- Because experiments use a single log, the reported results have low generalizability; future work targets other domains and alternative prediction techniques.