Machine learning algorithms for analysis and categorization of electronic text documents

Authors

  • M.I. Petrovskii Lomonosov Moscow State University
  • V.V. Glazkova Lomonosov Moscow State University

Keywords:

алгоритмы рубрикации текстовых и гипертекстовых документов, модели представления гипертекстовой информации, алгоритмы многотемной multi-label классификации, метод попарных сравнений

Abstract

The paper considers two main algorithmic problems arising in the field of analysis and categorization of electronic text documents. The first problem is the development of efficient formal representation models of hypertext data. Such models should incorporate both the text content of the documents and their hyperlink structure. The second problem is the development of efficient multi-label classification algorithms. The multi-label classification is a classification in the case of essentially overlapping classes when any classifying object (document) may belong to several classes (topics) simultaneously. A new text document representation model based on the extraction of frequent episodes of lexemes (or N-grams) and a new method for the hyperlinks structure analysis based on N-gram classification of a URL-hyperlink text are proposed. In this algorithm the lexemes are replaced in the initial document text by special tags. A possibility of applying the «one-versus-one» decomposition approach for solving the multi-label classification problem is also studied. A new multi-label classification method based on the paired comparison approach is proposed. In this method each pair of possibly overlapping classes is separated by two probabilistic binary classifiers that isolate the overlapping and non-overlapping areas. Then, the individual probabilities generated by the binary classifiers are combined together to estimate the final class probabilities that fit to the extended Bradley-Terry model with ties. In the proposed method, nonrelevant classes are cut off by a specially developed threshold function defined in the class-relevance vector space. Experimental performance evaluation using two well-known multi-label benchmark datasets demonstrated the higher-accuracy results of the proposed method as compared to existing approaches.

Author Biographies

M.I. Petrovskii

V.V. Glazkova

References

  1. Information Retrieval Tutorials: Document Indexing Tutorial: представление документов для информационного поиска (http://www.miislita.com/information-retrieval-tutorial/indexing.html).
  2. Vector Theory and Keyword Weights: выделение признаков из документов (http://www.miislita.com/information-retrieval-tutorial/indexing.html).
  3. Cavnar W.B., Trenkle J.M. Ngram-based text categorization // Proc. of SDAIR-94 (the 3rd Annual Symposium on Document Analysis and Information Retrieval). Las Vegas, 1994. 161-175.
  4. Chakrabarti S., Dom B.E., Indyk P. Enhanced hypertext categorization using hyperlinks // Proc. of the ACM Int. Conf. on Management of Data (SIGMOD). New York: ACM Press, 1998. 307-318.
  5. Pei J. Pattern-growth methods for frequent pattern mining. Ph.D. Thesis. Simon Fraser University. Vancouver, 2002.
  6. Elisseeff A., Weston J. A kernel method for multi-labelled classification // Proc. of the Conf. on Neural Information Processing Systems. Cambridge: MIT Press, 2002.
  7. Abe S., Inoue T. Fuzzy support vector machines for multiclass problems // Proc. of the European Symposium on Artificial Neural Networks. Bruges (Belgium), 2002. 113-118.
  8. Petrovskiy M. Probability estimation in error correcting output coding framework using game theory // Proc. of the 18th ACS Australian Joint Conf. on Artificial Intelligence. Lecture Notes in Artificial Intelligence. Vol. 3809. Berlin: Springer, 2005. 186-196.
  9. Huang T.-K., Weng R., Lin C.-J. A generalized Bradley-Terry model: from group competition to individual skill // Proc. of the Conf. on Neural Information Processing Systems. Cambridge: MIT Press, 2004. 85-115.
  10. Hunter D.R. MM-algorithms for generalized Bradley-Terry models // Annals of Statistics. 2004. 32, N 1. 384-406.
  11. Rao P.V., Kupper L.L. Ties in paired-comparison experiments: a generalization of the Bradley-Terry model // Amer. Statist. Assoc. 1967. 62. 194-204.
  12. Platt J. Probabilistic outputs for support vector machines and comparison to regularized likelihood methods // Advances in Large Margin Classifiers. Cambridge: MIT Press, 1999. 61-74.
  13. Zheng W., Zhao L., Zou C. A modified algorithm for generalized discriminant analysis // Neural Computation. 2004. 16, N 6. 1283-1297.
  14. Lewis D.D., Yang Y., Rose T.G., Li F. RCV1: A new benchmark collection for text categorization research // Machine Learning. 2004. 5. 361-397.
  15. Bank Research Dataset: Набор данных BankResearch (http://lib.stat.cmu.edu/datasets/bankresearch.zip).
  16. Zhang M.-L., Zhou Z.-H. A k-nearest neighbor based algorithm for multi-label classification // Proc. of the First IEEE Int. Conf. on Granular Computing. Beijing (China), 2005. 718-721.
  17. Everitt B.S. The analysis of contingency tables. London: Chapman and Hall, 1977.
  18. Chang C.-C., Lin C.-J. LIBSVM: a library for support vector machines (http://www.csie.ntu.edu.tw/ cjlin/libsvm).
  19. Crammer C., Singer Y. A family of additive online algorithms for category ranking // Machine Learning Research. 2003. 3. 1025-1058.
  20. Schapire R.E., Singer Y. BoosTexter: a boosting-based system for text categorization // Machine Learning. 2000. 39. 135-168.
  21. Boutell M.R., Luo J., Shen X., Brown C.M. Learning multi-label scene classification // Pattern Recognition. 2004. 37. 1757-1771.

Published

29-10-2007

How to Cite

Петровский М.И., Глазкова В.В. Machine Learning Algorithms for Analysis and Categorization of Electronic Text Documents // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2007. 8. 57-69

Issue

Section

Section 2. Programming