Диссертация (1137084), страница 17
Текст из файла (страница 17)
It splits the process model, finds fragments with inconsistencies, and repairs thesesub-model using process discovery. This procedure is performed in a greedy way to cope withnon-local inconsistencies. In the worst case the algorithm reduces to process discovery, and builds72a completely new perfectly fitting model. Chapter 4 shows the results of experimental evaluationof this algorithm.2.6Process Model Decomposition: Related WorkThe techniques presented in this chapter are based on divide & conquer principle, one ofseveral fundamental algorithmic approaches. Obviously, this is not the first usage of this principlein process mining.
In this thesis, a process model is decomposed using maximal decomposition oralgorithms which are based on it. However, other algorithms have been proposed in literature todecompose process models in various notations. Some of these algorithms applicable to Petri netsand produce valid decompositions. Thus, these algorithms can be used as a building block of themodular repair alongside maximal decomposition.
Related papers are listed in this section.It is already has been shown how the divide & conquer principle can be applied to processdiscovery and conformance checking [126]. H. Verbeek, W. van der Aalst, and J. Muñoz-Gamaconsidered different practical aspects of process model decomposition in process mining [127–129].In these papers, the log decompositions for better process discovery and conformance checking havebeen proposed.
So-called passages are used in the method by W. van der Aalst and H. Verbeek[127]. Earlier, a process discovery has been decomposed by J. Carmona et al. [130]So-called re-composition has been proposed by B. Hompes et al. [131,132] This method mergesdecomposition fragments to improve a performance of decomposed process discovery. Later, theidea of re-composition has been employed for an alignment-based conformance checking [133].H. Verbeek has proposed more improvements of the alignment-based algorithm based on divide &conquer principle [134–136].J.
Muñoz-Gama et al. applied decomposition to conformance checking [105,137]. The techniquefinds in the model special Single Entry Single Exit (SESE) fragments, and then decompose themodel using the fragments found. The idea of SESEs has been brought to process mining byJ. Vanhatalo et al. [110,138] and originates from the field of computer program analysis [139,140].Real-time conformance checking can also be decomposed.
A method to do so has been proposedby S. vanden Broucke et al. [141] Another way to apply divide & conquer principle is to use wellknown MapReduce model to calculate fitness, in cases when an event log is significantly large [18].More recent development include among others a method for event log composition that has beenproposed by L. Raichelson, P. Soffer and H. Verbeek [142].Note that some of decompositions mentioned in this section (for example, SESE-baseddecomposition has been proposed in [137]) are valid. Thus, they may be used as building block ofthe modular process model repair. This is one of directions of the future work, all of which willbe listed in the Conclusions chapter of this thesis.732.7Discussion and ConclusionsThis chapter presented a family of process model repair algorithms, which all based on a generalmodular approach considered in Section 2.2.
The main idea of this approach is to decompose theinitial model, to find sub-nets with inconsistencies with the corresponding sub-logs calculatedusing projection, and to replace them with fragments re-discovered from sub-logs. The most basic(naive) algorithm, that employs this idea, guarantees perfect fitness of the repaired model, butreduces its precision. To eliminate this drawback, we have proposed an improved algorithm forthe local model repair, and a greedy algorithm for the non-local repair.The technique considered in this thesis has been proposed for the cases when the model isrelatively large whereas inconsistencies are local and moderate.
The decomposition of the modelis used for the subsequent replacement of some unfitting fragments. The repaired model differsfrom the initial model only by the replaced fragments. Thus, these models are similar whenfragments are small, and only couple of fragments need to be replaced. This is the case whenfitness inconsistencies between an event log and a model are insignificant and local, and, at thesame time, a number of silent transitions in the model is small. In other words, the model can bedecomposed validly. The proposed technique is especially suitable when the initial model was builtby a human expert, and therefore well perceived by a person. The model, discovered from scratchto eliminate fitness inconsistencies, can be deprived of a readability advantage. Nevertheless, if asystem’s behaviour has been changed significantly, a process discovery of a completely new modelis more appropriate than any type of repair.The set of process activities does not change in the considered problem statement (seeSection 2.1).
The case, when this set changes, may be split in two following sub-cases:1. there are new activities in an event log which were not present in the model (as transitionslabelled with corresponding labels),2. there are obsolete activities in the model which are missing in the log (as events withcorresponding names).Recall, that we trust an event log when doing model repair.Actually, the second case is already handled by the presented approach. The techniquedecomposes process model, and then projects corresponding event log to calculate sub-logs.
Thisprojection leaves in each sub-log only those events, which correspond to a related sub-model. Then,the technique evaluates if each sub-log fits the corresponding sub-model. If a sub-model containsan obsolete transition that has no corresponding events in the sub-log, then this sub-model ismarked as non-fitting. The repair of such a sub-model is made using a discovery algorithm appliedto the corresponding sub-log.
As this sub-log contains no events with some name, there will beno transitions with the same label in the discovered model. Thus, all obsolete transitions will beremoved from the model by the modular repair approach.74We intentionally do not consider the first of these two cases, when the model need tobe extended with new transitions which reflect new activities within a process. Well-designedalgorithms to solve this problem have been proposed by D. Fahland and W.
van der Aalst [25],and improved by A. Polyvyanyy et al. [108] Moreover, these algorithms can be jointly used withour approach in a single process of model repair. In particular, one may firstly apply modularrepair approach that removes obsolete transitions and rearranges transitions which remain in themodel, and only then apply a suitable version of an algorithm contributed by D. Fahland andW. van der Aalst [25] that will add new transitions (or models of sub-processes) to the repairedmodel.A computational complexity of the modular repair technique is dictated by the complexity ofalgorithms used as building blocks. All operations of the general approach itself are made in a lineartime.
The most complex procedure is an alignment-based fitness checking which is exponentialaccording to the number of different process activities (transitions with the different labels in aprocess model) [22]. Thus, the whole modular repair technique is exponential in the worst case,if this fitness checking technique is used. Process discovery algorithms have different complexity.ILP -based techniques are also exponential according to the number of process activities, whereasinductive miner is a polynomial time algorithm [143]. The good news is that an actual numberof operations made by the employed time-complex algorithms is not very large due to modeldecomposition used, which itself can be made in a linear time.This chapter considered the main contribution of this thesis — the modular repair technique— and substantiated its correctness.
However, in the practical field of process mining newalgorithms should be evaluated using event logs. It is difficult to gather a set of process modelsand corresponding real-life event logs with exactly suitable characteristics. Thus, we developed amethod to generate artificial event logs with specified characteristics, that supports fine tuning.This method is described in the next chapter. Using a developed event log generator, we carefullyprepared a set of suitable event logs and evaluated the modular repair approach. The results ofexperimental evaluation are shown in Chapter 4.75Chapter 3Generating Artificial Event LogsChapter 2 considered the modular technique to repair process models. Results of its evaluationusing the set of process models and artificially generated event logs are presented in Chapter 4.To generate these event logs, we have used an approach and a tool, which are described in thischapter.This chapter is organized as follows.
Various approaches of process simulation are described inSection 3.1. Sections 3.2 and 3.3 present our techniques to generate event logs. In Section 3.2 weconsider how basic Petri net models may be simulated, whereas Section 3.3 describes generationof event logs using BPMN 2.0 process models. The chapter is concluded with Section 3.4.Process model simulation is an important sub-field of a discipline of process management andanalysis. In the broader field of business process management, simulation is used for performanceprofiling of business and software processes, and “what if” analysis when processes are being redesigned [144, 145]. In this thesis, process simulation is used to prepare test samples for modularrepair algorithms (see Figure 3.1).SimulationProcess ModelEvent LogFigure 3.1: Process simulationIn previous years, enormous work has been done for developing the process mining algorithms.However researchers are continuously inventing new and more sophisticated methods for processmining.
Every new method should be tested and evaluated in various ways.Most of process mining algorithms require an event log as an input parameter. However, inorder to develop and systematically evaluate these algorithms one requires large sets of modelsand corresponding event logs. Although the goal of process mining is to analyse real-life event logs,they are often not suitable for the verification of new algorithms at early stages of the development.76Thus, the first step of evaluation for every process mining method are tests using withartificial event logs.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
