Analysis of business process based on event logs

Размещено на http://www.allbest.ru/

Analysis of business process based on event logs

Contents

• 1. Preliminaries
• 1.1 Process Mining
• 1.2 Petri Net
• 1.3 Transition Systems
• 1.4 Process Logs
• 2. Overview
• 2.1 Two-phase approach to process discovery
• 2.2 Chain of plug-ins
• 2.3 Pattern Abstract plug-in
• 3. Theory Basement
• 3.1 Process mining techniques
• 3.2 Theory of Regions
• 3.3 Region-based process discovery
• 3.4 Algorithm for high-level process model discovery
• 3.5 Pseudocode of the algorithm
• 4. Implementation
• 4.1 XES logs
• 4.2 High-level activities
• 4.3 Plug-in
• 5. Examples of executions
• 5.1 Example 1
• 5.2 Example 2
• 6. Conclusion
• References
• Appendix 1
• Appendix 2
• 1. Preliminaries

• 1.1 Process Mining
• Process mining (PM) is a technique of process management that provides the analysis of business process basing on event logs [1,2]. Any information system record event logs and the main idea of PM is to get knowledge from them.
• Fig. 1. Process mining.
• Process mining not only provides tools and technics for discovering process, social, organizational and data structures from event logs. It is an approach to compare the analysed events with preferred or predefined models or rules. The most important part here is that the model should be evaluated in accordance with the criteria of how well it corresponds to the process in real life. This tasks requires plenty event logs, as much as we can get.
• Methods of PM are divided into 3 areas:
• Discovery. A discovery algorithm takes an event log and produces a model in the form of a Petri net explaining the behaviour recorded in the log. A lot of algorithms are fully described in literature [2]. On of them is the Region-Based algorithm that we'll review in details in this paper.
• Conformance checking. An existing process model is compared with an event log of the same process. The conformance checking is used to check whether information recorded in the log corresponds to the model.
• Enhancement. The idea here is to extend or improve existing process model using additional information about the process recorded in the event log.
• An example of event log that can be used as a starting point for PM is shown in Table 1. In this case the aim of this technique is to find a good characterization of all possible paths that can be expressed in different ways. One of the most popular of them is a Petri net.
• Table 1. An event log.

Case id	Activity id	Case id	Activity id	Case id	Activity id
1	A	4	A	3	D
2	A	2	B	4	B
3	A	2	D	5	E
3	B	5	A	5	D
1	B	4	C	4	D
1	C	1	D
2	C	3	C

• 1.2 Petri Net
• Formally a Petri net (Place/Transition net) is defined as follows [3,4]:
• ? = (P,T,F) is a place/transition net (or P/T-net) if:

– P is a finite, non empty set of places,?

– T is a finite, non empty set of transitions, such that P ? T = ? and T ?,

– F ? (PЧT)?(TЧP) is the flow relation of the net

Petri nets (PN) are usually used to specify processes. They consist of 2 modelling elements: transitions and places. If there is a need to represent PN visually the places may be drawn as circles and the transitions as rectangles. The current state of process execution is marked with a black dot called token. Multiple tokens may be contained in each place. One token is removed from each of the input places and one token is produced for each of the output places as soon as a transition fires.

Fig. 2. Example of a Petri net.

Figure 2 shows an example of a marked P/T-net, containing 10 places without labels and 11 transitions labelled A, B, C, D, E, F, G, H, I, J and K. Three places contain tokens drawn as black dots and these places are called marked. Marking is a distribution of all tokens over the places.

Further basic definitions were taken from [4]:

Definition 1.1. (Place/Transition net) ? = (P,T,F) is a place/transition net (or P/T-net) if:

– P is a finite, non empty set of places,?

– T is a finite, non empty set of transitions, such that P?T = ? and T ?,

– F?(PЧT)?(TЧP)is the flow relation of the net,

A marked Petri net is a pair (?,M0), where ? = (P,T,F) is a PN and M0 is a bag over P denoting the marking of the net. The set of all marked PNs is denoted N.

It should be noted, that Petri net can be defined as a directed graph ((P?T), F). So for this work we have to make some restrictions:

– *t? and t*? for all transitions t

– *p?p*? for all places p

As it was mentioned before PN are one of the best and most popular ways to describe processes and their dynamic behaviour. So it should be defined and from the dynamic view, not only static. The dynamics of PN are the combination of marking and firing rule.

First of all the notion of enabled transition should be defined:

Definition 1.2. (Enabled transition) Let ? = ((P,T,F),M0) be a marked P/T-net. Transition t T is enabled, denoted (?, M0)[t?, if and only if *t ? M0.

So a transition is enabled if all its input places have at least 1 token. A transition can fire only if the transition is enabled and it happens according to firing rule. They can fire only 1 by 1. Figure 2 shows 4 enabled transitions: H, G, I and F.

Definition 1.3. (Firing rule) Let ? = ((P,T,F),M0) be a marked Petri net. The firing rule (?, M0)[t?? NЧTЧN is the smallest relation satisfying for any ((P,T,F),M0)N and any t T, (?,M0)[t??(?,M0)[t?(?,M0?*t+t*).

When transition fires it takes 1 token from all the input places and puts only 1 token to every output place. Enabled transitions fire according to the plan that is called the firing rule. After F fires in Figure 2 the input place will have 0 tokens and output - 1 token.

The way of how tokens are distributed over the places is called marking. As one marking can be transformed into another the notion of reachable marking can be defined:

Definition 1.4. (Reachable markings) Let (?,M0) be a marked Petri net in N. A marking M is reachable from the initial marking M0 if and only if there exists a sequence of enabled transitions whose firing leads from M0 to M. The set of reachable markings of (?, M0) is denoted [?, M0?.

As a result a Petri net can reproduce each event from an event log it was obtained from.



1.3 Transition Systems

State-based models can be used for the formal specification and verification. Then they can be called Transition system (TS) as they reflect the states of a process and transitions between them.

Definition 1.5. (Transition system) A labelled state transition system is a triple (S,Л,>), where S is a set of states, Л is a set of labels, and >? SЧЛЧS is a ternary relation. If p,q S and б Л, (p,б,q) > is usually written as p q. This represents the fact that there is a transition from state p to state q, by executing a transition (or by performing an activity) labelled б. Furthermore, in this paper, we assume that a transition system is connected.

The idea of Regions was introduced for the aim of obtaining PN from TS. This process is called Synthesis. The main idea is to transform a TS into a PN that will exactly copy the its behaviour using regions as intermediate components.

Fig. 3. (a) Transition system, (b) minimal regions.

Definition 1.6. (Region in a transition system) Let TS = (S, Л, >) be a transition system. We say that R ? S is a region of TS if and only if for all (p, б, q), (p', б, q') ?> holds that:

– if p R and q R then p' R and q' R, i.e. all transitions labelled б exit the region, and we say that R is a pre-region of б,

– if p R and q R then p' R and q' R, i.e. all transitions labelled б enter the region, and we say that R is a post-region of б,

– if (p R)=(q R) then (p' R)=(q' R), i.e. all transitions labelled б do not cross the region. ?

There are some facts that should be mentioned about regions:

– For any transitions system two trivial regions can be found: ? ? S and S ? S.

– The set of all regions of a TS is usually marked with R(TS).

– The set of all minimal regions is marked with Rmin(TS).

Definition 1.7. (Minimal region) A region R R(TS) is said to be minimal if and only if for all R'?R with R' ? holds that R' R(TS).

Figure 3 shows the examples of regions. Minimal regions from Figure 3(a) are listed in Figure 3(b). According to it for region r₂:

– event a is an exit

– event d is an entry

– all other events don't cross

Definition 1.8. (Pre-set and post-set for events and regions) Let TS = (S, Л, >) be a transition system and a Л an activity label. The pre-region set and the post-region set of a are the sets of regions defined as follows:

– ?^TS a={R R(TS)|?(s,a,s) >:s R?s R} and

– a ?^TS ={R R(TS)|?(s,a,s) >:s R?s R}

• 1.4 Process Logs
• Information systems can log all kinds of events, but it entirely depends on the configuration. Moreover, systems can use some specific format. For our study we abstract from additional information presented in event logs and define a process log (PL) as a multiset of traces, where a trace is a sequence of events.
• Definition 1.9. (Trace, Process log) Let T be a set of activities. у T? is a trace, and W P(T?) is a process log.
• In Definition 1.9 a log is defined as a set of traces. But it can be not really a set as a trace can occur several times. Figure 4 illustrates an example of process log.
• Definition 1.10. (Globally complete log) Let T be a set of log events and L P(T?) be the set of all possible traces of some model or process. Furthermore, let W P(T?) be a process log over T. We say that W is a globally complete log if and only if W = L.
• In other words log is globally complete if it keeps all the possible behaviour of the underlying system. But really it's hard to predict whether a log is globally complete or it does not.
• Fig 4. A piece of process log.
• 
• 2. Overview
• Process models describe operational and business processes of companies as "maps". But classical process discovery algorithms have issues dealing with highly detailed event logs. The most common of them are:

1. Processes are much less structured than are expected to be.

2. Event logs contain too many logged events whereas user would like to view processes at a more global level.

So the obtained models are often too detailed and unclear. They can be even deceptive, i.e. "Spaghetti-like" model shown in Figure 5. So for common understanding of the business process it's better to use high-level business model - a model where low-level activities are merged into high-level according to their specification.

Fig. 5. "Spaghetti-like" low-level model

Definition 2.1. (Low-level model) Low-level model is such a model where each event corresponds to a single record in the log.

Definition 2.2. (High-level model) High-level model is a model where all low-level events are divided into non-overlapping groups. Such groups can be formed according to social, functional or some other traits.

The main and most popular approach for high-level model discovering is the Two-phase approach [5].


• 2.1 Two-phase approach to process discovery
• This approach to process discovery consists of 2 steps [1, 2, 5]:

– The first step (simplification) is to bring the log file to the desired level of detalization.

– The second one - process model discovering from the simplified log.

Phase 1: Log pre-processing

At this step, the log should be simplified. This process is usually based on the context analysis. The abstractions from low-level events to a desired level of detalization should be defined. On of the approaches is based on domain knowledge. An other one is to look for common execution patterns and some relationships can determine abstraction. These common execution patterns typically capture a sub-process/functionality. This behaviour can be captured as an abstract activity.

Definition 2.1. (Abstraction) Abstraction is a mapping M ? 2У Ч A between the original alphabet У of the event log and abstract alphabet A. An example of such a mapping:

M={({a,b},x),({b,c,d},y),({e},z),({d},z)}

Each (B, a) M may reflect a set of sequences s B+ capturing the set of patterns defined by the alphabet B for the abstraction a.

So the original event log L, turns into an abstract log L' basing on this mapping. Each trace t ? L is converted into a trace t' ? L'. At the same time a sub-log for each abstract activity a ? A is created. So the main idea of ??the algorithm is to look through each trace and to find out whether there is a pattern in the trace that is equal to one of the existing abstractions. If it can be found than the pattern in the trace is replaced by an abstract activity and at the same time the part that was replaced is added as a trace in the sub-log related to this abstract activity. Figures 6 and 7 shows an overview of the event log transformation.

Fig. 6. Converting the original log into an abstracted one.

Let's define the map for a set of events У:

D = (B,a)MB.

All the activities in У \ D aren't used in the definition of mapping activities are filtered from t during this transformation.

Fig. 7. For each one abstract sub-activity log is created. X, Y, Z and abstract work

Phase 2: Mining

The aim of the next phase is to obtain a model from the log that we got after transformation. The hierarchy over the abstract activities is induced by the mapping from the previous phase. Sub-logs for each abstract activity can be used to obtain a sub-process model that was captured before.

The phase can be repeated several times to obtain different levels of abstraction or hierarchy. In other words i+1-iteration can be obtained from the i-iteration. And if it would be defined over already existing abstraction then a hierarchy will be shown.

Fig. 8. Traditional and two-phase approaches to the discovery process.

Figure 8 illustrates the difference between the traditional approach to the discovery process and the two-phase approach. It's easy to see that the model obtained after two-phase approach is much more clear.

• 2.2 Chain of plug-ins
• The two-phase approach to process discovery enables the discovery of hierarchical and high-level process models [5]. In that paper the chain of plug-ins implemented in ProM [6] was described. The order of their application is illustrated in Figure 9.
• Fig. 9. An example of plugins that enables the discovery of abstract process model.
• At first the event log should be pre-processed and cleaned. In other words, some artificial event, like "start" or "end", can be added and some events may be filtered out.
• The next step is to find abstraction in the pre-processed log. There is the Pattern Abstractions plug-in implemented in ProM. Its aim is to find some common execution patterns and make abstractions over them. This plug-in can be applied several times one the same log. The log obtained after such a transformation becomes an input for the plug-in again on the next iteration. The approach helps to discover many different levels of hierarchy. Each of them can become a basis for a high-level model and for more iterations the log pass higher level of the model will be obtained.
• For each abstractions defined on this step a sub-log is created to save the information. The functionality of the Pattern Abstraction plug-in will be described in the next section.
• The last step is to discover process models not only for the pre-processed log, but both for all the generated sub-logs. Zooming on any abstraction can show them. The authors of the [5] recommend to use the Fuzzy Miner plug-in implemented in ProM [7].
• 2.3 Pattern Abstract plug-in
• Figure 10 shows the 5 parts of the Pattern Abstractions plug-in.
• Fig. 10. Parts of the Pattern Abstractions plugin.
• Discover Common Execution Patterns: This block discovers loop patterns and repeats of activities [7]. This process takes linear time depends only on the length of the log.
• Compute Pattern Metrics: This block tries to access the significance of the uncovered patterns with the help of different metrics.
• Filter Patterns: The aim of this block is to filter out some discovered patterns.
• Form and Select Abstractions: The approach used in this block is described in [8]. Abstractions are formed for the obtained patterns and some more features like merging.
• Transform Log: The last block replaces activities with abstract. Those ones that are replaced should be captured in sub-logs.
• This plug-in supports some more features: exporting the traces with patterns and visualizing.
• 
• 3. Theory Basement
• This section is dedicated to the idea that the process of high-level model discovery from the log can take less intermediate steps. For this purpose we have analysed the main approaches to process model discovery if they can be modified for the goals of our studying.
• 3.1 Process mining techniques
• Some classical techniques for process model discovery were analysed for ability to implement the goals of that research [1,2]:

· б-Algorithm ?

· Heuristic mining?

· Genetic mining

· Region-Based approach

All of them have their advantages and disadvantages and different fields of application.

б-Algorithm ?

This algorithm was one of the first that could deal with concurrency [1,2]. It is simple and is usually used as introduction to process mining and more complex and practically used discovery algorithms. Nowadays it is not often used in practice as it has some problems dealing with incomplete behaviour, complex constructs and noise.

Heuristic Miner

This approach extends б-algorithm and can be used to express the main behaviour of the system [1,2,9]. It deals even with noise but cares only about the order of events within cases. The order of the events among cases is not important.

Genetic mining

It is an evolutionary approach that copies the process of natural evolution basing on iterative procedures [1,2,10]. It depends on randomization looking for some new alternatives and is absolutely not deterministic. It can deal with incompleteness and noise like the previous approach and is quite flexible. But it is not very good for large logs and models as it can take to much time for computation. That's why it's usually combined with heuristic miner.

So all the approaches listed before are not suitable for solving the problem of the study. They are old fashion or too heuristic. But after some research we assumed that the Theory of Regions fits that purpose quite well.

• 3.2 Theory of Regions
• Theory of Regions was developed in the papers of Rozenberg and Ehrenfeucht [11] and it has been applied to the net synthesis [12] and to the characterization of concurrency models [13,14]. But still this approach to PM has not received great attention. At may be caused by the fact that the use of the regions in general gives a saturated net and in comparison with other methods its complexity is too high.
• The new approach to the Theory of Region was shown by B. van Dongen, N. Busi, G. Pinna and W. van der Aalst [4]. The novelty of the approach lied in the incremental calculus of the regions. Although regions of transition systems can be combined algebraically under precise conditions the attempt to find regions of compound transition system from the regions of the components was quite new and could gave better performance.
• Some approaches have been studied to take theory of Regions into practice in the area of synthesis. The polynomial algorithm of the synthesis of bounded nets was presented in [15] and then was adapted to the problems of process mining [16]. The Theory was applied for the synthesis of safe PN with bisimilar behaviour in [17] and has been extended to bounded PN [18]. Later [19] adapted the Theory from [18] to the problem of the PM.

• 3.3 Region-based process discovery
• The process of Process Model Discovery from log is basically divided into 2 phases:

1. Obtaining transition system from the process log

2. Mining Petri net from the obtained TS

Phase 1: Process log to transition system

The first step is to show each trace of the process log as TS. In classical approach this translation is rather simple [7].

Fig. 11. The 5 cases of Table 1 as TSs.

Figure 11 shows 5 translations for the 5 cases of Table 1. In this example all traces start with one activity, but in practice, they can start with different ones. However, this can be solved easily by adding a synthetic activity to the start all the traces.

The next step is to transform the obtained TSs into a single TS. On this stage all the duplicates may be removed. The result is shown in Figure 12.

Phase 2: Transition system to Petri net

Once a process log is translated to the TS the Theory of Regions can be applied for generating a Petri net from it. Each log event is represented as a transition in the TS, so each event has a set of post-regions and pre-regions in the TS that will be transformed into the input and output places in the PN.

Here is the classical algorithm [3,4] of PN synthesis based on minimal regions:

1. For each set of events e ? E generate a transition labelled with p in the PN.

2. For each minimal region ri ? RTS generate a place ri; ?

3. Place ri contains a token in the initial marking iff the corresponding ?region ri contains the initial state of the TS sin; ?

4. The flow relation is as follows: p ? ri* iff ri is a pre-region of p ?and p ? *ri iff ri is a post-region of p, i.e.,?

FTS {(r,p)|r?RTS ? p?P ? r? ^op} ?{(p,r)|r?RTS ? p?P ? r?p^o}

Fig. 12. The TSs of Figure 4 as single TS.

In this approach only minimal regions are translated into places and their computation is crucial for the synthesis method. The result of the synthesis on the TS from Figure 12 is shown in Figure 13.

Fig. 13. Generated Petri net from the TS of Figure 12.

• 3.4 Algorithm for high-level process model discovery
• In this section we present an algorithm for high-level business process model discovery. To discover a model we need to construct a high-level Transition System (HLTS) with high-level activities as transitions and then to synthesis the PN.
• That means that at first we should match low-level activities to high-level in such a way that for each set of low-level activities we associate one high-level activity. An example of such matching for activities from Table 1 is shown in Table 2.
• Table 2. Matching low-level activities to high-level.

Activity	A	B	C	D	E
High-level activity	F	G	G	H	J

• As a result we get: F = {A}, G = {B,C}, H = {D}, J = {E}.
• The process of log transformation into the HLTS is divided into 2 steps:

1. Mine preHLTS from the process log

2. Discover HLTS from the obtained preHLTS

Log to preHLTS

The first step is to obtain a preHLTS - a TS from the process log like in previous section where all the low-level activities are replaced by high-level ones and all the emerged duplicates are eliminated.

Fig. 14. PL to preHLTS based on Table 2.

Figure 14 shows the result of transformation of initial process log (a) to TS (b) and duplicates eliminating (c). The steps (b) and (c) can be processed in parallel.

So Figure 14(c) shows the preHLTS. But if we'll try to synthesis PN from this preHLTS as it was described in the previous section for low-level modelling we'll get a linear PN with self-loops. But since we want to get a high-level model, in most cases, such a TS should tell us that a few high-level steps are performed in parallel.

PreHLTS to HLTS

We propose the following algorithm for transforming preHLTS into HLTS. This algorithm is applicable only for process log without loops. It's based on the idea that for each repetition of a high-level transition we generate a new trace to consider all options for parallel execution. The example of such transformation of preHLTS from Figure 14(c) is shown in Figure 15.

Fig. 15. Generated Petri net from the TS of Fig.14.

The result of the HLTS synthesis with the proposed algorithm is shown on in Figure 16(a). Now if we use the second step of the Region-based algorithm for PN synthesis we'll obtain the HLPN shown in Figure 16(b).

Fig. 16. The result of the proposed algorithm (a) and the synthesised HLPN (b).

• 3.5 Pseudocode of the algorithm

1. getPreHLTS(Log);

2. drawTrace (preplace to draw from, place to draw from, transition to draw);

3. function getPreHLTS(Log) {

4. while (not the end of Log) {

5. if (high-level activity is not repeated) {

6. create transition and places for it;

7. remember the activity seen last;

8. }

9. }

10. }

11. function drawTrace(preplace, place, transition) {

12. while (not end of preHLTS) {

13. if (transition is not repeated) {

14. put transition to the set of all drawn transitions;

15. draw a transition and places;

16. and remember the last drawn transition;

17. } else {

18. if (transition is repeated for the first time) {

19. Place = get the place with that transition met before;

20. Trans = get all the transitions met before;

21. start new drawTrace(from Place, from next place, Trans);

22. remember that met transition second time;

23. }

24. }

25. }

26. }

• 
• 4. Implementation
• The algorithm presented in this work was implemented in the open source framework ProM [6] to check it in practice. It is a framework in Java that became a base for a lot of process mining techniques implemented in the form of plug-ins.
• Fig. 17. The developed plug-in.
• The plug-in takes a process log in XES format [20] as an input and returns a high-level transition system as an output in a common format that is widely used in most of the plug-ins working with TSs.
• 4.1 XES logs
• XES (eXtensible Event Stream) logs were used for holding the experiments. Figure 18 shows an example of such a log.
• Fig. 18. XES log.
• XES is an XML-based standard for event logs [14]. It was designed to be very applicable for general mining and statistical analysis. But its main purpose is for process mining and analysis that take event logs as an input.
• XES represents data in a very simple way. Such logs are understandable, and easy in parsing and generation. It can capture logs from any applications and strives to be a standard for any event log.
• The XES standard was developed in such a way to be very flexible and extensible, but at the same time to loose as little information as possible. All its elements, which can be identified in the only way, are strongly typed. All others are optional attributes.
• 4.2 High-level activities
• As it was written before there are several ways to associate low-level activities with high-level. For this plug-in the obtaining of special information from log was chosen.
• Fig. 19. Classifiers in XES log.
• Thanks for the special structure of the XES logs it's quite easy to store the high-level information, identify and analyse it. Figure 19 shows the list of so call "classifiers" that is defined at the beginning of the file. These tags define what of the characteristic of each activity written in the log can classify it. As every activity should contain these classifiers (Fig. 20) we can use them as that kind of information that is needed to divide all low-level activities into groups - high-level activities.
• Fig. 20. One event of the XES log.
• 4.3 Plug-in
• Before starting the log transformation to high-level transition system the developed plug-in ask user to set up some configurations of the log (Fig. 21).
• Fig. 21. Wizard for plug-in configuration.
• As it was written before it takes the XES log as an input. It analyses the set of classifiers used in that log and asks user to choose what of them should be used as classifiers of low-level and high-level activities. Figure 22 shows this step of configuration.
• Fig. 22. Classifiers configuration.
• The next step is to choose low-level and high-level activities that should be taken into account in the analysis. They are all selected by default (Fig. 23) as only this configuration can transform all the events from the log to transition system and show all possible traces of process execution.
• Fig. 23. Classifier filter.
• This is the last step of the miner configuration so after that the log analysis and transformation into the transition system will start. The result of this process is shown on Figure 24. pseudocode algorithm management plug-in
• Fig. 24. The obtained high-level transition system.

• 5. Examples of executions
• This section illustrates two examples of plug-in execution. First of them shows the efficacy of the developed algorithm in comparison to the classical approach. The second one illustrates the main idea and principal difference from common algorithm.
• 5.1 Example 1
• The effectiveness of the developed algorithm can be seen on the next example.
• Figure 25 shows the result of Petri net synthesis from the obtained High-level Transition system.
• Fig. 25. The PN synthesised from the HLTS.
• And it's easy to see that the obtained PN is much more simple and clear for understanding then another one synthesized with the classical approach from the same log (Fig. 26). This log can be found in Appendix 1.
• Fig. 26. The PN synthesised from the common TS.
• 5.2 Example 2
• Fig. 27. The obtained Perti net.
• This example shows the core difference or the developed algorithm on a short log with only one trace of execution (Appendix 2). Figures 27 and 28 shows the obtained high-level transition system after log transformation with the help of purposed technique and the Petri net synthesised from it.

• Fig. 28. High-level transition system.
• Figure 28 illustrates the feature of the proposed technique to detect parallel running processes of the system under analysis. Thanks for assumption made in Section 3.4 the synthesized Petri net shows the 2 processes "Check" and "Think" that are performed in parallel on Figure 27.
• Figure 29 illustrates Petri net synthesized from the common transition system transformed from the same log. It's linear.
• Fig. 29. Petri net after common transformation.
• 
• 6. Conclusion
• The main purpose of this study was to offer a solution to one of the most urgent problems of process mining. There are a lot of methods for business process analysis that discover process models from event logs. But for more detailed the log is, the more difficult for understanding and misleading becomes the obtained model. So sometimes it's much more convenient to use high-level abstractions of process models.
• In this work we tried to find a new solution for this problem and proposed a new method for it. All the goals set at the beginning of the work have been reached. We:

· Analyzed the existing approaches for high-level model discovery

· Developed a new algorithm for high-level business process model discovery

· Implemented the algorithm as a plug-in for ProM

· Checked the algorithm on some examples and got much more simple and understandable models then using classical approach

As a result we've got a method for process analysis that will be very helpful for specialists as it'll can help then to understand the analyzed process much more deep and clear.

There are several ways for future studding and investigations:

· To adapt the algorithm for working with high-level models with loops

· To simplify the obtained transition system after log transformation thanks for merging the repeated states

· To check out the possibility of using the obtained transition system not only with the Region-Based approach but also with others that take a transition system as an input for Petri net synthesis.

• 
• References

[1] Process mining. Available at: http://www.processmining.org/ (Accessed 01.06.2015).

[2] W. M. P. van der Aalst. Process Mining. Discovery, Conformance and enhancement of Business Processes. Department Mathematics & Computer Science Eindhoven University of Technology. Eindhoven, the Netherlands, 2011.

[3] T. Murata. Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE, 77(4):541-580, April 1989.

[4] B. van Dongen, N. Busi, G. Pinna, and W. van der Aalst. An iterative algorithm for applying the theory of regions in process mining. Technical Report Beta rapport 195, Department of Technology Management, Eindhoven University of Technology, 2007. ?

[5] R.P. Jagadeesh Chandra Bose, Eric H.M.W. Verbeek, Wil M.P. van der Aalst. Discovering Hierarchical Process Models Using ProM. IS Olympics: Information Systems in a Diverse World Lecture Notes in Business Information Processing Volume 107, 33-48, 2012.

[6] ProM. Process Mining Workbench. Available at: http://www.promtools.org/ (Accessed 01.06.2015).

[7] Gunther, C., van der Aalst, W.M.P.. Fuzzy Mining: Adaptive Process Simplification Based on Multi-perspective Metrics. In: International Conference on Business Process Management (BPM 2007). Volume 4714 of LNCS, Springer-Verlag, 328-343, 2007.

[8] Bose, R.P.J.C., van der Aalst, W.M.P.. Abstractions in Process Mining: A Taxonomy of Patterns. In Dayal, U., Eder, J., Koehler, J., Reijers, H., eds.: Business Process Management. Volume 5701 of LNCS., Springer-Verlag, 159-175, 2009.

[9] A.J.M.M. Weijters, W.M.P. van der Aalst, and A.K. Alves de Medeiros. Process Mining with the Heuristics Miner-algorithm. BETA Working Paper Series, WP 166, Eindhoven University of Technology, Eindhoven, 2006.

[10] W.M.P. van der Aalst, A.K. Alves de Medeiros, and A.J.M.M. Weijters. Genetic Process Mining. In G. Ciardo and P. Darondeau, editors, Applications and Theory of Petri Nets 2005, volume 3536 of Lecture Notes in Computer Science, pages 48-69. Springer-Verlag, Berlin, 2005.

[11] Ehrenfeucht and G. Rozenberg. Partial (Set) 2-Structures - Part 1 and Part 2. Acta Informatica, 27(4):315-368, 1989. ?

[12] J. Desel and W. Reisig. The synthesis problem of petri nets. Acta informatica, 33:297-315, 1996.

[13] P. W. Hoogers, H. C. M. Kleijn, and P. S. Thiagarajan. An event structure semantics for general Petri nets. Theoretical Computer Science, 153(1-2):129-170, 1996. ?

[14] M. Nielsen, G. Rozenberg, and P.S. Thiagarajan. Elementary transition systems. Theoretical Computer Science, 96(1):3-33, 1992. ?

[15] E. Badouel, L. Bernardinello, and P. Darondeau. Polynomial algorithms for the synthesis of bounded nets. Lecture Notes in Computer Science, 915:364-383, 1995. ?

[16] R. Bergenthum, J. Desel, R. Lorenz, and S.Mauser. Process mining based on regions of languages. In Proc. 5th Int. Conf. on Business Process Management, ?pages 375-383, Sept. 2007.

[17] J. Cortadella, M. Kishinevsky, L. Lavagno, and A. Yakovlev. Deriving Petri nets ?from finite transition systems. IEEE Transactions on Computers, 47(8):859-882, ?Aug. 1998. ?

[18] J. Carmona, J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and ?A. Yakovlev. A symbolic algorithm for the synthesis of bounded Petri nets. In ?29th International Conference on Application and Theory of Petri Nets and Other ?Models of Concurrency, June 2008. ?

[19] J. Carmona, J. Cortadella, M. Kishinevsky. A Region-based Algorithm for Discovering Petri Nets from Event Logs. Business Process Management, 358-373. 2008.

[20] XES. Extensible Event Stream. Available at: http://www.xes-standard.org/ (Accessed 01.06.2015)


• Appendix 1
• Example log 1.
• <?xml version="1.0" encoding="UTF-8" ?>
• <!-- XES version 1.0 -->
• <!-- Created by Fluxicon Nitro (http://fluxicon.com/nitro/ -->
• <!-- (c) 2010 Fluxicon Process Laboratories / http://fluxicon.com/ -->
• <log xes.version="1.0" xmlns="http://code.deckfour.org/xes" xes.creator="Fluxicon Nitro">
• <extension name="Concept" prefix="concept" uri="http://code.deckfour.org/xes/concept.xesext"/>
• <extension name="Time" prefix="time" uri="http://code.deckfour.org/xes/time.xesext"/>
• <extension name="Organizational" prefix="org" uri="http://code.deckfour.org/xes/org.xesext"/>
• <global scope="trace">
• <string key="concept:name" value="name"/>
• </global>
• <global scope="event">
• <string key="concept:name" value="name"/>
• <string key="org:resource" value="resource"/>
• <date key="time:timestamp" value="2011-04-13T14:32:48.100+02:00"/>
• <string key="Activity" value="string"/>
• <string key="Resource" value="string"/>
• <string key="Costs" value="string"/>
• </global>
• <classifier name="Activity" keys="Activity"/>
• <classifier name="HLActivity" keys="HLActivity"/>
• <string key="creator" value="Fluxicon Nitro"/>
• <trace>
• <string key="concept:name" value="3"/>
• <string key="creator" value="Fluxicon Nitro"/>
• <event>
• <string key="concept:name" value="register request"/>
• <string key="org:resource" value="Pete"/>
• <date key="time:timestamp" value="2010-12-30T14:32:00.000+01:00"/>
• <string key="Activity" value="register request"/>
• <string key="HLActivity" value="register"/>
• <string key="Resource" value="Pete"/>
• <string key="Costs" value="50"/>
• </event>
• <event>
• <string key="concept:name" value="examine casually"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2010-12-30T15:06:00.000+01:00"/>
• <string key="Activity" value="examine casually"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="400"/>
• </event>
• <event>
• <string key="concept:name" value="check ticket"/>
• <string key="org:resource" value="Ellen"/>
• <date key="time:timestamp" value="2010-12-30T16:34:00.000+01:00"/>
• <string key="Activity" value="check ticket"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Ellen"/>
• <string key="Costs" value="100"/>
• </event>
• <event>
• <string key="concept:name" value="decide"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-06T09:18:00.000+01:00"/>
• <string key="Activity" value="decide"/>
• <string key="HLActivity" value="decide"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="reinitiate request"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-06T12:18:00.000+01:00"/>
• <string key="Activity" value="reinitiate request"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="examine thoroughly"/>
• <string key="org:resource" value="Sean"/>
• <date key="time:timestamp" value="2011-01-06T13:06:00.000+01:00"/>
• <string key="Activity" value="examine thoroughly"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Sean"/>
• <string key="Costs" value="400"/>
• </event>
• <event>
• <string key="concept:name" value="check ticket"/>
• <string key="org:resource" value="Pete"/>
• <date key="time:timestamp" value="2011-01-08T11:43:00.000+01:00"/>
• <string key="Activity" value="check ticket"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Pete"/>
• <string key="Costs" value="100"/>
• </event>
• <event>
• <string key="concept:name" value="decide"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-09T09:55:00.000+01:00"/>
• <string key="Activity" value="decide"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="pay compensation"/>
• <string key="org:resource" value="Ellen"/>
• <date key="time:timestamp" value="2011-01-15T10:45:00.000+01:00"/>
• <string key="Activity" value="pay compensation"/>
• <string key="HLActivity" value="pay"/>
• <string key="Resource" value="Ellen"/>
• <string key="Costs" value="200"/>
• </event>
• </trace>
• <trace>
• <string key="concept:name" value="2"/>
• <string key="creator" value="Fluxicon Nitro"/>
• <event>
• <string key="concept:name" value="register request"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2010-12-30T11:32:00.000+01:00"/>
• <string key="Activity" value="register request"/>
• <string key="HLActivity" value="register"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="50"/>
• </event>
• <event>
• <string key="concept:name" value="check ticket"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2010-12-30T12:12:00.000+01:00"/>
• <string key="Activity" value="check ticket"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="100"/>
• </event>
• <event>
• <string key="concept:name" value="examine casually"/>
• <string key="org:resource" value="Sean"/>
• <date key="time:timestamp" value="2010-12-30T14:16:00.000+01:00"/>
• <string key="Activity" value="examine casually"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Sean"/>
• <string key="Costs" value="400"/>
• </event>
• <event>
• <string key="concept:name" value="decide"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-05T11:22:00.000+01:00"/>
• <string key="Activity" value="decide"/>
• <string key="HLActivity" value="decide"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="pay compensation"/>
• <string key="org:resource" value="Ellen"/>
• <date key="time:timestamp" value="2011-01-08T12:05:00.000+01:00"/>
• <string key="Activity" value="pay compensation"/>
• <string key="HLActivity" value="pay"/>
• <string key="Resource" value="Ellen"/>
• <string key="Costs" value="200"/>
• </event>
• </trace>
• <trace>
• <string key="concept:name" value="10"/>
• <string key="creator" value="Fluxicon Nitro"/>
• <event>
• <string key="concept:name" value="register request"/>
• <string key="org:resource" value="Pete"/>
• <date key="time:timestamp" value="2010-12-30T14:32:00.000+01:00"/>
• <string key="Activity" value="register request"/>
• <string key="HLActivity" value="register"/>
• <string key="Resource" value="Pete"/>
• <string key="Costs" value="50"/>
• </event>
• <event>
• <string key="concept:name" value="examine casually"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2010-12-30T15:06:00.000+01:00"/>
• <string key="Activity" value="examine casually"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="400"/>
• </event>
• <event>
• <string key="concept:name" value="check ticket"/>
• <string key="org:resource" value="Ellen"/>
• <date key="time:timestamp" value="2010-12-30T16:34:00.000+01:00"/>
• <string key="Activity" value="check ticket"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Ellen"/>
• <string key="Costs" value="100"/>
• </event>
• <event>
• <string key="concept:name" value="decide"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-06T09:18:00.000+01:00"/>
• <string key="Activity" value="decide"/>
• <string key="HLActivity" value="decide"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="reinitiate request"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-06T12:18:00.000+01:00"/>
• <string key="Activity" value="reinitiate request"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="examine thoroughly"/>
• <string key="org:resource" value="Sean"/>
• <date key="time:timestamp" value="2011-01-06T13:06:00.000+01:00"/>
• <string key="Activity" value="examine thoroughly"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Sean"/>
• <string key="Costs" value="400"/>
• </event>
• <event>
• <string key="concept:name" value="check ticket"/>
• <string key="org:resource" value="Pete"/>
• <date key="time:timestamp" value="2011-01-08T11:43:00.000+01:00"/>
• <string key="Activity" value="check ticket"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Pete"/>
• <string key="Costs" value="100"/>
• </event>
• <event>
• <string key="concept:name" value="pay compensation"/>
• <string key="org:resource" value="Ellen"/>
• <date key="time:timestamp" value="2011-01-15T10:45:00.000+01:00"/>
• <string key="Activity" value="pay compensation"/>
• <string key="HLActivity" value="pay"/>
• <string key="Resource" value="Ellen"/>
• <string key="Costs" value="200"/>
• </event>
• </trace>
• <trace>
• <string key="concept:name" value="7"/>
• <string key="creator" value="Fluxicon Nitro"/>
• <event>
• <string key="concept:name" value="register request"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2011-01-15T12:00:00.000+01:00"/>
• <string key="Activity" value="register request"/>
• <string key="HLActivity" value="register"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="50"/>
• </event>
• <event>
• <string key="concept:name" value="examine thoroughly"/>
• <string key="org:resource" value="Sean"/>
• <date key="time:timestamp" value="2011-01-16T12:00:00.000+01:00"/>
• <string key="Activity" value="examine thoroughly"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Sean"/>
• <string key="Costs" value="400"/>
• </event>
• <event>
• <string key="concept:name" value="decide"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-17T12:00:00.000+01:00"/>
• <string key="Activity" value="decide"/>
• <string key="HLActivity" value="decide"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="pay compensation"/>
• <string key="org:resource" value="Ellen"/>
• <date key="time:timestamp" value="2011-01-18T12:00:00.000+01:00"/>
• <string key="Activity" value="pay compensation"/>
• <string key="HLActivity" value="pay"/>
• <string key="Resource" value="Ellen"/>
• <string key="Costs" value="200"/>
• </event>
• </trace>
• <trace>
• <string key="concept:name" value="6"/>
• <string key="creator" value="Fluxicon Nitro"/>
• <event>
• <string key="concept:name" value="register request"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2011-01-06T15:02:00.000+01:00"/>
• <string key="Activity" value="register request"/>
• <string key="HLActivity" value="register"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="50"/>
• </event>
• <event>
• <string key="concept:name" value="examine casually"/>
• <string key="org:resource" value="Ellen"/>
• <date key="time:timestamp" value="2011-01-06T16:06:00.000+01:00"/>
• <string key="Activity" value="examine casually"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Ellen"/>
• <string key="Costs" value="400"/>
• </event>
• <event>
• <string key="concept:name" value="check ticket"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2011-01-07T16:22:00.000+01:00"/>
• <string key="Activity" value="check ticket"/>
• <string key="HLActivity" value="think"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="100"/>
• </event>
• <event>
• <string key="concept:name" value="decide"/>
• <string key="org:resource" value="Sara"/>
• <date key="time:timestamp" value="2011-01-07T16:52:00.000+01:00"/>
• <string key="Activity" value="decide"/>
• <string key="HLActivity" value="decide"/>
• <string key="Resource" value="Sara"/>
• <string key="Costs" value="200"/>
• </event>
• <event>
• <string key="concept:name" value="pay compensation"/>
• <string key="org:resource" value="Mike"/>
• <date key="time:timestamp" value="2011-01-16T11:47:00.000+01:00"/>
• <string key="Activity" value="pay compensation"/>
• <string key="HLActivity" value="pay"/>
• <string key="Resource" value="Mike"/>
• <string key="Costs" value="200"/>
• </event>
• </trace>
• </log>

• Appendix 2
• Example log 2.
• <?xml version="1.0" encoding="UTF-8" ?>
• <!-- XES version 1.0 -->
• <!-- Created by Fluxicon Nitro (http://fluxicon.com/nitro/ -->
• <!-- (c) 2010 Fluxicon Process Laboratories / http://fluxicon.com/ -->
• <log xes.version="1.0" xmlns="http://code.deckfour.org/xes" xes.creator="Fluxicon Nitro">
• <extension name="Concept" prefix="concept" uri="http://code.deckfour.org/xes/concept.xesext"/>
• <extension name="Time" prefix="time" uri="http://code.deckfour.org/xes/time.xesext"/>
• <extension name="Organizational" prefix="org" uri="http://code.deckfour.org/xes/org.xesext"/>
...