Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering

ABSTRACT

A novel method for simultaneous keyphrase extraction and generic text summarization is proposed by modeling text documents as weighted undirected and weighted bipartite graphs. Spectral graph clustering algorithms are useed for partitioning sentences of the documents into topical groups with sentence link priors being exploited to enhance clustering quality. Within each topical group, saliency scores for keyphrases and sentences are generated based on a mutual reinforcement principle. The keyphrases and sentences are then ranked according to their saliency scores and selected for inclusion in the top keyphrase list and summaries of the document. The idea of building a hierarchy of summaries for documents capturing different levels of granularity is also briefly discussed. Our method is illustrated using several examples from news articles, news broadcast transcripts and web documents.

REFERENCES

• 1: Adam L. Berger , Vibhu O. Mittal, OCELOT: a system for summarizing Web pages, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.144-151, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345565]
• 2: Paul S. Bradley , Usama M. Fayyad, Refining Initial Points for K-Means Clustering, Proceedings of the Fifteenth International Conference on Machine Learning, p.91-99, July 24-27, 1998
• 3: Wesley T. Chuang , Jihoon Yang, Extracting sentence segments for text summarization: a machine learning approach, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.152-159, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345566]
• 4: J. Conroy and D. P. O'Leary. Text Summarization via Hidden Markov Models and Pivoted QR Matrix Decomposition. Technical Report, Dept. Comp. Sci., CS-TR-4221, Univ. Maryland, 2001.
• 5: Document Understanding Conference. http://www-nlpir.nist.gov/projects/duc/.
• 6: Yihong Gong , Xin Liu, Generic text summarization using relevance measure and latent semantic analysis, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.19-25, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383955]
• 7: J.A. Hartigan and M.A. Wong. (1979). A K-means Clustering Algorithm. Applied Statistics, 28:100--108.
• 8: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 9: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 10: Julian Kupiec , Jan Pedersen , Francine Chen, A trainable document summarizer, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.68-73, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215333]
• 11: L. Lovasz and M.D. Plummer. (1986) Matching Theory. Amsterdam: North Holland.
• 12: Z. Luo. Clustering under Spatial Contiguity Constraint: A penalized K-means method. Technical Report, Department of Statistics, Penn State University, 2001.
• 13: I. Mani. Automatic Summarization. John Benjamins Pub Co., 2001.
• 14: Mark T. Maybury , Inderjeet Mani, Advances in Automatic Text Summarization, MIT Press, Cambridge, MA, 1999
• 15: Tadashi Nomoto , Yuji Matsumoto, A new approach to unsupervised text summarization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.26-34, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383956]
• 16: M. Porter. The Porter Stemming Algorithm. www.tartarus.org/~martin/PorterStemmer
• 17: L. A. Ramshaw and M. P. Marcus. Text Chunking Using Transformation Based Learning. Proceedings of the Third ACL Workshop on Very Large Corpora", Cambridge MA, USA, 1995.
• 18: G. Salton, A. Singhal, M. Mitra and C. Buckley. Automatic text structuring and summarization. 341--355, Advances in Automatic Text Summarization, edited by I. Mani and M. Maybury, 1999.
• 19: Hongyuan Zha , Zhenyue Zhang, Matrices with Low-Rank-Plus-Shift Structure: Partial SVD and Latent Semantic Indexing, SIAM Journal on Matrix Analysis and Applications, v.21 n.2, p.522-536, Oct.-Jan. 2000 [doi>10.1137/S0895479898344443]
• 20: H. Zha, M. Gu, X. He, C. Ding, and H. Simon. Spectral Relaxation for K-means Clustering. Advances in Neural Information Processing Systems, 14, eds. T. Dietterich, S. Becker, Z. Ghahramani, MIT Press, 2002.
• 21: Hongyuan Zha , Xiang Ji, Correlating multilingual documents via bipartite graph modeling, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564485]

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.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Experimentation, Theory

Keywords:
bipartite graph, graph partitioning, keyphrase extraction, mutual reinforcement principle, singular value decomposition, text summarization