Process Mining Techniques in Business Environments

Contents

1 Introduction..........................................

1.1 Business Process Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Process Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Book Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 Website . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Part I: State of the Art: BPM, Data Mining and Process Mining

2 Introduction to Business Processes, BPM, and BPM Systems....... 11

2.1 Introduction to Business Processes . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Petri Nets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1.2 BPMN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.3 YAWL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.4 Declare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.5 Other Formalisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Business Process Management Systems . . . . . . . . . . . . . . . . . . . . 19

3 Data Generated by Information Systems (and How to Get It)...... 23

3.1 Information Extraction from Unstructured Sources . . . . . . . . . . . . . 23

3.2 Evaluation with the Measure. . . . . . . . . . . . . . . . . . . . . . . . . . 24

4 Data Mining for Information System Data.................... 27

4.1 Classification with Nearest Neighbor . . . . . . . . . . . . . . . . . . . . . . 27

4.2 Neural Networks Applied to Estimation . . . . . . . . . . . . . . . . . . . . 28

4.3 Association Rules Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.4 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.4.1 Clustering with Self-organizing Maps . . . . . . . . . . . . . . . . 29

4.4.2 Clustering with Hierarchical Clustering . . . . . . . . . . . . . . . 30

4.5 Profiling Using Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Process Mining........................................ 33

5.1 Process Mining as Control-Flow Discovery. . . . . . . . . . . . . . . . . . 35

5.2 Other Perspectives of Process Mining. . . . . . . . . . . . . . . . . . . . . . 45

5.2.1 Organizational Perspective . . . . . . . . . . . . . . . . . . . . . . . . 45

5.2.2 Conformance Checking . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.2.3 Data Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3 Performance Evaluation of Process Mining Algorithm . . . . . . . . . . 46

6 Quality Criteria in Process Mining.......................... 49

6.1 Model-to-Log Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.2 Model-to-Model Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

7 Event Streams......................................... 53

7.1 Data Streams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7.1.1 Data-Based Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

7.1.2 Task-Based Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

7.2 Common Stream Mining Approaches . . . . . . . . . . . . . . . . . . . . . . 54

7.3 Stream Mining and Process Mining . . . . . . . . . . . . . . . . . . . . . . . 54

Part II: Obstacles to Process Mining in Practice Obstacles to Applying Process Mining in Practice............... 59

8.1 Typical Deploy Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

8.2 Problems with Data Preparation. . . . . . . . . . . . . . . . . . . . . . . . . . 60

8.3 Problems During the Mining Phase . . . . . . . . . . . . . . . . . . . . . . . 62

8.4 Problems with the Interpretation of the Mining Results and Extension of Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

8.5 Incremental and Online Process Mining . . . . . . . . . . . . . . . . . . . . 63

9 Long-term View Scenario................................. 65

9.1 A Target Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

9.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

Part III: Process Mining as an Emerging Technology Data Preparation....................................... 71

10.1 Process Mining in New Scenarios . . . . . . . . . . . . . . . . . . . . . . . . 72

10.2 Working Framework for Event Logs . . . . . . . . . . . . . . . . . . . . . . 73

10.3 Identification of Process Instances . . . . . . . . . . . . . . . . . . . . . . . . 75

10.3.1 Exploiting A-priori Knowledge . . . . . . . . . . . . . . . . . . . . . 75

10.3.2 Selection of the Identifier . . . . . . . . . . . . . . . . . . . . . . . . . 76

10.3.3 Results Organization and Filtering. . . . . . . . . . . . . . . . . . . 78

10.3.4 Deriving a Log to Mine . . . . . . . . . . . . . . . . . . . . . . . . . . 79

10.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

10.5 Similar Problems and Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . 81

10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

11 Heuristics Miner for Time Interval.......................... 85

11.1 Heuristics Miner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

11.2 Activities as Time Interval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Contents

11.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

12 Automatic Configuration of Mining Algorithm................. 97

12.1 The Problem of Selecting the Right Parameters . . . . . . . . . . . . . . . 98

12.2 Parameters of the Heuristics Miner++ Algorithm . . . . . . . . . . . . . . 99

12.3 Facing the Parameters Setting Problem . . . . . . . . . . . . . . . . . . . . . 101

12.4 Discretization of the Parameters Values . . . . . . . . . . . . . . . . . . . . 102

12.5 Exploration of the Hypothesis Space . . . . . . . . . . . . . . . . . . . . . . 103

12.6 Improved Exploration of the Hypothesis Space . . . . . . . . . . . . . . . 105

12.6.1 Factorization of the Search Space . . . . . . . . . . . . . . . . . . . 105

12.6.2 Searching for the Best Hypothesis . . . . . . . . . . . . . . . . . . . 106

12.7 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

12.7.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

12.7.2 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

12.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

13 User-Guided Discovery of Process Models..................... 113

13.1 Clustering for Process Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

13.2 Results on Clustering for Process Mining . . . . . . . . . . . . . . . . . . . 114

13.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

13.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

14 Extensions of Business Processes with Organizational Roles........ 119

14.1 Working Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

14.2 Rules for Handover of Roles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

14.2.1 Rule for Strong No Handover . . . . . . . . . . . . . . . . . . . . . . 124

14.2.2 Rule for No Handover . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

14.2.3 Degree of No Handover of Roles . . . . . . . . . . . . . . . . . . . 124

14.2.4 Merging Roles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

14.3 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

14.3.1 Step 1: Handover of Roles Identification . . . . . . . . . . . . . . 126

14.3.2 Step 2: Roles Aggregation . . . . . . . . . . . . . . . . . . . . . . . . 127

14.3.3 Generation of Candidate Solutions. . . . . . . . . . . . . . . . . . . 128

14.3.4 Partition Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

14.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

14.5 Other Approaches Dealing with Organizational Perspective. . . . . . . 134

14.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

15 Results Interpretation and Evaluation........................ 137

15.1 Comparing Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

15.1.1 Problem Statement and the General Approach. . . . . . . . . . . 139

15.1.2 Process Representation. . . . . . . . . . . . . . . . . . . . . . . . . . . 140

15.1.3 A Metric for Processes Comparison. . . . . . . . . . . . . . . . . . 144

Contents

15.2 A-Posteriori Analysis of Declarative Processes . . . . . . . . . . . . . . . 147

15.2.1 Declare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

15.2.2 An Approach for A-Posteriori Analysis . . . . . . . . . . . . . . . 148

15.2.3 An Algorithm to Discriminate Fulfillments

from Violations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

15.2.4 Healthiness Measures. . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

15.2.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

15.3 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

15.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

16 Hands-On: Obtaining Test Data

............................ 163

16.1 A Process and Logs Generator. . . . . . . . . . . . . . . . . . . . . . . . . . . 164

16.1.1 The Processes Generation Phase . . . . . . . . . . . . . . . . . . . . 165

16.1.2 Execution of a Process Model. . . . . . . . . . . . . . . . . . . . . . 169

16.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

16.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

Part IV: A New Challenge in Process Mining

17 Process Mining for Stream Data Sources..................... 177

17.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

17.2 Heuristics Miners for Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

17.2.1 Baseline Algorithm for Stream Mining. . . . . . . . . . . . . . . . 181

17.2.2 Stream-Specific Approaches . . . . . . . . . . . . . . . . . . . . . . . 183

17.2.3 Stream Process Mining with Lossy Counting

(Evolving Stream) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

17.3 Error Bounds on Online Heuristics Miner . . . . . . . . . . . . . . . . . . . 189

17.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

17.4.1 Models Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

17.4.2 Algorithms Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

17.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

17.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

Part V: Conclusions and Future Work Conclusions and Future Work............................. 207

18.1 Wrap-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

18.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

References............................................... 211