Local Process Models (LPMs) describe structured fragments of process behavior occurring in the context of less structured business processes. In contrast to traditional support-based LPM discovery, which aims to generate a collection of process models that describe highly frequent behavior, High-Utility Local Process Model (HU-LPM) discovery aims to generate a collection of process models that provide useful business insights by specifying a utility function. Mining LPMs is a computationally expensive task, because of the large search space of LPMs. In supportbased LPM mining, the search space is constrained by making use of the property that support is anti-monotonic. We show that in general, we cannot assume a provided utility function to be anti-monotonic, therefore, the search space of HU-LPMs cannot be reduced without loss. We propose four heuristic methods to speed up the mining of HU-LPMs while still being able to discover useful HU-LPMs. We demonstrate their applicability on three real-life data sets.
Process Mining [
Recently, Local Process Model (LPM) discovery [
A recent trend in the frequent pattern mining field is to take the relative
importance of the activities in the log into account in the knowledge discovery
process. This results in the discovery of patterns that address business concerns,
e.g. high financial costs, instead of the discovery of simply the most frequent
patterns. In previous work we introduced high-utility local process models
(HULPMs) [
To deal with the computational complexity of searching patterns with such
a rich set of constructs that are supported by LPMs (i.e., sequential orderings,
parallel blocks, loops, choices), a support-based pruning strategy [
In this paper we propose four different heuristic approaches to prune the
search space of the HU-LPM discovery task. We perform experiments on three
different logs and show that our approaches speed up the discovery of HU-LPMs,
while still being able to discover useful HU-LPMs. The techniques described in
this paper have been implemented in the ProM process mining framework [
This paper is organized as follows. Section 2 describes related work. Section 3 introduces the basic concepts used in this paper. In Section 4, we introduce the four heuristic approaches for HU-LPM mining. We discuss the experimental setup and experimental results in Section 5. Finally, we conclude and discuss future areas of research in Section 6. 2
In the pattern mining discipline, the limitations of support-based mining have
become apparent in recent years, and as a result the interest has grown in
highutility patterns; i.e., patterns providing useful business insight. This has led to an
increasing number of methods and techniques that address the high-utility mining
1 https://svn.win.tue.nl/repos/prom/Packages/LocalProcessModelDiscovery/
(HUM) problem [
The utility in sequential patterns is regarded to be the sum of the utility of the activities that fit the sequential pattern. The majority of pruning strategies that are used in HUM algorithms are based on Transaction-Weighted Utility (TWU). The TWU of a pattern X is the sum of utilities of the sequences containing X, resulting in an upper bound for the utility of pattern X that can be computed efficiently. In case the TWU of a pattern X does not meet a predefined minimum threshold, X can be safely pruned since its actual utility can only be lower than or equal to TWU. In traditional HUM algorithms, the utility function is defined on the activity level; i.e., each activity in the dataset is given a utility and the utility of a pattern is the sum of all activity utilities. Therefore, TWU and other activity-based pruning strategies can be used for efficient pruning for HU-LPM mining when utility is defined on the activity level. However, utility functions of HU-LPMs are defined in a more general way, allowing utility for example to depend also on event attributes or trace attributes instead of the activity. Therefore, TWU cannot be used to prune the search space of HU-LPMs. With sequence-based pruning strategies being inapplicable in HU-LPM mining, we investigate in this paper utility-based heuristics. 3
In this section we introduce notations related to event logs, Local Process Models (LPMs) and High-Utility Local Process Models (HU-LPMs) which are used in later sections of this paper. 3.1
X∗ denotes the set of all sequences over a set X and σ = ha1, a2, . . . , ani a sequence of length n, with σ(i) = ai and |σ| = n. hi is the empty sequence and σ1σ2 is the concatenation of sequences σ1 and σ2. We denote with σ X the projection of sequence σ on set X, e.g., for σ = ha, b, ci, and X = {a, c}, σ X = ha, ci.
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 e∈Σ. We call a sequence of events σ∈Σ∗ a trace. An event log L∈NΣ∗ is a finite 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. We lift projection of sequences to multisets of sequences, e.g., L {a,c} = [ha, ci5]. 3.2
LPMs [
A process tree is a tree structure where leaf nodes represent activities. The non-leaf nodes represent operators, which specify the allowed behavior over the activity nodes. Allowed operator nodes are the sequence operator (→) that indicates that the first child is executed before the second, the exclusive choice operator (×) that indicates that exactly one of the children can be executed, the concurrency operator (∧) that indicates that every child will be executed but allows for any ordering, and the loop operator ( ), which has one child node and allows for repeated execution of this node. L(LPM ) represents the language of process tree LPM , i.e., the set of sequences allowed by the model. Figure 1d shows an example process tree M4, with L(M4 )={hA, B, Ci, hA, C, Bi, hD, B, Ci, hD, C, Bi}. Informally, it indicates that either activity A or D is executed first, followed by the execution of activities B and C in any order.
A technique to generate a ranked collection of LPMs through iterative
expansion of candidate process trees is proposed in [
Figure 1 illustrates the expansion procedure, starting from the initial LPM M1 of Figure 1a. The LPM of Figure 1a is first expanded into a larger LPM by replacing A by operator node →, with activity A as its left child node and B its right child node, resulting in the LPM of Figure 1b. Note that M1 can also be expanded in other ways, and LPM discovery recursively explores all possible process trees that meet a support threshold by iterative expansion. In a second expansion step, activity node B of the LPM of Figure 1b is replaced by operator node ∧, with activity B as its left child and C its right child, resulting in Figure
time cost 26-3-2017 13:00 e 100 26-3-2017 13:27 e 200 26-3-2017 13:25 e 300 26-3-2017 13:35 e 100 26-3-2017 13:42 e 400 26-3-2017 15:47 e 200 26-3-2017 16:10 e 100 26-3-2017 16:34 e 400 26-3-2017 16:52 e 300 26-3-2017 16:59 e 200 26-3-2017 17:13 e 1000 26-3-2017 17:15 e 1000 26-3-2017 17:16 e 150 σ = ,D,B,C,D,C,A,C,B,D,A,B,A σ {A,B,C} = ,B,C,C,A,C,B,A,B,A Гσ,LPM = λ1 γ1 λ2 γ2 ,B,C,A,C,B (b) 1c. Finally, activity node A of the LPM of Figure 1c is replaced by operator node × with as left child activity A and as right child activity D, forming the LPM of Figure 1d. In traditional LPM discovery the expansion procedure of an LPM stops when the behavior described by the LPM is not observed frequently enough in an event log L (i.e., with regard to some support threshold ).
To evaluate a given LPM on a given event log L, its traces σ∈L are first projected on the set of activities X in the LPM, i.e., σ0 = σ X . The projected trace σ0 is then segmented into γ-segments that fit the behavior of the LPM and λsegments that do not fit the behavior of the LPM, i.e., σ0=λ1γ1λ2γ2 · · · λnγnλn+1 such that γi∈L(LPM ) and λi6∈L(LPM ). We define Γσ,LP M to be a function that projects trace σ on the LPM activities and obtains its subsequences that fit the LPM, i.e., Γσ,LP M = γ1γ2 . . . γn.
Let our LPM M3 under evaluation be the process tree of Figure 1c and
let σ be the example trace shown in Figure 2a. Function Act (LPM ) obtains
the set of process activities in the LPM, e.g. Act (M3) = {A, B, C}. Projection
on the activities of the LPM gives σ Act(M3) = hA, B, C, C, A, C, B, A, B, Ai.
Figure 2b shows the segmentation of the projected trace on the LPM, leading to
Γσ,LP M = hA, B, C, A, C, Bi. The segmentation starts with an empty non-fitting
segment λ1, followed by a fitting segment γ1=hA, B, Ci, which completes one
run through the process tree. 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-fitting segment λ2=hCi. γ2=hA, C, Bi again represents a run through
process tree, the segmentation ends with non-fitting segment λ3=hA, B, Ai. We lift
segmentation function Γ to event logs, ΓL,LP M ={Γσ,LP M |σ∈L}. An
alignmentbased [
Several metrics are taken into account to assess the quality of an LPM, but all
of them are support-based and depend on the number of events in ΓL,LP M . We
refer the reader to [
Definition 1. Local Process Model Mining Problem: Given an event log L, the LPM mining problem is defined as the task of discovering a set of frequent LPMs, where the total number of fragments replayable is above a defined threshold. 3.3
A High-Utility Local Process Model (HU-LPM) is an LPM where (i) its
importance is related to the utility of the fragments it can replay instead of the
number of fragments it can replay and (ii) where this utility is above a predefined
threshold. Note that HU-LPMs are a generalization of LPMs, as we have shown
in [
Event this class of utility functions can be used when the interest is focused on some event properties, but does not concern the trace-context of those events. Example of event-level utility function is the search for LPMs describing process fragments with high financial cost.
Activity defines the utility of an LPM based on the frequency of occurrences of each activity. It can be used when the analyst is more interested in some activities with high impact (e.g. lawsuits, security breaches, etc.). This scope if generally the one used in traditional pattern mining algorithms, allowing for the definition of upper bounds to efficiently prune the search space without loss.
Model this class of utility functions is not log-dependent, but allows the analyst to specify preferences for specific structural properties of the LPM.
Functions on the different scopes can be combined to form composite
functions, consisting of component functions on one of the scopes above. The utility
of an LPM M over an event log L is denoted u(L, M ), and we define as HU-list a
collection of HU-LPMs sorted in descending order according to their utility, with
|S| the number of HU-LPMs in HU-list S. For a more thorough introduction of
HU-LPMs and related concepts, we refer the reader to [
In contrast to regular Local Process Model (LPM) mining, High Utility LPM
(HU-LPM) mining cannot be performed with techniques that prune the search
space based on frequency, leading to a large search space. Therefore, there is
a need for an alternative pruning strategy for HU-LPM mining that makes
mining possible on larger logs, however the utility metric as defined in [
Property 1. ∃M∈M(∃M0∈Exp(M)u(L, M 0)<u(L, M ) ∧ ∃M0∈Exp(M)u(L, M 0)≥u(L, M )).
We show that anti-monotonicity does through the following counter-example. Let M1, M2, M3 and M4 be the four LPMs shown in Figure 1, with M2∈Exp(M1), M3∈Exp(M2), and M4∈Exp(M3). Let event log L consist of the single trace shown in Figure 2a, and let the utility be the sum of the cost attributes of the events that belong to replayable fragments. This results in utilities u(L, M1)=1350, u(L, M2)=2800, u(L, M3)=1300 and u(L, M4)=1400. It is easy to see that utility is not anti-monotonic, as u(L, M3)<u(L, M2), but u(L, M4)>u(L, M3). This leads to non-optimal HU-LPMs when we prune using a minimum utility threshold, e.g., stopping criterion c : u(L, M )≥1350 leads to M3 not being expanded because its utility is below the threshold, while the utility of M4 would have again been above the threshold. This is mainly explained by the fact that the utility added by the new activity does not compensate for the utility lost because of the fragments that do not fit the new LPM but that did fit the previous LPM. Definition 2. High-Utility Local Process Model Mining Problem: Given an event log L, the HU-LPM mining problem is defined as the task of discovering a set of LPMs with utility above a predefined threshold umin , i.e., u(L, LPM )≥umin .
In High-Utility Local Process Model (HU-LPM) discovery, the size of the search space grows combinatorially with the number of activities. Reducing the search space is an inevitable step to ensure efficiency or even to enable to algorithm to run in acceptable time. We have shown that the utility metric is not anti-monotonic and that we therefore cannot reduce the search space without loss. However, heuristics can be used to reduce execution time, without formal guarantee of finding an optimal solution; i.e., the discovered set of LPMs fulfilling the utility threshold might be incomplete.
The remainder of this section is as follows. We define new concepts related to HU-LPMs in Section 4.1, we introduce two memoryless heuristics in Section 4.2, and introduce two memory-based heuristics in Section 4.3. Par i(M ) = (Par i−1(Par (M )) if i > 1,
if i = 0.
For example, for the process trees of Figure 1, Par 3(M4)=M1. Note that M ∈/ dom(Par ) for LPMs M ∈ M that are initial LPMs, as initial LPMs have no parent LPM defined. Furthermore, we define it nb(M ) as the number of expansions to reach HU-LPM M from an initial HU-LPM; e.g. it nb(M3)=2. Formally:
M (0, (1) (2) Let M ∈M be a HU-LPM, then Par (M ) denotes the parent of m; Par (M )=M 0∈M such that M ∈Exp(M 0). For example, for the process trees of Figure 1, Par (M3) = M2. We generalize the concept of parent in Equation 1, and define Par i(M ) as the ith parent of M , with Par 0(M ) = M , Par 1(M ) = Par (M ), Par 2(M ) = Par (Par (M )) and so forth; In general, we define Par i(M ) as: it nb(M ) =
if M ∈/dom(Par ), it nb(Par (M )) + 1, if M ∈dom(Par ).
Using Par and it nb we define Anc(M ) as the set of ancestors of the LPM it nb(M) M ; Anc(M ) = S Par i(M ). For example for the process trees of Figure 1, i=1 Anc(M4)={M1, M2, M3}.
Based on these definitions, we now introduce four heuristics to reduce the execution time of HU-LPM mining. 4.2
This first type of heuristics focuses on local comparisons, i.e., an LPM is only compared with its parent, the previous expansions are not considered. The heuristics work as follows: for a defined number of successive extensions (noted k, such that 0<k<exp max), the new LPM is allowed to have a utility lower than or equal to the utility of its parent.
For each heuristic, we define a continuation criterium function, ctn(L, k, M ), which results to 1 if the k most recent expansion steps leading to LPM M meet the requirements of the heuristic, indicating that M should be expanded further. Otherwise, function ctn results to 0, indicating that M should not be expanded further, therefore reducing the search space and speeding up the discovery of HU-LPMs. We introduce heuristic h1, that formalizes the function ctn(L, k, M ) as defined above: – Heuristic 1 (h1): The expansion of LPM M ∈ M is stopped if all LPMs from the k−1th parent of M to M itself have a utility lower or equal to the utility of its parent. ctn(L, k, M )= 1− (u(L, Pari(M))≤u(L, Pari+1(M))), if it nb(M)≥1 otherwise.
(3) otherwise.
(4) Note that (u(L, Par i(M ))≤u(L, Par i+1(M )) is a boolean expression that evaluates to 1 when true and evaluates to 0 when false. As we want initials LPMs to always be expanded independently of any heuristic, ctn(L, k, M ) = 1 when it nb(M ) = 0, and the function defined by each heuristic otherwise. We additionally propose heuristic h2, a relaxed version of h1, where the expanded LPM is always allowed to have the same utility as its parent: – Heuristic 2 (h2): The expansion of LPM m ∈ M is stopped if all LPMs from the k−1th parent of M to M itself have a utility strictly lower than the utility of their parents. 4.3
The second type of heuristics keeps in memory the set of LPMs produced by the successive expansions. Instead of comparing two successive expansions, it compares an extension with its best ancestor. For an LPM M , we define B(L, M ) as the highest utility among the ancestors of M in event log L; B(L, M )=u(L, M 0) of LPM M 0∈Anc(M ) such that @M00∈Anc(M) : u(L, M 00)>u(L, M 0). The heuristics work as follows: for a defined number of successive expansions (noted k, such that 0<k<exp max), the expanded LPM is allowed to have a utility lower than or equal to the utility of its best ancestor.
We introduce heuristic h3, that formalizes the function ctn(L, k, M ) as defined above: – Heuristic 3 (h3): The expansion of LPM M ∈ M is stopped if all LPMs from the k−1th parent of M to M itself have a utility lower or equal to the highest utility among their ancestors.
We also propose heuristic h4, a relaxed version of h3, where the expanded LPM is always allowed to have the same utility as its best ancestor: – Heuristic 4 (h4): The expansion of LPM M ∈ M is stopped if all LPMs from the k−1th parent of M to M itself have a utility strictly lower than the highest utility among their ancestors.
To illustrate these four heuristics, let the plot in Figure 3a be our running example. Let sqi represent a sequence of expansions from an initial LPM, and sqi,j be the jth LPM of that sequence of expansions sqi. For each heuristic and k = 2, Figure 3b presents the sequences that would be expanded until the fourth step (marked with X) and those that would be stopped before (marked with 7).
Here, sq1 and sq5 are two extremes. While sq1 contains two successive utility decreases (sq1,2 and sq1,3), sq5 contains only LPMs having a higher utility at each expansion. In consequence, every heuristic would have stopped sq1 after sq1,3; removing further expansions from the search space, and would have expanded sq5 until sq5,4. Sq2 is only expanded until the fourth step by h2 because this relaxed version allows for the utility to stagnate during 2 steps after a first decrease. On the contrary, the expansion of sq4 is only stopped by h3 because the utility obtained in the first step remains higher than the ones obtained at each further step. Finally, sq3 is expanded until the fourth step by the memoryless heuristics but stopped by the memory-based heuristics because the increase at sq3,3 is enough for the utility of the expansion to be higher than the utility of its parent, but not enough to be at least equal to the utility of its best ancestor.
Heuristic h2 is the most permissive as an LPM is only compared with its parent and can have the same utility. On the contrary, Heuristic h3 is the most restrictive as a LPM is compared with its best ancestor and must have a higher utility. As heuristics are approximate methods, some LPMs will be wrongly pruned. In the example in Figure 3, the expansion line sq4 would have been pruned by heuristic h1 after sq4,3. However, we notice that the LPM produced in the next expansion has a utility higher than the best ancestor. This is an example of expansion line that shouldn’t have been stopped. Therefore, a good strategy will be a compromise between the number of good HU-LPMs we allow to loose and how small the search space has become thanks to the pruning methods. 5
In this section we evaluate the four heuristic HU-LPM mining approaches. We detail the experimental setup in Section 5.1 and discuss the results in Section 5.2. 5.1
We evaluate the four HU-LPM discovery heuristics using three event logs: the
BPI’13 closed problems log, consisting of 1487 traces and 6660 events, the BPI’13
open problems log, consisting of 819 traces and 2351 events, and an artificial log
used in the Process Mining book [
For each event log we first apply the HU-LPM discovery algorithm without any pruning, generating the desired list of HU-LPMs in terms of quality and leading to the worst case number of LPMs that are explored. As a next step, we discover HU-LPMs with each of the four different heuristic strategies, and {1, 2, 3} the values of parameter k, i.e. the number of expansions allowed not to meet the heuristic utility requirements. We limit the LPM expansion procedure to four successive expansions, i.e., exp max = 4, to be able to perform the experiments within reasonable time. We compare the number of explored LPMs using the heuristics with the number of LPMs explored when no pruning was applied. We do the same with execution times. A lower fractions of explored LPMs with pruning compared to the number of LPMs explored without pruning represents higher speedup in HU-LPM mining.
As shown in Section 4, the heuristics might prevent the discovery of HU-LPMs
with high utility, leading to HU-lists of lower quality. Let Sa = hM1, M2, . . . , Mni
be the HU-list obtained using heuristic a. We define Sid as the ideal HU-list; i.e.,
the HU-list extracted without any pruning. To assess the efficiency of the four
heuristics, we compare the HU-list extracted with the heuristics with the ideal
HU-list obtained with the existing HU-LPM mining technique [
p 2reli − 1 DCGp = X
i=1 log2(i + 1) nDCGp =
IDCG is defined as the DCG obtain the optimal ranking, which is the ideal HU-list in our example. Equation 8 defines nDCG based on the DCG of a ranking and the IDCG of the respective ideal ranking.
We limit the nDCG calculation to the p first HU-LPMs in the ranking. The upper bound of p is the cardinality of the HU-list Sa obtained with pruning, i.e., 0<p≤|Sa |. 5.2
The results of the experiments are shown in Figure 4. Figure 4c shows the nDCG values obtained for the three event logs, the four heuristics and the three values of k. The x-axis of each plot represents the p value used to compute nDCG@p, represented on the y-axis. Table 4a presents the number of LPMs generated by the different heuristics and the mining algorithm without any pruning. We also present in Table 4b the execution times in seconds of each mining. Setting parameter k to 1 leads to the largest reduction of search space for each heuristic, therefore resulting in the highest speedup. Furthermore, the nDCG values show that k=1 still results in the extracton high-quality HU-LPM rankings on two of the three datasets: the BPI’13 closed problems and the example log. The BPI’13 Open Problems dataset however shows that in some cases k = 1 leads to overly aggressive pruning, preventing LPMs with high utility from being found, and leading to low quality HU-LPM rankings. For the BPI’13 closed problems log heuristic h1 with k = 1 decreases the search space from 1771 LPMs to 512 LPMs (more than three times less), resulting in a computation speedup of 17x at best (from 11.9s to 0.7s). At the same time heuristic h1 with k = 1 on this log results (a)
BPI'13 Closed Problems
Log no pruning heur. k=1 k=2 k=3 Closed 28.3 h1 3.3 17.5 26.9 Closed 28.3 h2 5.2 20.5 30.3 Closed 28.3 h3 3.1 11.8 29.1 Closed 28.3 h4 5.6 19.7 27.4 Open 11.9 h1 0.7 6.1 10.5 Open 11.9 h2 0.9 7.3 11.0 Open 11.9 h3 1.2 3.0 13.5
Open 11.9 h4 1.2 3.4 12.2 Example 2.9 h1 0.7 2.7 3.2 Example 2.9 h2 1.5 2.8 2.9 Example 2.9 h3 0.7 2.4 3.2 Example 2.9 h4 1.8 2.8 3.5
(b) BPI'13 Open Problems
Example
(c) Fig. 4. (a) The number of HU-LPMs generated and (b) the execution times (in seconds) per combination of heuristic, event log, and value for parameter k. (c) The nDCG results of the four heuristics applied on the three logs. in an nDCG score of above 0.8 for all values of p, showing that high-quality HU-LPMs are still being found. We observe only minor differences between the four heuristics on the BPI’13 closed problems log and the example log in terms of quality of the HU-list, even if the memory-based heuristics perform better in terms of number of LPMs generated and execution time. However, on the BPI’13 open problems log there is a sizable difference in the quality of the obtained HU-list between heuristics h1 and h2 on the one hand and heuristics h3 and h4 on the other hand. On this log, heuristics h1 and h2 prune only around 10% of the LPM search space with a speed up of 2x in the execution time, and find a HU-list that is very close to the ideal HU-list for k=2. Heuristics h3 and h4, however, prune almost half of the search space for k=2 with a speed up of 4x in the execution time, and the resulting HU-list contains a couple of high-utility HU-LPMs, but the nDCG score drops below 0.7 for p=10, indicating that these heuristics where not able to discover more than 10 useful HU-LPMs.
We observe that the speed-up in terms of time is consistently higher than what would be expected based on the share of LPMs that are removed from the search space. We expect that this effect is caused by larger LPMs, generated in later expansion iterations, that are pruned more often than the small LPMs, causing a drop in the average evaluation time per LPM next to the reduction in search space in terms of number of LPMs. Moreover, the computation time of the memory-based heuristics becomes most of the time higher than the computation time of HU-LPM mining without any pruning with k=3, which is caused by the additional comparison procedure that the traditional mining technique does not perform. 6
In this paper we have shown that the High-Utility Local Process Model (HULPM) mining problem is not anti-monotonic when event-level or trace-level utility functions are used. We introduced four heuristics to reduce the search space and speed up the mining of HU-LPMs. We have shown that the heuristics that we propose still result in the extraction of high-quality rankings of HU-LPMs, while speeding up the mining process up to a factor 17. On larger logs, where mining becomes computationally infeasible without pruning the search space, the proposed heuristics enable the discovery of HU-LPMs.
We have shown in the experiments that the efficiency of the heuristics is log-dependent. In future work, we intend to investigate the properties of the event logs that are responsible for these differences. Based on this we aim at building an automated technique for choosing the appropriate heuristic and the value of k based on the log that results in a good trade-off between computation time of the mining and the quality of discovered HU-LPMs.