Диссертация (1137084), страница 16
Текст из файла (страница 16)
Moreover, the entire fragment consisting of the places 8 , end and the silent transition 5 was added to the fragment during the repair only because the67W(SN3)’〈a, d, b, e〉〈a, b, c, e〉〈a, b, c, e, h, d, b, e〉〈a, c, b, e〉dbt4as-startc3τt1c1ts1c2t2c5τττts2ts3ts4c4hcet5c7τts5c8s-endc6t3t8Figure 2.14: Sub-net discovered to replace the enlarged fragment (3 )′cycle through the transition 8 turned out to be divided between several fragments. The repairusing discovery always adds similar fragments, if there are divided cycles. Such fragments add nomeaning to the model, so they can be removed from the model together with additional beginningplaces (-start in our example).dbt4as-startc3τt1c1ts1c2c5c8τττts2ts3ts4c4sourcet2cc7eτt5ts5c6s-endft3t6ht8c9gsinkt7Figure 2.15: Petri net repaired using the improved approachThis section considered the technique of process model repair for the local case, which usesan information from the event log.
It is based on Divide & Conquer principle. The model isfirst divided into fragments with clearly defined borders. Then, the fragments, which do not fitthis event log, are replaced with new ones, constructed by using well-known process discoveryalgorithms. Finally, the repaired model is composed from the fragments.
The model obtained isfairly similar to the initial model, and fits the event log.The method considered can be especially useful in the cases, when the initial model has beendeveloped by an expert, and thus, is well-understood by a human being. A model, discovered fromscratch, can be correct, but unreadable. Our method, however, repairs the model locally and savesits readability.Nevertheless, the proposed method is not universal. It has proved itself in the case of localinconsistencies. In other words, we can repair a model by replacing individual fragments.
Chapter 4considers how proposed techniques (basic and improved) were experimentally evaluated.When fitness inconsistencies are global, the improved technique repairs them, but the resultmodel lacks in precision. Section 2.5 describes the modification of the modular repair applicable68to the non-local cases. In particular, a size of decomposition fragments can be adjusted to coverthe problematic part of the initial model.2.5Non-Local Repair of Process ModelsThis section considers the algorithm for the non-local model repair based on modular scheme.Firstly, the differences between local and non-local inconsistencies are described.
Secondly, thealgorithm for the non-local cases is shown, that employs two fundamental algorithmic paradigms:divide & conquer and greedy processing. The technique decomposes process model and repairs submodels in a greedy way using event logs with actual (normative) behaviour. Using this procedure,it is possible to repair both local and non-local inconsistencies, and save model precise in the localcases.Locality of InconsistenciesIn Section 2.3, the modular technique of model repair has been proposed, that corrects localinconsistencies between a model and an event log.
The weakness of basic modular repair algorithmproposed in Section 2.3 is that it reduces the precision of a repaired model. To cope with thisshortcoming, the improved technique has been proposed in Section 2.4, that joins the fragmentswith their direct neighbours, and then replaces larger fragments. This procedure successfully savesthe precision, but, though, only for the local repairs. In this section, we propose a simple extensionof the improved technique that can cope with the non-local cases and saves precision of the model.Firstly, the local model repair is defined. Let be a workflow net, and be an event log.In Section 2.4, we defined the direct neighbourhood of as (N ) = { ⋃︀ ∈ ∧ ( ) ∩ ( ) ≠ ∅}. Note that the neighbourhood of includes itself.
By ( ) we define theenlargement of fragment , which is constructed of and all its neighbour fragments, that is( ) = ⋃1≤≤ ( (N )).We will call the repair local if for all fragments with inconsistencies all respective events inthe initial event log are in directly follows relation. More formally, for any two transitions and from any fragment such that ( ↾( ) , ) < 1, a trace ∈ can be found, in thatthere is a subsequence ∐︀. . . , , , . . . ̃︀, where either = ( ) and = ( ), or = ( ) and = ( ).This means, that in the local case the needed repair for each inconsistency is just a change offlow relations within a single fragment. When doing the non-local repair, we actually want to“move” the transition from one fragment of a decomposition to another, which is impossible usingthe local repair methods.
In such a case, the repair, which has been proposed earlier, is able tocorrect fitness of a model by replacing transitions within fragments, but reduce the values of otherconformance metrics, including precision.69Figure 2.16 shows these two types of inconsistencies. The local repair methods correct bothinconsistencies in the same way. In particular, the algorithm to fix the fitness problem will changethe fragment with transitions 20 and 21 to allow for enabling the 21 in an arbitrary momentof model execution.
The algorithm has no other ways to fix inconsistency as it deals only withseparate sub-nets. Obviously, such a repair reduces model’s precision.Local:...at1bp1...t2et20dp20...t21<...,a,b,,d,e,...>d...Non-local:...at1bp1...t2et20p20t21<...,a,d,b,e,...>Figure 2.16: Two types of inconsistenciesNote that a locality of inconsistencies depends on the type of decomposition. The sameinconsistencies can be made local or non-local using different decompositions of the same model.This idea we use for the technique of the non-local repair.Greedy Algorithm of Process Model RepairThis section describes the greedy algorithm based on the modular repair technique. Figure 2.17shows the scheme of this algorithm, whereas more formally it is described in Algorithm 2.
In thefigure, the key modification of the repair scheme is highlighted with light-blue colour.The input of this algorithm is a workflow net (see Algorithm 2), which we want to repair,and an event log , which contains the actual (normative) behaviour. The algorithm decomposesthe model using maximal decomposition that has been described in Section 2.3. The set ofsub-logs is calculated using projection based on the decomposition. Then, the technique selectsthe sub-net with the worst fitness to the corresponding sub-log ↾( ) 1 . Then, the iterationstarts. At each step, the sub-net is joined with its neighbours ( ) and replaced by the model,which is discovered using one of the two discovery algorithms placed in procedural parameterdiscover (L ↾A(Nb ) ). Then, the intermediate net ′ is composed and returned.
The algorithmiterates until the perfect fitness is achieved between the intermediate net ′ and the actuallog . Then, it halts. A model ′ is the repaired Petri net.It is easy to see, that the algorithm is an extension of the improved algorithm for the local modelrepair, which enlarges the sub-nets with inconsistencies to save their borderlines. This algorithm1Actually, any unfitting fragment can be selected at the first step, if we correct a model to perfect fitness.70EventLogInputInitialWorkflow netDecompositionProjectionSelectionConformingSub-netsSub-netsSub-logsNon-conformingSub-netsEvaluationSub-logs forNon-conformingSub-netsAll Sub-nets, Some Non-conformingEnlargementAll Sub-nets,ConformingConforming Sub-netsEnlargedSub-netsRepairCorrectedSub-netsCompositionEvaluationEvaluationResultOutputCorrectedWorkflow netFigure 2.17: Non-local process model repairhas been described in Section 2.4.
For the improved algorithm we proved, that it guarantees aperfect fitness of repaired model. The same can be easily shown for the greedy algorithm.Indeed, at the first step we have a maximally decomposed net, which perfectly fits the log ifand only if each sub-net perfectly fits the corresponding sub-log. At each step we enlarge one of thesub-nets by joining it with neighbour sub-nets. The decomposition at each step is valid, becausethe decomposition at the first step was valid and the enlargement does not destroy its validity, asit has been show in Section 2.4.
Then, there are two possibilities: the iteration stops either whenall unfitting sub-nets are joined in a singe sub-net and replaced with the perfectly fitting sub-net,or all sub-nets are joined and the repair is reduced to a discovery of completely new model. Inthe first case, a problem is formulated as it has been done in Section 2.4. The second case is theworst one, but the algorithm still returns a perfectly fitting model, because a discovery algorithmis used which guarantees a perfect fitness.The particular example of greedy repair is shown in Figure 2.18. The model contains twounfitting fragments, which are highlighted with dark colouring. In particular, the labels of two71Algorithm 2 Greedy process model repair algorithm1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:Input: initial workflow net , event log ;Output: repaired Petri net ′ .Function greedyRepair(, ) ← ( ); ← argmin ( ↾( ) , ); ∈′ ← ;Repeat( ′ , ) ← greedyRepairStep( ′ , , , );Until fitness(, ′ ) = 1;return ′ ;EndFunctionFunction greedyRepairStep( , , , ) ← ( );′ ← ( ↾( ) ); ′ ← ( ∖ ( ) ∪ ′ );return ( ′ , );EndFunctiontransitions were swapped between these fragments.
The greedy algorithm started from the one ofthem and performed nine iterations of a sub-net enlargement. Finally, the whole highlighted partof the model should replaced with a newly discovered model.443536759845328546789Iterations:111237234567898These fragments do not fit the logFigure 2.18: Processing of the model with two unfitting fragmentsNote that eight iterations are sufficient to repair the model up to a perfect fitness, but thealgorithm may be forced to perform an additional ninth iteration as shown in Figure 2.18. Thisiteration guarantees the stability of a borderline between a replaced fragment and the remainderof the model. Otherwise, a precision of the repaired model can be reduced because of borderlinechange during repair.In this section, a greedy algorithm for process model repair using event logs has been described.This algorithm is based on two fundamental algorithmic paradigms: divide & conquer and greedyprocessing.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
