Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Графовая модификация метрических алгоритмов классификации

# 11, ноябрь 2016
DOI: 10.7463/1116.0850028
Файл статьи: SE-BMSTU...o141.pdf (516.14Кб)
авторы: Самарев Р. С.1, Васнецов А. Г.1,*

УДК 004.852

1 МГТУ им. Н.Э. Баумана, Москва, Россия

Задачи разметки и классификации последовательностей являются обобщением классической задачи классификации на случай последовательностей и заключаются в следующем: задача сопоставления метки каждому элементу последовательности (сильная задача классификации), и сопоставление класса всей последовательности целиком. Существующие методы решения этой задачи: скрытые марковские модели, Conditional Random Fields(CRF), марковские SVM - основываются на статистическом моделировании признаков элементов и в некоторых случаях могут оказаться не вполне эффективными. Один из таких случаев - невозможность описать элемент последовательности в виде набора признаков. В этом случае обычно применяют метрические алгоритмы классификации, оперирующие расстояниями между элементами, но не применимые напрямую к последовательностям данных.  Поэтому необходимо найти метод их обобщения для работы с последовательностями.
В работе предложен метод обобщения метрических алгоритмов классификации. В результате применения его к алгоритму k-ближайших соседей (kNN), получен новый метрический алгоритм классификации, применимый к последовательностям данных - SkNN (Structured kNN). Эффективность полученного алгоритма была экспериментально проверена на эталонных наборах данных CoNLL 2000 и UJI Pen Characters, в которых решались, соответственно, задачи разметки и классификации последовательностей. Эксперимент показал, что точность предложенного алгоритма превосходит точность других алгоритмов, широко используемых для решения аналогичной задачи, в частности, алгоритма CRF.
Полученный метод обобщения может быть применен и к другим метрическим алгоритмам классификации, результат работы которых может быть использован как самостоятельное решение задачи, так и служить исходными данными для композиции алгоритмов машинного обучения.
Сравнение алгоритма с существующими показывает, что при полученной точности алгоритма целесообразно продолжать работу в направлении поиска эффективной реализации и, например, реализации данного алгоритма для работы на вычислительных кластерах, что позволит существенно увеличить скорость его работы.

Список литературы
  1. Kocsor A., Kertesz-Farkas A., Kajan L., Pongor S. Application of compression-based distance measures to protein sequence classification: a methodological study // Bioinformatics. 2006. Vol. 22, no. 4.  P. 407-412.
  2. Sonego P., Kocsor A., Pongor S. ROC analysis: applications to the classification of biological sequences and 3D structures // Briefings in bioinformatics. 2008. Vol. 9, no. 3. P. 198-209.
  3. Feily M., Shahrestani A., Ramadass S. A survey of botnet and botnet detection //  3rd International Conference on Emerging Security Information, Systems and Technologies, 2009. IEEE, 2009. P. 268-273.
  4. Zhou G. D., Su J. Named entity recognition using an HMM-based chunk tagger // Proceedings of the 40th Annual Meeting on Association for Computational Linguistics. Association for Computational Linguistics, 2002. P. 473-480.
  5. Lafferty J., McCallum A., Pereira F. Conditional random fields: Probabilistic models for segmenting and labeling sequence data // Proceedings of the eighteenth international conference on machine learning, ICML2001. San Francisco: Morgan Kaufmann Publ., 2001. P. 282-289.
  6. Nguyen N., Guo Y. Comparisons of sequence labeling algorithms and extensions // Proceedings of the 24th international conference on Machine learning.  ACM, 2007.  P. 681-688.
  7. Левенштейн В.И. Двоичные коды с исправлением выпадений и вставок символа 1 // Проблемы передачи информации. 1965. Т. 1, №1. С. 2-25.
  8. Altun Y., Tsochantaridis I., Hofmann Th. Hidden markov support vector machines // Proceedings of the 20th International Conference on Machine Learning (ICML-2003), Washington DC, 2003. AAAI Press, 2003. Vol. 3. P. 3--10.
  9. Liu F., Vanschoenwinkel B., Chen Y., Manderick B. A modified value difference metric kernel for context-dependent classification tasks // International Conference on Machine Learning and Cybernetics, 2006. IEEE, 2006. P. 3432-3437.
  10. Sutton C., McCallum A. An introduction to conditional random fields for relational learning // Getoor L, Taskar B., eds. Introduction to statistical relational learning. Cambridge: MIT Press, 2006. Vol. 2. P. 93-128.
  11. Mikolov T., Sutskever I., Chen K., Corrado G.S., Dean J. Distributed representations of words and phrases and their compositionality // Advances in neural information processing systems (NIPS 2013). 2013. P. 3111-3119.
  12. Asuncion A., Newman D. J. UCI machine learning repository. 2007. Режим доступа:http://www.ics.uci.edu/~mlearn/MLRepository.html (дата обращения 21.11.2016)
  13. Llorens D. et al. The UJIpenchars Database: a Pen-Based Database of Isolated Handwritten Characters //LREC. – 2008.
  14. Tjong Kim Sang E. F., Buchholz S. Introduction to the CoNLL-2000 shared task: Chunking //Proceedings of the 2nd workshop on Learning language in logic and the 4th conference on Computational natural language learning - Volume 7. – Association for Computational Linguistics, 2000. – С. 127-132.
  15. Ramos-Garijo R. et al. An input panel and recognition engine for on-line handwritten text recognition //Frontiers in Artificial Intelligence and Applications. – 2007. – Т. 163. – С. 223.
  16. Acedański S. A morphosyntactic Brill tagger for inflectional languages //International Conference on Natural Language Processing. – Springer Berlin Heidelberg, 2010. – С. 3-14.
  17. Paul D. B., Baker J. M. The design for the Wall Street Journal-based CSR corpus //Proceedings of the workshop on Speech and Natural Language. – Association for Computational Linguistics, 1992. – С. 357-362.
  18. Daelemans W., Van den Bosch A. Memory-based language processing. – Cambridge University Press, 2005.
  19. Kent J. T. Information gain and a general measure of correlation //Biometrika. – 1983. – Т. 70. – №. 1. – С. 163-173.
  20. Mori T. Information gain ratio as term weight: the case of summarization of ir results //Proceedings of the 19th international conference on Computational linguistics-Volume 1. – Association for Computational Linguistics, 2002. – С. 1-7.
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2017 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)