Содержание к диссертации
Введение
ГЛАВА 1. Методы и системы приобретения и представления знаний 10
1.1. Приобретение знаний 10
1.1.1. Интервью 12
1.1.2. Методы когнитивной психологии 14
1.1.3. Диагностические игры 14
1.2. Представление знаний 17
1.2.1. Система Rhet [43] 24
1.2.2. Babylon 25
1.2.3. FruleKit, Parmenides [70] 25
1.2.4. Frobs, Frolic [53] 26
1.2.5. Florid [56] 27
1.2.6. FramerD [59] 27
1.3. Постановка задач исследования ЗО
Выводы к главе 1 30
ГЛАВА 2. Построение модели знаний в системах принятия решений для новых медицинских технологий 32
2.1. Модель представления знаний 32
2.1.1. Виды семантических связей 35
2.1.2. Типы сообщений. Формальное определение отношений 38
2.1.3. Правила формирования сообщений
2.2. Сетевая фреймовая модель представления объектов сети 43
2.2.1. Фреймы 43
2.2.2. Модель знаний 45
2.2.3. Связанные процедуры (демоны) 46
2.2.4. Правила 47
2.3. Формальное представление семантических свойств фреймовой модели 48
2.3.1. Основные понятия модели знаний. Структурный уровень 49
2.3.2. Ограничения семантической целостности 53
2.3.3. Основные операции во фреймовых моделях 56
2.4. Логическая модель ЛХЭ 59
2.4.1. Пример формирования текстового фрагмента результатов ЛХЭ 63
Выводы к главе 2 66
ГЛАВА 3. Связь базы данных и базы знаний в системе ЛХЭ 68
3.1. Методы Data Mining в задаче выявления знаний из баз данных 68
3.2. Методы выявления знаний 69
3.3. Методы анализа данных 71
3.4. Некоторые индуктивные алгоритмы и алгоритмы построения деревьев решений 81
3.5. База знаний 85
3.6. Формальный концептуальный анализ данных 90
Выводы к главе 3 99
ГЛАВА 4. Описание системы мониторинга лапароскопической холецистэктомии (СМ ЛХЭ) 101
4.1. Назначение 101
4.2. Основные возможности 102
4.2.1 Требования к аппаратному обеспечению 104
4.3. Работа с СМ ЛХЭ 104
4.3.1. Режимы запуска 104
4.3.2. Режим работы «Администратор» 105
4.3.3. Режим работы «Пользователь» 107
4.4. Фреймовая сеть ПО
4.4.1. Реализация суперфрейма 111
4.4.2. Реализация фрейма «Осмотр, пальпация живота» 112
4.5. Формирование протоколов 113
4.5.1. Реализация текстового фрагмента 115
4.5.2. Пример генерации текстового фрагмента 117
Выводы к главе 4 122
Заключение 123
Список литературы 1
- Представление знаний
- Типы сообщений. Формальное определение отношений
- Некоторые индуктивные алгоритмы и алгоритмы построения деревьев решений
- Требования к аппаратному обеспечению
Представление знаний
Основанная на них техника репертуарных решеток была разработана Дж. Келли [63] в качестве метода изучения систем личностных психологических конструктов. Конструкт — это биполярный признак. Польза конструкта именно в биполярности, контрасте. Конструкт это то, чем два или несколько объектов сходны между собой и, следовательно, отличны от третьего объекта или нескольких других объектов.
Исторически впервые автоматическое извлечение из экспертов конструктов и создание репертуарных решеток было реализовано в системе PLANET [46, 72], которая представляет собой комплекс программ для интерактивного конструирования и анализа решеток.
В системе ETS [45], созданной под руководством Дж. Буза в фирме Boeing, использован метод репертуарных решеток для выявления понятийной системы предметной области. Собственно, о выявлении знаний эксперта можно говорить, начиная, по-видимому, с этой работы. С этой точки зрения система TEIRESIAS является лишь интеллектуальным редактором, облегчающим эксперту процесс формирования правил и понятий. Потомками ETS являются система NeoETS и интегрированная среда для извлечения экспертных знаний AQUINAS. Дальнейшим развитием системы PLANET является интегрированная среда KITTEN, поддерживающая ряд методов извлечения знаний.
В диагностической системе MORE использованы принципы, сходные с теми, которые лежат в основе обеих описанных выше систем. Здесь впервые использовано несколько различных стратеги интервью. Техника интервью, использованная в MORE, направлена на выявление следующих сущностей: гипотез, симптомов, условий, связей и путей.
По-видимому, этот подход впервые был применен в группе И.М. Гель-фанда для выявления знаний экспертов в процессе решения задачи прогнозиро ГЛАВА 1 вания сроков сохранения нормального синусного ритма после электроимпульсной терапии. Изложим его схему, следуя [1, 16], на примере одной разновидности игр с экспертами — игры двух экспертов. Игра преследовала следующие цели: а) определение полноты набора признаков, используемых врачом при ре шении медицинских задач; б) редуцирование набора признаков (т.е. отбор наиболее существенных признаков с точки зрения решаемых задач). К этому же классу методов относится метод имитации консультаций. Этот метод реализован в системе АРИАДНА [28]. В основе этого метода - многократное решение экспертом проблемы классификации в режиме последовательной вопросно-ответной консультации «Клиент-Эксперт». При этом роль клиента моделируется всеми участниками работы, а эксперт выполняет функции, близкие к его профессиональной консультативной деятельности.
Приведенные прямые методы могут быть интегрированы в среды, реализующие различные методы приобретения знаний, рассмотренные выше, например, AQUINAS, KITTEN (Knowledge Initiation & Transfer Tools for Experts and Novices) [72]. Отличие KITTEN от AQUINAS заключается в том, что в KITTEN обеспечивается извлечение элементов и конструктов из текстов, кроме того, имеются процедуры, анализирующие примеры решения задач экспертом и генерирующие по ним продукционные правила. Продукционные правила, порождаемые из примеров и из решеток, могут быть загружены в БЗ оболочки Nex-pert, с помощью которой проводится тестирование БЗ.
Подводя предварительные итоги проведенного анализа методов и средств приобретения знаний, необходимо сделать следующие заключения. Несмотря на то, что в значительной степени отправным толчком к формированию направления ИИ - приобретение знаний - явились первые медицинские диагностические системы, глобального охвата целой отрасли все более совершенными, "умными" системами не произошло. На наш взгляд, это можно объяснить высказанной в самом начале настоящего разделе мыслью: плохая структурированность знаний эксперта часто приводит к неправильной оценке экспертом важности тех или иных знаний для решения задач. Однако не только в этом причина отставания внедрения полезных автоматизированных систем в медицине. Вербализация знаний в форме предписаний на самом деле скрывает некоторые "неструктурированные" знания эксперта, который может обойти верба-лизированную сущность и принять далеко нестандартное решение. Кроме того, отражение фрагментов знаний в форме объяснений - чрезвычайно важная, но в достаточной степени рутинная функция. Хотя она отражает некоторую гносеологию самой системы (диагностики, советчика и т.д.). Рутинность заключается в том, что трудно себе представить исчерпывающие для всех случаев объясняющие тексты. В этой связи, более целесообразным является выделение фрагментов текстов, общих для различных случаев. Эти фрагменты имеют смысл только в контексте. В этом случае не только процесс формирования объяснения становится более интеллектуализированным, ненавязанным, объективным, но и позволит сформировать некоторые заключительные протоколы, сопровождающие некоторое медицинское действо. Такой подход преследует несколько целей: помимо объективизации принятых решений, что само по себе ценно, преследуется и этический и правовой аспект.
Типы сообщений. Формальное определение отношений
Под семантической связью будем понимать коррелятивное или каузальное отношение между объектами (понятиями). В качестве элементарного отношения могут выступать бинарные отношения, в общем случае описываемые предикатами первого порядка и выступающие в качестве функторов в этих отношениях, или операции. В последнем случае они устанавливают связь между аргументами предиката. Такими отношениями являются "больше", "меньше", "равно", "иметь значение", "иметь свойство" и т.д.
Связи обладают свойствами симметричности, рефлексивности, транзитивности, антирефлексивности. Классификация по свойствам приводит к типизации связей. Можно выделить следующие виды семантических связей
Свойства приведенных отношений следуют из их семантики. Однако эти свойства следует иметь в виду, поскольку они имеют важное значение при определении концептуального графа (модели), особенно при необходимости его минимизации. Так, формальный подход к построению графа может указать на возможное существование рефлексивных связей, которые могут приводить к зацикливаниям. Кроме того, одновременное наличие свойств рефлексивности, транзитивности и симметричности приводит к новому отношению эквивалентности.
В наибольшей степени при создании интеллектуальных систем используются каузальные связи, описанные в [37, 39]. Основным свойством каузальных связей является их транзитивность, в то же время она нерефлексивна. Отношение сопровождения рефлексивно, транзитивно. Свойства остальных связей следуют из следующей таблицы, второй столбец которой поясняет отношение в виде высказывания:
Актуализация того или иного отношения сопровождается сообщением, совпадающим с приведенными в таблице высказываниями. Эти высказывания могут быть классифицированы в соответствии с их семантикой. Так, высказывания 1-5 (табл. 2.1) объединяются в класс сообщений Кь поскольку они все статичны и осуществление некоторого события зависит от одновременного в данный момент существования другого. Высказывания 6-8 определяют некоторую динамику, последовательность событий. Однако смыл их "развития" различен. Поэтому отнесем их в разные классы сообщений К2, К3, К4 соответственно. Последние два высказывания не могут быть отнесены ни к одной из групп: Neg отрицает Y при наличии X и Fin декларирует направление цели. Эти два типа высказываний отнесем к классам К5 и К6. Заметим, что приведенные высказывания могут быть расширены с помощью различных модальностей типа "часто", "иногда", "возможно", "обычно" и т.д. В этом случае количество высказываний в приведенных классах и число классов может увеличиться. Такого типа высказывания характерны для задач диагностики, которую, однако, в этой работе не рассматриваем.
В результате такого объединения получим следующую таблицу обобщенных сообщений и соответствующие им классы: Теперь можно для описания различных смыслов сообщений ввести понятие типа сообщения. Сообщение, имеющее некоторую форму класса Kj; относится к типу Ту, если для понятий, входящих в него, справедлива также одна из форм, входящих в класс Kj. Задача заключается в построении таких преобразований, которые позволяли бы получить отношения совместности событий и получения из сообщений базовых классов сложные сообщения. Например, "а сопровождается (3 и Р является проявлением а". В этом сообщении имеем совместность события формы 6 (Cous) и формы 5 (Ако). Иными словами имеем совмещение сообщений класса К2 и класса Ki и сформировано сообщение Т2\. Таким образом, необходимо определить формальное преобразование R, переводящее одно событие в другое и формирующее соответствующее сообщение.
Для реализации такого подхода введем в рассмотрение некоторое (определенное предметной областью) множество D={DbD2,...,Dn}, где каждое Dj -множество атрибутов и каждому объекту или событию ставится в соответствие подмножество А экземпляров (реализаций) из декартова произведения Dk=DilxDi2X...xDik (k n) из D. Пара (s, А) представляет событие с именем s и множеством экземпляров А. Тогда формальная модель неоднородной сети фреймов может быть представлена четверкой W= D,S,R,F , если отношения R заданы на парах конкретизированных (экземплярах) событий ((sbAi), (s2,A2)). F={fl,f2,...fm} определяет функциональные зависимости между признаками так, что каждому кортежу 5єБк функция f ставит в соответствие некоторый элемент f(5) из Dj. Событие-прототип s0eS назовем ситуацией. Признаки pj, р2 ,...,рк события s0 назовем признаками ситуации.
Некоторые индуктивные алгоритмы и алгоритмы построения деревьев решений
Это ограничение обеспечивает конечность числа слотов фрейма, тем самым предотвращается неограниченный рост фреймовой структуры.
Фрейм не должен содержать слот с именем фрейма или именем подчиненно го или родительского фрейма. Таким образом, исключается возможность для слота фрейма иметь в качестве допустимого значения фрейм или его подчинен ный фрейм: VfeM: 3f GM:(feM1)A(f=fv f,ft GE_is_av f ,f GE_is_a)).
Обязательными значениями называются значения, которые нельзя опустить при движении по фреймовой иерархии сверху вниз. Терминальные слоты име ГЛАВА 2 ют обязательные значения, нетерминальные же могут быть как обязательными, так и необязательными: FR(f,s,{afl})=FR(f,s,{a0})uFR(f,s,{anot_0}). VfeM:VseMi:{[is_terminal(s)= FR(f,s,{afl})=FR(f,s,{ao})]A [is_not_terminаl(s)= (FR(f,s,{aд})=FR(f,s,{a0})vFR(f,s,{д})= =FR(f,s,{anoto}))]}. Понятие обязательного и необязательного значения слота служит средством для эксплицитного выражения существования двух возможных значений. В некоторых слотах описывается действительное свойство фрейма, в то время как в других слотах значение может присутствовать, хотя это вовсе не требуется. Например, для слота ЦП фрейма КОМПЬЮТЕР в качестве значения задается конкретный процессор. Значениями слота «внешнее устройство» того же фрейма задаются типы внешних устройств. Из этого не следует, что конкретный КОМПЬЮТЕР обладает всеми этими внешними устройствами. Задача состоит в том, чтобы нетерминальный слот разбить на подчиненные слоты, тем самым, сокращая множество допустимых значений. Например, разбить слот «внешние устройства» на обязательные слоты «дисплей» и «клавиатура» и необязательный слот «принтер».
Обязательный (необязательный) слот при прохождении по фреймовой иерархии отношений не меняет своего свойства, т.е. продолжает оставаться обязательным (необязательным): V f,f eE_is_a: Vs eM i:VPe{is_obl,is_not_obl}:[P(f,s ) (s GM1AP(f,s )v is_not_terminal(s )A3seMi: ( s,s eIs_aAP(f,s)))]. Модельно зависимые ограничения Самым важным ограничением целостности в этом случае является задание режима заполнения слотов, указание допустимых значений для терминальных слотов или задание предопределенного множества допустимых значений нетерминальных слотов. Помимо эксплицитного задания множества допусти ГЛАВА 2 мых значений для терминальных слотов, ограничения на режим заполнения слотов могут быть заданы в виде правил: Єї может быть значением слота s = е2 (не) является значением слота S2A(V) е3 (не) является значением слота S3A(V) еп (не) является значением sn. Все ограничения целостности следует эксплицитно задавать в системе управления базой знаний. Следовательно, исключается внешняя процедурная поддержка для присваиваний. Нельзя гарантировать правильность и достоверность программы, скрытых в процедурах, внешних по отношению к базе знаний. Нельзя автоматически проверить, является ли множество указанных правил целостности свободным от противоречий в случае, когда некоторые из этих ограничений скрыты во внешних объявленных процедурах.
Нарушение семантической целостности может произойти только после выполнения модифицирующих операций: вставки, стирания или обновления. Разрешенные операции входят в концептуальное определение модели данных и являются единственным средством доступа к базе данных. Семантическая целостность должна гарантироваться допустимыми операциями. Поэтому, исходя из принципа соблюдения семантической целостности, должны быть определены модифицирующие операции.
Первый и последний этапы должны гарантировать семантическую цело ГЛАВА 2 стность. Соблюдение концептуальных отношений между двумя фреймами зависит от способности сохранять свойства, которые необходимы для их поддержания. Поэтому операции создания и уничтожения отношений являются исходными для последующих операций и должны выполняться в пределах системы, а не вне ее. Далее для иллюстрации изложенной концепции рассмотрим наиболее интересные операции. Пусть [х-»у] означает отображение х в у. Определим операции добавить фрейм
Требования к аппаратному обеспечению
По решетке можно проследить все свойства, которыми обладает то или иное состояние: это множество всех свойств, лежащих выше узла, помеченного названием состояния. Каждый узел решетки соответствует концепту. Например, к={{Сложностъ технического выполнения){g с d b h f а)) показывает, какие свойства делают проведение ЛХЭ технически невозможной, поэтому рекомендуется перейти к традиционному способу проведения операции. Концепт q—{{Неустранимые интраоперационные ослолснения Сложность технического выполнения) {fc db а)) содержит общие свойства двух состояний (строки 3 и 4) и показывает, при каких условиях выход из ЛХЭ связан с интраоперационными осложнениями, делающими продолжение ЛХЭ технически невозможной, концепт г=({ } М) - наименьший концепт решетки обладает всеми свойствами всех состояний. Концепт s=(V, {а)) - наибольший элемент решетки концептов, он объединяет все объекты, которые обладают общим свойством - а.
По решетке концептов можно установить зависимости на свойствах, которые представимы в виде импликаций, истинных в данном контексте. Если два концепта {А\,В\) {А2,В2), то все объекты А\, обладающие множеством при ГЛАВА З знаков В\, обладают также множеством признаков В2. Тогда, согласно теории формального концептуального анализа, на множествах признаков (атрибутов) можно установить зависимости в направлении дуг снизу вверх. Например, в контексте "Результаты выполнения ЛХЭ", g влечет cud: g- c и g- d. Каждое из этих продукционных правил имеет свою специфическую интерпретацию и дает возможность принять решение о допустимости их применения в отдельности или совместно.
Понятие зависимости между атрибутами основано на следующем: если для всех объектов контекста, для которых справедливо некоторое свойство Р, справедливо также некоторое свойство С, то импликация Р— С является истинной. Более точно, импликация Р-»С верна для контекста K-(G,M,P), где AzM и Ccjvl, если для gcG выполняется следующее требование: если каждый атрибут из посылки Р применим к объекту g, то атрибут из заключения С также применим к g.
Даже для малых контекстов множество всех импликаций может быть довольно большим. В связи с этим возникает проблема нахождения базиса импликаций контекста. В [10] установлено, что базис всех импликаций, верных в (G,M,f), задается как Р— Р", где множество атрибутов Р из (G,M,[) рекурсивно определяется, если Р Р" и Q"aP для всех Q, таких, что QaP.
Смысл полученного базиса можно пояснить следующим образом: из некоторой импликации вида Р Р", где РФР", может быть получена импликация, входящая в с\:.зис, гели .амыкаш -з импликаций, следующих из лосылки Р , где Р =РиР00и..., и P0={QaP & Q- C}, т.е., после того, как к посылке были применены импликации, непосредственно из нее следующие, а к полученному результату были применены импликации, следующие из него и т. д., пока в результате мы не получим заключения.
Алгоритм вычисления базиса импликаций можно разделить на следующие части: генерация множеств атрибутов, из которых могут порождаться импликации; критерий, который определяет, следует ли добавлять импликации множеству импликаций, получаемых в результате работы алгоритма; устранение из полученного множества избыточных импликаций. Для генерации множеств атрибутов обход концептуальной решетки осуществляется с помощью алгоритма поиска в глубину.
Для того чтобы не генерировать избыточные множества атрибутов, используется следующее свойство: если мы переходим от одного понятия концептуальной решетки к понятию, лежащему ниже, то импликации могут быть образованы только за счет добавления атрибутов, имеющихся у объектов, лежащих в объеме предыдущего понятия и не лежащих в объеме текущего понятия.
Условием того, что из множества атрибутов можно получить импликацию, является РФР". После этого проверяется, не может ли быть получена импликация Р Р" из ранее полученных импликаций. Для этого вычисляется замыкание Р множества атрибутов Р относительно ранее полученных импликаций. Если при этом Р ФР", то импликация добавляется в множество.
Третья часть необходима, поскольку вследствие добавления новых импликаций, некоторые импликации, полученные ранее, могут выводиться из других импликаций и новой. Устранение импликаций может осуществляться либо после добавления новой импликации к множеству импликаций, либо после окончания работы первой и второй частей алгоритма. Выявление зависимостей и их анализ позволяет извлекать правила, отражающие субъективные представления об исследуемой проблемной области.
