Метод обучения деревьев решений с нелинейными разделителями
- Авторы: Девяткин Д.А.1, Григорьев О.Г.1
-
Учреждения:
- Федеральный исследовательский центр «Информатика и управление» РАН
- Выпуск: № 3 (2022)
- Страницы: 96-105
- Раздел: Анализ текстовой и графической информации
- URL: https://journal-vniispk.ru/2071-8594/article/view/270475
- DOI: https://doi.org/10.14357/20718594220308
- ID: 270475
Цитировать
Полный текст
Аннотация
Деревья решений с одномерными разделителями, применяемые при обработке разреженных данных большой размерности, характеризуются низкой вычислительной эффективностью. Деревья решений с многомерными разделителями обладают большей выразительной способностью при классификации данных, но переобучаются на небольших выборках. В статье предложен метод обучения деревьев с многомерными нелинейными разделителями, который повышает точность классификации на наборах изображений и текстов. Это достигается за счёт совместной оптимизации расстояния от объектов обучающей выборки до разделяющей поверхности и критерия неоднородности данных при построении каждого узла дерева. Эффективность метода подтверждается результатами тестов.
Об авторах
Дмитрий Алексеевич Девяткин
Федеральный исследовательский центр «Информатика и управление» РАН
Автор, ответственный за переписку.
Email: devyatkin@isa.ru
научный сотрудник
Россия, МоскваОлег Георгиевич Григорьев
Федеральный исследовательский центр «Информатика и управление» РАН
Email: oleggpolikvart@yandex.ru
доктор технических наук, главный научный сотрудник
Россия, МоскваСписок литературы
- Breiman L. et al. Classification and regression trees. Routledge. 2017.
- 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.
- Breiman L. Random forests // Machine learning. 2001. Т. 45. №. 1. P. 5-32.
- Golea M. et al. Generalization in decision trees and DNF: Does size matter? // Advances in Neural Information Processing Systems. 1997. Т. 10.
- Vapnik V. N. An overview of statistical learning theory // IEEE transactions on neural networks. 1999. Т. 10. №. 5. P. 988-999.
- Breiman L. Some properties of splitting criteria // Machine learning. 1996. Т. 24. №. 1. P. 41-47.
- Liu W., Tsang I. W. Sparse perceptron decision tree for millions of dimensions // Thirtieth AAAI Conference on Artificial Intelligence. 2016.
- Liu W., Tsang I. W. Making decision trees feasible in ultrahigh feature and label dimensions // Journal of Machine Learning Research. 2017.
- 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.
- 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.
- Tibshirani R., Hastie T. Margin Trees for Highdimensional Classification // Journal of Machine Learning Research. 2007. Т. 8. №. 3.
- Manwani N., Sastry P. S. Geometric decision tree // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 2011. Т. 42. №. 1. P. 181-192.
- Hofmann T., Schölkopf B., Smola A. J. Kernel methods in machine learning //The annals of statistics. 2008. Т. 36. №. 3. P. 1171-1220.
- Norouzi M. et al. Co2 forest: Improved random forest by continuous optimization of oblique splits //arXiv preprint arXiv:1506.06155. 2015.
- Tsochantaridis I. et al. Large margin methods for structured and interdependent output variables //Journal of machine learning research. 2005. Т. 6. №. 9.
- Yuille A. L., Rangarajan A. The concave-convex procedure // Neural computation. 2003. Т. 15. №. 4. P. 915-936.
- DeSalvo G., Mohri M. Random composite forests // Proceedings of the AAAI Conference on Artificial Intelligence. 2016. Т. 30. №. 1.
- 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.
- Irsoy O., Alpaydin E. Autoencoder trees // Asian conference on machine learning. PMLR. 2016. P. 378-390.
- 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.
- Hecht-Nielsen R. Theory of the backpropagation neural network // Neural networks for perception. Academic Press. 1992. P. 65-93.
- 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.
- 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.
- Kumar M. A., Gopal M. A hybrid SVM based decision tree // Pattern Recognition. 2010. Т. 43. №. 12. P. 3977-3987.
- Krizhevsky A. Learning Multiple Layers of Features from Tiny Images // Master's thesis, University of Tront. 2009.
- Набор данных «Youtube channels dataset». URL: http://keen.isa.ru/youtube (дата обращения: 14.07.2022).
- Blake C. UCI repository of machine learning databases. URL: http://www.ics.uci.edu/~mlearn/MLRepository.html (дата обращения: 14.07.2022).
Дополнительные файлы
