Hybrid evolutionary algorithm for automated design of decision trees

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.