Event data can be found in any information system and provide the starting point for a range of process mining techniques. The widespread availability of large amounts of event data also creates new challenges. Existing process mining techniques are often unable to handle \big event data" adequately. Decomposed process mining aims to solve this problem by decomposing the process mining problem into many smaller problems which can be solved in less time, using less resources, or even in parallel. Many decomposed process mining techniques have been proposed in literature. Analysis shows that even though the decomposition step takes a relatively small amount of time, it is of key importance in nding a high-quality process model and for the computation time required to discover the individual parts. Currently there is no way to assess the quality of a decomposition beforehand. We de ne three quality notions that can be used to assess a decomposition, before using it to discover a model or check conformance with. We then propose a decomposition approach that uses these notions and is able to nd a high-quality decomposition in little time.
Process mining aims to discover, monitor and improve real processes by
extracting knowledge from event logs readily available in today's information systems
[
The problem is that there is currently no clear way of determining the quality of a given decomposition of the events in an event log, before using that decomposition to either discover a process model or check conformance with. The current decomposition approaches do not use any quality notions to create a decomposition. Thus, potential improvements lie in nding such quality notions and a decomposition approach that uses those notions to create a decomposition with.
The remainder of this paper is organized as follows. In Section 2 related work is discussed brie y. Section 3 introduces necessary preliminary de nitions for decomposed process mining and the generic decomposition approach. Section 4 introduces decomposition quality notions to grade a decomposition upon, and two approaches that create a high quality decomposition according to those notions. Section 5 shows a (small) use case. The paper is concluded with views on future work in Section 6. 2
Little work has been done on the decomposition and distribution of process
mining problems [3{5]. In [
This section introduces the notations needed to de ne a better decomposition
approach. A basic understanding of process mining is assumed [
Multisets are de ned as sets where elements may appear multiple times. B(A) is the set of all multisets over some set A. For some multiset b 2 B(A), and element a 2 A, b(a) denotes the number of times a appears in b. For example, take A = fa; b; c; dg: b1 = [] denotes the empty multiset, b2 = [a; b] denotes the multiset over A where b2(c) = b2(d) = 0 and b2(a) = b2(b) = 1, b3 = [a; b; c; d] denotes the multiset over A where b3(a) = b3(b) = b3(c) = b3(d) = 1, b4 = [a; b; b; d; a; c] denotes the multiset over A where b4(a) = b4(b) = 2 and b4(c) = b4(d) = 1, and b5 = [a2; b2; c; d] = b4. The standard set operators can be extended to multisets, e.g. a 2 b2, b5 n b2 = b3, b2 ] b3 = b4 = b5, jb5j = 6
A sequence is de ned as an ordering of elements of some set. Sequences are used to represent paths in a graph and traces in an event log. S(A) is the set of all sequences over some set A. s = ha1; a2; : : : ; ani 2 S(A) denotes a sequence s over A of length n. Furthermore: s1 = h i is the empty sequence and s1 s2 is the concatenation of two sequences.
For example, take A = fa; b; c; dg: s1 = ha; b; bi, s2 = hb; b; c; di, s1 ha; b; b; b; b; c; di s2 =
Let f 2 X 6! Y be a (partial) function and Q X. f Q denotes the projection of f on Q: dom(f Q) = dom(f ) \ Q and f Q(x) = f (x) for x 2 dom(f Q). The projection can be used for multisets. For example, b5 fa;bg = [a2; b2].
Let A be a set and Q A a subset. Q 2 S(A) ! S(Q) is a projection function and is de ned recursively: (1) h i Q = h i and (2) for s 2 S(A) and a 2 A: (hai s) Q = ( s Q hai s Q if a 2= Q if a 2 Q So ha; a; b; b; c; d; di fa;bg = ha; a; b; bi. 3.2
Event logs are the starting point for process mining. They contain information
recorded by the information systems and resources supporting a process.
Typically, the executed activities of multiple cases of a process are recorded. Note
that only example behavior is recorded, i.e. event logs only contain information
that has been seen. An event log often contains only a fraction of the possible
behavior [
Let A UA be a set of activities. A trace s 2 S(A) is a sequence of activities.
Let A UA be a set of activities. Let L 2 B(S(A)) be a multiset of traces over A. L is an event log over A.
An example event log is L1 = [ha; b; c; di5; ha; b; b; c; di2; ha; c; di3]. There are three unique traces in L1, and it contains information about a total of 10 cases. There are 4 5+5 2+3 3 = 39 events in total. The projection can be used for event logs as well. That is, for some log L 2 B(S(A)) and set Q A : L Q = [s Qjs 2 L]. For example L1 fa;b;cg = [ha; b; ci5; ha; b; b; ci2; ha; ci3]. We will refer to these projected event logs as sublogs. 3.3
In [
Let A UA be a set of activities. M(A) = (A A) ! [ 1:0; 1:0] denotes the set of causal activity matrices over A. For a; a0 2 A and M 2 M(A), M (a; a0) denotes the \directly follows strength" from a to a0.
A M (a; a0) value close to 1:0 signi es that we are quite con dent there exists a directly follows relation between two activities while a value close to 1:0 signi es that we are quite sure there is no relation. A value close to 0:0 indicates uncertainty, i.e., there may be a relation, but there is no strong evidence for it.
Let A UA be a set of activities. G(A) denotes the set of causal activity graphs over A. A causal activity graph G 2 G(A) is a 2-tuple G = (V; E) where V A is the set of nodes and E (V V ) is the set of edges. G = (V; E) 2 G(A) is the causal activity graph based on M 2 M(A) and a speci c causality threshold 2 [ 1:0; 1:0] i E = f(a; a0) 2 A A j M (a; a0) > g and V = S(a;a0)2E fa; a0g. That is, for every pair of activities (a; a0) 2 A, there's an edge from a to a0 in G i the value for a to a0 in the causal activity matrix M exceeds some threshold . Note that V A since some activities in A might not be represented in G.
Let A UA be a set of activities. C(A) denotes the set of activity clusters over A. An activity cluster C 2 C(A) is a subset of A, that is, C A.
Let A UA be a set of activities. Cb(A) denotes the set of activity clusterings over A. An activity clustering Cb 2 Cb(A) is a set of activity clusters, that is, Cb P (A). A k-clustering Cb 2 Cb(A) is a clustering with size k, i.e. jCbj = k. Let Cb 2 Cb(A) be a clustering over A, the number of activities in Cb is denoted by jjCbjj = j S Cj, i.e. jjCbjj signi es the number of unique activities in Cb.
C2Cb 3.4
Process discovery aims at discovering a model from an event log while
conformance checking aims at diagnosing the di erences between observed and modeled
behavior (resp. the event log and the model). Literature suggests many di erent
notations for models. We abstract from any speci c model notation, but will
de ne the set of algorithms that discover a model from an event log. Various
discovery algorithms have been proposed in literature. These discovery
algorithms are often called mining algorithms, or miners in short. For an overview
of di erent algorithms we refer to [
Let A UA be a set of activities. N (A) denotes the set of process models over A, irrespective of the speci c notation (Petri nets, transition systems, BPMN, UML ASDs, etc.) used.
Let A UA be a set of activities. D(A) = B(S(A)) ! N (A) denotes the set of discovery algorithms over A. A discovery algorithm D 2 D(A) discovers a process model over A from an event log over A. 3.5
As discussed, in [
It is apparent that the manner in which activities are clustered has a substantial
e ect on required processing time, and it is possible for similarly sized clusterings
(in the average cluster size) to lead to very di erent total processing times. As
a result of the vertex-cut (maximal ) decomposition approach [
Hence, a good decomposition should (1) maximize the causal relations between the activities within each cluster in the activity clustering, (2) minimize the causal relations and overlap across the clusters and (3) have approximately equally sized clusters. The challenge lies in nding a good balance between these three properties.
A clustering where one cluster is a subset of another cluster is not valid as it would lead to double work, and would thus result in an increase in required processing time without increasing (or even decreasing) model quality. Note that this de nition of a valid clustering allows for disconnected clusters, and that some activities might not be in any cluster. This is acceptable as processes might consist of disconnected parts and event logs may contain noise. However, if activities are left out some special processing might be required. valid clustering i : Cb 6= ; ^ 8C1;C22Cb^C16=C2 C1 6 valid clusterings over A.
Let A UA be a set of activities. Let Cb 2 Cb(A) be a clustering over A. Cb is a C2. CbV (A) denotes the set of 4.1
We de ne decomposition quality notions in terms of clustering properties. The rst clustering property we de ne is cohesion. The cohesion of an activity clustering is de ned as the average cohesion of each activity cluster in that clustering. A clustering with good cohesion (cohesion 1) signi es that causal relations between activities in the same cluster are optimized, whereas bad cohesion (cohesion 0) signi es that activities with few causal relations are clustered together.
Let A UA be a set of activities. Let M 2 M(A) be a causal activity matrix over A, and let Cb 2 CbV (A) be a valid clustering over A. The cohesion of clustering Cb in matrix M , denoted Cohesion(Cb; M ) is de ned as follows:
Cohesion(Cb; M ) = Cohesion(C; M ) =
PC2Cb Cohesion(C; M )
jCbj Pc1;c22C max(M (c1; c2); 0) jC Cj
The second clustering property is called coupling, and is also represented by a number between 0 and 1. Good coupling (coupling 1) signi es that causal relations between activities across clusters are minimized. Bad coupling (coupling 0) signi es that there are a lot of causal relations between activities in di erent clusters.
Let A UA be a set of activities. Let M 2 M(A) be a causal activity matrix over A, and let Cb 2 CbV (A) be a valid clustering over A. The coupling of clustering Cb in matrix M , denoted Coupling(Cb; M ) is de ned as follows:
Coupling(Cb; M ) = hmax(M (c1; c2); 0) + max(M (c2; c1); 0)i
Note that the weights of the causal relations are used in the calculation of cohesion and coupling. Relations of which we are not completely sure of (or that are weak) therefore have less e ect on these properties than stronger ones.
The balance of an activity clustering is the third property. A clustering with good balance has clusters of (about) the same size. Decomposing the activities into clusters with low balance (e.g. a k-clustering with one big cluster holding almost all of the activities and (k 1) clusters with only a few activities) will not speed up discovery or conformance checking, rendering the whole decomposition approach useless. At the same time nding a clustering with perfect balance (all clusters have the same size) will most likely split up the process / log in places that \shouldn't be split up", as processes generally consist out of di erent-sized natural parts. Balance is also represented by a number between 0 and 1, where a good balance (balance 1) signi es that all clusters are about the same size and a bad balance (balance 0) signi es that the cluster sizes di er quite a lot. This balance formula utilizes the standard deviation of the sizes of the clusters in a clustering to include the magnitude of the di erences in cluster sizes. A variation of this formula using squared errors or deviations could also be used as a clustering balance measure.
Let A UA be a set of activities. Let Cb 2 CbV (A) be a valid clustering over A. The balance of clustering Cb denoted Balance(Cb) is de ned as follows: Balance(Cb) = 1 2
(Cb) jjCbjj Where (Cb) signi es the standard deviation of the sizes of the clusters in the clustering Cb.
In order to assess a certain decomposition based on the clustering properties, we introduce a weighted scoring function, which grades an activity clustering with a score between 0 (bad clustering) and 1 (good clustering). A weight can be set for each clustering property, depending on their relative importance. A clustering with clustering score 1 has perfect cohesion, coupling and balance scores, on the set weighing of properties.
Let A UA be a set of activities. Let M 2 M(A) be a causal activity matrix over A, and let Cb 2 CbV (A) be a valid clustering over A. The clustering score (score) of clustering Cb in matrix M , denoted Score(Cb; M ) is de ned as follows: Score(Cb; M ) = Cohesion(Cb; M ) + Coupling(Cb; M ) + Balance(Cb)
where CohW , CouW , and BalW are the weights for Cohesion, Coupling, and Balance. 4.2
Creating a good activity clustering is essentially a graph partitioning problem.
The causal activity graph needs to be partitioned in parts that have (1) good
cohesion, (2) good coupling and (3) good balance. The existing maximal
decomposition approach [
Instead of applying or creating a di erent graph partitioning algorithm, we recompose the activity clusters obtained by the vertex-cut decomposition. The idea is that it is possible to create a clustering that has fewer larger clusters, requiring less processing time to discover the nal model, because overhead as well as cluster overlap are reduced. Additionally, model quality is likely to increase because of the higher number of activities in the clusters and the lower coupling between clusters.
There are often many ways in which a clustering can be recomposed to the desired amount of clusters, as shown in Figure 1. We are interested in the highest quality clustering of the desired size, i.e. the clustering that has the best cohesion, coupling and balance properties. A clustering that has a high clustering score will very likely lead to such a decomposition.
In order to nd a good decomposition in the form of a high-scoring clustering quickly, we propose two agglomerative hierarchical recomposition approaches, which iteratively merge clusters, reducing the size of the clustering by one each iteration. Proximity-based approach We propose an hierarchical recomposition approach based on proximity between activity clusters, where cluster coupling is used as the proximity measure. The starting point is the clustering as created by the vertex-cut approach. We repeatedly merge the clusters closest to one another (i.e. the pair of clusters with the highest coupling) until we end up with the desired amount of clusters (k ). After the k-clustering is found, it is made valid by removing any clusters that are a subcluster of another cluster, if such clusters exist. It is therefore possible that the algorithm returns a clustering with size smaller than k. By merging clusters we are likely to lower the overal cohesion of the clustering. This drawback is minimized, as coupling is used as the distance measure. Coupling is also minimized. The proximity-based hierarchical recomposition approach however is less favored towards the balance property, as it is possible that -because of high coupling between clusters- two of the larger clusters are merged. In most processes however, coupling between two \original" clusters will be higher than coupling between \merged" clusters. If not, the two clusters correspond to parts of the process which are more di cult to split up (e.g. a loop, a subprocess with many interactions and/or possible paths between activities, etc.). Model quality is therefore also likely to increase by merging these clusters, as process discovery algorithms don't have to deal with missing activities, or incorrect causal relations introduced in the corresponding sublogs. A possible downside is that as the clustering might be less balanced, processing time can be slightly higher in comparison with a perfectly-balanced decomposition. Score-based approach We propose a second hierarchical recomposition algorithm that uses the scoring function in a look-ahead fashion. In essence, this algorithm, like the proximity-based variant, iteratively merges two clusters into one. For each combination of clusters, the score of the clustering that results from merging those clusters is calculated. The clustering with the highest score is used for the next step. The algorithm is nished when a k-clustering is reached. Like in the proximity-based approach, after the k-clustering is found, it is made valid by removing any clusters that are a subcluster of another cluster, if such clusters exist. The advantage of this approach is that speci c (combinations of) clustering properties can be given priority, by setting their scoring weight(s) accordingly. For example, it is possible to distribute the activities over the clusters near perfectly, by choosing a high relative weight for balance. This would likely lead to a lower overall processing time. However, it might lead to natural parts of the process being split over multiple clusters, which could negatively a ect model quality. A downside of this algorithm is that, as the algorithm only looks ahead one step, it is possible that a choice is made that ultimately leads to a lower clustering score, as that choice cannot be undone in following steps. 4.3
All concepts and algorithms introduced in this paper are implemented in the
process mining toolkit ProM 1, developed at the Eindhoven University of
Technology. All work can be found in the BartHompes package2. For more elaborate
explanations, pseudo-code of the algorithms, and analysis results we refer to [
The proposed recomposition techniques are tested using event logs of di erent
sizes and properties. Results for an event log consisting of 33 unique activities,
and 1000 traces are shown in this section. For this test the ILP Miner process
discovery algorithm was used [
We are interested in the clustering scores of each algorithm when recomposing the clustering created by the vertex-cut approach to a certain smaller size. Exhaustively nding the best possible clustering proved to be too time- and resource-consuming, therefore, besides the two hierarchical approaches listed here, a random recomposition approach was used which recomposes clusters randomly one million times, as to give an idea of what the best possible clustering might be. The highest found clustering score is shown on the graph. Equal 1 See http://www.processmining.org 2 See https://svn.win.tue.nl/repos/prom/Packages/BartHompes/ weights were used for the three clustering properties in order to compute the clustering scores. As can be seen in Figure 2, the vertex-cut approach creates 22 clusters. We can see that all algorithms perform very similarly in terms of clustering score. Only for very small clustering sizes the proximity-based approach performs worse than the other approaches, due to its tendency to create unbalanced clusters.
Clustering scores 0,75 0,7 0,55 0,5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
#clusters
Agglomerative Hierarchicalw/ Proximity Agglomerative Hierarchicalw/ Scoring Random(max)
Besides clustering scores, we are even more interested in how each decomposition method performs in terms of required processing time and quality of the resulting process model. In Figure 3 we can see that decomposing the event log drastically reduces processing times. For an event log this size, the decomposition steps relatively takes up negligible time (see base of bars in gure), as most time is spent discovering the submodels (light blue bars). Processing times are reduced exponentially (as expected), until a certain optimum decomposition (in terms of speed) is reached, after which overhead starts to increase time linearly again. We have included two process models (Petri Nets) discovered from the event log. Figure 4 shows the model discovered when using the vertex-cut decomposition. Figure 5 shows the model discovered when using the clustering recomposed to 11 clusters with the Proximity-based agglomerative hierarchical approach. We can see that in Figure 4, activity \10" is disconnected (marked blue). In Figure 5, this activity is connected, and a structure (loop) is discovered. We can also see that activity \12" now is connected to more activities. This shows that the vertex-cut decomposition sometimes splits up related activities, which leads to a lower quality model. By recomposing the clusters we rediscover these relations, leading to a higher quality model. Processing times for these two models are comparable, as can be seen in Figure 3.
Time per step & Parti ti ons in model- ILP Miner Discovery Algorithm 900 800 700 600 s d no500 sce n ie400 m i T300 200 100 0 4 3 1 l e d o m 2 in s n ito r a P 2 3 4 A5gg6lom7era8vtie9Hie10rar1c1hi1c2al1w3/1P4ro1x5im16ity17 18 19 20 21 2 3 4 5Ag6glo7me8ravtie9 H1i0era11rch12ica1l3w1/4Sc1o5ri1n6g 17 18 19 20 21 22 0
Max. Decomp.
Recomposition method - # clusters
Matrix Graph Clustering Sublogs Submodels Merge Partion sin model
In decomposed process discovery, large event logs are decomposed by somehow clustering their events (activities), and there are many ways these activity clusterings can be made. Hence, good quality notions are necessary to be able to assess the quality of a decomposition before starting the time-consuming actual discovery algorithm. Being able to nd a high-quality decomposition plays a key role in the success of decomposed process mining, even though the decomposition step takes relatively very little time.
By using a better decomposition, less problems arise when discovering submodels for sublogs and when merging submodels into the overal process model. We introduced three quality notions in the form of clustering properties: cohesion, coupling and balance. It was shown that nding a non-maximal decomposition can potentially lead to a decrease in required processing time while maintaining or even improving model quality, compared to the existing vertexcut maximal decomposition approach. We have proposed two variants of an agglomerative hierarchical recomposition technique, which are able to create a high-quality decomposition for any given size, in very little time.
Even though the scope was limited to decomposed process discovery, the introduced quality notions and decomposition approaches can be applied to decomposed conformance checking as well. However, more work is needed to incorporate them in a conformance checking environment.
Besides nding a better decomposition, we believe improvements can be gained in nding a better, more elaborate algorithm to merge submodels into the overal process model. By simply merging submodels based on activity labels it is likely that implicit paths are introduced. Model quality in terms of tness, simplicity, generality or precision could su er. An additional post-processing step (potentially using causal relations) could also solve this issue.
Even though most interesting process discovery algorithms are exponential in the number of di erent activities, adding an infrequent or almost unrelated activity to a cluster might not increase computation time for that cluster as much as adding a frequent or highly related one. Therefore, besides weighing causal relations between activities in the causal activity matrix, activities themselves might be weighted as well. Frequency and connectedness are some of the many possible properties that can be used as weights. It might be possible that one part of a process can be discovered easily by a simple algorithm whereas another, more complex part of the process needs a more involved discovery algorithm to be modeled correctly. Further improvements in terms of processing time can be gained by somehow detecting the complexity of a single submodel in a sublog, and choosing an adequate discovery algorithm.
Finally, as discussed, the proposed recomposition algorithms expect the desired amount of clusters to be given. Even though the algorithms were shown to provide good results for any chosen number, the approach would bene t from some method that determines a tting clustering size for a given event log. This would also mean one less potentially uncertain step for the end-user.