Temporal mining for interactive workflow data analysis

ABSTRACT

In the past few years there has been an increasing interest in the analysis of process logs. Several proposed techniques, such as workflow mining, are aimed at automatically deriving the underlying workflow models. However, current approaches only pay little attention on an important piece of information contained in process logs: the timestamps, which are used to define a sequential ordering of the performed tasks. In this work we try to overcome these limitations by explicitly including time in the extracted knowledge, thus making the temporal information a first-class citizen of the analysis process. This makes it possible to discern between apparently identical process executions that are performed with different transition times between consecutive tasks.

This paper proposes a framework for the user-interactive exploration of a condensed representation of groups of executions of a given process. The framework is based on the use of an existing mining paradigm: Temporally-Annotated Sequences (TAS). These are aimed at extracting sequential patterns where each transition between two events is annotated with a typical transition time that emerges from input data. With the extracted TAS, which represent sets of possible frequent executions with their typical transition times, a few factorizing operators are built. These operators condense such executions according to possible parallel or possible mutual exclusive executions. Lastly, such condensed representation is rendered to the user via the exploration graph, namely the Temporally-Annotated Graph (TAG).

The user, the domain expert, is allowed to explore the different and alternative factorizations corresponding to different interpretations of the actual executions. According to the user choices, the system discards or retains certain hypotheses on actual executions and shows the consequent scenarios resulting from the coresponding re-aggregation of the actual data.

REFERENCES

• 1: The think3 company. http://www.think3.com.
• 2: Rakesh Agrawal, Dimitrios Gunopulos, and Frank Leymann. Mining process models from workflow logs. volume 1377--469+ of LNCS, '98.
• 3: Michele Berlingerio , Francesco Bonchi , Fosca Giannotti , Franco Turini, Mining Clinical Data with a Temporal Dimension: A Case Study, Proceedings of the 2007 IEEE International Conference on Bioinformatics and Biomedicine, p.429-436, November 02-04, 2007 [doi>10.1109/BIBM.2007.48]
• 4: Michele Berlingerio , Francesco Bonchi , Fosca Giannotti , Franco Turini, Time-Annotated Sequences for Medical Data Mining, Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, p.133-138, October 28-31, 2007 [doi>10.1109/ICDMW.2007.109]
• 5: Kalle Lyytinen , Lars Mathiassen , Janne Ropponen , Anindya Datta, Automating the Discovery of As-Is Business Process Models: Probabilistic and Algorithmic Approaches, Information Systems Research, v.9 n.3, p.275-301, March 1998 [doi>10.1287/isre.9.3.275]
• 6: Peter Lawrence, Workflow handbook 1997, John Wiley & Sons, Inc., New York, NY, 1997
• 7: Fosca Giannotti, Mirco Nanni, and Dino Pedreschi. Efficient mining of temporally annotated sequences. In Proc. of the 6th SIAM Intern. Conf. on Data Min., 2006.
• 8: Fosca Giannotti, Mirco Nanni, Dino Pedreschi, and Fabio Pinelli. Trajectory patter mining. In The 30th KDD Int.Conf. on Knowl.Disc. and Data Min., '07.
• 9: Fosca Giannotti , Mirco Nanni , Dino Pedreschi , Fabio Pinelli, Mining sequences with temporal annotations, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141413]
• 10: Gianluigi Greco , Antonella Guzzo , Giuseppe Manco , Domenico Saccí, Mining unconnected patterns in workflows, Information Systems, v.32 n.5, p.685-712, July, 2007 [doi>10.1016/j.is.2006.05.001]
• 11: Gianluigi Greco , Antonella Guzzo , Luigi Pontieri , Domenico Sacca, Discovering Expressive Process Models by Clustering Log Traces, IEEE Transactions on Knowledge and Data Engineering, v.18 n.8, p.1010-1027, August 2006 [doi>10.1109/TKDE.2006.123]
• 12: San-Yih Hwang , Chih-Ping Wei , Wan-Shiou Yang, Discovery of temporal patterns from process instances, Computers in Industry, v.53 n.3, p.345-364, April 2004 [doi>10.1016/j.compind.2003.10.006]
• 13: San-Yih Hwang , Wan-Shiou Yang, On the discovery of process models from their instances, Decision Support Systems, v.34 n.1, p.41-57, December 2002 [doi>10.1016/S0167-9236(02)00008-8]
• 14: Steffen Kempe and Jochen Hipp. Mining sequences of temporal intervals. In PKDD, pages 569--576, 2006.
• 15: Frank Höppner , Frank Klawonn, Finding Informative Rules in Interval Sequences, Proceedings of the 4th International Conference on Advances in Intelligent Data Analysis, p.125-134, September 13-15, 2001
• 16: Hongyan Ma, Process-aware information systems: Bridging people and software through process technology: Book Reviews, Journal of the American Society for Information Science and Technology, v.58 n.3, p.455-456, February 2007 [doi>10.1002/asi.v58:3]
• 17: Fabian Moerchen, Algorithms for time series knowledge mining, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150485]
• 18: Panagiotis Papapetrou , George Kollios , Stan Sclaroff , Dimitrios Gunopulos, Discovering Frequent Arrangements of Temporal Intervals, Proceedings of the Fifth IEEE International Conference on Data Mining, p.354-361, November 27-30, 2005 [doi>10.1109/ICDM.2005.50]
• 19: Dhaval Patel , Wynne Hsu , Mong Li Lee, Mining relationships among interval-based events for classification, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376658]
• 20: Po-shan Kam , Ada Wai-Chee Fu, Discovering Temporal Patterns for Interval-Based Events, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.317-326, September 04-06, 2000
• 21: S.Jablonski and C.Bussler. Workflow Management: Modeling Concepts, Architecture and Implementation. Intern. Thomson Comp. Press, 1996.
• 22: 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]
• 23: Wil M. P. van der Aalst, Jorg Desel, and Andreas Oberweis, editors. Business Process Management, Models, Techniques, and Empirical Studies, volume 1806 of LNCS. Springer, 2000.
• 24: Workflow management: models, methods, and systems, MIT Press, Cambridge, MA, 2002
• 25: T. Weijters and W. M. P. van der Aalst. Process mining: Discovering workflow models from event-based data., 2001.
• 26: Edi Winarko and John F. Roddick. Discovering richer temporal association rules from interval-based data. In A. Min Tjoa and J. Trujillo, editors, 7th DaWaK, volume 3589 of LNCS, pages 315--325. Springer, '05.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
temporal sequence mining, workflow mining