Process Discovery and Conformance Checking Using Passages

• Autorzy: van der Aalst W. M. P. , Verbeek H. M. W.

Identyfikatory

DOI

10.3233/FI-2014-1006

• Języki publikacji: EN

Abstrakty

EN

The two most prominent process mining tasks are process discovery (i.e., learning a process model from an event log) and conformance checking (i.e., diagnosing and quantifying differences between observed and modeled behavior). The increasing availability of event data makes these tasks highly relevant for process analysis and improvement. Therefore, process mining is considered to be one of the key technologies for Business Process Management (BPM). However, as event logs and process models grow, process mining becomes more challenging. Therefore, we propose an approach to decompose process mining problems into smaller problems using the notion of passages. A passage is a pair of two non-empty sets of activities (X, Y) such that the set of direct successors of X is Y and the set of direct predecessors of Y is X. Any Petri net can be partitioned using passages. Moreover, process discovery and conformance checking can be done per passage and the results can be aggregated. This has advantages in terms of efficiency and diagnostics. Moreover, passages can be used to distribute process mining problems over a network of computers. Passages are supported through ProM plug-ins that automatically decompose process discovery and conformance checking tasks.

Słowa kluczowe

EN

process mining; conformance checking; process discovery; distributed computing; business process management

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 1
• Strony: 103--138
• Opis fizyczny: Bibliogr. 50 poz., rys., tab.

Twórcy

autor

van der Aalst W. M. P.

• Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, The Netherlands

autor

Verbeek H. M. W.

• Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, The Netherlands

Bibliografia

• [1] van der Aalst, W.: The Application of Petri Nets toWorkflow Management, The Journal of Circuits, Systems and Computers, 8(1), 1998, 21–66.
• [2] van der Aalst, W.: Process Mining: Discovery, Conformance and Enhancement of Business Processes, Springer-Verlag, Berlin, 2011.
• [3] van der Aalst, W.: Decomposing Process Mining Problems Using Passages, Applications and Theory of Petri Nets 2012 (S. Haddad, L. Pomello, Eds.), 7347, Springer-Verlag, Berlin, 2012.
• [4] van der Aalst, W.: Distributed Process Discovery and Conformance Checking, International Conference on Fundamental Approaches to Software Engineering (FASE 2012) (J. Lara, A. Zisman, Eds.), 7212, Springer-Verlag, Berlin, 2012.
• [5] van der Aalst, W.: A General Divide and Conquer Approach for Process Mining, Federated Conference on Computer Science and Information Systems (FedCSIS 2013) (M. Ganzha, L. Maciaszek, M. Paprzycki, Eds.), IEEE Computer Society, 2013.
• [6] van der Aalst, W.: Decomposing Petri Nets for Process Mining: A Generic Approach, Distributed and Parallel Databases, 31(4), 2013, 471–507.
• [7] van der Aalst, W., Adriansyah, A., van Dongen, B.: Replaying History on Process Models for Conformance Checking and Performance Analysis, WIREs Data Mining and Knowledge Discovery, 2(2), 2012, 182–192.
• [8] van der Aalst,W., van Hee, K., van derWerf, J., Verdonk, M.: Auditing 2.0: Using Process Mining to Support Tomorrow’s Auditor, IEEE Computer, 43(3), 2010, 90–93.
• [9] van der Aalst, W., Rubin, V., Verbeek, H., van Dongen, B., Kindler, E., Günther, C.: Process Mining: A Two-Step Approach to Balance Between Underfitting and Overfitting, Software and Systems Modeling, 9(1), 2010, 87–111.
• [10] van der Aalst, W., Weijters, A., Maruster, L.: Workflow Mining: Discovering Process Models from Event Logs, IEEE Transactions on Knowledge and Data Engineering, 16(9), 2004, 1128–1142.
• [11] Adriansyah, A., van Dongen, B., van der Aalst, W.: Conformance Checking using Cost-Based Fitness Analysis, IEEE International Enterprise Computing Conference (EDOC 2011) (C. Chi, P. Johnson, Eds.), IEEE Computer Society, 2011.
• [12] Adriansyah, A., van Dongen, B., van der Aalst, W.: Towards Robust Conformance Checking, BPM 2010 Workshops, Proceedings of the Sixth Workshop on Business Process Intelligence (BPI2010) (M. Muehlen, J. Su, Eds.), 66, Springer-Verlag, Berlin, 2011.
• [13] Adriansyah, A., Munoz-Gama, J., Carmona, J., van Dongen, B., van der Aalst, W.: Alignment Based Precision Checking, Workshop on Business Process Intelligence (BPI 2012) (B. Weber, D. Ferreira, B. van Dongen, Eds.), Tallinn, Estonia, 2012.
• [14] Adriansyah, A., Sidorova, N., van Dongen, B.: Cost-based Fitness in Conformance Checking, International Conference on Application of Concurrency to System Design (ACSD 2011), IEEE Computer Society, 2011.
• [15] Agrawal, R., Gunopulos, D., Leymann, F.: Mining Process Models from Workflow Logs, Sixth International Conference on Extending Database Technology, 1377, Springer-Verlag, Berlin, 1998.
• [16] Agrawal, R., Shafer, J.: Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, 8(6), 1996, 962–969.
• [17] Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Process Mining Based on Regions of Languages, International Conference on Business Process Management (BPM 2007) (G. Alonso, P. Dadam, M. Rosemann, Eds.), 4714, Springer-Verlag, Berlin, 2007.
• [18] Boukala, M., Petrucci, L.: Towards Distributed Verification of Petri Nets properties, Proceedings of the International Workshop on Verification and Evaluation of Computer and Communication Systems (VECOS’07), British Computer Society, 2007.
• [19] Bratosin, C., Sidorova, N., van der Aalst, W.: Distributed Genetic Process Mining, IEEE World Congress on Computational Intelligence (WCCI 2010) (H. Ishibuchi, Ed.), IEEE, Barcelona, Spain, July 2010.
• [20] Calders, T., Guenther, C., Pechenizkiy, M., Rozinat, A.: Using Minimum Description Length for Process Mining, ACM Symposium on Applied Computing (SAC 2009), ACM Press, 2009.
• [21] Cannataro, M., Congiusta, A., Pugliese, A., Talia, D., Trunfio, P.: Distributed Data Mining on Grids: Services, Tools, and Applications, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 34(6), 2004, 2451–2465.
• [22] Carmona, J., Cortadella, J.: Process Mining Meets Abstract Interpretation, ECML/PKDD 210 (J. Balcazar, Ed.), 6321, Springer-Verlag, Berlin, 2010.
• [23] Carmona, J., Cortadella, J., Kishinevsky, M.: A Region-Based Algorithm for Discovering Petri Nets from Event Logs, Business Process Management (BPM2008), 2008.
• [24] Carmona, J., Cortadella, J., Kishinevsky, M.: Divide-and-Conquer Strategies for Process Mining, Business Process Management (BPM 2009) (U. Dayal, J. Eder, J. Koehler, H. Reijers, Eds.), 5701, Springer-Verlag, Berlin, 2009.
• [25] Cook, J., Wolf, A.: Discovering Models of Software Processes from Event-Based Data, ACM Transactions on Software Engineering and Methodology, 7(3), 1998, 215–249.
• [26] Cook, J., Wolf, A.: Software Process Validation: Quantitatively Measuring the Correspondence of a Process to a Model, ACM Transactions on Software Engineering and Methodology, 8(2), 1999, 147–176.
• [27] Darondeau, P.: Unbounded Petri Net Synthesis, Lectures on Concurrency and Petri Nets (J. Desel,W. Reisig, G. Rozenberg, Eds.), 3098, Springer-Verlag, Berlin, 2004.
• [28] van Dongen, B.: BPI Challenge 2012, 2012, Dataset. http://dx.doi.org/10.4121/uuid:3926db30-f712-4394-aebc-75976070e91f.
• [29] Goedertier, S., Martens, D., Vanthienen, J., Baesens, B.: Robust Process Discovery with Artificial Negative Events, Journal of Machine Learning Research, 10, 2009, 1305–1340.
• [30] Hilbert, M., Lopez, P.: The World’s Technological Capacity to Store, Communicate, and Compute Information, Science, 332(6025), 2011, 60–65.
• [31] IEEE Task Force on Process Mining: Process Mining Manifesto, Business Process Management Workshops (F. Daniel, K. Barkaoui, S. Dustdar, Eds.), 99, Springer-Verlag, Berlin, 2012.
• [32] Lakos, C., Petrucci, L.: Modular Analysis of Systems Composed of Semiautonomous Subsystems, Application of Concurrency to System Design (ACSD2004), IEEE Computer Society, 2004.
• [33] Manyika, J., Chui, M., Brown, B., Bughin, J., Dobbs, R., Roxburgh, C., Byers, A.: Big Data: The Next Frontier for Innovation, Competition, and Productivity, 2011, McKinsey Global Institute.
• [34] Medeiros, A., Weijters, A., van der Aalst, W.: Genetic Process Mining: An Experimental Evaluation, Data Mining and Knowledge Discovery, 14(2), 2007, 245–304.
• [35] Munoz-Gama, J., Carmona, J.: A Fresh Look at Precision in Process Conformance, Business Process Management (BPM 2010) (R. Hull, J. Mendling, S. Tai, Eds.), 6336, Springer-Verlag, Berlin, 2010.
• [36] Munoz-Gama, J., Carmona, J.: Enhancing Precision in Process Conformance: Stability, Confidence and Severity, IEEE Symposium on Computational Intelligence and Data Mining (CIDM 2011) (N. Chawla, I. King, A. Sperduti, Eds.), IEEE, Paris, France, April 2011.
• [37] Munoz-Gama, J., Carmona, J., van der Aalst, W.: Conformance Checking in the Large: Partitioning and Topology, International Conference on Business Process Management (BPM 2013) (F. Daniel, J. Wang, B. Weber, Eds.), 8094, Springer-Verlag, Berlin, 2013.
• [38] Munoz-Gama, J., Carmona, J., van der Aalst, W.: Hierarchical Conformance Checking of Process Models Based on Event Logs, Applications and Theory of Petri Nets 2013 (J. Colom, J. Desel, Eds.), 7927, Springer-Verlag, Berlin, 2013.
• [39] Polyvyanyy, A., Vanhatalo, J., Völzer, H.: Simplified Computation and Generalization of the Refined Process Structure Tree, WS-FM 2010 (M. Bravetti, T. Bultan, Eds.), 6551, Springer-Verlag, Berlin, 2011.
• [40] Rozinat, A., van der Aalst, W.: Decision Mining in ProM, International Conference on Business Process Management (BPM 2006) (S. Dustdar, J. Fiadeiro, A. Sheth, Eds.), 4102, Springer-Verlag, Berlin, 2006.
• [41] Rozinat, A., van der Aalst, W.: Conformance Checking of Processes Based on Monitoring Real Behavior, Information Systems, 33(1), 2008, 64–95.
• [42] Sole, M., Carmona, J.: Process Mining from a Basis of Regions, Applications and Theory of Petri Nets 2010 (J. Lilius, W. Penczek, Eds.), 6128, Springer-Verlag, Berlin, 2010.
• [43] Vanhatalo, J., V¨olzer, H., Koehler, J.: The Refined Process Structure Tree, Data and Knowledge Engineering, 68(9), 2009, 793–818.
• [44] Verbeek, H., van der Aalst, W.: An Experimental Evaluation of Passage-Based Process Discovery, Business Process Management Workshops, International Workshop on Business Process Intelligence (BPI 2012) (M. Rosa, P. Soffer, Eds.), 132, Springer-Verlag, Berlin, 2013.
• [45] Verbeek, H., van der Aalst, W.: Decomposing Replay Problems: A Case Study, BPM Center Report BPM-13-09, BPMcenter.org, 2013.
• [46] Weerdt, J., M. De Backer, Vanthienen, J., Baesens, B.: A Robust F-measure for Evaluating Discovered Process Models, IEEE Symposium on Computational Intelligence and Data Mining (CIDM 2011) (N. Chawla, I. King, A. Sperduti, Eds.), IEEE, Paris, France, April 2011.
• [47] Weijters, A., van der Aalst,W.: RediscoveringWorkflow Models from Event-Based Data using Little Thumb, Integrated Computer-Aided Engineering, 10(2), 2003, 151–162.
• [48] Weijters, A., van der Aalst, W., Medeiros, A.: Process Mining with the Heuristics Miner-algorithm, BETA Working Paper Series, WP 166, Eindhoven University of Technology, Eindhoven, 2006.
• [49] Weijters, A., Ribeiro, J.: Flexible Heuristics Miner (FHM), IEEE Symposium on Computational Intelligence and Data Mining (CIDM 2011) (N. Chawla, I. King, A. Sperduti, Eds.), IEEE, Paris, France, April 2011.
• [50] Werf, J., van Dongen, B., Hurkens, C., Serebrenik, A.: Process Discovery using Integer Linear Programming, Fundamenta Informaticae, 94, 2010, 387–412.