Mining common topics from multiple asynchronous text streams

ABSTRACT

Text streams are becoming more and more ubiquitous, in the forms of news feeds, weblog archives and so on, which result in a large volume of data. An effective way to explore the semantic as well as temporal information in text streams is topic mining, which can further facilitate other knowledge discovery procedures. In many applications, we are facing multiple text streams which are related to each other and share common topics. The correlation among these streams can provide more meaningful and comprehensive clues for topic mining than those from each individual stream. However, it is nontrivial to explore the correlation with the existence of asynchronism among multiple streams, i.e. documents from different streams about the same topic may have different timestamps, which remains unsolved in the context of topic mining. In this paper, we formally address this problem and put forward a novel algorithm based on the generative topic model. Our algorithm consists of two alternate steps: the first step extracts common topics from multiple streams based on the adjusted timestamps by the second step; the second step adjusts the timestamps of the documents according to the time distribution of the discovered topics by the first step. We perform these two steps alternately and a monotone convergence of our objective function is guaranteed. The effectiveness and advantage of our approach were justified by extensive empirical studies on two real data sets consisting of six research paper streams and two news article streams, respectively.

REFERENCES

• 1: 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]
• 2: D. M. Blei and J. D. Lafferty. Correlated topic models. In NIPS, 2005.
• 3: David M. Blei , John D. Lafferty, Dynamic topic models, Proceedings of the 23rd international conference on Machine learning, p.113-120, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143859]
• 4: D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent dirichlet allocation. In NIPS, pages 601--608, 2001.
• 5: 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
• 6: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 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: Andreas Krause , Jure Leskovec , Carlos Guestrin, Data association for topic intensity tracking, Proceedings of the 23rd international conference on Machine learning, p.497-504, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143907]
• 9: Wei Li , Andrew McCallum, Pachinko allocation: DAG-structured mixture models of topic correlations, Proceedings of the 23rd international conference on Machine learning, p.577-584, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143917]
• 10: Zhiwei Li , Bin Wang , Mingjing Li , Wei-Ying Ma, A probabilistic model for retrospective news event detection, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076055]
• 11: Qiaozhu Mei , Chao Liu , Hang Su , ChengXiang Zhai, A probabilistic approach to spatiotemporal theme pattern mining on weblogs, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135857]
• 12: 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]
• 13: David Mimno , Wei Li , Andrew McCallum, Mixtures of hierarchical topics with Pachinko allocation, Proceedings of the 24th international conference on Machine learning, p.633-640, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273576]
• 14: 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]
• 15: Xuerui Wang , Andrew McCallum, Topics over time: a non-Markov continuous-time model of topical trends, 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.1150450]
• 16: Xuanhui Wang , ChengXiang Zhai , Xiao Hu , Richard Sproat, Mining correlated bursty topic patterns from coordinated text 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.1281276]
• 17: 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]
• 18: ChengXiang Zhai , Atulya Velivelli , Bei Yu, A cross-collection mixture model for comparative text mining, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014150]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
asynchronous streams, temporal text mining, topic model