Диссертация (1137084), страница 33
Текст из файла (страница 33)
This model can replay all behaviour from the event log 2 , but it allows formany more process variants. One may note lots of additional silent transitions and places, copiedtransitions in all parts of the repaired model.Figure 4.46: Model LM2-BL-3 repaired using the Model Repair plug-in with settings alignsub-logs and compute global cost functionCompare this model with the model re-discovered from 2 using Inductive miner (seeFigure 4.9).
The repaired model is more precise, as it contains no flower fragments. But, it is verystructurally complex, and the repetition of transition labels is high in it, whereas re-discoveredmodel have no such problems.SummaryThis section considered experiments with local process model repair using the modulartechnique. Each repair have been evaluated using two process discovery algorithms, whichguarantee perfect fitness of a repaired model, namely inductive (Ind) and integer linearprogramming (ILP) algorithms (or miners).Table 4.8 summarizes characteristics of models which are repaired using the three mainapproaches: (1) a model re-discovery from scratch (using the normative event log only), (2) thenaive technique (see Section 2.3), and (3) the improved model repair technique (see Section 2.4).The model name is in the first column.
Then, there are two columns — Method and Discovery.The first one indicates the model repair method — naive or improved. This column can alsocontains word Discovery for the rows which show characteristics of models completely rediscovered from event logs 1 (for models SM1) and 2 (for models LM2). A column Discoveryindicates employed process discovery method (Inductive or ILP miner).Fitness and Precision columns show the corresponding characteristics which are calculatedusing algorithms described in Section 1.2.2. These results already discussed above.The Sim. column contains similarity evaluation results calculated using ProM 6 plugin Calculate Graph Edit Distance Similarity [131]. In turn, this plug-in is based on thetheoretical background presented by R.
Dijkman et al. [185] This method returns a numberbetween 0 (models are completely different) and 1 (models are equal).Note that this plug-in takes into consideration not only the structure of both models but alsonode labels. Because of that, for example, similarity between models repaired using the ProM 6Model Repair plug-in and related initial models is very low. During repair, the plug-in copies144Table 4.8: Process model repair in the local casemany existing transitions and adds pluses to their labels. Besides, new transitions, places, andsilent transitions are added to the model.Thus, this similarity measure is not very convincing, and another method to measure similarityis used in this thesis.
In particular, the number of total decomposition sub-nets is calculated, thenumber of sub-nets which are replaced during repair, and the number of nodes in these sub-nets.The number of changes in the model during repair procedure can be easily estimated using thesenumbers. Indeed, a repair technique that touches 3 nodes of 100, changes 0,03 of an initial modelstructure.The N-f column shows the overall number of fragments (sub-nets) in model decomposition.
Anumber of sub-nets with inconsistencies is shown in N-bf column. These fragments are changed(replaced/repaired) during the repair. One can find the number of nodes (both places andtransitions) in each model in the Size column, whereas the column Ch. indicates the size (number145of nodes) of all changed fragments. For example, when repairing the model SM1-BL-1 a naive modelrepair changes only 1 fragment of 19, and this change influence on 3 nodes of 40, and all incidentarcs of these three nodes. This column is the most interesting for us as it shows how model repairinfluences on a repaired model.For each experiment we calculated its duration in milliseconds. It is show in the column Time.Note that to conduct the experiments the following test configuration has been used: centralprocessing unit Intel Core i7-3630QM with a clock rate of 2.40 GHz ; 4 Gb of a random accessmemory; Windows 7 x64 operating system; and traditional HDD drive.
The system configuration isnot of top-level productivity. Thus, results can be sufficiently better using more powerful machines.However, we understand the relativity of such calculation.Each row Initial model shows the characteristics of a model which we try to reconstruct bythe repair (recall the scheme of experiment in Figure 4.5).Results of experimental evaluation of the modular repair technique in local case are as onemay expect.
Table 4.8 shows that the naive algorithm provided perfectly fitting models, but withsignificantly reduced precision. Moreover, in some cases the behaviour of the model is so diversethat the available 4 Gb of RAM is not enough for conformance checking algorithms to successfullyfind optimal alignments, or calculate the fitness/precision between an event log and a relatedmodel. These are cases, when a repaired model contains many silent transitions, and transitionswithout input places.
In such cases, the number of possible combinations which should be checkedby alignment-based conformance checking or graph edit distance algorithms is very large, andemployed ProM 6 plug-ins failed. If so, we put the letter f in a corresponding table cell. Whenthe improved method has been applied, the repaired models are as precise as initial models.In all considered examples a changed fragment is a small part of the model. In particular, whenrepairing the model LM2-BL-3 we change 2 of 63 fragments, which together contain 21 transitionsand places of the 133 nodes in the model.
Results in Table 4.8 are calculated with removing ofsource and sink places in replaced fragments, as it is described in Section 2.3. These results alreadyhas been discussed above.Note that model repair using the ILP algorithm is significantly faster for considered examples,than the re-discovery of a completely new model using ILP miner, even taking into account thetime spent on decomposition and additional fitness checks.
This result is expected for such poorlyscalable algorithms. As one may expect, in most cases a model repair using ILP miner is slowerthan using Inductive miner. However, this is not always the case. When the Inductive algorithmis used, a model repair is expectedly slower than a complete re-discovery due to the additionaloverhead.However, the main contributor to the whole repair time is an alignment-based conformancechecking.
Finally, repair times (including decomposed fitness evaluation to select unfittingfragments) are acceptable for the technique to be applied in practice. Thus, an effectivenessoptimization is not our goal for now.146Concrete settings of the used process discovery and conformance checking algorithms canchange the repaired model. For example, one can set different costs for nonconformities inalignment-based conformance checking (A. Polyvyanyy et al. investigated how it can be done[108]). Then some nonconformities can be ignored.
It is a responsibility of an expert-user toproperly configure employed repair techniques.In Chapter 2, we have described the model repair procedure using the small model shown inFigure 2.2 as example. This model is suitable for reasons of clarity, but the replaced fragmentin this case — especially when the improved technique is used — includes most of the model.The feature of the modular repair is as follows: as smaller is the changed fragment as higher theeffectiveness of the modular technique.Recall the larger repaired models.
Figure 4.47 shows how the approach deals with the test modelLM2-BL-3. A fragments affected by the repair are highlighted. Note that actually we replace twodisjoint net fragments in this case. All changes are located in these relatively small sub-nets. Theremaining part of the model remains untouched.Figure 4.47: Model LM2-BL-3 repaired using the improved techniqueFor comparison, Figure 4.48 shows the model which has been automatically discovered from theevent log using Inductive miner with zero noise threshold. This model is completely different incomparison with the initial model LM2 (see Figure 4.6). The model re-discovered using ILP minerdiffers even more (see Figure 4.10).Figure 4.48: Model discovered from scratch using the Inductive miner from the event log 2generated using the LM2 modelNaive and improved algorithms of model repair are not all-purpose.
In the remainder of thischapter, we show the results for a non-local case.1474.3.2Non-Local Process Model RepairAbove results of local process model repair has been presented. This section considers hownon-local cases can be repaired using repair techniques from Chapter 2.Model SM1-BNL-1The first example SM1-BNL-1 is shown in Figure 4.49. Labels of two transitions 0 and 20 arereplaced in this model. Because of this inconsistency its fitness with respect to the event log 1 is0,84.
At the same time, this model is relatively precise, that can be estimated as 0,91.Figure 4.49: Changed model SM1-BNL-1In this case, the naive repair technique produces very imprecise models. For example,Figure 4.50 shows the model repaired using the ILP miner. Note transitions 1 , 2 , 0 withoutincoming arcs, and transitions 20 , without outgoing arcs. Actually, these transitions supportthe fitness of the repaired model. Obviously, they significantly reduce its precision. Usually, sucha repair is not what a user wants. Thus, in non-local cases the naive repair technique is not thebest choice.Figure 4.50: Model SM1-BNL-1 repaired using the naive algorithm with ILP minerFigures 4.51 and 4.52 illustrate the repairs made by the improved technique. Still, there aretransitions without incoming or outgoing arc in both repaired models.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
