Быстрые символьные вычисления для медицинских систем поддержки принятия решений

Статья

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

пробелы, и число пробелов в каждом таком поле равно 5], г = 1, N.

Сами поля с пробелами обозначим вектором X=(хь..х;,.х) Пусть в массиве данных имеется также М полей, не содержащих

пробелов. Обозначим их вектором У=(у1,..у,..ум). Не располагая информацией о степенях взаимного влияния х, будем полагать, что каждое поле одинаково значимо для восстановления пробелов во всех остальных полях. Чем больше полей используем для восстановления поля тем больше, при прочих равных условиях, будет и достоверность восстановления. Но если поле хт содержит пробелы в тех записях, которые до его добавления в список входных полей мы могли использовать для обучения нейросети-аппроксиматора, то после добавления этого поля в список входных полей мы потеряем эти записи, что вызовет снижение достоверности восстановления пробелов в поле XI. Поэтому предлагаем начать восстановление с восстановления тех полей, которые содержат максимальное число пробелов, то есть выбирать номер поля для восстановления надо исходя из условия

= тах

Количество записей, имеющихся для обучения нейросети, восстанавливающей к-е поле, при использовании q полей в качестве исходных данных для восстановления, обозначим как Я^. Восстановление к-поля следует начинать с использования только

М известных полей У=(у1,..у ,...ум), т.е. на первой итерации q=M Если достоверность предсказания (определяемая по тестовой выборке) не достигает требуемого уровня, следует постепенно добавлять дополнительные поля. При этом порядок добавления полей в список исходных для восстановления к-го поля определяется исходя из условия /^+1 —/ ^тт Если по достижении величиной q значения M+N все еще не достигнута требуемая степень достоверности предсказаний а, надо инициировать запрос к пользователю: восстановить следующее по критерию (1) поле, оставив текущее поле для следующих итераций, либо снижать требуемый уровень достоверности предсказаний.

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

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

] 4

где к - номер восстанавливаемого поля; q - число полей, используемых для обучения нейросети, восстанавливающей это поле; ЯкЛ - число записей в обучающей выборке; ту - достоверность элемента данных (значения ьго поля ]-й записи).

Перед началом восстановления пробелов всем известным значениям присваивается значение достоверности, равное 1. Для восстановления некоторых полей удается уже на исходной выборке построить нейросеть, которая дает достоверность восстановления 100% (с учетом целочисленности данных). Целесообразно на первом этапе восстановления попытаться построить восстанавливающие сети для всех полей с пробелами, и при достижении 100% сразу же восстановить такие поля.

С учетом вышеизложенного был разработан алгоритм восстановления пробелов в массиве данных. Значительно (по грубым оценкам - на один-два порядка) уступая известным алгоритмам по скорости, данный алгоритм, как показали эксперименты, несколько превосходит их по достоверности. Это объясняется сложностью зависимостей, которые приходится аппроксимировать. Целесообразность применения медленного алгоритма основывается на том, что он применяется однократно, до построения

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

УДК 681.3; 616-089.48

БЫСТРЫЕ СИМВОЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МЕДИЦИНСКИХ СИСТЕМ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИИ

С.Г ЕМЕЛЬЯНОВ, Л.А. ЛИСИЦИН, Е.А. ТИТЕНКО*

Возникнув в 70-ых годах XX века, медицинские экспертные системы (ЭС) стали исторически первыми удачными программными системами, в которых технологии искусственного интеллекта (ИИ) принципиально улучшили уровень принятия решений для практически значимых задач диагностики и прогнозирования заболеваний [1]. Медицинские ЭС заложили основы теоретического проектирования и практической разработки данного класса интеллектуальных систем. Современный этап развития интеллектуальных систем характеризуется расширительным уточнением систем поддержки принятия решений (СППР) как распределенной совокупности взаимосвязанных подсистем информационного, моделирующего и экспертного назначений. Под информационной подсистемой понимается совокупность баз данных, созданных на основе универсальной СУБД и содержащих числовую, символьную, координатно-привязанную и др. типы информации. Моделирующая подсистема включает множество математических моделей для описания закономерностей предметной области и поддержки решений. Экспертная подсистема - это программная система, ориентированная на реализацию недетерминированных поисково-переборных методов на основе заложенных в базу экспертных знаний о предметной области. Являясь самостоятельными сложно организованными системами, информационная, моделирующая и экспертные подсистемы должны быть соединены в единую гибридную СППР. Ядром СППР является экспертная подсистема, ведущая обработку знаний в символьном виде. Особенностью процессов символьной обработки в ЭС является организация полного или эвристического поиска, базирующегося на недетерминированной трактовке правил обработки знаний.

Актуальное направление в области разработки медицинских СППР связано с проблемой создания адекватных моделей представления знаний и соответствующих им методов обработки знания. Среди существующих моделей представления знаний (продукционные системы, семантические сети, фреймы, логические модели) наибольшее распространение получили продукционная модель представления знания или комбинации с ней (продукционно-семантическая и др.). Целесообразность использования продукционных систем и методов быстрых символьных вычислений для таких систем определяется следующими причинами: естественность формы представления человеческих знаний в продукционном виде; высокий уровень модульности системы продукций; универсальность в реализации любых алгоритмов, т.е. способность отражать любое процедурное знание; легкая расширяемость при объединении систем продукций и сетевых представлений, а также легкость динамического разбиения системы на части; естественный параллелизм и асинхронность реализации. Анализ известных продукционных систем для обработки знаний, показывает, что их недостатком, ограничивающим область применения в задачах реального времени, является метрическая проблема генерации полного множества решений. Суть проблемы - в непродуктивных затратах времени принятия решения из-за последовательного генерирования путей в пространстве возможных решений. Формирование полного множества решений и обход всего пространства вывода основаны на процессах полного перебора путей с возвратами в точки ветвления. При этом возвратный механизм является основным источником временных затрат. Функционирование гибридных СППР требует разработки методов быстрых символьных вычислений, обеспечивающих динамически параллельную генерацию вариантов решений и без возвратов в пространстве состояний. ЭС с точки зрения теоретического проектирования [1] описывается множеством

305040 г. Курск, ул. 50 лет Октября, 94, КГТУ, кафедра Программного обеспечения вычислительной техники

т =

С.Г. Емельянов, Л. А. Лисицин, Е.А. Титенко

{Я, в, I},

где Я - область символьных данных в рабочем алфавите ^; В -база знаний (БЗ) в виде недетерминированной системы продукций; I - интерпретатор продукций (машина вывода). Машина вывода является важнейшим звеном в проектировании ЭС, так как определяет эффективность процессов генерирования решений и проверки их допустимости и корректности. Для продукций с недетерминированным характером срабатывания машина вывода, в общем случае, формирует некоторое конфликтное множество продукций, подлежащих выполнению и определяющих различные (альтернативные) варианты решений. При этом возникает проблема выбора из конфликтного множества продукций таких, которые будут активизированы в текущий момент. Эта проблема имеет ресурсное ограничение. Если ЭС реализована на ЭВМ с параллельной архитектурой, то из конфликтного множества продукций может выбираться не одна, а столько продукций, сколько параллельных процессов, т.е. ветвей в дереве решений, может выполнять ЭВМ. Проблема альтернативного выбора остается. В общем случае возможны два пути ее решения: централизованный и децентрализованный. В 1-м случае разрешение конфликта ведется специальной стратегией. При децентрализованном управлении конфликт разрешается текущей ситуацией в машине вывода. Анализ ЭС в различных областях [2] (медицина, энергетика, геология и др.) выявил традиционные стратегии управления выполнением продукций: стратегия «стопки книг», заключающаяся в адаптации системы продукции к внешним условиям путем, например, подсчета частоты использования продукций с ее положительной оценкой применимости; стратегия самого «длинного» образца, заключающаяся в эвристическом выборе из конфликтного множества такой продукции, у которой левая часть наиболее длинная; стратегия метапродукций, заключающаяся во введении служебных продукций, которые должны обрабатывать конфликтное множество и выбирать приоритетную продукцию; стратегия «классной доски», основанная на выделении общей рабочей области памяти для записи в нее временной информации о результатах и условиях срабатывания продукций в предыдущих ситуациях; стратегия приоритетного выбора, связанная с введением статических или динамических приоритетов над продукциями: статические приоритеты формируются экспертами, а динамические - в процессе решения путем учета событий активизации продукций при их сопоставлении с обрабатываемы -ми данными; стратегия управления по имени, заключающаяся в задании над продукциями внешней грамматики, определяющей очередность срабатывания продукций.

Данные стратегии характеризуются общими свойствами, ограничивающими применение продукционных систем в поисково-переборных задачах большой размерности и/или при наличии заданных временных ограничений при функционировании СППР: принципиальная неустранимость неопределенности выбора; трактовка процесса разрешения конфликта как выбора единственной приоритетной продукции; эвристическая адаптация под имеющийся в ЭС технический ресурс в ущерб равноправной реализации выбранных продукций из конфликтного множества. В целом, по мнению авторитетных ученых в проблематике ИИ (Н. Нильсон, Е. Шортлифф, Д.А. Поспелов, Э.В. Попов, и др.) сдерживающим фактором использования продукционных систем в СППР, в т.ч. медицинских СППР, является отсутствие теории, дающей полноту и непротиворечивость поиска.

В теории алгоритмов существует два типа объектов для генерации множества вариантов решений: алгоритмы и исчисления. Алгоритмические модели выступают как генераторы конструктивных линейных детерминированных процессов. Результат их работы описывается в виде И-дерева решений. Исчислитель-ные модели выступают как генераторы ветвящихся конструктивных недетерминированных процессов. Результат их работы описывается соответственно в виде ИЛИ-дерева решений.

Современный этап развития теории алгоритмов характеризуется двояким отношением к исчислительным моделям, так как свойство недетерминированности имеет уточнение в виде соглашения Поста или соглашения Дейкстры, эффективно применимых к практическим задачам. В соответствии с соглашением Поста недетерминированные правила исчисления понимаются как альтернативные в срабатывании правила, формирующие ветвящееся пространство решений линейно во времени, что дает непродуктивные затраты времени при генерации решений. Соглашение Дейкстры [3] уточняет трактовку недетерминирован-

ных правил как равноправных в срабатывании, что позволяет формировать пространство решений в многомерном пространстве времени. Основанных на соглашении Дейкстры представительных исчислительных моделей с собственными законами преобразования информации не создано в рамках теории алгоритмов и нет адекватных им программных и технических средств. В связи с этим актуальная метрическая проблема эффективной работы современных СППР определяет необходимость разработки методов быстрых символьных вычислений (БСВ), ориентированных на исчислительные продукционные системы, и исследования их временных законов на классе поисковопереборных задач. Для создания исчислительных методов БСВ будет использована недетерминированная продукционная система (2)с равноправным срабатыванием продукций.

Г Оі^Рі

Оі^Рі

Оі^Рі

• Оп^Рп

где О^Оп - заменяемые слова-образцы в рабочем алфавите ^; Р^Рп - заменяющие слова-подстановки в рабочем алфавите ^; ^ - метасимвол, не принадлежащий рабочему алфавиту ^. Попарное пересечение образцов продукционной системы с номерами у (Щ) является индикатором отношения зависимости между продукциями. Среди алгоритмических продукционных систем такие продукции получили название конкурирующих. Среди исчисли-тельных (грамматики Н. Хомского, исчисления Э. Поста и др.) такие продукции получили название конфликтующих. Сущность конфликта в том, что после срабатывания ьой продукции структура образца ]-ой продукции в обрабатываемом слове разрушается, и ]-ая продукция становится неприменимой. В исчислитель-ных продукционных системах с равноправным срабатыванием правил множественные отношения зависимости между образцами обусловливают создание нужного количества копий обрабатываемых слов. Структура фрагмента обрабатываемого слова, на котором возникает конфликт между продукциями, определяется только структурой их образцов и не зависит от характеристик пространства поиска. Такие фрагменты слов будут называться конфликтными словами. Реализация исчислительных методов БСВ базируется на конечном списке конфликтных слов, описывающем всевозможные конфликты в недетерминированной системе продукций. Поэому складывается самостоятельная задача синтеза списка конфликтных слов. Для решения этой задачи надо разработать рекурсивную процедуру синтеза конфликтных слов; определить и обосновать необходимые и достаточные логические условия корректности работы процедуры синтеза. Далее формализуется процесс синтеза конфликтных слов (слово, получаемое объединение двух образцов, имеющих особым образом выделенную общую часть - ядро). Конструктивный процесс синтеза конфликтных слов определяется следующими графическими схемами (3), задающими всевозможные варианты пересечений двух слов:

0! = 0?=5

а Ь а Ь

аЬвсЮ БаЬ= заЬзс!

б д

$ а і

аЬБс1ик8с11= аЬБСІІ

аЬ5(іи Ьб= аЬ5(1=

аЬБс!

аЬчс!

где и - операция объединения двух слов

Синтез конфликтных слов сводится к последовательности двух конструктивных процессов: конструктивный процесс обнаружения пересечения двух слов и выделения их ядра; конструктивный процесс дополнения ядра до конфликтного слова. В основе первого процесса используется логическое условие [4] пересечения 2 слов в виде конструктивной дизъюнкции

где каждый терм (3) описывает один из 4-х вариантов пересечения образцов в соответствии с рис.1; индексы «н», «к» обозначают начало и окончание ього и ^ого образцов, с - обозначение вхождения одного образца продукции в другой образец.

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

Статья

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

где индексы «н», «к» обозначают начало и окончание ього и ^ого образцов или ього и ^ого конфликтного слова. Данные конъюнкции описывают ситуации двойного пересечения начал и окончаний двух образцов или конфликтных слов. В случае истинности конструктивных конъюнкций (5) и (6) построение полного списка конфликтных слов невозможно. В этом случае стратегия равноправных выводов не обеспечит полноту и корректность генерируемых решений. Для метрически эффективной обработки знаний в СППР (медицинских) разработаны базовые принципы быстрых символьных вычислений, основанных на оригинальных законах параллельных вычислений. Методы быстрых символьных вычислений дают эффективную генерацию полного множества вариантов решений за счет использования стратегии безвозвратного поиска в пространстве состояний.

Литература

1. Попов Э.В. и др. Статические и динамические экспертные системы.- М.: Финансы и статистика, 1996.- 319 с.

2. Хорошевский В.Ф. Механизмы вывода решений в экспертных системах: Уч. пособие.- М.: МИФИ, 1988.- 44 с.

3. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем.- СПб.: Питер, 2001.- 384 с.

4. Довгаль В.М. Методы модификации формальных систем обработки символьной информации.- КурскГТУ, 1996.- 114 с.

УДК 519.816

О НЕИРОСЕТЕВОМ ПОДХОДЕ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИИ АМБУЛАТОРНО-ПОЛИКЛИНИЧЕСКИМИ СЛУЖБАМИ

В.Н. ЛОПИН*, И.Е. ПРИЛУЦКАЯ**

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

Для решения задачи поддержки принятия решений амбулаторно-поликлиническими службами предлагается использовать нейросетевой пакет №игоРго 0.25, разработанный в ИВМ СО РАН. Этот программный продукт является менеджером обучаемых нейронных сетей и позволяет реализовывать ряд базовых операций, связанных с задачами прогнозирования и классификации данных. В рассматриваемом подходе используется решение задачи классификации на основе нейросетей, обученных на объективных статистических данных информационной базы ССМП. Для обучения и тестирования результатов обучения использовались объективные обучающие и тестирующие выборки, включающие строки формата, показанного на рис.

Рис. Формат строки выборки: ро1 - код пола больного; уогг - код возраста больного; роу1 - код повода вызова больным ССМП на временном интервале ц - код диагноза поставленного врачом ССМП на временном интервале ц ур1 - код вида помощи оказанной врачом ССМП на временном интервале ц геэЬ - код принятого решения о лечении больного амбулаторно-поликлиническими службами.

Обучающая выборка содержала 270 строк (примеров), каждая из которых включает данные о поле, возрасте, результатах

***305040, г. Курск, ул. 50 лет Октября 94, КГТУ, тел. 55-45-48

305003, г. Курск, ул. Дружининская 3, Станция скорой медпомощи

трех последовательных во времени вызовах ССМП к больному и решению, принятому амбулаторно-поликлинической службой вследствие анализа этих данных. Тестирующая выборка содержала 30 аналогичных примеров, не участвовавших в обучении нейросети. Примеры в этой выборке состоят из шести групп, каждая из которых включает пять случайно выбранных примеров для одного из шести возможных решений. Обучающая и тестирующая выборки реализованы в виде соответствующих баз данных в формате ёЪ£ При создании вышеуказанных баз данных использовалось кодирование данных в соответствии с табл. 1-6.

Таблица 1

Кодировка пола

рої значение

1 мужчина

2 женщина

Таблица 2

Кодировка возраста

У02Г значение

1 18-39 лет

2 40-49 лет

3 50-59 лет

4 59-70 лет

5 70-74 лет

6 свыше 75 лет

Таблица 3

Кодировка повода вызова

роу значение

1 «задыхается»

2 «потеря сознания»

3 «боли в животе»

4 «травма, ушибы»

5 «приступ почек»

6 «приступ печени»

7 «задержка мочи»

8 «сердечный приступ»

9 «плохо пьяному»

10 «болят почки»

11 «болят суставы»

12 «плохо гипертонику»

13 «приступ бронхиальной астмы»

14 «болит печень»

15 «болит желудок»

16 «болит спина»

17 «плохо»

18 «болит голова»

19 «АД - давление»

20 «все болит»

Таблица 4

Кодировка диагноза больного

значение

1 болезни органов дыхания

2 болезни системы кровообращения

3 болезни органов пищеварения

4 болезни мочевыводящей системы

5 травмы и хирургия

6 болезни костно-мышечной системы

7 алкоголизм

8 практически здоров

Таблица 5

Кодировка вида помощи больному

уР значение

1 инъекция

2 закрытый массаж сердца

3 ЭКГ

4 остановка кровотечения

5 искусственное вентиляция легких

6 зондовое промывание;

7 шина

8 наложение повязок

9 катетер мочевого пузыря

10 совет

Таблица 6

Кодировка принятого решения

геэЬ значение

1 диспансеризация

2 эффективная медикаментозная терапия

3 направление в стационар

4 направление в социальную служба

5 консультация специалиста

6 созыв консилиума врачей