Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 159.688
HYBRID EVOLUTIONARY ALGORITHM FOR AUTOMATED DESIGN OF DECISION TREES
L. V. Lipinskiy [1], T. V. Kushnareva [1], E. V. Dyabkin [2], E. A. Popov [1]
[1] Siberian State Aerospace University named after academician M. F. Reshetnev 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation Е-mail: LipinskiyL@mail.ru, rare-avis@mail.ru, epopov@bmail.ru [2] Krasnoyarsk State Medical University 47, Partizana Zheleznyaka Str., Krasnoyarsk, 660022, Russian Federation Е-mail: dyabkyn@mail.ru
Issues related to the design and training of decision trees, are considered in the paper. Problems of decision trees over-fitting are discussed as well as their ability to the generalization. Questions of local search procedures for the adjustment of decision trees are described. An evolutionary approach to the automated design of decision trees is suggested based on a hybridization of the genetic programming and genetic algorithm. Genetic programming fulfills the search of effective structures in the space of decision trees. Genetic programming is searching for effective variant of decision trees functional nodes position and interconnections, i.e. a structure. The tree structure is built with elements of terminal and functional sets of genetic programming. Elements of the functional set are conditions which limited one of input variables and divided original data set into subgroups. Elements of the terminal set are possible decisions which should be made within solving a problem in hand. Genetic algorithm solves the problem of parameters optimization. Each condition within a decision tree has one or more parameters which are coded into binary string. Genetic algorithm seeks parameters which minimize an error of the decision tree on the instances of the training sample. In the article, the framework of the joint execution of genetic programming and genetic algorithm is given and main evolutionary operators are considered. Suggested approach was implemented as a computing system that allows designing binary decision trees with one parameter nodes. Operation windows of the implemented computing system are presented. The problem of diagnosing the severity of injuries of the abdominal cavity with peritonitis has been solved with the use of developed approach. It was demonstrated that the evolutionary techniques based on the hybridization of the genetic programming and the genetic algorithm allow automated designing decision trees with the high ability to generalization which use four times less information comparing to data usually collected in a patient anamnesis.
genetic programming, genetic algorithm, decision trees, design automation, medical diagnosis
References
  1. J. Ross Quinlan. Programs for Machine learning. Morgan Kaufmann Publishers. 1993. P. 302
  2. Barsegyan A. A., Kupriyanov M. S., Stepanenko V.V., Holod N.N. Metody i modeli analiza dannykh. OLAP i Data Mining [Methods and models of data analysis: OLAP и Data Mining]. SPb., BKhV-Peterburg Publ., 2004, 336 p.
  3. Russel S., Norvig P. Artificial Intelligence: A Modern Approach (3rd Edition). Pearson Education Limited, 2009, 1099 p.
  4. Haykin S. Neural networks, a comprehensive foundation. N. Y. : Macmillan College Publishing Company. 1994.
  5. Korotkiy S. Sovremennye mikroprotsessory. Neyronnye seti: algoritm obratnogo rasprostraneniya. [Modern microprocessors. Neural networks: back-propagation algorithm]. Moscow, 2000.
  6. Korotkiy S. Sovremennye mikroprotsessory. Neyronnye seti: osnovnye polozheniya. [Modern microprocessors. Neural networks: basic statements]. Moscow, 2000.
  7. Semenkin E. S. Lipinskiy L. V. [On co-evolutionary genetic algorithm for automated design of fuzzy logic system control] Avtomatizatsiya i sovremennye tekhnologii. 2006, no. 11.
  8. Semenkin E. S. Lipinskiy L. V. [Application of genetic programming algorithm in problems of intelligence information technologies automated design] Vestnik SibGAU. 2006, no. 3 (10), p. 22–26 (In Russ.).
  9. Semenkin E. S. Lipinskiy L. V. [The structural adaptation of neural network with genetic programming algorithm]. Sb. tr. II Mezhdunar. nauch.prakt. konf. “Issledovanie, razrabotka i primenenie vysokikh tekhnologiy v promyshlennosti” [Research, development and application of high technologies in the industry: Sat. tr. II International. scientific and practical. Conf.]. SPb. : Izd-vo Politekhn. un-ta Publ., 2006 (In Russ.).
  10. John R. Koza. Genetic programming Inc. Available at: http://www.genetic-programming.com. (accessed 17.01.2015).
  11. Koza J. R. Genetic programming tutorial. Morgan Kaufmann Publishers. 1994.
  12. Wright A. Genetic algorithms for real parameter optimization. Foundations of Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, 1991, p. 205–218.
  13. Poli Riccardo. Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover. Genetic Programming and Evolvable Machines, 2, 2001.
  14. Eiben, A. E., Smith J. E. Introduction to Evolutionary Computing. Springer-Verlag Berlin Heidelberg New York, 2003. 299 p.
  15. Haupt R. L., Haupt S. E. Practical Genetic Algorithms, 2ed., Wiley, 2004. P. 261.

  16. Semenkin, E., Semenkina, M. Self-configuring genetic algorithm with modified uniform crossover operator, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7331 LNCS (PART 1), 2012, p. 414–421.

  17. Semenkin E., Semenkina M. Self-Configuring Genetic Programming Algorithm with Modified Uniform Crossover. Proc. of the IEEE Congress on Evolutionary Computation, (CEC), Brisbane (Australia). 2012. P. 3401–3406.

  18. Semenkina M., Semenkin E. Hybrid self-configuring evolutionary algorithm for automated design of fuzzy classifier. In Y. Tan, Y. Shi, C.A.C. Coello (Eds.), Advances in Swarm Intelligence. 2014. PT1, LNCS 8794, Р. 310–317.

Lipinskiy Leonid Vitalievich – Cand. Sc., Docent of System analysis and operations research department, Siberian State Aerospace University named after academician M. F. Reshetnev. E-mail: LipinskiyL@mail.ru

Kushnareva Tatiana Vladimirovna – student of System analysis and operations research department, Siberian State Aerospace University named after academician M. F. Reshetnev. E-mail: rare-avis@mail.ru

Dyabkin Evgeny Vladimirovich – Cand. Sc., Docent of General surgery department, Krasnoyarsk State Medical University; surgeon for emergency of Rail-road Clinical Hospital, Krasnoyarsk railway station, JSC ‘Russian Railways’. E-mail: dyabkyn@mail.ru

Popov Evgeny Aleksandrovich – Dr. Sc., Professor of System analysis and operations research department, Siberian State Aerospace University named after academician M. F. Reshetnev. E-mail: epopov@bmail.ru