Summary (797511), страница 4
Текст из файла (страница 4)
(N ) = N ∪ (N ). Here (N ) ={︀ }︀N | N ∈ ∧ ∩ ̸= ∅ , and , ∈ {1, 2, . . . , }.The procedure of fragment enlargement is applied when there are morethan one unfitting fragment in model decomposition. It can be defined as follows.{︀}︀Definition (Sub-net Enlargement Procedure). Let = N 1 , . .
. ,N n be adecomposition of a workflow net , and = ∪ , where is a set ofunfitting net fragments, and is a set of other fragments. Obviously, ∩ =∅. The fragment enlargement procedure consists of the following steps:1. Each fragment from is extended by attaching its neighbours: ∀N ∈ :⋃︀ = (N ), = (N ); = is a set of all enlarged fragments,⋃︀ and = is a set of all fragments which were affected by the procedure,where = 1, 2, . . . , ; note that fragments can have common neighbours;2. All affected fragments are removed from the initial decomposition = ∖ ;3.
The new decomposition includes enlarged fragments: N = ∪ .We have shown that the enlargement procedure can be added to themodular repair technique, because it keeps a decomposition valid. This isformulated in the following theorem (Chapter 2).17Theorem (Sub-net Enlargement Preserves Decomposition Validity). Let N ={︀ 1}︀N , . . . ,N n ∈ (N ) be a valid decomposition of a net .
Let N be an enlargeddecomposition in which two fragments are combined, that is ∃, such that 1 ≤ <{︀}︀{︀}︀ ≤ and N = ∪ ∪N ∖ , . Then N is a valid decomposition,i.e. N ∈ (N ).The proof of the theorem is in Chapter 2.We call this advanced algorithm with a sub-net enlargement the improvedmodular repair technique. A model repaired using this technique is more precise(see Figure 8) when repairing local inconsistencies.dbt4as-startc3τt1c1ts1c2c5c8τττts2ts3ts4c4sourcet2c7eτt5ts5c6cs-endft3t6ht8c9gsinkt7Figure 8: Process model repaired using the improved techniqueIn a local case, the repair needed for each inconsistency is just a changeof the flow relations within a single model fragment. When repairing non-localinconsistencies, we actually need to “move” the transition from one fragment toanother, which is impossible using local repair methods.
In such a case, naive andimproved repair techniques can be used to repair the fitness of a model. Howeverthey reduce the values of other conformance metrics, including precision. Figure 9shows these two types of inconsistencies.In this chapter, we also describe the greedy repair technique, that is basedon the modular repair algorithm, and is able to repair non-local inconsistencies ina desired way.The input to this algorithm consists of two following components: aworkflow net , which will be corrected, and an event log , which containsa real system behaviour.
The algorithm decomposes the model using maximaldecomposition. Then, it selects the sub-net with the worst fitness to thecorresponding sub-log. Then, the iteration begins. At each step, a sub-net isenlarged, that is joined with its neighbours = ( ), and replaced by themodel, which is discovered using a discovery algorithm employed in proceduralparameter discover (L A(Nb ) ). Then, an intermediate net ′ is composed and18Local:...at1bp1...t2et20dp20...t21<...,a,b,,d,e,...>d...Non-local:...at1bp1...t2et20p20t21<...,a,d,b,e,...>Figure 9: Two types of inconsistenciesreturned.
The algorithm iterates until perfect fitness is achieved between theintermediate net ′ and the normative event log . Then, it halts. The model ′is the repaired Petri net.Figure 10 shows the scheme of this algorithm. In the figure, the keymodification of the modular repair scheme is highlighted with light-blue colour.The example of the greedy repair is shown in Figure 11. The model containstwo unfitting fragments which are highlighted with red. In particular, the labelsof two transitions were swapped between these fragments.
The greedy algorithmstarted from one of them, and performed nine steps to join the sub-nets. Finally,the whole highlighted part of the model should be replaced with a newly discoveredmodel.Chapter 2 presents a family of model repair algorithms which is based onthe single modular technique. Its main idea is to decompose the initial model, findsub-nets with inconsistencies, and replace them with fitting fragments.In the practical field of process mining new algorithms should be evaluatedusing event logs. It is difficult to gather a set of real-life models and event logswith suitable characteristics. Thus, we have developed an approach for generationof synthetic event logs with specified characteristics, which is described in thethird chapter.Using the event log generator, we have prepared a set of suitable eventlogs and evaluated the modular repair technique.
Results of this experimentalevaluation are shown in the fourth chapter.In the third chapter the supportive tools are considered which we use togenerate sample event data. We propose a set of algorithms to generate event logsvia a simulation of Petri nets and BPMN 2.0 models, and describe the prototypetool that implements presented algorithms.19EventLogInputInitialWorkflow netDecompositionProjectionSelectionSub-netsConformingSub-netsSub-logsNon-conformingSub-netsEvaluationSub-logs forNon-conformingSub-netsAll Sub-nets, Some Non-conformingEnlargementAll Sub-nets,ConformingConforming Sub-netsEnlargedSub-netsRepairCorrectedSub-netsCompositionEvaluationEvaluationResultOutputCorrectedWorkflow netFigure 10: Non-local process model repairThis chapter consists of two main parts.
The first one describes a set ofalgorithms to generate event logs via a simulation of Petri net models. A similarapproach is also applicable for BPMN 2.0 models. This extension is described inthe second part of the chapter.Simulation of a Petri net is based on the standard Petri net firing rule.The main features of the generator tool are as follows:∙ Generation settings allow users to decide how many event logs will begenerated, and how many traces will these logs include. In order to preventinfinite loops, a user is asked about the maximum number of steps duringalgorithm execution.
All event logs will be generated within single executionof the tool. By default the tool generates 5 event logs while every log consistsof 10 traces and it does at most 100 steps.∙ In cases of non-deterministic choice, a tool user may specify how the toolselects a transition to fire. A random transition can be fired with equalprobability, or preferable transitions can be specified for a choice construct.∙ Besides, the tool supports the timed execution of process models. A user candefine execution time for every transition and how punctual they are executed20443536759845328546789Iterations:111237234567898These fragments do not fit the logFigure 11: Example of the greedy model repairby defining deviations bounds. Then, two separate records correspondingto an event appear in the log.
The first one is the start of an activityexecution that is represented as transition firing. The second one is thetermination/completion of an activity.∙ The tool allows to create both completely fitting and noisy event logs.This chapter also describes algorithms to simulate BPMN 2.0 models,which contain core BPMN elements (tasks, AND-/XOR- gateways), data objects,and message flows. This approach takes time into account and allows for timedsimulating of process models.We describe how the proposed simulation approaches have been tested andevaluated.
Using the tool described in this chapter, we have evaluated the modularrepair technique that we presented in the second chapter of this thesis. Results ofthis evaluation are considered in the fourth chapter.The fourth chapter describes a prototype software that implements themodular repair technique, and presents results of its experimental evaluation.We have implemented the process model repair approach as a plug-infor ProM 6 Framework [26] which is a well-known tool in the process miningcommunity. The main features of this tool and its architecture are describedshortly in this chapter. The prototype software can be found at the page of thisproject: http://pais.hse.ru/research/projects/iskra.In order to evaluate our repair techniques, we use the experimental schemeas shown in Figure 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
