A genetic programming approach to business process mining

ABSTRACT

The aim of process mining is to identify and extract process patterns from data logs to reconstruct an overall process flowchart. As business processes become more and more complex there is a need for managers to understand the processes they already have in place. To undertake such a task manually would be extremely time consuming so the practice of process mining attempts to automatically reconstruct the correct representation of a process based on a set of process execution traces. This paper outlines an alternative approach to business process mining utilising a Genetic Programming (GP) technique coupled with a graph based representation. The graph based representation allows greater flexibility in the analysis of process flowchart structure and offers the possibility of mining complex business processes from incomplete or problematic event logs. A number of event logs have been mined by the GP technique featured in this paper and the results of the experimentation point towards the potential of this novel process mining approach.

REFERENCES

• 1: W. M. P. van der Aalst , A. J. M. M. Weijters, Process mining: a research agenda, Computers in Industry, v.53 n.3, p.231-244, April 2004 [doi>10.1016/j.compind.2003.10.001]
• 2: W. M. P. van der Aalst , B. F. van Dongen , J. Herbst , L. Maruster , G. Schimm , A. J. M. M. Weijters, Workflow mining: a survey of issues and approaches, Data & Knowledge Engineering, v.47 n.2, p.237-267, November 2003 [doi>10.1016/S0169-023X(03)00066-1]
• 3: Rakesh Agrawal , Dimitrios Gunopulos , Frank Leymann, Mining Process Models from Workflow Logs, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.469-483, March 23-27, 1998
• 4: Alves de Medeiros, A.K., Genetic Process Mining. Ph.D Thesis, Eindhoven Technical University, Eindhoven, The Netherlands, 2006.
• 5: Alves de Medeiros, A.K., van Dongen, B.F., van der Aalst, W.M.P., Weijters, A.J.M.M. Process mining: extending the a-algorithm to mine short loops, Beta Working Paper, Eindhoven University of Technology, The Netherlands, 2004.
• 6: A. K. Medeiros , A. J. Weijters , W. M. Aalst, Genetic process mining: an experimental evaluation, Data Mining and Knowledge Discovery, v.14 n.2, p.245-304, April 2007 [doi>10.1007/s10618-006-0061-7]
• 7: Ashlock, D., Smucker, M., Walker, J. Graph based genetic algorithms, Congress on Evolutionary Computation-CEC99, Vol. 2, 6-9 July 1999, IEEE, Washington, DC, USA, pp. 1362--1368, 1999.
• 8: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 9: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 10: Dongen, B.F., Alves de Medeiros, A. K., Verbeek, H.M.W., Weijters, A.J.M.M., Aalst, W.M.P. The ProM framework: - a new era in process mining tool support, in Proceedings of 26th International Conference on Applications and Theory of Petri Nets (ICATPN 2005),G. Ciardo, and P. Darondeau, Eds. Heidelberg, Springer Verlag, pp. 444--454, 2005.
• 11: Hirasawa, K., Okubo, M., Katagiri, H., Hu, J. and Murata, J. Comparison between Genetic Network Programming (GNP) and Genetic Programming (GP), Proceedings of the 2001 Congress on Evolutionary Computation, Vol. 2, 27-30 May 2001, IEEE, Seoul, South Korea, pp. 1276--1282, 2001.
• 12: Gregory S. Hornby, Shortcomings with using edge encodings to represent graph structures, Genetic Programming and Evolvable Machines, v.7 n.3, p.231-252, October 2006 [doi>10.1007/s10710-006-9007-5]
• 13: JGraphT, An open source Java graph library that provides mathematical graph-theory objects and algorithms, http://www.jgrapht.org/, viewed 01/18/2008.
• 14: John R. Koza , James P. Rice, Genetic programming (videotape): the movie, MIT Press, Cambridge, MA, 1992
• 15: Miller, J.F., Banzhaf, W. Evolving the program for a cell: from French flags to Boolean circuits, in On Growth, Form and Computers, S. J. Kumar and P. J. Bentley, Eds. New York: Academic, pp. 278--301, 2003.
• 16: Poli R. Evolution of graph-like programs with parallel distributed genetic programming, In E Goodman, Ed. Proceedings of Seventh International Conference on Genetic Algorithms, Michigan State University, pp. 346--353, East Lansing, USA, Morgan Kaufmann, 1997.
• 17: Shinichi Shirakawa , Shintaro Ogino , Tomoharu Nagao, Graph structured program evolution, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277290]
• 18: Wang, J., Fan, Z., Terpenny, J. P. and Goodman, E. D. Knowledge interaction with genetic programming in Mechatronic systems design using bond graphs", IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 35(2):pp. 172--182, 2005.
• 19: Weijters, A.J.M.M., van der Aalst, W.M.P. Process mining: discovering workflow models from event based data, in Kröse, B, Rijke., M, Schreiber, G, Someren, M, Eds. Proceedings of the 13th Belgium-Netherlands Conference on Artificial Intelligence, Amsterdam, The Netherlands, pp. 283--290, 2001.
• 20: A. J. M. M. Weijters , W. M. P. van der Aalst, Rediscovering workflow models from event-based data using little thumb, Integrated Computer-Aided Engineering, v.10 n.2, p.151-162, April 2003
• 21: Jason M. Daida , Adam M. Hilss , David J. Ward , Stephen L. Long, Visualizing Tree Structures in Genetic Programming, Genetic Programming and Evolvable Machines, v.6 n.1, p.79-110, March 2005 [doi>10.1007/s10710-005-7621-2]
• 22: Daida, J.M., Hilss, A.M., Identifying structural mechanisms in standard genetic programming, in Genetic and evolutionary computing - GECCO 2003, E. Cantu - Paz et al., Eds. Berlin: Springer-Verlag., pp. 1639--1651, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Experimentation

Keywords:
business process mining, genetic programming, graph based representation