Диссертация (1137084), страница 10
Текст из файла (страница 10)
Unfitting traces are considered as a separate execution variant. For eachtrace, this approach finds log moves in a corresponding alignment, and localizes the places inwhich the model was before the log or model move skip.Let us consider an example. Figure 1.18 shows a workflow net that is able to replay the trace∐︀, , ̃︀. Assume we need to repair this model such that it will additionally successfully replay thetrace ∐︀, , ̃︀.
Obviously, the initial model can not replay this trace.asourcet1bp1t2logmodelcp2t3sinkFigure 1.18: Initial process modelaa1d≫bb2≫c3Figure 1.19: Alignment for the unfittingtraceThe optimal alignment for this trace and the model is shown in Figure 1.19. There are twoskips in it: the single log move (, ≫) and the single model move (≫, 3 ). To repair the first skip42a new transition should be added to the model. The technique adds a transition with the desiredlabel () to the place just before the first synchronous move in the considered run.
Figure 1.20shows how the transition 4 is connected to the place 1 of the model. The second skip can beeasily repaired by adding a silent transition that allows to pass over the transition which is skippedin the alignment. Again, Figure 1.20 shows how transition 3 can be handled.dτt4ts1asourcebt1p1ct2eft5t6p2t3sinkFigure 1.20: Model repair technique of D.
Fahland and W. van der Aalst [25]: basic repairSuch basic repair operations are performed for each non-synchronous move. For example, ifthe model from Figure 1.18 is to be repaired according to the trace ∐︀, , , , , ̃︀, then threetransitions (4 , 5 , 6 ) will be added to the model as shown in Figure 1.20. This technique allowsus to repair model in terms of fitness, but reduces its precision. As a result, we may end up withflower models.D.
Fahland and W. van der Aalst [25] have proposed to group unfitting traces into sub-logs,for which sub-process models are discovered, and then embedded in the initial model. That is,sub-process are added to the initial model in such a way that the repaired model successfullyreplays the given event log. Figure 1.21 shows how this can be done to repair the model fromFigure 1.18 according to the trace ∐︀, , , , ̃︀.τt1p1ts1t2abcsourcep2dt4ep3t5t3sinkfp4t6Figure 1.21: Model repair technique of D. Fahland and W. van der Aalst [25]: sub-processadditionThe presented examples show that this technique works well when new activities are addedto the process, and found in the event log that used for repair. The technique is able to extenda process model with new transitions which allow model to replay the unfitting traces.
If sometransitions are to be skipped in some traces, the technique easily repairs the model by addingsilent transitions. Moreover, this approach also allows us to remove infrequently used parts of themodel, and hence to make the repaired model more simple reducing its fitness.43The main drawback of this technique is that it is less suitable when no additional activitiesare introduced within the process, but existing ones are replaced. In these cases, the techniquemay generate unnecessary complex and imprecise models, even when sub-processes are added tothe model instead of single transitions. This is the main reason to propose the technique that willbe presented in Chapter 2 of this thesis.1.3.2Impact-Driven Model RepairA.
Polyvyanyy et al. [108] have proposed the improvement to the process model repairtechnique of D. Fahland and W. van der Aalst [25]. This method is called impact-driven repair.The model repair problem statement is the same as in the papers by D. Fahland andW. van der Aalst [25] but with an important extension. The proposed procedure can be appliedwhen allowed number of basic repair operations is limited, and various repairs have different values.It takes into account the impact of particular basic repair operations on properties of the repairedmodel.
In particular, [108] suggests assigning costs to change operations, i.e. the cost of insertion orremoval of a transition related to a specific activity is different and specified upwards. Transitions,which a user consider important, will never be removed from the model or replaced, whereas othertransitions can be added or removed. This is useful, for example, when some activities are criticalin the process, and an absence of the corresponding events in the event log means incorrect loggingrather than process change.In such a formulation, the Petri net repair problem is reduced to an optimization problem.The approach investigates the space of all possible repairs which are encoded as sets of basic(add/remove) repair operations.
The authors have proposed and evaluated a set of algorithmswhich can seek optimal (w.r.t. assigned costs for repair operations) repairs. A large number ofexperiments have been conducted to select the most efficient optimisation algorithm with suitableparameters.1.3.3Improving Structured Business Process Models using Event LogsOne more contribution to the field of process model repair has been made by J. Buijs et al.
[109]This is an incremental re-discovery technique which is based on the following genetic principle.Processes are modelled using well-structured process models (process trees [67, 110]). Thesemodels are improved w.r.t. the balanced complex criterion based on four classical quality metrics:fitness, precision, generalization, and simplicity. Authors have used a special genetic algorithm, inwhich, along with the classic quality metrics, they calculate a similarity between the discoveredmodel and the initial one.The approach works as shown in Figure 1.22. It accepts an event log and, optionally, a set ofreference process trees.
Input models are evaluated according to a specified quality criterion thatis a weighted combination of the four classic quality metrics. Then, the iteration starts. At thebeginning of each iteration, the algorithm evaluates predefined stop criteria (again, it is a weighted44combination of classic quality metrics). If it has been decided to proceed, the models are changedusing basic change operations, and the next population of models is produced. Afterwards, thebest models with the highest score of the quality criterion are selected from the whole population.These best members of the population are transferred to the next iteration.EliteNewGenerationChangeSelectedNoProcess TreesSelection CriterionCalculatorInputEvent LogReference Process ModelsStop ?YesResult Process ModelFigure 1.22: Genetic model improvement technique of J. Buijs et al.
[109]In other words, the algorithm implements a typical genetic approach. Additionally, thesimilarity metric is used as a fifth component of the quality criterion. In particular, the robust treeedit distance [111] is measured between the reference model and the models constructed at eachiteration. Then, the constructed model is somehow reflects the balance between the behaviourfrom event log and reference model. Unfortunately, the search of appropriate weights for thecomponents of the quality criterion, which will lead to particular model characteristics, is a ratherdifficult problem.1.3.4Interactive and Incremental Business Process Model RepairA. Armas-Cervantes et al. [112, 113] proposed a significantly different approach. This freshtechnique is called interactive and incremental repair.
Authors consider core BPMN models withbasic control-flow elements (tasks, AND and XOR gateways). The goal is to improve model’sfitness, as earlier. The authors have proposed the following stepwise technique.Firstly, event structures [114] are constructed for both an event log and a process model.Authors show, that the partially synchronized product of these two event structures revealdifferences in the behaviour of a model and a real process presented an event log.
The differencesare indicated as two basic change operations: events can be matched (no change) or hidden (i.e.,skipped in the model or in the log). The authors have proposed the series of matching patternswhich allows for capturing more complex differences consisting of multiple matches and hides.Secondly, after the matching is made, its results are presented to the user. Moreover, theprototype software shows a possible repair for a difference found at the first step.
The role of useris to select a suitable repair operation, when a model fragment is replaced with another one.45Thirdly, the conformance of a changed model and the event log is checked again and the resultis shown to the user. The interactive process repair can be either stopped (if the model sufficesthe fitness criteria), or continued with the other repair technique selected by the user.This technique substantially differs from the others considered in this section.
The repair isperformed on BPMN models, and is made interactively with the user participation. Thus, thetechnique is a semi-automated approach rather than an automatic algorithm.1.3.5Automated Error Correction of Business Process ModelsYet another way to repair business-process models, called Automated Error Correction, hasbeen introduced by M. Gambini et al. [115]. Workflow models are repaired in this paper. Thequality criterion is their soundness [71]. Thus, the goal of error correction is to make the netsound, that is, to remove deadlocks automatically.The combined measure is used for the similarity evaluation a between a repaired and an initialmodels.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
