Диссертация (1137084), страница 9
Текст из файла (страница 9)
The top row of each alignmentrepresents a trace from the event log, while the bottom row shows the run in the model (itsexecution). Each event from a trace must correspond to the transition labelled with the same37activity name. If the action in the trace fails to match to the corresponding transition in themodel execution, then “ ≫′′ (skip) is added either to the trace or to the model execution.logmodelaa1bb2cc3ee5ff6logmodelaa1≫b2dd4b≫ee5gg7Figure 1.15: Two alignments (left: perfectly fitting; right: unfitting)The left part of Figure 1.15 shows the alignment with perfect fitting.
In the right alignment,we have added two skips, because otherwise this trace can not be replayed by the model.Let = (, , , ) be a labelled workflow net.Definition 2. Let ≫ = ∪ {≫} be a set of activities with skips, and ≫ = ∪ {≫} be a set oftransitions with skips. A sequence of moves ∈ (≫ × ≫ )∗ between a trace and a net isthe pair of sequences (1 , 2 ), where1. the first sequence 1 without skips is a prefix of the trace , i.e. 1 ()↾ ≤ ,2. the second sequence 2 without skips is a prefix of some model run , i.e. ∃ ∈ ∗ ∶ → and 2 ()↾ ≤ .A pair of elements (,) ∈ is called a legal move, if it is a synchronous move ( ∈ and ∈ ),or it is a log move ( ∈ and = ≫), or it is a model move ( = ≫ and ∈ ).Definition 3. An alignment ∈ (≫ × ≫ )∗ between a trace and a net is a sequence oflegal moves such that1.
the first sequence 1 without skips is exactly , i.e. 1 ()↾ = ,2 ()↾2. the second sequence 2 without skips is a full model run ÐÐÐÐ→ .Obviously, different alignments can be constructed for the same trace-run pair. Alignments areevaluated using cost functions ∶ ≫ × ≫ → R. The alignment with minimal total cost is calledoptimal.Definition 4. An alignment between a trace and a net is optimal with respect to the costfunction , if cost of any other alignment ′ is no lower than the cost of , i.e.
∑(,)∈ ((,)) ≤∑(′ ,′ )∈ ′ ((′ ,′ )).In this thesis, we use the standard cost function :)︀⌉︀⌉︀0, if ∈ , ∈ , and () = , or =≫ , and () = ,⌉︀⌉︀⌉︀⌉︀⌉︀ ((,)) = ⌋︀+∞, if ∈ , ∈ , and () ≠ , or = =≫ ,⌉︀⌉︀⌉︀⌉︀⌉︀⌉︀⌉︀]︀1, overwise.(1.3)38That is, we consider an alignment optimal, if it has minimal number of skips, when using thisfunction.A. Adriansyah [22] has considered various approaches for constructing optimal alignments,which are used for measuring model to log conformance.
In particular, Adriansyah defines relativefitness between an event log and a net as follows: (,, , ) = 1 − (∑,∈ ((,))1⋅ ∑ ∑ ( ()() ⋅)),⋃︀⋃︀ ∈ (,, )(1.4)where is an optimal oracle, is a cost function, and an alignment is selected from the setof all optimal alignments for all traces of .An optimal oracle is a function that calculates for each trace and each optimal alignment the probability of the alignment to be optimal for a trace (see details in [22]). A. Adriansyahshows more complex oracles, which are useful in some cases.
We will say that a model perfectlyfits an event log if (, ) = 1.Note that alignment-based techniques have well-made implementation. For example,Figure 1.16 shows how the set of calculated alignments can be projected on a Petri net. Onemay see that skips of transition c are needed to replay traces from a log. This fact is shown usingthe red frame around a transition.Figure 1.16: Alignments projected on a Petri net to highlight fitness inconsistenciesPrecision. In this thesis, precision is defined and calculated as it has been proposed byA. Adriansyah [22], who in turns refers to the precision calculation technique that has beenproposed by J.
Muñoz-Gama and J. Carmona [104].A precision of a Petri net is calculated with respect to a whole event log. Moreover, it is fullydefined for perfectly fitting Petri nets. If a Petri net does not perfectly fit an event log, an artificialevent log that extends the initial non-fitting log is constructed, and then it is used to calculateprecision [22].Precision is calculated using a special prefix finite automaton constructed using an event log.This automaton relates behaviour from the event log with a behaviour allowed by the Petri net.A.
Adriansyah [22] defines it as follows.Definition 5. Let ⊆ be a set of process activities. And = (, , , ) is a Petri net labelledusing function ∶ → ∪ { }. is an initial, and is a final marking for this net.39A precision automaton of the net is a tuple = (, , , , , ℎ) thatconsists of– a set of automaton states ,– a set of escaping states — in these states automaton transitions lead which have nocorresponding events in an event log ∈ B(),– a set of labelled directed arcs ⊆ × × ( ∪ ),– the state of the automaton,– a weight function ℎ ∶ → R.Besides, the following must hold:(1) A path from the start state of the automaton yields a firing sequence of the net, i.e.
if there existsan arc sequence ∐︁(, 1 , 1 ), (1 , 2 , 2 ), . . . , (⋃︀⋃︀−1 , ⋃︀⋃︀ , ⋃︀⋃︀ )̃︁ ∈ ∗ then ∈ ∗ and → ;(2) Let , ′ ∈ ∗ be two firing sequences in the net ;if there are two arc sequences ∐︁(, 1 , 1 ), (1 , 2 , 2 ), . . .
, (⋃︀⋃︀−1 , ⋃︀⋃︀ , )̃︁ ∈ ∗ and′∗ which both end in the state ∈ ̂︀(, 1′ , ′1 ), (′1 , 2′ , ′2 ), . . . , (′⋃︀′ ⋃︀−1 , ⋃︀′ ⋃︀ , )̃︂ ∈ ′then there exists a marking reachable from in the net such that → and → .The algorithm searches special states in a precision automaton which can not be reachedreplaying the behaviour derived from the event log, but they reachable within the models’behaviour. Note that this is a general definition which defines no construction algorithm. Differentconcrete algorithms can be used. In particular, A. Adriansyah [22] describes the algorithm thatbuilds prefix precision automata.
However, a concrete automata type has no influence on theprecision formula that is defined as follows.Let– ⊆ be a set of process activities,– ∈ B() be an event log,– = (, , , ) be a Petri net with an initial marking and a final marking ,– = (, , , , , ℎ) be a precision automaton of and .Then, precision of a Petri net with respect to an event log is computed as follows:∑ ℎ() ⋅ ⋃︀ {(, , ′ ) ∈ ⋃︀ ′ ∉ } ⋃︀( ) =∈∑ ℎ() ⋅ ⋃︀ {(, , ′ ) ∈ } ⋃︀.(1.5)∈Thus, to compute a precision the relative number of non-escaping states is calculated.
If a precisionautomaton for a particular model and event log has no escaping states, then this model is perfectly40precise, it adds no extra behaviour to that observed in the log. A precision automaton of animprecise model contains a lot of escaping states.Note that fitness and precision of a Petri net with respect to an event log can be correctlycalculated only for sound9 workflow nets using the alignment-based technique [22].Other precision notions have also been presented in the literature [96, 99, 105]. All of themhave their pros and cons. However, the discussion on choosing the best precision and fitnessmetrics is out of scope for this thesis in which we use elaborated metrics implemented in code.A curious reader may find interesting thoughts on conformance metrics in the recent papers byW.
van der Aalst [106] and N. Tax et al. [107]Conformance checking results can be used to improve or repair existing process models. Thenext section outlines the problem of model repair, and reviews the literature describing variousmodel repair techniques.1.3Process Model Repair: Related WorkThis section outlines the process model repair problem and considers different approaches to it.Various problem statements have already been presented in literature and corresponding solutionapproaches have been proposed.In the general case, this problem can be formulated as follows.
For a given (initial ) processmodel and a specified quality criteria, construct a new process model which is better than theinitial one according to the quality criteria (at least one of them). The main difference with rediscovery is that model repair must take initial model into consideration. A, repaired model isconstructed on the basis of the initial model, rather than from scratch. Figure 1.17 represents thescheme of the process model repair.Actual Event LogFitness is betterUnfittingProcess ModelRepairRepairedProcess ModelProcess ModelAdditionalInformationFigure 1.17: Process model repair9Soundness is a correctness criterion for workflow nets [5, 71]. A net is sound if it is free of dead- and live-locks.More formally, a sound workflow net satisfy four properties: boundedness, proper completion, option to complete,absence of dead parts.41Different types of process models are considered in various problem statements.
These canbe Petri nets, process trees, and BPMN models. Generally, there is an event log with recordedbehaviour of a process, and a model corresponding to this process. This process model does notmeet a specified conformance criterion, i.e. it does not reflect reality according to a given measure.Then the initial model is modified to fulfil the specified criterion (usually, a composite criterionor a multi-criteria is used). This is done using different repair operations (or actions), the set ofwhich depends on a modelling notation and additional limitations. Different problem statementsof process model repair arise, when we specify model types, and quality criteria.
The remainder ofthis section describes problem statements, and the approaches which have been proposed to solvethese problems.1.3.1Process Model Repair using Event LogsIn the field of process mining, D. Fahland and W. van der Aalst [6, 25] have been the firstto state the process model repair problem. Authors have proposed to use information from eventlogs to repair process models. Three use cases for model repair have been articulated in thisseries of papers: “improving conformance checking diagnostics”, “monitoring process evolution”,and “supporting customization”.
The common is that a repaired model should be as similar tothe initial one as possible. The other model repair techniques considered in the remainder of thissection seek to achieve similar goals.A labelled workflow net and an event log are given. A workflow net is defined in the samemanner as we do in Section 1.1.2, an event log definition is similar to the one from Section 1.1.3.The goal is to change such that the changed (repaired ) process model ′ can replay all tracesfrom the log , and is as similar to as possible. In other words, the approach focuses onfitness-aware repair of a model control-flow.The approach separates unfitting and fitting traces from the event log using the alignmentbased technique [22].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
