Discovery of effective infrequent sequences based on maximum probability path

Abstract

Process discovery usually analyses frequent behaviour in event logs to gain an intuitive understanding of processes. However, there are some effective infrequent behaviours that help to improve business processes in real life. Most existing studies either ignore them or treat them as harmful behaviours. To distinguish effective infrequent sequences from noisy activities, this paper proposes an algorithm to analyse the distribution states of activities and the strong transfer relationships between behaviours based on maximum probability paths. The algorithm divides episodic traces into two categories: harmful and useful episodes, namely noisy activities and effective sequences. First, using conditional probability entropy, the infrequent logs are pre-processed to remove individual noisy activities that are extremely irregularly distributed in the traces. Effective sequences are then extracted from the logs based on the state transfer information of the activities. The algorithm is based on a PM4Py implementation and is validated using synthetic and real logs. From the results, the algorithm not only preserves the key structure of the model and reduces noise activity, but also improves the quality of the model.

Keywords:

• Effective infrequent sequences
• noise activity
• maximum probability path
• conditional probability entropy
• state transition matrix
• process discovery

1. Introduction

The goal of process mining is to convert data logged as events into actionable objects (W. M. van der Aalst, 2016). There are three core branches in process mining: process discovery, consistency checking, and process enhancement. In process discovery, a well-structured model is expected to be found in the event log. To check whether the event log is consistent with the model, consistency checking techniques are applied to the models and logs. Finally, some event logging information is used to improve or enhance the existing process model during process enhancement. And process discovery plays a crucial role in process mining because this step transforms event logs into easy-to-understand visual graphics. All these event logs are recorded and stored by various information systems (Pecchia et al., 2020), such as movie websites (Wang et al., 2020), financial systems (Alizadeh et al., 2018), etc. But the reality is that not all information is useful.

In the last few years, most of the research has focused on analysing frequent behaviours to study the main part of the business process (Vázquez-Barreiros et al., 2015). However, real-world logs are often mixed with infrequent behaviours, which makes the process of discovery less straightforward. One of these is noisy activity (Xiao et al., 2021), which adds complexity to the system and should be filtered out. Another type of infrequent behaviour is important for improving business systems, such as network intrusions, credit card fraud and airbag pop-ups during car crashes, and ignoring them will lead to major system vulnerabilities. Therefore, not all infrequent behaviours should be treated as noisy activities. However, existing studies (Gúnther & Van Der Aalst, 2007; S. J. Leemans et al., 2013b; Maggi et al., 2012) do not distinguish between effective infrequency and ordinary infrequency. They either assume that this is done in configurations without infrequent noise, or they treat all infrequent behaviour equally. Such an assumption simplifies the analysis, but leads to the loss of important information in it. Thus, it is necessary to distinguish between noise and effective infrequent sequences.

We propose a process discovery algorithm based on maximum probability paths that aim to identify valid infrequent sequences based on the path with the highest probability of occurrence for each trace. Unlike previous methods based on frequency filtering, we aim to analyse strong transfer relationships between activities, which allows us to distinguish between valid and harmful infrequent behaviour. The algorithm uses conditional probability entropy to analyse the operational state of activities and identify noisy activities, allowing for a simplified model structure. Subsequently, we construct state transition matrices for infrequent traces to analyse the correlation between effective low frequencies and the body of the model. This leads to the discovery of effective infrequent behaviours from the logs that have not been attended to. Experiments on synthetic and real logs have shown that it retains not only the major high-frequency components but also the effective infrequent sequences, effectively optimising business processes.

The article structure is organised as follows. We reviewed some related work in Section 2. Section 3 illustrates the motivation of this article with a specific example introduces relevant background knowledge. Section 4 introduces the technology proposed in this paper. We evaluate the algorithm through synthetic logs and real cases in Section 5. Section 6 summarises the algorithm and points out the future research direction.

2. Related work

Existing studies generally focus on frequent behaviour only or treat infrequent behaviour as anomalous. Therefore, the research relevant to this paper is divided into infrequent behaviours in process discovery and the detection of abnormal behaviour.

2.1. Infrequent behaviours in process discovery

Interest in process discovery continues to rise in the field of process mining (dos Santos Garcia et al., 2019). Process discovery enables stakeholders to help understand the most frequent behaviours in business processes, thus early research focused more on frequent behaviours. As one of the pioneers in the field, the alpha algorithm obtains a reasonable network structure from the complete log (W. Van der Aalst et al., 2004). Over the next nearly two decades, a variety of more refined methods have emerged. For example, ILP miner (Van der Werf et al., 2008) algorithm based on regions, Inductive miner algorithm (S. J. Leemans et al., 2013a) based on block structure, Maximal Pattern Mining algorithm (Liesaputra et al., 2016) based on causal network (Augusto et al., 2019), and the discovery algorithm that processes large logs through random sampling (Sani et al., 2021).

There are also studies that consider some infrequent behaviours in real logs, including incomplete executions, noisy activities, error cases, etc. Some of them discovery models from such logs through built-in filters. S. J. Leemans et al. (2013b) expands on S. J. Leemans et al. (2013a) and is able to effectively remove low frequency behaviour. And another variant of it, which analyses incomplete logs through probabilistic behavioural relationships, is able to use very small logs to obtain high-quality results (S. J. Leemans et al., 2014). M. Leemans and van der Aalst (2017) are able to cope with incomplete logs in another scenario caused by cancellation or incorrect processing. van Zelst et al. (2018) filter some undesirable behaviours through built-in sequence coding diagrams. By deleting sequences lower than the set frequency, it ensures the accuracy and fitness of the algorithm. Sun et al. (2019) synthesis of a hybrid dependency with fine-grained filtering of noisy events based on statistical probabilities.

Most existing process discovery techniques work offline, using static historical data stored in event logs. These techniques cannot be implemented when logs are not available for political reasons. So the emergence of online process mining arises at the historic moment. These research methods analyse real-time data flows and provide immediate insight into business processes as they are being executed. In this context, some algorithms have emerged that can handle infrequent behaviours online. Awad et al. (2020) processes online events by buffering or speculative processing so that online data can be analysed. In van Zelst et al. (2020), an event handler is proposed to filter infrequent behaviour from the real-time event stream. Chapela-Campa et al. (2020) focus on the abstraction of infrequent behaviours with which to simplify process models. Mannhardt, de Leoni, Reijers, and van der Aalst (2017) proposes a heuristic data-aware mining method (DHM). It uses a classification method based on frequency-based data attributes to distinguish infrequent trace and random noise.

2.2. Detection of abnormal behaviour

There are anomalous activities that occur relatively infrequently but have a nasty impact. This is why anomalous activity is specifically dealt with in some studies. Ghionna et al. (2008) uses a two-step method to detect outliers in infrequent logs. By calculating log clusters and obtaining their average size, individuals that are hardly part of any cluster or actually smaller than the average size are considered as noise activities. In Sani et al. (2018), a sequence mining algorithm is used to discover the flow relationship between sequential patterns and rules as well as long-distance activities. This filtering method can more accurately detect the removal of abnormal behaviour, especially for event data with severe parallel and long-term dependencies. A new technology derived from information theory and Bayesian statistics in Tax et al. (2019) is proposed to filter out chaotic activities from event logs. Experiments show that the filtering technology is superior to the frequency-based algorithm, but the performance of the four active filtering technologies is highly dependent on the characteristics of event logs. Krajsic and Franczyk (2020) performs unsupervised anomaly detection on event streams in an online scenario, resulting in a better model.

These studies simply either consider only frequent behaviours or look at all infrequent behaviours as one category. The quality of the logs directly affects the effectiveness of the model (Cheng & Kumar, 2015), so as much information as possible about the correct behaviour should be retained in the logs.

3. Preliminaries

3.1. Motivation

The synthetic logs in Table 1 are records that simulate multiple users browsing a web site. We first used FHM algorithm (Weijters & Ribeiro, 2011) for analysis and obtained a causal network. FHM (Flexible heuristics Miner) is a new representation language combination mining algorithm. Its most important feature is the representation of segmentation and connection semantics. This makes the process model easy to understand even in the presence of non-trivial structures, low domains and noise. But FHM can only mine simple remote dependencies, and the implementation of remote mining is not perfect. As a result, the FHM algorithm filters out some existing cases of X, but does not delete X completely, and at the same time leads to incomplete mined models, as shown in Figure 1. iDHM (Interactive Data-aware Heuristics Miner) mining method is improved on the basis of existing heuristic discovery methods. It interactively sets the frequency threshold and dependency to filter logs containing noise (Mannhardt, de Leoni, & Reijers, 2017). Although iDHM effectively filters out noise activity X and obtains a causal network (as shown in Figure 2), there is no guarantee that the deletion does not contain important information.

Figure 1. Process model mined by FHM algorithm.

Figure 2. Process model mined by iDHM algorithm.

Table 1. 1000 logs containing noise activity x and the meaning of the activity.

Id	Trace	Number	Id	Trace	Number
1	〈AFGH〉	$\times 7$	18	〈AIMNOPD〉	$\times 1$
2	〈AXFGH〉	$\times 1$	19	〈AIMNOPH〉	$\times 41$
3	〈AFXGH〉	$\times 1$	20	〈AIMNOQ〉	$\times 8$
4	〈AFGXH〉	$\times 1$	21	〈AIMXNOQ〉	$\times 1$
5	〈AFGHX〉	$\times 1$	22	〈ABCD〉	$\times 121$
6	〈AFKLXD〉	$\times 9$	23	〈ABED〉	$\times 150$
7	〈AFKLH〉	$\times 1$	24	〈AFGD〉	$\times 172$
8	〈AFKNOPXD〉	$\times 1$	25	〈AFXGD〉	$\times 9$
9	〈AFKNOPH〉	$\times 100$	26	〈AIJGD〉	$\times 149$
10	〈AFXKNOPH〉	$\times 2$	27	〈AIJGXD〉	$\times 2$
11	〈AFKNOPXH〉	$\times 1$	28	〈AIXJGD〉	$\times 5$
12	〈AFKNOQ〉	$\times 5$	29	〈AIJGH〉	$\times 4$
13	〈AIJKLXD〉	$\times 1$	30	〈AIJGXH〉	$\times 1$
14	〈AIJKLH〉	$\times 7$	31	〈AXIJGH〉	$\times 2$
15	〈AIJKNOPXD〉	$\times 1$	32	〈AXIMLD〉	$\times 1$
16	〈AIJKNOPH〉	$\times 61$	33	〈AIMLH〉	$\times 121$
17	〈AIJKNOQ〉	$\times 12$

3.2. Background

$A=\{a_1,a_2,\dots ,a_n\}$ is a finite active set. $\mathcal{P}(A)$ represents the power set on A, i.e. the set of all possible subsets of A. $A^{\ast }$ represents the set of all series on A. $\sigma =⟨a_1,a_2,\dots ,a_n⟩$ represents a sequence of length n, subsequence ${\sigma }^{\prime }=⟨a_j,\dots a_k⟩,1\le j<k\le n$ is a subset of sequence A. Empty sequence is marked as ε. The connection of sequence ${\sigma }_1$ and ${\sigma }_2$ is marked as ${\sigma }_1\cdot {\sigma }_2$. One occurrence of an activity forms an event e. And a sequence of events $\sigma$ is the trace in the log. Event $logL$ represents a multi-set of traces (Deshmukh et al., 2020).

Each time a subsequence appears in the log, we count it one time. Therefore, we introduce the concept of subsequence frequency.

Definition 3.1

(Subsequence frequency) (Tax et al., 2019)

L is an event log based on activity set A. The frequency of the subsequence with respect to L is denoted as: (1) $\mathrm{freq}({\sigma }^{\prime },L)=\mathrm{\#}({\sigma }^{\prime },L),{\sigma }^{\prime }\in \sigma .$(1)

Example 3.2

Let $\log L$ has 40 traces. $L=\{⟨ABCDX{⟩}^{10},⟨ABCXD{⟩}^{10},⟨ABXCD{⟩}^{10},⟨AXBCD{⟩}^{10}\}.$

Then, $\mathrm{freq}(A,L)=40$, $\mathrm{freq}(A,B,L)=30$.

Considering the behavioural relationships between the different activities in the log, we introduce the following concept.

Definition 3.3

(Log behaviour profile) (Cao et al., 2018)

Let $L_p=n_1,n_2,\dots$,$n_m$ be a log in the process model $P=(A,a_i,a_0,C,F,T)$, and a pair of transitions $(x,y)\in (A_L\times A_L)$ has at most one of the following two relationships, namely these two relationship are mutually exclusive.

1. strict order relation: ${\to }_{L}L$, iff $x{\succ }_{L}y,y{\nsucc }_{L}x$;

2. interleaving order relation: $|{|}_{L}L$, iff $x{\succ }_{L}y,y{\succ }_{L}x$.

The set of these two relationships is called the behaviour profile in a log. And if activity A to B is strictly sequential, then the relationship from B to A is called strictly inverse sequential.

Definition 3.4

(Conditional Occurrence Probability) (Sani et al., 2017)

L is an event log over and ${\sigma }^{\prime }$ is a subsequence of L. For activity $a\in A$, then a's conditional probability with ${\sigma }^{\prime }$ in L, expressing as $\mathrm{COP}(a,{\sigma }^{\prime },L)$ is defined as follows. (2) $\mathrm{cop}(a,{\sigma }^{\prime },L)=\{\begin{array}{ll}{\displaystyle \frac{\mathrm{freq}({\sigma }^{\prime }\cdot ⟨a⟩,L)}{\mathrm{freq}({\sigma }^{\prime },L)}},& \mathrm{if}\mathrm{freq}({\sigma }^{\prime },L)\ne 0,\\ 0,& \mathrm{otherwise}.\end{array}$(2)

Conditional Occurrence Probability is the probability (W. Yu et al., 2020) that a subsequence will occur in succession with an activity, reflecting the following relationship between the two. If an activity always occurs after a subsequence, then its probability value tends to 1. Conversely, if the activity never occurs after the subsequence, the value is 0.

4. Mining effective infrequent behaviour sequences

Our Effective Infrequent Sequence Miner (EIM) algorithm extracts effective infrequent sequences from logs containing complex. This technique distinguishes effective infrequent from noise by two processes. Since we aim to analyse different types of activity in the infrequent part, we first separate the infrequent from the high-frequency logs. In the first stage, EIM identifies the noise from the infrequent logs by analysing the operational patterns of the activities through Conditional probability entropy to simplify the logs. Subsequently, based on the state transition matrix, EIM calculates the path with the highest probability of occurrence for each trace and retains the traces that meet the filtering criteria.

4.1. Process a single noisy activity in the log

Some activities may occur spontaneously at any moment of process execution. This situation affects the quality of the process model obtained by using process discovery technology (Tax et al., 2019). Not only does the model become more complex, but many mining algorithms cannot get satisfactory results. So our first task is to clear the noisy activity in the log. There are currently two solutions to deal with noise. Delete the corresponding event from the trace: event-level filtering. Delete the trace as a whole: trace-level filtering (Sani et al., 2017). Since trace-level filtering may cause the loss of important information in infrequent logs, we choose event-level filtering.

Due to strict ordering relationships between log activities, e.g. $⟨AB⟩$ and $⟨BA⟩$ correspond to different sequence, we define two new concepts: precursor conditional probability set and successor conditional probability set. They are based on conditional behavioural probability (Definition 3.4). Here, we only consider the previous activity x of activity a. For the sake of convenience, we will directly record the sequence with only one activity as the activity name.

Definition 4.1

Precursor conditional probability set

The precursor conditional probability of activity a is the conditional probability of $⟨x,a⟩$ in the log, which refers to the probability that activity x occurs before activity a: (3) $\mathrm{copp}(a,x,L)=\mathrm{cop}(a,x,L)=\{\begin{array}{ll}{\displaystyle \frac{\mathrm{freq}(x\cdot a,L)}{\mathrm{freq}(a,L)}},& \mathrm{if}\mathrm{freq}(x,L)\ne 0,\\ 0,& \mathrm{otherwise}.\end{array}$(3)

Denoting the subsequence by $X=\{x_1,x_2,\dots ,x_n\}$, we denote it as a tuple when considering the pattern of occurrence of activity a with all activities in the subsequence, denoted as Precursor conditional probability set. (4) $\mathrm{copp}(a,L)=\mathrm{copp}(a,X,L)=(\mathrm{copp}(a,x_1,L),\mathrm{copp}(a,x_2,L),\dots ,\mathrm{copp}(a,x_n,L)),n=|X|.$(4)

Successor conditional probability considers the case where it is inverse to Equation (3(3) $\mathrm{copp}(a,x,L)=\mathrm{cop}(a,x,L)=\{\begin{array}{ll}{\displaystyle \frac{\mathrm{freq}(x\cdot a,L)}{\mathrm{freq}(a,L)}},& \mathrm{if}\mathrm{freq}(x,L)\ne 0,\\ 0,& \mathrm{otherwise}.\end{array}$(3) ). In this case, it reflects the probability that a binding to x occurs and that a is followed by x.

Definition 4.2

Successor conditional probability set

The subsequent conditional probability of activity a is the conditional probability of $⟨x,a⟩$ in the log, which can be expressed as: (5) $\mathrm{copf}(a,x,L)=\mathrm{cop}(x,a,L)=\{\begin{array}{ll}{\displaystyle \frac{\mathrm{freq}(a\cdot x,L)}{\mathrm{freq}(a,L)}},& \mathrm{if}\mathrm{freq}(a,L)\ne 0,\\ 0,& \mathrm{otherwise}.\end{array}$(5)

Successor conditional probability set of activity a is a tuple composed of n successor conditional probabilities, defined as: (6) $\begin{array}{rl}\mathrm{copf}(a,L)& =\mathrm{copf}(a,X,L)\\ & =(\mathrm{copf}(a,x_1,L),\mathrm{copf}(a,x_2,L),\dots ,\mathrm{copf}(a,x_n,L)),n=|X|.\end{array}$(6)

Information entropy $H(x)=-\sum _{x\in X}x{\log }_2(x)$ (Yin et al., 2020) enables the quantification of information and describes the uncertainty of information (Gleick, 2011). In order to apply it to the analysis of the stochastic nature of activities, while integrating the strict-order and inverse-strict-order relationships between activities, we define conditional probability entropy of activity based on conditional entropy in L. Yu et al. (2020).

Definition 4.3

Conditional probability entropy of activity

Hereinafter referred to as entropy, it is used to describe the time and space uncertainty of the activity. (7) $H(a)=H(\mathrm{copf}(a,L))+H(\mathrm{copp}(a,L)).$(7)

Conditional probability entropy reflects the uncertainty degree of known random event y under the condition of activity set X. In the log, the higher the conditional entropy value of activity y is, the higher the uncertainty degree of the time and position of y with respect to the elements of the activity set is. On the contrary, the more random the time and position of y is, the higher the conditional entropy of y. Therefore, we filter the elements with the highest conditional entropy in the log trace to obtain a relatively stable system structure.

Example 4.4

Taking the log in Example 3.2 as an input, activity A is the starting event in the log, so $\begin{array}{r}\mathrm{copp}(A,A,L)=0,\mathrm{copp}(A,B,L)=0,\mathrm{copp}(A,C,L)=0,\\ \mathrm{copp}(A,D,L)=0,\mathrm{copp}(A,X,L)=0.\end{array}$So A's precursor conditional probability set is: $\mathrm{copp}(A,L)=(0,0,0,0,0).$Similarly, the following conditional probability set of A can be calculated as: $\mathrm{copf}(A,L)=(0,\frac{30}{40},0,0,\frac{10}{40}),$ $H(\mathrm{copp}(A,L))=0,H(\mathrm{copf}(A,L))=0.811278124,H(A)=0.811278124,$ $H(B)=1.622556249,H(C)=1.622556249,H(D)=1.622556249,H(X)=4.$

We use Conditional probability entropy for the analysis of infrequent logs and formalise the algorithmic idea as follows.

Algorithm 1: According to the log threshold, the log is divided into high-frequency traces and infrequent traces. We choose the infrequent part of the log. To identify and filter the noise activity, we process the log based on conditional probability entropy. After that, there is no noise activity in the log. We initialise a conditional probability entropy list H and log set Q at first (Algorithm 1:2). And save the log whose frequency is lower than the threshold to the new log set Q (Algorithm 1:3–7). According to Definition 4.3, we calculate the conditional probability entropy of each activity. Under the guidance of entropy, noise activity is identified (Algorithm 1:8–11). The algorithm outputs an infrequent log set without noise activity.

4.2. Mining effective infrequent sequences in logs

The method of filtering infrequent behaviour based on threshold can improve the quality of the model to a certain extent. However, the infrequent behaviour in real life is not necessarily completely noise. Because it may contain some infrequent sequences useful for perfecting the system. This section will analyse the infrequent trace obtained from Algorithm 1. The robustness of the system is enhanced by selecting traces that are highly transferable to the main activity.

In the log sequence $⟨x,y⟩$, suppose the system is in the x state at the time m and in the y state at the time n. The change from time m to time n is called state transition, and the probability from state x to state y is the corresponding transition probability. The state transition matrix is a matrix composed of transition probabilities.

Definition 4.5

State transform matrix

(8) $P=\left[\begin{array}{ccccc}{p}_{1,1}& p_{1,2}& \dots & p_{1,j}& \dots \\ p_{2,1}& p_{2,2}& \dots & p_{2,j}& \dots \\ ⋮& ⋮& \ddots & ⋮& ⋮\\ p_{i,1}& p_{i,2}& \dots & p_{i,j}& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}\right].$(8)

Wherein, it is expressed as the transition probability that the Markov chain is in the state $a_i$ at the time m and is transferred to the $a_j$ at the time m + 1.

Definition 4.6

string editing distance, string editing similarity

Let s and t be two strings, and $|x|$ represents the number of characters in a string x. $\mathrm{ed}(s,t)$ represents the editing distance of two strings. (9) $\mathrm{Sim}(s,t)=1.0-\frac{\mathrm{ed}(s,t)}{max(|s|,|t|)}.$(9)

It refers to the minimum number of times needed to edit (including modify, insert, delete) a single character when changing one string s to another string t. The similarity of string editing between s and t reflects the degree of association between the two.

Algorithm 2: Obtain the index j of each activity Z in the infrequent log activity set in turn, and divide all activities into predecessor $(0,\dots ,j)$ and successor $(j+1,\dots ,n)$ with Z as the dividing point (Algorithm 2: 4–19). Then start from Z and traverse backwards to obtain the set of activities Priori that are most likely to occur from Z (Algorithm 2: 7–10). In the same way, starting from Z and traversing forward, get the most likely set of activities Follow to reach Z. Combine the predecessor set Priori, Z, and the successor set Follow, which is the most likely path through the activity Z in the log (Algorithm 2:11–14). The third step is to use string editing similarity to verify, save the traces less than the threshold, and finally get a processed $\log Q$ (Algorithm 2: 16–20).

5. Evaluation

In this section, we design three experiments to evaluate the correctness of the algorithm proposed in this paper. The first two experiments used synthetic logs, and in the third experiment we analysed actual cases. To measure the quality of the algorithm, we implemented the algorithm of this article based on the open-source project PM4Py.¹ Besides, we developed an EIM software (Figure 3) to verify the validity of the algorithm.

Figure 3. Screenshot of the program running interface.

5.1. Experimental design

In this experiment, we will answer the following two questions:

1. Can the algorithm identify a single noise activity?

2. Can the algorithm reduce the complexity of the model while ensuring the accuracy of the model?

In response to problem (1), we designed experiment 1. The input data is a synthesised logs, including frequent traces and infrequent traces. Then we injected different numbers of noise activities into the log randomly. To answer question (2), we designed experiment 2 and experiment 3. In the first two experiments, Yasper² was used to generate artificial logs. The log has 17 activities, 5068 events, 1000 traces, and the trace frequency is between 1 and 172. The synthetic log has strong controllability, which is convenient for verifying the expected effect. In Experiment 3, the open-source data set BPI Challenge 2020: Request For Payment³ was used to verify the algorithm. The open-source data set has 19 activities, 36,796 events, 6886 traces, and the frequency is between 1 and 3011.

Generally, the frequency of noise occurrence is lower than the normal trace. Therefore, in Experiment 1, the log is divided into high-frequency traces and infrequent traces to be processed separately. To explore the impact of different log thresholds on the results, we use different thresholds (log thresholds ${\delta }_L$) to split the log. Then we inject noise activity in the infrequent log randomly. In this synthetic log, the ratio of traces is between 0.01 and 0.17. Thus, the threshold (noise threshold ${\delta }_N$) range is set in this interval, the step size is set to 0.01, and there are 17 values in total. Since we have separated the high-frequency traces from the infrequent traces, and these infrequent activities account for a small proportion in the log. So injecting a lot of noise will not affect the high-frequency traces. Hence the range of injected noise is set between 0 and 1, the step size is 0.1, and there are 10 values in total. Besides, the location of noise injection has uncertainty, and different locations result in different entropy values. To reduce the error, we take the method of taking the average of multiple experiments. We repeat the experiment 10 times for each setting. In this way, a total of $10\times 17\times 9=1530$ identifications is performed in Experiment 1.

In Experiment 2, the value range is reduced and set between 0 and 0.1, and the step size is set to 0.02. The setting of X is the same as in experiment 1. Let us consider the third threshold involved in the experiment, the similarity threshold. To investigate the impact of the similarity threshold on the results fully, we take 0.1 as the step size, and take values from 0 to the largest value of the infrequent trace similarity in turn. Repeat 10 times as in Experiment 1 and take the average value. After algorithm processing, a log that does not contain noise and contains effective infrequent sequences is obtained. We mine the logs processed by the method of frequency-based filter (FBF) and the Effective Infrequent Sequence miner(EIM) of this article. The mining algorithms used here are Inductive Miner (S. J. Leemans et al., 2013b), Heuristic Miner (Weijters et al., 2006) and Directly-Follows Graph Miner (S. J. Leemans et al., 2015). Then we use fitness F, accuracy P, generalisation G and conciseness S to evaluate the quality of the mining model.

Finally, in Experiment 3, we took a real-life log as input, and set the range of S as the smallest ratio and the largest ratio of the trace. But this experiment will no longer inject noise activity. Since the noise activity characteristics in the example are not as obvious as in the controllable situation, interactive operations with users are provided in the experiment. So we allow users to choose whether to delete suspected noise activities according to the threshold distribution of activities (the box plot in the lower-left corner of Figure 3). The experiment starts with the smallest similarity of the trace and ends with the largest similarity of the trace. A total of 90 experiments are carried out.

5.2. Result analysis

In Experiment 1, under different threshold settings, the average recognition accuracy of the algorithm for injected noise activities reached 99.73%. We plot some of the results in Figure 4. The first number in the legend represents ${\delta }_L$, and the second number represents ${\delta }_N$. The horizontal and vertical coordinates of each polyline represent each activity and its entropy in different thresholds. It can be seen that the original activity A Q entropy in the log fluctuates slightly. Even in different threshold settings, the difference between the largest value and the smallest value is less than 2. And the entropy value of other activities is not significantly different. Yet, the injected noise activity X is more prominent, and its entropy value changes more widely. Besides, the entropy value of X in each broken line is also significantly higher than the value of other activities. Let us further analyse the entropy of X.

Figure 4. The entropy of activities under different threshold settings.

Explanation of Figure 5: Figure 5 shows the average change of X in 10 repeated experiments. Divide the entropy of X into 17 groups. Looking at the trend, as the threshold for dividing the high frequency and low frequency of the log increases, the entropy value of each group X gradually increases. This is because as ${\delta }_S$ increases, more and more traces are classified as infrequent traces. The amount of noise injected increases accordingly, so the entropy value of X will increase slightly. Within each group, as the proportion of injected noise increases, the entropy value of X increases almost linearly. This will give it a clear advantage in comparison with other activities. So we confirmed the effectiveness of the algorithm to identify a single noise activity.

Figure 5. The change of entropy of noise activity in different thresholds.

In Experiment 2, IM, HM, and DFC mining algorithms are used to mine models from logs processed by FBF and EIM. Figures 6–8 shows the experimental results of the above three algorithms at different thresholds. The abscissa represents the set threshold. The three numbers on the x-axis scale represent the log threshold ${\delta }_L$, noise threshold ${\delta }_N$ and similarity threshold ${\delta }_S$. We first analyse the results from the trend. The results show that the same index of the same mining algorithm is less affected by the change of the threshold. Thus, we conclude that the log mining results after EIM processing are stable.

Figure 6. IM mines the model quality of manual logs under the threshold (${\delta }_L-{\delta }_N-{\delta }_S$).

Explanation of Figures 6–8. As shown in Figure 6, the degree of fitness (F-EIM) is less than 0.25 during the whole experiment, which is always above 0.95 and is always higher than F-FBF. The accuracy has been stabilised at 1.0 from the original unstable state, even reaching a smallest of 0.65. As shown in Figure 7, the original accuracy P-FBF is lower than 0.2 (the smallest value of the ordinate in the figure is 0.2, so P-FBF does not appear in the figure). It is higher than 0.9 after EIM treatment. When the HM algorithm in Figure 8 mines the EIM processed log, the simplicity is lower than the original value. Because the EIM algorithm retains part of the effective low frequency, and retains as much as possible to benefit the structure of the business process. Compared with the effective low frequency and useless low frequency as a whole and direct filtering, the EIM processed log retains more structure. Next, we will group by ${\delta }_N$ to analyse the effect of different ${\delta }_S$ in each group on the results. The quality index in Figure 7 fluctuates, so we take the DFG algorithm as an example and take four groups for analysis.

Figure 7. HM mines the model quality of manual logs under the threshold (${\delta }_L-{\delta }_N-{\delta }_S$).

Figure 8. DFG mines the model quality of manual logs under the threshold (${\delta }_L-{\delta }_N-{\delta }_S$).

We take $[0.02-0.5-0.0,0.02-0.5-0.9]$ (a), $[0.04-00-0.0,0.04-0.0-0.9]$ (b), $[0.04-0.5-0.0,0.04-0.5-0.9]$ (c), $[0.06-00-0.0,0.06-0.0-0.9]$ (d), a total of 40 data (Figure 9). The results show that with the increase of ${\delta }_S$, the model's suitability, accuracy, generalisation and simplicity all show an increasing trend.

Figure 9. Partial results of DFG mining synthetic logs.

In Experiment 3, the above three algorithms were used to analyse the real log. Part of the results of the experiment is shown in Table 2. Compare the quality of the model mined using EIM processed logs with the quality of the model mined using original logs (the third row in Table 2). The experimental results show that the logs processed by the EIM algorithm can improve the quality of IM algorithm mining, especially the accuracy and simplicity. The second is the DFG algorithm. The accuracy and conciseness are generally higher than (or remain stable) the original indicators, and the suitability and generalisation are improved when each threshold reaches half or more. Yet, the mining quality improvement ability of HM is limited, and only when the log threshold and the similarity threshold are high, there is a certain improvement. This is because the HM algorithm itself has the ability to deal with noise, it can make trade-offs on the log and remove part of the noise. But as we mentioned earlier, there is no guarantee that the relevance between the retained trace and the model is higher than that of the deleted trace.

Table 2. Model quality metrics under different threshold settings.

Delta	Fitness			Precision			Generalisation			Simplicity
(${\delta }_L-{\delta }_S$)	IM	HM	DFG	IM	HM	DFG	IM	HM	DFG	IM	HM	DFG
Before EIM	0.93	0.95	0.59	0.22	0.85	1.00	0.8	0.78	0.34	0.58	0.76	0.57
0.02–0.1	0.94	0.94	0.10	0.87	0.21	1.00	0.86	0.66	0.33	0.81	0.55	0.68
0.02–0.3	0.94	0.95	0.28	0.87	0.19	1.00	0.86	0.71	0.32	0.81	0.59	0.70
0.02–0.5	0.94	0.95	0.55	0.87	0.20	1.00	0.86	0.72	0.34	0.81	0.60	0.71
0.02–0.7	0.93	0.90	0.73	0.99	0.29	1.00	0.92	0.77	0.64	0.84	0.66	0.78
0.02–0.9	0.93	1.00	0.87	0.99	0.53	1.00	0.92	0.97	0.70	0.84	0.64	0.81
0.04–0.1	0.94	0.94	0.37	0.87	0.20	1.00	0.85	0.67	0.34	0.81	0.55	0.69
0.04–0.3	0.94	1.00	0.38	0.87	0.18	1.00	0.84	0.66	0.35	0.81	0.57	0.70
0.04–0.5	0.94	0.89	0.41	0.87	0.22	1.00	0.84	0.71	0.41	0.81	0.62	0.75
0.04–0.7	0.93	1.00	0.73	1.00	0.54	1.00	0.91	0.93	0.74	0.85	0.60	0.82
0.04–0.9	0.93	1.00	0.88	1.00	0.52	1.00	0.91	0.97	0.76	0.85	0.60	0.81
0.06–0.1	0.93	0.94	0.22	0.71	0.14	1.00	0.79	0.67	0.33	0.83	0.58	0.68
0.06–0.3	0.93	0.92	0.37	0.71	0.14	1.00	0.75	0.59	0.28	0.83	0.59	0.70
0.06–0.5	0.95	1.00	0.21	1.00	0.34	1.00	0.90	0.73	0.38	0.92	0.65	0.79
0.06–0.7	0.92	1.00	0.77	1.00	0.89	1.00	0.90	0.91	0.72	0.92	0.82	0.90
0.06–0.9	0.92	1.00	0.88	1.00	0.88	1.00	0.90	0.98	0.77	0.92	0.88	0.89
0.08–0.1	0.93	0.94	0.41	0.71	0.14	1.00	0.79	0.67	0.33	0.83	0.58	0.68
0.08–0.3	0.93	0.92	0.21	0.71	0.14	1.00	0.75	0.59	0.28	0.83	0.59	0.70
0.08–0.5	0.92	1.00	0.41	1.00	0.34	1.00	0.90	0.73	0.38	0.92	0.65	0.79
0.08–0.7	0.92	1.00	0.77	1.00	0.89	1.00	0.90	0.91	0.72	0.92	0.82	0.90
0.08–0.9	0.92	1.00	0.91	1.00	0.88	1.00	0.90	0.98	0.77	0.92	0.88	0.89
0.1–0.1	1.00	0.94	0.27	0.79	0.11	1.00	0.83	0.66	0.34	0.86	0.58	0.69
0.1–0.3	1.00	0.92	0.37	0.79	0.12	1.00	0.79	0.59	0.29	0.86	0.59	0.71
0.1–0.5	1.00	1.00	0.43	1.00	0.41	1.00	0.98	0.72	0.40	1.00	0.67	0.83
0.1–0.7	1.00	1.00	0.81	1.00	1.00	1.00	0.98	0.91	0.80	1.00	0.89	1.00
0.1-0.9	1.00	1.00	0.91	1.00	1.00	1.00	0.98	0.98	0.86	1.00	1.00	1.00
0.12–0.1	1.00	0.94	0.47	0.79	0.11	1.00	0.83	0.66	0.34	0.86	0.58	0.69
0.12–0.3	1.00	0.92	0.22	0.79	0.12	1.00	0.79	0.59	0.29	0.86	0.59	0.71
0.12–0.5	1.00	1.00	0.43	1.00	0.41	1.00	0.98	0.72	0.40	1.00	0.67	0.83
0.12–0.7	1.00	1.00	0.81	1.00	1.00	1.00	0.98	0.91	0.80	1.00	0.89	1.00
0.12–0.9	1.00	1.00	0.95	1.00	1.00	1.00	0.98	0.98	0.86	1.00	1.00	1.00
0.14–0.1	1.00	0.94	0.43	0.79	0.11	1.00	0.83	0.66	0.34	0.86	0.58	0.69
0.14–0.3	1.00	0.92	0.31	0.79	0.12	1.00	0.79	0.59	0.29	0.86	0.59	0.71
0.14–0.5	1.00	1.00	0.37	1.00	0.41	1.00	0.98	0.72	0.40	1.00	0.67	0.83
0.14–0.7	1.00	1.00	0.81	1.00	1.00	1.00	0.98	0.91	0.80	1.00	0.89	1.00
0.14–0.9	1.00	1.00	0.95	1.00	1.00	1.00	0.98	0.98	0.86	1.00	1.00	1.00
0.16–0.1	1.00	0.94	0.22	0.79	0.11	1.00	0.83	0.66	0.34	0.86	0.58	0.69
0.16–0.3	1.00	0.92	0.37	0.79	0.12	1.00	0.79	0.59	0.29	0.86	0.59	0.71
0.16–0.5	1.00	1.00	0.22	1.00	0.41	1.00	0.98	0.72	0.40	1.00	0.67	0.83
0.16–0.7	1.00	1.00	0.78	1.00	1.00	1.00	0.98	0.91	0.80	1.00	0.89	1.00
0.16–0.9	1.00	1.00	0.95	1.00	1.00	1.00	0.98	0.98	0.86	1.00	1.00	1.00
0.18–0.1	1.00	0.94	0.59	0.79	0.11	1.00	0.83	0.66	0.34	0.86	0.58	0.69
0.18–0.3	1.00	0.92	0.53	0.79	0.12	1.00	0.79	0.59	0.29	0.86	0.59	0.71
0.18–0.5	1.00	1.00	0.31	1.00	0.41	1.00	0.98	0.72	0.40	1.00	0.67	0.83
0.18–0.7	1.00	1.00	0.78	1.00	1.00	1.00	0.98	0.91	0.80	1.00	0.89	1.00
0.18–0.9	1.00	1.00	0.91	1.00	1.00	1.00	0.98	0.98	0.86	1.00	1.00	1.00

In summary of the three experiments, our algorithm effectively filters out noisy activities at the level of model structure and behaviour distribution, and is able to distinguish effective infrequent behaviour from harmful infrequent behaviour, improving the quality of process discovery.

6. Conclusion

Noisy activities often lead to inefficiencies or induce safety problems. The accuracy of process models can be affected by infrequent activities. However, removing all infrequent behaviours as useless sequences would result in the loss of important information. Accordingly, we propose a new approach to identify valid infrequent behaviours in event logs.

We define a two-stage approach EIM.

1. We consider the execution relationships between activities and remove the noise without reducing the quality of the mining. In this phase, we focus only on the low-frequency part of the logs, reducing the amount of data to be analysed. By using a method based on conditional probability entropy, irregular activities can be correctly judged as noise. The algorithm then removes the selected noisy activities for the purpose of cleaning up the dataset.

2. We were able to distinguish between effective infrequent sequences and useless infrequent sequences. The effective infrequent sequences were obtained by analysing each trace with the proposed maximum probability path algorithm, using the strong transfer relationship between activities.

We validated the algorithm using synthetic logs and real logs. The results show that the algorithm can retain as many key behaviours as possible and improve the quality of the findings.

Although the algorithm improves the quality of the mining model to a certain extent, it does not perform well when there is a loop structure in the model. So the loop structure will be considered in the future to expand the application range of the algorithm. At the same time, make full use of the time in the log, user role information and other attributes for further research. Besides, the traditional quality metrics cannot fully reflect the effect of effective infrequent behaviour when measuring mining results. In the future, therefore, we need to explore more reasonable measures of quality.

Acknowledgments

We also gratefully acknowledge the helpful comments and suggestions of the reviewers, which have improved the presentation.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Natural Science Foundation, China [grant numbers 61572035, 61402011], and the Natural Science Foundation of Anhui Province, China [grant number 2008085QD178].

Notes

1 https://pm4py.fit.fraunhofer.de

2 http://www.yasper.org/

3 https://data.4tu.nl/articles/dataset/BPI_Challenge_2020_Request_For_Payment/12706886