| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Workflow Mining: Discovering Process Models from Event Logs
September 2004 (vol. 16 no. 9)
pp. 1128-1142
Contemporary workflow management systems are driven by explicit process models, i.e., a completely specified workflow design is required in order to enact a given workflow process. Creating a workflow design is a complicated time-consuming process and, typically, there are discrepancies between the actual workflow processes and the processes as perceived by the management. Therefore, we have developed techniques for discovering workflow models. The starting point for such techniques is a so-called "workflow log” containing information about the workflow process as it is actually being executed. We present a new algorithm to extract a process model from such a log and represent it in terms of a Petri net. However, we will also demonstrate that it is not possible to discover arbitrary workflow processes. In this paper, we explore a class of workflow processes that can be discovered. We show that the \alpha{\hbox{-}}{\rm{algorithm}} can successfully mine any workflow represented by a so-called SWF-net.
[1] 1128 W.M.P. van der Aalst, Verification of Workflow Nets Application and Theory of Petri Nets, P. Azema and G. Balbo, eds., pp. 407-426, Berlin: Springer-Verlag, 1997.[2] W.M.P. van der Aalst, The Application of Petri Nets to Workflow Management The J. Circuits, Systems and Computers, vol. 8, no. 1, pp. 21-66, 1998.[3] Business Process Management: Models, Techniques, and Empirical Studies Lecture Notes in Computer Science, W.M.P. van der Aalst, J. Desel, and A. Oberweis, eds., vol. 1806, Springer-Verlag, Berlin, 2000.[4] W.M.P. van der Aalst and B.F. van Dongen, Discovering Workflow Performance Models from Timed Logs Proc. Int'l Conf. Eng. and Deployment of Cooperative Information Systems (EDCIS 2002), Y. Han, S. Tai, and D. Wikarski, eds., vol. 2480, pp. 45-63, 2002.[5] W.M.P. van der Aalst and K.M. van Hee, Workflow Management: Models, Methods, and Systems. Cambridge, Mass.: MIT Press, 2002.[6] W.M.P. van der Aalst, A.J.M.M. Weijters, and L. Maruster, Workflow Mining: Which Processes can be Rediscovered? BETA Working Paper Series, WP 74, Eindhoven Univ. of Technology, Eindhoven, 2002.[7] R. Agrawal, D. Gunopulos, and F. Leymann, Mining Process Models from Workflow Logs Proc. Sixth Int'l Conf. Extending Database Technology, pp. 469-483, 1998.[8] D. Angluin and C.H. Smith, Inductive Inference: Theory and Methods Computing Surveys, vol. 15, no. 3, pp. 237-269, 1983.[9] J.E. Cook and A.L. Wolf, Discovering Models of Software Processes from Event-Based Data ACM Trans. Software Eng. and Methodology, vol. 7, no. 3, pp. 215-249, 1998.[10] J.E. Cook and A.L. Wolf, Event-Based Detection of Concurrency Proc. Sixth Int'l Symp. the Foundations of Software Eng. (FSE-6), pp. 35-45, 1998.[11] J.E. Cook and A.L. Wolf, Software Process Validation: Quantitatively Measuring the Correspondence of a Process to a Model ACM Trans. Software Eng. and Methodology, vol. 8, no. 2, pp. 147-176, 1999.[12] J. Desel and J. Esparza, Free Choice Petri Nets Cambridge Tracts in Theoretical Computer Science, vol. 40, Cambridge, UK: Cambridge Univ. Press, 1995.[13] J. Eder and G.E. Olivotto, and W. Gruber, A Data Warehouse for Workflow Logs Proc. Int'l Conf. Eng. and Deployment of Cooperative Information Systems (EDCIS 2002), Y. Han, S. Tai, and D. Wikarski, eds., pp. 1-15, 2002.[14] A. Ehrenfeucht, G. Rozenberg, Partial (Set) 2-Structures Part 1 and Part 2 Acta Informatica, vol. 27, no. 4, pp. 315-368, 1989.[15] Workflow Handbook 2001, Workflow Management Coalition, L. Fischer, ed. Lighthouse Point, Fla.: Future Strategies, 2001.[16] E.M. Gold, Language Identfication in the Limit Information and Control, vol. 10, no. 5, pp. 447-474, 1967.[17] E.M. Gold, Complexity of Automaton Identification from Given Data Information and Control, vol. 37, no. 3, pp. 302-320, 1978.[18] D. Grigori, F. Casati, U. Dayal, and M.C. Shan, Improving Business Process Quality through Exception Understanding, Prediction, and Prevention Proc. 27th Int'l Conf. Very Large Data Bases (VLDB '01), P. Apers, P. Atzeni, S. Ceri, S. Paraboschi, K. Ramamohanarao, and R. Snodgrass, eds., pp. 159-168, 2001.[19] J. Herbst, A Machine Learning Approach to Workflow Management Proc. 11th European Conf. Machine Learning, pp. 183-194, 2000.[20] J. Herbst, Dealing with Concurrency in Workflow Induction Proc. European Concurrent Eng. Conf., U. Baake, R. Zobel, and M. Al-Akaidi, eds., 2000.[21] J. Herbst, Ein induktiver Ansatz zur Akquisition und Adaption von Workflow-Modellen PhD thesis, Universität Ulm, Nov. 2001.[22] J. Herbst and D. Karagiannis, Integrating Machine Learning and Workflow Management to Support Acquisition and Adaptation of Workflow Models Proc. Ninth Int'l Workshop Database and Expert Systems Applications, pp. 745-752, 1998.[23] J. Herbst and D. Karagiannis, An Inductive Approach to the Acquisition and Adaptation of Workflow Models Proc. Workshop Intelligent Workflow and Process Management: The New Frontier for AI in Business, M. Ibrahim and B. Drabble, eds., pp. 52-57, Aug. 1999.[24] J. Herbst and D. Karagiannis, Integrating Machine Learning and Workflow Management to Support Acquisition and Adaptation of Workflow Models Int'l J. Intelligent Systems in Accounting, Finance, and Management, vol. 9, pp. 67-92, 2000.[25] IDS Scheer, ARIS Process Performance Manager (ARIS PPM),http:/www.ids-scheer.com, 2002.[26] S. Jablonski and C. Bussler, Workflow Management: Modeling Concepts, Architecture, and Implementation. London: Int'l Thomson Computer Press, 1996.[27] B. Kiepuszewski, Expressiveness and Suitability of Languages for Control Flow Modelling in Workflows PhD thesis, Queensland Univ. of Technology, Brisbane, Australia, 2002, available viahttp://www.tm.tue.nl/it/researchpatterns .[28] F. Leymann and D. Roller, Production Workflow: Concepts and Techniques. Upper Saddle River, New Jersey, Prentice-Hall PTR, 1999.[29] H. Mannila and D. Rusakov, Decomposing Event Sequences into Independent Components Proc. First SIAM Conf. Data Mining, V. Kumar and R. Grossman, eds., pp. 1-17, 2001.[30] H. Mannila, H. Toivonen, and A.I. Verkamo, Discovery of Frequent Episodes in Event Sequences Data Mining and Knowledge Discovery, vol. 1, no. 3, pp. 259-289, 1997.[31] L. Maruster, W.M.P. van der Aalst, A.J.M.M. Weijters, A. van den Bosch, and W. Daelemans, Automated Discovery of Workflow Models from Hospital Data Proc. 13th Belgium-Netherlands Conf. Artificial Intelligence (BNAIC 2001), B. Kröse, M. de Rijke, G. Schreiber, and M. van Someren, eds., pp. 183-190, 2001.[32] L. Maruster, A.J.M.M. Weijters, W.M.P. van der Aalst, and A. van den Bosch, Process Mining: Discovering Direct Successors in Process Logs Proc. Fifth Int'l Conf. Discovery Science (Discovery Science 2002), pp. 364-373, 2002.[33] M.K. Maxeiner and K. Küspert, and F. Leymann, Data Mining von Workflow-Protokollen zur teilautomatisierten Konstruktion von Prozessmodellen Proc. Datenbanksysteme in Büro, Technik und Wissenschaft, pp. 75-84, 2001.[34] M. zur Mühlen, Process-Driven Management Information Systems Combining Data Warehouses and Workflow Technology Proc. Int'l Conf. Electronic Commerce Research (ICECR-4), B. Gavish, ed., pp. 550-566, 2001.[35] M. zur Mühlen, Workflow-Based Process Controlling-Or: What You Can Measure You Can Control Workflow Handbook 2001, Workflow Management Coalition, L. Fischer, ed., pp. 61-77, Lighthouse Point, Fla.: Future Strategies, 2001.[36] M. zur Mühlen and M. Rosemann, Workflow-Based Process Monitoring and Controlling Technical and Organizational Issues Proc. 33rd Hawaii Int'l Conf. System Science (HICSS-33), R. Sprague, ed., pp. 1-10, 2000.[37] T. Murata, “Petri Nets: Properties, Analysis and Application,” Proc. IEEE, vol. 77, no. 4, 1989.[38] L. Pitt, Inductive Inference, DFAs, and Computational Complexity Proc. Int'l Workshop Analogical and Inductive Inference (AII), K.P. Jantke, ed., pp. 18-44, 1889.[39] Lectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science, vol. 1491, W. Reisig and G. Rozenberg, eds., Berlin: Springer-Verlag, 1998.[40] M. Sayal, F. Casati, M.C. Shan, and U. Dayal, Business Process Cockpit Proc. 28th Int'l Conf. Very Large Data Bases (VLDB '02), pp. 880-883, 2002.[41] G. Schimm, Process Mining http:/www.processmining.de/, 2004.[42] G. Schimm, Generic Linear Business Process Modeling Proc. ER 2000 Workshop Conceptual Approaches for E-Business and The World Wide Web and Conceptual Modeling, S.W. Liddle, H.C. Mayr, and B. Thalheim, eds., pp. 31-39, 2000.[43] G. Schimm, Process Mining Elektronischer Geschäftsprozesse Proc. Elektronische Geschäftsprozesse, 2001.[44] G. Schimm, Process Mining linearer Prozessmodelle Ein Ansatz zur Automatisierten Akquisition von Prozesswissen Proc. 1. Konferenz Professionelles Wissensmanagement, 2001.[45] G. Schimm, Process Miner A Tool for Mining Process Schemes from Event-Based Data Proc. Eighth European Conf. Artificial Intelligence (JELIA), S. Flesca and G. Ianni, eds., pp. 525-528, 2002.[46] Staffware, Staffware Process Monitor (SPM),http:/www.staff ware.com, 2002.[47] H.M.W. Verbeek, T. Basten, and W.M.P. van der Aalst, Diagnosing Workflow Processes Using Woflan The Computer J., vol. 44, no. 4, pp. 246-279, 2001.[48] A.J.M.M. Weijters and W.M.P. van der Aalst, Process Mining: Discovering Workflow Models from Event-Based Data Proc. 13th Belgium-Netherlands Conf. Artificial Intelligence (BNAIC 2001), B. Kröse, M. de Rijke, G. Schreiber, and M. van Someren, eds., pp. 283-290, 2001.[49] A.J.M.M. Weijters and W.M.P. van der Aalst, Rediscovering Workflow Models from Event-Based Data Proc. 11th Dutch-Belgian Conf. Machine Learning (Benelearn 2001), V. Hoste and G. de Pauw, eds., pp. 93-100, 2001.[50] A.J.M.M. Weijters and W.M.P. van der Aalst, Workflow Mining: Discovering Workflow Models from Event-Based Data Proc. ECAI Workshop Knowledge Discovery and Spatial Data, C. Dousson, F. Höppner, and R. Quiniou, eds., pp. 78-84, 2002.
Index Terms:
Workflow mining, workflow management, data mining, Petri nets.
Citation:
Wil van der Aalst, Ton Weijters, Laura Maruster, "Workflow Mining: Discovering Process Models from Event Logs," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1128-1142, Sept. 2004, doi:10.1109/TKDE.2004.47
