Диссертация (1137084), страница 12
Текст из файла (страница 12)
Firstly, the formal problemstatement is presented in Section 2.1. Then, Section 2.2 describes the modular repair techniqueand its features. Various model decomposition and process discovery algorithms may be employedwithin our approach. A technique with a specific selection of algorithms is considered in Section 2.3.The model is maximally decomposed, and then repaired using Inductive and ILP miners. Thisnaive technique has its drawbacks which are mitigated in the improved technique described inSection 2.4. In turn, the improved technique is developed into the method for the non-local modelrepair considered in Section 2.5. Thus, this chapter proposes techniques for all cases of a modelrepair which are not covered by the other techniques in the field from Section 1.3 of the previouschapter.
We conclude this chapter with summarizing discussion and conclusions in Section 2.7.2.1Problem StatementIn Section 1.3 different process model repair approaches have been discussed. Let us nowpresent formal problem statement considered in this thesis, and underline aspects distinguishingit from the other problem statements.Let ⊆ be a set of process activities. An initial process model is a workflow net =(, , , ) with transition labels taken from . The net is also may have silent transitions labelledwith . Thus, the labelling function is ∶ → ∪ { }.An event log is a multi-set of traces, and is defined as in Section 1.1.3.
Event names aretaken from the same set of activities , i.e. ∈ ℬ(∗ ). Note that a set of event names of the log and a set of transition labels of the model are the same set , i.e. () = . This means, thereare no new or obsolete activities in the process, and this repair technique does not add/removetransitions to/from the model, except -labelled transitions.Besides, it is assumed that all transitions of a model except silent transitions have uniquelabels.
In other words, ∀1 , 2 ∈ : if (1 ) = (2 ) then 1 = 2 . Note that this assumption isneeded only to decompose the process model simply. In the worst case, if all transitions have the50same label, such a model cannot be decomposed using the decomposition algorithms which areconsidered in this thesis.The event log represents the normative behaviour that should be modelled. However, thismodel does not perfectly fit the event log , i.e. (, ) < 1.Given a net and an event log , the repair problem is to automatically construct a Petrinet (repaired model ) such that (, ) = 1, that is, perfectly fits .
In other words,this repaired model can replay all traces of . This is a hard (or strict) condition of successthat need to be satisfied.Besides, there are two soft conditions, which are desired but may not be satisfied in all cases.Firstly, the precise repaired model is desired. Such a model does not allow for “too many”executions which are not presented in .
At least, the repaired model should be as precise asinitial model , which means ( ) ≈ ( ). In other words, both of these modelsare approximately equally precise. Ideally, ( ) = ( ), but small fluctuationsare possible.Secondly, models and should have the similar structure. The less model is changed by therepair, the better this repair algorithm is. That is why a number of model’s elements touched bya repair procedure is counted in Section 4.3, in which an experimental evaluation of the proposedrepair technique will be described.This problem statement differs from those described in Section 1.3.
The most similar approachhas been proposed by D. Fahland and W. van der Aalst [25] (see Section 1.3.1). The key differenceis that in this thesis we focus on cases, when process activities are rearranged, but their set isstable. The majority of the other approaches focus on cases, when new activities are added tothe process, or some activities become obsolete. We believe, that the technique of D. Fahland andW. van der Aalst [25] can cope with such cases very well, whereas activity rearrangement may beresolved using another technique described in the remainder of this chapter.2.2Modular Technique for Process Model RepairThis section describes the general scheme of the modular technique for process model repairappropriate for solving the problem stated in Section 2.1.
The technique is based on the ideaof patch-ups. To repair the model, the technique detects non-conforming fragments in an initialmodel and replace them with newly discovered conforming ones. This modular technique can beused with various concrete algorithms implementing its steps.The general scheme is based on the divide & conquer principle, and defines a class of modelrepair algorithms. A model repair algorithm may be constructed based on the scheme by choosingappropriate methods as actual values of scheme’s procedural parameters. Thus, the repair schemeconsists of building blocks executing repair steps.51EventLogInputInitialWorkflow netDecompositionProjectionSelectionSub-netsConformingSub-netsSub-logsNon-conformingSub-netsCompositionSub-logs forNon-conformingSub-netsCorrectedSub-netsRepairEvaluationEvaluationResultOutputCorrectedWorkflow netFigure 2.1: Modular scheme of the model repair techniqueA graphical representation of the model repair scheme is shown in Figure 2.1.
Building blocksare shown with coloured bold frames. The following blocks are present in the repair scheme:1. Decomposition — an algorithm for process model decomposition,2. Projection — a simple projection algorithm,3. Selection — a method for selection of fragments to repair,4. Repair — a fragment (sub-net) replacement algorithm,5. Composition — an algorithm for fragments composition,6. Evaluation — a method for final evaluation of result.In a concrete implementation of the scheme, each block contains an applicable algorithm. Arcsshow the data transfer between building blocks.
The remainder of this chapter explains a purposeof each block.The input of the scheme is a pair (, ) where is an event log with correct (normative,trusted) process behaviour, and is a non-conforming initial model to be repaired according to52the . The technique works as follows. A workflow net is decomposed into several fragments(sub-nets) using one of model decomposition algorithms. In the projection block, an algorithmsplits the event log into sub-logs which correspond to model fragments (sub-nets).
The selectionblock contains a conformance checking algorithm. This algorithm calculates a conformance metricfor each pair ( , ), where = 1, 2, . . . , .. According to this number, all model fragmentsare separated into two sets. The first one contains conforming fragments (good sub-nets).
Thesecond one consists of model fragments which do not conform corresponding sub-logs (bad subnets). The repair block contains an algorithm which somehow replaces non-conforming sub-netsby conforming ones. Composition and decomposition blocks are paired one with another. Theresulting Petri net can be evaluated in the evaluation block using a conformance checking method.This is a general scheme of the model repair technique.Definition 6 (Modular Repair Scheme). Let denote the universal set of activities, and N bethe set of all workflow nets with transitions labelled over .We define the modular repair scheme as a procedure, which takes an event log ∈ ℬ(∗ ) anda labelled workflow net N ∈ N as its input, and returns a Petri net N r = ModularRepair (, N )perfectly fitting the log , i.e.
(,N r ) = 1.The procedural parameters of 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.In Section 2.3, we propose a specific set of algorithms which can be used to implement thescheme. Obviously, these algorithms cannot be chosen arbitrarily. The main constraint comesfrom the requirement of decomposition validity [126]. Valid decomposition assumes that the onlyelements, which can be shared between different model fragments, are visible transitions withunique (in the initial net) labels.
We slightly modify the definition of W. van der Aalst [126]. Inthis thesis, the valid decomposition is defined for workflow nets. This class of models is a sub-classof Petri net models considered in the original paper [126]. Thus, all results of W. van der Aalst [126]remain in force.Definition 7 (Valid Decomposition of a Workflow Net). Let N ∈ N be a workflow net with alabelling function . = {N 1 , N 2 , . . . ,N } ⊆ N is a valid decomposition if and only if– = ( , , , ) is a Petri net for all 1 ≤ ≤ ,– = ↾ for all 1 ≤ ≤ ,– ∩ = ∅ for 1 ≤ < ≤ ,53– ∩ ⊆ (N ) for 1 ≤ < ≤ , and– N = ⋃1≤≤ N .(N ) is the set of all valid decompositions of N .W.
van der Aalst proved [126] that each valid decomposition can be used to decompose bothprocess discovery and conformance checking. This means that one can split a model into severalfragments using valid decomposition and then unambiguously compose the initial model fromthese fragments using a suitable composition function. More formally, the following statementsare valid.Theorem 1 (Checking for Perfect Fitness Can Be Decomposed [126]).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
