Применение теории распознавания в медицинской диагностике

Работа сдана на 5. В дипломе собрана качественная и оргинальная теория по распознаванию. Реализована база данных с пациентами и анамнезом в Delphi и написаны 3 программы осуществляющие распознавание пациентов с заболеванием сердца. Работа писалась на протяжении 3 лет (курсовые работы и практика).
В данной работе проводится разработка программного комплекса «Применение теории распознавания в медицинской диагностике», включаю¬щего в себя алгоритм «Кора», а также алгоритм ближайшего соседа.
В качестве вспомогательного инструмента была создана база данных с информацией о пациентах и заболеваниях. Она может быть использована в целях удобства хранения данных и экономии времени при определения класса заболевания.
...

ВВЕДЕНИЕ
1 Задача классификации
1.1 Основная цель классификации
1.2 Основная задача классификации
1.3 Меры близости
1.4 Математическая постановка задачи классификации
1.5 Постановка диагноза как классификационная задача
1.6 Математические методы, используемые при постановке
диагнза
1.6.1 Классификация посредством задания границ
разделения
1.6.2 Примеры применения принципа разделения для диагностики заболеваний
2 Алгоритмы классификации
2.1 Алгоритм «Кора»
2.2 Суть алгоритма
2.3 Отказ от классификации
2.4 Основная теория
2.4 Достоинства и недостатки алгоритма «Кора»
2.5 Метод ближайшего соседа или метод одиночной связи
2.5.1Классификация заданного множества объектов методом ближайшего соседа
2.5.2 Простое невзвешенное голосование
3 Создание пакета прикладных программ для диагностики заболеваний сердца
3.1 Проектирование базы данных «Пациенты»
3.1.1 Создание информационной системы
3.1.2 Терминология, используемая при проектировании баз
данных
3.1.3 Логическое проектирование
3.1.4 Пример проектирования простейшей информационной
системы
3.1.5 Создание автоматизированных рабочих мест
3.1.6 О генерации уникальных первичных ключей
3.2 Реализация алгоритма «Кора»
3.3 Реализация метода ближайших соседей.
3.4 Оценка работы алгоритмов

ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Большое число красивых скриншотов базы данных и результатов работы программ
Из всех существующих методов функциональной диагностики в на-стоящее время наиболее широкое развитие получают методы, позволяющие оценивать состояние сердечнососудистой системы человека, в связи с тем, что в значительной степени увеличилось количество летальных исходов из-за инфарктов. Это обусловлено усложнением технических систем, используе¬мых в процессе производства, а также использования их в быту, в состав ко¬торых входит человек как неотъемлемый элемент.
Цель работы заключается в разработке пакета программ для диагно-стики двух заболеваний сердца: коронарная болезнь сердца и болезнь сер-дечных клапанов.
В ходе работы передо мной были поставлены следующие задачи:
1) постановка задачи медицинской диагностики как задачи распознава¬ния;
2) создание базы данных;
3) изучение и реализация алгоритмов распознавания.
На практике были собранны данные по двум заболеваниям сердечно-сосудистой сисетмы. На основе данных создана реальная база с большим ко¬личеством пациентов и симптомов. Создана удобная форма для поиска, уда¬ления и доступа к информации. Обращение к данным производится по иден¬тификатору ФИО. Поля можно заполнять как в форме, так и в основной таб¬лице. Так же были реализованы два алгоритма распознавания заболеваний сердца.

Связь - это логическое отношение между сущностями, выражающее некоторое ограничение или бизнес-правило. Связь обычно именуется глаголом. Связи обладают свойством, называемым кардинальностью. Например: «Пациент может иметь 1 или много заболеваний» (связь типа «1 или много»). 3.1.3 Логическое проектированиеПри логическом проектировании нередко также создаются связи "многие ко многим". Типичный пример такой связи - связь врач-пациент, когда любой пациент может лечиться у любого врача. В случае такой связи в общем случае невозможно определить, какой экземпляр одной сущности соответствует выбранному экземпляру другой сущности, что делает неосуществимой физическую (на уровне индексов и триггеров) реализацию такой связи между соответствующими таблицами. Поэтому перед переходом к физической модели все связи "многие ко многим" должны быть переопределены (некоторые CASE-средства, если таковые используются при проектировании данных, делают это автоматически). Обычно для этой цели вводится промежуточная сущность, обладающая ассоциативными атрибутами. В нашем примере объектом, представляющим собой экземпляр подобной сущности, может являться занесение нового анамнеза в базу или посещение пациентом врача (то есть реальное событие). Говоря о связях, нельзя не остановиться на понятии ключей и ключевых атрибутов. Первичным ключом называется атрибут или группа атрибутов, однозначно идентифицирующих каждый экземпляр сущности. Нередко возможны несколько вариантов выбора первичного ключа. В базе данных «Пациенты» первичными ключами сущности "пациент" могут быть как номер медицинской карты, так и комбинация фамилии, имени и отчества (при уверенности, что в базе нет полных тезок), либо номер и серия паспорта (если паспорта есть у всех пациентов). В таких случаях при выборе первичного ключа предпочтение отдается наиболее простым ключам (в данном примере – номеру медицинской карты). Другие кандидаты на роль первичного ключа называются альтернативными ключами. Отметим, что обязательным требованием, предъявляемым к первичному ключу, является его уникальность, два экземпляра сущности не должны иметь одинаковых значений первичного ключа. Другим важным требованием является компактность, сложный первичный ключ не должен содержать ни одного атрибута, удаление которого не приводило бы к утрате уникальности. Помимо этого, первичный ключ не должен содержать пустых значений. При выборе первичного ключа рекомендуется выбирать атрибут, значение которого не меняется в течение всего времени существования экземпляра (в этом случае табельный номер предпочтительнее фамилии, так как ее можно сменить, вступив в брак). При создании связей между сущностями (например, "один ко многим") в дочернюю сущность передаются атрибуты, составляющие первичный ключ в родительской сущности. Эти атрибуты образуют в дочерней сущности внешний ключ. 3.1.4 Пример проектирования информационной системыРассмотрим в качестве примера проектирование и создание информационной системы для ввода данных для пациентов больных сердечно-сосудистыми заболеваниями.Данный пример носит исключительно учебный характер и ни в коем случае не претендует на роль образцовой информационной системы для данной предметной области - в реальной информационной системе подобного назначения число таблиц и набор полей таблиц должно быть существенно большим, да и автоматизированные системы выглядят несколько по-другому. Целью данной информационной системы является хранение данных об анамнезе пациентов с целью дальнейшей статистической обработки. Основная форма по работе с данными представлена на рисунке 4. Итак, центральной сущностью будущей модели данных является занесение новых данных в базу или посещение врача пациентом.Рисунок 4 - Примерное содержание статистического талона В исходной сущности помимо атрибутов, идентифицирующих заболевание и пациента (которые, следовательно, могут повторяться) присутствуют атрибуты, характеризующие конкретный экземпляр данной сущности - дата рождения, давление, возраст (первичное или повторное это посещение), диагноз.При проектировании данных желательно создать также уникальный первичный ключ (номер талона или номер медицинской карты). Это более удобно, чем использование комбинации первичных ключей сущностей «Заболевание» и «Пациент».Учитывая возможную повторяемость значений атрибутов, характеризующих диагноз, создадим соответствующие дополнительные сущности, выполняющие роль справочников (вспомним о том, что модель данных должна удовлетворять первой нормальной форме). Рассмотрим сущность «Пациент», которую характеризуют 30 атрибутов. Итак, была создана логическая модель данных. До этого момента можно было думать о предметной области, не вдаваясь в подробности физической реализации разрабатываемой модели. Теперь нужно продумать выбор СУБД, создание таблиц, соответствующих созданным сущностям, типах полей для хранения атрибутов, а также о создании других объектов базы данных, предназначенных для облегчения поиска в таблицах, контроля ссылочной целостности данных, обработки данных, таких, как индексы, триггеры, хранимые процедуры. Использование серверной СУБД значительно облегчает разработку информационных систем по сравнению с использованием плоских таблиц типа dBase или Paradox. В последнем случае реализация правил ссылочной целостности, Для создания физической модели выберем соответствующую платформу в используемом CASE-средстве и опишем характеристики таблиц, соответствующих описанным в логической модели сущностям, и содержащихся в них полей, соответствующих их атрибутам, как показано на рисунке 5. Далее описаны свойства связей между таблицами, в частности, реакцию сервера на попытки нарушения ссылочной целостности желании можно также отредактировать тексты сообщений триггеров сервера, передаваемых со стороны клиентского приложения (рисунок 6). Рисунок 5 - Физическая модель данных Рисунок 6 - Описание реакции сервера на попытки нарушения ссылочной целостности данныхПосле этого можно создать на сервере схему базы данных, либо сгенерировать DDL-сценарий создания базы данных, представляющий собой набор предложений на процедурном расширении языка SQL данной серверной СУБД) с целью его последующего выполнения.Рисунок 7 - Созданные на сервере объекты базы данныхВ результате выполнения DDL-сценария на сервере должны быть созданы пустые таблицы, а также иные объекты базы данных, которые можно просмотреть с помощью утилиты Database Explorer (рисунок 7) 3.1.5 Создание карты пациентовСгенерировав базу данных с учетом правил ссылочной целостности в соответствии со схемой данных, представленной на рисунке 8, мы, конечно, можем быть уверены, что ввести в базу данных некорректные значения полей DOCT_ID, DIAG_ID, STAT_ID, PURP_ID, PAT_ID сервер пользователю не даст.Однако это вовсе не означает, что можно поместить на форму набор компонентов TDBEdit для ввода данных в эти поля. Такая реализация интерфейса приведет к совершенно неприемлемым условиям труда пользователя, вводящего данные - он должен помнить наизусть все табельные номера, номера карт и коды во вспомогательных таблицах и в случае ошибок сталкиваться с сообщениями, сгенерированными триггерами сервера.Рисунок 8 – Интерфейс заполнения карточки пациентаРазумно использовать выбор нужного значения из списка, поэтому для ввода данных в эти поля поместим на форму компоненты TDBLookupCombBox и выберем в качестве значения ListSource источники данных, связанные с соответствующими словарными таблицами, в качестве значения КеуField - имена их первичных ключей.Такая реализация заполнения полей, разумеется, не является идеальной. Если список действительно невелик, и выпадающий список здесь вполне уместен, то список пациентов, скорее всего, будет составлять не меньше сотни строк. Поэтому вполне уместно либо иметь этот список в отсортированном по алфавиту виде (например, создав соответствующий индекс в базе данных, либо используя в качестве источника данных компонент TQuery с соответствующим предложением Order by). В этом случае при наборе начала фамилии пациента указатель в списке автоматически установится на ближайшую подходящую позицию. Примерно так же можно поступить и со списком диагнозов. Возможен также ввод каких-либо признаков (например, тип заболевания) и дальнейший выбор диагноза из отфильтрованного списка, причем такая фильтрация записей может быть реализована как с помощью параметризованного запроса, выполняемого на сервере, так и с помощью локального фильтра в клиентском приложении. Отметим также, что в списке пациентов могут быть полные тезки. В этом случае следует создать в списке пациентов вычисляемое поле (например, включающее фамилию, имя , отчество и дату рождения пациента) и использовать его для поиска. 3.1.6 О генерации уникальных первичных ключейЕще одним серьезным недостатком подобной информационной системы является необходимость ввода пользователем значений первичных ключей, что в данном примере особенно критично для списка пациентов и списка посещений. В этом случае весьма высока возможность ошибки, связанной с вводом значения, уже имеющегося в базе данных.Проблема подобного рода может быть решена с помощью генерации уникальных первичных ключей. В приложении генерация первичного ключа осуществляется, например, путем создания длинной случайной символьной строки с помощью какого-либо генератора, использующего в качестве параметров время с точностью до долей секунды и какие-либо уникальные характеристики рабочей станции так, чтобы вероятность повторов была чрезвычайно мала. Этот способ обычно используется с теми СУБД, которые сами не поддерживают возможность генерации таких ключей (например, dBase). Он неудобен, так как при наличии нескольких различных приложений, использующих одну и ту же базу данных, требуется в каждом из них повторить код, отвечающий за генерацию первичных ключей. В качестве примера рассмотренно, как можно использовать возможности генерации первичных ключей, предоставляемые Oracle, для автоматического заполнения поля TAG таблицы VISIT. С этой целью воспользуемся генератором последовательностей Oracle, создающим последовательности уникальных целых чисел, используемых клиентскими приложениями в качестве значений первичных ключей. Создадим такую последовательность с помощью следующего набора операторов (исполнить их можно с помощью SQL Plus или с помощью утилиты Database Explorer)На главной форме приложения заменим компонент TDBEdit, в который ранее вводилось значение поля TAG, компонентом TDBText, чтобы исключить возможность ввода этого значения пользователем. В модуль данных нашего клиентского приложения поместим компонент TUpdateSQL, выберем его имя в качестве значения свойства UpdateObject компонента TTable, с помощью которого вводятся данные в таблицу VISIT, сгенерируем операторы SQL для вставки, удаления и модификации записи и изменим оператор SQL для вставки.Триггер можно создать, например, с помощью утилиты SQL Plus, и с помощью SQL Explorer можно просматривать его текст (рисунок 9): Рисунок 9 - Просмотр текста созданного триггера с помощью SQL ExplorerИтак, в результате мы имеем базу данных, содержащую четыре таблицы и ряд других объектов для реализации правил ссылочной целостности. Отметим, что, несмотря на наличие некоторых недостатков, такая реализация информационной системы является гораздо более эффективной, чем реализация в виде приложения, использующего одну-единственную таблицу, запись которой идентична содержанию статистического талона.Другими словами, при использовании основополагающих принципов проектирования данных в созданных информационных системах исключается повторяемость данных и, соответственно, уменьшается возможность ошибок, а также многократно экономится время, затрачиваемое на ввод данных. Помимо этого, более просто осуществляется разделение информационной системы на автоматизированные рабочие места в соответствии с должностными функциями пользователей. Все это наглядно подтверждает необходимость начинать любую, даже самую простую, информационную систему с создания логической и физической моделей данных, и лишь потом приступать к созданию собственно клиентских приложений.3.2 Результаты работы алгоритма «Кора»Все рассмотренные до сих пор конструктивные идеи алгоритмов обучения распознаванию образов были связаны с построением в спрямляющем пространстве разделяющей гиперплоскости. Алгоритм обучения распознаванию образов «Кора» исходит из иных конструктивных идей.Пусть обучающая последовательность распадается на два множества векторов – множество векторов первого класса {x} и множество векторов второго, класса x. Задается множество характеристических функций ψ(x,τ), которые называются признаками. Из множества признаков алгоритм выделяет так называемые достаточные признаки. Достаточным признаком для векторов первого класса называется признак ψ(x,τ*), который на всех векторах второго класса принимает значение 0, а на некоторых векторах первого класса 1.Аналогично определяются достаточные признаки второго класса. Алгоритм выбирает t достаточных признаков первого класса и t достаточных признаков второго класса, так, чтобы для каждого вектора обучающей последовательности нашлось несколько достаточных признаков, принимающих на этом векторе значение 1. Иными словами, признаки должны «покрывать» все множество примеров.Опознание вектора, не участвовавшего в обучении, проводится так: подсчитывается, сколько достаточных признаков первого класса на этом векторе приняли значение единица и сколько достаточных признаков второго класса приняли значение единица. Вектор относится к тому классу, для которого число достаточных признаков, принявших значение единица, больше.Особенность алгоритма «Кора» состоит в том, что рассматривается бинарное пространство X. В качестве класса характеристических функций ψ(x,τ) берутся все возможные конъюнкции двух - трех переменных.Для каждого класса отбор конъюнкций (признаков) производится по следующим правилам:1. Из всех возможных признаков (конъюнкций трех переменных) отбираются достаточные признаки. Достаточные признаки упорядочиваются: считается, что признак ψ(x,τ1) лучше, чем ψ(x,τ2), если число векторов обучающей последовательности, обладающих этим признаком (т. е. векторов, для которых ψx,τ1=1), больше числа векторов, обладающих признаком ψ(x,τ2).2. Из найденного множества достаточных признаков исключаются «подчиненные». Признак ψ(x,τ2) называется «подчиненным» признаку ψ(x,τ1), если множество векторов обучающей последовательности {x:ψx,τ1=1}, обладающих признаком ψ(x,τ1), включает в себя множество векторов {x:ψx,τ1=1}, обладающих признаком ψ(x,τ2). Подчиненность признаков легко проверяется от старшего в упорядоченном ряду признака к младшему.3. Из оставшихся достаточных признаков производится окончательный отбор tпризнаков. Принцип отбора таков, чтобы в окончательный набор вошли признаки, которые «покрывают» все множество примеров, данное на обучение, и чтобы, по возможности, все примеры обладали приблизительно одинаковым количеством признаков (признаки должны «покрывать» множество примеров «равномерно»).Характерной особенностью алгоритма «Кора» являются небольшая емкость класса решающих правил и чрезвычайно простой метод (хотя и эвристический) поиска правила, минимизирующего эмпирический риск. Заметим, что указать класс функций малой емкости, в котором можно найти достаточно хорошее решающее правило, значительно труднее, чем класс функций большой емкости.Оценим число возможных решающих правил для алгоритма «Кора». Пусть бинарное пространство X имеет размерность n, тогда число возможных троек координат равно Cn3. На каждой тройке с помощью конъюнкции может быть задано восемь функций алгебры логики. Таким образом, всего возможно T=8Cn3 различных признаков. Из возможных признаков должно быть отобрано t достаточных признаков первого класса и t достаточных признаков второго класса. Так как существует не более CTt способов выбрать t признаков из множества, содержащего T элементов, то число различных решающих правил N ограничено величиной N<(8CTt)2.Следовательно, N<n6t, если величина эмпирического риска близка к нулю, вероятность неправильной классификации с помощью найденного правила уклонится от эмпирической оценки не более чем на величину ε=6tlnn-ln⁡(η)l.Заметим, что величина уклонения пропорциональна только логарифму размерности пространства. В этом и есть замечательная особенность рассмотренного класса не гладких решающих правил.Существует база данных множества признаков представленных в виде булевой матрицы. Матрица представлена в таблице Excel для удобства импорта данных на вход программы. Данная процедура называется бинаризацией количественных признаков.Произвольный признак f:D→Df порождает семейство предикатов, проверяющих попадание значения f(x) в определённые подмножества множества Df. На рисунках 10 и 11 перечисляются наиболее типичные конструкции данного вида.Рисунок 10 - Вариационный ряд значения признаков fx и пороги diРисунок 11 - Начальное разбиение диапазона значений признака на зоны позитивных и негативных объектовОписанные способы позволяют получить огромное количество предикатов. Если в дальнейшем они будут использоваться для синтеза конъюнкций, то для сокращения перебора имеет смысл сразу отобрать из них наиболее информативные. В случае порядковых и количественных признаков данная задача решается путём оптимального разбиения диапазона значений признака на зоны.Пусть обучающая последовательность распадается на два множества векторов – множество векторов первого класса {x} и множество векторов второго, класса x. Результат бинаризации показан на рисунке 12Рисунок 12 - Преобразование таблицы признаков в булеву матрицуРанг конъюнкции равен 3, только при малых n алгоритм имеет значение. На выходе список всех конъюнкций.Таблица 1 – Характеристика работы алгоритма «Кора»АлгоритмКоличество элементовПорог обученияНадежность%«Кора»30 х 301782,810 х10771,2Задача состояла в классификации заболеваний сердца по классам признаков. Множество объектов задачи – 30критерие принадлежности заболеванию. К особенностям задачи можно отнести физическую однородность признаков, описывающих объект распознавания, а также то, что классы не являются контрастно различными.Таблица 2 – Множество объектов выборки1234567891011B01БС1В02БС2В03В04ТРП1ПФ1ПФ2РП2Задача 10,740,740,770,730,640,810.800,620,720,690,79Множество всех объектов случайным образом разбивают на две выборки (непересекающихся подмножества): обучающую – 17 объектов и контрольную – 13. В решении задачи участвовали эвристики: В01 – В04, ПФ1, ПФ2, БС1, БС2, РП1, РП2, Т. После этапа обучения оценка точности алгоритмов определялась как частота правильного распознавания объектов контрольной выборки. Точность алгоритма на задаче классификации иллюстрирует в таблице 2.3.3 Реализация алгоритма ближайшего соседа3.3.1 Пример работы алгоритмаЗная математическую основу классификатора, можно перейти к детальному рассмотрению самого алгоритма. Метрические классификаторы применяются для распознавания образов, они определяют степень «сходства» между различными объектами. Применяются, когда, либо сложно, либо мы не можем сформировать достаточно «хорошее» признаковое описание объектов. Фактически мы используем сырые данные, которые по нашему мнению содержат в себе информацию об объекте, но оснований так считать нет. Идейная составляющая метрических классификаторов основывается на том, что похожие объекты очень часто находятся «рядом», т.е. на близком расстоянии друг от друга. Рассмотрим, как мы, с человеческой точки зрения, определяем сходство между объектами. Например, как мы распознаём своих знакомых и друзей: мы запоминаем общие черты лица, цвет волос, цвет глаз, голос, походку, стиль одежды и другие признаки. Тех, кого мы видим очень часто, мы просто полностью запоминаем, набор признаков наиболее полон, кого видим реже, запоминаем только общие признаки без деталей.