The iterative method of regression trees induction
Abstract
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.
About the Authors
G. A. Melnikov
Новосибирский государственный технический университет
Russian Federation
Russian Federation
V. V. Gubarev
Новосибирский государственный технический университет
Russian Federation
Russian Federation
References
1. Classification and regression trees / L. Breiman, J.H. Friedman, R.A. Olshen, C.J. Stone. Belmont: Wadsworth International Group, 1984. 259 p.
2. Hyafil L., Rivest R L. Constructing optimal binary decision trees is NP-complete // Information Processing Letters. 1976. V. 5, № 1. P. 15-17.
3. Quinlan J.R. Learning with continuous classes // Proc. AI’92, 5th Australian Joint Conference on Artificial Intelligence. 1992. P. 343-348.
4. Karalic A. Employing linear regression in regression tree leaves // Proceedings of the 10th European Conference on Artificial Intelligence. 1992. P. 440-441.
5. Potts D., Sammut C. Incremental learning of linear model trees // Machine Learning. 2005. V. 61. P. 5-48.
6. Vogel D., Asparouhov O., Scheffer /. Scalable look-ahead linear regression trees // In: Proc. of 13th ACM SIGKDD. 2007. P. 757-764.
7. Loh W.-Y. Regression trees with unbiased variable selection and interaction detection // Statistica Sinica. 2002. V. 12. P. 361-386.
8. 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.
9. Мельников Г.А. Применение методов искусственного интеллекта для исследования инфекционных заболеваний: магистерская дис.. «Магистр техники и технологии»: 230100. г. Новосибирск, 2012. 141 с.
10. 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.
11. Chen J., Chen Z. Extended Bayesian information criteria for model selection with large model spaces // Biometrika. 2008. V. 95, № 3. P. 759-771.
12. 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.
13. 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.
14. Gramacy R.B. Model choice and data mining [Электронный ресурс]. URL: http://faculty.chicagobooth.edu/robert.gramacy/teaching/ara/lect7.pdf (дата обращения: 14.09.2014).
Review
For citations:
Melnikov G.A., Gubarev V.V. The iterative method of regression trees induction. The Herald of the Siberian State University of Telecommunications and Information Science. 2016;(4):59-67. (In Russ.)
Views:
1170
Email this article 