Business process model discovery (BPMD) is a signi cant research topic in the business process mining area. The present BPMD techniques encounter great challenges while dealing with real-life event logs that contain complex process behaviors. As a result, non- tting process models might be obtained. In this paper, we propose a new mechanism for locating and handling the process behaviors recorded in event logs which cannot be expressed by the utilised model discovery algorithms.
As one of the most important research directions in business process mining
area, the present business process model discovery (BPMD) techniques meet
great challenges while trying to mine process models from real-life event logs
that usually stem from the business processes implemented in highly exible
environments, e.g., healthcare, customer relationship management (CRM) and
product development [
the literature for solving the problem of low- tness process models mined from real-life event logs. Such a strategy aims at improving the expressive ability of existing BPMD algorithms or developing new algorithms that are able to model more complex work ow patterns.
In this paper, we develop a new method which inherits the basic idea of mining algorithm enhancement-based strategy for assisting the present BPMD techniques in generating high- tness process models from real-life event logs. In our method, the tness improvement problem for the inaccurately mined process models is surveyed from a new perspective and rede ned as an issue of locating the inexpressible process behaviors recorded in event logs and then transforming them into expressible behaviors for the utilised BPMD algorithms. The structure of the main contents of this paper is organised as: Copyright c by the paper's authors. Copying permitted only for private and academic purposes. - In Section 2, a novel method named IDC is put forward which is able to help the employed BPMD techniques mine more tting process models from real-life logs. - In Section 3, we carry out the proposed method IDC on an example event log to test the correctness and e ectiveness of it. - In Section 4, the related work from the academia is reviewed. - In Section 5, a conclusion together with the future problems that we are going to solve are elaborated. 2
We rstly introduce a method for detecting and structuring the process behaviors from real-life event logs in Section 2.1. Afterwards, based on the method presented in Section 2.1 a heuristic technique named IDC for helping the utilised BPMD algorithms mine more tting process models is put forward in Section 2.2. 2.1
Construct Process Behavior Space (PBS) Business process behaviors from real-life event logs cannot be analysed before they are extracted and structured in an appropriate form. We solve the PBS construction problem by providing the following two concepts:
Let SA be the set of activities for event log E. Let E represents a direct relation between any two activities from SA. For instance, for two activities a; b 2 SA, a E b = true if activity a is directly followed by b at least once in E. Symbol )E represents a behavior-based relation between any two activities from SA. For two activities c; d 2 SA, c )E d = true if c E d = true or d E c = true and d is also called a behavior-related activity of c.
Let SA be the set of activities and ST be the multiset of traces for event log E. Let t 2 ST be a trace from E, st v t be a sub-trace of t and SAst be the set of activities for st. Given an activity a 2 SA, st is a behavior-related sub-trace of a if 8b 2 SAst ^ b 6= a such that a )E b and 9c 2 SAst such that c = a.
Take a simple event log E1 = f< l1; m1; n1; x1; y1; z1 >15; < l1; n1; m1; y1; z1 >15 ; < l1; m1; x1 >3; < l1; n1; m1; z1 >5g (utilised for the rest of Section 2) as an example. According to De nition 1, the activity n1 from E1 has three behavior-related activities which are activity l1, m1 and x1. Then, according to De nition 2, a set of behavior-related sub-traces f< l1; m1; n1; x1 >15; < l1; n1; m1 >20g for activity n1 can be extracted from E1. Let : (ST +; SA+; SA) ! SBT be a function for nding all of the behavior-related sub-traces for a speci c activity from a given trace, where ST + represents the set of traces, SA+ represents the set of all possible sets of behavior-related activities, SA represents the set of activities and SBT stands for the set of all possible multisets of behavior-related sub-traces. The PBS construction procedure is described in Algorithm 1. Algorithm 1 Construct the PBS for a speci c event log E (CPBS) In this subsection, we rstly de ne a new concept called activity environment item. Afterwards, a new algorithm named IDC that is able to assist in detecting and converting the inexpressible process behaviors related to one particular activity is presented.
Let SA be the set of activities from event log E, activity a, b and c are three activities from SA, the tuple (b; c) is an environment item of activity a if 9t 2 E such that < b; < a : : : >; c >v t, where t stands for a trace from E and < a : : : > represents a sub-trace that only consists of activity a.
Take the event log E1 mentioned in Section 2.1 as an example. According to De nition 3, the activity n1 2 E1 has two types of environment items which are (m1; x1) and (l1; m1). Activity l1 2 E1 also has two types of environment items that are (null; m1) (the value null indicates that l1 appears as a starting activity) and (null; n1). Let : (SA; SBT ) ! SEI+ be an environment item searching function for a speci c activity, where SA represents the set of activities, SBT represents the set of all multisets of behavior-related sub-traces and SEI+ stands for the set of all sets of environment items. Let : (SA; SEI; SBT; SNA) ! SBT be an activity conversion function, where SEI stands for the set of environment items and SNA represents the set of activity names. Given an activity, function is capable of converting this activity into a new activity (with a new name) under a certain environment in all of the behavior-related sub-traces of the given activity. For the activity n1 2 E1, given an environment item ei = (m1; x1) of n1, the set of behavior-related sub-traces BSTn1 = f< l1; m1; n1; x1 >15; < l1; n1; m1 >20g of n1 and a new activity name n1 0, (n1; ei; BSTn1 ; n1 0) = f< l1; m1; n1 0; x1 >15; < l1; n1; m1 >20g. Let SST be the set of all possible multisets of traces, : SST ! SM be a work ow discovery algorithm, where SM is the set of process models. : (SM; SST ) ! SV represents a process model tness evaluation schema with an input of a process model and its relevant set of traces and an output of an assessed value from SV (the set of all possible values output by ). The details of IDC is described in Algorithm 2.
For a speci c activity a from log E, the algorithm IDC rstly obtains the set of behavior-related sub-traces BSTa for a through step 3, the set of environment items SEIa for a by step 4 and the tness of the behavior-related model (by mining the generated set of behavior-related sub-traces BSTa) of a by step 5. Afterwards, steps 6 13 try to nd the environment item of a under which converting a into ai in the set of behavior-related sub-traces of a will help generate a behavior-related model (by mining BSTt) with maximal tness and the discovered environment item is put in eit and the value of the maximal tness is stored by f2. Then, it is checked if the tness improvement acquired is larger than or equal to a threshold by step 14. If this is the case, the environment item is put in set SEIr (step 17) which will be nally output by IDC. The original set of behavior-related sub-traces is updated (step 16) by transforming the relevant activity under the found environment which is removed from SEIa later by step 18 and IDC continues to search for the next environment item if SEIa is not empty and the tness of the new behavior-related model is less than a target value ". Otherwise, the technique IDC stops. 3
In our experiment, we utilise the Heuristics Miner (HM) [
We tested the correctness and e ectiveness of our technique by utilising an example event log Ee. As shown in Figure 1, log Ee has nine activities and 523 traces and the process model generated by implementing the HM on Ee has a low ICS tness value which is 0.7748.
In the process of our experiment, we rstly utilise the algorithm CPBS (introduced in Section 2.1) to build the PBS for log Ee. Afterwards, the algorithm IDC (introduced in Section 2.2) is used to analyse the built PBS for discovering the activities together with their relevant environment items that are the main factors to turn out the inexpressible process behaviors for HM in log Ee. The model tness threshold " is set to 1 and the model tness improvement threshold is set to 0:3 for IDC.
According to Figure 2, the method IDC nds that the activity F under environment (D; E) and (H; I) in log Ee is the key factor for generating the process behaviors that cannot be expressed by HM. With this discovery from IDC, we replace the activity F under environment (H; I) by a new activity named F0 and the activity F under environment (D; E) by using F1 in log Ee so 1 http://www.promtools.org. An Example Event Log : Ee
<A, B, C, D, F, E, G>1 <A, B, C, D, E, H, F, I, G>64 <A, B, C, F, D, E, H, I, G>78 <A, B, C, D, F, E, H, I, G>247
<A, B, C, D, E, H, I, G>3 Newly Generated Log : Ee*
<A, B, C, D, F1, E, G>1 <A, B, C, D, E, H, F0, I, G>64 <A, B, C, F, D, E, H, I, G>78 <A, B, C, D, F1, E, H, I, G>247 <A, B, C, D, E, H, I, G>3
ICS Fitness : 0.7748
D
F
Process Model Generated by Heuristics Miner A
B
C
E
H
I
G A
B
C ICS Fitness : 0.9987
Process Model Generated by Heuristics Miner
D
F1
E
H
I F0
F
G
that a new log Ee (in Figure 2) can be generated. As shown in Figure 2, a more
tting process model (with a tness value 0.9987) is output by HM executed on
the newly generated log Ee . This positive evaluation results indicate that our
technique IDC successfully locate the inexpressible process behaviors from Ee
for HM.
In the literature, several e ective techniques stemming from the mining
algorithm enhancement-based strategy have been devised. Most of these presented
techniques are developed to mine tting process models expressed by Petri net.
The authors in [
In this paper, we mainly proposed a technique IDC for helping detect and convert the inexpressible process behaviors for the utilised BPMD techniques from particular real-life event logs. Through the evaluation results from Section 3, we demonstrated the e ectiveness of our technique.
A tting model might still be complex. Our future job will be focused on designing a new trace clustering technique [2{6] that contains two steps where the rst step focuses on building sub-models with lower complexity and the second step focuses on improving the accuracy of the mined sub-models by using the technique proposed in this paper. In the meantime, we will also validate our method on some other real-life cases.