Алгоритмы построения гибридного нечеткого классификатора для анализа медицинских данных

Государственное научное учреждение

«Объединенный институт проблем информатики

Национальной академии наук Беларуси»



УДК 004.931;004.8





Новоселова Наталья Анатольевна



Алгоритмы построения гибридного нечеткого классификатора для анализа медицинских данных



Автореферат диссертации
на соискание ученой степени кандидата технических наук
по специальности 05.13.01 – «Системный анализ, управление и обработка

информации»








Минск 2008


Работа выполнена в государственном научном учреждении «Объединенный институт проблем информатики
Национальной академии наук Беларуси»


Научный руководитель:

Том Игорь Эдуардович,
кандидат технических наук, заведующий лаборатории биоинформатики Объединённого института проблем информатики НАН Беларуси


Официальные оппоненты:

Булойчик Василий Михайлович,
доктор технических наук, профессор, начальник кафедры информационно-вычислительных систем Военной академии Республики Беларусь


Краснопрошин Виктор Владимирович, кандидат физико-математических наук, доцент, заведующий кафедры математического обеспечения автоматизированных систем управления Белорусского государственного университета

Оппонирующая
организация:

Белорусский государственный университет информатики и радиоэлектроники

Защита состоится 4 марта 2008 г. в 16.30 на заседании совета по защите диссертаций Д 01.04.01 при государственном научном учреждении «Объединенный институт проблем информатики Национальной академии наук Беларуси» по адресу: 220012, г. Минск, ул. Сурганова 6, телефон ученого секретаря (+375 17) 284 21 68, e-mail: lipn@newman.bas-net.by

С диссертацией можно ознакомиться в библиотеке государственного научного учреждения «Объединенный институт проблем информатики Национальной академии наук Беларуси»

Автореферат разослан « » …………. 2008 г.


Ученый секретарь совета
по защите диссертаций
доктор технических наук С.Ф. Липницкий

КРАТКОЕ ВВЕДЕНИЕ

Классификационная задача, которая в медицинской области эквивалентна задаче диагностики, является одной из основных задач анализа данных. В настоящее время классификаторы, построенные с помощью методов статистического анализа, нейронных сетей, эволюционных алгоритмов, экспертных систем и других подходов, позволяют получить достаточно точные результаты. Однако, для медика, принимающего решение о диагнозе, отнесении больного к той или иной группе риска, важны не только результаты классификации, но и возможность их интерпретации. Поэтому для медицинских задач предпочтительнее является классификационная модель, состоящая из набора лингвистических правил, аналогичных используемым в процессе рассуждений человека. Использование аппарата нечеткой логики позволяет представить классификатор в виде набора правил понятных медику. В связи с тем, что нечеткие классификаторы являются статичными, объединение их с другими интеллектуальными методами, обеспечивающими обучение и адаптацию классификатора к имеющимся данным, как например нейронные сети и генетические алгоритмы, представляет собой современное направление исследований в области интеллектуального анализа данных. Проведенный анализ литературных источников позволяет сделать вывод об отсутствии законченных решений по построению простого и компактного гибридного классификатора, обеспечивающего компромисс между точностью классификации и интерпретируемостью правил. Таким образом, актуальной задачей является разработка алгоритмов построения гибридного нечеткого классификатора для анализа медицинских данных, который обеспечивает не только высокую точность классификации, но и состоит из компактного и интерпретируемого набора классификационных правил.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Связь работы с крупными научными программами, темами

Диссертационная работа выполнена в Объединенном институте проблем информатики Национальной академии наук Беларуси в рамках следующих научных тем и программ:

  1. Государственная научно-техническая программа «Передовые информационные и телекоммуникационные технологии» (2004-2005), задание 01.08 «Разработать информационную технологию анализа данных на базе гибридных нейросетевых моделей для задач классификации и прогнозирования в детской лейкозологии», номер госрегистрации 20042180.

  2. Государственная комплексная программа научных исследований «Научные основы информационных технологий и систем» (Инфотех, 2006-2010), задание Инфотех-11 «Методы обработки, анализа и классификации многомерных данных и изображений», номер госрегистрации 20062478.

  3. Государственная программа прикладных исследований «Оптика, электроника, информатика» (2004-2005), задание «Разработать информационную технологию разведочного анализа прецедентных медицинских данных на основе нейросетевых и статистических методов для применения в детской онкогематологии», номер госрегистрации 20041307.

  4. Государственная научно-техническая программа «Информационные технологии» (2006-2009), задание «Разработать и внедрить информационную технологию диагностики врожденных иммунодефицитных состояний у детей на основе анализа клинических и лабораторных показателей», номер госрегистрации 2007183.

  5. Научный проект Белорусского республиканского фонда фундаментальных исследований №T02P-135 (2002-2004) «Нечеткие и синергетические модели в разработке антропоморфных агентов и эволюционных мультиагентных систем», номер госрегистрации 20022504.

  6. Международный проект МНТЦ В-522 «Создание компьютерной системы анализа прогностических факторов риска для выбора адекватной терапии острых лейкозов у детей» (2001-2005).

Цель и задачи исследования

Целью диссертационной работы является разработка алгоритмов построения гибридного нечеткого классификатора для анализа данных пациентов (объектов данных), характеризующихся набором значений различных клинических и лабораторных показателей.

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

    • разработка общей схемы и основных этапов построения гибридного нечеткого классификатора (ГНК);

    • разработка подхода и алгоритма предварительной обработки медицинских данных, которые позволяют отобрать наиболее информативные признаки для решения поставленной задачи классификации объектов данных, что обеспечивает возможность построения гибридного нечеткого классификатора с компактной структурой и с меньшими временными и вычислительными затратами;

    • разработка алгоритмов построения начальной структуры ГНК, позволяющих использовать имеющиеся данные для выделения отдельных нечетких правил из всего набора правил, представляющих собой все возможные комбинации нечетких множеств отдельных признаков;

    • представление гибридного нечеткого классификатора в нейросетевой архитектуре и разработка нейроподобного алгоритма его обучения с учетом не дифференцируемых активационных функций нейросетевого представления ГНК и семантических ограничений;

    • разработка алгоритма оптимизации и процедур упрощения структуры ГНК для получения компактного и интерпретируемого набора нечетких правил классификации;

    • разработка программного комплекса, реализующего решение задачи классификации пациентов, характеризующихся набором значений различных клинических и лабораторных показателей.

Объектом исследования диссертационной работы являются разнородные медицинские данные, для анализа которых разрабатывается гибридный нечеткий классификатор.

Предметом исследования являются алгоритмы построения гибридного нечеткого классификатора, предназначенного для анализа медицинских данных.

Объект исследования обладает специфическими характеристиками, которые не позволяют во многих случаях построить точную модель для решения классификационной задачи, кроме того, на практике, большое значение имеет представление результатов классификации в интерпретируемом виде. Таким образом, для анализа медицинских данных необходимым является разработка новых алгоритмов интеллектуального анализа данных, позволяющих не только эффективно решать задачу классификации, но и представлять решение на естественном для пользователя языке, в виде простых классификационных правил типа «если-то». Разрабатываемые алгоритмы должны быть направлены на построение простой и компактной структуры классификатора, позволяющей медику легко интерпретировать и оценивать получаемое решение классификационной задачи.

Положения, выносимые на защиту

  1. Подход к отбору информативных признаков для задач классификации с использованием генетического алгоритма. Согласно предложенному подходу отбор признаков рассматривается как задача многокритериальной оптимизации с двумя критериями: точность классификации и количество признаков в подмножестве. Отличительной особенностью подхода является использование генетического алгоритма для решения оптимизационной задачи, который позволяет за один прогон получить несколько недоминируемых подмножеств признаков с различными соотношениями между значениями частных критериев оптимизации.

  2. Структурно-ориентированный алгоритм инициализации базы правил гибридного нечеткого классификатора. Алгоритм включает последовательное выполнение трех процедур: создание набора нечетких предпосылок правил; определение следствий и весов для созданных предпосылок нечетких правил; формирование окончательного набора начальных правил с учетом коэффициентов эффективности. Отличительной особенностью алгоритма является возможность создания нечетких правил ГНК на основе обучающих данных, что позволяет уже на начальном этапе построить более компактную и ориентированную на имеющиеся данные структуру ГНК.

  3. Обобщенный алгоритм обучения гибридного нечеткого классификатора. Отличительной особенностью алгоритма является возможность его применения при наличии не дифференцируемых функций активации нейросетевого представления ГНК, а также использование ограничений в процессе обучения, гарантирующих сохранение семантической интерпретируемости гибридного нечеткого классификатора.

  4. Алгоритм многокритериальной оптимизации структуры гибридного нечеткого классификатора. Отличительной особенностью данного алгоритма является использование генетических операций, позволяющих получить несколько наборов нечетких правил, которые являются недоминируемыми по трем критериям: точность классификации, количество нечетких правил и общая длина нечетких правил. Конечному пользователю предоставляется возможность среди полученных наборов правил выбрать наиболее подходящий с точки зрения соотношения точности классификации и интерпретируемости соответствующего нечеткого классификатора.

  5. Гибридный нечеткий классификатор для анализа медицинских данных, позволяющий решать задачи классификации пациентов, характеризующихся набором значений различных клинических и лабораторных показателей. Отличительными особенностями гибридного нечеткого классификатора является его компактность и интерпретируемость, при сохранении достаточно высокой точности, что обеспечивается применением для его построения специально разработанных алгоритмов интеллектуального анализа данных.

Личный вклад соискателя

Все предложенные алгоритмы разработаны и программно реализованы лично автором. Участие научного руководителя заключалось в постановке задач и определении возможных путей решения, обсуждении результатов теоретических и практических исследований, проведенных автором самостоятельно. В публикациях с соавторами вклад соискателя определяется рамками излагаемых в диссертационной работе результатов.

Апробация результатов диссертации

Основные теоретические и практические результаты диссертационной работы были представлены автором на следующих научных конференциях:

4-я Международная научная конференция “Интеллектуализация обработки информации” ИОИ-2002, июнь 2002, г.Алушта, Украина.

Sixth Scientific Advisory Committee Seminar “Science and Computing”, 15-17 сентября 2003, г.Москва, Россия.

11-я Всероссийская конференция «Математические методы распознавания образов» 16-22 ноября 2003, г.Пущино, Россия.

5-я Международная научная конференция “Интеллектуализация обработки информации” ИОИ-2004, 14-19 июня 2004, г.Алушта, Украина.

International Conference "Building Information Society in the Healthcare in Euroregion Niemen", 17-19 февраля 2005, г.Белосток, Польша.

International Conference on Advanced Information and Telemedicine Technologies for Health”, 8-10 ноября 2005, г.Минск, Беларусь.

6-я Международная научная конференция “Интеллектуализация обработки информации” ИОИ-2006, 4-11 июня 2006г., г.Алушта, Украина.

4-я Международная дистанционная научно-практическая конференция «Информационные Технологии и Кибернетика на Службе Здравоохранения' 2006», июль 2006, г.Днепропетровск, Украина.

10-я Национальная конференция по искусственному интеллекту с международным участием (КИИ-06), 26-28 сентября 2006, г.Обнинск, Россия.

7-я Международная научно-техническая конференция «Искусственный интеллект. Интеллектуальные и многопроцессорные системы 2006», 24-29 сентября 2006, пос. Кацивели АР Крым, Украина.

3-я Международная конференция «Информационные системы и технологии» (IST’2006), 1-3 ноября 2006, г.Минск, Беларусь.

Опубликованность результатов диссертации

По теме диссертации опубликовано 22 научные работы, включающие 13 статей в рецензируемых научных журналах, 8 докладов на международных конференциях и 1 те­зисы доклада. Общий объём статей, опубликованных в изданиях, реко­мендуе­мых ВАК Беларуси, составляет 3,4 авторских листа; общий объём других на­учных публикаций составляет 3,7 авторских листа.

Структура и объем диссертации

Диссертационная работа состоит из введения, общей характеристики работы, четырёх глав, заключения, библиографического списка и прило­жений. В главе 1 рассматриваются методы обработки и анализа данных, ориентированные на медицинские задачи классификации, формулиру­ется содержательная постановка задач исследования, целью которого является разработка алгоритмов построения гибридного нечеткого классификатора для анализа медицинских данных. В главе 2 приводится определение гибридного нечёткого классификатора и обобщённая схема этапов его построения. Рассматривается первый этап построения ГНК – этап предобработки медицинских данных. В главе 3 описываются два альтернативных алгоритма определения начальной структуры гибридного нечёткого классификатора, составляющих содержание второго этапа его построения. В главе 4 описываются алгоритмы обучения гибридного нечеткого классификатора и многокритериальной оптимизации его структуры, составляющие содержание третьего и четвёртого этапов построения ГНК. Рассматривается назначение и структура программного комплекса (ПК) «Гибрид», реализующего предложенные алгоритмы и приводятся результаты тестирования ГНК на наборах медицинских данных из архива данных по машинному обучению и на реальном наборе данных из области лейкозологии. В приложениях приведено подробное описание работы с ПК «Гибрид», акты внедрения.

Диссертационная работа содержит 100 страниц основного текста; 43 рисунка и 29 таблиц, расположенных в тексте диссертации; 2 приложе­ния на 20 страницах; в списке использованных источников представлено 124 наименования, в списке публикаций автора по теме диссертации – 22 наименования работ.

Основное содержание работы

Во введении показана актуальность темы диссертационной работы, определена цель и задачи исследования.

В первой главе приводится формальная постановка задачи медицинской классификации объектов данных. Рассматриваются причины необходимости перехода к использованию классификационных моделей, представимых в виде набора правил. Обосновывается необходимость применения нечёткой логики для решения классификационных задач. Рассматривается общая архитектура и алгоритмы обучения нейронных сетей, которые применяются для обучения нечетких систем. Представлена нейросетевая нечеткая система Мамдани-Заде, представляющая интерес при использовании в качестве основы для построения формального инструмента решения медицинских задач классификации пациентов в условиях неопределенности.

Показана целесообразность проведение исследований по разработке простого и компактного гибридного нечеткого классификатора, объединяющего нечеткие системы, с их возможностями манипулировать понятными и интерпретируемыми правилами, нейронные сети с их адаптивными алгоритмами обучения и генетические алгоритмы, позволяющие находить оптимальные решения в многомерном пространстве поиска. Выполнена содержательная постановка задач исследования, целью которого является разработка алгоритмов построения гибридного нечеткого классификатора, который сочетал бы высокую точность классификации пациентов с простотой и семантической интерпретируемостью классификационных правил.

В
о второй главе
приводится определение нечёткого классификатора и гибридного нечёткого классификатора, разработанного в рамках диссертационной работы. Предложена обобщенная схема (рисунок 1) и сформулированы основные четыре этапа его построения: 1) предварительная обработка медицинских данных; 2) построение начальной структуры; 3) обучение ГНК; 4) оптимизация структуры ГНК.

Рисунок 1 – Обобщенная схема этапов построения ГНК

Для возможности сохранения интерпретируемости ГНК сформулированы основные семантические и синтаксические критерии интерпретируемости нечетких правил классификации, которые накладывают ограничения на изменение параметров нечеткого классификатора.

Гибридный нечеткий классификатор представлен в трехслойной нейросетевой архитектуре (рисунок 2), что позволяет использовать нейроподобные алгоритмы обучения для настройки его параметров. Веса соединений первого и второго слоев представляются нечеткими множествами предпосылок правил, веса соединений второго и третьего слоев представляют степени достоверности правил, в качестве функций активации используются Т-нормы и Т-конормы, а именно функции минимума и максимума.

Рисунок 2 – Нейросетевое представление нечеткого классификатора с k правилами и M классами

Рассматривается первый этап построения ГНК – этап предобработки медицинских данных, который включает отбор информативных признаков, позволяющий упростить начальную структуру ГНК. Для отбора подмножеств признаков используются два альтернативных подхода:

  1. подход к отбору информативных признаков с использованием генетического алгоритма;

  2. интерактивный алгоритм построения дерева решений.

Согласно предложенному подходу, задача отбора информативных признаков сформулирована как задача многокритериальной оптимизации. Выполнена постановка задачи многокритериальной оптимизации, согласно которой из множества различных подмножеств признаков требуется найти подмножество , которое является решением двухкритериальной задачи оптимизации с двумя следующими критериям:

max f1(S), min f2(S),

где f1(S) – количество правильно классифицированных объектов с использованием подмножества признаков S, f2(S) – количество элементов подмножества признаков S.

Для решения поставленной оптимизационной задачи используется генетический алгоритм, который имеет модифицированную схему реализации и позволяет за один прогон получить несколько подмножеств признаков, аппроксимирующих множество Парето решаемой многокритериальной оптимизационной задачи. Приводится пример применения подхода для набора медицинских данных из международного архива данных по машинному обучению. Отличительными особенностями предложенного подхода к отбору информативных признаков являются:

  1. Представление задачи отбора информативных признаков в качестве задачи многокритериальной оптимизации.

  2. Использование генетического алгоритма для отбора признаков, в котором: недоминируемые решения хранятся в отдельной дополнительной популяции, которая обновляется на каждой итерации; при расчете значений функции приспособленности для особей генетического алгоритма весовые коэффициенты критериев оптимизации генерируются случайным образом; на каждой итерации используется модифицированная стратегия элитаризма.

  3. Получения нескольких недоминируемых подмножеств признаков с различными соотношениями между отдельными критериями оптимизации.

Описывается разработанный интерактивный алгоритм построения дерева решений, который в процессе своей работы осуществляет отбор информативных признаков, позволяя в интерактивном режиме учитывать знания медиков-экспертов одновременно с выполнением стандартного алгоритма последовательного разделения объектов данных по значению признака с использованием информационного критерия, применяемого в CART деревьях. Интерактивность алгоритма построения классификационного дерева обеспечивается разработанным интерфейсом. На каждом шаге построения дерева решений имеется возможность выбора из нескольких интерактивных функций, определяющих последовательность работы алгоритма.

В третьей главе предлагаются два альтернативных алгоритма определения начальной структуры (базы правил) нечеткого классификатора, составляющих содержание второго этапа построения ГНК:

  • структурно-ориентированный алгоритм инициализации базы правил ГНК;

  • алгоритм построения начальной структуры ГНК с использованием нечеткой кластеризации данных.

Для реализации структурно-ориентированного алгоритма и осуществления нечеткого разбиения области значений всех входных непрерывных признаков разработана процедура определения количества и расположения функций принадлежности нечетких множеств на интервале значений каждого из признаков. Процедура использует результаты работы предложенного автором статистического алгоритма дискретизации и отбора признаков, тем самым, учитывая статистические характеристики данных.

Структурно-ориентированный алгоритм позволяет ограничить максимальное количество возможных классификационных правил, используя обучающий набор данных. Алгоритм включает последовательное выполнение трех процедур. С использованием первой процедуры предложенного алгоритма создаются все необходимые предпосылки нечетких правил. С использованием второй процедуры определяется наилучшее следствие для каждого нечеткого правила и его весовой коэффициент. Построение начальной базы правил завершается реализацией третьей процедуры, которая позволяет сократить количество нечетких правил путем их отбора с использованием коэффициента эффективности. Коэффициент эффективности правила рассчитывается с использованием критерия поддержки по формуле:

.

Коэффициент P(Rk) определяет однозначность правила Rk и его значения лежат в диапазоне [-1,1].

Отличительные особенности алгоритма следующие:

  • определение следствий, весовых коэффициентов нечетких правил с использованием критерия доверия;

  • расчет значений коэффициента эффективности нечетких правил, который является модифицированной версией критерия оценки итерационного алгоритма обучения нечеткой модели;

  • формирование окончательной структуры ГНК с использованием значений коэффициентов эффективности нечетких правил.

Далее описывается алгоритм построения начальной структуры ГНК с использованием нечеткой кластеризации данных. Отличительной особенностью алгоритма является одновременное определение нечетких множеств и нечетких классифицирующих правил на основе обучающего набора данных. Основными этапами реализации алгоритма построения начальной структуры ГНК с использованием нечеткой кластеризации являются:

  1. Выполнение нечеткой кластеризации входных данных, результатом которой является набор нечетких многомерных кластеров.

  2. Проектирование многомерного кластера на одномерные координатные оси и аппроксимация полученных дискретных функций принадлежности нечетких множеств треугольными или трапециевидными функциями.

  3. Генерация классификационных правил, соответствующих отдельным кластерам.

В четвёртой главе рассматриваются алгоритм обучения гибридного нечеткого классификатора и алгоритм многокритериальной оптимизации его структуры, составляющие содержание третьего и четвёртого этапов построения ГНК. Перед началом обучения гибридный нечеткий классификатор представляется в нейросетевой архитектуре, описанной в главе 2. Далее согласно предложенному обобщенному обучающему алгоритму осуществляется настройка параметров классификатора. Одна итерация обобщенного алгоритма состоит из последовательной реализации двух этапов обучения. На первом этапе настраиваются параметры функций принадлежности с использованием эвристического нейроподобного алгоритма обучения без расчета градиентов. Основная идея эвристического алгоритма заключается в определении степени влияния уровня активации нечеткого правила (нейрона слоя правил) на общий выход ГНК. Полученная информация затем используется для настройки параметров функций принадлежности ГНК. Величина модификации параметров зависит от значения ошибки нечеткого правила Rk, которая рассчитывается следующим образом:

где – ошибка выхода в случае, когда следствием правила Rk является класс Cj, j=1,…,M.

Эвристический алгоритм обучения использует следующую стратегию:

если степень принадлежности объекта данных нечеткому множеству, а следовательно и активация соответствующего правила, должна быть увеличена, то носитель нечеткого множества расширяется и смещается таким образом, что ядро нечеткого множества сдвигается по направлению к текущему входному значению; если же степень принадлежности должна быть уменьшена, осуществляется обратное преобразование: носитель сжимается и смещается в направлении, обратном текущему значению признака (рисунок 3).

Для того чтобы гарантировать приемлемую степень интерпретируемости нечетких множеств, обучающий алгоритм принимает во внимание следующие ограничения: значения параметров должны принадлежать области значений признака, функции принадлежности должны пересекаться, но не совмещаться, быть симметричными и т.д.

Р
Рисунок 3
– Изменение треугольной функции принадлежности предпосылки правила

На втором этапе обучения выполняется адаптация весовых коэффициентов выходного слоя нейросетевого представления ГНК, соответствующих весам нечетких правил. Для этого используется алгоритм, основанный на стратегии поощрения/наказания. Основной идеей алгоритма является увеличение или уменьшение весового коэффициента, соответствующего правилу с наибольшей активацией для входного вектора признаков.

Таким образом, обобщенный алгоритм обучения ГНК позволяет:

  • настраивать параметры не дифференцируемой функции классификации, реализуемой ГНК;

  • учитывать ограничения, накладываемые на изменение параметров функций принадлежности, для удовлетворения семантическим критериям интерпретируемости нечеткой модели.

Далее описывается заключительный этап построения ГНК – этап оптимизации структуры гибридного нечёткого классификатора с целью сокращения количества и упрощения состава нечетких классифицирующих правил. Для осуществления этого этапа используются два альтернативных подхода:

  • эвристические процедуры сокращения количества и упрощения состава нечётких классифицирующих правил;

  • алгоритм многокритериальной оптимизации структуры ГНК.

Для упрощения структуры ГНК предлагаются три эвристические процедуры: удаление избыточных правил; удаление избыточных предпосылок правила; удаление избыточных нечетких множеств. Процедуры применяются итерационно, причем модификация структуры ГНК сохраняется только в том случае, если точность классификации ГНК улучшается или остается без изменений.

Предложенный алгоритм рассматривает задачу упрощения структуры гибридного нечёткого классификатора как задачу многокритериальной оптимизации. Выполнена постановка задачи многокритериальной оптимизации структуры ГНК, согласно которой из множества различных наборов нечетких правил требуется найти набор нечетких правил S, который является решением трехкритериальной задачи оптимизации с критериями Fk(S) (k=1,…,3), определяющими точность классификации и компактность ГНК:

max F1(S), min F2(S), min F3(S),

где F1(S) – количество правильно классифицированных объектов с использованием набора правил S, F2(S) – количество нечетких правил в S, F3(S) – суммарное количество элементов предпосылок в S.

Алгоритм многокритериальной оптимизации структуры ГНК позволяет решить сформулированную выше задачу путем поиска решений, недоминируемых по совокупности нескольких оптимизируемых критериев. Алгоритм разработан на основе генетического алгоритма с модифицированной схемой реализации и адаптирован к решению задачи оптимизации структуры ГНК. Приводится краткое описание шагов реализации предложенного алгоритма, разработанных специальных генетических операций и кодировки решения применительно к решаемой задаче. Нечеткое правило Rk представлено в особи алгоритма как комбинация лингвистических значений (таблица 1), соответствующих нечетким множествам предпосылки правила, закодированных числами (рисунок 4). При кодировании набора правил, для каждого из признаков вводится дополнительное нечеткое множество, соответствующее лингвистическому значению «пустой», которое позволяет не учитывать отдельные признаки в составе предпосылки правила.

Таблица 1 – Кодирование лингвистических значений

нечетких множеств

Лингвистическое значение

Код

малый

0

средне малый

1

средний

2

средне большой

3

большой

4

пустой

-1

Р
исунок
4 – Пример кодированного представления нечеткого правила

Длина отдельных особей может варьироваться, что позволяет вести поиск недоминируемых наборов нечетких правил в многомерном пространстве наборов правил разной длины.

Основным преимуществом использования алгоритма многокритериальной оптимизации структуры ГНК является возможность с использованием генетических операций генерировать несколько недоминируемых наборов нечетких правил. Таким образом, проблема поиска компромисса между степенью точности и интерпретируемостью нечеткого классификатора может решаться конечным пользователем путем отбора наиболее подходящего для конкретной задачи набора нечетких правил классификации.

Далее рассматривается назначение и структура программного комплекса (ПК) «Гибрид», реализующего предложенные алгоритмы построения ГНК. В результате тестирования ГНК на наборе данных по раку груди из международного архива тестов был получен следующий набор нечетких правил:

Правило R1: если x1 (плотность скопления клеток) есть малое и x2 (единообразие размера клетки) есть малое и x6 (голое ядро) есть малое то класс 1 (доброкачественная опухоль).

Правило R2: если x2 (единообразие размера клетки) есть большое то класс 2 (злокачественная опухоль).

Правило R3: если x2 (единообразие размера клетки) есть малое и x6 (голое ядро) есть большое то класс 2 (злокачественная опухоль).

Точность классификации с использованием набора правил составляет 96,48%. Функции принадлежности для признаков x1, x2, x6, в предпосылках данного набора нечетких правил представлены на рисунке 5.

Рисунок 5 – Функции принадлежности признаков x1, x2 и x6

Сравнительный анализ разработанного классификатора с четырьмя наиболее близкими зарубежными методами-аналогами показал его более высокую эффективность в части компактности и интерпретируемости при сохранении высокой точности классификации. Были получены положительные результаты при проверке эффективности ГНК на реальных данных из области лейкозологии. В заключении сформулированы основные полученные результаты. Приложения содержат описание работы с ПК «Гибрид» и акты внедрения результатов диссертации.

ЗАКЛЮЧЕНИЕ

Основные научные результаты диссертации

  1. Предложена обобщенная схема и сформулированы основные четыре этапа построения гибридного нечеткого классификатора (ГНК) для анализа медицинских данных, реализуемые посредством последовательного применения комплекса разработанных алгоритмов.

  2. Предложен подход к отбору информативных признаков для задач классификации с использованием генетического алгоритма. Согласно предложенному подходу, отбор признаков рассматривается как задача многокритериальной оптимизации с двумя критериями: точность классификации и количество признаков [2, 22]. Отличительной особенностью предложенного подхода является возможность получения нескольких недоминируемых подмножеств признаков с различными соотношениями между отдельными критериями оптимизации. Конечному пользователю предоставляется возможность выбора единственного подмножества признаков согласно его знаниям и представлениям о решаемой задаче.

  3. Предложен способ нечеткой кластеризации [12], отличительной особенностью которого является возможность найти не только оптимальное разбиение набора данных на кластеры, но и определить их количество, которое соответствует минимуму показателя качества разбиения. На базе способа нечеткой кластеризации предложен алгоритм построения начальной структуры ГНК [20, 21]. Отличительной особенностью алгоритма является одновременное определение нечетких множеств и нечетких классифицирующих правил на основе обучающего набора данных.

  4. Предложен структурно-ориентированный алгоритм инициализации базы правил гибридного нечеткого классификатора, который позволяет автоматически определять его начальную структуру, и включает последовательное выполнения трех процедур: создание набора нечетких предпосылок правил, определение следствий и весов для созданных предпосылок нечетких правил и формирование окончательного набора начальных правил с учетом коэффициентов эффективности [6, 8]. Отличительной особенностью алгоритма является возможность создания нечетких правил ГНК на основе обучающих данных, что позволяет уже на начальном этапе построить более компактную и ориентированную на имеющиеся данные структуру ГНК.

  5. Разработан обобщенный алгоритм обучения ГНК. Согласно предложенному алгоритму, обучение ГНК осуществляется в два этапа. На первом этапе настраиваются параметры функций принадлежности, а на втором этапе – веса нечетких правил. Отличительной особенностью алгоритма является возможность его применения при наличии не дифференцируемых функций активации нейросетевой архитектуры ГНК, а также использование ограничений в процессе обучения, гарантирующих сохранение семантической интерпретируемости нечеткого классификатора [6, 8].

  6. Разработан алгоритм многокритериальной оптимизации структуры ГНК [9]. Отличительной особенностью данного алгоритма является использование генетических операций, позволяющих получить несколько наборов нечетких правил, которые являются недоминируемыми по трем критериям: точность классификации, количество нечетких правил и общая длина нечетких правил. Выбор окончательного набора нечетких классифицирующих правил зависит от предпочтений эксперта и целей применения ГНК.

  7. Предложен гибридный нечеткий классификатор для анализа медицинских данных, позволяющий решать задачи классификации пациентов, характеризующихся набором значений различных клинических и лабораторных показателей. Отличительными особенностями ГНК является его компактность и интерпретируемость, при сохранении достаточно высокой точности классификации.

Рекомендации по практическому использованию результатов

Разработанные алгоритмы построения ГНК для анализа медицинских данных в виде ПК «Гибрид» внедрены в:

  • Республиканском научно-практическом центре детской онкологии и гематологии (РНПЦ ДОГ) Министерства здравоохранения Республики Беларусь (МЗ РБ) и используются для решения задач уточнения стратификации групп риска и прогнозирования исхода терапии острых детских лейкозов;

  • Республиканском научно-практическом центре гематологии и трансфузиологии (РНПЦ ГТ) МЗ РБ и предназначены для использования при проведении исследований в области гематологии.

Применение ГНК в практической лейкозологии и в области гематологии позволит медикам-экспертам принимать более обоснованные решения, способствующие как улучшению качества жизни пациентов после терапии, так и более рациональному расходованию средств на лечение (акты о внедрении, см. приложение Б диссертации).

Разработанный гибридный нечеткий классификатор рекомендуется для использования в автоматизированных системах извлечения знаний из баз данных [3,5,7], а также в специализированных системах поддержки принятия решений при решении классификационных задач в медицине [10,11,13] и в других областях знаний, где необходимым является высокая точность классификации с помощью понятных для пользователя правил.

Список публикаций по теме диссертации

Статьи в журналах

  1. Новоселова, Н.А. Разведочный анализ медицинских данных с использованием самоорганизующихся карт Кохонена / Н.А. Новоселова // Искусственный интеллект. №2. – 2002. C. 526–533.

  2. Новоселова, Н.А. Предварительный отбор информативных признаков для улучшения точности предсказания с помощью нейронной сети / Н.А. Новоселова // Искусственный интеллект. №2. – 2004. C. 150–154.

  3. Том, И.Э. Технология анализа медицинских данных статистическими и нейросетевыми методами / И.Э.Том, О.В. Красько, Н.А. Новоселова, М.П. Потапнев, Т.А. Углова // Искусственный интеллект. №2. – 2004. C. 398–402.

  4. Novoselova, N.A. Uncover the relations between the discretized continuous-valued features with multiple correspondence analysis in medical domain / N.A. Novoselova, I.E. Tom, O.V. Krasko // Annual Proceedings of Medical Science. Vol.50, Suppl. 2. – 2005. P. 40–42.

  5. Tom, I.E. Subsystem of prognostic risk factors analysis of childhood acute leukemias / I.E. Tom, O.V. Krasko, B.A. Zalessky, N.A. Novoselova, A.P. Suchkova, E.E. Sotikova, N.M. Skrygan, M.P. Potapnev, T.A. Uglova // Annual Proceedings of Medical Science. Vol.50, Suppl. 2. – 2005. P. 53–55.

  6. Новоселова, Н.А. Нечеткое нейросетевое моделирование для получения интерпретируемого набора классифицирующих правил / Н.А. Новоселова, И.Э. Том, О.В. Красько // Искусственный интеллект. – 2006. №2. С. 211–214.

  7. Tom, I.E. Experience of the medical-oriented information-analytical system’s development on a basis of the three-tier architecture / I.E. Tom, O.V.  Krasko, N.A. Novoselova, O.I. Bydanov // Искусственный интеллект. №2. – 2006. C. 462–465.

  8. Новоселова, Н.А. Построение нечеткой нейросетевой модели для решения задач классификации / Н.А. Новоселова // Информатика. №3. – 2006. C. 5–14.

  9. Новоселова, Н.А. Построение нечеткой модели классификации с использованием многокритериального генетического алгоритма / Н.А. Новоселова // Искусственный интеллект. №3. – 2006. С.613–622.

  10. Дривотинов, Б.В. Использование нечеткой нейросетевой модели для дифференциальной диагностики подтипов транзиторных ишемических атак / Б.В. Дривотинов, А.С. Мастыкин, Е.Н. Апанель, Н.А. Новоселова // Медицинский журнал. №2. – 2007. – С.102–105.

  11. Пустовойтенко, В.Т. Нейросетевое моделирование в решении классификационных задач ортопедии и травматологии с использованием индекса массы тела / В.Т. Пустовойтенко, А.С. Мастыкин, Н.А. Новоселова // Военная медицина. № 2. 2007. С. 108–110.

  12. Novoselova, N. Supervised fuzzy clustering using genetic algorithm for the fuzzy classifier construction / N. Novoselova // Искусственный интеллект. №4. – 2007. С. 343–351.

  13. Дривотинов, Б.В. Адаптивная нейро-нечёткая модель для дифференциальной диагностики подтипов транзиторных ишемических атак / Б.В. Дривотинов, Е.Н. Апанель, Н.А. Новоселова, А.С. Мастыкин, А.С. Федулов // Военная медицина. № 4. 2007. С. 101–106.

Материалы конференций и тезисы докладов

  1. Aleinikova, O.V. Selection the medical decision for therapy strategy in childhood leukemia based on computing of clinical and laboratory data / O.V. Aleinikova, M.P. Potapnev, T.A. Uglova, I.A. Tom, O.V. Krasko, N.A. Novoselova, S.V. Petrovich, O.I. Bydanov // Proc. of the 6th Scientific Advisory Committee Seminar on Science and Computing, Moscow, 15-17 September 2003. – Vol.2. Moscow, Russia, 2003. P. 123.

  2. Potapnev, M.P. Architecture of the information system for prognostic factors analysis in childhood oncohematology / M.P. Potapnev , I.A. Tom, O.V. Krasko, T.A. Uglova, N.A. Novoselova, S.V. Petrovich, O.I. Bydanov, O.V Aleinikova // Proc. of the 6th Scientific Advisory Committee Seminar on Science and Computing, Moscow, 15-17 September 2003. – Vol.2. Moscow, Russia, 2003. P. 372–376.

  3. Новоселова, Н.А. Компьютерная подсистема для статистического и интеллектуального анализа медицинских данных / Н.А. Новоселова, Б.А. Залесский, О.В. Красько, Н.М. Скриган, Е.Е. Сотикова, А.П. Сучкова, И.Э. Том // Доклады 11-ой Всероссийской конференции «Математические методы распознавания образов», Пущино, 16-22 ноября 2003 г. Пущино, Россия, 2003. C.389–392.

  4. Tom, I.E. The information analytical system for support of childhood leukemias treatment / I.E. Tom, O.V. Krasko, B.A. Zalesky, N.A. Novoselova [et al.] // Proc. of the International Conference on Advanced Information and Telemedicine Technologies for Health (AITTH’2005), Minsk, 8-10 November, 2005. – Vol.2. Minsk, Belarus, 2005. P.171–176.

  5. Novoselova, N.A. Interactive decision tree induction algorithm with pre-discretization of continues-valued attributes / N.A. Novoselova, O.V. Krasko, I.E. Tom // Proc. of the International Conference on Advanced Information and Telemedicine Technologies for Health (AITTH’2005), Minsk, 8-10 November, 2005. – Vol.2. Minsk, Belarus, 2005. P. 213–218.

  6. Aleinikova, O.V. Prediction the outcome of induction therapy of childhood acute myeloid leukemia using decision trees model / O.V. Aleinikova, M.P. Potapnev, T.A. Uglova, K. Welte, I.E. Tom, O.V. Krasko, N.A. Novoselova // Proc. of the International Conference on Advanced Information and Telemedicine Technologies for Health (AITTH’2005), Minsk, 8-10 November, 2005. – Vol.2. Minsk, Belarus, 2005. P. 219–222.

  7. Невдах, С.В. Усовершенствованный метод классификации на основе кластерного генетического алгоритма / С.В. Невдах, Н.А. Новоселова, И.Э. Том // Доклады IV-ой Международной дистанционной научно-практической конференции «Информационные Технологии и Кибернетика на Службе Здравоохранения' 2006», Днепропетровск, 15 июля 2006 г. – Днепропетровск, Украина, 2006 – С. 52–57.

  8. Новоселова, Н.А. Построение нечеткого классификатора с использованием метода субтрактивной кластеризации и последующая оптимизация его структуры для повышения интерпретируемости результатов / Н.А. Новоселова // Доклады десятой национальной конференции по искусственному интеллекту с международным участием (КИИ-06), Обнинск, 26-28 сентября 2006 г. Обнинск, Россия, 2006. C. 425–433.

  9. Новоселова, Н.А. Отбор признаков для задач классификации с использованием многокритериального генетического алгоритма / Н.А. Новоселова // Материалы Третьей Международной конференции Информационные системы и технологии (IST’2006), Минск, 1 3 ноября 2006 г. / Белорус. гос. ун-т. Минск, 2006. – С. 198–203.

РЭЗЮМЭ

Навасёлава Наталля Анатолеўна

Алгарытмы пабудовы гібрыднага невыразнага класіфікатара для аналізу медыцынскіх дадзеных

Ключавыя словы: гібрыдны невыразны класіфікатар, інтэлектуальны аналіз дадзеных, класіфікацыя, нейрасеткавая архітэктура, генетычны алгарытм, шматкрытэрыйная аптымізацыя, невыразная кластарызацыя.

Мэтай працы з'яўляецца распрацоўка алгарытмаў пабудовы гібрыднага невыразнага класіфікатара (ГНК) для аналізу дадзеных пацыентаў, якія характарызуюцца наборам значэнняў розных клінічных і лабараторных паказчыкаў.

Прапанаваная абагульненая схема і сфармуляваныя асноўныя чатыры этапу пабудовы гібрыднага невыразнага класіфікатара: прадапрацоўка, пабудова пачатковай структуры, навучанне і аптымізацыя структуры. Прапанаваны падыход да адбору інфарматыўных прыкмет з выкарыстаннем генетычнага алгарытму, паводле якога адбор прыкмет уяўляецца як задача шматкрытэрыйнай аптымізацыі. Рашэннем задачы з'яўляецца некалькі недамінаваных падмностваў прыкмет з рознымі суадносінамі паміж значэннямі дзеляў крытэраў аптымізацыі. Распрацаваны структурна-арыентаваны алгарытм ініцыялізацыі базы правіл ГНК. Алгарытм уключае паслядоўнае выкананні трох працэдур: стварэнне набору перадумоў невыразных правіл, азначэнне следстваў і ваг правіл і фармаванне канчатковага набору правіл з улікам каэфіцыентаў эфектыўнасці.

Распрацаваны абагульнены алгарытм навучання ГНК. Адметнай асаблівасцю алгарытму з'яўляецца магчымасць яго ўжывання пры наяўнасці не дыферэнцаваных функцый актывацыі ГНК, улічваючы абмежаванні, якія гарантуюць захаванне семантычнай інтэрпрэтаванасці.

Прапанаваны алгарытм шматкрытэрыйнай аптымізацыі структуры ГНК. Алгарытм выкарыстае генетычныя аперацыі, якія дазваляюць атрымаць некалькі набораў невыразных правіл, якія з'яўляюцца недамінаванымі па трох крытэрам: дакладнасць класіфікацыі, колькасць невыразных правіл і агульная даўжыня невыразных правіл.

Распрацаваныя алгарытмы пабудовы ГНК дазваляюць атрымаць рашэнне задачы класіфікацыі ў выглядзе кампактнага інтэрпрэтаванага набору невыразных правіл пры захаванні досыць высокай дакладнасці класіфікацыі, што пацвярджаецца праведзенымі эксперыментамі.

Вынікі дысертацыйнай працы ўкаранёныя ў Рэспубліканскім навукова-практычным цэнтры дзіцячай анкалогіі і гематалогіі, і ў Рэспубліканскім навукова-практычным цэнтры гематалогіі і трансфузіалогіі Міністэрствы аховы здароўя Рэспублікі Беларусь.

РЕЗЮМЕ

Новоселова Наталья Анатольевна

Алгоритмы построения гибридного нечеткого классификатора для анализа медицинских данных

Ключевые слова: гибридный нечеткий классификатор, интеллектуальный анализ данных, классификация, нейросетевая архитектура, генетический алгоритм, многокритериальная оптимизация, нечеткая кластеризация.

Целью работы является разработка алгоритмов построения гибридного нечеткого классификатора (ГНК) для анализа данных пациентов, характеризующихся набором значений различных клинических и лабораторных показателей.

Предложена обобщенная схема и сформулированы основные четыре этапа построения гибридного нечеткого классификатора: предобработка, построение начальной структуры, обучение и оптимизация структуры ГНК. Предложен подход к отбору информативных признаков с использованием генетического алгоритма, согласно которому отбор признаков представляется как задача многокритериальной оптимизации. Решением задачи является несколько недоминируемых подмножеств признаков с различными соотношениями между значениями частных критериев оптимизации. Разработан структурно-ориентированный алгоритм инициализации базы правил ГНК. Алгоритм включает выполнения трех процедур: создание набора предпосылок нечетких правил, определение следствий и весов правил и формирование окончательного набора правил с учетом коэффициентов эффективности.

Разработан обобщенный алгоритм обучения ГНК. Отличительной особенностью алгоритма является возможность его применения при наличии не дифференцируемых функций активации ГНК, учитывая ограничения, гарантирующие сохранение семантической интерпретируемости.

Предложен алгоритм многокритериальной оптимизации структуры ГНК. Алгоритм использует генетические операции, позволяющие получить несколько наборов нечетких правил, которые являются недоминируемыми по трем критериям: точность классификации, количество нечетких правил и общая длина нечетких правил.

Разработанные алгоритмы построения ГНК позволяют получить решение задачи классификации в виде компактного интерпретируемого набора нечетких правил.

Результаты диссертационной работы внедрены в Республиканском научно-практическом центре детской онкологии и гематологии, и в Республиканском научно-практическом центре гематологии и трансфузиологии Министерства здравоохранения Республики Беларусь.

SUMMARY

of the dissertation thesis by Natalia N. Novoselova

Algorithms of construction of hybrid fuzzy classifier for medical data analysis

Keywords: hybrid fuzzy classifier, intelligent data analysis, classification, neural network architecture, genetic algorithm, multi-objective optimization, fuzzy clustering.

The research is aimed at developing the algorithms of hybrid fuzzy classifier (HFC) construction for the analysis of patient data, characterized by values of different clinical and laboratory indices.

A generalized scheme of the construction of hybrid fuzzy classifier is proposed and the main four construction stages are formulated, which include preprocessing, structure initialization, parameter tuning and structure optimization stages. An approach to informative feature selection using genetic algorithm is proposed, which regards the feature selection as the multi-objective optimization task and allows with single run of genetic algorithm to obtain several nondominated feature sets with different ratio of particular optimization criteria. A structure-oriented algorithm is developed for initialization of HFC data base. The algorithm includes the successive execution of three procedures: the generation of the set of fuzzy rule antecedents, the definition of fuzzy rule consequence and weights, the producing of final rule set taking into account efficacy coefficient.

A generalized learning algorithm of hybrid fuzzy classifier is developed. The distinctive feature of the algorithm consists in considering the non-differentiable activation functions of HFC neural network architecture, taking into account the semantic interpretability constraints.

An algorithm is proposed for multi-objective optimization of hybrid fuzzy classifier structure. The algorithm makes use of genetic operations, allowing to obtain several fuzzy rule sets, which are nondominated with respect to three objectives: the accuracy of classification, the number of fuzzy rules and the total rule length.

The developed algorithms of hybrid fuzzy classifier (HFC) construction make it possible to obtain the decision of classification task in the form of compact, interpretable set of fuzzy rules, preserving the sufficiently high classification accuracy, which is proved experimentally.

The results of the work have been implemented into practice and used in State scientific-practical center of childhood oncology and hematology, and in State scientific-practical center of hematology and transfusiology of Ministry of Health, Republic of Belarus.