Light Region-based Techniques for Process Discovery

• Autorzy: Solé M. , Carmona J.
• Języki publikacji: EN

Abstrakty

EN

A central problem in the area of Process Mining is to obtain a formal model that represents selected behavior of a system. The theory of regions has been applied to address this problem, enabling the derivation of a Petri net whose language includes a set of traces. However, when dealing with real-life systems, the available tool support for performing such a task is unsatisfactory, due to the complex algorithms that are required. In this paper, the theory of regions is revisited to devise a novel technique that explores the space of regions by combining the elements of a region basis. Due to its light space requirements, the approach can represent an important step for bridging the gap between the theory of regions and its industrial application. Experimental results show that there is improvement in orders of magnitude in comparison with state-of-the-art tools for the same task.

Słowa kluczowe

EN

knowledge discovery; data and process re-engineering; visualization; process mining; region theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 3/4
• Strony: 343--376
• Opis fizyczny: Bibliogr. 36 poz., tab., wykr.

Twórcy

autor

Solé M.

autor

Carmona J.

• Campus Nord edifici Omega despatx 111, UPC, Barcelona, Spain,

Bibliografia

• [1] 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, 2009.
• [2] van der Aalst, W. M. P.: Process-Aware Information Systems: Lessons to Be Learned from Process Mining, Transactions on Petri Nets and Other Models of Concurrency (ToPNoC), 2, 2009, 1-26.
• [3] van der Aalst, W. M. P., van Dongen, B. F., Günther, C. W., Mans, R. S., de Medeiros, A. K. A., Rozinat, A., Rubin, V., Song, M., Verbeek, H. M. W. E., Weijters, A. J. M. M.: ProM 4.0: Comprehensive Support for real Process Analysis, Int. Conf. on Applications and Theory of Petri Nets and OtherModels of Concurrency, 4546, 2007, 484-494.
• [4] van der Aalst, W. M. P., de Medeiros, A. K. A., Weijters, A. J. M. M.: Genetic Process Mining, Int. Conf. on Applications and Theory of Petri Nets and Other Models of Concurrency, 3536, 2005, 48-69.
• [5] van der Aalst, W. M. P., Weijters, T., Maruster, L.: Workflow Mining: Discovering Process Models from Event Logs, IEEE Transactions on Knowledge and Data Engineering, 16(9), 2004, 1128-1142.
• [6] van Dongen W.M.P. van der Aalst A.K.A de Medeiros, B., Weijters, A.: Process Mining: Extending the alpha-algorithm to Mine Short Loops, Technical Report BETA Working Paper Series, WP 113, Eindhoven University of Technology, 2004.
• [7] Arnold, A.: Finite Transition Systems, Prentice Hall, 1994.
• [8] Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial Algorithms for the Synthesis of Bounded Nets, Theory and Practice of Software Development (TAPSOFT), 915, 1995, 364-383.
• [9] Badouel, E., Darondeau, P.: Theory of Regions, Petri Nets, 1491, 1998, 529-586.
• [10] Bergenthum, R., Desel, J., Lorenz, R., S.Mauser: Process Mining Based on Regions of Languages, Business Process Management, September 2007, 375-383.
• [11] Bernardinello, L.: Synthesis of Net Systems, Application and Theory of Petri Nets, 691, Springer Verlag, 1993, 89-105.
• [12] Bernardinello, L., Michelis, G. D., Petruni, K., Vigna, S.: On the Synchronic Structure of Transition Systems., Proc. of the Int. Workshop on Structures in Concurrency Theory (STRICT), 1995, 69-84.
• [13] Carmona, J., Cortadella, J., Kishinevsky, M.: A Region-based Algorithm for Discovering Petri nets from Event Logs, Business Process Management, 2008, 358-373.
• [14] Carmona, J., Cortadella, J., Kishinevsky,M.: Genet: A Tool for the Synthesis and Mining of Petri Nets, Int. Conf. on Application of Concurrency to System Design (ACSD), 2009, 181-185.
• [15] Carmona, J., Cortadella, J., Kishinevsky, M.: New Region-Based Algorithms for Deriving Bounded Petri nets, IEEE Transactions on Computers, 2009.
• [16] Cortadella, J., Kishinevsky,M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: A Tool forManipulating Concurrent Specifications and Synthesis of Asynchronous Controllers, Information and Systems, E80-D(3), March 1997, 315-325.
• [17] Cortadella, J., Kishinevsky,M., Lavagno, L., Yakovlev, A.: Deriving Petri nets from finite transition systems, IEEE Transactions on Computers, 47(8), August 1998, 859-882.
• [18] Desel, J., Reisig, W.: The Synthesis Problem of Petri Nets, Acta Informatica, 33(4), 1996, 297-315.
• [19] Ehrenfeucht, A., Rozenberg, G.: Partial (Set) 2-Structures. Part I, II, Acta Informatica, 27, 1990, 315-368.
• [20] Gao, D., Liu, Q.: An improved simulated annealing algorithm for process mining, Int. Conf. on Computer Supported Cooperative Work in Design (CSCWD), 2009, 474-479.
• [21] Gu, C.-Q., Chang, H.-Y., Yi, Y.: Workflow mining: Extending the α-algorithm to mine duplicate tasks, Int. Conf. on Machine Learning and Cybernetics, 1, july 2008, 361-368.
• [22] van Hee, K., Sidorova, N., Voorhoeve,M.: Resource-ConstrainedWorkflow Nets, Fundamenta Informaticae, 71(2,3), 2006, 243-257.
• [23] Juhás, G., Kazlov, I., Juhásová, A.: Instance Deadlock: A Mystery behind Frozen Programs, Petri Nets, 6128, 2010, 1-17.
• [24] Li, J., Liu, D., Yang, B.: Process Mining: Extending α-Algorithm to Mine Duplicate Tasks in Process Logs, in: Advances in Web and Network Technologies, and Information Management, vol. 4537 of LNCS, Springer, 2007, 396-407.
• [25] Mukund,M.: Petri Nets and Step Transition Systems, Int. Journal of Foundations of Computer Science, 3(4), 1992, 443-478.
• [26] Murata, T.: Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, April 1989, 541-580.
• [27] Nüttgens, M., Feld, T., Zimmermann, V.: Business Process Modeling with EPC and UML: Transformation or Integration?, UML Workshop, 1997, 250-261.
• [28] Rozinat, A., van der Aalst, W. M. P.: Conformance checking of processes based on monitoring real behavior, Information and Systems, 33(1), 2008, 64-95.
• [29] Schrijver, A.: Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1986.
• [30] Solé, M.: The way of the lazy: on the verification of timed concurrent systems using relative timing, Ph.D. Thesis, Universitat Polit`ecnica de Catalunya, April 2009.
• [31] Solé, M.: rbminer, http://personals.ac.upc.edu/msole/homepage/rbminer.html, 2010.
• [32] Solé, M., Carmona, J.: Process Mining from a Basis of State Regions, Petri Nets, 6128, 2010, 226-245.
• [33] Solé, M., Carmona, J.: rbminer:: A Tool for Discovering Petri Nets from Transition Systems, Automated Technology for Verification and Analysis (ATVA), 2010, 396-402.
• [34] Weijters, A., van der Aalst, W., de Medeiros, A. A.: Process Mining with the Heuristics Miner-algorithm, Technical ReportWP 166, BETA Working Paper Series, Eindhoven University of Technology, 2006.
• [35] Wen, L.,Wang, J., Sun, J.-G.: Detecting ImplicitDependenciesBetween Tasks fromEvent Logs, Asia-Pacific Web Conference (APWeb), 3841, 2006, 591-603.
• [36] van der Werf, J. M. E. M., van Dongen, B. F., Hurkens, C. A. J., Serebrenik, A.: Process Discovery Using Integer Linear Programming, Petri Nets, 5062, 2008, 368-387.