Сибирский федеральный университет

Перевод названия: Hybrid evolutionary algorithm for automated design of decision trees

Тип публикации: статья из журнала

Год издания: 2014

Ключевые слова: genetic algorithm, genetic programming, decision trees, design automation, medical diagnosis, генетический алгоритм, генетическое программирование, деревья принятия решений

Аннотация: Рассматриваются вопросы, связанные с построением и обучением деревьев принятия решения. Разбираются проблемы переобучения деревьев принятия решения и их способности к обобщению. Обсуждаются проблемы локальных поисковых процедур для настройки деревьев принятия решения. Предлагается эволюционный подход к автоматизированному формированию деревьев принятия решения на основе гибридизации алгоритма генетического программирования и генетического алгоритма. Алгоритм генетического программирования решает задачу структурного поиска в пространстве деревьев принятия решения. Объектом поиска для генетического программирования служит взаимное расположение функциональных узлов в дереве принятия решения (структура). Структура дерева выстраивается из элементов терминального и функционального множеств. В качестве элементов функционального множества выбираются возможные условия, которые ограничивают одну из входных переменных и разбивают исходную совокупность на группы. В качестве элементов терминального множества выбираются возможные решения, которые принимаются в рамках рассматриваемой задачи. Генетический алгоритм решает задачу параметрической оптимизации. Каждое условие в дереве имеет один или несколько числовых параметров. Эти параметры кодируются в бинарную строку и осуществляется поиск в направлении уменьшения ошибки дерева принятия решения на обучающей выборке. Приводится совместная схема работы генетического программирования и генетического алгоритма. Рассматриваются основные эволюционные операторы. Предложенный подход был реализован в виде программной системы, позволяющей получать бинарные деревья принятия решения с узлами, содержащими не более одного параметра. Приводятся рабочие окна программы. С помощью программной системы решена задача о диагностике степени тяжести повреждений органов брюшной полости при перитоните. Показано, что эволюционный алгоритм, построенный на основе гибридизации алгоритма генетического программирования и генетического алгоритма, позволяет получать деревья принятия решения с высоким свойством обобщения, использующие в 4 раза меньше информации в сравнении с теми данными, которые фиксируются при анамнезе пациента. 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.

Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева

Выпуск журнала: № 5

Номера страниц: 85-92

ISSN журнала: 18169724

Место издания: Красноярск

Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева

• Липинский Леонид Витальевич (Сибирский государственный аэрокосмический университет им. акад. М.Ф. Решетнева)
• Кушнарева Татьяна Владимировна (Сибирский государственный аэрокосмический университет им. акад. М.Ф. Решетнева)
• Дябкин Евгений Владимирович (Дорожная клиническая больница на ст. Красноярск ОАО «РЖД»)
• Попов Евгений Александрович (Сибирский государственный аэрокосмический университет им. акад. М.Ф. Решетнева)

• РИНЦ (eLIBRARY.RU)