CN106021642A - Reachable identification based process model repairing method - Google Patents

Abstract

The invention discloses a process model restoration method based on reachable marks. The process model repair method firstly proposes extensions to the calibration, adds the reachable marks of the Petri net, proposes the concept of extended calibration, and attempts to calibrate through the extended To identify the various types of extended actions that may occur. The optimal extended calibration can provide support for the repair of various deviations. By separately analyzing the extended log action and the extended model action, the present invention proposes algorithms to repair these two types of deviations. A simulation experiment of this method was carried out through the event log of the Thoracic Surgery Department of a certain hospital, and it was found that the method of the present invention has improved accuracy and generalization. Compared with existing methods, the method of the present invention has better performance in each dimension.

Description

A Process Model Restoration Method Based on Reachability Mark

technical field

The invention relates to a process model restoration method based on reachable marks.

Background technique

Process mining was proposed by R.Agrawal et al. in 1998. At present, the definition of process mining recognized internationally is "process mining refers to the methods for extracting structured process descriptions from actual execution sets".

There are three types of applications of process mining technology: process discovery, conformance checking and process enhancement. The goal of process discovery techniques is to construct a process model from event logs. When constructing a process model, the control flow dimension is mainly considered. Consistency detection is to compare a known process model with the event log of this model to check whether the actual situation recorded in the log conforms to the model. The idea of process enhancement is to extend or improve an existing process by using the event log generated by the actual process. Unlike consistency detection, the third process mining scenario aims at improving and extending known models.

The "good or bad" of the process model needs to be evaluated through different aspects. The main evaluation criteria are: fitness, precision, simplicity and generalization. Among them, the degree of fit is the most important index for process model evaluation. A model with an excellent fit means that the model is able to reproduce all the traces in the log. High accuracy means that the model will only replay the events in the event log, simplicity means the best model is the simplest model that can explain the behavior seen in the log, and generalization means whether the model can allow future behavior .

In terms of consistency detection and process enhancement techniques, the biggest challenge at present is to perform replay on the process model to find the optimal path of the behavior observed in the event log.

The event log-based calibration method given in the prior art can not only replay the event log, but also solve problems such as repeated transitions, invisible transitions, complex control flow and loops during the replay process. In addition, for deviations in the process model, calibration can also find out where the deviations occur and provide diagnostic information for the deviations. Furthermore, by assigning different degrees of severity to different deviations, calibration can be used to implement analysis from different angles.

By calibrating the event log, various deviations in the log can be found. How to repair the deviation in the calibration so that it can be better reproduced in the process model has gradually become the focus of attention. Model restoration technology is a new application technology of process mining, which belongs to the category of process enhancement. Model repair takes event log and process model as input. If the traces in the event log cannot be reproduced in the process model, the process model needs to be modified. The modified model should be as similar as possible to the original model, that is, the basic structure of the original model should not be changed.

There exist methods that use edit distance matrices to discover improved models, which is consistent with the goal of inpainting models, but is not a model inpainting technique. Based on the deviation of the model and the log to repair the model, at present, there are not many existing methods. Although a model repairing method is proposed in the prior art, the model repairing method uses calibration to discover the deviation of the model and the log to pass the calibration, and then repairs the model. However, this model repair method mainly focuses on the dimension of fit, and lacks consideration for other dimensions such as simplification and accuracy. Under this background, the present invention comprehensively considers the indicators of each dimension, and then repairs the process model.

Contents of the invention

Aiming at the above-mentioned technical problems in the prior art, the present invention proposes a method for repairing a process model based on reachable marks, which facilitates repairing the process model by comprehensively considering the above dimensions.

In order to achieve the above object, the present invention adopts the following technical solutions:

A method for repairing a process model based on reachability identification, characterized in that it includes the following steps:

a parameter definition

Define traces and event logs

Assume is the activity set, the trace σ∈A* is the activity queue, and the event log L is a multiple set of traces, that is, L∈1B(A*);

Defining Petri nets

The quadruple PN=(P, T; F, M) is called a Petri net PN if and only if:

(1) N=(P, T; F) is a network, wherein, P is a finite place set, T is a finite transition set, is a finite arc set;

(2) M:P→N is called an identifier of the network PN, where m _i is the initial identifier, and m _f is the termination identifier;

(3) PN has the following transition rules:

(a) For transition t∈T, if Then the transition t is said to be enabled under the mark M, denoted as M[t>;

(b) If M[t>, then under the label M, the transition t can occur, and a new label M' can be obtained from the transition t triggered by the label M, which is denoted as M[t>M', and for

In the definition of Petri net ^, t represents the input set of t ^, t represents the output set of t, M(p) represents the identity at place p, and M′(p) represents the position at place p after triggering transition t logo;

define calibration

γ∈(A ^>> ×T ^>> )* is the calibration between the trace σ and the model PN if and only if:

(1) π ₁ (γ) _↓A = σ, that is, the movement sequence in the trace produces this trace;

(2) That is, the sequence of moves in the model produces a complete sequence of occurrences;

where Γ _σ,PN is the set of all calibrations between the trace σ and the model PN, π ₁ (γ) _↓A represents the first element in the calibration, and π ₂ (γ) _↓T represents the second element in the calibration;

There are three types of actions in calibration: synchronous actions, log actions, and model actions; among them,

Synchronous actions refer to actions that occur in both the trace and the model, log actions refer to actions that occur in the log but not in the model, and model actions refer to actions that occur in the model but not in the log;

Define Optimal Calibration

The function lc:A ^>> ×T ^>> →IR is the likelihood cost function of the calibration, the calibration γ∈Γ between the trace σ and the model PN _σ,PN is an optimal calibration if and only if any calibration γ'∈Γ _σ,PN : Σ _(a,t)∈γlc ((a,t))≤Σ _{(a',t')∈γ'lc} ((a',t'));

where Γ _σ,PN,lc is the optimal calibration set between the trace σ and the model PN when the possibility cost function is lc, and Σ _(a,t)∈γ lc((a,t)) denotes the calibration γ The possible next generation value of , Σ _{(a',t')∈γ'} lc((a',t')) represents the possible cost value of calibrating γ';

Define an extended move queue

β∈(A ^>> ×T ^>> ×M)* is the extended movement queue between trace σ and model PN if and only if:

(1) π ₁ (β) _↓A ≤ σ, that is, the movement of the extended mobile queue in the trace is the prefix of the trace σ;

(2) There is a complete occurrence sequence Have That is, the movement of the extended movement queue in the model is the prefix of the complete occurrence sequence;

in, Represents a complete sequence, T* represents a finite queue under the transition set T;

(3) m _i [π ₂ (β) _↓T >m, that is, the movement m∈R(m _i ) of the extended mobile queue in the model;

For the triplet (a, t, m) ∈ β in the extended mobile queue, there are the following extended actions:

(1) If a∈A and t=>>, it is called an extended log action;

(2) If a=>> and t∈T, it is called an extended model action;

(3) If a ∈ A and t ∈ T, it is called an extended synchronous action;

(4) Other types are called illegal extension actions;

The definition of the extended calibration is given further by the definition of the extended mobile queue:

Define Extended Calibration

The extended calibration β is an extended mobile queue between the trace σ and the model PN if and only if:

(1) π ₁ (β) _↓A = σ, that is, the movement of the extended mobile queue in the trace is this trace σ;

(2) That is, the movement of the extended movement queue in the model is a complete occurrence sequence;

(3) m _i [π ₂ (β) _↓T >m _f , that is, after the movement of the extended movement queue in the model occurs, it will eventually reach the termination mark,

where B _σ,PN is the set of all extended calibrations between the trace σ and the model PN; where π ₁ (β) _↓A represents the mapping of the first element in the calibration on the active set A, and π ₂ (β) _{↓ T} represents the mapping of the second element in the transition set T in the calibration;

Define Optimal Extended Calibration

An extended calibration β∈B _σ, PN between the trace σ and the model PN is an optimal extended calibration if and only if any extended calibration β'∈B _σ,PN : Σ _{(a,t,m)∈βlc} ( (a,t))≤Σ _{(a',t',m')∈β'} lc((a',t'));

where B _σ,PN,lc is the optimal extended calibration set between the trace σ and the model PN when the likelihood cost function is lc;

c bias fix

Define extended event logs and extended trace sets

For event log L, fitness(L, PN) = 1, event log L' is an extended event log if and only if:

(1) L'∩L=L;

(2)

(3) 0<fitness(L',PN)<1;

For the new trace after expansion, its set PA=L'-L is called the extended trace set;

Among them, fitness(L, PN) represents the fitting degree of the event log L under the model PN, and fitness(L', PN) represents the fitting degree of the event log L' under the model PN;

c.1 extended log action fix

Define log action bias set

Let the optimal extended calibration set Β _{L, PN, lc} be the optimal extended calibration set based on event log L and Petri net PN, given a place p, MLS is the log action deviation set, if and only if:

$\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; L</span>}\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \{</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}{\mathrm{<span\; class="notranslate">\; and\&pi;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; ></span><span\; class="notranslate">\; ></span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; ;</span>$

Collect the log action of the specified library, the steps are as follows:

Step1: input optimal extended calibration set Β _{L, PN, lc} and designated place p, traverse the entire optimal extended calibration set Β _{L, PN, lc} ;

Traverse the calibration β _i in the optimal extended calibration set, and perform the following operations during the traversal:

1) If there exists β _i [j..k]∈β _i , for There m _l (p)=1, andπ ₂ (β _i [l])=>>, then L←L∪γ _i [j..k];

Among them, β _i [j..k] represents some elements in β _i , and j and k are used to determine the range; β _i [l] represents an element of β _i , and m _l (p) represents the identity of m _l in the place the value at p;

2) If there is no extension sequence conforming to 1), then jump to Step1;

Step2: After traversing all the calibrations in the optimal extended calibration set Β _{L, PN, lc} , output the log action deviation set MLS;

To repair the log action of the extended log, the specific steps are as follows:

Step1: Input the log action deviation set MLS and the specified place p, use the InductiveMiner algorithm to mine the log action deviation set MLS, and set PN’←InductiveMiner(MLS);

Step2: For all transitions t belonging to the posterior set of m _i ', perform the following operations:

1): Add the arc (p, t) to the arc set F of the original model PN;

2): Delete the arc (m _i ', t) from the arc set F' of the mining model PN';

Step3: For all transitions t belonging to the previous set of m _f ', perform the following operations:

1): Add the arc (t,p) to the arc set F of the original model PN;

2): Delete the arc (t, m _f ') from the arc set F' of the mining model PN';

Step4: Delete the initial place m _i ' and the termination place m _f in the place set P' of the mining model PN', and add all elements of the place set P' to the place set P of the original model PN ;

Step5: Add all elements of the place set T' to the place set T of the original model PN;

Step6: Add all elements of the place set F' to the place set F of the original model PN;

Step7: Output model PN;

c.2 Repair the model action of the extended log, the specific steps are as follows:

Step1: Input the calibration β and the position i where the model action appears, and add the invisible transition τ to the transition set of the original model PN;

Step2: For all places p belonging to the previous set of π ₂ (β[i]), perform the following operations:

1): Add the place p to the place set P of the original model PN;

2): Add the arc (p, τ) to the arc set F of the original model PN;

Step3: For all places p belonging to the back set of π ₂ (β[i]), perform the following operations:

1): Add the place p to the place set P of the original model PN;

2): Add the arc (τ, p) to the arc set F of the original model PN;

Step4: Output model PN.

The present invention has the following advantages:

The present invention firstly proposes an extension to the calibration, adds the reachability mark of the Petri net, proposes the concept of the extended calibration, and attempts to identify various possible extended actions through the extended calibration. The optimal extended calibration can provide support for the repair of various deviations. By separately analyzing the extended log action and the extended model action, the present invention proposes algorithms to repair these two types of deviations. A simulation experiment of this method is carried out through the event log of the Thoracic Surgery Department of a certain hospital, and it is found that the present invention has improved accuracy and generalization. Compared with the existing methods, the present invention has better performance in each dimension.

Description of drawings

Fig. 1 is the model schematic diagram of Petri net among the present invention;

Fig. 2 is the extended calibration schematic diagram of the trace based on Petri net among the present invention;

Fig. 3 is a schematic diagram of optimal extended calibration of all traces in the event log L based on Petri net in the present invention;

Fig. 4 is the restoration sketch map of log action in the present invention;

Fig. 5 is the extended calibration schematic diagram of the trace based on Petri net among the present invention;

Fig. 6 is a schematic diagram of repairing model actions in the present invention;

Fig. 7 is the Petri net model schematic diagram of certain hospital thoracic surgery in the example of the present invention;

Fig. 8 is the schematic diagram of the Petri net model after the repair of a certain hospital thoracic surgery in the example of the present invention.

detailed description

The basic idea of the present invention is: the present invention attempts to restore the process model by comprehensively considering the above dimensions. Calibration can replay the event log and find various deviations, namely log actions and model actions, but cannot determine where the deviations appear in the Petri net. Therefore, the present invention proposes the concept of extended calibration based on the reachability mark of the Petri net , so that the location of the deviation can be determined. Furthermore, the present invention proposes algorithms for repairing log actions and model actions that appear in the extended calibration. Finally, the experiment proves that the restoration algorithm has better performance in each dimension.

Below in conjunction with accompanying drawing and specific embodiment the present invention is described in further detail:

A method for repairing a process model based on reachability identification, which includes the following steps:

1. Parameter definition

Define traces and event logs

Assume is the activity set, the trace σ∈A* is the activity queue, and the event log L is a multiple set of traces, namely

Petri net is a directed bipartite graph including places and transitions.

Defining Petri nets

The quadruple PN=(P, T; F, M) is called a Petri net PN if and only if:

(1) N=(P, T; F) is a network, wherein, P is a finite place set, T is a finite transition set, is a finite arc set;

(2) M:P→N is called an identifier of the network PN, where m _i is the initial identifier, and m _f is the termination identifier;

(3) PN has the following transition rules:

(a) For transition t∈T, if Then the transition t is said to be enabled under the mark M, denoted as M[t>;

(b) If M[t>, then under the label M, the transition t can occur, and a new label M' can be obtained from the transition t triggered by the label M, which is denoted as M[t>M', and for

In the definition of Petri net ^, t represents the input set of t ^, t represents the output set of t, M(p) represents the identity at place p, and M′(p) represents the position at place p after triggering transition t logo;

Taking a process model as a reference, the activity does not deviate from the model during its execution, which means that the activity is allowed by the model in its current state. That is, given an event log without any bias, activities are executed exactly in the order of the model. Based on this idea, the concept of calibration is given in the prior art to compare the activities in the event log with the activities on the model. Obviously, an instance of a process model cannot directly affect other instances of the same process. So, for calibration, there is one calibration per instance.

define calibration

γ∈(A ^>> ×T ^>> )* is the calibration between the trace σ and the model PN if and only if:

(1) π ₁ (γ) _↓A = σ, that is, the movement sequence in the trace produces this trace;

(2) That is, the sequence of moves in the model produces a complete sequence of occurrences;

where Γ _σ,PN is the set of all calibrations between the trace σ and the model PN, π ₁ (γ) _↓A represents the first element in the calibration, and π ₂ (γ) _↓T represents the second element in the calibration;

There are three types of actions in calibration: synchronous actions, log actions, and model actions.

Synchronous actions refer to actions that occur in both the trace and the model, log actions refer to actions that occur in the log but not in the model, and model actions refer to actions that occur in the model but not in the log.

Given a trace and a Petri net, multiple calibrations may exist. In the actual process, the possibility of deviation will have different effects according to the different activities and different artificial formulations. For example,

It can be considered that the bias produced by the log action is larger than the bias produced by the model action. In order to be able to produce the most probable alignment, it is necessary to assign a likelihood cost to each move. In the present invention, for the log action and the model action, the possibility cost value is 1, and for the synchronous extension action, the possibility cost value is 0. According to the established possible cost value, the calibration with the lowest possible cost value can be found, and this kind of calibration is called the optimal calibration.

Define Optimal Calibration

Let the function lc:A ^>> ×T ^>> →IR be the possibility cost function of the calibration, the calibration between the trace σ and the model PN γ∈Γ _σ,PN is an optimal calibration if and only if: γ'∈Γ _σ,PN : Σ _(a,t)∈γlc ((a,t))≤Σ _{(a',t')∈γ'lc} ((a',t'));

where Γ _σ,PN,lc is the optimal calibration set between the trace σ and the model PN with the likelihood cost function lc.

Calibration and optimal calibration can correlate event logs with process models, and optimal calibration can handle invisible transitions in process models, complex control flows and loops, etc. Calibration can show where deviations occur when they occur and provide diagnostic information for further investigation. The likelihood cost function provides a measure of severity for calibration.

2. Extended Calibration

Process model repair belongs to the specific application of process enhancement, and its idea is to use the event log generated in the actual process to extend and improve an existing process model. Calibration can replay the event log and find various deviations, that is, log actions and model actions, but it cannot determine where the deviations appear in the Petri net. Therefore, the present invention expands the calibration by introducing reachable marks to determine where the deviation occurs. Then it is possible to repair the deviation at the corresponding position.

Process model restoration requires an evaluation index, and the fitting degree is the most important evaluation index of the process model. For the convenience of description, the present invention uses fitness(L, N) to represent the fitting degree of the event log L under the model N.

For other indexes, it should be considered under the condition of ensuring high fitting degree as much as possible, so the present invention makes the process model have better accuracy and simplification while ensuring high fitting degree.

In order to fix the process model, some extensions to the calibration are needed to suit the needs.

Define an extended move queue

β∈(A ^>> ×T ^>> ×M)* is the extended movement queue between trace σ and model PN if and only if:

(1) π ₁ (β) _↓A ≤ σ, that is, the movement of the extended mobile queue in the trace is the prefix of the trace σ;

(2) There is a complete occurrence sequence Have That is, the movement of the extended movement queue in the model is the prefix of the complete occurrence sequence;

in, Represents a complete sequence, T* represents a finite queue under the transition set T;

(3) m _i [π ₂ (β) _↓T >m, that is, the movement m∈R(m _i ) of the extended mobile queue in the model;

For the triplet (a, t, m) ∈ β in the extended mobile queue, there are the following extended actions:

(1) If a∈A and t=>>, it is called an extended log action;

(2) If a=>> and t∈T, it is called an extended model action;

(3) If a ∈ A and t ∈ T, it is called an extended synchronous action;

(4) Other types are called illegal extension actions;

The definition of the extended calibration is given further by the definition of the extended mobile queue:

Define Extended Calibration

The extended calibration β is an extended mobile queue between the trace σ and the model PN if and only if:

(1) π ₁ (β) _↓A = σ, that is, the movement of the extended mobile queue in the trace is this trace σ;

(2) That is, the movement of the extended movement queue in the model is a complete occurrence sequence;

(3) m _i [π ₂ (β) _↓T >m _f , that is, after the movement of the extended movement queue in the model occurs, it will eventually reach the termination mark,

where B _σ,PN is the set of all extended calibrations between the trace σ and the model PN; where π ₁ (β) _↓A represents the mapping of the first element in the calibration on the active set A, and π ₂ (β) _{↓ T} represents the mapping of the second element in the transition set T in the calibration;

Taking the Petri net shown in Figure 1 as an example, assuming there is a trace σ=<a, d, e, f>, its extended calibration is shown in Figure 2. Taking the trace σ=<a,d,e,f> as an example, the extended calibration shown in Figure 2 can be obtained. For the above two extended calibrations, it can be found that the extended move (a,a,m ₁ ) is a synchronous extended action, (f,>>,m ₅ ) is a log extended action, and (>>,b,m ₃ ) is A model extension action. Among them, the reachable identifier m ₂ : m ₂ (p ₂ )=m ₂ (p ₅ )=1, m ₂ (p ₁ )=m ₂ (p ₂ )=m ₂ (p ₃ )=m ₂ (p ₄ ) =m ₂ (p ₆ )=0.

In practice, the severity of the deviation will have different impacts depending on the activities and human formulations. In order to be able to generate the most probable extended calibration, it is necessary to assign a likelihood cost value to each extended action. According to the formulated possibility cost function, the extended calibration with the lowest possible cost value can be found, which is called the optimal extended calibration.

Define Optimal Extended Calibration

An extended calibration β∈B _σ, PN between the trace σ and the model PN is an optimal extended calibration if and only if any extended calibration β'∈B _σ,PN : Σ _{(a,t,m)∈βlc} ( (a,t))≤Σ _{(a',t',m')∈β'} lc((a',t'));

where B _σ,PN,lc is the optimal extended calibration set between the trace σ and the model PN when the likelihood cost function is lc;

In the present invention, for the log extension action and the model extension action, the possibility cost value is 1, and for the synchronous extension action, the possibility cost value is 0. Therefore, for the two extended calibrations β ₁ and β ₂ in Fig. 2, the possible cost values lc(β ₁ )=2, lc(β ₂ )=2, obviously, β ₁ and β ₂ are traces σ = Optimal extended calibration for <a,e,i,f,g>.

3. Deviation repair method

In real life, process models are often built through process mining algorithms or manually. Therefore, there is such a situation: the event log is completely consistent with the process model at the beginning, but with the development of the actual process, the event log gradually expands, and some traces that do not exist in the original process model appear. This type of log is called extended log in the present invention.

Herein, the present invention provides a formalized definition of an extended log.

Define extended event logs and extended trace sets

For event log L, fitness(L,PN)=1. The event log L' is an extended event log if and only if:

(1) L'∩L=L;

(2)

(3) 0<fitness(L',PN)<1.

For the newly appearing traces after expansion, the set PA=L’–L is called the extended trace set.

For the extended event log, the traces in the extended trace set lead to a decrease in the fit of the extended event log. Therefore, as long as various deviations appearing in the extended trace set are found and repaired, the process model restoration work of the extended event log can be completed.

For optimal extended calibration, there are two basic types of biases, extended log actions and extended model actions. Here, the two types of deviations are processed and repaired respectively.

3.1 Extended log action repair

The appearance of the extended log action indicates that there are activities in the event log that do not exist in the process model, and the original process model needs to be extended. Therefore, it is necessary to add a self-loop to the repository where the log action appears to meet this type of repair requirement. . When there are multiple optimal extended calibrations for a trace, and their deviations are exactly the same, taking any one of them as a reference will not affect the restoration of the process model. Therefore, the present invention only selects any one of the optimal extended calibrations for such cases. For event logs, different log actions may occur in different traces of the same library, so it is necessary to classify the log actions of the library. Save it in the form of an event log, and then call the mining algorithm to mine the event log, and add it to the library after mining the corresponding structure.

When defining the extended calibration, it can be known that π ₃ (β) is the reachable label after the transition in the model occurs. According to the occurrence rules of Petri nets, for any π ₃ (β[j])∈π ₃ (β), there exists at least For a place p, its reachability flag m _j (p)=1, if there are multiple places in the reachable flag so that the reachable flag value is 1, it needs to be preprocessed to avoid repeated repairs. Therefore, one can arbitrarily select a storehouse for log collection, and the present invention selects the earliest storehouse.

First of all, it is necessary to design an algorithm to realize the collection of log actions in a certain library. Its input is the optimal extended calibration set corresponding to the event log and the designated location. The idea is to traverse each extended calibration in turn. When the specified location is found and it is an extended log action, it will be stored in the log MLS. For log MLS, it is called log action deviation set here. After traversing all the extended optimal calibrations, an event log will be obtained, which lays the foundation for the next step of process model repair. The formal definition of log action deviation set is given below:

Define log action bias set

Assume is the active set, L is the event log based on the active set A, PN=(P, T, F, M) is the Petri net based on the active set A, and the optimal extended calibration set Β _{L, PN, lc} is based on the event log and the optimal extended calibration set of Petri nets, given a place p, MLS is a log action deviation set if and only if:

$\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; L</span>}\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; \{</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}{\mathrm{<span\; class="notranslate">\; and\&pi;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; \&lsqb;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&rsqb;</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; ></span><span\; class="notranslate">\; ></span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; .</span>$

Algorithm 1 collects the log actions of the specified library, and its steps are as follows:

Step1: input optimal extended calibration set Β _{L, PN, lc} and designated place p, traverse the entire optimal extended calibration set Β _{L, PN, lc} ;

Traverse the calibration β _i in the optimal extended calibration set, and perform the following operations during the traversal:

1) If there exists β _i [j..k]∈β _i , for There m _l (p)=1, andπ ₂ (β _i [l])=>>, then L←L∪γ _i [j..k];

Among them, β _i [j..k] represents some elements in β _i , and j and k are used to determine the range; β _i [l] represents an element of β _i , and m _l (p) represents the identity of m _l in the place the value at p;

2) If there is no extension sequence conforming to 1), then jump to Step1;

Step2: After traversing all the calibrations in the optimal extended calibration set Β _{σ, PN, lc} , output the log action deviation set MLS;

Taking the Petri net in Figure 1 as an example, suppose the event log L={<a,b,f,g,h,d,e>,<a,b,f,h,d,e>,<a,b, f, k, h, d, e>}, respectively seek their optimal extended calibration, as shown in Figure 3.

The log action bias set MLS={<f,g,h>,<f,h>,<f,k,h>} is obtained through the optimal extended calibration using the above steps.

After collecting the log actions of all specified libraries, store them in the log action deviation set. The next step is to process the log action deviation set. The process model can be mined through the mining algorithm, and then this model is added to the specified repository. At present, many scholars at home and abroad are devoted to the research of process mining algorithms. For example, the α algorithm based on the sequence relationship of activities and its derivative algorithms, the region mining and ILP mining based on semantic technology, and so on. The process mining algorithm used in the present invention is inductive mining. In the following, the restoration algorithm of the log action is given. The main idea is to dig out the process model corresponding to the log action deviation set through the mining algorithm, and then insert this process model into the specified repository.

Algorithm 2 repairs the log action of the extended log, and its specific steps are as follows:

Step1: Input the log action deviation set MLS and the specified place p, use the InductiveMiner algorithm to mine the log action deviation set MLS, and set PN’←InductiveMiner(MLS);

Step2: For all transitions t belonging to the posterior set of m _i ', perform the following operations:

1): Add the arc (p, t) to the arc set F of the original model PN;

2): Delete the arc (m _i ', t) from the arc set F' of the mining model PN';

Step3: For all transitions t belonging to the previous set of m _f ', perform the following operations:

1): Add the arc (t,p) to the arc set F of the original model PN;

2): Delete the arc (t, m _f ') from the arc set F' of the mining model PN';

Step4: Delete the initial place m _i ' and the termination place m _f in the place set P' of the mining model PN', and add all elements of the place set P' to the place set P of the original model PN ;

Step5: Add all elements of the place set T' to the place set T of the original model PN;

Step6: Add all elements of the place set F' to the place set F of the original model PN;

Step7: Output model PN.

Continuing to take the event log L as an example, according to its log action deviation set MLS={<f,g,h>,<f,h>,<f,k,h>}, according to Algorithm 2, formulate the place as p ₃ , the process model shown in Figure 4 can be obtained, where the repaired part has been marked.

3.2 Extended Model Action Repair

The appearance of model actions indicates that such activities do not exist in the event log. In order to make the event log replay in the process model, an invisible transition is added to extend the model so that it maintains a high fit with the event log.

The process model restoration algorithm in this situation is given below. The input of the algorithm is the model action in the optimal extended calibration, and the corresponding transition in the process model is determined through the model action, and then the front set and the back set of the transition are determined, and further Add an invisible transition, and finally output the process model.

Algorithm 3 repairs the model action of the extended log, and its specific steps are as follows:

Step1: Input the calibration β and the position i where the model action appears, and add the invisible transition τ to the transition set of the original model PN;

Step2: For all places p belonging to the previous set of π ₂ (β[i]), perform the following operations:

1): Add the place p to the place set P of the original model PN;

2): Add the arc (p, τ) to the arc set F of the original model PN;

Step3: For all places p belonging to the back set of π ₂ (β[i]), perform the following operations:

1): Add the place p to the place set P of the original model PN;

2): Add the arc (τ, p) to the arc set F of the original model PN;

Step4: Output model PN.

Taking the Petri net shown in Figure 1 as an example, for the trace σ=<a,d,e>, its optimal extended calibration is shown in Figure 5. According to the above steps to repair it, the repaired process model can be obtained, as shown in Figure 6.

By confirming the extended log action and the extended model action, you can determine where the deviations in the event log appear in the model, and repair these two types of deviations respectively, and the model will eventually be repaired.

The present invention takes the business process of the thoracic surgery department of a certain hospital as an example, and obtains the Petri net model in FIG. 7 by mining and modeling on the basis of the original event log. Its main activity process is described as follows: First, patients can make an appointment. There are two ways to make an appointment: reserve at triage station and reserve by phone. After the appointment is completed, make an appointment registration (booking ) and get reservation number. Patients can also consult without reservation directly, so patients need to register. For patients who make appointments and registered patients, the hospital needs to arrange and call number by order, and the patients will seek a doctor's consultation (inquiry) according to the order. Doctors ask questions to determine whether to order imaging tests and clinical tests. There are three types of imaging examinations: common CT (common ct), PET-CT, and chest enhanced scan. There are 4 types of clinical tests, erythrocyte sedimentation rate (ESR), biochemical full set, blood gas analysis and blood routine. After that, the doctor makes a diagnosis based on the test results. If the patient is in good condition, they can leave the hospital. If the patient is seriously ill, hospitalization is required.

Due to the huge amount of data in the hospital, only part of it is taken as the event log here. The event log used in this experiment consists of 2016 traces, and each trace is calibrated separately to obtain all the optimal extended calibration sets. On the basis of the original event log, new activities appear in this event log, so that this event log cannot be reproduced by the above process model, that is, there is a lack of activities in this model relative to the real process.

Taking the trace σ=<Reserve by Internet, Booking, Get reservation number, Arranging, Call number by order, Inquiry, Common ct, ESR, Diagnosis, Hospitalization> as an example, the optimal extended calibration is given.

Through the optimal extended calibration, it can be found that (Reserve by Internet,>>,m ₁ ) is an extended log action, indicating that there is an activity that does not exist in the model, and this activity may be the missing activity in the model. And (>>,Reserve by Phone,m ₂ ) is an extended model action, indicating that this activity should exist in the trace, but the fact does not exist. For these two actions, corresponding repair algorithms are required to repair the model. Extensive calibration of all traces enables discovery of all extended log actions and extended model actions present in the event log. In turn, these actions can be repaired.

In order to fix extended log actions, it is necessary to collect these actions in the event log. All the algorithms of the present invention are implemented in the ProM6.0 platform. ProM is an open source process mining tool, which provides source codes for people to learn and apply.

First, we take the event log and the process model as input, and obtain the optimal calibration set Γ _L,PN,lc of the event log through the Replay a Log on Petri Net for All Alignments plug-in.

On the basis of the optimal calibration set, the present invention adds a reachability mark to it, and obtains its optimal extended calibration set BL _,PN,lc .

After obtaining the optimal extended calibration set Β _{L, PN, lc} of the event log, it is necessary to collect the log action deviation set. Algorithm 1 is invoked with the optimal extended calibration set Β _{L, PN, lc} and place p ₁ as input.

Traversing all the extended calibrations in the optimal extended calibration set Β _{L, PN, lc} , it can be found that some of the optimal extended calibrations exist β _i [j..k]∈β _i , and for With m _l (p ₁ )=1 and π ₂ (β _i [l])=>>, Algorithm 1 adds it to a log L. If the optimal extended calibration does not satisfy this condition, the algorithm will continue to traverse.

After traversing the optimal extended calibration set Β _σ,PN,lc , Algorithm 1 will output the log action deviation set MLS at p ₁ .

Similarly, by performing Algorithm 1 processing on all the locations of the process model, the log action deviation set of each location of the entire process model can be obtained.

For the event log used in the present invention, the log action deviation set obtained through Algorithm 1 is shown in Table 1.

Table 1 Log Action Bias Sets at Various Positions

These actions are present in the event log but not in the process model, so the process model needs to be fixed. With the log action deviation set MLS at p ₁ and the designated place p ₁ as input, call Algorithm 2.

Algorithm 2 will first call the InductiveMiner algorithm that already exists in ProM to mine the log action deviation set MLS, and obtain a Petri net PN of an intermediate variable. '

Next, Algorithm 2 will process PN'. For all transitions t belonging to the back set of _{mi ', the arc (p,t) will be added to the arc set F of the original model PN and the arc (m i '} ,t) is deleted from the arc set F' of the mining model PN';

For all transitions t belonging to the previous set of m _f ', the arc (t,p) will be added to the arc set F of the original model PN and the arc (t,m _f ') will be added to the arc set of the mining model PN'F' is deleted.

Afterwards, Algorithm 2 will delete the initial place m _i ' and the termination place m _f ' in the place set P' of the mining model PN', and add all elements of the place set P' to the places of the original model PN Set P in.

Further, Algorithm 2 adds all elements of place set T' to place set T of the original model PN; and adds all elements of place set F' to place set F of the original model PN.

Finally, Algorithm 2 outputs the model PN.

Similarly, for the log action deviation set MLS at p ₁₂ and the designated place p ₁₂ , the process model is repaired by Algorithm 2.

Finally, for the restoration of the extended model action, taking the optimal extended calibration β of the trace σ as an example, it can be found that when i=2, an extended model action appears. Algorithm 3 is invoked with the optimal extended calibration β and i=2 as input.

First, Algorithm 3 will add invisible transition τ to the transition set T of the original model PN.

Next, in Algorithm 3, for all the places p belonging to the previous set of π ₂ (β[i]), add the places p to the place set P of the original model PN; add the arc (p,τ) to the original There is an arc set F of model PN.

Afterwards, Algorithm 3, for all the places p belonging to the back set of π ₂ (β[i]), adds the places p to the original model PN’s place set P; adds the arc (τ,p) to the original There is an arc set F of model PN.

Finally, Algorithm 3 outputs the model PN.

Similarly, traverse the entire optimal extended calibration set Β _σ,PN,lc and repair all the extended model actions that appear.

_The repaired process model adds two activities at p1, reserve by Internet and reserve by WeChat. Added two new categories of diagnostic measures at p ₁₃ , Conservative treatment and Referral treatment. In addition, as shown in the figure, two invisible transitions are added to the Petri net model to repair the model actions that occur in the optimal extended calibration.

For the repaired process model, it is not difficult to find that its event log can be completely replayed by it. That is, this process model conforms to the real process. In order to better evaluate this model, the comparison between this model and existing methods in terms of fitting degree, accuracy, generalization degree and time is given, and its indicators are shown in Table 2.

Table 2 Consistency indicators of the process model

Fit Accuracy Generalization time(s) original model 0.8566 0.7511 0.9021 existing methods 1 0.8188 0.97602 6.5 The method of the invention 1 0.8502 0.98802 6.4

According to Table 2, it can be found that the fitting degree of the method of the present invention and the existing method is 1, indicating that the event log can be completely reproduced in the process model. In terms of accuracy and generalization, the method of the invention is improved compared with the existing methods. As for the time complexity, since the two methods use the same mining method, the time difference between the two methods is very small.

Of course, the above descriptions are only preferred embodiments of the present invention, and the present invention is not limited to the above-mentioned embodiments. It should be noted that all equivalent substitutions made by any person skilled in the art under the teaching of this specification , obvious deformation forms, all fall within the essential scope of this specification, and should be protected by the present invention.

Claims (1)

1. A process model repairing method based on reachable identification is characterized by comprising the following steps:

a parameter definition

Defining traces and event logs

Is provided withIs an active set, trace σ ∈ A is an active queue, and event log L is a multiple set of traces, i.e.Defining a Petri Net

The quadruple PN (P, T; F, M) is called a Petri net PN if and only if:

(1) n-is a net, where P is a finite set of libraries, T is a finite set of transitions,is a finite arc set;

(2) p → N is called an identifier of the net PN, where M_iFor initial identification, m_fIs a termination identifier;

(3) PN has the following transition occurrence rules:

(a) for transition T ∈ T, ifThen the transition t is called to be enabled under the identifier M and is marked as M [ t ]>；

(b) If M [ t ]>Then, under the mark M, transition t can occur, and a new mark M' is obtained by triggering transition t from the mark M and is marked as M [ t ]>M' and to

In the definition of the Petri net,^·t represents an input set of t, t^·An output set representing t, M (p) represents the identity at repository p, M' (p) represents the identity at repository p after the transition t is initiated;

defining calibration

γ∈(A^>>×T^>>) Is the alignment between trace σ and model PN, if and only if:

(1)π₁(γ)_↓Aσ, i.e. the sequence of movements in the trace produces this trace;

(2)that is, the moving sequence in the model generates a completely occurring sequence;

wherein,_σ,PNis the set of all calibrations between trace sigma and model PN, pi₁(γ)_↓ADenotes the first element in the alignment, π₂(γ)_↓TRepresents the second element in the calibration;

there are three types of actions in calibration: a synchronization action, a log action, and a model action; wherein,

synchronous action refers to action that occurs in both the trace and the model, log action refers to action that occurs in the log but does not occur in the model, and model action refers to action that occurs in the model but does not occur in the log;

defining optimal calibration

Function lc: A^>>×T^>>→ IR is the possible cost function of calibration, calibration γ ∈ between trace σ and model PN_σ,PNIs an optimal calibration and only if the gamma' ∈ is arbitrarily calibrated_σ,PN:∑_(a,t)∈γlc((a,t))≤∑_{(a’,t’)∈γ’}lc((a’,t’))；

Wherein,_σ,PN,lcis the optimal calibration set between trace σ and model PN for a probability cost function of lc, ∑_(a,t)∈γlc ((a, t)) represents the cost value of the possibility of calibrating γ, ∑_{(a’,t’)∈γ’}lc ((a ', t ')) represents the cost value of the possibility to calibrate γ ';

b extended calibration

Defining extended mobile queues

β∈(A^>>×T^>>× M) is the extended move queue between trace σ and model PN, if and only if:

(1)π₁(β)_↓Asigma is less than or equal to, namely the movement of the extended mobile queue in the trace is the prefix of the trace sigma;

(2) there is a fully occurring sequenceIs provided withNamely, the movement of the extended movement queue in the model is the prefix of the completely-occurring sequence;

wherein,indicating a completely occurring sequence, T indicates a limited queue under the transition set T;

(3)m_i[π₂(β)_↓T>m, i.e. the movement of the extended movement queue in the model m ∈ R (m)_i)；

For a triplet (a, t, m) e β in the extended move queue, there are the following extended actions, respectively:

(1) if a belongs to A and t is > >, the operation is called an extended log operation;

(2) if a > and T belongs to T, the method is called an extended model action;

(3) if a belongs to A and T belongs to T, the method is called as an extended synchronization action;

(4) the other type is called illegal extension action;

the definition of extended alignment is further given by the definition of extended mobility queue:

defining extended calibration

Spread calibration β is the spread move queue between trace σ and model PN if and only if:

(1)π₁(β)_↓Aσ, that is, the movement of the extended move queue in the trace is the trace σ;

(2)namely, the movement of the extended movement queue in the model is a completely occurring sequence;

(3)m_i[π₂(β)_↓T>m_fi.e. after the extended mobile queue moves in the model, the termination flag is finally reached,

wherein, B_σ,PNIs the set of all spread calibrations between trace σ and model PN; wherein, pi₁(β)_↓ARepresenting the mapping of the first element in the alignment on the active set A, π₂(β)_↓TRepresenting a mapping of a second element in the calibration in the transition set T;

defining optimal extended calibration

Spread calibration β∈ B between trace σ and model PN_σ,PNIs an optimal spread calibration and only if any spread calibration β' ∈ B_σ,PN:∑_(a,t,m)∈βlc((a,t))≤∑_{(a’,t’，m’)∈β’}lc((a’,t’))；

Wherein, B_σ,PN,lcThe optimal extended calibration set between the trace sigma and the model PN under the condition that the probability cost function is lc;

c bias repair

Defining extended event logs and extended trace sets

For event log L, the fitness (L, PN) is 1, event log L' is an extended event log if and only if:

(1)L’∩L＝L；

(2)

(3)0<fitness(L’,PN)<1；

for a trace which newly appears after the extension, a set PA (PA) is L' -L and is called an extension trace set;

wherein, the fitness (L, PN) represents the fitting degree of the event log L under the model PN, and the fitness (L ', PN) represents the fitting degree of the event log L' under the model PN;

c.1 extended Log action repair

Defining a set of log action biases

Set the optimal extended calibration set B_L,PN,lcIs an optimal extended calibration set based on event logs L and Petri nets PN, given a repository p, MLS is a set of log action deviations, if and only if:

$MLS=\left\{mls\right|\&ForAll;mls\&lsqb;i\&rsqb;\&Element;mls,m_i\left(p\right)=1{\mathrm{and\&pi;}}_2(mls\&lsqb;i\&rsqb;)=>>\};$

collecting the log action of the designated library, which comprises the following steps:

step1 input the optimal extended calibration set B_L,PN,lcAnd a designated library place p, traversing the whole optimal extended calibration set B_L,PN,lc；

Traversing calibrations β in the optimal extended calibration set_iAnd executing the following operations in the traversal process:

1) if present β_i[j..k]∈β_iTo aHas m_l(p)＝1，andπ₂(β_i[l])＝>>Then L ← L ∪ gamma_i[j..k]；

Wherein, β_i[j..k]Representation β_iβ, j and k are used for determining the range_i[l]Representation β_iAn element of (1), m_l(p) represents the symbol m_lThe value at bin p;

2) if no spreading sequence according to 1) exists, jumping to Step 1;

step 2: traversing the optimal extended calibration set B_L,PN,lcCalibrating all the devices, and outputting a log action deviation set MLS;

the method for repairing the log action of the expansion log comprises the following specific steps:

step1: inputting a log action deviation set MLS and a specified library p, mining the log action deviation set MLS by using an InduceMiner algorithm, and setting PN' ← InduceMiner (MLS);

step 2: for all of m_i' transition t of the latter set, performing the following operations:

1): adding arcs (p, t) into an arc set F of the original model PN;

2): arc (m)_i', t) are deleted from the arc set F ' of the mining model PN ';

step 3: for all of m_f' transition t of the previous set, performing the following operations:

1): adding arcs (t, p) into an arc set F of the original model PN;

2): will arc (t, m)_f') is deleted from the arc set F ' of the mining model PN ';

step 4: deleting an initial repository m in a repository set P' of a mining model PN_i' and terminating library m_f'and adding all elements of the library set P' into the library set P of the original model PN;

step 5: adding all elements of the library set T' into the library set T of the original model PN;

step 6: adding all elements of the library set F' into the library set F of the original model PN;

step 7: outputting a model PN;

c.2, repairing the model action of the expansion log, and specifically comprising the following steps:

step1: inputting a calibration beta and a position i where model action occurs, and adding an invisible transition tau in a transition set of an original model PN;

step 2: for all belonging to pi₂(β[i]) The library of the previous set p, performing the following operations:

1): adding the place P into a place P of the original model PN;

2): adding the arcs (p, tau) into an arc set F of the original model PN;

step 3: for all belonging to pi₂(β[i]) The library of the latter set p, the following operations are performed:

1): adding the place P into a place P of the original model PN;

2): adding arcs (tau, p) into an arc set F of the original model PN;

step 4: and outputting the model PN.