Constructing comprehensive summaries of large event sequences

ABSTRACT

Event sequences capture system and user activity over time. Prior research on sequence mining has mostly focused on discovering local patterns. Though interesting, these patterns reveal local associations and fail to give a comprehensive summary of the entire event sequence. Moreover, the number of patterns discovered can be large. In this paper, we take an alternative approach and build short summaries that describe the entire sequence, while revealing local associations among events.

We formally define the summarization problem as an optimization problem that balances between shortness of the summary and accuracy of the data description. We show that this problem can be solved optimally in polynomial time by using a combination of two dynamic-programming algorithms. We also explore more efficient greedy alternatives and demonstrate that they work well on large datasets. Experiments on both synthetic and real datasets illustrate that our algorithms are efficient and produce high-quality results, and reveal interesting local structures in the data.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Richard Bellman, On the approximation of curves by line segments using dynamic programming, Communications of the ACM, v.4 n.6, p.284, June 1961 [doi>10.1145/366573.366611]
• 3: Darya Chudova , Padhraic Smyth, Pattern discovery in sequences under a Markov assumption, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775070]
• 4: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 5: Panagiotis Karras , Dimitris Sacharidis , Nikos Mamoulis, Exploiting duality in summarization with deterministic guarantees, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281235]
• 6: Eamonn J. Keogh , Selina Chu , David Hart , Michael J. Pazzani, An Online Algorithm for Segmenting Time Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.289-296, November 29-December 02, 2001
• 7: Pekka Kilpeläinen , Heikki Mannila , Esko Ukkonen, MDL learning of unions of simple pattern languages from positive examples, Proceedings of the Second European Conference on Computational Learning Theory, p.252-260, March 13-15, 1995
• 8: M. Koivisto, M. Perola, T. Varilo, et al. An MDL method for finding haplotype blocks and for estimating the strength of haplotype block boundaries. In Pacific Symposium on Biocomputing, pages 502--513, 2003.
• 9: Heikki Mannila , Marko Salmenkivi, Finding simple intensity descriptions from event sequence data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.341-346, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502562]
• 10: H. Mannila and H. Toivonen. Discovering generalized episodes using minimal occurrences. In KDD , pages 146--151, 1996.
• 11: M. Mehta, J. Rissanen, and R. Agrawal. Mdl-based decision tree pruning. In KDD, pages 216--221, 1995.
• 12: Spiros Papadimitriou , Philip Yu, Optimal multi-scale patterns in time series streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142545]
• 13: Jian Pei , Jiawei Han , Wei Wang, Constraint-based sequential pattern mining: the pattern-growth methods, Journal of Intelligent Information Systems, v.28 n.2, p.133-160, April 2007 [doi>10.1007/s10844-006-0006-z]
• 14: L. R. Rabiner and B. H. Juang. An introduction to Hidden Markov Models. IEEE ASSP Magazine, pages 4--15, January 1986.
• 15: J. Rissanen. Modeling by shortest data description. Automatica, 14:465--471, 1978.
• 16: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 17: Yasushi Sakurai , Spiros Papadimitriou , Christos Faloutsos, BRAID: stream mining through group lag correlations, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066226]
• 18: E. Terzi and P. Tsaparas. Efficient algorithms for sequence segmentation. In SDM, 2006.
• 19: Jiong Yang , Wei Wang , Philip S. Yu , Jiawei Han, Mining long sequential patterns in a noisy environment, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564738]
• 20: Yunyue Zhu , Dennis Shasha, StatStream: statistical monitoring of thousands of data streams in real time, Proceedings of the 28th international conference on Very Large Data Bases, p.358-369, August 20-23, 2002, Hong Kong, China

INDEX TERMS

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

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Experimentation, Theory

Keywords:
dynamic programming, event sequences, log mining, minimum description length, summarization