Multi-evidence, multi-criteria, lazy associative document classification

ABSTRACT

We present a novel approach for classifying documents that combines different pieces of evidence (e.g., textual features of documents, links, and citations) transparently, through a data mining technique which generates rules associating these pieces of evidence to predefined classes. These rules can contain any number and mixture of the available evidence and are associated with several quality criteria which can be used in conjunction to choose the "best" rule to be applied at classification time. Our method is able to perform evidence enhancement by link forwarding/backwarding (i.e., navigating among documents related through citation), so that new pieces of link-based evidence are derived when necessary. Furthermore, instead of inducing a single model (or rule set) that is good on average for all predictions, the proposed approach employs a lazy method which delays the inductive process until a document is given for classification, therefore taking advantage of better qualitative evidence coming from the document. We conducted a systematic evaluation of the proposed approach using documents from the ACM Digital Library and from a Brazilian Web directory. Our approach was able to outperform in both collections all classifiers based on the best available evidence in isolation as well as state-of-the-art multi-evidence classifiers. We also evaluated our approach using the standard WebKB collection, where our approach showed gains of 1% in accuracy, being 25 times faster. Further, our approach is extremely efficient in terms of computational performance, showing gains of more than one order of magnitude when compared against other multi-evidence classifiers.

REFERENCES

• 1: R. Amsler. Application of citation-based automatic classification. Technical report, The University of Texas at Austin, Linguistics Research Center, 1972.
• 2: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and regression trees. Wadsworth Intl., 1984.
• 3: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 4: Pável Calado , Marco Cristo , Edleno Moura , Nivio Ziviani , Berthier Ribeiro-Neto , Marcos André Gonçalves, Combining link-based and content-based methods for web document classification, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956938]
• 5: D. Cohn and T. Hofmann. The missing link - A probabilistic model of document content and hypertext connectivity. In Advances in Neural Inf. Processing Systems, pages 430--436. MIT Press, 2001.
• 6: S. Dasgupta, M. Littman, and D. McAllester. PAC generalization bounds for cotraining. In Proc. of Neural Inf. Processing Systems, 2001.
• 7: M. Fisher and R. Everson. When are links useful? Experiments in text classification. In Proc. of ECIR03, pages 41--56, Pisa, Italy, April 2003.
• 8: J. Friedman, R. Kohavi, and Y. Yun. Lazy decision trees. In Proc. of the Nat. Conf. on Artificial Intelligence, pages 717--724, Menlo Park, 1996.
• 9: Johannes Fürnkranz, Exploiting Structural Information for Text Classification on the WWW, Proceedings of the Third International Symposium on Advances in Intelligent Data Analysis, p.487-498, August 01, 1997
• 10: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 11: Thorsten Joachims , Nello Cristianini , John Shawe-Taylor, Composite Kernels for Hypertext Categorisation, Proceedings of the Eighteenth International Conference on Machine Learning, p.250-257, June 28-July 01, 2001
• 12: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 13: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In Knowledge Discovery and Data Mining, pages 80--86, 1998.
• 14: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 15: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 16: Altigran S. da Silva , Eveline A. Veloso , Paulo B. Golghe , Berthier Ribeiro-Neto , Alberto H. F. Laender , Nivio Ziviani, CoBWeb A Crawler for the Brazilian Web, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.184, September 21-24, 1999
• 17: H. Small. Co-citation in the scientific literature: A new measure of relationship between two documents. JASIS, 24(4):265--269, 1973.
• 18: Aixin Sun , Ee-Peng Lim , Wee-Keong Ng, Web classification using support vector machine, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/584931.584952]
• 19: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Selecting the right interestingness measure for association patterns, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775053]
• 20: Loren Terveen , Will Hill , Brian Amento, Constructing, organizing, and visualizing collections of topically related Web resources, ACM Transactions on Computer-Human Interaction (TOCHI), v.6 n.1, p.67-94, March 1999 [doi>10.1145/310641.310644]
• 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
• 22: Yiming Yang , Seán Slattery , Rayid Ghani, A Study of Approaches to Hypertext Categorization, Journal of Intelligent Information Systems, v.18 n.2-3, p.219-241, March-May 2002 [doi>10.1023/A:1013685612819]
• 23: X. Yin and J. Han. CPAR: Classification based on predictive association rules. In Proc. of the SDM03. SIAM, 2003.
• 24: Mohammed J. Zaki , Charu C. Aggarwal, XRules: an effective structural classifier for XML data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956787]
• 25: Baoping Zhang , Yuxin Chen , Weiguo Fan , Edward A. Fox , Marcos Gonçalves , Marco Cristo , Pável Calado, Intelligent GP fusion from multiple sources for text classification, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099688]

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.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Experimentation

Keywords:
classification, data mining, lazy algorithms