Unsupervised Event Abstraction using Pattern Abstraction and Local Process Models

Abstract

Process mining analyzes business processes based on events stored in event logs. However, some recorded events may correspond to activities on a very low level of abstraction. When events are recorded on a too low level of abstraction, process discovery methods tend to generate overgeneralizing process models. Grouping low-level events to higher level activities, i.e., event abstraction, can be used to discover better process models. Existing event abstraction methods are mainly based on common sub-sequences and clustering techniques. In this paper, we propose to rst discover local process models and, then, use those models to lift the event log to a higher level of abstraction. Our conjecture is that process models discovered on the obtained high-level event log return process models of higher quality: their tness and precision scores are more balanced. We show this with preliminary results on several real-life event logs.

Keywords

• Process Discovery
• Unsupervised Learning
• Event Abstraction

-

Process mining [ 1 ] is a fast growing research discipline that concerns the analysis of events that are logged during the execution of a business process. Recorded events contain information on what was done, by whom, where, when, etc. Such event data is often readily available from business information systems such as ERP, CRM, or, work ow management systems. Process discovery, the task of automatically generating a process model that accurately describes the business process based on the event data, plays a central role in the process mining eld. A variety of process discovery techniques have been developed over the years [ 3, 6, 9, 20 ], generating process models in di erent notations, such as Petri nets [ 15 ], EPC, and BPMN. The degree to which a discovered process model represents the event data from which is discovered is typically expressed in several quality dimensions. Two of such quality dimensions are tness: the amount of behavior in the event log that is allowed by the model and precision: the model should not be too general by allowing for much more behavior that was not seen in the event log (i.e., it should not be under tting).

For successful application of process discovery it is crucial that the events logged in the event log directly correspond to the activities that are recognizable (1) discover (3) abstract

High-level Log

(4) discover

High-level Model

(2) lter

Candidate LPMs

Filtered LPMs

for process stakeholders. In practice, this is not always the case, and there can be an n:m-relation between the recorded events and activities of the process [ 4, 8 ]. Process models that are generated by process discovery when recorded events and activities do not match have semantics that are unclear to process stakeholders. Moreover, a mismatch between events and activities can cause process discovery techniques to discover under tting process models that allow for too much behavior (i.e., process models with low precision) [ 18 ].

A recent approach to abstract recorded events to high-level activities [ 13 ] uses activity patterns to capture the domain knowledge about the relation between the high-level activities and the low-level recorded events. Each activity pattern is a process model that describes the possible behavior in terms of low-level events that are conjectured to be observed during the execution of a certain high-level activity. However, such domain knowledge might not be available, and when the process contains many activities it becomes a tedious task to model each of them manually. Local Process Model (LPM) discovery [ 17, 19 ] is a technique to automatically discover frequent patterns of process behavior (i.e., LPMs) from an event log. Each LPM, like an activity pattern, is a process model that describes the behavior over only a subset of the event types in the log.

In this paper we explore the application of automatically discovered LPMs to replace the domain knowledge in pattern-based abstraction to form a novel, completely automated, abstraction technique. Figure 1 gives an overview of the proposed method. Each LPM discovered by the LPM discovery method [ 17, 19 ] is assumed to represent a high-level activity. Then, we propose a technique to lter the set of LPMs, and use this ltered set of LPMs as activity patterns with the event abstraction method proposed in [ 13 ] and discover a high-level process model using o -the-shelf discovery methods. Our proposed, integrated approach aims to improve the precision of process models found by process discovery techniques by abstraction of the event log while not sacri cing too much tness.

In Section 2, we introduce basic concepts and notations. Section 3 explains how LPM discovery and pattern-based abstraction can be combined to form a fully automated abstraction technique. In Section 4, we present and discuss some preliminary results, and we conclude the paper and discuss future directions in Section 5.

Preliminaries

In this section we introduce concepts used in later sections of this paper. X denotes the set of all sequences over a set X and = ha1; a2; : : : ; ani a sequence of length n, with (i) = ai. hi is the empty sequence.

In the context of process logs, we assume the set of all process activities to be given. An event e in an event log is the occurrence of an activity e2 . We call a sequence of events 2 a trace. An event log L2N is a nite multiset of traces. For example, the event log L = [ha; b; ci2; hb; a; ci3] consists of 2 occurrences of trace ha; b; ci and three occurrences of trace hb; a; ci.

A process model notation that is frequently used in the process mining area is the Petri net. A labeled Petri net N = hP; T; F; `i is a tuple where P is a nite set of places, T is a nite set of transitions such that P \ T = ;, F (P T ) [ (T P ) is a set of directed arcs, called the ow relation, and ` : T 9 is a labeling function that assigns process activities to transitions. Unlabeled transitions, i.e., t2T with t62dom(l), are referred to as -transitions, or invisible transitions.

The state of a Petri net is de ned by its marking. The marking assigns a nite number of tokens to each place. Transition of the Petri net represent activities and can be executed. The input places of a transition t 2 T are all places for which there is a directed edge to the transition: fp 2 P j(p; t)2F g. The output places of a transition are de ned respectively. Executing a transition consumes one token from each of its input places and produces one token on each of its output places, i.e., the marking is changed. A transition can only be executed when there is at least one token in each of its input places.

Often it is useful to consider a Petri net in combination with an initial marking and a nal marking. This allows us to de ne the language, L(N ), accepted by Petri net N . The language of a Petri net is de ned by the set of all possible sequences of visible transition labels (i.e., ignoring -transitions) that start in the initial marking and end in the nal marking. This allows to check whether some behavior is part of the behavior of the Petri net, i.e., can be replayed on it.

Figure 2a shows an example of an accepting Petri net. Circles represent places and rectangles represent transitions. Invisible transitions are depicted as black rectangles. Places that belong to the initial marking contain a token and places belonging to a nal marking are marked as . The language of this accepting Petri net, with = fA; B; Cg is fhA; B; Ci; hB; A; Ci; hA; B; B; Ci; hB; B; A; Ci; hB; A; B; Ci; : : : g. We refer to [ 15 ] for a comprehensive introduction of Petri nets. 2.1

Local Process Models LPMs [ 19 ] are process models that describe the behavior seen in the event log only partially, focusing on frequently observed behavior. Typically, LPMs describe the behavior of only up to 5 activities. LPMs can be represented in any process modeling notation, such as BPMN, UML, or EPC. Here we use Petri nets to represent LPMs. A technique to generate a ranked collection of LPMs through iterative expansion of candidate process models is proposed in [ 19 ]. The search 2 B

(a) 1

3

Queued+Awaiting Assignment A C

Accepted+Wait Completed+Closed

σ = ,B,X,B,C,C,A,B,C,B,B,X,A,C σ {A,B,C} = ,B,B,C,C,A,B,C,B,B,A,C

λ1 γ1 Гσ,LPM = B,B,C,B,C,A,C space of process models is xed, depending on the event log. We de ne LPMS (L) as the set of possible LPMs that can be constructed for given event log L. We refer the reader to [ 19 ] for a detailed description of search space LPMS (L).

To evaluate a given LPM on a given event log L, its traces 2L are rst projected on the set of activities in the LPM, i.e., 0= . The projected trace 0 is then segmented into -segments that t the behavior of the LPM and segments that do not t the behavior of the LPM, i.e., 0= 1 1 2 2 n n n+1 such that i2L(LPM ) and i62L(LPM ). We de ne ;LP M to be a function that projects trace on the LPM activities and obtains its subsequences that t the LPM, i.e., ;LP M = 1 2 : : : n.

Let our LPM N1 under evaluation be the Petri net of Figure 2a and let = hA; B; X; B; C; C; A; B; C; B; B; X; A; C i be an example trace. Function act (LPM ) obtains the set of process activities in the LPM, e.g. act (N1) = fA; B; Cg. Projection on the activities of the LPM gives act(N1) = hA; B; B; C; C ; A; B; C; B; B; A; Ci. Figure 2b shows the segmentation of the projected traces on the LPM, leading to ;LP M = hB; B; C; B; C; A; Ci. The segmentation starts with a non- tting segment 1 = hAi, followed by a tting segment 1=hB; B; Ci, which completes one run through the model from initial to nal marking. The second event C in cannot be replayed on LP M , since it only allows for one C and 1 already contains a C. This results in a non- tting segment 2=hC; Ai.

2=hB; Ci again represents a run through the model from initial to nal marking, and 3=hB; Bi does not t the LPM. 3=hA; Ci again represents a run though the model, and we end with a empty non- tting segment 4. We lift segmentation function to event logs, L;LP M =f ;LP M j 2Lg. An alignment-based [ 2 ] implementation of , as well as a method to rank and select LPMs based on their support, i.e., the number of events in L;LP M , is described in [ 19 ]. An overview of the pattern-based abstraction method proposed in [ 13 ] is depicted in Figure 3. The input is an event log and a set of activity patterns. Each activity pattern is a process model that represents the behavior expected for one execution of a high-level activity. Moreover, a mapping from activities to life-cycle transitions of the high-level activity is required, i.e., : T 6! LT with, e.g., LT = fstart; completeg. Mapping allows to obtain information on when

Event Log

Build Abstraction

Activity Patterns Model

Aligned Log

Align Log

activities started and when they were completed, which some process discovery algorithms, such as [ 10 ], are able to leverage.

Activity patterns are composed to an abstraction model and, then, an alignment technique [ 2 ] is used to obtain a high-level event log. Through the use of the alignment technique, we can capture approximate executions of activity patterns. Then, we use the alignment information to create a corresponding high-level event log by only retaining those events that were aligned to activities t 2 T that are mapped to high-level activities, i.e., t 2 dom( ). Activity patterns may use any kind of process models with clear semantics, thus, the abstraction method also works with LPMs. For example, assume that LPM N1 represents the behavior expected for some high-level activity. Mapping function could be de ned such that the transition corresponding to A and transition 1 are mapped to start and the transition corresponding to C is mapped to complete. It is possible to automatically obtain such mapping function , e.g., by mapping the source activities to the start and the and the sink activities to the complete life-cycle transitions. 3

Unsupervised Abstraction Technique

We use discovered LPMs to replace the domain knowledge originally used in the pattern-based event abstraction method. Our proposed method discovers a high-level process model in the following four steps shown graphically in Fig. 1. 1. We discover a xed number of candidate LPMs based on the ranking proposed in [ 19 ]. The LPM ranking proposed in [ 19 ] is based on support (i.e., frequency). When setting the number of LPMs to use for abstraction to k, we select the top k LPMs of the discovered ranking of LPMs R. For event logs with large numbers of activities the original LPM discovery algorithm [ 19 ] becomes computationally infeasible. For such logs, faster, approximate, techniques for discovering LPMs can be applied [ 17 ]. 2. The LPMs in ranking R can overlap in the activities that they describe.

For the purpose of event abstraction this can be undesirable, because this results in multiple similar patterns for pattern-based abstraction, making it unclear which low-level event belongs to which high-level activity. Therefore, we introduce a diversity score for the i-th LPM of LPM ranking R as: div (R; i)= (

jact(R(i))\act(R(j))j maxij=11 jact(R(i))j+jact(R(i))j jact(R(i))\act(R(j))j if i > 1; 1 if i = 1: Based on this de nition of diversity we introduce a diversity threshold tdiv to lter out all LPMs from R where div (R; i) tdiv . This lter removes LPMs from R when there is a stronger LPM, higher in ranking R, that describes (almost) the same set of activities. 3. We use those LPMs as activity patterns and obtain a high-level event log with the abstraction method described in [ 13 ]. In work [ 13 ] several composition functions are presented that allow ne grained control of the interaction between activities. In our case, we do not assume any domain knowledge on the process, thus, we limit the choice of composition parameter for our method to: interleaving and parallel. Interleaving means that any two high-level activities cannot occur at the same time, whereas parallel means that no such restriction is placed. 4. Based on the high-level event log, we discover a high-level process model using existing methods such as the Inductive Miner (IM) [ 9 ].

For example, take LPM N1 shown in Fig. 2 and assume that we apply the proposed method to trace . We assume that LPM N1 represents the behavior of some high-level activity H. Three executions (i.e., -segments) of the LPM N1 are present in trace , thus, the high-level activity H was executed three times. When applying pattern-based abstraction, we obtain the high-level trace hH; H; Hi1. Some low-level events in could not be matched to a high-level activity, e.g., the rst event of the trace: A. Since we cannot assume that the discovered LPMs represent the entire behavior of the process, we add all those low-level events to the resulting trace. Therefore, we use the trace hA; H; C; A; H; B; B; H i, which contains less events than the original trace , for discovery.

Note that our technique does not discover the names of the high-level activities represented by the LPMs. However, LPMs can be labeled to its corresponding business activity based on domain knowledge. 4

Preliminary Results and Discussion

To be able to deal with the computational complexity of LPM mining for logs with many activities, we discover LPMs using activity clustering based on Markov clustering, as proposed in [ 17 ]. As proposed in [ 14 ], we expand high-level activities in the discovered process model with the corresponding LPMs to provide a fair comparison based on the low-level event log. The resulting expanded process model can be related to the low-level events with existing techniques that determine the models quality in terms of tness and precision [ 2 ]. We evaluate the quality of the expanded process models in terms of F-score [ 7 ], i.e., the harmonic mean between tness and precision. 1 The abstraction technique also provides events for the start and complete life-cycle transitions. So far, we only use the complete transition. Diversity threshold 0.5 0.6 0.2 0.3 0.4 0.7 0.8 0.9

B P I 1 3 − C S e p s i s R o a d F i n e s C o s e l o g B P I 1 3 − I composition

Interleaved Parallel

Figure 4 shows the F-score of the process models discovered with the IM infrequent [ 9 ] process discovery algorithm with 20% noise ltering. Horizontally it shows the results for di erent LPM diversity thresholds (0.2 to 0.9). Vertically it shows the results for ve di erent event logs: the BPI challenge 2013 incidents (I) and closed problems (C) log[ 16 ], the CoSeLoG receipt phase log [ 5 ], the road nes log [ 11 ], and the sepsis log [ 12 ]. The results are shown for 1 to 5 LPMs used in abstraction and parallel and interleaving composition. The dotted line indicates the F-score of the process model discovered from the original event log, i.e., without abstraction.

Figure 5 shows an expanded process model that is discovered for the BPI13-C log based on the proposed method. The LPM N1 was used as activity pattern and is part of the process model. Thus, the process model can hierarchically decomposed into sub-processes based on the activity patterns. Its precision score is improved from 0.53 to 0.86 at the expense of tness, which drops from 0.84 to 0.65. The F-score improved from 0.65 to 0.74.

In our preliminary results we found that for three out of ve event logs the F-score of the process model can be improved by abstracting the event log prior to process discovery. Furthermore, it seems that abstracting with parallel composition does only improve the process model over abstraction with interleaving composition in one case, which is bene cial since the interleaving composition is computationally less expensive. The optimal number of LPMs used for abstraction di ers between event logs, with the optimal number of LPMs being 5 for the sepsis log and 1 for the BPI13-C log. To make an abstraction technique based on LPM discovery and pattern-based abstraction fully automated, further experimentation would be needed. We need to analyze whether the optimal number of LPMs depends on properties of the event log and for which logs the good results can be expected. 5

Conclusions and Future Work

In this paper we have described a technique to abstract an event log to a higherlevel event log using Local Process Model (LPM) discovery and pattern-based abstraction. We have shown on ve real life event logs that the abstraction approach applied prior to process discovery can result in more precise process models.

We found that (1) the number of LPMs that should be used for abstraction, (2) the diversity threshold, and (3) the composition method which result in good process models being discovered are very dependent on the event log on which the technique is applied. In future work, we want to investigate this interplay between event log properties and the parameters of the abstraction approach that are needed to discover process models that strike a good balance between precision and tness. We aim to apply this insight in the relation between parameters settings of the abstraction technique and properties of the event log in a technique that can abstract an event log completely automatically, where no manual parameter setting is needed.

References

1. van der Aalst , W.M.P. : Process mining: data science in action . Springer ( 2016 )

2. van der Aalst , W.M.P. , Adriansyah , A., van Dongen , B.F. : Replaying history on process models for conformance checking and performance analysis . WIREs Data Min. Knowl. Discovery 2 ( 2 ), 182 { 192 ( 2012 )

3. van der Aalst , W.M.P. , Weijters , T. , Maruster , L. : Work ow mining: Discovering process models from event logs . IEEE Trans. Knowl. Data Eng . 16 ( 9 ), 1128 { 1142 ( 2004 )

4. Baier , T. , Mendling , J.: Bridging abstraction layers in process mining by automated matching of events and activities . In: BPM, LNCS , vol. 8094 , pp. 17 { 32 . Springer ( 2013 )

5. Buijs , J.: Receipt phase of an environmental permit application process (WABO), CoSeLoG project . Eindhoven University of Technology. Dataset ( 2014 ), http: //dx.doi.org/10.4121/uuid: a07386a5 -7be3- 4367 - 9535 -70bc9e77dbe6

6. Conforti , R. , Dumas , M. , Garc a-Ban~uelos, L., La Rosa , M.: BPMN miner: automated discovery of BPMN process models with hierarchical structure . Information Systems 56 , 284 { 303 ( 2016 )

7. De Weerdt , J. , De Backer , M. , Vanthienen , J. , Baesens , B. : A robust F-measure for evaluating discovered process models . In: CIDM . pp. 148 { 155 . IEEE ( 2011 )

8. Gunther, C.W. , Rozinat , A., van der Aalst , W.M.P. : Activity mining by global trace segmentation . In: BPM . pp. 128 { 139 . Springer ( 2009 )

9. Leemans , S.J.J. , Fahland , D., van der Aalst, W.M.P. : Discovering block-structured process models from event logs containing infrequent behaviour . In: BPM. LNBIP , vol. 171 , pp. 66 { 78 . Springer ( 2013 )

10. Leemans , S.J.J. , Fahland , D., van der Aalst, W.M.P. : Using life cycle information in process discovery . In: BPM. LNBIP , vol. 256 , pp. 204 { 217 . Springer ( 2015 )

11. de Leoni, M. , Mannhardt , F. : Road tra c ne management process . Eindhoven University of Technology. Dataset ( 2015 ), http://dx.doi.org/10.4121/uuid: 270fd440-1057 - 4fb9 - 89a9-b699b47990f5

12. Mannhardt , F. : Sepsis cases - event log . Eindhoven University of Technology. Dataset ( 2016 ), http://doi.org/10.4121/uuid: 915d2bfb -7e84 - 49ad - a286-dc35f063a460

13. Mannhardt , F., de Leoni , M. , Reijers , H.A., van der Aalst , W.M. , Toussaint , P.J.: From low-level events to activities - a pattern-based approach . In: BPM. LNCS , vol. 9850 , pp. 125 { 141 . Springer ( 2016 )

14. Mannhardt , F., de Leoni , M. , Reijers , H.A., van der Aalst , W.M. , Toussaint , P.J.: Guided process discovery - a pattern-based approach . Information Systems (submitted)

15. Reisig , W.: Petri nets: an introduction , vol. 4 . Springer ( 2012 )

16. Steeman , W.: BPI challenge 2013 . Ghent University. Dataset ( 2013 ), http://dx. doi.org/10.4121/uuid: a07386a5 -7be3- 4367 - 9535 -70bc9e77dbe6

17. Tax , N. , Sidorova , N., van der Aalst , W.M.P. , Haakma , R.: Heuristic approaches for generating local process models through log projections . In: CIDM . pp. 1 { 8 . IEEE ( 2016 )

18. Tax , N. , Sidorova , N. , Haakma , R., van der Aalst, W.M.P. : Event abstraction for process mining using supervised learning techniques . In: IntelliSys. IEEE ( 2016 )

19. Tax , N. , Sidorova , N. , Haakma , R., van der Aalst, W.M.: Mining local process models . Journal of Innovation in Digital Ecosystems 3 ( 2 ), 183 { 196 ( 2016 )

20. van der Werf , J.M.E.M. , van Dongen , B.F. , Hurkens , C.A.J. , Serebrenik , A. : Process discovery using integer linear programming . Fundamenta Informaticae 94 ( 3 ), 387 { 412 ( 2009 )