Process discovery is one of the key challenges in process mining. It aims at discovering process models from event logs recorded from process executions. One of the main problems with process discovery is that in real event logs often irrelevant or faulty infrequent behavior is present. Process models including such infrequent behavior are complex and hard to understand and hide the relevant main behavior of the underlying process. In this paper we describe a new general approach to filter dependencies between activities that are based on infrequent behavior in a given event log. Afterwards the data can be further analyzed with other methods and converted into a process model. The approach uses statistical methods based on hypothesis tests. Its main advantage is the obtained statistical foundation of the results including an upper bound for the risk of false classifications. We present an implementation and prove its general applicability for real life event logs.
Process discovery is one of the key challenges in process mining. It aims
at discovering process models from event logs recorded from process
executions. One of the main problems with process discovery is that in
real event logs often irrelevant or faulty infrequent behavior is present
(e.g. noise or exceptional behavior) [
There are several process discovery algorithms which are able to
handle infrequent behavior [
We describe a new general approach to filter dependencies between activities that are based on infrequent behavior in a given event log. Afterwards the data can be further analyzed and converted into a process model with other methods. The approach uses statistical methods based on hypothesis tests. Its main advantage is the obtained statistical foundation of the results. In particular, the meaning of the upper bound chosen by the user to classify infrequent behavior is clear, and there is an upper bound for the risk of false classifications.
We exemplarily apply hypothesis tests to filter infrequent observations of directly following events, present an implementation and prove its general applicability for real life event logs. The user sets the following parameters controlling the filtering: – p0: 1 −p0 serves as upper bound for the probability of the occurrence of directly following events being classified as infrequent. – α: serves as upper bound for the error probability of falsely classifying the occurrence of directly following events as infrequent. The result of the filtering is a correlation matrix and a causal footprint omitting observations of directly following events detected as infrequent. These models can be used for further analysis and discovery techniques. The proposed technique can also be used to filter w.r.t. other properties or parts of logs, which can be infrequent, e.g. single occurrences of events in traces, concurrent occurrences of events or complete traces. In the following chapter, all basic notations concerning logs are explained first, then Sect. 3 introduces basic statistical terms as well as definition and general use of hypothesis tests. In Sect. 4 the procedure for detecting infrequent behavior is presented in detail. In Sect. 5 a short comparison to other filtering methods which are also based on fractions of observations of direct following events is given. In Sect. 6 our implementation of the procedure is described and the evaluations of the program are briefly outlined. Sect. 7 gives an outlook on further work. 2
We denote the natural numbers by N and N0 := N ∪ {0}. Let T be a set,
then m : T → N0 is a multiset over T . For a ∈ T we denote by m(a)
the number of occurences of a in m. We write a ∈ m if a is contained
in m, i.e. a ∈ m :⇔ m(a) > 0. A finite multiset m over A with elements
a1, . . . , an is also written in the form [a1m(a1), . . . , anm(an)].
Definition 1 (Event, Trace, Event log [
• An activity a ∈ T is contained in σ if it occurs in σ at any time (a ∈ σ :⇔ σ = ht1, . . . , tni ∧ ∃i ∈ {1, . . . , n} : ti = a). • Let σ = ht1, . . . , tni ∈ T ∗ be a trace with n ≥ 1. We define first(σ) := t1 and last(σ) := tn.
– An event log L : T ∗ → N0 over T is a multiset of traces. The preprocessing method will be demonstrated with the example log L = [ha, b, ci100 207, ha, b, di100 013, hb, a, ci98 020, hb, a, di1 002, hb, a, d, ci15 584]. We use the following ordering relations.
Definition 2 (Ordering relations [
For the example log introduced above, this definition results in the following ordering relations: – >L= {(a, b), (a, c), (a, d), (b, a), (b, c), (b, d), (d, c)} – →L= {(a, c), (a, d), (b, c), (b, d), (d, c)} – #L = {(a, a), (b, b), (c, c), (d, d)} – kL= {(a, b), (b, a)}.
For detecting infrequent behavior, we will use hypothesis tests that analyze how often some event is directly followed by another event in the traces in a given event log. For this purpose, the information on successive events is summarized in the so-called correlation matrix. This matrix is then used for several hypothesis tests to identify which predecessor/successor pairs of events occur so rare in the traces that they are not considered as main process behavior.
Definition 3 (Correlation matrix). Let L be an event log over T . Further, TStart := T ∪{Start} and TEnd := T ∪{End} with Start, End ∈/ T . The correlation matrix for event log L is a square matrix CL := N|0TStart| × N0 |TEnd| with CL := (CiL,j )i∈TStart,j∈TEnd , where
|(i, j)|>L if i, j ∈ T CiL,j = Pσ∈L,first(σ)=j L(σ) if i = Start, j ∈ T , σ 6= λ Pσ∈L,last(σ)=i L(σ) if i ∈ T , j = End, σ 6= λ L(λ) if i = Start, j = End.
Here λ denotes the empty trace and for i, j ∈ T the value |(i, j)|>L is the number of times i is directly followed by j in all traces contained in L. The correlation matrix belonging to our example event log L = [ha, b, ci100 207, ha, b, di100 013, hb, a, ci98 020, hb, a, di1 002, hb, a, d, ci15 584] looks as follows: Start a b c d In our preprocessing method we have to identify the binary causal relations between all occurring activities. In summarized form, the relations of a process are represented in a footprint.
Definition 4 (Footprint). Let R := {→L, ←L, kL, #L}, L an event log and T the set of activities occurring in L.
The footprint of event log L is a square matrix F L := R|T | × R|T | with F L := (FiL,j )i,j∈T , where FiL,j is the relation R ∈ R for which iRj holds. The relation ←L is intuitively defined as a ←L b :⇔ b →L a. Using the ordering relations already determined, we obtain the following footprint for our example log:
a b c d a # k → → b k # → → c ← ← # ← d ← ← → # The result of our preprocessing method is later represented as the updated footprint ignoring the infrequent behavior. 3
As mentioned before, we want to use hypothesis tests to decide which
pairs of events directly following each other should be considered as
infrequent behavior for a given event log. This section first describes some
basic statistical terms according to Hornsteiner in [
A probability distribution frequently occurring with discrete random variables is the so-called binomial distribution. This occurs, for example, when there is a set of objects from which several objects are drawn one after the other (each one is put back before drawing the next one) and checked for a certain property. One object is randomly selected at a time and the number of objects drawn so far is increased by 1. If the drawn object has the desired property, the number of drawn objects with this property is also increased by 1. The drawn object is then put back to the set of the other objects. Now another object can be drawn from the original set. This process is repeated until the desired number of drawn objects is reached. In the hypothesis tests performed by us, all pairs (x, y) of directly succeeding events with predecessor x = a or successor y = b are considered (“drawn”). The desired property is fulfilled exactly by the pairs equal to (a, b).
The probability mass function of a binomially distributed random variable is bn;θ(z) = ( n z · θz · (1 − θ)n−z for z ∈ {0, 1, . . . , n} 0 else.
In this context, θ specifies the ratio of objects with the desired property to the total, n the number of drawn objects and z the number of drawn objects with the desired property. The distribution function of a binomially distributed random variable is calculated as the sum over the individual probabilities and is denoted by B.
Hypothesis tests in general Hypothesis tests can be used to check whether a certain assumption is actually valid with a sufficiently high probability. A hypothesis here is a statement about a certain property of objects of the population. First of all, such an assumption, the so-called hypothesis, has to be made, which will then be tested. In addition, data is needed to check whether the hypothesis should be accepted or declined. For this purpose, a sufficiently large and representative sample of fitting data must be available in order to be able to conclude on the population from this sample. Since we get the information for our sample from a given event log, we need a reasonably large event log to get enough data for our hypothesis tests.
In our preprocessing method we will use one-sided binomial tests. For this kind of test two hypotheses are formulated regarding an unknown parameter p ∈ [0; 1] compared to a known parameter p0 ∈ [0; 1]. Using data from a sample, a hypothesis test is used to decide whether the (unknown) value of p ∈ [0; 1] lies in [0; p0] or ]p0; 1], i.e. whether the null hypothesis H0 : p ≤ p0 or the alternative hypothesis H1 : p > p0 is true. However, this decision cannot be made for sure with a hypothesis test, so there is always a certain probability that the wrong decision will be made. The probability of this error can be estimated, making it possible to make very reliable statements about which of the two alternatives holds.
In our framework, the value p0 is chosen by the user. 1 − p0 determines how often two events a and b must occur in sequence compared to all considered predecessor/successor pairs to be considered main behavior of the process. The unknown parameter p is the probability that a pair (x, y) of directly succeeding events with predecessor x = a or successor y = b does not equal (a, b). If p ≤ p0 (null hypothesis), the probability p is small enough to assume that a directly followed by b occurs often enough to be considered main behavior of the process.
The execution of a one-sided binomial test is based on a sample of size n with a result z = (z1, . . . , zn) that shows how many of the objects contained in the sample have a given property, i.e. in our case zi = 1 if the i-th of the considered pairs equals the pair (a, b), for which a decision is to be made whether it is infrequent behavior, and zi = 0 otherwise. As test statistic the random variable Tn : {0, 1}n → {0, . . . , n} denotes the number of matches in the sample.
As a naive decision rule, we could assume the null hypothesis for a result Tn(z) ≤ np0 and the alternative hypothesis for a result Tn(z) > np0. However, to protect the null hypothesis from being rejected due to an error, the acceptance range of the null hypothesis is slightly increased. For this purpose a critical number k ∈ N with np0 < k ≤ n is chosen. This critical number is used to change the decision rule so that for Tn(z) < k the null hypothesis is now assumed and for Tn(z) ≥ k the alternative hypothesis. Depending on the choice of the value for k, the decision based on it is correct with varying degrees of probability.
Different types of errors can occur when accepting one of the hypotheses. A type 1 error occurs when the null hypothesis is rejected and the alternative is accepted even though the null hypothesis is correct, i.e. falsely classifying a pair of events as infrequent in our case. A type 2 error occurs when the null hypothesis is accepted even though the alternative hypothesis is correct, i.e. falsely classifying a pair of events as main behavior.
Since the null hypothesis should, if possible, only be rejected if it actually does not apply, the probability of a type 1 error should therefore be kept as low as possible. With the function g(p, n, k) := Pn l=k nl pl(1 − p)n−1 the probability of the type 1 error can be specified for p ≤ p0. To keep the probability of this error as low as possible, the function g must be minimized. Overall, the probability of a type 1 error for the described parameters is at most g(p0, n, k) = Pln=k nl pl0(1 − p0)n−1. A low value for this error bound ensures that an incorrect rejection of the null hypothesis occurs only very rarely. Therefore, a so-called significance level α ∈ ]0; 1[ is often given, which defines an upper bound for the type 1 error and thus limits the probability of the null hypothesis being rejected by mistake. So g(p0, n, k) ≤ α should then apply. Using this given α and the known size of the sample n, an optimal value for k can then be determined. For k the smallest possible value kα with np0 < kα ≤ n is used, for which g(p0, n, kα) ≤ α applies. Since a calculation of this value for k is quite time-consuming, usually only an approximation is used. If for σn := pnp0(1 − p0) the condition σn > 3 applies, the value kα can be approximated by kα = dnp0 + σn · u1−αe where u1−α is the (1 − α)-quantile1 of the standard normal distribution. The calculation of u1−α is also time-consuming, but can be quickly determined by looking up already calculated value tables. If the condition is not met, a suitable value for k must be found using the binomial distribution. For this purpose, the formula Pkj
i=0 bn;p0 (i) is used to calculate values for different kj (j = 0, 1, . . . ). For k the value for the lowest j is then used, for which the sum is greater than or equal to 1 − α.
Hypothesis tests in our approach For the application of our preprocessing procedure the user can choose the values for p0 and α and thereby influence the results of the hypothesis tests. The choice of p0 determines how often certain events must occur in sequence to be considered main behavior of the process. This allows the user to decide how often particular behavior must occur so that it is part of the main behavior of the process.
The main advantage of our new preprocessing approach using statistical methods is the obtained statistical foundation of the results including an upper bound for the risk of false classification of events directly following each other (whether they should be considered as main or infrequent behavior of the process) and flexible adaptability of the used probability for the classification. 4
The following section describes the method we have developed for detecting infrequent behavior. First, the data contained in the given event log L is summarized in the corresponding correlation matrix. Afterwards hypothesis tests are performed with it in order to detect infrequent behavior. Each hypothesis test examines the direct succession of a particular pair of events in the event log. The result of each hypothesis 1 For q ∈]0; 1[, the value of z for which P (Z ≤ z) = q holds is called q-quantile. test indicates whether the corresponding pair should be considered infrequent behavior. After all infrequent occurring pairs of activities have been found, we create a footprint that describes the relations between activities of the process recorded in the log, that can be used for further analysis. When creating this footprint, we ignore all pairs of activities that occur infrequently according to the hypothesis tests.
Data preparation In the first step the given event log is converted to the correlation matrix as shown in Sect. 2.
Performing the hypothesis tests To determine which of the dependencies between events contained in the log should be ignored, hypothesis tests are now performed on the correlation matrix of direct successors created in the first step. For each pair of activities from the set of all activities occurring in the correlation matrix (including the fictive activities “Start” and “End”), it is determined whether the direct succession of the two events should be considered infrequent behavior or not w.r.t. the value p0 set by the user. Thus, a one-sided binomial test is performed for each pair of activities (a, b) with CaL,b > 0, since it is precisely when it occurs “too rarely” in the available data that it is considered infrequent behavior. For pairs of activities (a, b) with CaL,b = 0, no hypothesis test has to be performed, since b never occurs directly after a in L, so it is already known that there is no dependency. Our approach is based on counting the number of occurrences of a pair of direct neighbors (a, b) within the traces of the event log L (frequency of ab, |(a, b)|>L ). We identify such an occurrence as infrequent behavior if the number of occurrences is “low” compared to the number of all pairs (x, y) with predecessor x = a or follower y = b. For the decision, we use one-sided hypothesis tests based on the binomial distribution for each pair (a, b). Any direct succession of two events in a trace of event log L is considered to be an observation of the operation, which results shall be examined using the hypothesis tests. A directly succeeding pair with predecessor a or successor b fulfills the property “direct succession of a and b” exactly when it is the pair (a, b). The number of pairs fulfilling this property is the frequency of the subtrace ha, bi, which is registered in the correlation matrix as the value of CaL,b. The total number of pairs with predecessor a or successor b is the number of considered objects (denoted by n in Sect. 3) and is obtained by summing up the corresponding row and column of the correlation matrix.
The user can specify the value pinfrequent, which defines the minimum probability of an event pair with predecessor a or successor b occurring in a trace being (a, b) so that this pair of events is not considered infrequent behavior. For this purpose the user defines the value p0 for the hypothesis tests as p0 := 1 − pinfrequent (thus, p0 is the maximum probability of an event pair with predecessor a or successor b occurring in a trace not being (a, b)). The choice of p0 may depend on the considered event log. A higher value of p0 leads to the classification of fewer pairs of events as infrequent behavior.
The choice of p0 depends on the available information about the process recorded in the log. If, for example, many different events can occur next after the event a, each of these events will occur relatively rarely as a successor to a. Conversely, the same applies to many different possible events as predecessors of an event b. Therefore, if it is known that a process contains many such variations, the value for p0 should be set higher than usual. This information can be obtained by looking at the correlation matrix.
Choosing a value for α depends on how sure you want to be that pairs of activities are not incorrectly classified as infrequent behavior. If you want to avoid such an error, you should set α as low as possible.
We formulate the following two hypotheses: – Null hypothesis H0 : p ≤ p0: The occurrence of a directly followed by b should be considered as main behavior. – Alternative hypothesis H1 : p > p0: The occurrence of a directly followed by b should not be considered as main behavior, but as infrequent behavior.
In this context p is the probability that a pair of direct successors (a, y) or (x, b) is not (a, b). The aim is to restrict the risk of falsely inferring that H1 is true when indeed H0 is (error type 1), by fixing an upper bound α. That means, we determine the smallest value k, such that
p(|(a, b)|>L ≥ k | p ≤ p0) ≤ α, and decide for H1 if the frequency of (a, b) is greater or equal to k.2 If a trace contains a subtrace ha, bi which is classified as infrequent behavior, we discard only that part of the trace for further analysis of the process. This means that the other relationships between events in the trace are still being taken into account when creating the footprint, representing the main relations.
For our sample log L, we perform the hypothesis tests with different values for p0 (p0 = 0.95 / p0 = 0.9) and α (α = 0.05 / α = 0.1). For the tests we need the sets T := {a, b, c, d}, TStart := T ∪ {Start} and TEnd := T ∪ {End}.
For p0 = 0.95 and α = 0.05 we have the null hypothesis H0 : p ≤ 0.95 and alternative hypothesis H1 : p > 0.95. For each pair of activities we have to perform a separate hypothesis test.
For instance, the following results are obtained for the pair (a, c): – n = (Pj∈TEnd CaL,j ) + (Pi∈TStart\{a} CiL,c) = 314 826 + 115 791 = 430 617 – σn = pnp0(1 − p0) = √430 617 · 0.95 · 0.05 ≈ √20 454.31 ≈ 143.02 – Since σn > 3, we can use the approximation, i.e. k0.05 = dnp0 + σn · u1−αe ≈ d430 617 · 0.95 + 143.02 · 1.64e = 409 321.
Because n − CaL,c = 430 617 − 98 020 = 332 597 < 409 321 = k, we assume the null hypothesis to be correct and c directly following a in a trace is not considered infrequent behavior.
As the next pair of activities we consider (a, d): 2 In this setting, we control the false classification of “infrequent behavior” by α. It is also possible to exchange H0 and H1: then the false classification of “main behavior” is controlled by α. – n = (Pj∈TEnd CaL,j ) + (Pi∈TStart\{a} CiL,d) = 314 826 + 100 013 = 414 839 – σn = pnp0(1 − p0) = √414 839 · 0.95 · 0.05 ≈ √19 704.85 ≈ 140.37
Because n − CaL,d = 414 839 − 16 586 = 398 253 ≥ 394 328 = k, we assume the alternative hypothesis to be correct and d directly following a is considered to be infrequent behavior.
The other hypothesis tests show that only the pair of direct successors (a, d) should be considered infrequent behavior. All other pairs occur often enough to be classified as main behavior of the observed process. In the same way we can calculate the hypothesis tests for other values of p0 and α. Using p0 = 0.9 and α = 0.05, the pair (d, c) is identified as infrequent behavior as well as (a, d). For p0 = 0.9 and α = 0.1 the pairs (d, c) and (a, d) are categorized as infrequent behavior. With p0 = 0.95 and α = 0.1, we again find (d, c) and (a, d) as infrequent behavior.
We can see that a lower value of p0 can cause more dependencies to be classified as infrequent behavior, since event pairs must follow each other more often in a relative perspective in order to be considered main behavior. In addition, a higher value for α can also result in more pairs being classified as infrequent behavior, since the threshold for incorrect classification as infrequent behavior is higher.
Generating the footprint Next, the footprint (Def. see Sect. 2) is created for the given event log ignoring all pairs of events detected as being infrequent in the last step. That is, first the relation >L is created as specified in the definition. Then all pairs (a, b) which are considered infrequent behavior according to the corresponding hypothesis test are removed from this relation. Finally, the modified relation >L is used to determine the other relations, which are then summarized in the footprint. The obtained footprint represents the relations between all occurring activities of the process that should be used for further analysis.
The following table shows the footprint of our original event log L.
a b c d a # k → → b k # → → c ← ← # ← d ← ← → # After modifying the footprint using the results of the hypothesis tests, the footprints below are obtained for the different parameter values.
a b c d a # k → # b k # → → c ← ← # ← d # ← → #
a b c d a # k → # b k # → → c ← ← # # d # ← # # As you can see, the direct dependency between pairs of events interpreted as infrequent behavior disappears. All other relations remain as in the original footprint because they were identified by the hypothesis tests as main behavior. 5
There are other filtering methods which are also based on fractions of observations of direct following events.
The Inductive Miner - infrequent (IMi) [
Implementation We implemented our approach as a command line
application h0filterlog using Java [
When analyzing an event log, the tool first prints the footprint built from the input log to the command line (see Fig. 3). Then the correlation matrix is displayed (see Fig. 4) and the hypothesis tests are performed. After all tests have been performed, all pairs of events that were detected as infrequent behavior are shown (see Fig. 5 for results of analyzing our example log with p0 = 0.95 and α = 0.05) and the footprint is printed again, this time ignoring the infrequent behavior (see Fig. 6). Evaluation We tested the implementation with different event logs. To find out its limitations, we also considered some larger logs. The event logs we used for the analysis were provided as xes-files.
We analyzed some event logs that contain up to about 13 000 traces or
up to about 400 different activities. Characteristics and results for the
log with the most traces and the log with the most different activities
are shown in the following table.
We analyzed the log from [
Fig. 6: Footprint of event log after removing infreqent behavior.
The event log with the most activities we analyzed was [
Overall, as we improve our program based on these results, we will try to make the import of logs and the calculation of footprints more efficient. The program uses approximate calculations to compute the hypothesis tests (see Sect. 3). In some cases this approximation cannot be used, which means that the calculation of the hypothesis tests then takes a little longer. We will also try to improve this slightly more time-consuming calculation in the future. 7
The presented method can be considered as proof of concept for using hypothesis test in the context of filtering dependencies between activities in event logs and has still possible gaps and inaccuracies concerning practical applicability: – The resulting correlation matrix may not be sound in the sense that the corresponding direct follows graph may contain events which are not on a path from start to end. We plan to add the possibility to detect and omit such events. – The proposed hypothesis tests for direct following events are used to decide whether observations of causal dependent and concurrent events are infrequent. The population underlying the hypothesis test for direct following events a and b also takes events, which are concurrent to a and/or b, into account (since concurrency is detected after filtering). We plan to develop separate hypothesis tests for deciding whether observations of concurrent events are infrequent, which are applied before considering causal dependency of events. – The same value p0 is used for each pair of events, independent from the number of possible predecessors resp. successors (neighbors) of the events from such a pair. Since the number of neighbors of two events a and b influences the probability p that a and b are neighbors, we plan to examine the calculation and use of individual values p0 for each pair of events depending on the number of possible neighbors of the events. – For each choice of p0 (and α) a separate calculation has to be performed. For each pair of events a lower bound k for the frequency of their direct succession is computed from p0. If the frequency is below k, the direct succession is classified as infrequent. It would be more efficient to calculate (the other way round) for each pair of events a lower bound for p0 from the frequency of their direct succession: If p0 is above the lower bound, then the direct succession is classified as infrequent, otherwise as main behavior. – There are several other properties or parts of logs, which can be infrequent, e.g. events in traces or complete traces. We plan to develop hypothesis tests also for such aspects. – Currently, cycles are not yet recognized as such by our method and the footprint therefore shows, for example, a parallelism between two events that are in a short cycle of length 2. In order to avoid this and other errors that occur in the context of cycles in the future, we are planning to improve our method so that cycles are detected.