Strategies for minimising errors in hierarchical web categorisation

ABSTRACT

On the Web, browsing and searching categories is a popular method of finding documents. Two well-known category-based search systems are the Yahoo!~and DMOZ hierarchies, which are maintained by experts who assign documents to categories. However, manual categorisation by experts is costly, subjective, and not scalable with the increasing volumes of data that must be processed. Several methods have been investigated for effective automatic text categorisation. These include selection of categorisation methods, selection of pre-categorised training samples, use of hierachies, and selection of document fragments or features. In this paper, we further investigate categorisation into Web hierarchies and the role of hierarchical information in improving categorisation effectiveness. We introduce new strategies to reduce errors in hierarchical categorisation. In particular, we propose novel techniques that shift the assignment into higher level categories when lower level assignment is uncertain. Our results show that absolute error rates can be reduced by over 2%.

REFERENCES

• 1: Chidanand Apté , Fred Damerau , Sholom M. Weiss, Automated learning of decision rules for text categorization, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.233-251, July 1994 [doi>10.1145/183422.183423]
• 2: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 3: S. D'Alessio, K. Murray, R. Schiaffino, and A. Kershenbaum. The effect of using hierarchical classifiers in text categorization. In Proceeding of RIAO-00, 6th International Conference "Recherche d'Information Assistee par Ordinateur", pages 302--313, Paris, FR, 2000.
• 4: S. D'Alessio, K. Murray, R. Schiaffino, and A. Kershenbaum. Category levels in hierarchical text categorization. In Proc. of EMNLP-98, 3rd Conference on Empirical Methods in Natural Language Processing, Granada, Spain, 1998. Association for Computational Linguistics, Morristown.
• 5: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 6: Philip J. Hayes , Steven P. Weinstein, CONSTRUE/TIS: A System for Content-Based Indexing of a Database of News Stories, Proceedings of the The Second Conference on Innovative Applications of Artificial Intelligence, p.49-64, May 01-03, 1990
• 7: Thorsten Joachims, A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.143-151, July 08-12, 1997
• 8: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 9: Leah S. Larkey , W. Bruce Croft, Combining classifiers in text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.289-297, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243276]
• 10: 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]
• 11: D. Mladenic and M. Grobelnik. Feature selection for classification based on text hierarchy. In Working notes of Learning from Text and the Web, Conference on Automated Learning and Discovery CONALD-98, Pittsburg, USA, 1998.
• 12: J.J. Rocchio. Relevance feedback in information retrieval. In The Smart Retrieval System --- Experiments in Automatic Document Processing, pages 313--323. Prentice-Hall, Englewood, Cliffs, New Jersey, 1971.
• 13: Miguel E. Ruiz , Padmini Srinivasan, Hierarchical neural networks for text categorization (poster abstract), Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.281-282, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312700]
• 14: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 15: V. Shanks and H.E. Williams. Fast categorisation of large document collections. In 8th International Symposium on String Processing and Information Retrieval (SPIRE2001), pages 194--204, San Rafael, Chile, 2001.
• 16: A.S. Weigend, E.D. Wiener, and J.O. Pedersen. Exploiting hierarchy in text categorization.
• 17: W. Wibowo and H.E. Williams. On using hierarchies for document classification. In Proc. Australian Document Computing Conference, pages 31--37, Coffs Harbour, Australia, 1999.
• 18: H.E. Williams and J. Zobel. Searchable words on the web. International Journal of Digital Libraries. To appear.
• 19: Yiming Yang, An Evaluation of Statistical Approaches to Text Categorization, Information Retrieval, v.1 n.1-2, p.69-90, 1999 [doi>10.1023/A:1009982220290]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
categorisation, error reduction, hierarchical categorisation