We present a novel information-theoretic framework to detect anomalous traces in business process event logs. Although informationtheoretic approaches to anomaly detection are considered fundamental in data analytics, they have not been considered in the context of event logs. The proposed framework combines a trace-level anomaly score based on statistical leverage, which also gives an indication of the severity of an anomaly, and diferent ways of setting the value of a threshold to detect anomalous traces. The framework has been first proposed in a traditional ofline setting, but we also discuss its extension in the online setting, i.e., when events in a log are considered as a stream.
Business processes span across all departments in an organization, and
information logged during the execution of business processes is available in so-called
event logs [
Event logs are prone to errors due to diferent root causes afecting the process
execution and/or the logging process, such as system malfunctioning or
suboptimal resource behaviour [
Commons License Attribution 4.0 International (CC BY 4.0). of developing methods to identify and possibly correct the anomalies recorded in an event log.
Our work focuses on detecting anomalies at the trace-level in event logs, i.e., anomalous sequences of activities for a case. This problem has been approached initially in the literature relying on a model of correct behaviour, captured for instance by a process model or labelled instances from which a model of positive/negative behaviour can be extracted. More recently, however, machine learning-based approaches have tackled this problem more generally as an unsupervised problem, without any reliance on an existing process model or labelled data.
In this context, this paper gives a brief overview of our recent and ongoing work on trace-level anomaly detection using statistical leverage. We propose a novel information-theoretic measure of anomaly score of a trace, based on the definition of statistical leverage. Besides supporting the anomaly detection task – through the definition of an appropriate anomaly threshold – an anomaly score is also able to represent the severity of anomalies, which is an aspect that cannot be handled naturally by classification-based approaches. The approach has been customised to both ofline and online settings, i.e., treating an event log as a batch of events accumulated over a relatively long period, and as a stream of events that become available as soon as they captured, respectively.
The content of this paper is compiled from our previous publications on
ofline [
Ofline settings: anomaly score and anomaly detection
In statistics, the leverage is a measure capturing how far away one observation
is from other observations in a dataset [
The main idea underpinning our approach is to define an anomaly score for
each trace in a log based on the notion of statistical leverage. To calculate the
leverage of traces in an event log E, this has to be appropriately pre-processed
to obtain a numeric matrix of observations X(E). Similarly to other approaches
in the literature [
3 3 2019/10/29 13:01:13 CaseY 12 42 22001199//1100//2380 1049::4251::5531 CaseID EventID CompleteTimeStamp
1 1 0 0 0 2019/10/27 10:25:21 CaseX 2 0 1 0 0 2019/10/29 12:31:48
3 0 0 1 0 2019/10/29 13:01:13 CaseY 12 00 10 00 01 22001199//1100//2380 0194::4215::5531
Step 2. Concatenate grouped events & 0padding CaseID CaseX 1 0 0 0 0 1 0 0 0 0 1 0 CaseY 0 1 0 0 0 0 0 1 0 0 0 0 0-padding X(E) by zero-padding, where N max = maxσ j∈E (Nj ) is the length of the longest trace(s) in E.
Then, the leverage ˆl(σ j ) of a trace σ j is calculated using the matrix X(E). The leverage of the j-th trace in a log is equal to j-th diagonal element of the projection matrix H(E) = X(E) · (X(E)T · X(E))− 1 · X(E)T :
ˆl(σ j ) = hj,j ∈ H(E)
However, the leverage ˆl(σ j ) defined above sufers from a bias due to
zeropadding, which increases the leverage of longer traces and decrease the one of
shorter traces (which are more likely to be considered similar because they
contain many zero-padded values). In order to counter this issue afecting ˆl(σ j ), the
anomaly score that we propose is a weighted version of the leverage ˆlw(σ j ), which
considers a trace-length weighting factor wj that can optimally be adjusted using
a robustly-fitted model on diferent real-life event logs. The detailed procedure
of defining the weight wj is described in our published paper [
The anomaly score defined above ranges between 0 and 1 and the higher its value the more likely a trace to be anomalous. Therefore, to support anomaly detection, a threshold has to be chosen that discriminates between anomalous (above threshold) and normal (below threshold) traces.
We propose 3 diferent methods to define such a threshold: (i) a deviationbased threshold (M 1), (ii) a statistical distribution-based threshold (M 2), and (iii) a distributional gap-based threshold (M 3).
In M 1, the threshold T is defined by the mean and standard deviation of the anomaly scores of all traces in a log. In particular, a trace is considered anomalous if its score is greater than the sum of the average and the standard deviation of the anomaly scores of all traces in a log, i.e., T = meanσ j⊆ E [ˆlw(σ j )] + stdevσ j⊆ E (ˆlw(σ j )). In M 2, the threshold is defined as the 0.9 quantile of the probability density function of a gamma distribution fitted using the anomaly scores of all traces in a log. Finally, in M 3 the threshold is chosen empirically as the first stationary point of the expected cumulative denisty function of the anomaly score values. The latter method M 3, in particular, is robust because it does not require any prior knowledge about the ratio of anomalies in an event log, and therefore it is easy to use due to its non-parametric design. 2.3
The proposed anomaly detection framework, i.e., the anomaly score and the anomaly threshold to support anomaly detection, has been evaluated on artificial and real life event logs against state of the art anomaly detection techniques (heuristic methods, classification-based and deep learning-based methods). In a nutshell, the evaluation has found that: – For real logs, the proposed framework shows the highest average F1-score, compared with the state of the art baselines, while, for artificial logs, the performance is comparable with the one of best baselines; – The proposed framework is better than the state of the art baselines at maintaining a good performance particularly with low anomaly ratios in event logs; it also shows robust performance regardless of the anomaly ratio, while the performance of the baselines tends to degrade for lower anomaly ratios; – The proposed framework shows a balanced performance in respect of recall and precision, with recall/1.5 ≤ precision ≤ 1.5· recall in most experiments, while other baselines often show skewed performance towards one of the two performance measures.
More details about the evaluation are reported in our original publication [
Adapting the framework to online settings
Anomaly detection in online settings can be crucial for discovering anomalies in process execution as soon as they occur and, consequently, allowing to promptly take early corrective actions. However, the online settings introduce additional challenges such as requirements of adaptability to concept drift, and the finite memory usage.
To cope with these challenges, we have adapted the framework described in the previous section to online settings by considering the two basic concepts of grace period and (trace-based) sliding window. The parameter Grace Period (GP ) specifies a minimum number of traces to be completed, i.e., for which all the events have to be received, before the framework can be evaluated, which prevents running the anomaly detection model at early stages with an insuficient number of received events. The Sliding Window (SW ) aims at keeping the finite Case.70
Event_300
Step 2. Preprocess zero padding the event log of total 300 events (one-hot encoding and zero padding)
Anomaly score ( ) Case.01 0.09 Case.02 0.19 Case.03 0.04 Case.04 0.02 Case.05 0.32 Case.06 0.01 Case.07 0.06 Case.08 0.08 Case.09 0.05 Case.10 0.21
… … Case.70 0.83 Case.71 0.07 Case.72 0.16 Step 3. Calculate anomaly score
Event_ID Case.01 Event_1 Case.02 Event_2 Case.03 Event_3 Case.01 Event_4 Case.02 Event_5 Case.02 Event_6 Case.01 Event_7
… Case.70 Event_297 Case.72 Event_298 Case.72 Event_299 Case.70 Event_300
Event_ID Case.01 Event_1 Case.02 Event_2 Case.03 Event_3 Case.01 Event_4 Case.02 Event_5 Case.02 Event_6 Case.01 Event_7
… Case.70 Event_297 Case.72 Event_298 Case.72 Event_299 Case.70 Event_300 Step 4. Allocate the anomaly score of case.70
to corresponding event (Event_300) memory usage by maintaining only the events of a finite number of recent traces for the analysis.
After having introduced the basic concepts of grace period and (trace-based) sliding window, we now introduce the main procedure for the online anomaly detection in Figure 1. Each time a new event is received, we get a sliding window data Et satisfied with the two parameters GP and W . Then, using the anomaly scoe defined in the previous Section 2, after applying one-hot encoding & zeropadding to Et, we calculate an anomaly score for all traces ˆlw(σ j ) in the sliding window.
For a quicker and fully-automated way of detecting anomalies in online settings, as far as thresholds are concerned, we consider three constant thresholds and one variable threshold. We consider the constant values Tc1 = 0.1, Tc2 = 0.15, and Tc3 = 0.2 and, as variable threshold, the value Tv = meanσ j⊆ Et [ˆlw(σ j )]+ stdevσ j⊆ Et (ˆlw(σ j )), which calculates the threshold based on the mean and standard deviation of the leverage scores of all traces in the sliding window. Based on a set threshold, a trace σ j is labelled as anomalous if ˆlw(σ j ) > T . This procedure is replicated each time a new event is received. The proposed online framework for anomaly detection has been evaluated on artificial and a real life event log. The results obtained can be summarised as follows: – Since event logs are structured by instance observations, not point observations, the performance of the proposed framework becomes high and stable when a suficient number of events have been received for all traces in the window SW ; – The performance (accuracy) of the framework tends to improve as the size of the sliding window increases, although this also leads to increased run time; – The proposed framework shows better recall than precision or F1-score, i.e., the framework is good at recognising correctly the anomalous traces, but often mistakes non-anomalous traces for anomalous ones, therefore creating false positives.
More details about this evaluation are available in our original paper [
This paper has presented a novel information-theoretic framework for anomaly detection of anomalous traces in business process event logs. The proposed framework has been applied to both online and ofline event log settings. The results have shown proposed framework is robust on performance across diferent event logs and even with low anomaly ratios, as well as it can be easily used even by less experienced data analysts owing to its non-parametric design.