Содержание к диссертации
Введение
Глава 1 Анализ алгоритмов идентификации образов 8
1.1 Понятие образа как многомерного объекта 8
1.2 Общая постановка задачи распознавания образов 10
1.2.1 Проблема обучения распознаванию образов 10
1.2.2 Гипотеза компактности 14
1.3 Современные подходы к проблеме идентификации наблюдений 15
1.3.1 Геометрический и структурный подходы 15
1.3.2 Дискриминантный анализ 19
1.3.3 Кластерный анализ 21
1.3.4 Вероятностный подход 23
1.3.5 Нейросетевой подход 27
1.3.6 Логические и лингвистические методы. Нечеткие системы 29
1.4 Практическое применение систем идентификации в задачах медицинской диагностики 37
1.5 Постановка задач диссертационного исследования 40
Глава 2 Синтез адаптивной модели нечеткой идентификации 42
2.1 Анализ базовых элементов системы нечеткого вывода 42
2.2 Оптимизация параметров лингвистических переменных 49
2.3 Формирование множества правил 62
2.4 Взаимодействие алгоритмов структурной и параметрической адаптации 64
2.5 Выводы 67
Глава 3 Специальное математическое и программное обеспечение анализа эффективности адаптивных систем 68
3.1 Алгоритмизация основных структурных элементов модели 69
3.2 Программная реализация системы анализа многомерных данных 71
3.3 Генерация многомерных тестовых распределений 78
3.4 Критерия качества модели идентификации 80
3.5 Анализ качества идентификации при различных геометрических структурах обучающих множеств 83
3.6 Анализ оптимальности использования различных операторов импликации 95
3.7 Выводы 97
Глава 4 Комплекс программ для решения задач идентификации состояний объектов 98
4.1 Выбор и формализация идентификационных признаков 99
4.2 Постановка задачи диагностики урологических заболеваний 103
4.3 Анализ результатов идентификации состояний пациентов 104
4.4 Структура и организация программного комплекса 108
4.5 Выводы 118
Заключение 118
Библиографический список 121
- Практическое применение систем идентификации в задачах медицинской диагностики
- Взаимодействие алгоритмов структурной и параметрической адаптации
- Анализ качества идентификации при различных геометрических структурах обучающих множеств
- Анализ результатов идентификации состояний пациентов
Введение к работе
Актуальность темы. Активное использование современных информационных технологий для создания математических основ интеллектуальных систем в последние годы позволило по-новому взглянуть на проблему обработки многомерных данных в условиях неполной и неточной информации. Одной из наиболее актуальных задач в этой сфере является задача идентификации объектов - отнесение некоторого объекта, заданного набором параметров, к классу подобных объектов. Классические методы многомерной статистики, используемые в подобных задачах, основаны на определенных предположениях о структуре исходных данных и, как следствие, попытки их применения приводили к высоким процентам ошибок при условии несоответствия обучающих наборов этим предположениям. Наиболее перспективным направлением при решении данной задачи является использование универсальных аппроксиматоров широкого класса многомерных нелинейных функций - адаптивных моделей нечеткого логического вывода. Они представляют собой дальнейшее развитие нечетких экспертных систем, исследованиям которых посвящены работы Л.А. Заде, А. Кофмана, Д.А. Поспелова, А.Н. Борисова, Е.А. Мамдани и др. Основная трудность их использования заключается в структурной и параметрической адаптации - поиске оптимального набора параметров термов лингвистических переменных, структуры множества правил логического вывода. Для ее решения обычно привлекаются эксперты в соответствующих областях знаний. Параметры адаптивной модели нечеткого логического вывода формируются путем их оптимизации в смысле некоторого критерия, формируемого по данным из обучающей выборки. Исследованиям отдельных элементов таких систем посвящены работы В.В. Круглова, А.П. Ротштейна, С.Д. Штовбы, Т. Фукуда и др. Однако в настоящий момент отсутствуют общепризнанные методы
применения адаптивных моделей нечеткого вывода для идентификации многомерных объектов, отсутствуют методы их обучения в рамках этой задачи. Кроме того, несмотря на постоянное совершенствование средств хранения информации и увеличение объемов носителей проблема сжатия множества правил в базе знаний модели по-прежнему является актуальной.
Одним из путей решения перечисленных проблемы является развитие моделей нечеткого вывода, методов структурной и параметрической оптимизации, алгоритмов сжатия базы знаний, оценки эффективности алгоритмических реализаций моделей.
Диссертационная работа выполнена в рамках тематики госбюджетной НИР ГБО1 -04 «Разработка информационно вычислительных систем непромышленного назначения».
Цель и задачи исследования. Целью работы является разработка моделей, численных методов и алгоритмов идентификации многомерных объектов на базе множества нечетких логических правил для повышения эффективности решения задачи идентификации, создание на их основе средств специального математического и программного обеспечения, апробация моделей и методов.
Для достижения поставленных целей необходимо решить следующие задачи:
Провести анализ различных подходов к решению задачи идентификации состояний многомерных объектов.
Разработать модели идентификации многомерных объектов, базирующейся на аппарате нечеткой логики, и методы их структурной и параметрической оптимизации. Разработать методы построения набора правил из экспериментальных данных.
Реализовать на ЭВМ модели идентификации объектов и алгоритмы их оптимизации для применения моделей в прикладных программах.
Провести теоретический анализ эффективности предложенных методов идентификации при различных тестовых выборках, отличающихся начальными условиями и параметрами.
Осуществить практическую апробацию прикладных разработок применительно к задачам медицинской диагностики (идентификация состояния при диагностике урологических заболеваний).
Методы исследования. В ходе исследования использовались методы теории математического моделирования, нечеткая логика и нечеткие множества, теории оптимизации, эволюционного моделирования, системного анализа и принятия решений, математической статистики.
Научная новизна. В работе получены следующие результаты, характеризующиеся научной новизной:
предложена структура нечеткой модели идентификации многомерных объектов отличающаяся возможностью автоматизации процесса формирования базы нечетких логических правил;
разработан комбинированный метод адаптивного построения множества нечетких правил модели, отличающийся использованием информации из обучающих выборок, что позволяет редуцировать множество правил;
разработаны методы кодирования и оптимизации параметров модели на основе генетического аппарата, отличающейся возможностью применения генетических алгоритмов оптимизации без дополнительных ограничений на пределы изменения параметров модели.
Практическая значимость работы. Практическая значимость работы заключается в создании специального программного обеспечения, позволяющего осуществлять анализ моделей идентификации объектов, а также инвариантных программно-алгоритмических модулей для применения моделей идентификации в различных приложениях.
Реализация результатов работы. Теоретические и практические результаты работы реализованы в специальном программном комплексе
исследования многомерных данных и анализа моделей многомерной идентификации, положенный в основу программного обеспечения «Анализ и идентификация многомерных данных», который внедрен в практическую деятельность дорожная поликлиники ЮВЖД (г. Воронеж).
Материалы диссертации, а также разработанное программное обеспечение используются в учебном процессе Воронежского государственного технического университета при обучении студентов специальности 230100 в дисциплинах «Системы искусственного интеллекта» и «Теория принятия решений»
Апробация работы. Основные положения диссертации докладывались и обсуждались на Международной открытой научной конференции «Математические методы в технике и технологиях - ММТТ-17», (Кострома, 2004), международной научно-технической конференции и Российской научной школе молодых ученых и специалистов "Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий" (Сочи, 2002), V-VUI Республиканских научных конференциях "Современные проблемы информатизации" (Воронеж, 2000-2003), а также на научных семинарах кафедры ABC ВГТУ (Воронеж, 2001-2004).
Публикации. По результатам исследований опубликовано 14 печатных работ, в том числе 8 без соавторов. В работах, опубликованных в соавторстве и приведенных в конце диссертации, лично соискателем предложены: в основные принципы использования нечетких моделей для дискретной идентификации многомерных наблюдений, методы построения базы знаний на основе экспертной информации, в методы редукции множества правил нечеткого вывода.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, двух приложений, изложена на 124 листах машинописного текста, содержит список литературы из 110 наименований, 45 рисунков, 14 таблиц.
Практическое применение систем идентификации в задачах медицинской диагностики
Задачи медицинской диагностики относятся к проблемам классификации образов [1, 17]. Решение такой задачи заключается в указании класса или выбора одного из нескольких вариантов. К числу задач данного типа относятся задачи распознавания и анализа медицинских образов, постановки медицинского диагноза, т.е. отнесение к той или иной известной нозологической форме заболевания, характеризующегося набором симптомов, задача медицинского прогноза, т.е. предсказание вероятности того или иного исхода заболевания (развития осложнения и т.п.), экспертная оценка качества проводимого лечения.
К числу медицинских образов относятся данные таких инструментальных исследований, как электрокардиография, электроэнцефалография, реография, визуализационные методики эхография, доплерография, рентгенография, компьютерная томография, а также патоморфологическое исследование тканей и клеток на основе световой и электронной микроскопии [4]. Применение автоматизированных систем распознавания образов может быть эффективно в тех случаях, когда приходится обрабатывать большие объемы архивной или поступающей в реальном времени информации, например, при анализе многочасовой записи ЭКГ, при мониторировании ЭКГ в реальном времени, а также в случаях, когда производится профилактический осмотр большого количества пациентов. Специфика данной задачи в области медицины близка к постановке задачи в других областях [56].
Для задачи медицинской диагностики в той или иной мере использовались все перечисленные ранее методы. К сожалению, медицина по историческим и объективным причинам характеризуется плохой формализацией знаний, что затрудняет применение базирующихся на логике экспертных систем. Классические статистические методы строят линейные разделяющие поверхности, что во многих случаях недостаточно для успешной идентификации. Байесовкий классификатор способен строить нелинейную разделяющую поверхность второго порядка. К сожалению, баесовский метод теоретически обоснован только для данных с нормальным законом распределения и требует задания априорных вероятностей, что не всегда удается выполнить корректно.
Являясь универсальными аппроксиматорами [47], нечеткие адаптивные системы логического вывода лишены перечисленных недостатков. Они представляются наиболее перспективными в задачах медицинской диагностики.
В литературе описано множество примеров применения систем, основанных на логических правилах, относящихся к различным разделам медицины [68], в частности диагностика раковых заболеваний, прогнозирование сердечной недостаточности у больных с пороками сердца, идентификация сердечных ритмов и т.д.
Важной подзадачей медицинской диагностики является проблема определения диагностической значимости отдельных признаков. На сегодняшний день в теории нечетких адаптивных систем не существует строго обоснованных аналитических методов выделения наиболее значимых признаков. Для этих целей применялся статистический и экспертный подходы. Рассмотрим более подробно технологию разработки адаптивного нечеткого классификатора на примере системы диагностики заболеваний предстательной железы [37].
В процессе анализа задачи были выбраны четыре вида состояний, на которые можно разделить больных с нарушениями предстательной железы - периодическое наблюдение, хронический простатит, ДГПЖ (доброкачественная гиперплазия предстательной железы) с рекомендациями на оперативное лечение и ДГПЖ с рекомендациями на консервативное лечение. При постановке задачи необходимо было обеспечить классификацию состояния пациента по этой шкале.
Обучающие параметры представляли собой ранговые и числовые признаки, характеризующие данные обследования больного. Обучающая выборка составляла 91 человек. Для идентификации состояний пациентов были созданы и проанализированы различные адаптивные системы идентификации, различающиеся параметрами правил и функций принадлежности термов. Результат практического использования экспертов на данной задаче показал вполне приемлемые результаты диагностики состояний.
Таким образом, адаптивные нечеткие системы логического вывода могут достаточно эффективно применяться в задачах медицинской диагностики как в качестве виртуального эксперта, так и в научных целях для определения эффективности методики диагностики. К числу недостатков можно отнести необходимость разработки эффективных методов оптимизации большого числа параметров модели, что делает эту задачу особенно актуальной.
Взаимодействие алгоритмов структурной и параметрической адаптации
Обсуждение вопроса о влиянии метода создания родительских пар экземпляров Sj на поведение генетического алгоритма невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Использование вещественных значений в элементах хромосом для описания экземпляров Sj систем распознавания образов накладывает ряд ограничений на применяемые методы отбора экземпляров для применение генетических операторов. В частности, распространенный метод отбора с замещением [94, 99, 104, 105] не может быть применен именно в силу вещественности параметров - процедура сравнения и поиска одинаковых экземпляров вырождается в процедуру оценки их сходства. Поэтому за основу механизма отбора были взяты для сравнения два вероятностных оператора пропорциональной и турнирной селекции.
В пропорциональном алгоритме отбора сначала подсчитывается присособленность каждого экземпляра fj. После этого находят среднюю приспособленность в популяции fcp как среднее арифметическое значений приспособленности всех особей. Затем для каждой особи вычисляется отношение —-. Если это отношение больше 1, то экземпляр считается хорошо приспособленной и допускается к скрещиванию, в противном случае экземпляр исключается из популяции. Например, если дробь равна 3.23, то данная особь имеет тройной шанс на скрещивание и будет иметь вероятность равную 0.23 четвертого скрещивания. Если же приспособленность равна 0.48, то особь примет участие в единственном скрещивании с вероятностью 0.68.
При турнирной селекции формируется случайное подмножество из элементов популяции и среди них выбирается один элемент с наибольшим значением целевой функции. Турнирный алгоритм отбора может быть описан следующим образом: из популяции, содержащей N строк, выбирается случайным образом t строк и лучшая строка записывается в промежуточный массив (между выбранными строками проводится турнир). Эта операция повторяется N раз. Строки в полученном промежуточном массиве затем используются для скрещивания (также случайным образом). Размер группы строк, отбираемых для турнира часто равен 2. В этом случае говорят о двоичном/парном турнире (binary tournament). Вообще же t называется численностью трунира (tournament size).
Турнирная селекция имеет определенные преимущества перед пропорциональной, так как не теряет своей избирательности, когда в ходе эволюции все элементы популяции становятся примерно равными по значению целевой функции. Операторы селекции строятся таким образом, чтобы с ненулевой вероятностью любой элемент популяции мог бы быть выбран в качестве одного из родителей. Более того, допускается ситуация, когда оба родителя представлены одним и тем же элементом популяции.
Этот метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. Использование «элитизма» позволяет не потерять хорошее промежуточное решение и предоставляет алгоритму возможность анализировать разные строки из пространства поиска.
В литературе, посвященной генетическим алгоритмам, например в [3], элитному отбору отводят место как достаточно слабому с точки зрения эффективности поиска. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Однако, быстрая сходимость, обеспечиваемая элитным отбором, может быть с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом.
Теперь рассмотрим вопрос относительно выбора родительских экземпляров для дальнейшего скрещивания. Первый подход самый простой - это случайный выбор родительской пары ("панмиксия"), когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции. Второй способ выбора особей в родительскую пару - так называемый селективный. Его суть состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставиться задача определения нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений. Кроме того, для некоторого класса задач со сложным ландшафтом приспособленности быстрая сходимость может превратиться в преждевременную сходимость к квазиоптимальному решению. Этот недостаток может быть отчасти компенсирован использованием подходящего механизма отбора, который бы "тормозил" слишком быструю сходимость алгоритма.
Другие два способа формирования родительской пары, на которые хотелось бы обратить внимание, это инбридинг и аутбридинг. Оба эти метода построены на формировании пары на основе близкого и дальнего "родства" соответственно. Под "родством" здесь понимается расстояние между членами популяции как в смысле геометрического расстояния особей в пространстве параметров (для фенотипов), так и в смысле хэмминингого расстояния между хромосомными наборами особей (для генотипов). В связи с этим будем различать генотипный и фенотипный (или географический) инбридинг и аутбридинг.
Анализ качества идентификации при различных геометрических структурах обучающих множеств
В своей работе исследователь использует огромное количество информации, и далеко не вся она имеет числовую природу. Характерной особенностью, например, медицинской информации является ее разнотипность по представлению и описанию. Такая разнородность представления значительно затрудняет разработку алгоритмов принятия решения в автоматизированных системах. Особые трудности возникают при одновременном использовании количественной и качественной информации [44].
Все управленческие решения, принимаемые в ходе медицинского технологического процесса, основываются на анализе данных, получаемых при исследовании пациента различными методами. Обычно эти методы, а также информацию, получаемую с их помощью, подразделяют на три группы: - информация, получаемая врачом при опросе больного. - информация, полученная при непосредственном обследовании больного (объективное или физикальное исследование). - информация, полученная с помощью специальных медицинских инструментов (инструментальные исследования) и методы исследования различных субстратов, получаемых от больного (лабораторные исследования). Количественные, или числовые, показатели замеряются в определенной шкале или в шкале интервалов. В процессе обследования и диагностики могут замеряться показатели, имеющие различную физическую природу, следовательно их величины буду представляться в различных физических единицах. Поэтому в ряде случаем может быть использовано приведение всех количественных данных к единой шкале. Как вариант может быть использована шкала [0,1], при этом новое значение вычисляется в соответствии с принципом принципу «предпочтительно иметь большее значение величины» по формуле 2.1 [50]. Следует отметить, что подобные преобразования не влияют на результат идентификации, так как не меняют ни взаимного расположения классов, ни их форму. Однако результаты вычислений будут представляться в единой унифицированной шкале.
Качественные признаки могут быть представлены в виде ранговых (балльных) или классификационных показателей. Ранговые используются для выражения терминов и понятий предметной области, не имеющих цифровых значений (например: тяжесть состояния, яркость окраски, оценка состояния и т.д.), и замеряются в шкале порядка. Классификационные (или номинальные) показатели замеряются в шкале наименований (например, возраст, пол, группа крови).
Для того чтобы при диагностике стало возможным использование математического аппарата, необходимо провести формализацию полученных данных, которая заключается в кодировании информации, когда каждому значению отдельного показателя ставится в соответствие определенное кодовое число. При кодировании обязательно сохраняется медицинская информация, то есть семантическая сила и смысл данных не искажаются [65].
При кодировании количественной информации область изменения каждого показателя разбивается на несколько интервалов с учетом требуемой степени детализации описания. Ранговые показатели разделяются на градации в соответствии с изменением их выраженности, а классификационные кодируются произвольно. Таким путем осуществляется построение классификационно-квантифицированных шкал, то есть процедура идентификации и установления физических границ изучаемых показателей.
Задачу формализации идентификационной информации, получаемой на различных этапах диагностического поиска, можно считать решенной, когда для описания каждого рассматриваемого показателя предусмотрена возможная область его значений, а само описание таково, что обусловливает его однозначную интерпретацию.
Как уже было сказано, задача выбора классификационных признаков — одна из первых и самых главных при построении системы диагностики. От выбранных признаков и их количества будет зависеть качество и достоверность распознавания.
Совокупность признаков должна в наибольшей степени отражать те свойства объектов, которые важны для их распознавания [1, 65]. При этом от размерности признакового пространства в значительной степени зависит вычислительная сложность процедур обучения и принятия решения, достоверность распознавания. Уменьшение количества признаков снижает затраты на произведение измерений и вычислений, но может привести к падению достоверности распознавания. Из этого следует, что, с практической точки зрения, требования минимума общей размерности задачи распознавания и максимума достоверности оказываются противоречивыми.
Любая предметная область, содержит достаточно большое количество параметров, однако далеко не все их них реально используются в вычислениях. Первоначальный набор признаков формируется до начала распознавания из числа доступных измерению характеристик объекта, отражающих его наиболее существенные для распознавания свойства [57]. Далее из первоначального набора пытаются сформировать новый набор характеристик, состоящий из меньшего числа переменных. Традиционный способ формирования новых признаков в условиях априорного знания основан на максимизации критерия, характеризующего некоторое расстояние между классами в признаковом пространстве. Данный критерий исходит из того, что значение указанного расстояния пропорционально достоверности распознавания. Чем больше расстояние между классами в признаковом пространстве, тем больше различие между классами, тем легче его обнаружить и тем выше будет достоверность различения классов. Максимизация расстояния между классами повышает разделяющую силу признаков.
Анализ результатов идентификации состояний пациентов
Результатом является автоматизации процесса диагностики урологических заболеваний. Предполагается системы предполагается для периодического профилактического осмотра, диагностики и обработки статистической диагностической информации. Основные требования, предъявляемые к программе: - система должна обеспечивать решение задачи медицинской диагностики, то есть результатом работы системы становится вывод о наличии заболевания у пациента, сделанный по исследуемым данным; - создание удобного интерфейса пользователя, обеспечивающего диалог врача с системой и предусматривающего систему меню и подсказок на каждом этапе диагностического процесса - накопление информации, полученной от пользователя - ведение баз данных и знаний в предметной области и работа с ними - конечные результаты должны быть представлены в виде, допускающем их однозначную интерпретацию в рамках данной области медицины - использование алгоритмов статистической обработки данных, позволяющих повысить точность и эффективность работы всей системы В соответствии с предъявляемыми требованиями в ходе разработки программы преследовалась цель: обеспечение удобства работы с программой пользователя, обладающего малым объемом знаний и навыков в использовании компьютерной техники, а также достижение высокого быстродействия и эффективности программы. Минимальная конфигурация ЭВМ, необходимая для работы программы: - процессор - Intel Pentium 200 и выше; - видеосистема - SVGA 512k video memory; - клавиатура, мышь; - операционная система - Windows 95 OSR2/NТ72000; - свободный объем на жестком диске - не менее 2Мб (без учета объема базы) Программа написана на языке C++ с использованием средства визуального проектирования Microsoft Visual C++ v6.0. Выбор этих средств обусловлен следующими факторами: - язык C++ на сегодняшний день является одним из самых популярных, гибких и удобных языков, с хорошо продуманным синтаксисом и богатыми возможностями; - существует достаточно большое количество свободно распространяемых компонент, предназначенных для использования в среде Visual C++, которые могут составить сильную конкуренцию визуальным средствам проектирования таких сред как C++ Builder или Delphi, в которых реализована концепция RAD (Rapid Application Development - быстрое создание приложений); - используемая средой Visual C++ библиотека объектных компонентов MFS (Microsoft Foundation Class library) предоставляет полный контроль над всеми программными компонентами библиотеки и системных ресурсов. Библиотека MFS и, следовательно, разработанное программное средство, реализуют объектно-ориентированный подход в программировании. С позиции ООП все элементы управления интерфейсом программы представляют собой объекты с определенными свойствами и методами управления. Основой интерфейса программы являются формы. Иерархия форм программы «Анализ и идентификация состояний пациентов» представлена на рисунке 4.4. Все математические алгоритмы реализованы в виде отдельных процедур и расположены в отдельном модуле. Более подробно модульная структура программы и реализация математических алгоритмов будет приведена ниже. Основные алгоритмические модули программы приведены на рисунке 4.5. К ним относятся: - обучающие выборки и группы наблюдения - таблицы базы данных формата Paradox 7.0; - подсистема взаимодействия и доступа к БД - совокупность драйверов БД, алгоритмических средств доступа к ним; - блок вычислений, объединяющий в себе нечеткую адаптивную модели идентификации и подсистему принятия решений; - блок обучения и оптимизации параметров - эволюционный алгоритм используемый для адаптации системы на этапе обучения; - подсистема интерфейса пользователя - набор визуальных компонент и функций формирования информации для них, включает в себя также блок тестирования, в котором находятся список вопросов и ответов для тестирования пациентов по опросникам I-PSS, Мадсена и Боярского.
