Диссертация (1137084), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Figure 4 shows agraphical representation of this scheme. Building blocks are highlighted using bold frames.EventLogInputInitialWorkflow netDecompositionProjectionSelectionSub-netsConformingSub-netsSub-logsNon-conformingSub-netsCompositionSub-logs forNon-conformingSub-netsCorrectedSub-netsRepairEvaluationEvaluationResultOutputCorrectedWorkflow netFigure 4: Modular repair schemeThe input to the scheme is a couple (, ), where is a correct (normative, trusted)event log, and is a non-conforming initial model.

The model is decomposed into severalfragments 1 , 2 , . . . , using one of the model decomposition algorithms. In the projectionblock, an algorithm splits the event log into sub-logs 1 , 2 , . . . , which correspond to model fragments (sub-nets). The selection block contains a conformance checking algorithm. Thisalgorithm calculates the conformance value for each pair ( , ), where = 1, 2, . . . , . Accordingto the corresponding conformance value, all model fragments are separated into two sets. Thefirst one contains conforming (good ) fragments.

The second one consists of sub-nets which do notconform to corresponding sub-logs (bad fragments). The repair block contains an algorithm whichreplaces non-conforming model fragments by conforming ones. The composition block is pairedwith the decomposition one. The result of repair can be evaluated in the evaluation block by usinga conformance checking method, or another approach.This general scheme can be defined more formally, as it is done in the following definition.Definition (Modular Repair Scheme). Let denote the universal set of activities, and N bethe set of all WF-nets with transitions labelled over .14We define the modular repair scheme as a procedure, which takes an event log ∈ ℬ(∗ )and a labelled WF-net N ∈ N as its input, and returns a Petri net N r = ModularRepair (, N )perfectly fitting the log , i.e. (,N r ) = 1, as a result.The procedural parameters in the modular repair scheme are the following:– eval ∈ (ℬ(∗ ) × N ) → (︀0; 1⌋︀ is an evaluation function,– repair ∈ (ℬ(∗ ) × N ) → N is a repair algorithm,– split ∈ N → (N ) is a decomposition algorithm,– compose ∈ (N ) → N is a composition algorithm.Usually, fitness is considered as the main conformance criterion when doing process mining.Indeed, no one needs a model that does not reflect an observed behaviour of the system analysed.Thus, we also consider fitness as the major criterion.

Then, we formulate the perfect fitness repairconditions.Definition (Perfect Fitness Repair for Workflow Nets). Let ∈ ℬ(∗ ) be an event log with ⊆ ,and let N ∈ N be a workflow net such that fitness(, N ) < 1. Let N ′ = ModularRepair (, N ) be amodular repair scheme. ModularRepair (L, N ) is a perfect fitness repair if fitness(, N ′ ) = 1.The modular repair technique guarantees perfect fitness of a repaired model, if a perfectdiscovery algorithm5 is used in the repair building block, and a valid decomposition algorithm isemployed to decompose the model.

By definition, perfect discovery algorithms construct a perfectlyfitting process model for any event log. A decomposition is valid if it successfully decomposes bothmodel and its marking, and allows for an unambiguous composition.Theorem (Perfect Fitness Repair Conditions). The modular repair scheme ModularRepair (L, N )ensures perfect fitness if1. split is a valid decomposition function;2.

repair is a perfect discovery function, i.e. for any event log it returns a Petri net, whichperfectly fits this event log;3. compose is a transition fusion function that merges all transitions with the same labels.The proof of this theorem presented in Chapter 2.Then, we describe the algorithm that employs concrete procedural parameters as buildingblocks of the general modular scheme.We assign the procedural parameters in the modular repair scheme as follows:5These algorithms always discover perfectly fitting models.15– evaluation function eval ∈ (ℬ(∗ ) × N ) → (︀0; 1⌋︀ is the alignment-based fitness checkingalgorithm [22],– model repair function repair ∈ ℬ(∗ ) × N ) → N is the inductive process discoveryalgorithm [23], or the integer-linear-programming-based discovery algorithm [24],– decomposition function split ∈ N → (N ) is the maximal decomposition algorithm,– composition function compose ∈ (N ) → N is the algorithm based on fusion oftransitions with the same labels.This gives us the decomposed repair algorithm.

In this chapter, we show that this repairalgorithm satisfies the perfect fitness repair conditions 1, 2, and 3.To implement the repair algorithm, we need to be able to decompose Petri nets maximally.Thus, we propose an algorithm to calculate maximal decomposition of a Petri net. It is presentedin Chapter 2.Figure 5 shows a maximal decomposition of the process model shown in Figure 3. The netis decomposed into six net fragments: 1 , 2 , 3 , 4 , 5 , and 6 .

All transitions inthe initial model are observable and have unique labels. Thus, transitions 1 (a), 2 (b), 3 (c),4 (d), 5 (e), 6 (f), 7 (g), and 8 (h) are borderline nodes. Inner nodes are places , 1 ,2 , 2 , 3 , 4 , and . One may see how the initial marking is split: the single token moves withthe place in the sub-net 1 .

It is easy to see, that fragments can be composed into theworkflow net shown in Figure 3 via a fusion of transitions with the same labels.SN5hSN2hSN1sourceaat1t1c1t8SN3cSN4cbbt3t3t2t2c2ddt4t4t8c3eet5t5c4fSN6ft6t6ggt7t7sinkFigure 5: Maximal decomposition of the model from Figure 3We call this repair method the naive modular repair technique. Figure 6 shows how the modelfrom Figure 3 can be repaired using this repair algorithm, if the event log consists of two traces:∐︀, , , , ̃︀ and ∐︀, , , , ̃︀.Repairs of the naive technique are not perfect hence such models are imprecise. That is whythe procedure greatly increases the number of possible model runs.

The chapter contains detaileddiscussion of the reasons for this precision reduction. In order to cope with this shortcoming ofthe naive repair technique, we propose the improved repair algorithm.The key idea is to enlarge each fragment-to-repair so that the repair procedure will not affectborderline transitions of enlarged fragments.

Figure 7 demonstrates attaching neighbours to the16hft8asourcecbt1t2c1et3s3t6t5c3gc4ττts1sinkt7ts2s2dt4Figure 6: Process model from Figure 3 repaired using the naive techniquefragment 3 in the example net. This sub-net has two neighbours, namely 2 and 4 , to beattached.W(SN3) SN5hSN2hsourceSN3t8SN1aat1t1c1bbt2t2c2cSN4ct3t3ddt4t4t8c3W(SN3)cSN1sourceaat1t1t3bc1t2c2dc3eet5t5c4fSN6ft6t6ggt7t7sinkSN5hht8t8eet5t5c4t4fSN6ft6t6ggt7t7sinkFigure 7: Neighbours are attached to the sub-netWe define an enlarged fragment (N ) for N as a fragment obtained by attaching to N all its neighbours, i.e. (N ) = N ∪ (N ).

Here (N ) = {N ⋃︀ N ∈ ∧ ∩ ≠ ∅}, and, ∈ {1, 2, . . . , }.The procedure of fragment enlargement is applied when there are more than one unfittingfragment in model decomposition. It can be defined as follows.Definition (Sub-net Enlargement Procedure). Let = {N 1 , . . . ,N n } be a decomposition of aworkflow net , and = ∪ , where is a set of unfitting net fragments, and is a set ofother fragments. Obviously, ∩ = ∅.

The fragment enlargement procedure consists of thefollowing steps:1. Each fragment from is extended by attaching its neighbours: ∀N ∈ : = (N ), = (N ); = ⋃ is a set of all enlarged fragments, and = ⋃ is a set of allfragments which were affected by the procedure, where = 1, 2, . . . , ; note that fragments canhave common neighbours;172. All affected fragments are removed from the initial decomposition = ∖ ;3. The new decomposition includes enlarged fragments: N= ∪ .We have shown that the enlargement procedure can be added to the modular repair technique,because it keeps a decomposition valid. This is formulated in the following theorem (Chapter 2).Theorem (Sub-net Enlargement Preserves Decomposition Validity).

Let N = {N 1 , . . . ,N n } ∈(N ) be a valid decomposition of a net . Let Nbe an enlarged decomposition in which twofragments are combined, that is ∃, such that 1 ≤ < ≤ and N= { ∪ } ∪ N ∖ { , }.Then Nis a valid decomposition, i.e. N∈ (N ).The proof of the theorem is in Chapter 2.We call this advanced algorithm with a sub-net enlargement the improved modular repairtechnique. A model repaired using this technique is more precise (see Figure 8) when repairinglocal inconsistencies.dbt4as-startc3τt1c1ts1c2t2c5c8τττts2ts3ts4c4sourcecc7eτt5ts5c6s-endft3t6ht8c9gsinkt7Figure 8: Process model repaired using the improved techniqueIn a local case, the repair needed for each inconsistency is just a change of the flow relationswithin a single model fragment. When repairing non-local inconsistencies, we actually need to“move” the transition from one fragment to another, which is impossible using local repair methods.In such a case, naive and improved repair techniques can be used to repair the fitness of a model.However they reduce the values of other conformance metrics, including precision.

Характеристики

Список файлов диссертации