LIPED: HMM-based life profiles for adaptive event detection

ABSTRACT

In this paper, the proposed LIPED (LIfe Profile based Event Detection) employs the concept of life profiles to predict the activeness of event for effective event detection. A group of events with similar activeness patterns shares a life profile, modeled by a hidden Markov model. Considering the burst-and-diverse property of events, LIPED identifies the activeness status of event. As a result, LIPED balances the clustering precision and recall to achieve better F1 scores than other well known approaches evaluated on the official TDT1 corpus.

REFERENCES

• 1: Charu C. Aggarwal, A framework for diagnosing changes in evolving data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872826]
• 2: Aizen, J., Huttenlocher, D., Kleinberg, J., and Novak, A. Traffic-Based Feedback on the Web. In Proceedings of the National Academy of Sciences: 101, 2004, 5254--5260.
• 3: James Allan , Ron Papka , Victor Lavrenko, On-line new event detection and tracking, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.37-45, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290954]
• 4: Allan, J., Carbonell, J., Doddington, G., Yamron, J., and Yang, Y. Topic Detection and Tracking Pilot Study: Final Report. In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop, 1998, 194--218.
• 5: Baum, L. E., Petrie, T., Soules, G., and Weiss, N. A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains. In Annals of Mathematical Statistics: 41, 1970, 164--171.
• 6: Dempster, A. P., Laird, N. M., and Rubin, D. B. Maximum likelihood from incomplete data via the EM algorithm. In Journal of the Royal Statistical Society. Series B 39, 1977, 1--38.
• 7: Jon Kleinberg, Bursty and hierarchical structure in streams, 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.775061]
• 8: Ghahramani, S. Fundamentals of Probability. Prentice Hall, 2000.
• 9: Markov, A. A. An example of statistical investigation in the text of 'Eugene Onyegin' illustrating coupling of 'tests' in chains. In Proceedings of the Academy of Sciences 7, 1913, 153--162.
• 10: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 11: Myers, C., Rabiner, L. R., and Rosenberg, A. E. Performance Tradeoffs in Dynamic Time Warping Algorithms for Isolated Word Recognition. In IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-28, No. 6, Dec, 1980, 623--635.
• 12: Rabiner, L. R. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. In Proceedings of the IEEE, 77(2), 1989, 257--286.
• 13: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 14: Viterbi, A. J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. In IEEE Transactions on Information Theory IT-13, 1967, 1260--1269.
• 15: Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290953]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
clustering, event detection, hidden markov models, life profiles