Разработка базы знаний: дерево решений

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

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

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

На рис. 1 показано дерево решений для примера с приемом на работу. Видно, что диаграмма состоит из кружков и прямоугольников, которые называются вершинами. Каждой вершине присваивается номер. На вершины можно ссылаться по этим номерам. Линии, соединяющие вершины, называются дугами или ветвями. Кружки, содержащие вопросы, называются вершинами решений. Прямоугольники содержат цели диаграммы и означают логические выводы. Линии показывают направление диаграммы. Многие вершины имеют сразу по нескольку ветвей, связывающих их с другими вершинами. Выбор выходящей из вершины ветви определяется проверкой условия, содержащегося в вершине.

Рис. 1. Дерево решений для выбора должности

 

Преобразование дерева решений в правила

Процесс формирования правил для всех возможных логических выводов состоит из следующих шагов:
1. Выбрать из дерева решений вершину вывода (прямоугольник) и зафиксировать её.
2. Найти вершину решения (кружок), расположенную слева от выбранной вершины вывода и связанную с ней ветвью, и зафиксировать её.

Таблица 1
Таблица имён переменных

Имя переменной	Условия	Вершина (ы)
DEGREE	Посетитель имеет ученое звание?
DESCOVERY	Посетитель сделал важное открытие?
EXPERIENCE	Каков опыт работы в этой области?
GRADE	Каков средний балл посетителя за время учебы?
POSITION	Какая должность предложена посетителю?	2,6,8,9,10
QUALIFY	Возможно, посетитель будет принят на работу

З. Повторять шаг 2 до тех пор, пока не будут исчерпаны все вершины решения, расположенные левее зафиксированной вершины вывода, или не встретится новая вершина вывода. Если встретилась вершина вывода, то её надо зафиксировать и прекратить выполнение шага 2. - Выполнение также прекращается, если исчерпаны все вершины.
4. Каждая вершина решения, составляющая путь, - это одна из переменных части ЕСЛИ правила. Значение, связанное с ветвью, представляет собой условие. Переменные условной части правила объединяются логическим оператором И.
5. Выбранный логический вывод перенести в часть ТО правила.

 

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

Таблица 2
Правила ЕСЛИ-ТО

Правило	Путь
10 ЕСЛИ DEGREE - НЕТ, ТО POSITION-НЕТ 20 ЕСЛИ DEGREE - ДА, ТО QUALIFY-ДА 30 ЕСЛИ DEGREE - ДА И DISCOVERY - ДА, ТО POSITION - НАУЧНЫЙ СОТРУДНИК 40 ЕСЛИ QUALIFY- ДА И AVERAGE 3.5 И EXPERIENCE- 2, ТО POSITION - ИНЖЕНЕР ПО ЭКСПЛУАТАЦИИ 50 ЕСЛИ QUALIFY - ДА И AVERAGE - 3.5 И EXPERIENCE 2, ТО POSITION-НЕТ 60 ЕСЛИ QUALIFY - ДА И AVERAGE - 3.5, ТО POSITION - ИНЖЕНЕР-КОНСТРУКТОР	1,2 1,3 1,4,6 3,5,7,10 3,5,7,9 3,5,8

 

Работа с базой знаний

Приступим к реализации обратной цепочки рассуждений. База знаний должна использоваться для определения пути, ведущего к какому-либо логическому выводу.

Список логических выводов - это структура данных, содержащая упорядоченный список возможных логических выводов. Список состоит из номера правила, логического вывода, связанного с этим правилом, и условий, которые формируют вывод. На каждое правило базы знаний в списке приходится одна запись. Список логических выводов используется исключительно для поиска вывода по номеру правила. Когда условия части ЕСЛИ истинны, вызывается часть ТО, тем самым переменной логического вывода присваивается значение.

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

Структура данных, содержащая перечень всех переменных для всех условных частей правил, называется списком переменных условия.

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

Правило 10 ЕСЛИ DEGREE=НЕТ, ТО POSITION = НЕТ Правило 20 ЕСЛИ DEGREE ДА, TO QUALIFY = ДА Правило 30 ЕСЛИ DEGREE = ДА И, DISCOVERY = ДА ТО POSITION = НАУЧНЫЙ СОТРУДНИК Правило 40 ЕСЛИ QUALIFY = ДА И, GRADE < 3.5 И EXPERIENCE = 2 ТО POSITION= ИНЖЕНЕР ПО ЭКСПЛУАТАЦИИ Правило 50 ЕСЛИ QUALIFY = ДА И GRADE < 3.5 И EXPERIENCE = 2 ТО POSITION = НЕТ Правило 60 ЕСЛИ QUALIFY = ДА И GRADE >= 3.5 ТО POSITION = ИНЖЕНЕР КОНСТРУКТОР	1 POSITION 2 QUALIFY 3 POSITION 4 POSITION 5 POSITION 6 POSITION ———————— Список логических выводов	1 INTEREST 2 3 4 5 DEGREE 6 7 8 9 DEGREE 10 DISCOVERY 11 12 13 QUALIFY 14 GRADE 15 EXPERIENCE 16 17 QUALIFY 18 GRADE 19 EXPERIENCE 20 21 QUALIFY 22 GRADE
DEGREE DISCOVERY EXPEREIENCE GRADE ——————————— Список переменных Вершина стека
———————————————— База знаний	Номер Номер правила условия ———————————————— Стек логических выводов	———————— Список переменных условия

Рис. 2. База знаний и структуры данных

 

Пример использования базы знаний

Для того чтобы свести воедино все выше сказанное, рассмотрим полный цикл обработки экспертной системой запроса пользователя. Работа начинается с ввода пользователем логического вывода в форме вопроса: