Метод обучения деревьев решений с нелинейными разделителями

Обложка

Цитировать

Полный текст

Аннотация

Деревья решений с одномерными разделителями, применяемые при обработке разреженных данных большой размерности, характеризуются низкой вычислительной эффективностью. Деревья решений с многомерными разделителями обладают большей выразительной способностью при классификации данных, но переобучаются на небольших выборках. В статье предложен метод обучения деревьев с многомерными нелинейными разделителями, который повышает точность классификации на наборах изображений и текстов. Это достигается за счёт совместной оптимизации расстояния от объектов обучающей выборки до разделяющей поверхности и критерия неоднородности данных при построении каждого узла дерева. Эффективность метода подтверждается результатами тестов.

Об авторах

Дмитрий Алексеевич Девяткин

Федеральный исследовательский центр «Информатика и управление» РАН

Автор, ответственный за переписку.
Email: devyatkin@isa.ru

научный сотрудник

Россия, Москва

Олег Георгиевич Григорьев

Федеральный исследовательский центр «Информатика и управление» РАН

Email: oleggpolikvart@yandex.ru

доктор технических наук, главный научный сотрудник

Россия, Москва

Список литературы

  1. Breiman L. et al. Classification and regression trees. Routledge. 2017.
  2. Chen T., Guestrin C. Xgboost: A scalable tree boosting system // Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. 2016. P. 785-794.
  3. Breiman L. Random forests // Machine learning. 2001. Т. 45. №. 1. P. 5-32.
  4. Golea M. et al. Generalization in decision trees and DNF: Does size matter? // Advances in Neural Information Processing Systems. 1997. Т. 10.
  5. Vapnik V. N. An overview of statistical learning theory // IEEE transactions on neural networks. 1999. Т. 10. №. 5. P. 988-999.
  6. Breiman L. Some properties of splitting criteria // Machine learning. 1996. Т. 24. №. 1. P. 41-47.
  7. Liu W., Tsang I. W. Sparse perceptron decision tree for millions of dimensions // Thirtieth AAAI Conference on Artificial Intelligence. 2016.
  8. Liu W., Tsang I. W. Making decision trees feasible in ultrahigh feature and label dimensions // Journal of Machine Learning Research. 2017.
  9. Bennett K. P., Blue J. A. A support vector machine approach to decision trees // 1998 IEEE International Joint Conference on Neural Networks Proceedings. IEEE World Congress on Computational Intelligence (Cat. No. 98CH36227). IEEE. 1998. Т. 3. P. 2396-2401.
  10. Menze B. H. et al. On oblique random forests // Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, Heidelberg. 2011. P. 453-469.
  11. Tibshirani R., Hastie T. Margin Trees for Highdimensional Classification // Journal of Machine Learning Research. 2007. Т. 8. №. 3.
  12. Manwani N., Sastry P. S. Geometric decision tree // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 2011. Т. 42. №. 1. P. 181-192.
  13. Hofmann T., Schölkopf B., Smola A. J. Kernel methods in machine learning //The annals of statistics. 2008. Т. 36. №. 3. P. 1171-1220.
  14. Norouzi M. et al. Co2 forest: Improved random forest by continuous optimization of oblique splits //arXiv preprint arXiv:1506.06155. 2015.
  15. Tsochantaridis I. et al. Large margin methods for structured and interdependent output variables //Journal of machine learning research. 2005. Т. 6. №. 9.
  16. Yuille A. L., Rangarajan A. The concave-convex procedure // Neural computation. 2003. Т. 15. №. 4. P. 915-936.
  17. DeSalvo G., Mohri M. Random composite forests // Proceedings of the AAAI Conference on Artificial Intelligence. 2016. Т. 30. №. 1.
  18. Hehn T. M., Kooij J. F. P., Hamprecht F. A. End-to-end learning of decision trees and forests // International Journal of Computer Vision. 2020. Т. 128. №. 4. P. 997-1011.
  19. Irsoy O., Alpaydin E. Autoencoder trees // Asian conference on machine learning. PMLR. 2016. P. 378-390.
  20. Chai Z., Zhao C. Multiclass oblique random forests with dual-incremental learning capacity // IEEE transactions on neural networks and learning systems. 2020. Т. 31. №. 12. P. 5192-5203.
  21. Hecht-Nielsen R. Theory of the backpropagation neural network // Neural networks for perception. Academic Press. 1992. P. 65-93.
  22. Yang B. B., Shen S. Q., Gao W. Weighted oblique decision trees // Proceedings of the AAAI Conference on Artificial Intelligence. 2019. Т. 33. №. 01. P. 5621-5627.
  23. Carreira-Perpinán M. A., Tavallali P. Alternating optimization of decision trees, with application to learning sparse oblique trees // Advances in neural information processing systems. 2018. Т. 31.
  24. Kumar M. A., Gopal M. A hybrid SVM based decision tree // Pattern Recognition. 2010. Т. 43. №. 12. P. 3977-3987.
  25. Krizhevsky A. Learning Multiple Layers of Features from Tiny Images // Master's thesis, University of Tront. 2009.
  26. Набор данных «Youtube channels dataset». URL: http://keen.isa.ru/youtube (дата обращения: 14.07.2022).
  27. Blake C. UCI repository of machine learning databases. URL: http://www.ics.uci.edu/~mlearn/MLRepository.html (дата обращения: 14.07.2022).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).