Д.А. Девяткин1

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

Постановка проблемы. Случайные леса деревьев решений с одномерными разделителями широко используются для обработки данных и текстов, однако они ограниченно применимы для анализа многомерных разреженных данных. Вместе с тем обработка подобных выборок имеет большую практическую значимость. Например, определение вегетационных индексов почв на основе изображений, полученных средствами дистанционного зондирования Земли, позволяет повысить эффективность управления сельскохозяйственными предприятиями. Одним из подходов к решению этой проблемы является построение лесов деревьев решений с многомерными линейными или нелинейными разделителями. Время обучения таких ансамблей на данных большого объема существенно превосходит время построения лесов деревьев решений с одномерными разделителями. Кроме того, для построения различных видов разделителей требуются разные вычислительные ресурсы: если линейный разделитель может быть построен с использованием центральных процессоров, то для обучения нелинейных разделителей необходимо задействование графических ускорителей.

Цель. Разработать распределенную архитектуру системы построения случайных лесов деревьев решений, в которой отдельные разделители обучаются параллельно, что позволяет снизить простой аппаратных ресурсов и назначать задания на обучение различным видам вычислительных узлов в зависимости от типа разделителя, а также динамически масштабировать состав вычислительных узлов системы в зависимости от нагрузки.

Результаты. Экспериментально исследована система обучения деревьев решений, основанная на предложенной архитектуре. Показано, что она позволяет значительно снизить машинное время, необходимое для обучения лесов на массивах данных большой размерности.

Практическая значимость. Представленная архитектура может использоваться в качестве основы при создании прикладных систем анализа данных и изображений большой размерности, предназначенных для применения в различных отраслях экономики: сельском хозяйстве, промышленности, транспорте.

Девяткин Д.А. Система распределенного построения случайных лесов деревьев решений с линейными и нелинейными разделителями // Системы высокой доступности. 2022. Т. 18. № 3. С. 59−68. DOI: https://doi.org/10.18127/j20729472-202203-05

1. Breiman L. Classification and regression trees. Routledge. 2017. 368 p.
2. Breiman L. Random forests // Machine learning. 2001. V. 45. № 1. P. 5−32.
3. Khan Z., Rahimi-Eichi V., Haefele S., Garnett T., Miklavcic S.J. Estimation of vegetation indices for high-throughput phenotyping of wheat using aerial imaging // Plant methods. 2018. V. 14. № 1. P. 1−11.
4. Devyatkin D.A., Grigoriev O.G. Random Kernel Forests // IEEE Access. 2022. V. 10. P. 77962−77979.
5. Friedman J.H. Stochastic gradient boosting // Computational statistics & data analysis. 2002. V. 38. № 4. P. 367−378.
6. Kraska T., Talwalkar A., Duchi J.C., Griffith R., Franklin M.J., Jordan M.I. MLbase: A Distributed Machine-learning System // CIDR. 2013. V. 1. P. 2−1.
7. Zaharia M., Chowdhury M., Das T., Dave A., Ma J., McCauley M., Franklin M., Shenker S., Stoica I. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing // 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). 2012. P. 15−28.
8. Hindman B., Konwinski A., Zaharia M., Ghodsi A., Joseph A.D., Katz R., Stoica I. Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center // 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11). 2011.
9. Malewicz G., Austern M.H., Bik A.J., Dehnert J.C., Horn I., Leiser N., Czajkowski G. Pregel: a system for large-scale graph processing //Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 2010. P. 135−146.
10. Low Y., Gonzalez J., Kyrola A., Bickson D., Guestrin C., Hellerstein J.M. Distributed Graphlab: A framework for machine learning in the cloud //arXiv preprint arXiv:1204.6078. 2012.
11. Low Y., Gonzalez J.E., Kyrola A., Bickson D., Guestrin C.E., Hellerstein J. Graphlab: A new framework for parallel machine learning //arXiv preprint arXiv:1408.2041. 2014.
12. Gillick D., Faria A., DeNero J. Mapreduce: Distributed computing for machine learning // Berkley. December 2006. V. 18.
13. Panda B., Herbach J.S., Basu S., Bayardo R.J. PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce // Proceeding VLDB Endow. 2009. V. 2. P. 1426–1437.
14. Murdopo A. Distributed decision tree learning for mining big data streams // Master of Science Thesis, European Master in Distributed Computing. 2013. P. 75.
15. Ye J., Chow J.-H., Chen J., Zheng Z. Stochastic gradient boosted distributed decision trees // Proceedings of the 18th ACM conference on Information and knowledge management. 2009. P. 2061−2064.
16. Li B., Yu Q., Peng L. Ensemble of fast learning stochastic gradient boosting // Communications in Statistics-Simulation and Computation. 2022. V. 51. № 1. P. 40−52.
17. Chen T., He T., Benesty M., Khotilovich V., Tang Y., Cho H., Chen K. Xgboost: extreme gradient boosting // R package version 0.4‑2. 2015. V. 1. № 4. P. 1−4.
18. Dorogush A.V., Ershov V., Gulin A. CatBoost: gradient boosting with categorical features support // arXiv preprint arXiv:1810.11363. 2018.
19. Дружков П.Н., Половинкин А.Н. Реализация параллельного алгоритма обучения в методе градиентного бустинга деревьев решений для систем с распределенной памятью // Параллельные вычислительные технологии 2012 (ПАВТ'2012). Новосибирск, 26−30 марта 2012. Новосибирск. 2012. С. 459−465.
20. Zhang H. et al. Real-time distributed-random-forest-based network intrusion detection system using Apache spark // IEEE 37th international performance computing and communications conference (IPCCC). 2018. P. 1−7.
21. Murphy P.M. and Aha D.W. UCI Repository of machine learning databases // Dept. Inf. Comput. Sci., Univ. California, Irvine, CA, USA, Tech. Rep., 1991. Режим доступа: Jul. 24, 2022. URL: https://archive.ics.uci.edu/ml/about.html.
22. Krizhevsky A. Learning multiple layers of features from tiny images // M.S. thesis, Dept. Comput. Sci., Univ. Toronto, Toronto, ON. Canada. 2009.