Алгоритмы машинного обучения для задачи анализа и рубрикации электронных документов

Авторы

  • М.И. Петровский Московский государственный университет имени М.В. Ломоносова
  • В.В. Глазкова Московский государственный университет имени М.В. Ломоносова

Ключевые слова:

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

Аннотация

Методы машинного обучения и интеллектуального анализа данных предназначены для решения задач анализа, классификации и выявления скрытых закономерностей в больших объемах разнородных сложно структурированных данных. К таким задачам относится прикладная задача анализа и рубрикации больших коллекций электронных текстовых и гипертекстовых документов. Для ее решения необходима разработка эффективных по точности и скорости алгоритмов для многотемной классификации (multi-label classification), т.е. классификации в условиях существенно перекрывающихся классов, когда любой объект классификации (документ) может принадлежать более чем одному классу (теме) одновременно, а также разработка формальных моделей представления гипертекстовых данных, эффективных по точности представления исходной информации и занимаемой при этом памяти. В настоящей статье предлагается новая модель представления данных, основанная на выделении частых эпизодов лексем (или N-грамм), и новый метод учeта гиперссылок, основанный на классификации с помощью N-граммного классификатора текста адресов гиперссылок и замене их в исходном тексте документа на специальные признаки. Кроме того, исследуется возможность использования подхода на основе декомпозиции «каждый против каждого» для решения задачи многотемной классификации. Предлагается новый метод многотемной классификации, основанный на подходе попарных сравнений с помощью набора бинарных классификаторов, где результирующие вероятности принадлежности документа темам (релевантности классов) вычисляются с помощью обобщенной модели Брэдли-Терри, а нерелевантные классы отсекаются с помощью пороговой функции, заданной в пространстве релевантностей классов. Все разработанные алгоритмы экспериментально проверены на эталонных тестовых наборах данных и показали лучшие результаты по сравнению с традиционными методами. Работа поддержана грантом РФФИ № 06-01-00691, грантом поддержки научных школ № 02.445.11.7427 и грантом Президента РФ МК-4264.2007.9.

Авторы

М.И. Петровский

В.В. Глазкова

Библиографические ссылки

  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.

Загрузки

Опубликован

29-10-2007

Как цитировать

Петровский М., Глазкова В. Алгоритмы машинного обучения для задачи анализа и рубрикации электронных документов // Вычислительные методы и программирование. 2007. 8. 57-69

Выпуск

Раздел

Раздел 2. Программирование