A Conformance Checking-Based Approach for Sudden Drift Detection in Business Processes

1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 1 A Conformance Checking-based Approach for Sudden Drift Detection in Business Processes Víctor Gallego-Fontenla, Juan C. Vidal, Member, IEEE, and Manuel Lama Abstract— Real life business processes change over time, in both planned and unexpected ways. The detection of these changes is crucial for organizations to ensure that the expected and the real behavior are as similar as possible. These changes over time are called concept drifts and its detection is a big challenge in process mining since the inherent complexity of the data makes difficult distinguishing between a change and an anomalous execution. In this paper, we present C2D2 (Conformance Checking-based Drift Detection), a new approach to detect sudden control-flow changes in the process models from event traces. C2D2 combines discovery techniques with conformance checking methods to perform an offline detection. Our approach has been validated with a synthetic benchmarking dataset formed by 68 logs, showing an improvement in the accuracy while maintaining a very low delay in the drift detection. Index Terms—Business Processes, Concept drift, Process mining, Conformance checking-based detection F 1 INTRODUCTION R EAL-LIFE processes are not immutable. Instead, they evolve to adapt to changes in their context, as new regulations or new consumption patterns. Changes can be planned by the organization, but also happen unexpectedly. In the first case, the impact on the process can be computed and minimized. But in the second case, it may lead to wrong decisions because of outdated information. Thus, organizations should put in place prevention measures to detect when something is running differently from planned to reduce this negative impact. These unforeseen changes over time are known as concept drifts, which is one of the challenges presented in the Process Mining Manifesto [1]. Changes can be classified based on their distribution over time [2]: (i) sudden drifts (Figure 1a), which means that the new concept replaces the previous one; (ii) gradual drifts (Figure 1b), where the new and the old concepts coexist for some time; and (iii) incremental drifts (Figure 1c), when the transition from the oldest concept to the newest one passes through some intermediate states that are, usually, some kind of combination from both. Furthermore, when changes can be repeated over time, periodically switching between concepts, the change is classified as a recurrent drift (Figure 1d). In this paper, we focus on sudden drift detection. In addition, based on how data are processed [3], concept drift can be: (i) offline, when change detection is made post-mortem, being all data available from the beginning, and (ii) online, when change detection is made on-the-fly, and new data are processed just when it is generated. In this paper we focus on offline concept drift, which additionally faces two challenges: a) the inherent complexity of process models, that can contain and combine different structures such as sequences, loops, parallel branches and choices; and • Víctor Gallego-Fontenla, Juan C. Vidal and Manuel Lama are with the Centro Singular de Investigación en Tecnoloxías Intelixentes (CiTIUS), Universidade de Santiago de Compostela, Galicia, Spain. Juan C. Vidal is also with the Departamento de Electrónica e Computación, Universidade de Santiago de Compostela, Galicia, Spain. E-mail: {victorjose.gallego, juan.vidal, manuel.lama}@usc.es b) the distinction between a change and an outlier which is not always clear [2], [4], [5], [6] and may depend on the application domain and the context of the detection. For example, when analyzing a sales process, the changes caused by the increase in customers on Black Friday can be considered a drift if we analyze the data on a weekly time frame. But if we analyze the data for a whole year to get an overall perspective, these changes can be considered as outliers, because they last for a very short time. Although some authors have proposed different approaches for concept drift detection in process mining [3], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], identifying all possible change patterns [22] with a short delay, allowing organizations to know exactly when the change took place and helping in the identification of the reasons that caused the change, are still a challenge. In addition, many of the existing approaches can only detect some change patterns, which makes them less suitable for real use, as some of the drifts will remain unknown to the organizations. Another issue in some proposals is their high dependence on the end-user, who is required to have some apriori knowledge of the process structure or skills to identify accurately the drift within a set of possibilities. To address the aforementioned issues, in this paper we present C2D2, a novel and fully automatic approach based on discovery and conformance checking techniques for offline detection of sudden concept drifts in the control-flow of process models. The method starts by defining a reference window, that will serve as a ground truth. Then traces are processed by a discovery algorithm to extract the corresponding process model. To process the remaining traces, the window is slid over the log, updating conformance metrics related to that process model. With these conformance values a regression is computed, and when the measurements decrease significantly a drift is detected. The underlying idea is that the value from the conformance metrics computed over the reference model and the new traces should decrease when the latter comes from a modified process, being this enough to determine if a change exists or not with a low This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 2 M1M1M1M1M1 M2M2M2M2M2 Time (a) Sudden drift M1M1 M2 M1M1 M2M2 M1 M2M2 Time (b) Gradual drift M1M1M2M3M4M5M6M7M8M8 Time (c) Incremental drift M1M1 M2M2 M1M1 M2M2 M1M1 Time (d) Recurring drift Figure 1. Types of concept drift based on their occurrence over time. delay. Specifically, the main contribution of this paper is the use of conformance metrics, in particular, fitness and precision, to detect changes in processes, which is a novel and unexplored approach so far. Namely, we propose the use of fitness metrics to detect changes that include traces with behavior not supported by the current process model, and the use of precision metrics to detect changes that imply behavior from the model disappearing from the real executions. C2D2 has been tested using a dataset with 68 synthetic event logs. The results have been compared with the ones obtained by the methods available in the state of the art. C2D2 has proved to be better at the accuracy level, getting better Fscore . In addition, C2D2 gets very low delays, identifying changes closer to the point in which they happened. Getting good values for both metrics is important for organizations for minimizing the number of unidentified changes and for reacting as soon as possible to those changes. The remainder is structured as follows. In Section 2 we analyze the main approaches to concept drift analysis. In Section 3 we define a set of terms necessary to understand correctly our approach. In Section 4 a formal proof of the hypothesis for sudden concept drift detection is presented. In Section 5 we detail our method for offline control-flow process concept drift detection. In Section 6 we present the experimentation performed to validate our approach and how it outperforms the main algorithms from the literature. Finally, in Section 7 we present our conclusions and outline our future work. 2 RELATED WORK Although process mining is a rather active research field, concept drift analysis has not received much attention until recently. It is worth noting that, although the method proposed in this paper focuses on offline detection, online approaches are also considered in the following analysis, because they can be easily adapted to detect this type of change by simulating an online environment from the complete event log. In [7], the authors propose a method for online concept drift detection using a polyhedron-based log representation. Then, they monitor the probability that a trace falls into that polyhedron using the ADWIN algorithm [23]. The main drawback of this approach is that it can only detect the presence of a change, but it does not give any information about when it happened. Online detection is also addressed in [8], where the authors discover a probabilistic process model that, given an activity, assigns a probability to every possible successor, and check how these probabilities evolve throughout the complete log using statistical hypothesis tests. Although the method identifies drifts in most cases, small changes in less likely activities generate changes in the probabilities that can stay undetected. In [9] the authors propose an online approach based on the extraction of histograms from traces and then use a clustering algorithm to generate groups of similar traces. A change is triggered when a new cluster appears. An important drawback of this approach is that events order is not accounted for. Thus, it can only detect the addition or removal of new activities, but not the changes in the precedence relations between them. In [3], the authors use a fixed-size window over some features extracted from the follows/precedes relations present in traces, and statistical hypothesis tests to evaluate whether these features have changed significantly. The weak point of this method is that it requires a lot of interaction from the user, including previous knowledge of the process model and the areas where the changes can be located. An extension of this work has been proposed in [11], where the authors implement a recursive bisectioning approach. Specifically, they take the traces that are involved in a drift detection and recursively split them into halves, intending to automatically localize the change. A drawback of this approach is that it still requires the user to know the possible changes to obtain good results. A similar solution is presented in [12], where the authors propose the usage of event class correlation as a feature, and apply statistical hypothesis tests to detect changes. However, it fails in detecting some change patterns such as the changes in the execution order of activities. Another approach followed by some authors is the usage of clustering techniques to detect the drift. In [14], the authors cluster traces using the distance between pairs of activities. However, this approach does not support models with loops. Moreover, the distance can ignore certain change patterns depending on how many activities are affected by the change. In [15], the authors extend a trace clustering algorithm [24] adding a time dimension to force clusters to include only consecutive traces, and thus be able to detect changes. Their approach highly depends on the number of clusters, fixed by the user, and only obtain good results when the number of clusters is equal to the number of changes. In [16], the authors use a Markov clustering algorithm over different time windows to detect changes, but the approach does not focus on the control-flow perspective. Instead, multiple viewpoints of the process are taken into account simultaneously, mixing control-flow changes with behavioral and resource changes. Another interesting approach, called ProcessDrift, is proposed in [17], where the authors transform traces into partialordered-runs and then apply a statistical hypothesis test over two windows (one for reference and one for detection) to detect changes. The main drawback of this approach lies in its sensitivity to changes in the frequencies of certain relations present in the log, which may lead to false positives in the detection. A related method is presented in [21], where the authors focus on detecting the change at the event level instead of at trace level. Specifically, they extract the α+ relations from two consecutive adaptive windows This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 3 of events, and then, applying a statistical test, namely the G-test, compare the relations distribution of these two windows. This allows the detection even with unfinished executions, and reduce the detection delay. The drawback of this approach is that it requires high amounts of traces to be able to detect changes, being possible to ignore them when they are close to each other. In [18], [19] the authors apply graph metrics to detect changes. In [18], the authors compare the eigenvectors and the eigenvalues of undirected weighted graphs representing the log at different instants. In this graph, each vertex represents a trace. The edges weight is the similarity between the vertex (traces) it connects. However, this method needs a huge amount of traces, being unable to detect changes in logs with less than 2,000 traces. In [19] the authors compare models over time using graph features, such as the node degree, the graph density or the occurrence of nodes and edges. However, this approach does not perform well in processes with loops. In [20] the authors present TPCDD, a method that transforms the event log into a relation matrix using direct succession and weak order relations, where each column represents a trace and each row a relation. Then, based on the trend of these relations, it generate candidate drift points. These points are clustered using DBSCAN, to group candidates that belong to the same drift point. This approach relies heavily in the user defining a correct radius for the DBSCAN algorithm, potentially getting a high number of false positives when it is too low and a high number of false negatives when it is too high. In [25], authors propose an algorithm for detecting sudden drifts in event streams using relation frequency maps and an adaptive window. They propose the use of an ADWIN with different distances between these frequency matrices, so a change would be detected if two consecutive frequency maps are different enough. The main drawback with this approach lies in choosing a good distance metric that serves to detect all types of drift in any context. A similar approach to the proposed one is presented in [26], where the authors perform the drift discovery over an event stream using a sliding window and process histories. A process history is a collection of every process model used to represent the behaviour in the event stream along time. For detecting changes they compute the fitness between the last known model from the process history and the trace for the current event, considering that a trace fits a model if the computed fitness is over a threshold. If the trace that is being processed does not fit the last known model, they discover a new one by using only the unfitting traces from the window. To avoid false positives due to anomalous executions, they also assign a score to the model, and these positives are considered viable only if the computed score is over a threshold. Finally, detected changes are classified based on the models present in the process history, using two thresholds. The drawbacks of this approach are that it requires the end-user to provide multiple parameters (the window size and 4 different thresholds), and that it can not detect all types of change in the model, as when optional parallel paths from the model change to an exclusive choice. Finally, an interesting job is presented in [27], where multiple configurations for [3] and [17] are tested in a real Table 1 An example of a process log. Case Timestamp Activity Resource Cost 1 01-01-2010 10:00 A User 1 10 1 01-01-2010 11:30 B User 2 4 1 01-01-2010 11:40 C User 3 6 1 01-01-2010 15:00 D User 3 11 1 02-01-2010 08:00 E User 1 7 1 02-01-2010 09:00 G User 1 5 2 01-01-2010 12:00 A User 3 12 2 01-01-2010 12:10 C User 2 2 2 02-01-2010 07:25 B User 2 17 2 02-01-2010 13:15 D User 1 18 2 02-01-2010 13:25 E User 3 18 2 02-01-2010 14:00 G User 2 1 3 01-01-2010 11:45 A User 3 4 3 01-01-2010 12:30 B User 1 7 3 03-01-2010 10:00 C User 3 13 3 03-01-2010 17:25 D User 1 1 3 03-01-2010 17:30 F User 2 117 3 03-01-2010 17:35 G User 3 3 life scenario, showing the complexity of the concept drift detection in process mining. With C2D2 we take the aforementioned issues and try to minimize them to improve the results of the process drift detection. The method removes any user interaction in the drift detection, requiring only a minimum window size to be specified. Moreover, the method can detect all change patterns independently of the process structure. Furthermore, the method is designed to identify drifts with low delay, minimizing the detection of false negatives and positives. 3 PRELIMINARIES Below we present some concepts needed to understand the proposed method. The method takes an event log of a process and tries to detect the changes in the execution of that process over time. Definition 1 ( Event ) . An event ε represents the execution of the activity α in the context of a process. Events have some mandatory attributes such as the activity, the execution case or the execution timestamp. They can also have optional attributes, such as the resource that performed the activity, the variables that were modified or the location. Definition 2 ( Trace ) . A trace is an ordered sequence of events τ=hε1, ..., εni where every event belongs to the same execution case. Definition 3 ( Log ) . A log is defined as an ordered collection of traces L=hτ1, ..., τni where each trace represents one execution of the process. The size of the log, denoted as |L| , represents the number of traces in that log. Table 1 shows an example of a log, where each row is an event, and dotted lines separate different traces. In addition to the mandatory attributes, the log has information about who performed the activity and the cost of executing that activity. For clarity, in the rest of the paper we represent traces as a sequence of ordered activities, without showing the rest of the attributes, and logs as collections of traces, ordered by the timestamp of their last event. This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 4 AB CDE FG Figure 2. Example of a Petri net representing a process model. A process model is a graph that describes the log behavior, that is, a graph that can replay the log traces. A process model contains a representation of the coordination between the process activities, through sequences, parallels, choices and so on. In this paper we formalize process models using Petri nets. Definition 4 ( Petri net ) . A Petri net is a tuple N= (P, T, F ) , where: •Pis a finite set of places •Tis a finite set of transitions; •P∩T=∅; and •F⊆(P×T)∪(T×P)is a set of directed arcs. Given x∈T∪P , the set •x={y|(y, x)∈F} is the set of inputs of x, and x•={y|(x, y)∈F}the set of outputs of x. Given a Petri net N= (P, T, F ) , a marking of N is a mapping M:P→N, where Nis the number of tokens in the place. Processes usually have a unique start place s∈P which has no inputs ( •s=∅ ) and a unique end place f∈P which has no outputs ( f•=∅ ). The initial marking of the Petri net M0 contains only the initial place M0(s)=1∧ ∀q6=s∈P: M0(q)=0 . For a transition t to be fired, all its input places must contain at least one token ( ∀p∈•t:M(p)≥1 ). When t is executed, it consumes a token from each of its inputs and puts a token in every of its outputs. Petri nets can be depicted as bipartite graphs, being transitions represented as rectangles and places as circles. A black bullet into a place represents a token. Figure 2 shows a Petri net example. In this example, the process is conformed by the activities A , B , C , D , E , F and G . In real executions, A must be executed first. Then, B and C can be executed in any order. After these two activities are finished, D is executed. Then, exclusively one of E or F must be executed. Finally, G is executed and the process execution finishes. The quality of a process model N with respect to a log L can be estimated comparing the allowed and the observed behaviour through some well established metrics such as fitness and precision. Definition 5 ( Fitness metric ) . Given a log L and a process model N , the fitness can be defined as a function γ:L×N→ R which represents the fraction of the observed behaviour that is captured by the model [28]. Fitness can be represented by the following expression, where B represents the allowed behaviour of N: γ=|L∩B| |L|(1) For instance, every trace in the log from Table 1 fits perfectly in the model depicted in Figure 2, because they can be fully executed from start to end. Conversely, traces hA, B, D, E, F, Gi or hA, C, D, E, F, Gi do not fit the model because D can not be executed without executing both B and C previously and, furthermore, E and F can not appear both in the same trace. Definition 6 ( Precision metric ) . Given a log L and a process model N , the precision can be defined as a function ρ: L×N→R which measures the fraction of the allowed behaviour that is observed in the log [28]. Precision can be defined by the next expression, where B represents the allowed behaviour of N: ρ=|L∩B| |B|(2) For instance, if we compute the precision of the model depicted in Figure 2 against cases 1 and 2 from the log in Table 1, the value will be lower than when using the full log, because the model allows for executing alternatively E or F, but in the first two traces only Eis observed. Although there exist multiple ways to compute these metrics, these approaches can be grouped in two main groups [29]: 1) Metrics based on replaying the log over the model, like in [30], where each trace is re-executed over the model in order to detect discrepancies. 2) Metrics based on the alignment between the log and the model, like in [31] and [32], where an alignment is computed between the expected and the observed behaviour (namely, the one supported by the model and the one presented in the log). Despite using Petri nets for modeling the processes, not all discovery algorithms use this representation. Indeed, the literature contains multiple ways for representing a process model (e.g., process trees or heuristics nets). However, these representations can be translated to an equivalent Petri net without loosing information. Moreover, all the conformance metrics used in this paper need a Petri net as its input [33]. Using Petri nets as an intermediate representation of the processes allows C2D2 to be agnostic with respect to the chosen discovery and conformance metrics. It is worth mentioning that, although the proposed algorithm is agnostic to a specific metric, results will depend, to a large extent, on the ability of the metric to stabilize over time. In order to study the impact that the choice of a particular metric may have, tests have been carried out using metrics that are well established in the state of the art. Specifically, the following metrics were used: Alignment Based Fitness [31] and Negative Event Recall [34] for fitness; and Advanced Behavioural Appropriateness [35] and Negative Event Precision [34] for precision. In addition, two new metrics are proposed (one for fitness and one for precision). The proposed metrics are better suited for this problem (Section 5.3) and, as we will see below, obtain better results in change detection, in addition of having a lower computational complexity. One of the objectives in this paper is the identification of changes in the process structure over time. This is done exploring the traces generated by the process and assessing if the more recent traces are product of the same process model. The concept of a sliding window captures this latter set of traces. Definition 7 ( Sliding window ) . Given a log L and an integer n≤ |L| , a sliding window of size n over the log L can be defined as the sublog that at instant i contains the last n This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 5 τ0τ1τ2τ3τ4τ5τ6τ7 ω0ω1ω2 Figure 3. Example of the sliding window behaviour. traces, denoted by ωi=hτi, ..., τi+ni . When a new trace is read from the log, i is incremented, so the oldest trace from the window is forgotten, and the new one is added at the end of the window (ω(i+1) =hτ(i+1), ..., τ(i+1)+ni). Figure 3 shows an example log and the behaviour of a six-sized sliding window over it. At instant 0 , the sliding window ω0 contains traces τ0 to τ5 . When a new trace is read from the log, i is incremented, so the oldest trace in the window ( τ0 ) is forgotten and the new trace ( τ6 ) is added to the window. This behaviour continues until the full log has been read. The structural evolution of the process over time, e.g., to adapt to new context circumstances or organization needs, is known as a drift candidate. Definition 8 ( Drift candidate ) . Let ωi=hτi, ..., τi+ni and ω(i+1) =hτ(i+1), ..., τ(i+1)+ni be two consecutive windows over a log. Let Ni= (P, T, F ) and Ni+1 = (P∗, T∗, F∗) be the models describing the behaviour observed in ωi and ω(i+1) respectively, mined using a discovery algorithm. We say that the trace τi+n is a drift candidate when any of the following conditions is satisfied: •T6=T∗ , which means that there are different activities in both models •F6=F∗ , which means that the conections between activities have changed. A drift candidate indicates a potential change point in the log, which has to be confirmed ex post. To prevent false positives due to the presence of noise or anomalous data, a trace τj will be considered as a confirmed change if it was marked as a drift candidate and several of the next traces are also marked as drift candidates. 4 CONFORMANCE CHECKING BASED DRIFT DETECTION The algorithm proposed in this paper is based on the assumption that changes in the model structure (drifts) can be detected through changes in fitness or precision. Theorem 1. Fitness detects changes related to unsupported behaviour that is being observed, but it can not detect fitting behaviour that is disappearing from the log. Proof. Let us suppose a log L , a model M , and let B be the behaviour supported by M . Also, let us suppose that every trace in the log is supported by the model. ∀τ∈L:τ∈B=⇒L⊆B=⇒L∩B=L If we replace the former property in Eq. (1) and Eq. (2), then: γ(L,N) = |L| |L|ρ(L,N) = |L| |B| Now, let us suppose we observe a new trace τ∗ that is not part of the supported behaviour, that is, τ∗/∈B . If we add τ∗ to L, Eq. (1) and Eq. (2) can be written as: γ(L∪τ∗,N) = |(L∪τ∗)∩B| |L∪τ∗|=|(L∩B)∪(τ∗∩B)| |L∪τ∗| ρ(L∪τ∗,N) = |(L∪τ∗)∩B| |B|=|(L∩B)∪(τ∗∩B)| |B| If we apply the assumption that every trace is supported by the model to the former equation then: γ(L∪τ∗,N) = |L∪ ∅| |L∪τ∗|=|L| |L|+ 1 ρ(L∪τ∗,N) = |L∪ ∅| |B|=|L| |B| Thus, γ(L,N)> γ(L∪τ∗,N) and ρ(L,N) = ρ(L∪τ∗,N) , i.e., when a new behaviour arises in the log, fitness can detect the change but precision can not. Theorem 2. Precision detects changes related to the fitting behaviour that is disappearing from the log, but it can not detect new unsupported behaviour that is being observed. Proof. Let us suppose now a trace τ∗ , which behaviour is unique, disappears from the log. In this situation, Eq. (1) and Eq. (2) are equivalent to: γ(L\τ∗,N) = |(L\τ∗)∩B| |L\τ∗|=|(L∩B)\τ∗| |L\τ∗|=|L\τ∗| |L\τ∗| ρ(L\τ∗,N) = |(L\τ∗)∩B| |B|=|(L∩B)\τ∗| |B|=|L\τ∗| |B| Since all the behaviour in the log is supported by the model, the equations can be simplified to: γ(L\τ∗,N) = |L\τ∗| |L\τ∗|=|L| − 1 |L| − 1 ρ(L\τ∗,N) = |L\τ∗| |B|=|L| − 1 |B| Therefore, γ(L,N) = γ(L\τ∗,N) and ρ(L,N)> ρ(L\ τ∗,N) , i.e., when some behaviour disappears from the log the fitness can not detect changes but precision can. Corollary. Fitness and precision separately can not detect all possible changes in the process structure, but a combination of both can. To illustrate these theorems, let us suppose the models N1 and N2 depicted in Figure 4a and Figure 4b. The difference between both models is that activities B and C are in parallel in N1 , but in sequence in N2 . Let us also suppose that the process N1 changes to N2 at instant i= 8 , which log is represented in Figure 4c, henceforth denoted as L1 . Traces τ1 to τ8 correspond to the execution of N1 and traces τ9 to τ16 correspond to N2 . In L1 , the concurrent execution of activities B and C becomes a sequence from τ9 onwards. After this change, traces are still replayable, so the fitness remains unaltered. However, no trace in the window contains the path A→C→D from τ9 onwards, so the precision falls. This can be seen in Figure 4e, where precision falls because the model allows more behaviour than is present in the traces, but fitness remains unaltered. This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 6 AB CDE FG (a) Model N1. A B CD E F G (b) Model N2. ID Trace τ1ABCDEG τ2ACBDEG τ3ABCDFG τ4ACBDFG τ5ABCDEG τ6ACBDEG τ7ABCDFG τ8ACBDFG τ9ABCDEG τ10 ABCDFG τ11 ABCDEG τ12 ABCDFG τ13 ABCDEG τ14 ABCDFG τ15 ABCDEG τ16 ABCDFG (c) Log generated using N1 as the initial process and N2 as the modified one. ID Trace τ1ABCDEG τ2ABCDFG τ3ABCDEG τ4ABCDFG τ5ABCDEG τ6ABCDFG τ7ABCDEG τ8ABCDFG τ9ABCDEG τ10 ACBDEG τ11 ABCDFG τ12 ACBDFG τ13 ABCDEG τ14 ACBDEG τ15 ABCDFG τ16 ACBDFG (d) Log generated using N2 as the initial process and N1 as the modified one. 2 4 6 8 10 12 0.97 0.98 0.99 1 i measurement Fitness Precision (e) Fitness and precision evolution when using a window of size 4, log from Figure 4c and reference model N1 2 4 6 8 10 12 0.85 0.9 0.95 1 i measurement Fitness Precision (f) Fitness and precision evolution when using a window of size 4, log from Figure 4d and reference model N2. Figure 4. Measurements evolution for two logs with different changes. Let us now suppose a different change, from model N2 to N1 , at the same time instant, which log is represented in Figure 4d, henceforth denoted as L2 . Traces τ1 to τ8 are generated by N2 while traces τ9 to τ16 by N1 . In L2 , B and C , originally in sequence, are in parallel from τ9 onwards. This change can not be detected using precision (the model does not generate more behavior than the present in the log), but it can be detected though fitness, since τ10 , τ12 , τ14 and τ16 can not be replayed by N2 . This situation is represented in Figure 4f, where precision remains unchanged, but fitness falls in the 7th iteration of the algorithm. 5 ALGORITHM In this section we will detail how changes in the structure of a process can be identified when significant variations in the conformance are detected when comparing incoming traces and the process model. Algorithm 1 (C2D2) performs drift detection based on a sliding window (Def. 7) whose optimal size is automatically adjusted at the beggining and after a drift is confirmed (line Algorithm 1 Conformance Checking-based Drift Detection Inputs: an event log L and a minimum window size min_ws < |L| Outputs: a list of trace causing drift D 1: procedure CONCEPTDRIFTDETECTION(L,min_ws) 2: D←[]//confirmed drift traces 3: i←0 4: while i < |L|do 5: Γ←[]//fitness measures (Def. 5) 6: P←[]//precision measures (Def. 6) 7: DΓ←[]//drift candidates (fitness) 8: DP←[]//drift candidates (precision) 9: n←ADJUSTWINDOW(min_ws, hτi, ..., τ|L|i) 10: ωi← hτi, ..., τi+ni 11: N←discover(ωi) 12: while ((i+n)<|L|)∧(τi+n−1/∈D)do 13: Γ←Γ :: γ(ωi, N)//append current fitness 14: P←P:: ρ(ωi, N)//append current precision 15: DΓ←DΓ:: IDENTIFYDRIFTCANDIDATE(n,Γ,DΓ) 16: DP←DP:: IDENTIFYDRIFTCANDIDATE(n,P,DP) 17: if CONFIRMDRIFT(n,DΓ,DP)then 18: D←D:: τi+n 19: end if 20: i←i+ 1 21: ωi← hτi, ..., τi+ni 22: end while 23: end while 24: return D 25: end procedure 26: function IDENTIFYDRIFTCANDIDATE(n, data, D∗) 27: Υ←regress({data|data|−(n/2), ..., data|data|}) 28: m<←Υ.slope <0∧Υ.confidence <0.05 29: m>←Υ.slope >0∧Υ.confidence <0.05 30: m=←(¬m<)∧(¬m>) 31: return (|data|>n/2)∧(m<∨m>∨(m=∧(D∗ |D∗|=true))) 32: end function 33: function CONFIRMDRIFT(n,DΓ,DP) 34: dΓ← ∀d∈ {DΓ |DΓ|−n, ..., DΓ |DΓ|}:d=true 35: dP← ∀d∈ {DP |DP|−n, ..., DP |DP|}:d=true 36: return (|DΓ| ≥ n∧dΓ)∨(|DP| ≥ n∧dP) 37: end function 9). Thus, the only input of the algorithm is a minimum window size, aside from the event log. The algorithm starts by initializing a list D of traces that are confirmed drifts (line 2), and the initial window index i= 0 (line 3). From lines 4 to 23, the main loop will identify and confirm the drifts of the process. In this loop, the list Γ will store the fitness of a model N that is discovered from the traces of a window. For instance, Γi will contain the fitness of the model N with respect to the traces of the window ωi . Similarly, the list P will store the precision measurements. In addition, the lists DΓ and DP store, at index i , a boolean that indicates whether the last trace from window ωi has been marked as a drift candidate or not for fitness and precision, respectively. For instance, DΓ i is set to true when the trace τi+n has been marked as a drift candidate. In line 9, the optimal sliding window size is calculated from the remaining traces that have not been processed (more details in Section 5.2), and then the sliding window ωi and the model that describes the behavior observed in this window are obtained (lines 10 and This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 7 11). These four lists, the sliding window ωi and the model N are reinitialized whenever a drift has been confirmed. The inner loop (lines 12 to 22) performs the detection of drifts based on conformance measurements. This loop iterates from the index i , corresponding to the window ωi , until the end of the log as long as no drift has been confirmed (line 12). In each iteration i , the fitness and precision of the model N are computed with respect to the sliding window ωi (lines 13 and 14). Traces are identified as a drift candidate (lines 15 and 16) by computing in function IDENTIFYDRIFTCANDIDATE a linear regression over the values of the lists DΓ and DP (lines 26 to 32) and then by checking if the slope of the fitted function is statistically different from zero (more details in Section 5.1). If the trace τi+n is identified as a drift candidate, the function CONFIRMDRIFT checks if this drift persist over time (line 17). This function checks that the last n traces have been classified as drift candidates either for fitness (line 34) or precision (line 35). This allows the method to prevent false positives due to the existence of temporal falls in the metrics caused by outlier traces. Once the candidate is confirmed as a real drift, trace τi+n is added to the list of confirmed drifts D (line 18), the window slides one position, reading a new trace from the log (line 21), and the algorithm loops back to the initialization phase. 5.1 Drift detection The detection mechanism is listed in lines 26 to 32 of Algorithm 1 (function IDENTIFYDRIFTCANDIDATE). As a first step, a simple linear regression [36] is computed over the last n/2 measurements for both fitness and precision (line 27). To calculate this regression, the ordinary least squares method has been used, which minimizes the sum of squares of the difference between the real and the predicted values of the dependent variable (i.e., the fitness/precision value). Also, a statistical test over the regression slope has been performed. Namely a t-test with (n/2) −2 degrees of freedom. The null hypothesis ( H0 ) states that the slope of the regression is equal to zero. The minimum significance level has been set at 0.05 . When H0 is rejected (i.e. Υ.confidence <0.05 ) we asume that enough evidences exist to accept the slope value Υ.slope . Otherwise, we can not assume that the slope value is different from 0. There are three possible situations: 1) The regression slope is negative (line 28): metrics get lower values, so more traces are not replayable for fitness or, conversely, more paths of the model are not contained in traces for precision. Thus the window is marked as a drift candidate. 2) The regression slope is positive (line 29): metrics get higher values, since more traces are replayable for fitness or, conversely, more paths of the model are contained in traces for precision. Thus the window is marked as a drift candidate. 3) The regression slope is zero (line 30): no change in conformance metrics, i.e., the window does not present any drift. In this case, a drift can also be detected, but only if the previous window was marked as a drift candidate. Fitness Precision (a) Log 1 ( pl ). Precision falls every time a change happens but fitness remain unaltered. Fitness Precision (b) Log 2 ( cb ). Fitness falls but precision remains unaltered in every change. Figure 5. Evolution of fitness and precision metrics when computed over a sliding window of 100 traces on logs pl and cb. An example of this behaviour is depicted in Figure 5. This example shows the drift detection using the logs pl and cb , that will be described in Section 6.1, which contain a change every 250 traces. In the case of pl (Figure 5a), two fragments that are originally executed in a concurrent form are transformed into a sequential execution, which should imply a reduction in precision but not in fitness. In the case of cb (Figure 5b), a fragment is transformed from mandatory to skippable, which should imply a reduction in fitness but not in precision. 5.2 Adjusting the Window Size When some behaviour appears in some traces but not in the model, they can be initially considered as outliers. But when this behaviour persists for a long time, it can be flagged as a change, having the organization an opportunity to enhance its process. Something similar happens when some behaviour is no longer observed in the log. A path of the process that is not present during a short period of time can be seen as a temporary exception. But if this behaviour is absent for a long time, some optimizations can be made to improve the process performance. Hence, small windows will detect less durable changes, while larger window sizes will detect changes that persist. Adjusting the window size for processing the log is not a trivial task. A small window would led to multiple false detections, due to the window not containing enough information to describe the process executed at a given instant. On the other hand, a big window would not detect some changes, because the reference window will contain traces from before and after the change. Thus, a good balance between the two options is essential. To adjust the window size, C2D2 uses an approach based on the comparison of models from consecutive sublogs (Algorithm 2). We start with three empty models (line 2) and a window size n0 , that is initialized to the minimum window size n (line 3). Then, three new models for three consecutive sublogs are discovered with the same discovery algorithm used for the detection (lines 5-7). If these three discovered models are equal, we increment the window size and try again (lines 8-10). Else, if any of the discovered models differ from the rest, the procedure finishes and the last n0 is used as the window size. By default, we use a minimum window size of 1 % and an increment of 0.1 % of the log size. Figure 6 shows why three consecutive models are required. Let us consider the log in Figure 4d, that presents a This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 8 Algorithm 2 Automatic window size optimizer Inputs: an event log L and a minimum window size n < |L| Outputs: the optimal window size for processing L 1: function ADJUSTWINDOW(n, L) 2: N1, N2, N3← ∅ 3: n0←n 4: while N1=N2=N3do 5: N1←discover(hτ0, ..., τn0i) 6: N2←discover(hτn0, ..., τ2n0i) 7: N3←discover(hτ2n0, ..., τ3n0i) 8: if N1=N2=N3then 9: n0←increment(n0) 10: end if 11: end while 12: return n’ 13: end function τ1τ2τ3τ4τ5τ6τ7τ8τ9τ10 τ11 τ12 τ13 τ14 τ15 τ16 Change ω6ω12 ω5ω10ω15 Added Behaviour Removed Behaviour Added Behaviour Removed Behaviour N26=N1 N1=N1 N26=N1=N1 N1=N16=N2 Figure 6. Behaviour of the adaptive window in the example from Figure 4. Log correspond with the one in Figure 4c and Figure 4d for removing and adding behaviour, respectively. N1 and N2 refer respectively to the models in Figure 4a and Figure 4b. change between traces τ8 and τ9 . The change consist in some behaviour being added to the process (the execution of B before C is replaced by a concurrent execution of these two activities). In this case, using two windows, one that contains behaviour from before the change and one that contains behaviour from both before and after the change, is enough because the models will be different. Consider now the log in Figure 4c, that also contains a change between traces τ8 and τ9 . This time, the change consists in some behaviour being removed from the process (the execution of C before B disappears from the log). In this case, when using just two windows, the model discovered with traces from both preand post-drift traces reflects no changes, because the missing path is present in the pre-drift traces used for discovery. In this scenario three windows, with their respective models, are required: one to depict the behaviour of the process before the change, one to detect both preand post-drift behaviour, which will be the same as in the pre-drift case, and one to represent the behaviour after the change. 5.3 Custom Fitness and Precision Traditional fitness and precision metrics are designed to assess the global quality of a model. These metrics use different approaches to compute fitness and precision in a reliable way, giving each trace a score in a continuous scale depending on how well they conform to the model, rather than following a discrete approach where traces can only get a binary rating for Conformance. However, C2D2 use them to detect structural changes in the execution of a process. In this AB CDE FG Log ABCDEG ACBDEG ABCDEG ACBDEG ACBDEG ABCDEG ABCDEG ACBDEG ABCDEG OLP =h(A→B)(A→C)(B→D)(C→D) (D→E)(D→F)(E→G)(F→G)i DFR =h(A→B)(A→C)(B→C)(B→D) (C→B)(C→D)(D→E)(E→G)i PC = 1 −|h(D→F)(F→G)i| 8=0.75 Figure 7. PC computation example. paper, we propose two simpler fitness and precision metrics aside from the well-established metrics from the state of the art. These two approaches have much lower computational complexity and were designed to detect changes in simple and noise-free logs. In the case of fitness, we use the percentage of replayable traces (Eq. 1). This approach is not particularly useful for measuring the quality of a model, since it equally penalizes traces that do not fit the model and those that deviate slightly from it. Despite this, it can be used to estimate changes in fitness, since a change in the percentage of traces that can be replayed in the model always leads to a change in the metric value. For precision, the following approach is used: PC = 1 −|OLP \DFR| |OLP|(3) where: • A set of one-length paths (OLP) is extracted from the model. An OLP is a pair of activities that are directly connected in the process model, without any other activity in between. • A set of directly-follows relations (DFR) is extracted from the log. A DFR is a pair os activities that appear one after the other in the log, without any activity in between. •Operator \is the difference between two sets. Eq. (3) does not measure the precision per se, but the change in the precision. The moment a OLP stops appearing in the log is indicative that some path of the model has disappeared. The proposed approach returns 1 when all the supported behavior of the model appear at least once in the log, and 0 otherwise, i.e., when none of the behavior supported by the model appears in the log. The computation of this metric is illustrated with an example in Figure 7. 6 EXPERIMENTATION Concept drift algorithms are assessed based on two quality measures: Fscore (4a), which is an accuracy metric computed as the harmonic mean between precision (4b) and recall (4c); and delay (henceforth ∆ ), which is the distance between the point when the change really happened and when it is detected. Fscore =2×precision ×recall precision +recall (4a) This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information. 1939-1374 (c) 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031, IEEE Transactions on Services Computing 9 0 5 10 15 20 25 δ5 5δ5 20 TP FP FP FN Figure 8. Change results classification in TP , FP and FN . A dot represents a real change. A cross represents a detection. Shadowed in the neighborhood. Table 2 Simple change patterns from [22] applied to the original model. Code Change pattern Class cm Move fragment into/out of conditional branch I cp Duplicate fragment I pm Move fragment into/out of parallel branch I re Add/remove fragment I rp Substitute fragment I sw Swap two fragments I cb Make fragment skippable/non-skippable O lp Make fragments loopable/non-loopable O cd Synchronize two fragments R cf Make two fragments conditional/sequential R pl Make two fragments parallel/sequential R precision =TP TP +FP (4b) recall =TP TP +FN (4c) To classify the detected changes as true positives ( TP ), false positives ( FP ) or false negatives ( FN ), we use a threshold ε , that represents the error tolerance of the quality measures, and a neighborhood δε i , defined as the interval between i−ε and i+ε . Let a change happen at instant i . This change is classified as a TP only when it is detected in δε i . When no change is detected in δε i it is classified as FN . Finally, all changes detected in δε i where a previous change has been already detected are classified as a FP , as well as the ones detected outside any δε . Figure 8 shows an example with two real changes ( d5 , at instant 5 , and d20 , at instant 20 ), and three detections, at instants 4 ( c4 ), 7 ( c7 ) and 12 ( c12 ), using a ε= 5 . In this example, c4 is classified as a TP , because it lies in the neighborhood of d5 ; c7 is classified as a FP , because, despite being in the neighborhood of d5 , another change has been detected previously; c12 is classified too as a FP , in this case for being detected outside any neighborhood δ5 ; and finally, d20 is classified as a FN since no change is detected in its neighborhood. The algorithm implementation is published online and available to researchers as a REST API1. 6.1 Validation Data Our proposal has been tested with three models extracted from the literature [37], [38], [39], which describe a loan application process, a hospital emergency ward process, and a central venous catheter process, respectively. These models are usually part of benchmarks for concept drift 1. https://tec.citius.usc.es/concept-drift-api/swagger-ui.html detection, process discovery and conformance ckecking. A set of sythetic logs for each one of the process models have been generated using the methodoloy and change patterns described in [17]. This is the most extended methodology [19], [20], [40] for generating datasets when validating sudden concept drift detection algorithms in process mining. For each process, we generated a dataset composed of 68 logs: 17 with 2,500 traces, 17 with 5,000 , 17 with 7,500 and 17 with 10,000 . The original dataset from [17] contains 4 more logs (one for each of the sizes), but they have been discarded because its drifts (changing the frequency of the branches in a choice construct) are not control-flow drifts, but behavioural ones. It should be noted that, for simplicity and space limitation, the explanation of the concept drift tests will only describe the results of the loan application process. Detailed results of the other two models can be found in the supplemetary material of this paper. The Petri net corresponding to the loan application process is depicted in Figure 9. To generate the 17 modified models, 11 simple change patterns from [22] are applied to the original process. The applied patterns are collected in Table 2. These changes can imply an insertion (labeled as I ), an optionalization (labeled as O ) or a resequentialization (labeled as R ). For each simple change pattern a different model is generated. The remaining 6 models are generated by applying a combination of simple change patterns, picking one change from each of the previously named classes. Once all the models are available, the logs are generated simulating executions of those processes. The original log is then combined with the modified ones to generate logs with drifts. The final log is composed joining alternatively sublogs from both the original model and the modified ones. Each drifting log presents a change every 10 % of its final size. A log generation example is represented in Figure 10. Two logs ( L1 and L2 ) with different models are split in 5 sublogs with equal sizes ( L1 1 to L5 1 and L1 2 to L5 2 ). This sublogs are combined alternatively into a log L, with size |L1|+|L2|. 6.2 Impact of Discovery Algorithm in Fitness and Precision Metrics during Detection In order to check the impact of the discovery algorithm and the conformance metrics in C2D2 performance, different configurations have been tested: 1) Discovery algorithms: Inductive Miner ( IM ) [41] and Heuristics Miner ( HM ) [42], which are two of the most used methods for discovering models from event logs. No algorithm based on evolutionary computation has been selected because it would increase the computational complexity significantly. 2) Fitness metrics: Alignment Based Fitness ( AF ) [43], Negative Event Recall ( NR ) [34] and the percentage of completely replayable traces (RT) from Section 5.3. 3) Precision metrics: Advanced Behavioural Appropriateness ( ABA ) [35], Negative Event Precision ( NP ) [34] and precision change assessment (PC) from Section 5.3. The key when choosing a discovery algorithm and a pair of fitness and precision metrics is to obtain a combination that allows the results of the regression to stabilize around a value, so the slope is zero while there are no changes. If we focus on fitness, reaching a constant value in absence of changes This article has been accepted for publication in IEEE Transactions on Services Computing. This is the author's version which has not been fully edited and content may change prior to final publication. Citation information: DOI 10.1109/TSC.2021.3120031 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See https://www.ieee.org/publications/rights/index.html for more information.