дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
NUMBER (> ?C1 0))(?C2 NUMBER (> ?C2 0))) ( — (+ ?C1 ?C2)(* ?СР1 и CFz) больше или равны нулю 12.2. Коэффициенты достоверности (defrule OAV::combine- certainties (declare (auto-focus TRUE)) ?fact1 < — (oav (object $?o) (attribute а) (value $?v) (CF Со а) (value $?v) (CF С) (test (neq ?fact1 ?fact2)) => (retract ?fact1) (modify ?fact2 (CF (combine-certainties С ?С2)))) СР(Р1 or Р) = max(C'Å(Ð), СР(Р2)) СР(Р1 апс1 P2) = min(CР(Р1), СГ(Р2)j СЕ(по1 Р) = — CF(P) В этих формулах Р, Р1 и Р обозначают шаблоны из левой части правила. Кроме того, если коэффициент достоверности в левой части правила меньше 0.2, то правило рассматривается как неприменимое и запуск его не происходит. Логический вывод значения коэффициента достоверности факта, внесенного в список фактов под действием правой части правила, осуществляется путем умножения коэффициента достоверности вносимого факта на коэффициент до- Обратите внимание на то, что идентификаторы фактов ? fact1 и ? fact2 сравниваются друг с другом в условном элементе test. Такая операция применяется для получения гарантий того, что правило не согласовано с фактом с использованием точно такого же факта для первых двух шаблонов. Адреса фактов позволяют сравнить функции eq и neq. Кроме того, следует отметить, что для данного правила разрешен атрибут auto — focus. Это позволяет гарантировать, что две тройки OAV будут скомбинированы, прежде чем будет разрешен запуск других правил, шаблонам которых соответствуют обе эти тройки. Следующим шагом на пути к внедрению средств поддержки коэффициентов достоверности в систему CLIPS является связывание коэффициентов достоверности фактов, согласующихся с левой частью правила, с коэффициентами достоверности фактов, внесенных в список фактов с помощью правой части правила. В системе логический вывод коэффициента достоверности ассоциирующегося с левой частью правила, осуществляется с использованием следующих формул Глава 12. Примеры проектов экспертных систем Для завершения эмуляции коэффициентов достоверности требуется еще один, последний шаг. В правиле combine — certainties предусмотрен единственный метод combine — certainties, в котором учитывается лишь такой случай, когда оба коэффициента достоверности являются положительными. А введение дополнительных методов должно позволить учитывать другие случаи комбинирования коэффициентов достоверности. Ниже описаны оставшиеся случаи комбинирования. New Certainty = (СЕ + СХ'2) + (СЕ * CFg) если СГ1 < 0 и СХ2 < 0 СЕ, +СЕ, New Certainty = 1 — min(C'F], CFOG) если — 1 < CF> * CF2 < 0 стоверности, заданный в левой части правила. Ниже приведен результат преобразования правила приведенного вначале данного разделав правило CLIPS; это правило показывает, как вычисляются коэффициенты достоверности в левой и правой частях правила. Правило помещается в модуль IDENTIFY, который импортирует конструкцию de f template с именем oav из модуля OAV. defmodule IDENTIFY (import OAV deftemplate oav)) (defrule IDENTIFY::MYCIN-to-CLIPS-translation (oav (object organism) (attribute stain) (value gramneg) (CF С) (oav (object organism) (attribute morphology) (value rod) (CF ?C2)) (oav (object patient) (attribute is а) (value compromised host) (CF ?C3)) (test (> (min С ?C3) 0.2)) — > (bind ?C4 (* (min ?Cl ?C2 ?C3) 0.6)) (assert (oav (object organism) (attribute identity) (value pseudomonas) (С. Деревья решений 955 12.3 Деревья решений Как было указано в главе 3, деревья решений лежат в основе удобного подхода к решению задач классификации некоторых типов. Деревья решений позволяют находить решения путем сокращения множества возможных ответов с помощью осуществления ряда выборов или ответов на вопросы, которые отсекают лишние ветви в пространстве поиска. Задачи, пригодные для решения с помощью деревьев решений, характеризуются тем, что ответ в них отыскивается из заранее заданного множества возможных ответов. Например, для решения одной из задач таксономии может потребоваться идентификация драгоценного камня путем выбора из множества всех известных драгоценных камней, а для решения задачи диагностики может потребоваться выбрать один возможный способ исправления ситуации из множества способов исправления ситуации или одну причину нарушения из множества возможных причин. Но, вообще говоря, деревья решений не очень хорошо подходят для задач составления расписаний, планирования и синтеза, в которых приходится вырабатывать решения, а не только выбирать среди существующих решений, поскольку при использовании деревьев решений множество ответов должно быть определено заранее. Напомним, что деревья решений состоят из узлов и ребер. Узлы представляют различные местонахождения в дереве. Ребра, направленные сверху вниз, соединяют родительские узлы с дочерними, а ребра, направленные снизу вверх, соединяют дочерние узлы с родительскими. Узел, находящийся в вершине дерева и не имеющий родительских узлов, называется корневым узлом. Следует отметить, что в дереве каждый узел имеет только один родительский узел, за исключением корневого узла, не имеющего родительского узла. Узлы, не имеющие дочерних узлов, называются листовыми узлами. Листовые узлы дерева решений представляют всевозможные решения, которые могут быть получены логическим путем с помощью этого дерева. Такие узлы именуются у лами ответов, а все другие узлы в дереве называются узлами принятия решений. Каждый узел принятия решений представляет вопрос, на который нужно дать ответили решение, которое нужно принять, после чего определяется соответствующее ребро дерева решений, по которому необходимо проследовать дальше. В простых деревьях решений в качестве вопроса могут применяться вопросы, требующие однозначного ответа, "да" или "нет, например "Является ли данное животное теплокровным. Левое ребро, отходящее от узла, представляет путь, по которому нужно проследовать, если ответ положителен, а правое ребро путь дальнейшего продвижения, если ответ отрицателен. Но, вообще говоря, в узле принятия решений для выбора ребра, по которому необходимо проследовать дальше, могут применяться любые критерии, при условии, что процесс выбора всегда приводит к получению решения, указывающего только на единственное ребро. Таким образом, в узлах принятия решений может выбираться ребро, со Глава 12. Примеры проектов экспертных систем ответствующее множеству или диапазону значений, ряду случаев или функциям, отображающим состояния, заданные в узле принятия решений, на ребра, исходящие из узла принятия решений. Структура узлов принятия решений может также быть настолько сложной, чтобы сих помощью осуществлялся перебор с возвратами или вероятностные рассуждения. Для иллюстрации процесса функционирования дерева решений рассмотрим следующие эвристические правила выбора вина, которое может подаваться на стол вместе с различными блюдами IF the main course is red meat THEN serve red wine IF the main course is poultry and it is turkey THEN serve red wine IF the main course is poultry and it is not turkey THEN serve white wine IF the main course is fish THEN serve white wine Представление этих эвристических правил по выбору вина в виде бинарного дерева решений показано на рис. 12.1. Узлы принятия решений сформированы на основе предположения, что на каждый вопрос может быть получен только положительный или отрицательный ответ. На тот случай, что главным блюдом не является ни черное мясо (баранина, говядина, ни мясо домашней птицы, ни рыбак множеству эвристических правил добавлен применяемый по умолчанию узел ответа, содержащий ответ "наиболее подходящий тип вина неизвестен. Процедура прохождения по дереву и достижения узла ответа весьма проста. Процесс логического вывода начинается с того, что текущее местонахождение в дереве решений устанавливается на корневой узел. Если текущим местонахождением является один из узлов принятия решений, то необходимо дать в определенной форме ответ на вопрос, связанный сданным узлом принятия решений (как правило, такой ответ предоставляет лицо, получающее консультацию с использованием дерева решений). Если ответ является положительным, то текущее местонахождение устанавливается на дочерний узел, соединенный с ребром положительного ответа (или левым ребром, отходящим от текущего местонахождения. Если ответ на вопрос является отрицательным, тов качестве текущего местонахождения устанавливается дочерний узел, соединенный с ребром отрицательного ответа (или с правым ребром), отходящим от узла текущего местонахождения. Если в какой- либо момент времени текущим местонахождением становится узел ответа, то значение узла ответа рассматривается как ответ, полученный логическим путем с помощью проведения консультации на основе дерева решений. В противном случае процедура обработки узлов принятия решений продолжа- 12.3. Деревья решений 957 Рис. 12.1. Бинарное дерево решений ется до тех пор, пока не будет достигнут один из узлов ответа. Ниже приведен псевдокод для такого алгоритма Solve Binary Tree Set the current location in the tree to the root node. while the current location is а decision node do Ask the question at the current node. if the reply to the question is yes Set the current node to the yes branch. else Set the current node to the по branch. end if end do Return the answer at the current node. end procedure Деревья решений с несколькими ребрами При использовании деревьев решений, которые допускают формирование только узлов принятия решений с бинарными ребрами, затрудняется представление решений, допускающих множество ответов или ряд случаев. Наглядным приме Глава 12. Примеры проектов экспертных систем 958 Рис. Дерево решений с несколькими ребрами procedure Solve Tree Set the current tree location to the root node. while the current location is а decision node do Ask the question at the current node until an answer in the set of valid choices for this node has been provided. Set the current node to the child node of the branch associated with the choice selected. end do ром низкой эффективности таких деревьев решений может служить бинарное дерево решений, подготовленное для решения задачи с выбором вина. В том случае, если основным блюдом является рыба, приходится принимать три решения, для того чтобы определить, что вином наиболее подходящего типа является белое вино отвечать на вопросы "Является ли основным блюдом черное мясо, "Является ли основным блюдом домашняя птица" и "Является ли основным блюдом рыба?" Гораздо более удобным вопросом, позволяющим кратко представить данный узел принятия решений, мог бы стать следующий вопрос "Что является основным блюдом" Узел принятия решений, способный обрабатывать подобный вопрос, должен допускать выбор одного из нескольких ребер с учетом ряда возможных решений (в данном случае — черное мясо, домашняя птица, рыба и т.д.). На рис. 12.2 показано модифицированное дерево решений, впервые приведенное на рис. 12.1, которое теперь допускает использование нескольких ребер такая возможность достигнута благодаря описанной ниже простой модификации алгоритма Solve BinaryTree. 959 12.3. Деревья решений Return the answer at the current node. end procedure Деревья решений, позволяющие проводить обучение Иногда возникает необходимость вводить в деревья решений новые знания в процессе их обучения в качестве примера подобного приложения принято использовать дерево решений для идентификации животных. После достижения в дереве решений некоторого ответа приложение выводит вопрос пользователю, является ли ответ правильными в случае подтверждения какие-либо дальнейшие действия не предпринимаются. Но если ответ оказался неправильным, то дерево решений модифицируется в целях включения правильного ответа. Узел ответа заменяется узлом принятия решений, который содержит вопрос, позволяющий провести различие между старым ответом, присутствовавшим в этом узле, и ответом, который не был угадан правильно. На рис. показано дерево решений, которое позволяет определить вид животного по его характерным признакам. Это дерево решений является весьма упрощенным (в нем имеется информация только о трех животных) и необходимо провести обучение этого дерева. Рис. 12.3. Дерево решений для идентификации животных В качестве примера рассмотрим сеанс выдвижения предположений с помощью этого дерева решений, который может проходить следующим образом Is the animal warm- blooded? (yes or по) yesJ Does the animal purr? (yes or по) noJ I guess it is а dog Am I correct? (yes or по) noJ What is the animal? birdJ Глава 12. Примеры проектов экспертных система а dog? Does the animal fly?J Now I can guess bird Try again? (yes or по Рис. 12.4. Дерево решений для идентификации животных после обучения распознаванию птиц Ниже приведен псевдокод, позволяющий модифицировать алгоритм Solve Tree таким образом, чтобы в нем была реализована возможность обучения Solve Tree and Learn Set the current location in the tree to the root node while the current location is а decision node Такой сеанс может продолжаться неограниченно долгов ходе чего дерево решений будет воспринимать в процессе обучения все больше и больше информации. На рис. 12.4 показано представление того же дерева решений, но после проведения описанного выше сеанса. Но обучение в такой форме имеет один недостаток — в конечном итоге полученное дерево решений может либо не иметь качественную иерархическую структуру, либо не отличаться очень высокой эффективностью выработки предположений, касающихся наиболее подходящего животного. Эффективное дерево решений должно иметь примерно одинаковое количество ребер от корня к узлам ответов по всем путям 12.3. Деревья решений Ask the question at the current node. if the reply to the question is yes Set the current node to the yes branch. else Set the current node to the по branch. end if end do Ask if the answer at the current node is correct ° if the answer is correct Return the correct answer. else Determine the correct answer. Determine а question which when answered уев will distinguish the answer at the current node from the correct answer. Replace the answer node with а decision node that has as its по branch the current answer node and as its yes branch an answer node with the correct answer. The decision node's question should be the question which distinguishes the two answer nodes. end if end procedure Программа для работы с деревом решений, основанная на правилах Первый шаг к выяснению того, как может быть реализовано в языке CLIPS обучающееся дерево решений, состоит в создании наиболее подходящего варианта представления знаний. Поскольку дерево решений должно обеспечивать обучение, по-видимому, целесообразно представить дерево в виде фактов, а не правил, в связи с тем, что факты могут быть легко добавлены и удалены для обновления дерева входе его обучения. Для перехода по дереву решений входе реализации алгоритма Solve Tree and Learn с использованием подхода на основе правил может применяться множество правил CLIPS. Каждый узел дерева решений будет представлен в виде факта. Для представления и узлов ответов, и узлов принятия решений будет использоваться следующая конструкция de f template: 962 Глава 12. Примеры проектов экспертных систем (с1еftåmðlàtå node (slot name) (slot type) (slot question) (slot yes- node) (slot no-node) (slot answer)) В этом определении слот пате содержит уникальное имя узла, а слот type обозначает тип узла и содержит значение answer или decision. Слоты question, yes — node и по используются только в узлах принятия решений. Слот question содержит вопрос, который должен быть задан при переходе к узлу принятия решений. Слот yes — node указывает на узел, к которому должен быть выполнен переход, если ответ на вопрос является положительным, а слот по — node указывает на узел, к которому должен быть выполнен переход, если ответ на вопрос является отрицательным. Слот answer используется только в узлах ответа и представляет собой ответ, формируемый деревом решений после перехода к узлу ответа. Поскольку эта программа идентификации животных должна обучаться, то возникает необходимость сохранять информацию о том, что было усвоено программой в процессе обучения от одного прогона к другому. В данном случае для представления структуры дерева решений используется коллекция фактов, поэтому было бы удобно сохранять эти факты в файле с применением формата команды load — facts, затем вносить их в список фактов с помощью команды load — facts вначале работы программы и снова сохранять с использованием команды save — facts после завершения работы программы. Факты, предназначенные для этой программы, хранятся в файле animal dat. Если в качестве исходного дерева решений используется дерево, показанное на рис. 12.3, то файл animal . dat должен содержать текст, приведенный ниже. Обратите внимание на то, что корневой узел (гоо t) обозначен как таковой, а каждому из прочих узлов присвоено уникальное имя. Кроме того, следует отметить, что некоторые слоты (такие как decision, yes — node и по — node для узлов ответа) остаются незаданными, поскольку им должны присваиваться значения, предусмотренные по умолчанию (а для разрабатываемой программы неважно, какие значения будут помещены в эти слоты. (node (name root) (type decision) (question "Is the animal warm-blooded?" ) (yes-node node1) (по node2)) (node (name node1) (type decision) (question "Does the animal purr?") (yes-node node3) (no-node node4)) 12.3. Деревья решений 963 (node (name node2) (type answer) (answer snake)) (node (name node3) (type answer) (answer cat)) (node (name node4) (type answer) (answer dog)) Теперь необходимо разработать правила, применяемые для прохождения по дереву решений. Инициализация программы обучения дерева решений осуществляется с помощью следующего правила (defrule initialize (not (node (name root))) => (load-facts "animal.dat") (assert (current-node root))) Запуск этого правила initialize происходит, если в списке фактов отсутствует факт, соответствующий корневому узлу. Действия, предусмотренные в правиле initialize, обеспечивают загрузку представления дерева решений в список фактов и внесение в список фактов того факта, который указывает, что текущим узлом, представляющим интерес, является корневой узел. Ниже приведены конструкция def function и правило, которые выводят вопрос, связанный с узлом принятия решений, а затем вносят в список фактов тот факт, который содержит ответ на вопрос по (?question) (printout t ?question " (yes or по) ") (bind ?answer (read)) (while (and (neq ?answer yes) (neq ? answer по) (printout t ?question " (yes or no) ") (bind ?answer (read))) (return ?answer)) (defrule ask-decision-node-question ?node <- (current-node ?name) (node (name ?name) (type decision) (question ?question)) (not (answer ?)) > (assert (answer (ask-уев-or- по ?question)))) Второй шаблон согласуется с текущим узлом, только если этот узел представляет собой узел принятия решений. В третьем шаблоне проверяется, что ответ на заданный вопрос еще не получен. Конструкция def function с именем ask — yes — or — no, применяемая в правой части правила, позволяет повторно задавать вопрос до тех пор, пока не будет получен один из допустимых ответов 964 Глава 12. Примеры проектов экспертных систем yes или по. После получения ответа на вопрос запускается одно из следующих правил (defrule proceed-to-yes-branch ?node <- (current-node ?name) (node (name ?name) (type decision) (yes- node ?yes-branch)) ?answer <- (answer yes) — > (retract ?node ? answer) (assert (current-node ?yes-branch))) (defrule по- branch ?node <- (current-node ?name) (node (name ?name) (type decision) (по ?no-branch)) ?answer <- (answer по) — > (retract ?node ?answer) (assert (current-node ?no-branch))) В обоих правилах извлекается факта затем вместо него в список фактов вносится новый факт, зависящий от ответа на вопрос. Факт с ответом извлекается для того, чтобы снова было активизировано правило askdecision-node-question. Следующее правило обеспечивает вывод вопроса о том, было ли предположение, представленное в узле, приемлемым это правило действует аналогично правилу ask — decision — node — question: (defrule ask-if-answer-node-is-correct ?node <- |