Stream prediction using a generative model based on frequent episodes in event sequences

ABSTRACT

This paper presents a new algorithm for sequence prediction over long categorical event streams. The input to the algorithm is a set of target event types whose occurrences we wish to predict. The algorithm examines windows of events that precede occurrences of the target event types in historical data. The set of significant frequent episodes associated with each target event type is obtained based on formal connections between frequent episodes and Hidden Markov Models (HMMs). Each significant episode is associated with a specialized HMM, and a mixture of such HMMs is estimated for every target event type. The likelihoods of the current window of events, under these mixture models, are used to predict future occurrences of target events in the data. The only user-defined model parameter in the algorithm is the length of the windows of events used during model estimation. We first evaluate the algorithm on synthetic data that was generated by embedding (in varying levels of noise) patterns which are preselected to characterize occurrences of target events. We then present an application of the algorithm for predicting targeted user-behaviors from large volumes of anonymous search session interaction logs from a commercially-deployed web browser tool-bar.

REFERENCES

• 1: J. Bilmes. A gentle tutorial on the EM algorithm and its application to parameter estimation for gaussian mixture and hidden markov models. Technical Report TR-97-021, International Computer Science Institute, Berkeley, California, Apr. 1997.
• 2: Thomas G. Dietterich , Ryszard S. Michalski, Discovering patterns in sequences of events, Artificial Intelligence, v.25 n.2, p.187-232, Feb. 1985 [doi>10.1016/0004-3702(85)90003-7]
• 3: D. Downey, S. T. Dumais, and E. Horvitz. Models of searching and browsing: Languages, studies and applications. In Proceedings of International Joint Conference on Artificial Intelligence, pages 2740--2747, 2007.
• 4: Allison P. Heath , Ryen W. White, Defection detection: predicting search engine switching, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367712]
• 5: Yun-Fang Juan , Chi-Chao Chang, An analysis of search engine switching behavior using click streams, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062863]
• 6: F. Korkmazskiy , B. Juang , F. Soong, Generalized Mixture of HMMs for Continuous Speech Recognition, Proceedings of the 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '97)-Volume 2, p.1443, April 21-24, 1997
• 7: Srivatsan Laxman , Prasad Naldurg , Raja Sripada , Ramarathnam Venkatesan, Connections between Mining Frequent Itemsets and Learning Generative Models, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.571-576, October 28-31, 2007 [doi>10.1109/ICDM.2007.83]
• 8: Srivatsan Laxman , P. S. Sastry , K. P. Unnikrishnan, Discovering Frequent Episodes and Learning Hidden Markov Models: A Formal Connection, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1505-1517, November 2005 [doi>10.1109/TKDE.2005.181]
• 9: Srivatsan Laxman , P. S. Sastry , K. P. Unnikrishnan, A fast algorithm for finding frequent episodes in event streams, 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.1281238]
• 10: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 11: Tridas Mukhopadhyay , Uday Rajan , Rahul Telang, Competition between Internet Search Engines, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 8, p.80216.1, January 05-08, 2004
• 12: Ricardo Vilalta , Sheng Ma, Predicting Rare Events In Temporal Domains, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.474, December 09-12, 2002
• 13: G. M. Weiss and H. Hirsh. Learning to predict rare events in event sequences. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining (KDD 98), pages 359--363, New York City, NY, USA, Aug. 27-31 1998.
• 14: A. Ypma and T. Heskes. Automatic categorization of web pages and user clustering with mixtures of Hidden Markov Models. In Lecture Notes in Computer Science, Proceedings of WEBKDD 2002 - Mining Web Data for Discovering Usage Patterns and Profiles, volume 2703, pages 35--49, 2003.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
event prediction, event sequences, frequent episodes, generative models, hidden markov models, mixture of HMMs, stream prediction, temporal data mining