When an event log is generated based on the real-life data of an existing process, there is a high probability that apart from events that happen frequently and therefore should be represented in the process model, infrequent behavior is featured in the event log that would make a model generated from this log hardly readable. There are many process discovery algorithms that work with such outliers by filtering infrequent behavior just before or during the creation of an appropriate process model. Less common methods make use of statistical tests to detect infrequent behavior in a preprocessing step. This paper aims to simplify the use of hypothesis tests introduced by Petrak et al. and proposes an approach to delete infrequent behavior without generating unwanted side efects for the process model. Furthermore, we solve a problem regarding the use of hypothesis tests for a process that contains loops and compare the results of hypothesis tests to well-known discovery techniques.
Finding mathematical models for real-life processes is a highly relevant task, since such models can easily be analyzed in a way that shows exactly where the process has its weaknesses and where it can be optimized. However, constructing such a process model by hand leads to results that describe what the process should look like instead of how it actually looks. Therefore, it is highly desired to create such models automatically and analyze them afterwards, so there is no bias present in the model. To automatically construct such a model, a record of the behavior of the process, e.g. in the form of an event log, is needed. However, there are several challenges that make it hard to construct a model from an event log, especially if such a model has to meet some criteria like being readable.
One example of such a challenge is the existence of outliers in the event log – data that is
present in the log but is so infrequent that it does not belong to the important parts of a process.
Related to the existence of outliers is the existence of noise – data in the event log that cannot
occur in the process. There are several causes for noise, such as human error ("I meant to log
a diferent task than I actually did") or technical failure ("A part of the system shut down and
didn’t log a status during a period of time"). While noise is erroneous behavior and should not
be featured in the event log, outliers can very well be part of the actual behavior of the process.
However, removing edge cases of the event log promises to make the remaining behavior and
therefore a suitable process model more clear and readable. Finding such a reasonable model
despite the existence of outliers in the event log is the task of process discovery. Most such
techniques handle noise by using heuristics or by setting thresholds for the maximum amount of
behavior that may be deleted [
As mentioned before, a discovered model needs to meet some quality measures. For example,
we want a process model that is able to replay most of the behavior present in the event log
(but not everything, since infrequent behavior should be excluded) – this trait is measured by
the fitness of a process model. However, fitness alone is not enough for a good process model,
since we can accomplish perfect fitness by simply allowing every behavior, even behavior
that has nothing to do with the process. Therefore, another quality measure is the precision,
which ensures that the process model cannot replay way more than is present in the event
log. The notion of generalization describes how open the model is for reasonable extensions,
i.e. behavior that was not recorded in the log but can happen in the process. Finally, a process
model should be simple and easy to read, so that a human can understand and analyze it –
this trait is measured by the simplicity of the discovered process model. More information on
quality measures for process models can be found in [
In this paper, we continue research on the question of how to discover a "good" process
model for the main behavior of an event log by filtering out infrequent behavior. The idea to
use hypothesis tests to find such outliers in an event log was presented in [
We denote the set of natural numbers {1, 2, 3, . . . } by N and define N0 := N ∪ {0}. For an arbitrary set we call : → N0 a multiset over . For any ∈ , () is the number of occurences of the element in the multiset . We write ∈ if this number is greater than zero, i.e. ∈ :⇔ () > 0. We also write a finite multiset over with elements 1, . . . , in the form [1(1), . . . ,
()].
Definition 1 (Event, Trace, Event log [
Regarding a real-life process, we give every event that takes place a name, which can be an
artificial one (like , , , . . . ) or a descriptive one (like _). A trace then describes a
sequence of events that happened for a special case, e.g. for a customer or a general object.
Definition 2 (Ordering relations [
From these ordering relations > will be of great interest for us, since we want to investigate the neighborhood of two events and decide whether two events directly following each other happen often (i.e. main behavior) or rarely (i.e. infrequent behavior). To do so, we need to know how often two events follow each other, which we can store in the Correlation Matrix: Definition 3 (Correlation matrix). Let be an event log over with , ̸∈ . Further, take := ∪ {}, := ∪ {} and := ⟨⟩, the empty trace. We denote the number of times ∈ is directly followed by ∈ in all traces contained in by |(, )|> . The correlation matrix for an event log is defined as the square matrix : × → N0 with , = ⎪⎧|(, )|> if , ∈ ⎪ ⎪⎪⎨∑︀ ∈∖{ },( )= ( ) if = Start, ∈ ⎪⎪∑︀ ∈∖{ },( )= ( ) ⎪ ⎪⎩( ) if ∈ , = End if = Start, = End.
Recall that is a multiset and hence, for any ∈ , ( ) denotes the number of times the trace is contained in .
Apart from the Correlation Matrix, we can store the information related to which events are directly followed by one another in the Directly Follows Graph, which is a simple directed graph containing all events as vertices. Two vertices and are connected by an edge (, ) if somewhere in the event log is directly followed by . The weight on the edge shows how often this happens in the event log.
Definition 4 (Directly Follows Graph). Let be an event log over a set of activities . The Directly Follows Graph (DFG) for is a weighted directed graph = (, , ) with • := ∪ {, }, • := > ∪ {(, ) | ∃ ∈ : = ( )}
∪ {(, ) | ∃ ∈ : = ( )} and • : → N0, ((, )) := ,.
An example for a Directly Follows Graph will be given in Figure 1 in Section 4, where
we first need the DFG. A useful property of the DFG is that it can easily be translated to a
language-equivalent Petri-net. Leemans et al. [
Definition 5 (Soundness of the Directly Follows Graph [
As a running example for this paper we take a set of activities = {, , , } and an artificial event log which is defined as
= [⟨, , , ⟩100, ⟨, , ⟩50, ⟨, , ⟩100, ⟨, ⟩1000, ⟨, ⟩1000, ⟨, , , , , ⟩100]. To construct the Correlation Matrix, we simply count how often an event 1 ∈ is followed by an event 2 in the event log and add this quantity to the Correlation Matrix in row 1 and column 2.
The artificial event () is used to record how often an event ∈ is the first (last) event in a trace of . The Correlation Matrix is very handy to calculate values needed for the execution of hypothesis tests, which are described in the next section.
Rather recently, Petrak et al. [
Generally speaking, hypothesis tests can be used to check whether a certain hypothesis is valid with a "suficiently high" probability. Such a hypothesis makes a statement about a certain property of the objects in a population. As a simple example, take the set of all researchers in the field of process mining as the population and the statement "At least 80% of researchers in the ifeld of process mining like process discovery" . Since this is a statement that can’t be proved or falsified without asking every single researcher in the population (which would be a rather costly operation) one could easily doubt the correctness of this statement. So next to the already stated Null-Hypothesis 0, we formulate an Alternative Hypothesis 1 stating the contrary: "Less than 80% of researchers in the field of process mining like process discovery" . To check which of the two hypotheses is correct, we take a small sample of the population and check how many researchers of this population like process discovery. We then perform a left-sided hypothesis test to check whether this sample implies that the Null-Hypothesis 0 or the Alternative Hypothesis 1 is true.
In general, let ∈ [
The probability that we chose 1 when in reality 0 is true is called the -error; the
probability that we chose 0 when in reality 1 is true, is called -error. In the context of this
paper, we are especially interested in the -error, which can be bounded by a given when using
hypothesis tests. We then want to find a value such that for a random variable (which can
be understood as the number of elements in a random sample that fulfill the property defined in
0) ( ≤ | 0 is true) ≤ is true. The values of for which this inequality holds can be
determined by using the density-function of the given probability distribution. However, since
this computation is quite time-consuming, we use an approximation for if said probability
distribution is a binomial distribution and the standard-deviation := √︀ · 0 · (1 − 0)
satisfies > 3. In this case, we approximate by
= ⌈0 − · 1− ⌉,
(1)
where 1− is the (1 − )-quantile of the standard normal distribution. A more formal
description of hypothesis tests can be found in [
To detect noise in an event log, Petrak et al. [
(1,2) := {(, ) ∈ × | ( = 1 ∨ = 2) ∧ |(, )|> > 0}, which defines the sample size as the number of events that can follow 1 or can be followed by 2 in the process: := |(1,2)| = ∑︁ |(1, )|> + ∑︁ |(, 2)|> − | (1, 2)|> .
∈ ∈ With the user-given constants 1 − 0 and they then execute a right-sided hypothesis test, which means, for a pair of events (1, 2), they estimate by ⌈0 − · 1− ⌉ and decide for 0 when − | (1, 2)|> < . Since this is equivalent to estimate by the formula in Equation 1 and deciding for 0 when |(1, 2)|> > , we can instead perform a left-sided hypothesis test with the probability 0 as described at the start of this section.
With this idea we can calculate the critical value for which ( ≤ | 0 is true) ≤
holds and check afterwards whether |(1, 2)|> > . If this is true, we accept the Null
Hypothesis 0 and consider 2 directly following 1 as main behavior. Otherwise, we reject the Null
Hypothesis, which means we accept the Alternative Hypothesis 1 and consider 2 directly
following 1 as infrequent behavior. However, if ≤ 3, we need to calculate the critical value
by evaluating the binomial distribution and finding a for which the integral of the density
function from 0 to is less than 1 − . For a more detailed description of this idea, see [
It is notable that in this example the direct neighborhood of the events and has the lowest frequency, but the result of the hypothesis test implies that being directly followed by is main behavior. This is due to the fact that is only followed by or and is only preceded by or . The number of sightings where precedes or follows after is rather small, so that the neighborhood between and can be considered as main behavior. 100 150 1100
1000 1 0 0
Executing the hypothesis test for every pair of events leads to the result that the pairs (, ), (, ), (, ), (, ) and (, ), of direct neighbors are infrequent. Petrak et al. propose to simply delete these direct neighborhood relations from the footprint and use the footprint that was constructed in this way to mine a process model.
We use the approach presented by Petrak et al., but construct a Directly Follows Graph (see Definition 4) instead of a footprint. Gaining a Petri-net from a DFG is rather simple, and we can easily check the soundness of a DFG by performing two Depth First Searches, which gives us the possibility to easily construct a DFG that is sound.
By applying the hypothesis tests to the event log with Algorithm 1 we immediately get a set ⊆ ( ∪ {, })2 of direct neighbors that are part of the main behavior of the event log and a set ⊆ ( ∪ {, })2 of direct neighbors that are infrequent behavior. Obviously, no direct neighborhood can be both main and infrequent behavior, so ∩ = ∅. Let = (, ) be the DFG for our event log. Since we only add behavior to or if we have seen the direct neighborhood at least once in the event log, ⊆ and ⊆ hold. On the other hand, due to the definition of , there is no pair of events in ∪ that is not present in , since contains every pair of direct neighbors that was observed in the event log. Therefore, we can conclude that ∪ = . The DFG for our running example is shown in Figure 1, the black edges are those of the set and the highlighted edges are those of the set . 300 200 50 100 150 1000 150 100
100 2000
When deleting edges from the DFG, we need to be careful, since the deletion of the whole set may lead to a result that is not sound according to Definition 5. This is also the case for the DFG in Figure 1, since without all the highlighted edges, the events and do not lie on a path from to . A process model constructed directly from such a DFG is not sound, so the goal is to delete as many infrequent edges as possible without sacrificing the soundness of the DFG. Deleting every highlighted edge except the edges (, ) and (, ) leads to the result shown in Figure 2.
1 0 0
In general, it is not always clear which set ⊆ should be deleted from the DFG, since the deletion of an edge could lead to a situation where other edges are needed for soundness, whereas said edges would not be needed if wasn’t deleted. Finding the "best" subset of to delete from the DFG is a dificult problem, since it is not clear when one subset is better than another. If we define a function : () → N0 which maps every subset of to a numerical value, where a high value indicates that the subset is a better candidate for deletion than another candidate with a lower value, we have an optimization problem at hand: Maximize ( ) where ′ = (, ∖ ) is a sound DFG and ⊆ . As a default for we propose ( ) := | |, so that edge sets that contain more infrequent edges are preferred for deletion. A naive implementation that solves this problem can be found in Algorithm 2.
Algorithm 2 Deleting infrequent edges from the DFG Input: = (, ), , ⊆ with ∪ = and ∩ = ∅, : () → N0 Output: ′ = (, ′)
← end if end for return (, ∖ ) ← ∅ for each ⊆ do ′′ ← (, ∖ ) if ( ) > () and ′′ is sound then
This algorithm needs (2|| · (| | + ||)) time and is therefore exponential in time, but since the number of infrequent edges, and therefore the cardinality || of , is rather small in the most cases, we accept this naive implementation, since it allows for an easy exchange of the user-given function that should be optimized, and is easy to read. In our running example, this algorithm leads to the sound DFG shown in Figure 2.
As can be seen in the example of Figure 1, loops in the DFG can have a high impact on the population for our hypothesis tests. In this example, executing the loop between and some times artificially increases the number of times when was preceded by another event than and the number of times when after followed another event than . Even though the edges (, ) and (, ) are only encountered in the same trace as the edges (, ) and (, ), the repetition of this loop leads to the efect that (, ) and (, ) are classified as infrequent behavior. In the example of Figure 1 this is not a problem, since these two infrequent edges are not deleted for the sake of soundness. However, the following simple event log shows that we are not always in such a lucky situation: ⟳ = [⟨, , . . . , , ⟩10, ⟨, , , ⟩40, ⟨, , ⟩100]
Executing hypothesis tests on this log leads to the classification of the direct neighborhood between and as infrequent.
Every other direct neighborhood is classified as main behavior by the hypothesis tests, so we get the DFG for ℒ that is shown in Figure 3.
Check (, ) ∈>⟳ : ⇒ (, ) ∈>⟳ is infrequent behavior.
Deletion of the highlighted edge would not violate the soundness of the DFG, but doing so would remove the entire behavior of being followed by one or more s, which is followed by a single . This is a problem, since the neighborhood (, ) would not be classified as infrequent behavior if the event log would feature fewer iterations of the -loop:
To eliminate this problem, we propose a preprocessing step for the hypothesis tests to reduce the number of loop iterations if there is a loop present in the process. To do so, we alter the traces of our event log that contain such a loop for the hypothesis tests. The idea is to construct a DFG for this single trace and find a path from to that cycles less frequently through the loop in the trace, if this is possible. To do so, we firstly introduce the notion of a Trace DFG: Definition 6 (Trace DFG). multigraph = (, ) with
Let = ⟨1, . . . , ⟩ be a trace. The Trace DFG for is a directed • := {, } ∪ {1, . . . , } and • : ( ∪ {, })2 → N0, ((1, 2)) = {︃1 |{ | = 1 ∧ +1 = 2}| if 1 = or 2 = otherwise
For a trace , the Trace DFG is therefore the DFG of the log [ ], where the edge weights of said DFG are interpreted as multiple edges. The Trace DFG for the trace ⟨, , , ⟩ for example is a simple path, the Trace DFG for the trace ⟨, , . . . , , ⟩ is shown in Figure 4. ⏟51 tim⏞es 50
To reduce the number of loop iterations in the Trace DFG we first introduce a new, artificial edge from to , as shown by the dashed dart in Figure 4. The resulting multigraph is eulerian, which means there is a eulerian cycle in .
Theorem 1. Let ∈ * be a trace and = (, ) the Trace DFG of . Then, the graph ′ = (, ∪ {(, )} is eulerian, i.e. contains a eulerian cycle.
Proof. By construction of the Trace DFG, is a path from to that uses every edge in exactly once. With the artificial edge (, ) in ′ this path becomes a cycle that uses every edge in ′ exactly once, i.e. a eulerian cycle.
Since this extended Trace DFG ′ is eulerian, we can find the shortest cycle through ′ that
uses every type of edge in ′ at least once, but no more than the multiplicity of the edges allow.
The problem of finding this shortest cycle is known as the Chinese Postman Problem, which
was introduced by Edmonds et al. [
We implemented the algorithm described in this paper in python, version 3.8, using the process
mining library pm4py [
To check the Petri net for soundness, the external tool WOFLAN [16] is used. Aside from pm4py there are other tools, like Entropia [17], that are also interesting for eficient and robust conformance checking. We plan to investigate these tools in the future and use them to further evaluate our results.
We chose some real-life event logs that are often used to evaluate new process discovery techniques, to test and compare our implementation to other mining-techniques. We used • BPI_Challenge_2012.xes (BPI12), which can be found at [18], • DomesticDeclarations.xes (DD), • InternationalDeclarations.xes (ID), • PermitLog.xes (PL), • PrepaidTravelCost.xes (PTC), • RequestForPayment.xes (RFP), all of which can be found at [19].
We also compared our approach to the technique presented in [
Since the DFM and our approach result in a DFG instead of a Petri net, we also need to convert the DFG into a Petri net to compute the quality measures as implemented in pm4py. To do so we constructed a labeled Petri net = (, , , ) from a DFG = (, , ) as follows: • For each node ∈ a place ∈ is added. • For each edge (, ) ∈ × ( ∖ {}), a transition , ∈ with (,) = is added. • For each edge (, ) ∈ × { }, we also add an edge , ∈ . However, this is a silent transition, i.e. (,) = .
• Finally, for each transition , ∈ two arcs are added: (, ,) ∈ and (,, ) ∈ .
The results of executing the algorithms and the conformance checking methods on the resulting Petri nets can be found in Figure 5. For all evaluated methods and logs, Fitness and Generalization were similarly good. Simplicity also showed consistently good values, except for a few very good results from the DFM. The percentage of fitting traces was consistently very good for DFM, while the other techniques achieved variously good values for diferent logs. The largest diferences between the methods were observed for the Precision and the F-Score. Here, the results for diferent logs vary greatly for the DFM, while IMi achieves rather low results. Both of our new approaches achieve very good values most of the time in these two categories.
It is notable that the approach of [
IMi scores similary to our approach, except for precision and therefore F-Score. This is due to the fact that IMi classifies edges as infrequent with a rather local argument – the frequency of an edge is compared to the frequencies of all other outgoing edges, but not to the frequencies in the full graph. Hence, IMi may often delete single edges from many traces. For example, for the very simple event log [⟨, , ⟩], it can easily be forced to delete the edge (, ) by introducing a trace ⟨, , ⟩ +1 to the event log. Then, the edge (, ) in the DFG becomes infrequent compared to the other outgoing edge (, ) and is therefore deleted. Then, the trace ⟨, , ⟩ can not be replayed, which leads to a worse fitness, but the trace ⟨, , ⟩ can be replayed, even though it is not present in the event log.
With the user-chosen threshold that afects the behavior of the DFM, we have direct control over the fitness of the mined model, so this metric features always very good values. However, since DFM deletes only traces and not single edges, it seems odd that the precision of DFM is as low as it is for some event logs. This may be associated with the fact that in the DFG there is exactly one vertex for every event present in the event log, and therefore some traces that share an event name but have nothing else in common lead to a Petri net where traces can be replayed that are not part of the event log. However, our approach shares the same problem concerning the DFG, which makes it unclear why the precision of our approaches have a much higher precision most of the time. To investigate this behavior further could be an interesting task for future work.
When comparing the simpler version of our method to the one with loop reduction, it can be seen that both versions achieve similar results, which can be explained by the structure of the chosen event logs. It may be interesting to investigate further how the two variants difer on event logs with many loops.
During the execution of the diferent algorithms, the times required to construct a model in each case were measured. These do not include the calculation of the metrics that were afterwards calculated on it. In Table 2, all execution times are given in seconds. Hence, for all event logs and algorithms evaluated, a result could be calculated within a few seconds.
In this paper, we revisited the use of hypothesis tests of Petrak et al. [
Further research should include the evaluation of logs with high loop iterations to verify that the shortening of loops is not only reasonable in theory, but also in practice. It is interesting how often the loop-shortening is relevant in real-life logs and under what circumstances (concerning the underlying process) the necessity of loop-shortening is probable. Also, there are some more techniques that outliers before mining a process model [20, 21, 22], some of which also use statistical ideas. It would be very interesting to see how our approach competes to these techniques. Since the DFG loses information on concurrency, a preprocessing step to detect concurrency may be a topic of further research – as well as the investigation on the existence of event logs that lead to bad results with our approach due to concurrency. [15] F. R. Blum, Metrics in process discovery, 2015. [16] W. M. P. van der Aalst, Woflan: A Petri-net-based Workflow Analyzer, Systems analysis modelling simulation 35 (1999) 345–357. URL: https://publications.rwth-aachen.de/record/ 714622. [17] A. Polyvyanyy, H. Alkhammash, C. D. Ciccio, L. García-Bañuelos, A. A. Kalenkova, S. J. J.
Leemans, J. Mendling, A. Mofat, M. Weidlich, Entropia: A Family of Entropy-Based Conformance Checking Measures for Process Mining, CoRR abs/2008.09558 (2020). URL: https://arxiv.org/abs/2008.09558. arXiv:2008.09558. [18] B. van Dongen, BPI Challenge 2012, 2012. URL: https://data.4tu.nl/articles/dataset/ BPI_Challenge_2012/12689204/1. doi:10.4121/uuid:3926db30-f712-4394-aebc75976070e91f. [19] B. van Dongen, BPI Challenge 2020, 2020. URL: https://data.4tu.nl/collections/ BPI_Challenge_2020/5065541/1. doi:10.4121/uuid:52fb97d4-4588-43c9-9d043604d4613b51. [20] R. Conforti, M. L. Rosa, A. H. t. Hofstede, Filtering Out Infrequent Behavior from Business Process Event Logs, IEEE Transactions on Knowledge and Data Engineering 29 (2017) 300–314. doi:10.1109/TKDE.2016.2614680. [21] X. Lu, D. Fahland, W. M. van der Aalst, Interactively Exploring Logs and Mining Models with Clustering, Filtering, and Relabeling, in: BPM, 2016. [22] D. Brons, R. Scheepens, D. Fahland, Striking a new Balance in Accuracy and Simplicity with the Probabilistic Inductive Miner, in: 2021 3rd International Conference on Process Mining (ICPM), 2021, pp. 32–39. doi:10.1109/ICPM53251.2021.9576864.