An investigation of linguistic features and clustering algorithms for topical document clustering

ABSTRACT

We investigate four hierarchical clustering methods (single-link, complete-link, groupwise-average, and single-pass) and two linguistically motivated text features (noun phrase heads and proper names) in the context of document clustering. A statistical model for combining similarity information from multiple sources is described and applied to DARPA's Topic Detection and Tracking phase 2 (TDT2) data. This model, based on log-linear regression, alleviates the need for extensive search in order to determine optimal weights for combining input features. Through an extensive series of experiments with more than 40,000 documents from multiple news sources and modalities, we establish that both the choice of clustering algorithm and the introduction of the additional features have an impact on clustering performance. We apply our optimal combination of features to the TDT2 test data, obtaining partitions of the documents that compare favorably with the results obtained by participants in the official TDT2 competition.

REFERENCES

• 1: John Aberdeen , John Burger , David Day , Lynette Hirschman , Patricia Robinson , Marc Vilain, MITRE: description of the Alembic system used for MUC-6, Proceedings of the 6th conference on Message understanding, November 06-08, 1995, Columbia, Maryland [doi>10.3115/1072399.1072413]
• 2: D. M. Bates and D. G. Watts. NonlinearRegressionAnalysis and its Applications. Wiley, New York, 1988.
• 3: William W. Cohen, Integration of heterogeneous databases without common domains using queries based on textual similarity, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.201-212, June 01-04, 1998, Seattle, Washington, United States
• 4: J. Fiscus, G. Doddington, J. Garofolo, and A. Martin. NIST's 1998 Topic Detection and Tracking evaluation (TDT2). In Proceedings of the 1999 DARPA Broadcast News Workshop, pages 19-24, Hemdon, Virginia, February-March 1999.
• 5: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: L. Gay , W. Croft, Interpreting nominal compounds for information retrieval, Information Processing and Management: an International Journal, v.26 n.1, p.21-38, 1990 [doi>10.1016/0306-4573(90)90007-O ]
• 7: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 8: L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley, New York, 1990.
• 9: Mark Llberman. Topic Detection and Tracking Principal Investigators meeting, 1998.
• 10: Stephen A. Lowe. The beta-bmomml mixture model and its application to TDT tracking and detection. In Proceedings of the 1999 DARPA Broadcast News Workshop, pages 127-131, Hemdon, Virginia, February-March 1999.
• 11: Kathleen R. McKeown , Judith L. Klavans , Vasileios Hatzivassiloglou , Regina Barzilay , Eleazar Eskin, Towards multidocument summarization by reformulation: progress and prospects, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.453-460, July 18-22, 1999, Orlando, Florida, United States
• 12: National Institute of Standards and Technology. The Topic Detection and Tracking Phase 2 (TDT2) evaluation plan, 1998. Version 3.7, August 3rd, 1998. Available from http://www.itl .nist.gov/iaui/894. 01/ tdt98/doc/tdt2, eval .plan. 98 .v3.7 .pdf.
• 13: Ron Papka, James Allan, and Victor Lavrenko. UMass approaches to detection and tracking at TDT2. In Proceedings of the 1999 DARPA Broadcast News Workshop, pages 111-116, Hemdon, Virginia, February-March 1999.
• 14: Carl L. Sable , Vasileios Hatzivassiloglou, Text-Based Approaches for the Categorization of Images, Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries, p.19-38, September 22-24, 1999
• 15: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0 ]
• 16: G. Salton , M. Smith, On the application of syntactic methodologies in automatic text analysis, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.137-150, June 25-28, 1989, Cambridge, Massachusetts, United States
• 17: T. J. Santner and D. E. Duffy. The Statistical Analysis of Discrete Data. Springer-Verlag, New York, 1989.
• 18: Alan F. Smeaton, Progress in the application of natural language processing to information retrieval tasks, The Computer Journal, v.35 n.3, p.268-278, June 1992 [doi>10.1093/comjnl/35.3.268]
• 19: N. Wacholder. Simplex NPs clustered by head: A method for identifying significant topics in a document. In Proceedings of the COLING/ACL Workshop on the Computational Treatment of Nominals, pages 70-79, Montreal, Canada, October 1998.
• 20: Nina Wacholder , Yael Ravin , Misook Choi, Disambiguation of proper names in text, Proceedings of the fifth conference on Applied natural language processing, p.202-208, March 31-April 03, 1997, Washington, DC [doi>10.3115/974557.974587]
• 21: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 22: 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:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

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

General Terms:
Algorithms, Experimentation