Содержание к диссертации
Введение
Глава 1. Анализ формальных методик построения интеллектуальных систем 8
1.1. Общие положения об интеллектуальных системах 8
1.2. Обзор основных методологий интеллектуального анализа 10
1.2.1. Метод, основанный на алгоритме Байеса 10
1.2.2. Метод Шортлиффа 12
1.2.3. Редукционные модели 12
1.2.4. Исчисление предикатов 13
1.2.5. Нечеткий вывод 16
1.2.6. Генетические алгоритмы 19
1.2.7. Нейронные сети 21
1.3. Анализ методов представления знаний 22
1.3.1. Продукционная модель 22
1.3.2. Предикатные модели 24
1.3.4. Модели на основе нечеткой логики 24
1.3.5. Семантические сети 26
1.3.6. Сети фреймов 28
1.4. Сравнение методик построения интеллектуальных систем 30
1.5. Выводы по главе 1 34
Глава 2. Проектирование формальных моделей ИС «Электронная история болезни» и СППР «В помощь молодому специалисту» 35
2.1. Постановка задачи 35
2.2. Разработка математической модели ИС 35
2.2.1. Семантическое моделирование объектов ИС 36
2.2.2. Автоматная модель ИС 39
2.3. Разработка математической модели СППР 44
2.3.1. Семантическое моделирование СППР 44
2.3.2. Автоматная модель СППР 48
2.3.3. Формальное описание математической модели логического вывода в СППР 52
2.4. Разработка фреймовой модели схемы БЗ 58
2.5. Выводы по главе 2 62
Глава 3. Оценка результатов семантического моделирования ИС и СППР... 63
3.1. Выбор методики моделирования 63
3.2. Архитектура имитационной модели 64
3.3. Алгоритм имитационной модели БЗ СППР ИС «Электронная история болезни» 67
3.4. Описание методики имитационного моделирования 68
3.6. Оценка результатов и основные выводы 72
Глава 4. Функционально-алгоритмическое проектирование моделей ИС «Электронная история болезни» и СППР «В помощь молодому специалисту» 74
4.1. Постановка задачи 74
4.2. Разработка функциональной модели ИС на языке UML 76
4.3. Диаграммы функциональной модели модуля СППР 92
4.4. Функциональное моделирование источников данных 100
4.4.1. База данных ИС «Электронная история болезни» 100
4.4.2. База знаний и словарь модуля СППР «В помощь молодому специалисту» 101
4.5. Выводы по главе 4 108
Заключение по
Литература
- Обзор основных методологий интеллектуального анализа
- Анализ методов представления знаний
- Семантическое моделирование объектов ИС
- Алгоритм имитационной модели БЗ СППР ИС «Электронная история болезни»
Введение к работе
Актуальность темы. В настоящее время активно ведется научная работа в сфере создания интеллектуальных информационных систем (ИС) различного прикладного назначения. Специфика реализации предметно-ориентированных ИС состоит в том, что для конкретных сфер применения не существует четких алгоритмов формализации постановки и решения нетривиальных задач. Поэтому приоритетной целью в этой области является повышение степени интеллектуальной составляющей в проектировании и разработке ИС.
Для решения задачи создания интеллектуальных ИС анализа данных необходим комплекс математических методов и алгоритмов по формализации исходных данных и интеллектуального вывода. Построение интеллектуальных ИС является задачей первостепенной важности особенно в области медицины. Поэтому в данной диссертационной работе вопрос создания предметно-ориентированной ИС решается с уклоном на инфраструктуру лечебно-профилактического учреждения (ЛПУ). Компенсация недостатка исходных данных в этой области состоит в применении алгоритмов искусственного интеллекта, позволяющих максимально сгладить последствия возможных ошибок в анализе. Исследования в области применения прикладной информатики и искусственного интеллекта в медицине проводились и проводятся Edward Shortliffe (США, университет колледжа штата Аризона при Колумбийском университете, Феникс), Natasha F. Noy (США, университет в Стэнфорде, центр исследований биомедицинской информатики). В России этой проблеме посвящены работы П. О. Сафонова (ВГТУ, Воронеж), В. А. Нагина (МГИЭТ(ТУ), Москва) и др. Анализ этих работ показал, что необходимо проведение дальнейших исследований с целью повышения эффективности методов представления и управления знаниями о предметной области (ПО).
Создание моделей предметно-ориентированных интеллектуальных ИС для принятия решений в медицине является актуальной задачей, и данное диссертационное исследование направлено на ее решение.
Целью диссертационной работы являются исследование методик построения интеллектуальных ИС, научное обоснование, разработка алгоритмов моделей представления и аналитической обработки исходных данных на примере ИС «Электронная история болезни».
Для достижения поставленной цели решаются следующие задачи:
Анализ методик моделирования и построения интеллектуальных предметно-ориентированных ИС.
Разработка семантической и алгоритмической моделей' интеллектуальной ИС для формализации процессов проектирования и разработки ИС «Электронная история болезни».
Разработка алгоритма и семантической модели для реализации системы поддержки принятия решения (ОДIP) молодым специалистом в выбранной ПО.
Разработка модели базы знаний (БЗ) СППР для решения задачи управления знаниями о ПО.
Разработка методики оценки необходимых вычислительных ресурсов для функционирования БЗ СППР.
Объектом исследования является информационная система для стационарного отделения ЛПУ.
Предмет исследования - семантические модели ИС «Электронная история болезни» и СППР «В помощь молодому специалисту».
Методологической основой диссертационной работы являются: теория реляционных баз данных; теория объектно-ориентированного проектирования; теория исчисления предикатов, нечеткая логика, а также теория сетей фреймов.
Научная новизна работы:
Разработаны семантические модели для ИС и СППР, позволяющие получить новый формальный аппарат создания ИС в выбранной ПО.
Разработана и реализована новая методика представления знаний в иерархическом фрейме, позволяющая повысить гибкость представления исходных данных для логического вывода и снизить потребление вычислительных ресурсов.
Описана методика нечеткого вывода, использующая БЗ на основе иерархического фрейма, позволяющая ускорить процесс вывода за счет упрощения получения исходных посылок в сравнении с другими методиками.
Предложена методика оценки и сравнения потребления вычислительных ресурсов базой знаний СППР в сравнении с классической реализацией БЗ в виде продукций.
Достоверность результатов работы подтверждена в ходе использования результатов данной работы в реальной разработке ИС «Электронная история болезни».
Практическая ценность работы состоит в создании алгоритмического и программного обеспечения для ИС «Электронная история болезни», которая позволяет повысить эффективность решения задач сбора и анализа информации.
Реализация и внедрение результатов. Информационная система «Электронная история болезни» внедрена в Медицинском институте Пензенского государственного университета, а также в Областной больнице им. Н. Н. Бурденко.
На защиту выносятся:
Семантическая модель ИС «Электронная история болезни».
Семантическая модель для СППР.
Модель организации предметно-ориентированной БЗ.
4. Методика представления предметно-ориентированных знаний в
иерархическом фрейме с возможностью формального представления
исходных посылок в виде предикатных выражений произвольного порядка.
5. Методика оценки и сравнения потребления вычислительных
ресурсов в семантической модели СШ IP.
Апробация работы. Основные результаты докладывались и обсуждались на международных научно-технических конференциях: «Новые информационные технологии и системы» (НИТИС) в Пензенском государственном университете в 2005 и 2006 гг., на XXXIII Международной научно-технической конференции в Пензенском артиллерийском инженерном институте и Всероссийской конференции памяти А. Ф. Блинохватова в Пензенской государственной сельскохозяйственной академии (ПГСХА) в 2005 году.
Публикации. По теме диссертации было опубликовано 10 печатных работ, в которых отражены основные результаты научной работы. Две статьи опубликованы в изданиях, рекомендованных ВАК.
Структура и объем работы. Диссертация содержит введение, четыре главы, список литературы и приложения.
Обзор основных методологий интеллектуального анализа
Другим декларативным способом представления знаний являются редукционные модели, основанные на методе вывода решения. Пусть исходная задача описывается тройкой (S,G,D), где S - описание начального состояния, D - описание множества конечных или целевых состояний, G - множество операторов. Решением является последовательность операторов g\,g2 gi -- Sn из множества G: Г = „(&_. (...g2 (Я і («)). (1-4) Отношением (1.4) определяется путь (трасса) в пространстве состояний, определяющий следование от исходного состояния S к целевому D. Данный способ позволяет разбить задачу на серию промежуточных состояний: іЛ-» и (Ь5 при этом каждое tt лежит на пути к целевому состоянию D. Тогда решение задачи сводится к декомпозиционной последовательности решений подзадач (S,G,tx),(S,G,t2),(S,G,t3),...,(S,G,tn),(S,G,D). Ввиду того, что сразу вся последовательность (1.5) неизвестна, сначала решается задача (SjGj ), а затем формулируется задача (S,G,t2) и т.д.
По определению, предикат [8,9] является расширением понятия «высказывание». В предикат можно подставлять аргументы, истинность или ложность которых он отражает. Логический вывод на основе высказываний не отражает причинно-следственной связи между соседними выражениями. Таким образом, следование одного факта из другого не представимо [3].
Использование предикатных моделей первого порядка в системах искусственного интеллекта целесообразно по следующим причинам:
1. При использовании предикатов получается четкий и логически определенный язык, не содержащий неоднозначностей. Кроме того, он обладает достаточной универсальностью для того, чтобы на нем можно было описывать различные объекты.
2. Используемая процедура доказательства допускает произвольное взаимодействие аксиом и является логически полной (если теорема есть логическое следствие набора аксиом, то доказательство можно получить). . Система доказательств проблемно-независима: для описания новых объектов достаточно добавить несколько новых аксиом, без внесения изменений в программу [1]. Любой предикат содержит переменную, которая является отражением объекта ПО (для логики предикатов первого порядка). Подставляя те или иные значения в предикат, мы получаем истинное или ложное высказывание. Зх(Р(х)), (1.6) где х- предметная переменная. Для (1.6) тождественно высказывание типа «для некоторого препарата существует противопоказание», а предикат Р означает «имеет противопоказание».
В отличие от алгоритмов, в предикатных системах порядок применения правил может быть произвольным. Объекты являются частью высказываний о ПО, истинность или ложность которых определяется значением входящего в него терма - переменной. Исключение составляют исходные правила — аксиомы, истинность которых не зависит от предикатной переменной.
Фигуры вида: - и 3L, (1.7) S S где Sv S2 - верхние секвенции, S - нижние секвенции, называют непосредственным выводом [10]. Правил вывода существует множество. Одними из примеров являются правила modus ponens и modus tolens: А,А- В В А,А- В (1.8)
Выражения (1.18) и (1.19) называются правилами непосредственного вывода, где А,А- В - посылка вывода, В - заключение. Эти выражения формализуют основной закон дедуктивных систем: «из истинных посылок всегда следуют истинные заключения» [1, 24]. Решаемая задача представляется в виде последовательности аксиом (Р1,Р2,...,Рп). Истинность или ложность цели вывода требуется доказать.
Однако, (1.6) может быть условно истинным высказыванием. Например, препарат х имеет противопоказание (Р(х)), в случае, если пациентка у беременна (Q(y))
Анализ методов представления знаний
Для представления знаний используются нечеткие алгоритмы, представляющие собой формальные последовательности получения доказательств и/или выводов. Для этого применяются цепочки нечетких высказываний, отношений, а также лингвистических переменных [19, 26, 27], которые имеют вид: ( / ,T,X,G,F), (1.24) где ф - наименование переменной, Т- базовое терм-множество, где располагаются названия переменных, областью значений которых является X, X - универсальное множество, G - синтаксическая процедура, позволяющая осуществлять операции над элементами множества Т (в частности, генерировать новые элементы), F - семантическая процедура, позволяющая конвертировать каждую новую лингвистическую переменную, образованную с использованием процедуры G в нечеткую переменную [28, 29] вида: {Р,Х9В)9 (1.25) где /?- наименование переменной, X - универсальное множество, является областью /3,
В - нечеткое множество, описывающее ограничения на значения нечеткой переменной. Формула (1.25) является функцией принадлежности переменной /? множеству X.
Модели на основе нечеткой логики обеспечивают, так называемые, «мягкие вычисления» [30] с применением логико-лингвистических выражений. При этом результат (принимаемое решение) в общем виде представим системой нечетких правил и высказываний.
Для решения задачи нечеткого логического вывода на основе продукционной модели вводится понятие нечеткого правила. В этом случае функция принадлежности, выражающая истинность или ложность факта, будет описывать нечеткое значение переменной вывода. Достоинством применения нечетких правил состоит в том, что при условии снижения значения одного параметра влияние другого может учитываться более интеллектуально, без резких перепадов в граничных значениях области определения функции принадлежности [1].
Таким образом, нечеткие системы могут моделировать человеческие рассуждения и объяснять приемы принятия решения, свойственные специалисту [31]. Очевидно, нечеткие системы будут реже предлагать пользователю неверные или неприемлемые решения, полученные из-за использования упрощенной логики или недостаточного уровня знаний [32], свойственные системам других типов.
Основная идея метода состоит в представлении сложных объектов ПО в виде модели набора сущностей и связей между ними. Графически семантические сети изображаются в виде направленных графов [33, 34, 35], где вершинам соответствуют сущности (объекты реального мира), а связи в виде помеченных дуг графа, отражают отношения между ними.
Для агрегатных сущностей целесообразно введение связи "является частью" или "входит в состав". Такие связи имеют смысл, когда один объект входит в состав другого. Очевидно, что в состав агрегатного объекта не может входить обобщенный объект [1].
Обобщенный и индивидные объекты имеют связь "является представителем". Для такой связи важна преемственность, и обычно эти виды связей между объектами несут описательную нагрузку ПО: любой индивидный объект принадлежит классу, описываемому обобщенной сущностью.
У семантической модели есть свойство транзитивности [1], которое может быть использовано и в ходе логического вывода, и в ходе сжатия базы знаний. Отношение а является транзитивным, если и только если в группе трёх объектов А, В, С, таких, что А находится в отношении а с В, В находится в отношении а с С, выполняется утверждение, что А находится в отношении а с объектом С. Данное свойство позволяет хранить не все описания отношений, а лишь необходимую часть из них. Использование этой части механизмом поддержки транзитивности позволит полностью восстановить семантическую сеть.
Отдельно в теории семантических сетей рассматриваются так называемые К-сети [1]. Модели на их основе используют вопросно-ответные методики и исчисление предикатов с развитой системой индексирования объектов. В К-сети существуют три типа связей между блоками: отрицание, дизъюнкция и импликация. Одним из важнейших свойств К-сети является то, что она дает возможность представления произвольно сгруппированных кванторов существования и общности. Данное свойство позволяет гибко описывать ПО на выбранном языке, что необходимо не только для отражения логической структуры объекта, но и для минимизации числа правил в формальном описании.
Модификация информации в базе производится добавлением и удалением новых ребер и вершин в граф описания семантической сети. Поиск информации в БЗ ведется по именам сущностей и/или связей с применением операций сопоставления с образцом [1].
К преимуществам использования семантических сетей относят: 1. Описание объектов и событий производится на уровне, близком к естественному языку. 2. Обеспечивается возможность сцепления различных фрагментов сети. 3. В семантической сети возможные отношения между понятиями и событиями образуют достаточно небольшое и хорошо формализуемое множество. 4. Для каждой операции над сущностями можно выделить некоторый участок семантической сети, который охватывает необходимые в данном запросе смысловые характеристики [36].
Семантическое моделирование объектов ИС
Для моделирования ИС «Электронная история болезни» были выбраны теории исчисления предикатов, нечетких лингвистических вычислений и сетей фреймов. Основной задачей моделирования является получение формализованных описаний ИС и СППР для функционального проектирования схем ИС в выбранной ПО.
Определим агенты и объекты-сущности модели системы в виде семантической сети. Взаимодействие составляющих отражено направленными связями с указанием характера взаимодействия. На рисунке 2.1 представлены объекты внешней среды (агенты): «Пользователь» молодой специалист, работающий с ИС «Электронная история болезни» и «Эксперт» - профессионал в выбранной ПО. Сущность (внутренний объект) «ИС» представлена вместе с «ОДІР» - системой поддержки принятия решений; между ними существует связь по данным, обеспечивающая взаимодействие с агентами «Эксперт» и «Пользователь». Действие агентов на экземпляры объектов «Пациент» и «Решение» имеют непосредственными целями инициирование и контроль решения поставленной задачи. Для описания отношения «Пациент»-«Решение» введено формальное описание взаимодействия экземпляров этих объектов. Рассмотрим состав и характер взаимодействия между отдельными сущностями семантической модели ИС с точки зрения агентов «Пользователь» и «Эксперт». Каждая сущность представляет собой конечное множество объектов реального мира.
Формализация исходных данных в виде аксиом, постановка и решение задач должны отражать главную цель сущности «Пользователь», поскольку именно на лечащего врача возлагается ответственность за пациента и за принимаемое решение. Для получения такого формального представления в виде семантической сети примем соответствие агентов и сущностей конечным множествам, показанное в таблице 2.1.
Наравне с описанием задачи и аксиом, необходимо описать алгоритмический процесс принятия решения, который в обобщенном виде имеет три этапа: первоначальный анализ: ознакомление с первичной информацией, предварительным диагнозом, пройденными обследованиями; выработка стратегии лечения: подбор препаратов и процедур; мониторинг результатов, корректировка решения. С целью формализации представления этого алгоритма рассмотрим автоматную модель семантической модели ИС.
Для получения формального алгоритма рассмотрим словесное описание поведения модели. Работа с ИС производится агентами «Пользователь» и «Эксперт» одновременно или последовательно в соответствии с рабочим графиком. Ввиду того, что на «Пользователя» возлагается принятие решений, в ходе его работы необходимо удовлетворение условия достаточности всех исходных данных для принятия решения. В случае затруднений, агент «Пользователь» активизирует сущность «СППР», экземпляр которой помогает принимать решения в условиях нехватки исходных данных. Для успешной работы агента «Эксперт» никаких дополнительных условий не вводится, так как деятельность профессионала в контексте модели ИС ограничена потребностями молодых специалистов. Таким образом, задача эксперта - контроль решений от сущности «Пользователь» и/или «СППР».
Для спецификации алгоритма работы модели, описанной в подразделе 2.2.1, определим автомат Мура [42, 43]. Данный выбор обусловлен результатами семантического моделирования ИС, где последовательность действий «Пользователя» подчинены целям его профессиональной деятельности. Каждое действие специалиста может быть описано в виде конечного числа входных сигналов (множество X(l) = {x l), x[l), х\1)}) для которых определен порядок смены состояний (множество Sm = ( ,5 ,...,6 0}) модели. В данном случае условие независимости входных логических условий от результатов выполнения микроопераций не соблюдается. Для всех действий «Эксперта» вводится набор внешних воздействий, а для всех функций системы — множество состояний автомата Мура в таблице 2.2.
Алгоритм имитационной модели БЗ СППР ИС «Электронная история болезни»
Построенные UML-диаграммы стенда для имитационного моделирования БЗ позволяют составить описание алгоритмов моделей. Согласно поставленным задачам, реализация этих алгоритмов будет содержать возможность мониторинга временных характеристик и оценки потребления вычислительных ресурсов. Как видно из рисунка 3.3, алгоритм для стенда фреймовой БЗ СППР содержит на одну вершину меньше, что позволяет сделать его реализацию более простой и эффективной, следовательно, фреймовая БЗ имеет потенциальное преимущество в быстродействии.
Для анализа представленных моделей по компактности представления в запоминающем устройстве компьютера необходимо сравнить характеристики обеих моделей БЗ, учитывая значения времени доступа к знаниям и расходу ресурсов хранения на размещение каждой из них.
Имитационное моделирование проводится в два этапа: составление XML-документа и его наполнение тестовыми данными; разработка приложения для проведения имитационного моделирования.
Последовательность моделирования можно представить в виде диаграммы последовательности (рисунок 3.4), на которой представлены 5 агентов: «Пользователь», «Программа», «XML-документ», «Шаблон XML», «Файл результатов». Диаграмма определяет последовательность действий в ходе сбора результатов для сравнения.
Для каждой из тестируемых моделей организации СППР разработан отдельный шаблон, который описывает структуру и принцип организации БЗ СППР. Объект «XML-документ» содержит тестовые данные, которые анализируются объектом «Программа». Результаты моделирования сохраняются в объекте «Файл результатов». X Рисунок 3.4 — Диаграмма последовательности для стенда имитационного моделирования БЗ СППР В качестве испытуемых схем были выбраны следующие модели: 1. Модель на основе фреймовой сети с предикатными условиями применимости. 2. Продукционная модель, включающая декларативные и процедурные знания о ПО.
Одной из наиболее частых операций во фрейме является сопоставление по образцу, когда некоторый набор данных накладывается на БЗ. В этом случае скорость работы БЗ определяется преимущественно временем операции считывания знаний. Для оценки длительности чтения и добавления фактов в реальной БЗ введем два временных параметра. Обозначим Тч среднее время чтения знаний из фрейма, Тд - среднее время добавления факта во фрейм.
Для вычисления Тч определим формулу: у 1=1 +tc, (3.2) П где tf - время доступа к слоту /-го уровня вложенности, / = 1,п; t0— время, затрачиваемое на словарное сопоставление. Тогда формула оценки ТД будет выглядеть следующим образом: г«= у-+ =+ ,,„ (3-3) где /- порядок предикатного выражения условия применимости для добавляемого факта; tf - время доступа к z-й продукции БЗ; /зап - время записи данных в слот. В предельном случае, когда п = /, справедливо следующее равенство: Т =Т . (3.4) ч д зап \ / Обозначим tf и tf в виде Гд{С1уп и Т соответственно. Тогда оценка времени доступа Т/ п для фреймовой (n = 2) модели может быть представлена как сумма математических ожиданий для слотов 1-го и 2-го уровней иерархии: 7=1 j=n-k+l В случае с продукционной моделью время Т определяется как математическое ожидание равномерного дискретного распределения значений времени доступа к у-й продукции в БЗ: N С = Ем+гр (3-6) где р - вероятность обращения к j-й продукции за время t.\ tl - время декодирования предикатных посылок в каждой продукции.
Для оценки объема, занимаемого БЗ на основе фреймовой модели, введем значение отношения объема продукционной и фреймовой баз с одинаковыми наборами знаний: U = - , (3.7) V f где Vp - объем множества продукций БЗ; Vf - объем, занимаемый множеством слотов. Значение отношения Vr и V приводится в таблице 3.1 для семантически равнозначных БЗ на основе фреймовой и продукционной моделей.
Можно утверждать, что эффективность расхода памяти для фреймовой модели в целом выше. Продукционная модель будет эффективнее только в случае, если начальные условия логического вывода полностью совпадут с набором предикатов в условной части продукции. Однако, реальная медицинская практика показывает, что такие случаи единичны. Экспериментальное подтверждение этим выводам приведено в подразделе 3.6.
Преимущество фреймовой модели объясняется тем, что она обеспечивает распределенное хранение элементарных условий. Это позволяет «набирать» готовые комбинации в результате сопоставления по образцу при обходе ветвей фрейма.
