11institutetext: Eindhoven University of Technology, The Netherlands
11email<EMAIL_ADDRESS>
# Extracting and Pre-Processing Event Logs

Dirk Fahland

###### Abstract

Event data is the basis for all process mining analysis. Most process mining
techniques assume their input to be an _event log_. However, event data is
rarely recorded in an event log format, but has to be _extracted_ from raw
data. Event log extraction itself is an act of _modeling_ as the analyst has
to consciously choose which features of the raw data are used for describing
which behavior of which entities. Being aware of these choices and subtle but
important differences in concepts such as trace, case, activity, event, table,
and log is crucial for mastering advanced process mining analyses.

This text provides fundamental concepts and formalizations and discusses
design decisions in event log extraction from a raw event table and for event
log pre-processing. It is intended as study material for an advanced lecture
in a process mining course.

##  1 Event Data

Event data is the basis for all process mining analysis. Most process mining
techniques assume that their input is in the form of a _simple event log_ such
as the following:

$\begin{array}[]{rl}L=[&\langle A,B,C,D\rangle^{10},\\\ &\langle
A,C,B,D\rangle^{5},\\\ &\langle A,B,A,D\rangle^{3},\\\ &\langle
A,E,D\rangle^{1}].\end{array}$

This simple event log is defined over an _alphabet_ $\Sigma=\\{A,B,C,D,E\\}$
which is a _set_ of activity names that have been observed. Each $a\in\Sigma$
is the name of an _activity_ , i.e., a specific action that can be executed or
observed. For now, we consider each activity name as “atomic” — later in this
chapter we will see that activities themselves can have some “structure”
themselves.

A _trace_ $\sigma\in\Sigma^{*}$ is a finite sequence of activities111Recall
that the star ∗ after $\Sigma$ is the _Kleene star_ which we use when
constructing the set of all possible finite sequences over the elements of set
$\Sigma$.. It describes that this sequence of activities had been observed at
some point in the past. Each occurrence of an activity in a trace $\sigma$ is
called an _event_. For example, the trace $\langle A,B,A,D\rangle$ describes
we first observed $A$, then $B$ followed by another occurrence of $A$, and
finally we observed $D$.

###### Exercise 1

Which other traces can be built from $\Sigma=\\{A,B,C,D,E\\}$ that are not in
$L$?

A _simple event log_ $L\in\mathds{B}(\Sigma^{*})$ is a multiset222A multi-set
is also called a _bag_ , which explains the symbol $\mathds{B}$ we use for
constructing the multiset over $\Sigma^{*}$. Recall that a multiset can
contain the same element $\sigma\in\Sigma^{*}$ multiple times. of traces
describing that various traces that have been observed and _how often_ each
trace has been observed, e.g., $\langle A,B,A,D\rangle^{3}$ was observed $3$
times.

###### Exercise 2

Why do we only study finite sequences of activities when analyzing event logs
(recorded historic executions) of processes?

However, event data is _not_ recorded in this form in practice. First of all,
an event records multiple attributes, not just the name of an activity.
Secondly, event data is recorded as it occurs, and thus never grouped into
traces or event logs.

A central part of process mining comprises actually obtaining event data from
various data sources, and transforming it into an event log. We will see that
both steps are non-trivial and allow for many choices. After the event log has
been created, it rarely has sufficient quality to be used for any process
mining analysis. Consequently, we have to pre-process the event log.

In the following, we first introduce a generic event data model and the notion
of an event table in Sect. 2. Then, we explain in Sect. 3 how to extract
structured event logs from such an event table and kinds of choices that can
be made. We then introduce in Sect. 4 the notion of event classifiers required
to turn structured event logs into the simple event logs explained above. We
introduce the three central pre-processing operations on structured event logs
in Sect. 5.

##  2 Events and Event Table

The most common direct or “raw” logging format for events is an _event table_
or _event stream_ as shown in Table 1. Each row in this table is one _event
record_. Each column is an _attribute_ where the column header defines the
_attribute name_. The contents of a table cell for event $e$ in column $a$ is
the _attribute value_ event $e$ has for attribute $a$.

The event table can be considered as “raw” data as besides providing
attributes per event, the data has no further structure. Specifically notice
that no traces are recognizable in this event table.

Table 1: Event Table

The following definitions formally define events described by attributes and
an event table.

  * •

Let $\mathit{AN}$ be a set of _attribute names_.

  * •

Let $\mathit{Val}$ a set of _values_.

  * •

Let $\mathcal{E}$ be the universe of events.

######  Definition 1 (Event)

An _event_ $e\in\mathcal{E}$ describes that a specific discrete observation
has been made (by a sensor, a system, a human observer, etc.). The observation
itself is described by attribute-value pairs through the partial333A partial
function does not have a value for each argument function
$\pi:\mathcal{E}\times\mathit{AN}\nrightarrow\mathit{Val}$.

For each event $e\in\mathcal{E}$ and each attribute name $a\in\mathit{AN}$,
$\pi(e,a)=v$ defines the value $v$ of attribute $a$. We write $\pi(e,a)=\perp$
if attribute $a$ is undefined for $e$ (has no value). We also write
$\pi_{a}(e)=v$ or $e.a=v$ for $\pi(e,a)=v$.

For each event $e\in\mathcal{E}$, we require that

  * •

the attribute $\mathit{time}$ is defined, i.e.,
$\pi_{\mathit{time}}(e)\neq\perp$.

  * •

$e$ carries a value $\pi_{a}(e)\neq\perp$ for some other attribute
$a\in\mathit{AN},a\neq\mathit{time}$.

In other process mining literature, you also find the notation $\\#_{a}(e)=v$
instead of $\pi_{a}(e)=v$ or $e.a=v$ to describe that event $e$ has attribute
$a$ with value $v$.

By the two requirements on each event $e\in\mathcal{E}$ in Def. 1, we ensure
that each event has a timestamp $\pi_{\mathit{time}}(e)$ and records at least
_one_ meaningful observation $\pi_{a}(e)$ (but it can record more). To be able
to analyze processes in a meaningful way, we need the events we analyze to
share some common ground: They should refer to the same kinds of observations,
i.e., share some attributes. Therefore, an event table is a sequence of
events, that all have the same attribute $a$ defined. We can think of
attribute $a$ as the activity name or measurement that was recorded.

######  Definition 2 (Event Table)

An _event table_ is a finite sequence $\mathit{ET}=\langle
e_{1},\ldots,e_{n}\rangle$ of events $e_{1},\ldots,e_{n}\in\mathcal{E}$ of
events with $\pi_{a}(e_{i})\neq\perp$ for some attribute $a\in\mathit{ET}$ and
all $1\leq i\leq n$.

We write $e_{i}\in\mathit{ET},1\leq i\leq n$ when referring to an event in
$\mathit{ET}$.

Definitions 1 and 2 define the absolute bare minimum for analyzing events: all
events $e$ have a timestamp $\pi_{\mathit{time}}(e)$ and record the some
observation (or value) $\pi_{a}(e_{i})$. In this bare form, an event table
could even specify a time-series. However, most events carry many additional
attributes which we exploit in process mining.

Table 1 shows an event table according to Def. 1 and Def. 2.

###### Exercise 3

Choose any event from Table 1 and give its formal definition according to Def.
1.

Strictly speaking, Definition 2 does not define an event _table_ in the sense
of the data model of relational databases, but rather just a finite stream of
events of attribute-value pairs. However, the table format representation is
convenient and data in this form is often stored and exchanged using the
_Comma Separated Value (CSV)_ format.

###### Exercise 4

What are the differences between Definition 2 and the data model of relational
databases?

We can reorder the events/rows in an event table to better understand its
contents. Table 2 reorders the events of Table 1 by grouping them by attribute
_order_ and the sorting all events per order on attribute _time_. In Table 2,
we added a column assigning each event a unique identifier to be able to refer
to them individually, e.g., $e_{1}$ is the first event in this table.

In this sorted event table, we can start recognizing the traces we discussed
in Sect. 1. However, the traces are no objects yet in their own right. We
discuss how to obtain traces and structured event logs next.

##  3 Extracting Structured Event Logs from an Event Table

An event table only records for each event its timestamp and some observation
such as an activity name. The essential difference between an event table and
an event _log_ is the presence of an additional attribute called the _case
identifer_. It allows to group events into cases and traces and compare
multiple sequences of events to each other.

###  3.1 Entities and Case

We use the term _Case_ to refer to an _entity_ or _object_ that we are
“tracking” over time in terms of the events in which this entity is involved.

For example, for the first event in Table 2 we can recognize that three _types
of entities_ were involved.

  * •

_order_ (for which we find the order id “23” as attribute value)

  * •

_user_ (for which we find the user name “System” as attribute value)

  * •

_customer_ (for which we find an identifer “A7001” as attribute value)

Other events also refer to a fourth entity type _delivery_.

In contrast, the attribute _item_ does not refer to an entity type because its
values describe sets or classes of similar objects but do not identify a
unique entity or object. Recognizing which attributes of an event refer to
entity types requires domain knowledge or additional context information.

To obtain a structured event log from an event table, we have to recognize
from all attribute names the entity types, and then select one these
attributes $c$ referring to an entity type as the _case identifier_ attribute.
The attribute values for $c$ we find among all events are the cases we find in
the data.

######  Definition 3 (Case identifier, cases)

Let $\mathit{ET}=\langle e_{1},\ldots,e_{n}\rangle$ be an event table.

The set of attribute names in $\mathit{ET}$ is

$\mathit{AN}(ET)=\\{a\in\mathit{AN}\mid\exists
e_{i}\in\mathit{ET},\pi_{a}(e_{i})\neq\perp\\}.$

If we select an attribute $\mathit{id}\in\mathit{AN}(ET)$ as _case identifier_
, then

$\mathit{Cases}(\mathit{ET},\mathit{id})=\\{\pi_{\mathit{id}}(e_{i})\mid
e_{i}\in\mathit{ET}\\}$

is the set of cases for this case identifier.

By choosing one entity type as case identifier, we decide to reformat the
event data in a way that “tracks” what has happened to all entities of this
type.

Note that Definition 3 allows to pick any attribute as case identifier, not
just those that refer to entity types. For example, we could even pick
attribute name $\mathit{action}\in\mathit{AN}(ET)$. The next steps in building
a structured event log work with any chosen case identifier. However, the
subsequent analysis entirely depends on how sensible this choice of a case
identifier was for the particular analysis question. In other words, we have
to understand which analysis question we try to answer, and then identify the
corresponding attribute name (e.g., of an entity type of interest) that we
want to use as case identifier.

This also means that at this point we implicitly require that each event $e$
has _three_ mandatory attributes that are different from each other (i.e., we
do not choose $a=c$ or $a=c=\mathit{time})$:

  1. 1.

the _timestamp_ $\pi_{\mathit{time}}(e)$ (see Def. 1)

  2. 2.

a recorded action or _activity_ $\pi_{\mathit{a}}(e)$ (see Def. 2)

  3. 3.

a _case identifier_ $\pi_{\mathit{c}}(e)$ (see Def. 3)

However, except for $\pi_{\mathit{time}}(e)$, activity and case identifier are
_not_ pre-determined by the event table. They are choices we make.

###### Exercise 5

Can two events happen at the same time? Do they have to be in different cases?
Do they have to have different activities?

Table 2: Event Table

For the example of Table 2, we can see four candidates for case identifiers
based on the entity-types we found in the event table: $\mathit{order}$,
$\mathit{delivery}$, $\mathit{user}$, and $\mathit{customer}$.

###### Exercise 6

What are the cases for case identifier $\mathit{delivery}$ in Table 2?

If we have selected an attribute $id$ as case identifier, then we say an event
$e$ is _correlated_ to a case $c$ if its $id$-attribute refers to $c$, i.e.,
$\pi_{id}(e)=c$.

######  Definition 4 (Correlation to a case)

Let $\mathit{ET}$ be an event table. Let
$c\in\mathit{Cases}(\mathit{ET},\mathit{id})$ be a case for a case identifier
$\mathit{id}\in\mathit{AN}(ET)$.

Event $e\in\mathit{ET}$ is _correlated_ to $c$ iff $\pi_{id}(e)=c$. The set of
all events correlated to $c$ is

$\mathit{corr}(\mathit{ET},id,c)=\\{e\in\mathit{ET}\mid\pi_{id}(e)=c\\}.$

For example, events $e_{1}$ and $e_{2}$ are correlated to $order=23$ in Table
2. Note that if an event $e$ does not have attribute $id$ defined, i.e.,
$\pi_{id}(e)=\perp$, then it is not correlated to any case of this case
identifier.

###### Exercise 7

Which events are correlated to $order=35$?

###### Exercise 8

Which events are correlated to $delivery=623$?

###### Exercise 9

What happens when we choose $\mathit{time}$ to be an activity name or a case
identifier?

If all events correlated to a case $c$ carry the _same_ value $v$ for an
attribute $x$, then we call $x$ a _case attribute_ of $c$.

######  Definition 5 (Case attribute)

Let $\mathit{ET}$ be an event table. Let
$c\in\mathit{Cases}(\mathit{ET},\mathit{id})$ be a case for a case identifier
$\mathit{id}\in\mathit{AN}(ET)$.

Attribute $x\in\mathit{AN}(ET)$ is a _case attribute_ of $c$ iff for all
$e,e^{\prime}\in\mathit{corr}(\mathit{ET},id,c)$ holds
$\pi_{x}(e)=\pi_{x}(e^{\prime})=v\neq\perp$. We then lift the function
$\pi(.)$ from events to cases and write $\pi_{x}(c)=v$.

Attribute $x$ is a _global_ case attribute iff it is a case attribute for
every case $c\in\mathit{Cases}(\mathit{ET},\mathit{id})$.

The case identifier is _always_ a global case attribute. A global case
attribute has to be defined for each case, but each case can have its own
value.

###### Exercise 10

What are the case attributes of Table 2 for case identifier $order$?

###  3.2 Trace

A _trace_ is the sequence of events correlated to a case and ordered by time.
For example, the trace of $order=23$ in Table 2 is $\langle
e_{1},e_{2}\rangle$.

######  Definition 6 (Trace of a case)

Let $\mathit{ET}=\langle e_{1},\ldots,e_{n}\rangle$ be an event table. Let
$\mathit{id}\in\mathit{AN}(ET)$ be the selected case identifier.

A sequence $\langle e_{1},\ldots,e_{k}\rangle$ of events is a _trace_ of case
$c\in\mathit{Cases}(\mathit{ET},\mathit{id})$ iff

  1. 1.

$\\{e_{1},\ldots,e_{k}\\}=\mathit{corr}(\mathit{ET},id,c)$, i.e., it consists
of all events of $\mathit{ET}$ correlated to $c$, and

  2. 2.

for each $i=1,\ldots,k-1$ holds
$\pi_{\mathit{time}}(e_{i})\leq\pi_{\mathit{time}}(e_{i+1})$, i.e., events are
ordered by time.

Note that there may be more than one way to sequentialize the events
$\\{e_{1},\ldots,e_{k}\\}=\mathit{corr}(\mathit{ET},id,c)$ correlated to a
case $c$. This happens where two or more events $e_{i},e_{i+1}$ have the same
time-stamp $\pi_{\mathit{time}}(e_{i})=\pi_{\mathit{time}}(e_{i+1})$.

###### Exercise 11

What is the trace of $order=35$?

###### Exercise 12

What is the trace of $delivery=623$?

###  3.3 Structured Event Log

A structured event log is a set of cases where each case is associated with
exactly one trace for this case as a case attribute.

######  Definition 7 (Structured Event Log)

Let $\mathit{ET}=\langle e_{1},\ldots,e_{n}\rangle$ be an event table. Let
$\mathit{id}\in\mathit{AN}(ET)$ be the selected case identifier.

The _structured_ event log $L$ is the set
$L=\mathit{Cases}(\mathit{ET},\mathit{id})$ of cases for case identifier
$\mathit{id}$ so that additionally each case $c\in L$ gets assigned a trace
$\langle e_{1},\ldots,e_{k}\rangle$ of $c$ as trace attribute
$\pi_{\mathit{trace}}(c)=\langle e_{1},\ldots,e_{k}\rangle$.

For example, the structured event log of Table 2 has the cases
$L=\\{23,35,41,56,72\\}$ for $order$ and the following traces:

  * •

$\pi_{trace}(23)=\langle e_{1},e_{2}\rangle$ where

    * –

$e_{1}$ has

      * *

$\pi_{order}(e_{1})=23$

      * *

$\pi_{time}(e_{1})=\text{19/12/2018 15:46}$

      * *

$\pi_{action}(e_{1})=\text{receive payment}$

      * *

$\ldots$

    * –

$e_{2}$ has

      * *

$\pi_{order}(e_{2})=23$

      * *

$\pi_{time}(e_{2})=\text{19/12/2018 16:30}$

      * *

$\pi_{action}(e_{2})=\text{archive}$

      * *

$\ldots$

  * •

$\pi_{trace}(35)=\langle e_{3},e_{4},e_{5},\ldots,e_{10}\rangle$

  * •

$\pi_{trace}(41)=\langle e_{11},e_{12},e_{13},\ldots,e_{18}\rangle$

  * •

$\pi_{trace}(56)=\langle e_{19},\ldots,e_{24}\rangle$

  * •

$\pi_{trace}(72)=\langle e_{25},\ldots,e_{32}\rangle$

A structured event log has a simple hierarchical structure. At the top-level
are the cases
$L=\\{c_{1},\ldots,c_{k}\\}=\mathit{Cases}(\mathit{ET},\mathit{id})$. Each
case has case attributes as “children”, one of them is the trace
$\pi_{\mathit{trace}}(c)$. Each event $e$ in a trace has event attributes as
children, including $\pi_{time}(e)$ (time-stamp), $\pi_{a}(e)$ (the observed
activity), and $\pi_{c}(e)$ (the case identifier).

  1. 1.

A structured event log $L$ consists of a set of cases
$L=\\{c_{1},\ldots,c_{n}\\}\subseteq\mathit{Val}$, i.e., values for some case
identifier.

  2. 2.

Each case $c\in L$ defines a trace $\pi_{\mathit{trace}}(c)=\langle
e_{1},\ldots,e_{k}\rangle\in\mathcal{E}^{*}$ as a sequence of events ordered
by time, i.e., $\pi_{\mathit{time}}(e_{i})\leq\pi_{\mathit{time}}(e_{i+1})$
for each $i=1,\ldots,k-1$.

  3. 3.

The events in $\pi_{\mathit{trace}}(c)$ are all correlated to the case, i.e.,
$\pi_{\mathit{id}}(e_{i})=c$. However, most XES event logs do not store the
case identifier as an event attribute again.

  4. 4.

There is at least one attribute $a$ (e.g., the activity name) defined by each
event $\pi_{a}(e)$ in each trace $e\in\pi_{\mathit{trace}}(c),c\in L$.

  5. 5.

Cases do not share events, i.e., there is no event $e\in\mathcal{E}$
with
$e\in\pi_{\mathit{trace}}(c),\pi_{\mathit{trace}}(c^{\prime}),c,c^{\prime}\in
L,c\neq c^{\prime}$.

This hierarchical structure is formalized in the XES-standard [2, 7, 6]. See
also other formalizations of event logs [1]

###### Exercise 13

Provide the cases and traces of the structured event log of Table 2 for case
identifier _delivery_.

###### Exercise 14

Which other meaningful structured event logs can you extract from Table 2?

##  4 Event Classifiers and Simple Event Logs

The nested hierarchy of a structured event log contains all information about
all events. However, analysis techniques operating on events, prefer a flat
data structure where

  * •

a structured event $e\in\mathcal{E}$ with its various attributes is
represented by a single attribute value $\pi_{a}(e)$, e.g., the activity name,

  * •

a structured case $c$ with its various case attributes is not represented its
trace $\pi_{trace}(c)=\langle e_{1},\ldots,e_{k}\rangle$ but rather in its
simplified form $\langle\pi_{a}(e_{1}),\ldots,\pi_{a}(e_{k})\rangle$.

For example, we can transform $\langle e_{1},e_{2}\rangle$ of Table 2 into
$\langle\text{receive payment},\text{archive}\rangle$. This representation
allows easily searching for patterns in the sequences of activity names.

###  4.1 Event Classifiers and Event Classes

However, as for Definition 3 of the case identifier, events do not have a
canonical or standard attribute $a$ by which it _must_ be represented in this
simplified way. Rather, we again can pick.

Literature introduces for this purpose the definition of an _event
classifier_.

######  Definition 8 (Event Classifier)

An event classifier is a function with signature

$\mathit{class}:\mathcal{E}\to\mathit{Value}$

that maps each event to a value. The value $\mathit{class}(e)$ is called the
_event class_. Any two events $e,e^{\prime}$ with
$\mathit{class}(e)=\mathit{class}(e^{\prime})$ belong to the same event class,
which means they describe the same kind of observation.

Usually, the event classifier is defined over event attributes which can be a
single attribute or a combination of attributes. For example,

  * •

The standard event classifier is the _activity name classifier_
$\mathit{class}_{act}(e)=\pi_{a}(e)$ where $\mathit{a}\in\mathit{AN}$ is the
attribute we identify as the activity name.

For Table 2, the _activity name classifier_ is
$\mathit{class}_{act}(e)=\pi_{action}(e)$. For example, events $e_{4},e_{8}$
have the same activity name class
$\mathit{class}_{act}(e_{4})=\mathit{class}_{act}(e_{8})=\text{pack order}$.

  * •

The _activity+lifecycle_ classifier combines the activity name $a$ with the
event life-cycle attribute $lc$ (if it exists in the event log), i.e.,
$\mathit{class}_{act+lifecycle}(e)=(\pi_{a}(e),\pi_{lc}(e))$.

For Table 2, the _activity+lifecycle_ classifier is
$\mathit{class}_{act+lifecycle}(e)=(\pi_{action}(e),\pi_{\text{life-
cycle}}(e))$.

For example, events $e_{4}$ belong to different event classes for this
classifier: $\mathit{class}_{act+lifecycle}(e_{4})=(\text{pack
order},\text{start})$ and
$\mathit{class}_{act+lifecycle}(e_{8})=(\text{pack order},\text{complete})$.

Event classes over multiple attributes are also represented with a ‘+’, e.g.,
$\mathit{class}_{act+lifecycle}(e_{4})=\text{pack order+start}$.

  * •

The _resource_ classifier $\mathit{class}_{res}(e)=\pi_{r}(e)$ where
$\mathit{r}\in\mathit{AN}$ is the attribute deferring to the user, machines,
or resource that participated in the event.

For Table 2, the _resource_ classifier is
$\mathit{class}_{res}(e)=\pi_{user}(e)$. For example, events $e_{4}$ and
$e_{8}$ belong to the same event resource event class:
$\mathit{class}_{res}(e_{4})=\mathit{class}_{res}(e_{8})=\text{Alice}$.

We can in principle choose any combination of attributes for the event
classifier. This essentially corresponds to _feature selection_ in data
mining: we choose the event attributes we think are most relevant for the
analysis task at hand. If the event has no value defined for the selected
event classifier, e.g., $\mathit{class}_{item}(e)=\pi_{item}(e)$ and
$\mathit{class}_{item}(e_{1})=\perp$, then the event will be omitted from the
analysis.

It is also possible to derive new event attributes based on other events in
the trace or even the entire event log, and to use these subsequently as event
classifiers. This would correspond to _feature engineering_.

###### Exercise 15

Identify another meaningful event classifier from Table 2.

######  Definition 9 (Event Classes of an Event Log)

Given a structured event log $L$ (according to Def. 7) and an event classifier
$\mathit{class}$, the _set of event classes_ in $L$ is the set
$\Sigma_{\mathit{class}}(L)=\\{\mathit{class}(e)\mid c\in
L,e\in\pi_{trace}(c),\mathit{class}(e)\neq\perp\\}$.

###### Exercise 16

What are the event classes of the event log in Table 2 for the classifier
$\mathit{class}(e)=\pi_{\text{customer}}(e)?$

###  4.2 Simple Event Log

If we have fixed an event classifier $\mathit{class}$, we can represent each
trace in a log $L$ by the sequence of event classes, e.g., the sequence of
activity names. However, we omit all $\perp$ values.

######  Definition 10 (Simple Trace)

Let $L$ be a structured event log, let $\langle
e_{1},\ldots,e_{k}\rangle=\pi_{trace}(c),c\in L$ be a trace. Let
$\mathit{class}$ be an event classifier.

The _simple trace_ of $c$ is the sequence

$\mathit{simple}_{\mathit{class}}(c)=\langle\mathit{class}(e_{1}),\ldots,\mathit{class}(e_{k})\rangle|_{\Sigma_{\mathit{class}}(L)}$

where we replace each event $e_{i}$ by $\mathit{class}(e_{i})$ and then
project444We write $\sigma|_{\Sigma^{\prime}}$ for the projection of a trace
$\sigma\subseteq\Sigma^{*}$ onto a subset $\Sigma^{\prime}\subseteq\Sigma$ of
some alphabet. the resulting sequence onto all valid event classes
$\Sigma_{\mathit{class}}(L)$, i.e., all values that are not $\perp$.

The simple trace for case $23$ and the activity event classifier
$\mathit{class}_{act}(e)=\pi_{action}(e)$ is

$\langle\text{receive payment},\text{archive}\rangle.$

The simple trace for case $23$ and the activity event classifier
$\mathit{class}(e)=\pi_{customer}(e)$ is

$\langle\text{A7001}\rangle.$

We obtain the simple event log of $L$ by collecting all simple traces of all
cases $L$ in a multiset. Recall from Sect. 1 that $\sigma\in\Sigma^{*}$ is a
finite sequence of activity names and $\mathds{B}(\Sigma^{*})$ is a multi-set
(bag) of finite sequences.

######  Definition 11 (Simple Event Log)

Let $L$ be a structured event log. Let $\mathit{class}$ be an event
classifier. Let $\Sigma=\Sigma_{\mathit{class}}(L)$

The simple event log is the multiset
$\mathit{simple}_{\mathit{class}}(L)=L^{\prime}\in\mathds{B}(\Sigma^{*})$
where $L^{\prime}(\sigma)=|\\{c\in
L\mid\mathit{simple}_{\mathit{class}}(c)=\sigma\\}|$, i.e., there are as many
copies of $\sigma$ as there are cases which have the same simple trace
$\mathit{simple}_{\mathit{class}}(c)=\sigma$.

The simple event log of Table 2 for the _action_ classifier is (we abbreviate
each action name for succinctness):

$\begin{array}[]{rl}L^{\prime}=[&\langle\text{RP},\text{AR}\rangle^{1},\\\
&\langle\text{RO},\text{PO},\text{AI},\text{AI},\text{SP},\text{PO},\text{RP},\text{AR}\rangle^{1},\\\
&\langle\text{RO},\text{PO},\text{AI},\text{SP},\text{AI},\text{SP},\text{PO},\text{AR}\rangle^{1},\\\
&\langle\text{RO},\text{PO},\text{RP},\text{AI},\text{PO},\text{AR}\rangle^{1},\\\
&\langle\text{RO},\text{PO},\text{AI},\text{PO},\text{RP},\text{PO},\text{AI},\text{SP}\rangle^{1}].\end{array}$

The simple traces in a simple event log are also called _trace variants_ of
the event log as they show the principle ways the object that is tracked by
the case identifier “moves” through the data.

###### Exercise 17

What is the simple event log for the _activity+life-cycle_ classifier?

###### Exercise 18

What is the simple event log for the _item_ classifier?

Note that each simple trace is a finite sequence $\sigma\in\Sigma^{*}$ over
some alphabet of event classes $\Sigma=\Sigma_{\mathit{class}}(L)$ and that
the simple event log is a multiset of simple traces. We now have a complete
procedure for obtaining a simple event log, as outlined in Sect. 1 from event
data as it is recorded in practice, i.e., an event table.

  1. 1.

Find meaningful entity identifiers in the attributes of the event table that
correspond to your analysis question.

  2. 2.

Select one entity identifier as case identifier $\mathit{id}$.

  3. 3.

Construct the structured event log $L$ for this case identifier by correlating
events and ordering them over time.

  4. 4.

Find meaningful event attributes to summarize or classify the observation that
is recorded in the event.

  5. 5.

Select or define one event classifier $\mathit{class}$.

  6. 6.

Derive the simple event log from $L$ for this event classifier
$\mathit{class}$.

Given an event table $\mathit{ET}$, any simple event log is fully defined by
two decision: the case identifier $\mathit{id}$ and the event classifier
$\mathit{class}$. However, these two choices are powerful and allow you to
derive many different views.

###### Exercise 19

What is the simple event log for case identifier _customer_ and event
classifier _order_?

Almost all process mining software contains a view to visualize the event log
in the form of a simple event logs; for example the “Explore Event Log”
visualizer of ProM555http://www.promtools.org/ shown in Fig. 1 visualizes
event logs as simple event logs and allows identifying patterns through color-
coding the event classes.

Figure 1: The Explore Event Log visualizer of ProM

##  5 Pre-Processing Event Logs

Analyzing event data, just like any data analysis, requires pre-processing to
remove data points that are not relevant for the specific analysis question at
hand.

There are three basic pre-processing operations on event logs that allow us to
reduce or “filter” the data in three fundamentally different ways. Most other
pre-processing operations are a combination of these three operations. They
are defined on the data model of the structured event log (Def. 7).

  1. 1.

_Selection_ of traces reduces the set of cases in $L$ to those that satisfy a
specific property. All other cases are removed. The pre-processed log
$L^{\prime}$ contains just a subset of the cases in $L$, i.e.,
$L^{\prime}\subseteq L$ and each cases keeps all its properties, especially
all events in its trace.

Figure 2 (top) illustrates the selection of $L$ to all cases whose traces end
with an event with activity name $C$. The resulting log $L^{\prime}$ does not
contain the cases whose traces end with $B$ or $A$.

  2. 2.

_Projection_ removes from each trace in $L$ all events that do _not_ satisfy a
particular property. The resulting event log $L^{\prime}$ keeps all its cases,
but their traces may contain fewer events or even be empty.

Figure 2 (left) illustrates the projection of $L$ to all events with activity
attribute $A$ or $C$. The resulting event log does not contain any event with
activity attribute $B$ anymore.

  3. 3.

_Aggregation_ groups in each trace multiple subsequent events
$e_{1},\ldots,e_{k}$ with the same property into a new event $e^{*}$ whose
properties are derived from $e_{1},\ldots,e_{k}$; $e_{1},\ldots,e_{k}$ are
then replaced by $e^{*}$. The pre-processed log $L^{\prime}$ keeps all its
cases, but the traces may have fewer events and may contain a new aggregated
event with new properties that were not explicitly visible in $L$.

Figure 2 (bottom right) illustrates the aggregation of subsequent events with
the same activity name. For example, the subsequence $\langle B,B\rangle$ in
the second case was replaced by a single $B$.

Figure 2: Pre-Processing Operations on Event Logs

######  Definition 12 (Selection)

Let $L$ be a structured event log. Let $\varphi(c)$ be a predicate over the
case attributes and event attributes of $L$. The _selection_ of $L$ wrt.
$\varphi$ is the subset

$\mathit{Select}_{\varphi}(L)=\\{c\in L\mid\varphi(c)=true\\}.$

Here are several example selection predicates for the event log in Table 2:

  * •

$\varphi_{1}(c)\equiv\pi_{type}(c)=\text{online}$ (only cases of type
“online”)

  * •

$\varphi_{2}(c)\equiv\pi_{trace}(c)=\langle
e_{1},\ldots,e_{n}\rangle\mathrel{\wedge}\pi_{action}(e_{1})=\text{receive
order}$ (only cases starting with “receive order”)

  * •

$\varphi_{3}(c)\equiv\pi_{trace}(c)=\langle
e_{1},\ldots,e_{n}\rangle\mathrel{\wedge}\pi_{time}(e_{n})-\pi_{time}(e_{1})<24h$
(only cases completing within 24 hours)

  * •

$\varphi_{4}(c)\equiv|\\{c^{\prime}\in
L\mid\mathit{simple}_{\mathit{class}}(c)=\mathit{simple}_{\mathit{class}}(c^{\prime})\\}|\geq
10$ for some event classifier $\mathit{class}$ (only cases whose trace
variant, i.e., simple trace, occurs at least 10 times in the event log)

Note that $\varphi_{4}(c)$ is not purely local to the case $c$ but rather
“reaches out” into the entire event log $L$.

###### Exercise 20

Which cases are selected by $\varphi_{1}(c)$-$\varphi_{4}(c)$?

######  Definition 13 (Projection)

Let $L$ be a structured event log. Let $\psi(e)$ be a predicate over the event
attributes of $L$.

Let $\sigma=\langle e_{1},\ldots,e_{n}\rangle=\pi_{trace}(c),c\in L$ be a
trace. The _projection_ of $\sigma$ onto $\psi$ is the projection of $\sigma$
onto all events $e_{i}$ where $\psi(e_{i})=true$, i.e.,

$\mathit{Proj}_{\psi}(\sigma)=\langle
e_{1},\ldots,e_{n}\rangle|_{\psi(e_{i})=true}.$

We obtain the _projection_ of $L$ into $\psi$, written
$\mathit{Proj}_{\psi}(L)$, by setting
$\pi_{trace}(c)\mathrel{:=}\mathit{Proj}_{\psi}(\pi_{trace}(c))$.

Here are several example projection predicates for the event log in Table 2:

  * •

$\psi_{1}(e)\equiv\pi_{\text{life-cycle}}(e)=\text{complete}$ (only “complete”
events)

  * •

$\psi_{2}(e)\equiv\pi_{\text{delivery}}(e)\neq\perp$ (only events with a
reference to a delivery)

  * •

$\psi_{3}(e)\equiv\pi_{\text{type}}(e)=\text{online}$

  * •

$\psi_{4}(e)\equiv\pi_{\text{user}}(e)\in\\{\text{Alice},\text{Bob}\\}$ (only
events where Alice or Bob are involved)

  * •

$\psi_{5}(e)\equiv c=\pi_{order}(e)\mathrel{\wedge}\pi_{trace}(c)=\langle
e_{1},\ldots,e_{n}\rangle\mathrel{\wedge}e=e_{i}\mathrel{\wedge}\forall
j=i+1,\ldots,n\mathrel{\wedge}\pi_{action}(e_{i})\neq\pi_{action}(e_{j})$
(only the last occurrence of each activity in a trace)

  * •

$\psi_{6}(e)\equiv|\\{e^{\prime}\mid c^{\prime}\in
L,e^{\prime}\in\pi_{trace}{c^{\prime}},\pi_{act}(e)=\pi_{act}(e^{\prime})|\geq
5$ (only events of activities which occur at least 5 times in the event log
$L$).

Note that when we constructed the event log from the event table, each event
$e$ had the chosen case identifier $id$ as event attribute, i.e.,
$\pi_{id}(e)=c$ refers to the case. When constructing the event log, we used
the value $c$ to construct the case itself. This means, we can “reach” the
case $c$ from an event $e$, and once we have the case $c$, we can “reach” the
entire trace $\pi_{trace}(c)$ that also contains $e$. We use this in
$\psi_{5}(e)$ to reason about whether $e$ is not the last event in the trace
of the same activity.

Such projection attributes are not possible in all process mining software. It
can only be defined if the event $e$ actually has a reference to the case $c$
and the data structure in which the event is stored allows to resolve this
reference. Similarly, $\psi_{6}(e)$ requires that the entire event log (or
statistics about the event log) are accessible.

###### Exercise 21

Apply $\mathit{Proj}_{\psi_{2}}(L)$ on the event log of Table 2 and derive the
simple event log for the activity name event classifier.

###### Exercise 22

What is the difference between $\mathit{Select}_{\mathit{selectP_{1}}}(L)$ and
$\mathit{Proj}_{\mathit{projP_{3}}}(L)$?

For aggregation, we do not provide a full formal definition, but outline what
has to be defined. Aggregation in a case $\mathit{Agg}_{g,r}(c)$ requires two
functions $g$ and $r$:

  * •

A _grouping_ classifier $g:\mathcal{E}\to\mathit{Val}$ which maps each event
to a value, similar to an event classifier.

  * •

With $g$, we partition the trace $\pi_{trace}(c)=\sigma$ into maximal
subsequences $\sigma_{i}\langle e_{i_{1}},\ldots,e_{i_{n}}\rangle$ so that
$g(e_{j})=g(e_{j+1})$ for all $i_{1}\leq j<i_{n}$, e.g., all subsequences with
the same activity name. This results in a sequence of $k$ such sub-sequences
of various lengths, i.e.,
$g(\sigma)=\langle\sigma_{1},\ldots,\sigma_{k}\rangle$, for instance,
$\langle\langle e_{1},e_{2}\rangle,\langle e_{3}\rangle,\langle
e_{4},e_{5}\rangle\rangle$

  * •

A _replacement_ function $r:\mathcal{E}^{+}\to\mathcal{E}$ that replaces any
non-empty subsequence $\langle e_{i},\ldots,e_{i+m}\rangle$ by a new event
$r(\langle e_{i},\ldots,e_{i+m}\rangle)=e^{\prime}$ and defines the event
attributes for $e^{\prime}$ based on the attribute values of $\langle
e_{i},\ldots,e_{i+m}\rangle$; $r$ specifically has to set the timestamp of
$e^{\prime}$ to be within
$\pi_{time}(e_{i})\leq\pi_{time}(e^{\prime})\leq\pi_{time}(e_{i+m})$. For a
singleton sub-sequence $\langle e_{i}\rangle$, the replacement function should
just return the event $e_{i}$, i.e., the event remains unchanged.

  * •

$\mathit{Agg}_{g,r}(c)$ apply $r$ to each sub-sequence $\langle
e_{i},\ldots,e_{i+m}\rangle$ obtained from $g$ which results in a new sequence
of events, i.e., $\mathit{Agg}_{g,r}(c)=\langle
r(\sigma_{1}),\ldots,r(\sigma_{k})\rangle$ where
$g(\sigma)=\langle\sigma_{1},\ldots,\sigma_{k}\rangle$ and
$\sigma=\pi_{trace}(c)$. For example,
$\langle r(\langle e_{1},e_{2}\rangle),r(\langle e_{3}\rangle),r(\langle
e_{4},e_{5}\rangle)\rangle=\langle e_{12},e_{3},e_{45}\rangle$.

  * •

Set $\pi_{trace}(c)\mathrel{:=}\mathit{Agg}_{g,r}(c)$

For example, we can use $g(e)=\pi_{action}(e)$ to find all subsequences where
the same activity occurs repeatedly. In Table 2, this would be only $\langle
e_{5},e_{6}\rangle$. We can then define a replacement function $r(\langle
e_{1},\ldots,e_{k}\rangle)$ where the new event $e^{\prime}$ gets
$\pi_{x}(e^{\prime})=\pi_{x}(e_{k})$ for all attributes $x$ defined for
$e_{k}$, i.e., we replace the sequence by the last event. We could also define
$\pi_{item}(e^{\prime})=\\{\pi_{item}(e_{i})\mid 1\leq i\leq k\\}$ to collect
the items that were involved in these events into a set.

###### Exercise 23

What is the difference between aggregation where any subsequence is replaced
by the last event and projection with $\psi_{5}(e)$?

All three event log pre-processing operations selection, projection, and
aggregation always result in single event log. This allows to apply them in
arbitrary combinations. For example, first project onto all events where “Bob”
is involved and then aggregate on $\pi_{action}(e)$.

As in any data analysis, identifying which event log pre-processing operations
to apply for the analysis question at hand is an iterative process. Process
mining software supports this iterative process by letting the analyst
interactively build a _stack_ of filtering operations that can be modified and
re-arranged alongside a visualization of the outcome of the filtering
operation. Figure 3 shows the “Filter Event Log” plugin of ProM.

Figure 3: Interactive event log filtering in ProM, accessible via the “Filter
Event Log” plugin. The shown event data has been filtered using two filters
executed one after the other.

Other pre-processing operations on event data are

  * •

Clustering the cases in the event log $L$ into multiple sub-logs
$L_{1},\ldots,L_{k}$ so that cases in a sub-log $L_{i}$ have similar trace
variants and cases in different sub-logs $L_{i}\neq L_{j}$ have maximally
different trace variants. Technically, clustering is repeated selection.
However, the selection criteria are not based on selection predicates; see [8]
for a survey on available clustering techniques.

  * •

Event data abstraction is a form of aggregation where arbitrary patterns in
the event data are aggregated into higher level events; see [3] for an
overview.

##  6 Event logs have limitations

Event logs as defined in this document face severe limitations.

  * •

The timestamp information in event data is often not reliable. For example, if
events are only recorded on day-level granularity and three events
$e_{1},e_{2},e_{3}$ occurred on the same day, then their order
$e_{1},e_{2},e_{3}$ in the event table may not be the order in which they
occurred. When creating an event log, we have to pick on ordering of these
events to build a trace, but it may be the wrong one. A possible solution is
to define a trace $\pi_{trace}(c)$ not as a sequence $\langle
e_{1},\ldots,e_{n}\rangle$ of events, but as a _strict partial order_ $(E,<)$
where $e_{i}<e_{j}$ are ordered only iff
$\pi_{time}(e_{i})<\pi_{time}(e_{j})$. Events with the same time-stamp remain
unordered.

  * •

Structured event logs only order event data according to a single case
identifier. However, we have seen that even basic event data contains multiple
entity identifiers that are in 1:n and n:m relationships to each other. For
example in Table 2, customer A7001 is involved in 3 orders and deliver 623 is
involved in 2 orders. The data structure of the structured event log cannot
capture these relations. Graph-based data structures such as [5, 4] allow
tracing the behavior of multiple objects together.

## References

  * [1] van der Aalst, W.M.P.: Process Mining - Data Science in Action, Second Edition. Springer (2016). https://doi.org/10.1007/978-3-662-49851-4, https://doi.org/10.1007/978-3-662-49851-4
  * [2] Acampora, G., Vitiello, A., Di Stefano, B., Aalst, W.M.P.v.d., Günther, C.W., Verbeek, H.M.W.: IEEE 1849TM: The XES Standard: The Second IEEE Standard Sponsored by IEEE Computational Intelligence Society. IEEE Computational Intelligence Magazine pp. 4–8 (May 2017). https://doi.org/10.1109/MCI.2017.2670420
  * [3] Diba, K., Batoulis, K., Weidlich, M., Weske, M.: Extraction, correlation, and abstraction of event data for process mining. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 10(3) (2020). https://doi.org/10.1002/widm.1346, https://doi.org/10.1002/widm.1346
  * [4] Esser, S., Fahland, D.: Multi-dimensional event data in graph databases. J. Data Semant. 10(1-2), 109–141 (2021). https://doi.org/10.1007/s13740-021-00122-1, https://doi.org/10.1007/s13740-021-00122-1
  * [5] Fahland, D.: Process mining over multiple behavioral dimensions with event knowledge graphs. In: van der Aalst, W.M.P., Carmona, J. (eds.) Process Mining Handbook, Lecture Notes in Business Information Processing, vol. 448, pp. 274–319. Springer (2022). https://doi.org/10.1007/978-3-031-08848-3_9, https://doi.org/10.1007/978-3-031-08848-3_9
  * [6] Günther, C.: First XES Standard Definition version 1.0. Xes standard proposal (November 2009), http://www.xes-standard.org/
  * [7] IEEE 1849 (XES) WG: IEEE Standard for eXtensible Event Stream (XES) for Achieving Interoperability in Event Logs and Event Streams. IEEE Std 1849-2016 pp. 1–50 (Nov 2016). https://doi.org/10.1109/IEEESTD.2016.7740858
  * [8] Zandkarimi, F., Rehse, J., Soudmand, P., Hoehle, H.: A generic framework for trace clustering in process mining. In: van Dongen, B.F., Montali, M., Wynn, M.T. (eds.) 2nd International Conference on Process Mining, ICPM 2020, Padua, Italy, October 4-9, 2020. pp. 177–184. IEEE (2020). https://doi.org/10.1109/ICPM49681.2020.00034, https://doi.org/10.1109/ICPM49681.2020.00034