sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-234Research ArticleСтатьиИтеративный метод построения деревьев регрессииThe iterative method of regression trees inductionМельниковГ. А.MelnikovG. A.grme189@gmail.comГубаревВ. В.GubarevV. V.gubarev@vt.cs.nstu.ruНовосибирский государственный технический университетRussian Federation201624102022045967Copyright © Мельников Г.А., Губарев В.В., 20222022Мельников Г.А., Губарев В.В.Melnikov G.A., Gubarev V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/234

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

The majority of modem algorithms for regression tree induction are greedy. They are all based on a recursive division of the data. We propose to revise this «tradition». The paper describes the novel iterative method and algorithm with pre-pruning for regression tree induction. The results of the experiments based on publicly available data sets show that the proposed algorithm is comparable with recursive algorithms for regression tree induction in accuracy. However, it results in less complex solutions and has a much lower time complexity.

машинное обучениенелинейная регрессиякусочно-заданная линейная регрессиядеревья моделейдеревья регрессииупрощение деревьев регрессииmachine learningnonlinear regressionpiecewise linear regressionmodels treesregression treesregression trees pruningReferencesClassification and regression trees / L. Breiman, J.H. Friedman, R.A. Olshen, C.J. Stone. Belmont: Wadsworth International Group, 1984. 259 p.Classification and regression trees / L. Breiman, J.H. Friedman, R.A. Olshen, C.J. Stone. Belmont: Wadsworth International Group, 1984. 259 p.Hyafil L., Rivest R L. Constructing optimal binary decision trees is NP-complete // Information Processing Letters. 1976. V. 5, № 1. P. 15-17.Hyafil L., Rivest R L. Constructing optimal binary decision trees is NP-complete // Information Processing Letters. 1976. V. 5, № 1. P. 15-17.Quinlan J.R. Learning with continuous classes // Proc. AI’92, 5th Australian Joint Conference on Artificial Intelligence. 1992. P. 343-348.Quinlan J.R. Learning with continuous classes // Proc. AI’92, 5th Australian Joint Conference on Artificial Intelligence. 1992. P. 343-348.Karalic A. Employing linear regression in regression tree leaves // Proceedings of the 10th European Conference on Artificial Intelligence. 1992. P. 440-441.Karalic A. Employing linear regression in regression tree leaves // Proceedings of the 10th European Conference on Artificial Intelligence. 1992. P. 440-441.Potts D., Sammut C. Incremental learning of linear model trees // Machine Learning. 2005. V. 61. P. 5-48.Potts D., Sammut C. Incremental learning of linear model trees // Machine Learning. 2005. V. 61. P. 5-48.Vogel D., Asparouhov O., Scheffer /. Scalable look-ahead linear regression trees // In: Proc. of 13th ACM SIGKDD. 2007. P. 757-764.Vogel D., Asparouhov O., Scheffer /. Scalable look-ahead linear regression trees // In: Proc. of 13th ACM SIGKDD. 2007. P. 757-764.Loh W.-Y. Regression trees with unbiased variable selection and interaction detection // Statistica Sinica. 2002. V. 12. P. 361-386.Loh W.-Y. Regression trees with unbiased variable selection and interaction detection // Statistica Sinica. 2002. V. 12. P. 361-386.Torgo L. A Comparative study of reliable error estimators for pruning regression trees // In Proceeding of the Iberoamerican Conference on Artificial Intelligence. 1998. P. 1-12.Torgo L. A Comparative study of reliable error estimators for pruning regression trees // In Proceeding of the Iberoamerican Conference on Artificial Intelligence. 1998. P. 1-12.Мельников Г.А. Применение методов искусственного интеллекта для исследования инфекционных заболеваний: магистерская дис.. «Магистр техники и технологии»: 230100. г. Новосибирск, 2012. 141 с.Мельников Г.А. Применение методов искусственного интеллекта для исследования инфекционных заболеваний: магистерская дис.. «Магистр техники и технологии»: 230100. г. Новосибирск, 2012. 141 с.Murthy Sreerama K. Automatic construction of decision trees from data: A multi-disciplinary survey // Data Mining and Knowledge Discovery. 2005. V. 2, № 4. P. 345-389.Murthy Sreerama K. Automatic construction of decision trees from data: A multi-disciplinary survey // Data Mining and Knowledge Discovery. 2005. V. 2, № 4. P. 345-389.Chen J., Chen Z. Extended Bayesian information criteria for model selection with large model spaces // Biometrika. 2008. V. 95, № 3. P. 759-771.Chen J., Chen Z. Extended Bayesian information criteria for model selection with large model spaces // Biometrika. 2008. V. 95, № 3. P. 759-771.Frank A., Asuncion A. UCI machine learning repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science. 2010.Frank A., Asuncion A. UCI machine learning repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science. 2010.KEEL data-mining software tool: data set repository, integration of algorithms and experimental analysis framework / J. Alcalâ-Fdez, A. Fernandez, J. Luengo, J. Derrac, S. Garda, L. Sânchez, F. Herrera // Journal of Multiple-Valued Logic and Soft Computing. 2011. V. 17. P. 255-287.KEEL data-mining software tool: data set repository, integration of algorithms and experimental analysis framework / J. Alcalâ-Fdez, A. Fernandez, J. Luengo, J. Derrac, S. Garda, L. Sânchez, F. Herrera // Journal of Multiple-Valued Logic and Soft Computing. 2011. V. 17. P. 255-287.Gramacy R.B. Model choice and data mining [Электронный ресурс]. URL: http://faculty.chicagobooth.edu/robert.gramacy/teaching/ara/lect7.pdf (дата обращения: 14.09.2014).Gramacy R.B. Model choice and data mining [Электронный ресурс]. URL: http://faculty.chicagobooth.edu/robert.gramacy/teaching/ara/lect7.pdf (дата обращения: 14.09.2014).

The authors declare that there are no conflicts of interest present.