Analyzing feature trajectories for event detection

ABSTRACT

We consider the problem of analyzing word trajectories in both time and frequency domains, with the specific goal of identifying important and less-reported, periodic and aperiodic words. A set of words with identical trends can be grouped together to reconstruct an event in a completely un-supervised manner. The document frequency of each word across time is treated like a time series, where each element is the document frequency - inverse document frequency (DFIDF) score at one time point. In this paper, we 1) first applied spectral analysis to categorize features for different event characteristics: important and less-reported, periodic and aperiodic; 2) modeled aperiodic features with Gaussian density and periodic features with Gaussian mixture densities, and subsequently detected each feature's burst by the truncated Gaussian approach; 3) proposed an unsupervised greedy event detection algorithm to detect both aperiodic and periodic events. All of the above methods can be applied to time series data in general. We extensively evaluated our methods on the 1-year Reuters News Corpus [3] and showed that they were able to uncover meaningful aperiodic and periodic events.

REFERENCES

• 1: Apache lucene-core 2.0.0, http://lucene.apache.org.
• 2: Google news alerts, http://www.google.com/alerts.
• 3: Reuters corpus, http://www.reuters.com/researchandstandards/corpus/.
• 4: James Allan, Topic Detection and Tracking: Event-Based Information Organization, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: James Allan , Victor Lavrenko , Hubert Jin, First story detection in TDT is hard, Proceedings of the ninth international conference on Information and knowledge management, p.374-381, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354843]
• 6: James Allan , Courtney Wade , Alvaro Bolivar, Retrieval and novelty detection at the sentence level, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860493]
• 7: Thorsten Brants , Francine Chen , Ayman Farahat, A System for new event detection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860495]
• 8: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1):1--38, 1977.
• 9: Gabriel Pui Cheong Fung , Jeffrey Xu Yu , Philip S. Yu , Hongjun Lu, Parameter free bursty events detection in text streams, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 10: Q. He, K. Chang, and E.-P. Lim. A model for anticipatory event detection. In ER, pages 168--181, 2006.
• 11: Q. He, K. Chang, E.-P. Lim, and J. Zhang. Bursty feature reprensentation for clustering text streams. In SDM, accepted, 2007.
• 12: 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]
• 13: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the Bursty Evolution of Blogspace, World Wide Web, v.8 n.2, p.159-178, June 2005 [doi>10.1007/s11280-004-4872-4]
• 14: Giridhar Kumaran , James Allan, Text classification and named entities for new event detection, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009044]
• 15: Qiaozhu Mei , ChengXiang Zhai, Discovering evolutionary theme patterns from text: an exploration of temporal text mining, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081895]
• 16: W. D. Penny. Kullback-liebler divergences of normal, gamma, dirichlet and wishart densities. Technical report, 2001.
• 17: Nicola Stokes , Joe Carthy, Combining semantic and syntactic document classifiers to improve first story detection, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.424-425, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384068]
• 18: Russell Swan , James Allan, Automatic generation of overview timelines, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.49-56, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345546]
• 19: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 20: 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]
• 21: Yiming Yang , Jian Zhang , Jaime Carbonell , Chun Jin, Topic-conditioned novelty detection, 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.775150]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
DFT, Gaussian, event detection, feature categorization