Process models can be seen as \maps" describing the operational processes of organizations. Traditional process discovery algorithms have problems dealing with ne-grained event logs and lessstructured processes. The discovered models (i.e., \maps") are spaghettilike and are di cult to comprehend or even misleading. One of the reasons for this can be attributed to the fact that the discovered models are at (without any hierarchy). In this paper, we demonstrate the discovery of hierarchical process models using a set of interrelated plugins implemented in ProM.3 The hierarchy is enabled through the automated discovery of abstractions (of activities) with domain signi cance.
We have applied process mining techniques in over 100 organizations. These
practical experiences revealed two problems: (a) processes tend to be less
structured than what stakeholders expect, and (b) events logs contain ne-grained
events whereas stakeholders would like to view processes at a more coarse-grained
level. In [
The two-phase approach to process discovery [
Filtering
Event Log s a m b c u d n j e s a m q f h l l h g i k e s a m f g h l h i k q e s a m b c d n u j e s a m f h l g i h l h k q e s a m q f g i h l h k e s a m q f g h l h i k e s a m p c u d n r e s a m b d n c u j e s a m p d n c u r e
Two-phase
Approach Abstractions de ned over common execution patterns
Traditional Approach Transformed Log X b Z j e X q Y Y e X Y Y q e X b Z Z j e X Y Y Y q e X q Y Y Y e X q Y Y Y e X p Z r e X b Z j e X p Z r e
The event log may rst be cleansed using some simple lters (e.g., adding
arti cial start/end events, ltering events of a particular transaction type such as
considering only `complete' events etc.). The Pattern Abstractions plugin is then
applied on this ltered log one or several times. The Pattern Abstractions plugin
has been implemented as a log visualizer in ProM and caters to the discovery
of common execution patterns, the de nition of abstractions over them, and the
pre-processing of the event log with these abstractions. The transformed log
(preprocessed log with abstractions) obtained in iteration i is used as the input for
the Pattern Abstractions plugin in iteration i + 1. It is this repetitive application
of the Pattern Abstractions plugin that enables the de nition of multiple levels
of hierarchy (new abstractions can be de ned over existing abstractions). During
the pre-processing phase, for each de ned abstraction, the Pattern Abstractions
plugin generates a sub-log that captures the manifestation of execution patterns
de ned by that abstraction as its process instances. The Fuzzy Miner plugin
[
Running Example. We use the work ow of a simple digital photo copier as our running example. The copier supports photocopying, scanning and printing of documents in both color and gray modes. The scanned documents can be sent to the user via email or FTP. Upon receipt of a job, the copier rst generates an image of the document and subsequently processes the image to enhance its quality. Depending on whether the job request is for a copy/scan or print, separate procedures are followed to generate an image. For print requests, the document is rst interpreted and then a rasterization procedure is followed to form an image. The image is then written on the drum, developed, and fused on to the paper.
We have modeled this work ow of the copier in CPN tools [
The basic building blocks of the Pattern Abstractions plugin are shown in Figure 3. Figures 4 and 5 illustrate these building blocks.
Discover Common Execution Patterns
Compute Pattern Metrics
Filter Patterns
Form &
Select Abstractions
Transform
Log
{ Discover Common Execution Patterns: The Pattern Abstractions plugin
supports the discovery of tandem arrays (loop patterns) and maximal repeats
(common subsequence of activities within a process instance or across
process instances) [
Compute Pattern Metrics
Discover Common Execution Patterns Uncovered Patterns
Pattern
Metric Values
{ Compute Pattern Metrics: Various metrics (e.g, overlapping and
non-overlapping frequency counts, instance count etc.) to assess the signi cance of
the uncovered patterns are supported.
{ Filter Patterns: It could be the case that too many patterns are uncovered
from the event log. To manage this, features to lter patterns that are less
signi cant are supported.
{ Form and Select Abstractions: Abstractions are de ned over the ltered
patterns. Patterns that are closely related are grouped together to form
abstractions. The approach for forming abstractions is presented in [
At any iteration, if n abstractions are selected, the Pattern Abstractions plugin generates a transformed log, and n sub-logs (one for each of the n chosen abstractions). We recommend to process for loop patterns in the initial iterations and maximal repeats in the subsequent iterations. For the example event log, we have performed three iterations. The transformed log after the third iteration has 19 event classes and 1601 events. In the process, we have de ned various abstractions such as half-toning, image processing, capture image, etc.
Select Abstractions
Form Abstractions Transform Log
The Pattern Abstractions plugin supports additional features such as visualizing patterns and exporting the traces that contain the patterns. 3
(Enhanced) Fuzzy Miner Plugin
The Fuzzy Miner [
Like high-level maps only show major objects of interest and major streets, high-level fuzzy instances also show only major elements (nodes and edges). For this purpose, the Fuzzy Miner computes from the log a signi cance weight for every element and an additional correlation weight for every edge. The higher these weights are, the more major the element is considered to be. Furthermore, the Fuzzy Miner uses a number of thresholds: Only elements that meet these thresholds are shown. As such, these thresholds correspond to the required level of abstraction: The higher these thresholds are, the higher the level of abstraction is. For sake of completeness we mention here that a fuzzy instance may contain clusters of minor nodes: If some objects of interest on the Amsterdam map are too minor to be shown by themselves on some map, they may be shown as a single (and major) object provided that they are close enough. For this reason, the Fuzzy Miner rst attempts to cluster minor nodes into major cluster nodes, and only if that does not work it will remove the minor node from the map.
Figure 6 shows an example fuzzy model (left-hand side) and fuzzy instance (right-hand side). Note that both views show a fuzzy instance, but the fuzzy model view allows the user to change the thresholds (by changing the sliders) whereas the fuzzy instance view does not. The signi cance of a node is displayed as part of its label (for example, the node \Transfer Image" has a signi cance of 0:253), the signi cance of an edge is visualized using its wideness (the wider the edge, the more signi cant it is), and the correlation of an edge is visualized using its color contrast (the darker the edge is, the more correlated its input node and its output node are). The octagonal shaped nodes in the right-hand side view correspond to the cluster nodes (one of the cluster nodes contain 4 activities and the other contains 11 activities). All activities on the left hand side except \Job Complete" are contained in a cluster node on the right. Apparently, the signi cance weights for these nodes (0:262, 0:253, 0:250, 0:296 and 0:403) were too low to be shown, which indicates that the corresponding threshold was set to at least 0:403. Furthermore, the node \Interpret" (on the right) is highly selfcorrelated, whereas the nodes \Transfer Image" and \Send SMTP" (on the left) are moderately correlated.
The Fuzzy Miner has been enhanced to utilize the availability of sub-logs obtained from the Pattern Abstractions plugin for the chosen abstractions. Fuzzy models are discovered for each of the sub-logs and are displayed upon zooming in on its corresponding abstract activity. Abstract activities are di erentiated from other activities by means of a distinct color (a darker shade of blue, see also Figure 6).
Figure 7 depicts the top-level process model of the copier example. This model is generated from the transformed log obtained after the third iteration of Pattern Abstractions plugin. The upper branch of the process model corresponds to the creation of the document image for print requests while the lower branch corresponds to image creation for copy/scan requests. The two branches meet after the image is formed and the image is subjected to some image processing functionality. The document is then printed or sent to the user via email or FTP. The lower level details of image creation, image processing, print image have been abstracted in this model. The Pattern Abstractions plugin enables the discovery of such abstractions with strong domain (functional) signi cance. Upon zooming in on the Image Processing abstraction, the process model depicted in Figure 8 is shown. This sub-process in turn contains another abstract activity viz., Half Toning (the level of hierarchy is two). Zooming in on this abstract activity displays the sub-process de ning it as depicted in Figure 8. Figure 9 depicts two other abstractions.
Interpretation of pages in a document to print
Rendering and Screening of the document
Printing the Image Capturing the Image of the Document to Copy/Scan
Image Processing
In this fashion, using the chain of plugins presented in this paper, one can discover hierarchical process models. 4
We demonstrated the discovery of hierarchical process models using a chain of plugins implemented in ProM. The repetitive application of Pattern Abstractions plugin enables the discovery of multiple levels of hierarchy. We can use this approach to create maps that (i) depict desired traits, (ii) eliminate irrelevant details, (iii) reduce complexity, and (iv) improve comprehensibility. Acknowledgments R.P.J.C. Bose and W.M.P. van der Aalst are grateful to Philips Healthcare for funding the research in process mining.