Classification algorithms for NETNEWS articles

ABSTRACT

We propose several algorithms using the vector space model to classify the news articles posted on the NETNEWS according to the newsgroup categories. The baseline method combines the terms of all the articles of each newsgroup in the training set to represent the newsgroups as single vectors. After training, the incoming news articles are classified based on their similarity to the existing newsgroup categories. We propose to use the following techniques to improve the classification performance of the baseline method: (1) use routing (classification) accuracy and the similarity values to refine the training set; (2) update the underlying term structures periodically during testing; and (3) apply k-means clustering to partition the newsgroup articles and represent each newsgroup by k vectors. Our test collection consists of the real news articles and the 519 subnewsgroups under the REC newsgroup of NETNEWS in a period of 3 months. Our experimental results demonstrate that the technique of refining the training set reduces from one-third to two-thirds of the storage. The technique of periodical updates improves the routing accuracy ranging from 20% to 100% but incurs runtime overhead. Finally, representing each newsgroup by k vectors (with k = 2 or 3) using clustering yields the most significant improvement in routing accuracy, ranging from 60% to 100%, while causing only slightly higher storage requirements.

REFERENCES

• 1: Eric W. Brown , James P. Callan , W. Bruce Croft, Fast Incremental Indexing for Full-Text Information Retrieval, Proceedings of the 20th International Conference on Very Large Data Bases, p.192-202, September 12-15, 1994
• 2: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 3: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 4: W. Francis and H. Kucera. Frequency Analysis of English Usage, New York: Houghton Mifflin, 1982.
• 5: Hector Garcia-Molina , Wilburt Labio , Jun Yang, Expiring Data in a Warehouse, Proceedings of the 24rd International Conference on Very Large Data Bases, p.500-511, August 24-27, 1998
• 6: J. Gonzalo, F. Verdejo, I. Chugur, J Cigarran. "Indexing with WordNet Synsets can Improve Text Retrieval", Coling-ACL'98 Workshop: Usage of Word- Net in Natural Language Processing Systems, pp. 38- 44, August 1998.
• 7: A.D. Gordon. Classification, Chapman and Hall, 1981.
• 8: W. Hsu, and S. Lang, "NETNEWS Classification via Batch Routing and Updates", Proceedings of international Conference of Information Resources Management Association, May 1999.
• 9: Paul S. Jacobs, Using Statistical Methods to Improve Knowledge-Based News Categorization, IEEE Expert: Intelligent Systems and Their Applications, v.8 n.2, p.13-23, April 1993 [doi>10.1109/64.207425]
• 10: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 11: Wai Lam , Chao Yang Ho, Using a generalized instance set for automatic text categorization, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.81-89, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290961]
• 12: K. Lang. "Newsweeder: Learning to filter netnews", Proceedings of International Conference on Machine Learning, pp. 331-339, July 1995.
• 13: David D. Lewis , Robert E. Schapire , James P. Callan , Ron Papka, Training algorithms for linear text classifiers, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243277]
• 14: P.C. Mahalanobis, "On the Generalized Distance in Statistics", Proceedings of the National Institute of Science of India, 12, pp. 49-55, 1936.
• 15: H. Mase. "Experiments on Automatic Web Page Categorization for IR system", technical report, Stanford University, 1998.
• 16: Kerttu Pollari-Malmi , Eljas Soisalon-Soininen , Tatu Ylönen, Concurrency Control in B-Trees with Batch Updates, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.975-984, December 1996 [doi>10.1109/69.553166]
• 17: M.F. Porter. "An Algorithm for Suffix Stripping", Program, 14(3), pp. 130-137, 1980.
• 18: M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz. "A Bayesian approach to filtering junk email", Proceedings of AAAi'98 Workshop on Learning for Text Categorization, 1998, Madison, Wisconsin.
• 19: G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 20: 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]
• 21: S. Scott, and S. Matwin. "Text Classification Using WordNet Hypernyms', Coting-ACL'98 Workshop: Usage of WordNet in Natural Language Processing Systems, pp. 45-51, August 1998.
• 22: Anthony Tomasic , Héctor García-Molina , Kurt Shoens, Incremental updates of inverted lists for text document retrieval, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States
• 23: S. A. Weiss, S. Kasif, and E. Brill. "Text Classification in USENET Newsgroups: A Progress Report", Proceedings of the AAAI Spring Symposium on Machine Learning in Information Access, pp. 125-127, 1996
• 24: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 25: Yiming Yang, Expert network: effective and efficient learning from human decisions in text categorization and retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.13-22, July 03-06, 1994, Dublin, Ireland
• 26: Yiming Yang, Noise reduction in a statistical approach to text categorization, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215367]
• 27: Yiming Yang , John Wilbur, Using corpus statistics to remove redundant words in text categorization, Journal of the American Society for Information Science, v.47 n.5, p.357-369, May 1996 [doi>10.1002/(SICI)1097-4571(199605)47:5<357::AID-ASI3>3.3.CO;2-0]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases
  H.3 INFORMATION STORAGE AND RETRIEVAL

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Publishing

General Terms:
Algorithms, Design, Documentation, Experimentation, Human Factors, Management, Measurement, Performance, Reliability, Theory