Summary (797511), страница 3
Текст из файла (страница 3)
The model, re-discovered from scratch using only anevent log, can be deprived of such an advantage. Besides, the presented techniqueis best suited when a set of activities is stable during the repair.The second chapter presents the main contribution of this thesis: themodular technique for process model repair.In the first section, we present the specific problem considered in the thesis.Let ⊆ be a set of process activities. The initial process model isa workflow net = (, , , ) with transition labels taken from .
The netmay have silent transitions labelled with . Thus, the labelling function is : → ∪ { }.An event log is a multi-set of traces, and is defined in Section 1.1.3.Event names are taken from the same set of activities , i.e. ∈ ℬ(* ). Notethat the event names of the log and the transition labels of the model arefrom the set , i.e. () = . This means, that there are no new or obsoleteactivities in the process, and the repair technique does not add/remove transitionsto/from the model, except -labelled transitions.Besides, it is assumed that all transitions of a model except silenttransitions have unique labels. That is, for a model = (, , , ), ∀1 , 2 ∈ : if (1 ) = (2 ) then 1 = 2 .
Note that this assumption is needed to decomposethe process model. In the worst case, if all transitions have the same label,such a model can not be decomposed using decomposition algorithms which areconsidered in this thesis.The event log represents the normative (correct) behaviour that shouldbe modelled, when the model does not perfectly fit this event log, i.e. (, ) < 1.Given a net and an event log , the problem is to automaticallyconstruct a Petri net (repaired model ) such that (, ) = 1.
Strictlyspeaking, perfectly fits . In other words, this repaired model can replayall traces of . This is a strict condition of success that needs to be satisfied.Besides, there are two soft conditions, which are aspired for but may notbe satisfied.Firstly, the precise repaired model is desired. should not allow “toomany” execution variants which are not present in .
At least, the repaired model should be as precise as the initial model , which means ( ) ≈( ). In other words, both of these models are approximately equally12precise. Ideally, ( ) = ( ), but small fluctuations arepossible.Secondly, models and should have a similar structure. The lesswe change a model by repair, the better this repair algorithm is.
That is why anumber of model elements touched by a repair procedure reflects the acceptabilityof a repair in Section 4.3, in which an experimental evaluation of proposed repairtechnique will be described.Then, this chapter presents the main contribution of this thesis. Firstly, itpresents the modular scheme of the proposed model repair technique. Secondly,algorithms are presented implementing the general modular scheme for particularrepair cases.The modular repair scheme proposed in this thesis employs the ideaof patching-up.
The algorithm searches non-conforming model fragments, andreplaces them with conforming ones. This technique is modular. In other words,the general scheme is constructed of several building blocks. Various particularalgorithms can play this role. Thus, the general scheme can be refined into differentrepair algorithms by choosing appropriate algorithms as its actual proceduralparameters.Each building block of the modular repair scheme executes one repair step.Figure 4 shows a graphical representation of this scheme. Building blocks arehighlighted using bold frames.The input to the scheme is a couple (, ), where is a correct(normative, trusted) event log, and is a non-conforming initial model. Themodel is decomposed into several fragments 1 , 2 , .
. . , using oneof the model decomposition algorithms. In the projection block, an algorithmsplits the event log into sub-logs 1 , 2 , . . . , which correspond to model fragments (sub-nets). The selection block contains a conformancechecking algorithm. This algorithm calculates the conformance value for eachpair ( , ), where = 1, 2, . . . , .
According to the corresponding conformancevalue, all model fragments are separated into two sets. The first one containsconforming (good ) fragments. The second one consists of sub-nets which do notconform to corresponding sub-logs (bad fragments).
The repair block contains analgorithm which replaces non-conforming model fragments by conforming ones.The composition block is paired with the decomposition one. The result of repaircan be evaluated in the evaluation block by using a conformance checking method,or another approach.This general scheme can be defined more formally, as it is done in thefollowing definition.13EventLogInputInitialWorkflow netDecompositionProjectionSelectionSub-netsConformingSub-netsSub-logsNon-conformingSub-netsCompositionSub-logs forNon-conformingSub-netsCorrectedSub-netsRepairEvaluationEvaluationResultOutputCorrectedWorkflow netFigure 4: Modular repair schemeDefinition (Modular Repair Scheme). Let denote the universal set ofactivities, and N be the set of all WF-nets with transitions labelled over .We define the modular repair scheme as a procedure, which takesan event log ∈ ℬ(* ) and a labelled WF-net N ∈ N as its input, andreturns a Petri net N r = ModularRepair (, N ) perfectly fitting the log , i.e.
(,N r ) = 1, as a result.The procedural parameters in the modular repair scheme are the following:∙ eval ∈ (ℬ(* ) × N ) → [0; 1] is an evaluation function,∙ repair ∈ (ℬ(* ) × N ) → N is a repair algorithm,∙ split ∈ N → (N ) is a decomposition algorithm,∙ compose ∈ (N ) → N is a composition algorithm.Usually, fitness is considered as the main conformance criterion when doingprocess mining. Indeed, no one needs a model that does not reflect an observedbehaviour of the system analysed. Thus, we also consider fitness as the majorcriterion. Then, we formulate the perfect fitness repair conditions.Definition (Perfect Fitness Repair for Workflow Nets). Let ∈ ℬ(* ) bean event log with ⊆ , and let N ∈ N be a workflow net such that14fitness(, N ) < 1.
Let N ′ = ModularRepair (, N ) be a modular repair scheme.ModularRepair (L, N ) is a perfect fitness repair if fitness(, N ′ ) = 1.The modular repair technique guarantees perfect fitness of a repairedmodel, if a perfect discovery algorithm5 is used in the repair building block, and avalid decomposition algorithm is employed to decompose the model. By definition,perfect discovery algorithms construct a perfectly fitting process model for anyevent log. A decomposition is valid if it successfully decomposes both model andits marking, and allows for an unambiguous composition.Theorem (Perfect Fitness Repair Conditions).
The modular repair schemeModularRepair (L, N ) ensures perfect fitness if1. split is a valid decomposition function;2. repair is a perfect discovery function, i.e. for any event log it returns a Petrinet, which perfectly fits this event log;3. compose is a transition fusion function that merges all transitions with thesame labels.The proof of this theorem presented in Chapter 2.Then, we describe the algorithm that employs concrete proceduralparameters as building blocks of the general modular scheme.We assign the procedural parameters in the modular repair scheme asfollows:∙ evaluation function eval ∈ (ℬ(* ) × N ) → [0; 1] is the alignment-basedfitness checking algorithm [22],∙ model repair function repair ∈ ℬ(* ) × N ) → N is the inductiveprocess discovery algorithm [23], or the integer-linear-programmingbased discovery algorithm [24],∙ decomposition function splitdecomposition algorithm,∈N→(N ) is the maximal∙ composition function compose ∈ (N ) → N is the algorithm based onfusion of transitions with the same labels.This gives us the decomposed repair algorithm.
In this chapter, we show thatthis repair algorithm satisfies the perfect fitness repair conditions 1, 2, and 3.5These algorithms always discover perfectly fitting models.15To implement the repair algorithm, we need to be able to decomposePetri nets maximally. Thus, we propose an algorithm to calculate maximaldecomposition of a Petri net. It is presented in Chapter 2.Figure 5 shows a maximal decomposition of the process model shown inFigure 3.
The net is decomposed into six net fragments: 1 , 2 , 3 , 4 ,5 , and 6 . All transitions in the initial model are observable and have uniquelabels. Thus, transitions 1 (a), 2 (b), 3 (c), 4 (d), 5 (e), 6 (f), 7 (g), and8 (h) are borderline nodes. Inner nodes are places , 1 , 2 , 2 , 3 , 4 , and. One may see how the initial marking is split: the single token moves withthe place in the sub-net 1 . It is easy to see, that fragments can becomposed into the workflow net shown in Figure 3 via a fusion of transitions withthe same labels.SN5hSN2hSN1sourceSN3t8aat1t1c1bbt2t2c2cSN4ct3t3ddt4t4t8c3eet5t5c4fSN6ft6t6ggt7t7sinkFigure 5: Maximal decomposition of the model from Figure 3We call this repair method the naive modular repair technique.
Figure 6shows how the model from Figure 3 can be repaired using this repair algorithm,if the event log consists of two traces: ⟨, , , , ⟩ and ⟨, , , , ⟩.hft8asourcet1cbt2c1s3t3ττts1s2t6ec3t5c4gsinkt7ts2dt4Figure 6: Process model from Figure 3 repaired using the naive techniqueRepairs of the naive technique are not perfect hence such models areimprecise.
That is why the procedure greatly increases the number of possiblemodel runs. The chapter contains detailed discussion of the reasons for thisprecision reduction. In order to cope with this shortcoming of the naive repairtechnique, we propose the improved repair algorithm.16The key idea is to enlarge each fragment-to-repair so that the repairprocedure will not affect borderline transitions of enlarged fragments.
Figure 7demonstrates attaching neighbours to the fragment 3 in the example net. Thissub-net has two neighbours, namely 2 and 4 , to be attached.W(SN3) SN5hSN2hsourceSN3t8SN1aat1t1c1bbt2t2c2cSN4ct3t3ddt4t4t8c3W(SN3)cSN1sourceaat1t1t3bc1t2c2dc3t4eet5t5c4fSN6ft6t6ggt7t7sinkSN5hht8t8eet5t5c4fSN6ft6t6ggt7t7sinkFigure 7: Neighbours are attached to the sub-netWe define an enlarged fragment (N ) for N as a fragment obtained byattaching to N all its neighbours, i.e.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
