Domain-independent text segmentation using anisotropic diffusion and dynamic programming

ABSTRACT

This paper presents a novel domain-independent text segmentation method, which identifies the boundaries of topic changes in long text documents and/or text streams. The method consists of three components: As a preprocessing step, we eliminate the document-dependent stop words as well as the generic stop words before the sentence similarity is computed. This step assists in the discrimination of the sentence semantic information. Then the cohesion information of sentences in a document or a text stream is captured with a sentence-distance matrix with each entry corresponding to the similarity between a sentence pair. The distance matrix can be represented with a gray-scale image. Thus, a text segmentation problem is converted into an image segmentation problem. We apply the anisotropic diffusion technique to the image representation of the distance matrix to enhance the semantic cohesion of sentence topical groups as well as sharpen topical boundaries. At last, the dynamic programming technique is adapted to find the optimal topical boundaries and provide a zoom-in and zoom-out mechanism for topics access by segmenting text in variable numbers of sentence topical groups. Our approach involves no domain-specific training, and it can be applied to texts in a variety of domains. The experimental results show that our approach is effective in text segmentation and outperforms several state-of-the-art methods.

REFERENCES

• 1: J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y. Yang. Topic Dectection and Tracking pilot study final report. In Proceedings of the DARPA broadcast news transcription and understanding workshop, pp.194--218, 1998.
• 2: Doug Beeferman , Adam Berger , John Lafferty, Statistical Models for Text Segmentation, Machine Learning, v.34 n.1-3, p.177-210, Feb. 1999 [doi>10.1023/A:1007506220214]
• 3: Branimir K. Boguraev , Mary S. Neff, Discourse Segmentation in Aid of Document Summarization, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 3, p.3004, January 04-07, 2000
• 4: David M. Blei , Pedro J. Moreno, Topic segmentation with an aspect hidden Markov model, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.343-348, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384021]
• 5: Thorsten Brants , Francine Chen , Ioannis Tsochantaridis, Topic-based document segmentation with probabilistic latent semantic analysis, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584829]
• 6: James P. Callan, Passage-level evidence in document retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.302-310, July 03-06, 1994, Dublin, Ireland
• 7: Freddy Y. Y. Choi, Advances in domain independent linear text segmentation, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.26-33, April 29-May 04, 2000, Seattle, Washington
• 8: Mochizuki Hajime , Honda Takeo , Okumura Manabu, Text segmentation with multiple surface linguistic cues, Proceedings of the 36th annual meeting on Association for Computational Linguistics, p.881-885, August 10-14, 1998, Montreal, Quebec, Canada
• 9: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 10: Marti A. Hearst, Multi-paragraph segmentation of expository text, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.9-16, June 27-30, 1994, Las Cruces, New Mexico [doi>10.3115/981732.981734]
• 11: Marti A. Hearst, TextTiling: segmenting text into multi-paragraph subtopic passages, Computational Linguistics, v.23 n.1, p.33-64, March 1997
• 12: Oskari Heinonen, Optimal multi-paragraph text segmentation by dynamic programming, Proceedings of the 36th annual meeting on Association for Computational Linguistics, August 10-14, 1998, Montreal, Quebec, Canada [doi>10.3115/980691.980814]
• 13: T. K. Ho. Stop Word Location and Identification for Adaptive Text Recognition. International Journal of Document Analysis and Recognition, 3, 1, August 2000.
• 14: X. Ji and H. Zha. Extracting Shared Topics of Multiple Documents. In Proceedings of the 7th Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2003.
• 15: M. Y. Kan, J. L. Klavans, and K. R. McKeown. Linear segmentation and segment significance. In Proc. of the 6th International Workshop of Very Large Corpora, pp.197--205, 1998.
• 16: Hideki Kozima, Text segmentation based on similarity between words, Proceedings of the 31st annual meeting on Association for Computational Linguistics, June 22-26, 1993, Columbus, Ohio [doi>10.3115/981574.981616]
• 17: I. Mani. Automatic Summarization. John Benjamins Pub Co., 2001.
• 18: P. Perona , J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.629-639, July 1990 [doi>10.1109/34.56205]
• 19: Jay M. Ponte , W. Bruce Croft, Text Segmentation by Topic, Proceedings of the First European Conference on Research and Advanced Technology for Digital Libraries, p.113-125, September 01-03, 1997
• 20: M. Porter. The Porter Stemming Algorithm. www.tartarus.org/~martin/PorterStemmer
• 21: Lev Pevzner , Marti A. Hearst, A critique and improvement of an evaluation metric for text segmentation, Computational Linguistics, v.28 n.1, p.19-36, March 2002 [doi>10.1162/089120102317341756]
• 22: Jeffrey C. Reynar, Statistical models for topic segmentation, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.357-364, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034735]
• 23: Gerard Salton , J. Allan , Chris Buckley, Approaches to passage retrieval in full text information systems, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.49-58, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160693]
• 24: Gerard Salton , Amit Singhal , Chris Buckley , Mandar Mitra, Automatic text decomposition using text segments and text themes, Proceedings of the the seventh ACM conference on Hypertext, p.53-65, March 16-20, 1996, Bethesda, Maryland, United States [doi>10.1145/234828.234834]
• 25: Masao Utiyama , Hitoshi Isahara, A statistical model for domain-independent text segmentation, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.499-506, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073076]
• 26: C. Wayne. Multilingual Topic Detection and Tracking: Successful Research Enabled by Corpora and Evaluation. In Proc. of Language Resources and Evaluation Conference, pages 1487--1494, 2000
• 27: Y. Yamron. Segmentation of expository texts by hierarchical agglomerative clustering. In Proc. of Recent Advances in Natural Language Proceessings, 1997.
• 28: Hongyuan Zha, Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering, 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.564398]
• 29: 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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing

General Terms:
Algorithms, Experimentation, Theory

Keywords:
anisotropic diffusion, document-dependent stop words, dynamic programming, text segmentation