RESEARCH OF SELF-CONFIGURATING MODELS AND PROCEDURES OF GENETIC PROGRAMMING FOR FORMATION OF DECISION TREES IN PROBLEMS OF THE INTELLIGENT DATA ANALYSIS

Full Text

Введение. Алгоритм автоматизированного формирования деревьев принятия решений методом генетического программирования [1; 2] показал свою эффективность при решении тестовых и прикладных задач [3-5]. Следовательно, его дальнейшая модернизация для повышения скорости работы, удобства пользователя и уровня автоматизации является актуальной задачей. Для улучшения алгоритма были рассмотрены и реализованы три процедуры самоконфигурации: Population-Level Dynamic Probabilities (PDP), Individual-Level Dynamic Probabilities (IDP) [6] и управление с помощью нечеткого контроллера [7]. Данные процедуры позволят снизить участие пользователя в настройке алгоритма, что, в свою очередь, приведет к повышению скорости работы, удобства интерфейса и уменьшит риск человеческого фактора. Следовательно, данный алгоритм можно будет применять для решения задачи ракетно-космической отрасли, где требуется высокая точность и минимизация рисков. Population-Level Dynamic Probabilities и Individual-Level Dynamic Probabilities. Метод PDP работает следующим образом: вероятности использования генетических операторов напрямую зависят от успешности одного или другого оператора, т. е. чем успешнее действие оператора, тем чаще он используется. Вероятности рассчитываются по формуле (1): (1) где successi - это число успешных применений i-го оператора; usedi - общее число применений i-го оператора; n - общее число операторов [6; 7]. В методе IDP каждому индивиду популяции присваивается счетчик (cntji) по числу неудачных применений оператора. Вероятности применения операторов рассчитываются для каждого индивида отдельно по формуле (2): (2) где n - общее число операторов [6; 7]. Нечеткий котроллер. Нечеткий контроллер - это регулятор, построенный на базе нечетких правил [8-10]. Общую схему регулятора можно увидеть на рис. 1. Управление системы на основании нечеткой логики состоит из трех основных этапов: 1) фаззификация; 2) нечеткий вывод; 3) дефаззификация. На этапе фаззификации четкий вход (информация об управляемом объекте) переводится в нечеткую точку (если вход - скаляр) или точки (если вход - вектор), в соответствии с лингвистическими переменными. На этапе нечеткого вывода по имеющимся нечетким точкам, полученным на этапе фаззификации, и базе нечетких правил находится нечеткий выход. Нечеткий выход представляет собой нечеткое множество, конкретный элемент которого выбирается на следующем этапе. На заключительном этапе дефаззификации нечеткий выход, полученный на предыдущем этапе, переводят в четкий, используя соответствующие лингвистические переменные. Существуют несколько возможных вариантов такого перехода, например, первый максимум: из нечеткого множества (нечеткого выхода) выбирают наименьший элемент, принадлежность которого равна максимуму из принадлежностей точек, полученных при фаззификации. Нечеткий контроллер управляет вероятностями селекции (ps), скрещивания (pc) и мутации (pm) на основании таких показателей, как номер итерации (Ni), разнообразие популяции (Ii) и средняя пригодность (sredi). Общая схема управления представлена на рис. 2. На рис. 3-5 представлены функции принадлежности для каждого входа и выхода. В табл. 1-3 представлены базы правил. Формируются они следующим образом. Например, если номер итерации большой и разнообразие популяции не изменилось, то вероятность мутации изменяется слабо. Базы правил формулируются на основе многократного решения различных задач и обобщения полученного опыта. Самоконфигурирующийся гибридный эволюционный алгоритм автоматизированного проектирования деревьев принятия решений. Три настройки были реализованы в существующем алгоритме, главное рабочее окно программы можно увидеть на рис. 6. Рис. 1. Схема нечеткого контроллера Рис. 2. Общая схема управления Рис. 3. Функции принадлежности входных и выходных параметров Рис. 4. Функции принадлежности для каждого входного и выходного параметра селекции Рис. 5. Функции принадлежности для каждого входного и выходного параметра скрещивания Таблица 1 База правил для управления мутацией Ni Ii pm Если номер большой и разнообразие сильное то вероятность мутации не изменяется Если номер меньше или равен среднему и разнообразие ниже или равно слабому то вероятность мутации изменяется сильно Если номер больше или равен среднему и разнообразие ниже или равно слабому то вероятность мутации изменяется средне Если номер меньше или равен среднему и разнообразие среднее то вероятность мутации изменяется средне Если номер большой и разнообразие среднее то вероятность мутации изменяется слабо Если номер меньше или равен среднему и разнообразие сильное то вероятность мутации изменяется слабо Таблица 2 База правил для управления селекцией Sred1 Sred2 Sred3 P1 P3 P2 Если средние пригодности одинаковые (большие, средние или маленькие) то вероятности становятся равными Если две средние пригодности большие, а одна средняя то две соответствующие вероятности селекции увеличиваются, а одна уменьшается Если две средние пригодности средние, а одна маленькая то две соответствующие вероятности селекции увеличиваются, а одна уменьшается Если две средние пригодности средние, а одна большая то две соответствующие вероятности селекции уменьшаются, а одна увеличивается Если две средние пригодности маленькие, а одна средняя то две соответствующие вероятности селекции уменьшаются, а одна увеличивается Если одна средняя пригодность большая, вторая средняя, а третья маленькая то соответствующие вероятности: увеличивается, не изменяется, уменьшается Таблица 3 База правил для управления скрещиванием Sred1 Sred2 P1 P3 Если средние пригодности изменились одинаково то вероятности становятся равными Если sred1 > sred2 то вероятность одноточечного скрещивания увеличивается то вероятность случайного скрещивания уменьшается Если sred1 < sred2 то вероятность одноточечного скрещивания уменьшается то вероятность случайного скрещивания увеличивается Рис. 6. Главное рабочее окно программы Решение задачи классификации ирисов Фишера и задачи прогнозирования побочных эффектов при лечении эпилепсии. Оценка работоспособности алгоритма с реализованными методами самонастройки была проведена на репрезентативном множестве тестовых задач, решение одной из которых (классификации ирисов Фишера [11]) представлено в табл. 4 для сравнения эффективности настроек. После оценки было проведено исследование предложенного подхода на практической задаче прогнозирования нежелательных явлений при лечении эпилепсии [12]. Для решения этой задачи была построена выборка, содержащая сведения об около ста пациентах. Для каждого пациента в выборке были определены следующие параметры. 1. Входные: пол, возраст, степень обследования, характеристика приступов, МРТ, ВЭМ, терапевтический лекарственный мониторинг, фармакогенетика, вид мутации по трем цитохромам, наличие нежелательных лекарственных явлений. 2. Выходные: группа риска нежелательных явлений и со стороны каких систем организма есть нежелательные явления. По первому выходу представлены 5 градаций: низкая, средняя, высокая группа риска, не уточнялась и данных для определения недостаточно. Для второго выхода выделены 11 систем: не зарегистрированы нежелательные явления, со стороны центральной нервной системы, со стороны желудочно-кишечного тракта, со стороны эндокринной системы, поражение кожи и ногтей, со стороны мочевыделительной системы, со стороны репродуктивной системы, данных для определения недостаточно, а также есть случаи, когда нежелательные явления проявлялись со стороны нескольких систем одновременно. Алгоритму были предоставлены достаточные и равные вычислительные ресурсы. Проведены исследования всех трех подходов, получены результаты по 40 запускам для каждого подхода, рассчитываемые по формуле (3), впоследствии усредненные и отраженные в табл. 4. Также в табл. 4 содержится усредненный результат работы алгоритма без самонастройки: (3) где error - ошибка классификации; nо - число неверно расклассифицированных измерений; n - общее число измерений. Статистический анализ результатов. Для сравнения эффективности подходов был проведен статистический анализ [13]. Была выдвинута нулевая гипотеза о том, что нет статистически значимого различия между каждыми двумя генеральными совокупностями, т. е. их математические ожидания равны (H0: M[X] = M[Y]), при конкурирующей гипотезе, что математическое ожидание первой совокупности больше, чем у второй (H1: M[X] > M[Y]). Так как независимые выборки произвольно распределены и их дисперсии неизвестны, но при этом они имеют объем, больше 30 каждая, то выборочные средние распределены приближенно нормально, а выборочные дисперсии являются достаточно хорошими оценками генеральных дисперсий. Тогда можно применить следующий критерий (формула (4)): (4) Критическая область в данном случае правосторонняя (рис. 7), уровень значимости равен 0,05, критическая точка равна 1,65 [14; 15]. Значения критерия соответствующих выборок приведены в табл. 5 и 6 (при zнабл < zкр гипотеза H0 принимается, иначе отвергается). Таблица 4 Результаты работы алгоритма с разными настройками Методы/задачи Классификация ирисов Фишера Прогнозирование побочных реакций при лечении эпилепсии Алгоритм без самонастройки 0,044 0,173 IDP 0,02 0,153 PDP 0,022 0,156 Настройка с помощью нечеткого контроллера 0,016 0,132 Рис. 7. Правосторонняя критическая область Таблица 5 Попарный статистический анализ для задачи классификации ирисов IDP PDP Настройка с помощью нечеткого контроллера Алгоритм без самонастройки 3,28 2,31 5,02 IDP 0,90 1,86 PDP 2,65 Таблица 6 Попарный статистический анализ для задачи прогнозирования побочных явлений IDP PDP Настройка с помощью нечеткого контроллера Алгоритм без самонастройки 2,04 1,69 4,37 IDP 0,46 2,38 PDP 2,82 Заключение. Проведенный попарный статистический анализ результатов выявил следующие результаты: алгоритм с любой процедурой самоконфигурирования лучше, чем без нее; управление с помощью нечеткого контроллера лучше, чем методы PDP и IDP, при этом последние не имеют статистически значимого различия между собой, поэтому несравнимы. Следует заметить, что у нечеткого контроллера есть и дополнительные преимущества: прозрачность принятия решения, широкие возможности в управлении (включение перезапуска, добавление новых случайных индивидов и т. д.). Последующая разработка процедур автоматизированной настройки правил позволит существенно увеличить эффективность алгоритма.

About the authors

L. V. Lipinskiy

Reshetnev Siberian State Aerospace University

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

T. V. Kushnareva

Reshetnev Siberian State Aerospace University

Email: rare-avis@mail.ru
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

References

Supplementary files