Гибридный эволюционный алгоритм автоматизированного формирования деревьев принятия решения
Автор: Липинский Леонид Витальевич, Кушнарева Татьяна Владимировна, Дябкин Евгений Владимирович, Попов Евгений Александрович
Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau
Рубрика: Математика, механика, информатика
Статья в выпуске: 5 (57), 2014 года.
Бесплатный доступ
Рассматриваются вопросы, связанные с построением и обучением деревьев принятия решения. Разбираются проблемы переобучения деревьев принятия решения и их способности к обобщению. Обсуждаются проблемы локальных поисковых процедур для настройки деревьев принятия решения. Предлагается эволюционный подход к автоматизированному формированию деревьев принятия решения на основе гибридизации алгоритма генетического программирования и генетического алгоритма. Алгоритм генетического программирования решает задачу структурного поиска в пространстве деревьев принятия решения. Объектом поиска для генетического программирования служит взаимное расположение функциональных узлов в дереве принятия решения (структура). Структура дерева выстраивается из элементов терминального и функционального множеств. В качестве элементов функционального множества выбираются возможные условия, которые ограничивают одну из входных переменных и разбивают исходную совокупность на группы. В качестве элементов терминального множества выбираются возможные решения, которые принимаются в рамках рассматриваемой задачи. Генетический алгоритм решает задачу параметрической оптимизации. Каждое условие в дереве имеет один или несколько числовых параметров. Эти параметры кодируются в бинарную строку и осуществляется поиск в направлении уменьшения ошибки дерева принятия решения на обучающей выборке. Приводится совместная схема работы генетического программирования и генетического алгоритма. Рассматриваются основные эволюционные операторы. Предложенный подход был реализован в виде программной системы, позволяющей получать бинарные деревья принятия решения с узлами, содержащими не более одного параметра. Приводятся рабочие окна программы. С помощью программной системы решена задача о диагностике степени тяжести повреждений органов брюшной полости при перитоните. Показано, что эволюционный алгоритм, построенный на основе гибридизации алгоритма генетического программирования и генетического алгоритма, позволяет получать деревья принятия решения с высоким свойством обобщения, использующие в 4 раза меньше информации в сравнении с теми данными, которые фиксируются при анамнезе пациента.
Генетический алгоритм, генетическое программирование, деревья принятия решений
Короткий адрес: https://sciup.org/148177378
IDR: 148177378
Список литературы Гибридный эволюционный алгоритм автоматизированного формирования деревьев принятия решения
- Quinlan J. Ross. Programs for Machine learning//Morgan Kaufmann Publishers. 1993. P. 302.
- Методы и модели анализа данных: OLAP и Data Mining: учеб. пособие/А. А. Барсегян . СПб.: БХВ-Петербург, 2004. 336 с.
- Russel S., Norvig P. Artificial Intelligence: A Modern Approach. 3rd Edition. Pearson Education Limited, 2009. 1099 p.
- Haykin S. Neural networks, a comprehensive foundation. N. Y.: Macmillan College Publishing Company. 1994.
- Короткий С. Современные микропроцессоры//Нейронные сети: алгоритм обратного распространения: сб. ст./сост. В. В. Корнеев, А. В. Киселев. 2-е изд. М., 2000.
- Короткий С. Современные микропроцессоры//Нейронные сети: основные положения: сб. ст./сост. В. В. Корнеев, А. В. Киселев. 2-е изд. М., 2000.
- Семенкин Е. С., Липинский Л. В. О коэволюци-онном генетическом алгоритме автоматизированного проектирования системы управления на нечеткой логике//Автоматизация и современные технологии. 2006. № 11.
- Семенкин Е. С. Липинский Л. В. Применение алгоритма генетического программирования в задачах автоматизации проектирования интеллектуальных информационных технологий//Вестник СибГАУ 2006. Вып. 3(10).
- Семенкин Е. С. Липинский Л. В. Структурная адаптация нейронной сети методом генетического программирования//Исследование, разработка и применение высоких технологий в промышленности: сб. тр. II Междунар. науч.-практ. конф. СПб.: Изд-во Политехн. ун-та, 2006.
- О генетическом программировании . URL: http://www.genetic-programming. com (дата обращения: 17.01.2015).
- Koza J. R. Genetic programming tutorial. Morgan Kaufmann Publishers, 1994.
- Wright A. Genetic algorithms for real parameter optimization//Foundations of Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, 1991. Рp. 205-218.
- Poli Riccardo. Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover//Genetic Programming and Evolvable Machines. 2001. № 2.
- Eiben A. E., Smith J. E. Introduction to Evolutionary Computing. New York: Springer-Verlag Berlin Heidelberg. 2003. 299 p.
- Haupt R. L., Haupt S. E. Practical Genetic Algorithms. 2ed. Wiley, 2004. P. 261.
- 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. Pp. 414-421.
- 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.
- Semenkina M., Semenkin E. Hybrid selfconfiguring evolutionary algorithm for automated design of fuzzy classifier//Advances in Swarm Intelligence/Y. Tan, Y. Shi, C. A. C. Coello (Eds.). 2014. PT1. LNCS 8794. Pp. 310-317.
