This is the fifth and last lecture on conformance checking.
relating event logs to process models.
of the three conformance checking approaches used in this course.
compared the syntactical structure, using the directly follows relation.
Then we looked at a more advanced approach, using token-based replay.
Today we will look at alignment-based conformance checking.
overcoming the limitations of the approaches that we have seen before?
For example, we should not be restricted to work-flow nets.
where there cannot be two transitions having the same label.
example to model an OR split or an OR join.
we want to relate it to a valid path through the process model.
involving precision, generalization or more advanced forms of diagnostics.
We first need to relate reality to a path through the model.
So it's a kind of enabler for all kinds of other types of analysis.
What is the notion of an alignment?
Here we can see a trace taken from the bigger log that we have used before.
the model that exactly matches, the trace that we have seen in the log.
So the top row is a trace through the log.
in this case they perfectly agree.
Here you see an example of another trace, that doesn't fit into the model.
If we look at the trace a, d, e, g, h, we can see two problems.
First of all, a b or c is missing, which should be executed concurrently to d.
Moreover, at the end it cannot be that both decisions are taken at the same time.
So we should have g or h, but not both.
not mimicked by reality, and at the end there was a g and an h.
And in the model one of these two had to be ignored.
So, what are the terms that we are using, when we are talking about alignments?
refers to the log, the bottom line refers to the path through the model.
the label of an activity in the top row, but not in the bottom row.
A move in model only is the reverse.
The model had to make a move which could not be mimicked by reality.
then both make a move at the same time.
the corresponding analysis techniques, are independent of the process model notation.
BPMN models, for transition systems, it doesn't really matter.
Let us take a look at some examples.
the notion of an optimal alignment.
and in principal, there may be many paths possible through the model.
So which path are we going to choose?
We choose the path that is closest to what we have seen in reality.
is the alignment that is optimal.
Because there's a perfect agreement, between model and log.
it's an example that we have used before.
And now there are multiple explanations that can be used.
so, which one is the best explanation for what we have seen?
e3 that we saw reality, in the model correspond to d1, d2, and d3.
So which is the best alignment?
It is difficult to say, it depends on the cost function.
Are the deviations related to e1, e2 and e3.
More or less of here, than the deviation that we saw with respect to a and b.
to make an objective decision we introduced the notion of a cost function.
So we associate costs to moves.
mobile agree on the action to be taken, we have cost 0.
For all the other situations, we need to introduce positive costs.
in other ways we give it such high cost that we will never take such a solution.
a move on log the same cost, namely one.
the second alignment has cost 2, because we have a move a log and a move in model.
The bottom one has cost 10, because there are 10 no move symbols.
So the top one is optimal, because there is no other alignment that has lower cost.
here we see the two alignments that we have seen before.
because we can not find other alignments that have lower costs.
And so all alignments have cost two or higher.
may be many different optimal alignments, given a trace in the log, and a model.
So the cost of this alignment is two.
f happened, but we should ignore them.
and we ignore e and f, cost 2.
that we need to add two events that did not happen in reality to explain.
The scenario in terms of a path in the model from beginning to end.
in this explanation they are added.
Let's see whether you understood these concepts.
So, take a look at this trace.
The one that we have seen before, and the model.
How many optimal alignments are there?
let's try to understand what these nine alignments are.
because this b could be replaced by a c, and so we have these possible variants.
there are more, because d is concurrent with b and c.
So, we can reorder these different variants.
So we can swap the move related to d with the move related to b, or to c.
if they are very similar, then we can have a lower cost.
are being executed by the wrong person.
then we can associate a penalty to it.
example within a period of three weeks.
you can assign a penalty to the fact that things are being too late.
For example larger orders or smaller orders should take different paths.
One can take a look at the risks, one can take a look at context information.
diagnose the differences taking into account these other perspectives.
So far we only provided diagnostics, move in model only, move in log only.
As indications of that reality and the model disagree.
one, we need to think of a worst case scenario.
What kind of costs does the worst case scenario have?
just have move in models, and move in logs.
compute fitness using the worst case scenario.
we just do a move in log only.
do just move in model only actions.
And if we do that, then we get this number.
So, the optimal alignment had a cost of two, we have seen that before.
The trace has length seven, the shortest path has length five.
we will see that the fitness of this particular trace is 0.83.
So this is the way that we can compute fitness.
Now try to compute fitness using this trace.
And again we should think about a worst case scenario to be able to compute this.
So, we need to align the trace that we have seen with the model.
Look at the optimal alignment, and the worst case alignment.
The optimal alignment, we have seen that before, has a cost of 2.
If we look at the worst case alignment, what does it look like?
Well, this is an example of a worst case alignment.
we see that everything that was in the log, corresponds to a move in log only.
we just do move on model there.
And if we do that, we can see that the optimal alignment has a cost of two.
And the worst case scenario, has cost six plus six.
we find the fitness of 0.833.
Just by accident, it is the same value as what we have seen before.
So what are the advantages of aligning log and model.
events being executed by the wrong person, etcetera.
We get very detailed diagnostics.
We can compare events at a very refined level.
and we can do all kinds of other types of analysis.
And so that makes alignments extremely important.
To illustrate this, let us take a look at this diagram.
So this is a path through the model, and so this is the modeled behavior.
to diagnose where these deviations are, and why they happened.
But this is not the only thing, why alignments are important.
reality into the model, even if it does not fit perfectly.
analysis that require us to use the model and the event data at the same time.
is the ability to drill down.
non-fitting traces, and then we can analyze them separately.
between the deviating cases and the non-deviating cases.
we can analyze the two parts as if they are a new event log.
So we can apply all of the techniques that we have seen before.
We can also move beyond fitness and control flow.
fitness but also precision, generalization and simplicity are important.
these dimensions but they are outside the scope of this course.
we have mostly focus on control flow.
as has been illustrated before.
that take into account control flow and data at the same time.
To read more on conformance checking you can look in chapter seven.
that this providing much more information related to the notion of alignments.