Диссертация (1137084), страница 5
Текст из файла (страница 5)
Figure 9 showsthese two types of inconsistencies.In this chapter, we also describe the greedy repair technique, that is based on the modularrepair algorithm, and is able to repair non-local inconsistencies in a desired way.The input to this algorithm consists of two following components: a workflow net , whichwill be corrected, and an event log , which contains a real system behaviour. The algorithmdecomposes the model using maximal decomposition.
Then, it selects the sub-net with theworst fitness to the corresponding sub-log. Then, the iteration begins. At each step, a sub-netis enlarged, that is joined with its neighbours = ( ), and replaced by the model, which18Local:...at1bp1...t2et20dp20...t21<...,a,b,,d,e,...>d...Non-local:...at1bp1...t2et20p20t21<...,a,d,b,e,...>Figure 9: Two types of inconsistenciesis discovered using a discovery algorithm employed in procedural parameter discover (L ↾A(Nb ) ).Then, an intermediate net ′ is composed and returned. The algorithm iterates until perfectfitness is achieved between the intermediate 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 key modification of the modularrepair scheme is highlighted with light-blue colour.The example of the greedy repair is shown in Figure 11. The model contains two unfittingfragments which are highlighted with red. In particular, the labels of two transitions were swappedbetween these fragments. The greedy algorithm started from one of them, and performed nine stepsto join the sub-nets. Finally, the whole highlighted part of the model should be replaced with anewly discovered model.Chapter 2 presents a family of model repair algorithms which is based on the single modulartechnique.
Its main idea is to decompose the initial model, find sub-nets with inconsistencies, andreplace them with fitting fragments.In the practical field of process mining new algorithms should be evaluated using event logs. Itis difficult to gather a set of real-life models and event logs with suitable characteristics. Thus, wehave developed an approach for generation of synthetic event logs with specified characteristics,which is described in the third chapter.Using the event log generator, we have prepared a set of suitable event logs and evaluated themodular repair technique.
Results of this experimental evaluation are shown in the fourth chapter.In the third chapter the supportive tools are considered which we use to generate sampleevent data. We propose a set of algorithms to generate event logs via a simulation of Petri netsand BPMN 2.0 models, and describe the prototype tool that implements presented algorithms.This chapter consists of two main parts. The first one describes a set of algorithms to generateevent logs via a simulation of Petri net models. A similar approach is also applicable for BPMN 2.0models. This extension is described in the second part of the chapter.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 repairSimulation of a Petri net is based on the standard Petri net firing rule.
The main features ofthe generator tool are as follows:– Generation settings allow users to decide how many event logs will be generated, and howmany traces will these logs include. In order to prevent infinite loops, a user is asked aboutthe maximum number of steps during algorithm execution. All event logs will be generatedwithin single execution of the tool. By default the tool generates 5 event logs while everylog consists of 10 traces and it does at most 100 steps.– In cases of non-deterministic choice, a tool user may specify how the tool selects a transitionto fire. A random transition can be fired with equal probability, or preferable transitions canbe specified for a choice construct.– Besides, the tool supports the timed execution of process models.
A user can define executiontime for every transition and how punctual they are executed by defining deviations bounds.Then, two separate records corresponding to an event appear in the log. The first one is thestart of an activity execution 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.20443536759845328546789Iterations:111237234567898These fragments do not fit the logFigure 11: Example of the greedy model repairThis chapter also describes algorithms to simulate BPMN 2.0 models, which contain coreBPMN elements (tasks, AND-/XOR- gateways), data objects, and message flows.
This approachtakes time into account and allows for timed simulating of process models.We describe how the proposed simulation approaches have been tested and evaluated. Using thetool described in this chapter, we have evaluated the modular repair technique that we presentedin the second chapter of this thesis. Results of this evaluation are considered in the fourth chapter.The fourth chapter describes a prototype software that implements the modular repairtechnique, and presents results of its experimental evaluation.We have implemented the process model repair approach as a plug-in for ProM 6Framework [26] which is a well-known tool in the process mining community.
The main featuresof this tool and its architecture are described shortly in this chapter. The prototype software canbe found at the page of this project: http://pais.hse.ru/research/projects/iskra.In order to evaluate our repair techniques, we use the experimental scheme as shown inFigure 12. The goal of an experimental evaluation is to apply a prototype implementation ofalgorithms to test samples, and measure the characteristics of result repaired models.
These resultsshow pros and cons of an algorithm when applied to samples with particular properties.Chapter 4 describes selected process models, and corresponding generated event logs. Eachsample model has been used to generate the event log with perfect fitness and other characteristics.A natural way to test or evaluate the repair technique is as follows. Take a correct (serviceable)object , introduce artificial inconsistencies in it ( ), and then try to repair it using theevaluated/tested technique. If it works as expected, then the repaired object should work(service) as the initial object does.
Otherwise, the test is failed. The result of such a repair canbe evaluated using suitable measuring tools. Results of different experiments may be compared.In the fourth chapter, we follow exactly the same way to evaluate the modular process modelrepair. A repair technique passes the test if it is able to reconstruct the initial sample model.Besides, we applied other repair methods to compare the results. The chapter presents tables andfigures which show results of the process model repair using various approaches.21Sample ModelEvent LogGeneratorEventLogProcess ModelRepairChangedModelRepairedModelEvaluationResultsFigure 12: Scheme of the experimental evaluationThe experiments show an applicability of our approach.
The naive technique provides a userwith perfectly fitting but significantly less precise models compared to those obtained by usingother approaches. Moreover, the behaviour of some models is so diverse that the alignment-basedalgorithm for calculating model precision lacks available hardware resources. These are cases, whena repaired by the naive technique model contains many silent transitions and transitions withoutinput/output places.The improved method reconstructed the initial model in most cases.
The experimentalevaluation shows its effectiveness.Figure 13 shows the model from Figure 1 repaired using the improved technique. Fragmentsof the model changed during repair are highlighted with green colour. One may note that such arepair preserves structure of the initial model.Figure 13: Model from Figure 1 repaired using the improved techniqueWe also evaluated techniques in non-local cases. The greedy technique is effective when amodel contains non-local inconsistencies. However, it changes a model more, than the improvedtechnique. One can easily compare naive, improved, and greedy techniques using data shown inthis chapter.
Within considered examples, the greedy technique constructs models, which are asprecise as models discovered from scratch.22Extra large models can also be repaired using the techniques proposed in this thesis. Forexample, Figure 14 shows a model that contains more than a thousand of nodes which has beenrepaired using the greedy technique. A fragment that has been replaced by the repair is highlightedwith green.Figure 14: Extra large model repaired using the greedy technique with Inductive minerFinally, the last chapter concludes the thesis. Main contributions of this project aresummarized in the chapter.
It also discusses open issues, and directions for future research onthe subject of this thesis.23Chapter 1BackgroundLet us begin by introducing basic notions, which are needed in the remainder. In this chapter,we also discuss related work.The chapter is organized as follows. Section 1.2 describes the general context of the work.The notions of process models and event logs are presented in Section 1.1.
In Sections 1.2.1, and1.2.2 we recall the definitions and algorithms, which will be employed in this work. Section 2.6 isabout the approaches for model decomposition, and Section 4.1 describes the usage of modularstrategies in process mining. In Section 1.3 we describe the model repair problem and reviewexisting approaches for its solution.1.11.1.1Basic NotionsMultisets, Functions, SequencesBy N we denote the set of natural numbers including zero. Let be a set. A multiset over is a function ∶ → N, where for ∈ : () is a multiplicity of . By ℬ() we denote the set ofall finite multisets over . A finite multiset can be specified by enumerating all its elements andindicating their multiplicity. For example, = (︀, , , , , ⌋︀ = (︀3 , , 2 ⌋︀ denotes the multiset withthree occurrences of , single , and two ’s.By abuse of notation, we extend the standard set operations to multisets in the usual way.
Let be a set, and , ′ be two multisets over . The sum of multisets and ′ over set is defined as:( ⊎ ′ )() = () + ′ () for all ∈ . We write ⊇ ′ iff ∀ ∈ ∶ () ≥ ′ (). The differenceof multisets and ′ over set , such that ⊇ ′ , is defined as: (/ ′ )() = () − ′ () forall ∈ . The cardinality of a multiset over is denoted by ⋃︀⋃︀ and defined as ⋃︀⋃︀ = ∑ ().∈We will consider sets as a special case of multisets, where elements can occur 0 or 1 times. Thus,operations defined for multisets can be applied to sets.For a function ∶ → , ( ) denotes its domain, ( ) = { ()⋃︀ ∈ ( )} ⊆ definesits range, and ∶ ↛ denotes a partial function, s.t.
( ) ⊆ . If ( ) = , then is a24total function. A function ↾ ∶ ↛ is a projection of a (partial) function onto a set ⊆ suchthat ∀ ∈ ∶ ↾ () = (). This notation can be used for multisets, e.g. (︀3 , , 2 ⌋︀↾{,} = (︀, 2 ⌋︀.A relation over sets 1 , 2 , . . . , is a subset ⊆ 1 × 2 × ⋅ ⋅ ⋅ × . We denote a set ofelements of relation as () = ()∪(), where () is the domain of , and ()is the range of . In particular, ({(, ), (, )}) = {, }, ({(, ), (, )}) = {, }, and({(, ), (, )}) = {, , }.By ∗ we denote the set of all finite sequences over a set , and we use triangle bracketsto denote sequences, e.g.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
