-Real-time response is crucial in many business process scenarios, however, few tools support the online processing of Process Mining tasks. In this paper, we present Concept Drift in Event Stream Framework (CDESF), a tool focused on concept drift detection that also supports several online Process Mining tasks. CDESF highlights the process model evolution during the stream processing and alerts the detection of new drifts aided by an online clustering layer. This paper presents CDESF as a tool that is available for the community and process practitioners. Index Terms-Online process mining, clustering, concept drift detection, process model graph
Process Mining (PM) aims at extracting information from
event logs, which are recorded by information systems during
the execution of business processes. Further, PM provides
insights from recorded business processes, such as the
creation of a process model, detection of anomalous executions,
and extraction of process metrics [
cycle to take action, which leverages the necessity for online processing of event logs. This way, online PM has emerged as an area with the goal of handling event streams, that is, events are processed as their generation occurs.
chronously, i.e., one might first discover a process model, then apply a conformance checking technique to detect deviations and extract metrics, and so on. However, online PM imposes constraints that make traditional processing unfeasible.
that the flow of events is continuous, fast, and possibly infinite. This poses the first constraint, the limitation of time and memory. Algorithms are required to have forgetting mechanisms to keep memory consumption viable (as it is impossible to store an infinite stream) and low time consumption (as the processing of events should be faster than the arrival rate of events). Moreover, PM practiced in online scenarios must also consider concept drifts, a phenomenon characterized by the change of the relation between a feature vector and
This study was also partly supported by the program “Piano di sostegno
alla ricerca 2019” funded by Universita` degli Studi di Milano.
its associated class over time, and also consider incomplete
traces. Lastly, an updated version of the process model is
needed to assess the differences between reference and real
executions correctly. Therefore, methods should be aware of
the process model and detect deviations at the same time while
maintaining an updated model and being prepared to handle
concept drifts [
Several methods for online PM have been proposed in the
last few years, ranging from online process discovery [
is maintained online and updated using the most recent events. The updating step keeps the model relevance while it serves as the representation of the business process behavior.
both the process model and the traces as graphs. The decision is based on the broad support of graph operations. This way, metrics are extracted by comparing trace and process model. Further, the obtained metrics allows the detection of deviations from normal behavior.
the concept of micro-clusters. Given the micro-clusters behavior over time, a concept drift is detected.
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Event
Cases: Transformation
E
Check Point 1 2 3 Stream Processing Distance Computation
A
A B B E C D F
event streams (not to be mistaken with trace streams) ingesting one event at a time unit.
CDESF tackles several problems faced in online PM and provides in-depth insights into the business process for stakeholders. This way, moving forward the current state of tools available for users and PM enthusiasts. Recently, CDESF has been released as a Python library for the community1. A video demonstrating the framework’s use and its capabilities is available2. Moreover, a tutorial showing detailed information on how to use the framework, along with a deeper discussion of its visualizations is also available3. We also note that
tion II presents CDESF architecture and its main features.
Figure 1 exposes CDESF architecture and how each step is performed. Notice that the event stream is possibly infinite and that events from different cases are interspersed. This way, at the arrival of a new event, its case must be retrieved and complemented with the event. For each new event, CDESF steps 1 to 3 are processed, i.e., the framework does not consume data in chunks, such as window-based techniques.
When a new event arrives, the Transformation step adds the event into its corresponding case and models the case into a graph-based representation. If the new event belongs to a new case (i.e. a case that has never been seen before), the case is initialized with the event. Then, the graph representation will contain a single event. Instead, if the event is from an already existing case, the case is updated with the event. Consequently, the graph representation is also updated by adding a new node.
relations, respectively.
The second step, Distance Computation, aims to extract features that describe the case behavior. For that, the case is compared with the PMG, which captures the current business process nature. The comparison catches two perspectives: trace and time, noted as graph-distance trace (GDtrace) and graph-distance time (GDtime). Distances are measured in a normalized PMG. From a trace perspective, the normalization is the occurrence of a specific transition divided by the value of the most occurred transition. The result of this operation is referred to as weight. For the time perspective, edge normalization computes the mean time of a transition between activities. Equations 1 and 2 show the computing of GDtrace and GDtime, respectively.
GDtrace(tr) =
PiT=tr1 1 P MGweight(tr[i])
Ttr (1)
Online Process Discovery
Online Conformance
Checking
Online
Process
Enhancement Anomaly Detection
Drift Detection Fig. 1: CDESF architecture is divided into four main steps.
extracted. These metrics are fed to a density-based online clustering for anomaly and concept drift detection. Finally, a seasonal step updates the model and releases inactive cases from memory.
GDtime(tr) = log10
PiT=tr1 jP MGtime(tr[i]) tr[i]timej
PjT=tr1 P MGtime(tr[j]) (2) Given a trace tr, Ttr is the total amount of edges in tr, tr[i] corresponds to the ith edge in tr, tr[i]time is the time delta in tr[i] and tr[i]weight is the weight of tr[i]. The graph distances capture two essential aspects of traces, the controlflow and the time between activities. And given the flexibility of the framework, it is possible to add multiple dimensions considering additional perspectives, e.g., event attributes.
... common patterns and sparser regions represent anomalous patterns. Moreover, it detects cases that do not belong to any cluster or are not dense enough to form one. These points are also considered anomalous since they are isolated in the feature space. DenStream uses the concept of micro-clusters and further classifies micro-clusters in three types: outlier micro-cluster (anomalies), potential micro-cluster (potentially common behavior), and core micro-cluster (common behavior). The detection of concept drift relies on the detection of new core micro-clusters, i.e., if a new behavior has appeared in the stream and is dense enough to form a core micro-cluster, then a drift has been detected.
control and model update. It is controlled by a hyperparameter (in time unit) that sets a time horizon to how frequent
the last time horizon are used to build a temporary graph.
The temporary graph represents the newest behavior of the
process since it is built with the newest events. Then, the
temporary graph is merged into the PMG to update the
process representation. Before merging, a decay factor is
applied to the PMG to balance new and historical data. If a
directly-follows relation stops appearing, its weight decreases
gradually. This step supports process model enhancement by
using new information to maintain the PMG faithful to real
data. Regarding memory control, older cases are released from
memory according to the Nyquist sampling theorem [
researches [
One of the main interests in PM analysis is to evaluate the process model, i.e., process discovery. Traditionally, given a complete event log, the relations between events are inferred to build a process model. In a stream of events, algorithms have to periodically update the process model since recent events may represent new behavior. This way, a constant model update component is required, so the process always represents the newest behavior seen in the stream. In CDESF, the CP step controls model updates using the most recent events that have arrived in the last time window. Figure 2 shows the PMG in different stages of the stream. In the first
amount of events that have arrived. Note that CDESF does not start stream processing with a pre-built model, instead, it learns the model during the stream processing. This way, it is expected that during the first CPs, the process model is simple since the presented behavior of the stream is minimal. Already on CP 3 (Figure 2b), we can observe how the PMG has embedded more information. And on CP 28 (Figure 2c), an even more complete PMG has been created. There is a clear relationship between the time horizon hyperparameter, which controls CP frequency, and the PMG update. Higher time horizons imply in a longer time between updates, this is advised in processes where more constant behavior is expected. Contrarily, lower time horizons have more frequent
streams or processes where change is expected. Other than the visual output, CDESF also saves the PMGs during every
(a) CP 1 (b) CP 3 (c) CP 28 Fig. 2: Evolution of the PMG through several check points (CP). In the first CP, the PMG is still very basic since very few events have arrived in the stream. With the consumption of more events over time, the PMG is updated to represent new behavior better, as seen in CPs 3 and 28.
During the stream processing, CDESF triggers drift alerts when a drift is detected. This approach facilitates decision making for organizations using the framework since the drift is detected and alerted on the fly. Moreover, CDESF also creates a visual output after stream processing showing the number of detected drifts and their positions. This visualization is shown in Figure 3. Vertical dashed lines represent the point in time where drifts were detected. At the same time, the figure demonstrates the cumulative number of drifts detected in the stream. In this scenario, further behavioral analysis is possible.
initial stages, and with time, the process execution got a stabler form.
CDESF is also capable of representing the evolution of clusters in the stream. Figure 4 shows the clustering feature space after 2950 processed events. Core, potential, and outlier micro-clusters are represented in black, blue and red, respectively. The micro-clusters contain two rings, the dashed line is the maximum range a micro-cluster can achieve (controlled by a hyperparameter), while the continuous line is the actual radius of the micro-cluster. It follows that the points (cases) are 7 6 s t if5 r d f r4 o e b 3 m u N 2 1 0
Drifts and cumulative number of drifts in the stream Drift points Number of drifts 1000 2000 3000 4000 5000
Event stream Fig. 3: Relation of the event stream processing, number of detected drifts and their positions. Vertical lines represent the drift positions and the curve shows the cumulative number of drifts. represented in two ways. The black dot is a normal case falling under a core micro-cluster area, while the yellow marker represents anomalous behavior, i.e., cases that do not conform to the PMG.
Fig. 4: Feature space after 2950 events processed. Core microclusters (black regions) represent common process behavior.
by the metrics which are saved after the processing. CDESF provides the evolution of clusters and case metrics, which opens opportunities for further analysis. Both visualizations and metrics information can be crossed in many ways to offer in-depth insights into the business process.
In this paper, we present CDESF, a tool for detection of concept drifts and monitoring of business processes in online scenarios. CDESF handles conflicting goals (memory consumption and accuracy) in stream processing, maintains a process model and supports drift detection using an online clustering layer. CDESF is an available open-source tool implemented as a library in Python.