Clustering documents in a web directory

ABSTRACT

Hierarchical categorization of documents is a task receiving growing interest due to the widespread proliferation of topic hierarchies for text documents. The worst problem of hierarchical supervised classifiers is their high demand in terms of labeled examples, whose amount is related to the number of topics in the taxonomy. Hence, bootstrapping a huge hierarchy with a proper set of labeled examples is a critical issue. In this paper, we propose some solutions for the bootstrapping problem, implicitly or explicitly using a taxonomy definition: a baseline approach where documents are classified according to class labels, and two clustering approaches, where training is constrained by the a-priori knowledge of the taxonomy structure, both at terminological and topological level. In particular, we propose the TaxSOM model, that clusters a set of documents in a predefined hierarchy of classes, directly exploiting the knowledge of both their topological organization and their lexical description. Experimental evaluation was performed on a set of taxonomies taken from the Google Web directory.

REFERENCES

• 1: Charu C. Aggarwal , Stephen C. Gates , Philip S. Yu, On the merits of building categorization systems by supervised clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.352-356, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312279]
• 2: Aixin Sun , Ee-Peng Lim, Hierarchical Text Classification and Evaluation, Proceedings of the 2001 IEEE International Conference on Data Mining, p.521-528, November 29-December 02, 2001
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: M. Bonifacio, P. Bouquet, and P. Traverso. Enabling distributed knowledge management. managerial and technological implications. Informatik/Informatique, 3(1), 2002.
• 5: M. Ceci and D. Malerba. Hierarchical classification of html documents with webclassii. In Proc. of the 25th European Conf. on Information Retrieval (ECIR'03), volume 2633 of Lecture Notes in Computer Science, pages 57--72, 2003.
• 6: Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Using Taxonomy, Discriminants, and Signatures for Navigating in Text Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.446-455, August 25-29, 1997
• 7: Chun Hung Cheng , Jian Tang , Ada Wai-Chee Fu , Irwin King, Hierarchical Classification of Documents with Error Control, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.433-443, April 16-18, 2001
• 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: Anhai Doan , Pedro Domingos , Alon Halevy, Learning to Match the Schemas of Data Sources: A Multistrategy Approach, Machine Learning, v.50 n.3, p.279-301, March 2003 [doi>10.1023/A:1021765902788 ]
• 10: 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]
• 11: Sally A. Goldman , Yan Zhou, Enhancing Supervised Learning with Unlabeled Data, Proceedings of the Seventeenth International Conference on Machine Learning, p.327-334, June 29-July 02, 2000
• 12: B. Jeon and D. Landgrebe. Partially supervised classification using weighted unsupervised clustering. IEEE Trans. on Geoscience and Remote Sensing, 37(2):1073--1079, 1999.
• 13: Michael I. Jordan , Robert A. Jacobs, Hierarchical mixtures of experts and the EM algorithm, Neural Computation, v.6 n.2, p.181-214, March 1994 [doi>10.1162/neco.1994.6.2.181]
• 14: Teuvo Kohonen, Self-organizing maps, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 15: T. Kohonen, S. Kaski, K. Lagus, J. Salojarvi, J. Honkela, V. Paatero, and A. Saarela. Self organization of a massive document collection. IEEE Trans. on Neural Networks, 11(3):574--585, 2000.
• 16: Bing Liu , Wee Sun Lee , Philip S. Yu , Xiaoli Li, Partially Supervised Classification of Text Documents, Proceedings of the Nineteenth International Conference on Machine Learning, p.387-394, July 08-12, 2002
• 17: A. McCallum and K. Nigam. Text classification by bootstrapping with keywords. In ACL99 - Workshop for Unsupervised Learning in Natural Language Processing, 1999.
• 18: Kamal Nigam , Andrew McCallum , Sebastian Thrun , Tom Mitchell, Learning to classify text from labeled and unlabeled documents, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.792-799, July 1998, Madison, Wisconsin, United States
• 19: Miguel E. Ruiz , Padmini Srinivasan, Hierarchical Text Categorization Using Neural Networks, Information Retrieval, v.5 n.1, p.87-118, January 2002 [doi>10.1023/A:1012782908347 ]
• 20: Ke Wang , Senqiang Zhou , Shiang Chen Liew, Building Hierarchical Classifiers Using Class Proximity, Proceedings of the 25th International Conference on Very Large Data Bases, p.363-374, September 07-10, 1999
• 21: 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

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Experimentation

Keywords:
TaxSOM, constrained clustering, digital libraries, k-means, knowledge management, taxonomy bootstrapping process, text categorization, web directories