3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...

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

Списки нередко употребляют для представления множеств. Такое 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... внедрение списков имеет тот недочет, что проверка принадлежности элемента огромному количеству оказывается достаточно неэффективной. Для более действенной реализации дела принадлежности используют разные древовидные структуры, а именно, двоичные деревья.

Существует много методов представления двоичных деревьев на 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... Прологе. Более обычный метод: избрать особый знак для обозначения пустого дерева и функтор для построения непустого дерева из 3-х компонент (корня и 2-ух поддеревьев). Создадим последующий выбор.

Пусть атом nil 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... представляет пустое дерево. В качестве функтора примем tr, так что дерево с корнем X, левым поддеревом L и правым поддеревом R будет иметь вид терма tr(L,X,R).

С двоичным деревом легче работать 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., если оно упорядочено. Такое дерево именуется двоичным справочником. Чтоб можно было выстроить такое дерево, определим отношение "добавить лист" (adlist). Правила прибавления частей на уровне листьев таковы:

- итог прибавления элемента X 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... к пустому дереву есть дерево tr(nil,X,nil).

- если X совпадает с корнем дерева D, то лист не добавляется.

- если корень дерева D больше, чем X, то X вносится в левое поддерево дерева 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... D;

- если корень меньше чем X, то X вносится в правое поддерево.

adlist( nil, X, tr( nil, X, nil )).

adlist(tr( L, X, R ), X, tr( L, X, R )).

adlist(tr 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...( L, K, R ), X, tr( L1, K, R )):-

X < K, adlist( L, X, L1 ).

adlist(tr( L, K, R ), X, tr( L, K, R1 )):-

X > K, adlist( R, X, R1 ).

Для построения дерева 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... введем цикл while. В итоге работы двоичное дерево будет записано в базу данных.

domains

tre = tr( tre, integer, tre); nil

database

ntree( tre )

predicates

tree( tre )

adlist( tre, integer, tre )

while( integer, tre )

clauses

tree(tr(tr 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...( nil, 6, nil ), 8,

tr(tr( nil, 10, nil ), 9, nil ))). % Пример двоичного дерева

adlist( nil, X, tr( nil, X, nil )).

adlist(tr( L, X, R ), X, tr( L, X, R )).

adlist(tr( L, K, R 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... ), X, tr( L1, K, R)):-

X < K, adlist( L, X, L1 ).

adlist(tr( L, K, R ), X,tr( L, K, R1 )):-

X > K, adlist( R, X, R1 ).

while( 999, D ):- asserta( ntree 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...( D )), !.

while( X, D):- adlist( D, X, D1 ), readint( X1 ), while( X1, D1 ).

Goal

while( 7, nil ), ntree( X ).

Юзеру будет нетрудно выстроить отношение принадлежности верхушки X дереву T, которое поистине, если X 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... есть одна из вершин дерева T.
^ 3.9. Программки систематизации
Эти программки систематизации представляют собой на самом деле макет некой экспертной системы, так как реализуют собой основной блок экспертной системы – вывод на познаниях, которые представлены в 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... виде совокупы фактов и правил.

Основой задач систематизации является так называемое решающее дерево. Информация представлена в виде иерархической структуры классификационных правил типа «Если – То» Тут мы разглядим вопросно-ответную систему, которая является примером 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... маленький экспертной системы в том смысле, что программка варьирует процесс опроса зависимо от событий; более того, она может задавать мало нужное число вопросов.

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



Рис. Классификационное дерево


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

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

^ Если животное имеет шерсть

И кормит детенышей молоком

То животное является млекопитающим

Таким же образом можно перейти к последующему уровню дерева 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... от млекопитающего к хищнику:

^ Если млекопитающее имеет острые зубы

И имеет когти

И имеет глаза, направленные вперед

То млекопитающее является хищником

И, в конце концов, переход к нижнему уровню:

^ Если хищник имеет рыжеватый цвет

И имеет 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... темные полосы

То хищник является тигром

Программка систематизации может быть реализована с прямой либо оборотной цепочкой рассуждений. Оборотная цепочка рассуждений может быть удачно использована к задачкам, в каких имеется всего несколько решений при наличии 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... огромных объемов входной инфы. В данном случае целенаправлено избрать одно из вероятных решений, а потом собрать все свидетельства, которые могут его подтвердить либо опровергнуть.
^ 3.9.1. Программка систематизации с оборотной цепочкой рассуждений
Первой приведем пример 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... версии программки с оборотной цепочкой рассуждений, т.к. она поближе к встроенному в Пролог механизму вывода, и, как следует, реализуется довольно прямолинейно.

Оборотная цепочка рассуждений подразумевает продвижение от цели 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., в нашем случае от опознаваемого животного. Структура версии с оборотной цепочкой рассуждений проектируется введением группы правил высочайшего уровня, т.е. включающих в себя несколько правил. Каждое такое правило обрисовывает одно животное, Дадим описание нескольких животных 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...:

animal_is(“тигр”) :– i

t_is(“млекопитающее”),

it_is(“хищник”),

positive(“имеет”, “рыжеватый цвет”),

positive(“имеет”, “темные полосы”).

animal_is("гепард") :–

it_is("млекопитающее"),

it_is("хищник"),

positive("имеет","рыжеватый цвет"),

positive 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...("имеет", "темные пятна").

animal_is("зебра") :–

it_is("копытное"),

positive("имеет","темные полосы").

animal_is("пингвин") :–

it_is("птица"),

negative("умеет", "летать"),

positive("умеет", "плавать"),

positive("имеет", "черно-белый цвет 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...").

Схожие правила должны быть для всех животных, которых предстоит систематизировать программке.

Все правила поддерживаются на последующем, более малом уровне некими соподчиненными предикатами:

it_is("млекопитающее") :–

positive("имеет", "шерсть"),

positive("кормит", "детенышей молоком").

it 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..._is("хищник") :–

positive("имеет", "острые зубы"),

positive("имеет", "когти"),

positive("имеет", "глаза, направленные вперед").

it_is("копытное") :–

it_is("млекопитающее"),

positive("имеет", "копыта"),

positive("жует", "жвачку").

Свою работу программка начинает с использования правила

Goal 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... animal_is(X), !,

write("Отгаданное животное ", X),

retractall( _ ).

Дальше система пробует по очереди установить истинность либо ложность правил высочайшего уровня, т.е. отыскать кандидата, которого она сумеет проверить на соответствие предикату 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... animal_is.

Определение истинности такового правила тянет за собой проверку всего дерева подчиненных фактов и свидетельств, которые должны быть настоящими, чтоб подтвердить основное заключение. По мере продвижения вниз по дереву программка соответственно 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... ситуации задает нужные вопросы в необходимое время для получения недостающей инфы, потому ее поведение кажется разумным. Большая часть работы совершается правилами positive и negative, xpositive и xnegative. Они употребляются для проверки определенных 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... атрибутов животных, которые могут быть обнаружены в процессе диалога и записаны в базу данных.

Тут задействован механизм вопросов-ответов, потому нам нужно тщательно разглядеть эти правила. Ниже следует соответственная часть программки.

database

xpositive( symbol, symbol 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... )

xnegative( symbol, symbol )

Clauses

positive( X, Y ) :– % Положительный ответ найден

xpositive( X, Y ), !. % в базе данных

positive( X, Y ):–

xnegative( X, Y ), !, fail. % Отрицательный ответ найден в базе данных

positive( X, Y ) :– % Задается вопрос, для 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... которого

ask( X, Y, yes ), !. % ожидается положительный ответ

ask( X, Y, yes ) :–

write( X, " оно ", Y, “?\n”),

readchar( Reply ),

ans_pos( X, Y, Reply ).

ans_pos( X, Y, 'y' ):– assertz( xpositive( X, Y 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... )).

ans_pos( X, Y, 'n' ):– assertz( xnegative( X, Y )), !, fail.

Когда механизм вывода доходит до места, где требуется выяснить, был ли установлен некий атрибут животного, он употребляет правила positive и negative. (Тут 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... у нас приведен предикат positive, соответственный положительному значению атрибута. Схожий по работе с ним предикат negative записывается симметрично.)

1-ая из статей предиката positive принуждает систему конкретно просмотреть информацию, уже включенную в базу данных 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной.... Если атрибут в ней найден, процесс завершается. 2-ое правило этого предиката инициирует поиск отрицания того, что мы пытаемся установить, и если оно найдено, значение атрибута становится неверным, система перебегает к 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... проверке последующего правила animal_is. Если же фактов нет посреди настоящих и неверных, программка задает вопрос юзеру, при всем этом хоть какой приобретенный ответ запоминается с целью конкретного либо следующего внедрения.

Все факты 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., что программка помещает в базу данных, всегда имеет вид пары, состоящей из глагола и характеристики, к примеру:

xpositive("имеет","перья").

Потому просто сделать грамматически правильное предложение для предъявления его юзеру, поставив слово "оно 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..." меж глаголом и свойством. Юзер, возможно, введет знаки "y" либо "n" в ответ на запрос, а запоминающее правило внесет информацию в базу данных средством 1-го из 2-ух предикатов:

xpositive (verb, attribute)

xnegative 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... (verb, attribute).

Можно просмотреть протокол диалога после его окончания, если сохранить содержимое динамической памяти под любым именованием. Команда сохранения, к примеру, может иметь вид: save(“mybd”).

Для проведения повторной консультации с программкой следует 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... поначалу очистить динамическую базу данных от ответов на вопросы, данные при ведении последнего диалога. Они продолжают находиться в базе данных и будут оказывать влияние на последующие результаты, если их не 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... удалить. Сделать это можно при помощи стандартных предикатов чистки динамической базы данных. Предикат retrectall( _ ) позволяет удалить все факты, т.е. на сто процентов очистит динамическую память.
^ 3.9.2. Программки систематизации с прямой цепочкой рассуждений 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной....
Стратегия прямого вывода заключается в том, что задается последовательность вопросов, построенных таким макаром, что любой из их позволяет откинуть огромную группу возможных ответов, по этому существенно сужается место поиска. Так длится до того времени 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., пока не остается один определенный ответ. Движение начинается с корня классификационного дерева и завершается в концевой верхушке, продвижение по дереву направляется данными, т.е. дополнительной информацией, получаемой в процессе диалога 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной....

Животные классифицированы в разные категории, имеющие соответствующие черты: млекопитающие, хищники, копытные и т.д. Одна категория перебегает в другую при выполнении неких критерий. К примеру, категория «хищник» перебегает в категорию «гепард», если производятся 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... условия: «животное имеет рыжеватый цвет", "имеет животное черные пятна».

Познания в этой системе представляют собой правила, имеющие вид:

rule( N, CAT1, CAT2, COND ).

Тут N - порядковый номер правила,

^ CAT1 - выражение, стоящее в 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... левой части правила и характеризующее признак класса (подкласса и т.д.), к которому относится данное правило;

CAT2 - содержание правила в правой части, содержащее вывод из этого правила;

^ COND - перечень номеров критерий 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., определяющих правило.

Условие имеет вид:

cond( N, CONDTEXT ),

где N - номер условия,

CONDTEXT - текст условия.

Таким макаром, база познаний рассматриваемой экспертной системы последующая:

rule( 1, "хищник", "гепард", [ 1, 2 ] )

rule( 2, "хищник", "тигр", [ 1, 3 ] )

rule( 3, "копытное", "жираф", [ 5, 4, 2 ] )

rule 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...( 4, "копытное", "зебра", [ 3 ])

rule( 5, "птица", "страус", [5, 7 ] )

rule( 6, "птица", "пингвин", [ 9, 7 ] )

rule( 7, "птица", "альбатрос", [ 10 ] )

rule( 8, "животное", "млекопитающее", [ 11,12 ] )

rule( 9, "животное", "птица", [ 8, 13 ] )

rule( 10, "млекопитающее", "хищник", [ 14, 15, 16 ] )

rule( 11, "млекопитающее", "копытное", [ 17, 18 ] )

cond( 1, "оно имеет рыжеватый цвет" )

cond( 2, "оно имеет черные 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... пятна" )

cond( 3,"оно имеет темные полосы" )

cond( 4, "оно имеет длинноватую шейку" )

ond( 5, "оно имеет длинноватые ноги" )

cond( 6, "оно летает" )

cond( 7, "оно имеет темный и белоснежный цвет" )

cond( 8, "оно имеет перья 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..." )

cond( 9, "оно плавает" )

cond( 10, "оно летает отлично" )

cond( 11, "оно имеет шерсть" )

cond( 12, "оно кормит детенышей молоком" )

cond( 13, "оно откладывает яичка" )

cond( 14, "оно ест мясо" )

cond( 15, "оно имеет когти" )

cond( 16, "оно имеет острые зубы 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..." )

cond( 17, "оно жует жвачку" )

cond( 18, "оно имеет копыта" )

Просто созидать, что таковой метод представления познаний реализует конструкцию вида ЕСЛИ-ТО:

если ^ САТ1 отвечает условиям СOND, то САТ1 есть САТ2. С другой стороны, отношение rule 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... очень похоже на продукционное правило, дополненное перечнем истинности внедрения продукции. Продукционное правило позволяет использовать рекурсивный механизм продвижения по дереву, что и употребляется в истинной реализации.

В целом все описание соответствует древовидной структуре 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... представления инфы, в которую отлично вписываются разные классификационные системы. Такая программка организует диалог с юзером в процессе консультаций, модификацию базы познаний, также имеет систему разъяснений.

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

yes(N) либо no(N 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...),

где N - номер условия, являющегося первым аргументом предиката cond.

Главным рабочим предикатом ЭС является рекурсивный предикат go. Этот предикат организует просмотр дерева базы познаний, выделение еще одного правила и выдачу 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... советов в случае заслуги концевой верхушки классификационного дерева. Он также позволяет хранить предысторию процесса консультации (т.е. набор использованных правил) для реализации системы разъяснений.

go( _ , Mygoal ):- /*Цель достигнута */

not(rule( _ , Mygoal, _ , _ )),

write 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...( "Отгаданное животное: ",Mygoal ).

go( HISTORY, Mygoal ):-

rule( RNO, Mygoal, NY, COND ),

check( RNO, HISTORY, COND ),

go( [ RNO | HISTORY ], NY ).

1-ое правило предиката go является базисным для рекурсии, оно соответствует достижению конечной верхушки 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... (в базе данных нет правила rule, где конечная верхушка дерева стоит вторым аргументом). Если конечная верхушка не достигнута, работает рекурсивное правило предиката go. Выбирается еще одно правило rule из базы данных 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной....

Предикат check, входящий во 2-ое правило предиката go, производит проверку перечня критерий COND на достоверность, т.е. делает поиск уже имеющихся фактов, относящихся к данным условиям. Если ответ на эти условия имеется 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... в базе данных в виде фактов yes(BNO) либо no(BNO), проверка на этом завершается. В случае, если требуемые факты не обнаружены, определяется запрос юзеру при помощи предиката inpq. Если проверка check 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... завершается неверно, то выбирается последующее правило из базы познаний. Если же проверка успешна, номер правила присоединяется к списку удачных правил HISTORY, по которому можно вернуть историю поиска, а текущей целью становится 3-ий аргумент 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... правила rule, что значит переход к последующему уровню дерева:

check( RNO, HISTORY, [ BNO | REST ] ) :- yes( BNO ), !, % Ответ “yes” найден

check( RNO, HISTORY, REST ).

check( _ , _ , [ BNO | _ ] ) :- no( BNO ), !, fail. % Ответ “no” найден

check( RNO, HISTORY, [ BNO 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... | REST ] ) :-

cond( BNO, TEXT_COND ),

inpq( HISTORY, RNO, BNO, TEXT_COND ),

check( RNO, HISTORY, REST ).

check( _ , _ , [ ] ).

Предикат inpq запускает диалоговый механизм, средством которого система получает недостающую информацию. Система задает юзеру вопросы, представляющие из 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... себя условия истинности определенного правила, при всем этом юзер может ответить “yes”, “no” либо “why”. 3-ий ответ значит, что юзеру необходимо знать, почему система задала таковой вопрос. В данном случае 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... намерения системы демонстрируются в виде цепочки правил и целей, соединяющих эту информацию с начальным вопросом.

inpq( HISTORY, RNO, BNO, TEXT_COND ) :-

write( "Это правда, что ", TEXT_COND),

readln( ANS ),

do_answer( HISTORY, RNO 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., TEXT_COND, BNO, ANS ).

Предикат do_answer организует заполнение базы данных новыми фактами, приобретенными в процессе диалога с юзером, также реализует систему разъяснений, которая предоставляет юзеру набор правил, на основании 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... которых было принято то либо другое решение:

do_answer( _ , _ , _ , BNO, “yes” ) :- assert( yes( BNO )), write( yes ), !. % Ответ “yes”

do_answer( _ , _ , _ , BNO, “no” ) :- assert( no( BNO )), write(no), !, fail. % Ответ “no”

do_answer( HISTORY 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., RNO, TEXT_COND, BNO, “why” ) :- !, % Ответ “why”

rule( RNO, Mygoal1, Mygoal2, _ ),

sub_cat(Mygoal1,Mygoal2,Lstr),

concat("I try to show that: ",Lstr,Lstr1),

concat(Lstr1,"\nBy using rule number ",Ls1),

str 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..._int(Str_num,RNO),

concat(Ls1,Str_num,Ans),

show_rule(RNO,Lls1),

concat(Ans,Lls1,Ans1),

report(HISTORY,Sng),

concat(Ans1,Sng,Answ),

display(Answ),

do_answer(HISTORY,RNO,TEXT 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...,BNO, ANS).

Вдумчивый читатель мог увидеть, что программка отличается от предшествующей по своим способностям, а конкретно: перечень критерий содержит только положительные признаки. Преодолеть этот недочет можно, по-видимому, различными методами: или внести отрицание на уровне 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... строковых констант («оно не летает»), или дополнить отношение rule еще одним аргументом – перечнем негативных признаков, что является более грамотным.

Такая экспертная система может быть довольно легко преобразована в оболочку 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... экспертной системы, довольно базу фактов, представляющую базу познаний предметной области, вынести в динамическую память. Разделение базы данных и программки позволяет воплотить оболочку экспертной системы. Такая оболочка может быть настроена на всякую предметную область 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., которую можно представить в виде классификационного дерева. Программка можно дополнить модулями, присущими экспертной системе: модулем работы в режиме консультаций, блоком разъяснений, обеспечить способности просмотра, редактирования и пополнения базы познаний.

Разглядим еще одну задачку, реализуемую 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... при помощи прямой цепочки рассуждений, не использующую рекурсивный механизм поиска. Ровная цепочка на каждом шаге позволяет отбрасывать приблизительно половину оставшихся способностей, т.е. она употребляется, когда количество исходных состояний характеристик невелико, а 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... место состояний неуправляемо (огромное количество перестановок, сочетаний). Это может быть в случаях, когда характеристики независимы. Программка именуется: «Прогнозирование наводнения».

В качестве примера возьмем ситуацию, необходимо ли эвакуировать расположенный в горах маленькой городок 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... при опасности наводнения. Сначала, исходя из задачки, необходимо выявить причины, которые будут употребляться для прогноза:

1. Уровень воды в водоеме. Если уровень воды высок, то существует угроза наводнения. Уровень воды также может 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... повышаться за счет стоков дождика и талого снега.

2. Дождик. Если ожидаются обильные дожи и уровень воды высок, другими словами возможность наводнения.

3. Температура. Если предсказана теплая погода и с гор в реку стаяло 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... много снега, другими словами опасность наводнения.

4. Снег. В расчет принимается количество снега в горах.

В качестве атрибутов этих причин будут употребляться значения лингвистических переменных согласно нечеткой логике4: высочайший, маленький, не много 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., много, теплый и т.д.

Отметим, что эти причины, в главном, независимы и могут проявляться в разных сочетаниях. Прогноз, зависимо от сочетания причин, может принимать одно из 3-х значений: эвакуировать, усилить внимание, не 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... волноваться.

Как и ранее, представим базу познаний в виде дерева решений, а потом преобразуем его в правила вида ЕСЛИ-ТО. Дерево решений представлено на рис. 3….




Рис. 3. Дерево решений для системы прогнозирования наводнений

Для каждого 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... пути можно записать правило. Совокупа всех правил составит базу познаний.

^ ЕСЛИ НЕ (уровень воды высочайший)

И НЕ (дождик обильный)

ТО прогноз = не волноваться

ЕСЛИ НЕ (уровень воды высочайший)

И дождик обильный

И снегу 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... много

И температура высочайшая

ТО прогноз = усилить внимание

ЕСЛИ НЕ (уровень воды высочайший)

И дождик обильный

И снегу много

И НЕ (температура высочайшая)

ТО прогноз = не волноваться

ЕСЛИ НЕ (уровень воды высочайший)

И 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... дождик обильный

И НЕ (снегу много)

ТО прогноз = не волноваться

ЕСЛИ уровень воды высочайший

И дождик обильный

ТО прогноз = эвакуировать

ЕСЛИ уровень воды высочайший

И НЕ (дождик обильный)

И снегу много

И температура высочайшая

ТО прогноз 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... = эвакуировать

ЕСЛИ уровень воды высочайший

И НЕ (дождик обильный)

И снегу много

И НЕ (температура высочайшая)

ТО прогноз = усилить внимание

ЕСЛИ уровень воды высочайший

И НЕ (дождик обильный)

И НЕ (снегу много)

И НЕ (температура высочайшая)

ТО 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... прогноз = не волноваться

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

До сего времени все было как ранее. Сейчас начинается 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... увлекательная реализация. Сначало будет запущен предикат proverka, который внесет прогноз в динамическую базу данных. Извлечь его оттуда уже не представляет трудности (предикат prognoz).

start :- proverka,

prognoz( P ),

write( “Наш прогноз - ”, P ).

Предикат 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... proverka состоит из 4 тестов, любой из которых соответствует проверке 1-го из перечисленных причин:

proverka :- test1( F1 ), % Уровень воды

test2( F1, F2 ), % Дождик

test3( F1, F2, F3 ), % Снег

test4( F1, F2, F3, _ ). % Температура

proverka.

В процессе диалога переменные 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... F1, F2, F3 могут принимать одно из 2-ух значений: «y» либо «n». Прямой вывод будет направляться этими значениями, при этом ответы, приобретенные из предшествующего теста, будут употребляться как входные для следующих тестов 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной.... Приведем цепочки вывода:

test1( ‘y’ ) :- it_is( “уровень воды высочайший” ). % Проверка продолжится

test1( ‘n’ ). % Проверка продолжится

test2( ‘y’, ‘y’ ) :- it_is( “дождик обильный” ),

assert( prognoz( “эвакуировать” )). % Конец ветки

test2( ‘y’, ‘n’ ).

test2( ‘n’, ‘y 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...’ ) :- it_is( “дождик обильный” ).

test2( ‘n’, ‘n’ ) :- assert( prognoz( “не волноваться” )).

test3( ‘y’, ’n’, ‘y’ ) :- it_is( “снегу много”).

test3( ‘y’, ’n’, ‘n’ ) :- assert( prognoz( “не волноваться” )).

test3( ‘n’, ’y’, ‘y’ ) :- it_is( “снегу 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... много”).

test3( ‘n’, ’y’, ‘n’ ) :- assert( prognoz( “не волноваться” )).

test4( ‘y’, ‘n’, ‘y’ ,’y’ ) :- it_is( “температура высочайшая”),

assert( prognoz( “эвакуировать” )).

test4( ‘y’, ‘n’, ‘y’ ,’n’ ) :- assert( prognoz( “усилить внимание” ).

test4( ‘n 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...’, ‘y’, ‘y’ ,’y’ ) :- it_is( “температура высочайшая”),

assert( prognoz( “усилить внимание” )).

test4( ‘n’, ‘y’, ‘y’ ,’n’ ) :- assert( prognoz( “не волноваться” ).

It_is( X ) :- write( X, “?”), % Механизм диалога

readchar( A ), A = ‘y 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной...’.

Когда по какой-нибудь ветки достигается решение, факт прогноза помещается в динамическую базу данных.

Предикат proverka рассчитан на выполнение 4 проверок, хотя время от времени довольно 2-ух либо 3-х, при всем этом ответ 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... помещается в базу данных. Но предикат продолжает свою работу и пробует удовлетворить последующие испытания, что нереально. В итоге 1-ое правило предиката proverka завершится неверно, сработает 2-ой дизъюнкт. Ответ уже находится в динамической базе 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... данных, и извлечь его оттуда нетрудно.

Отметим, что в этой реализации программки систематизации ответы юзера не сохраняются, но при некой модификации нетрудно их запоминать и, соответственно, воплотить механизм разъяснений. Не считая того, можно разглядеть 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... случаи, когда лингвистическая переменная принимать не только лишь бинарные значения («снегу много» либо «снегу мало»), да и любые дискретные.

Когда правила логически обоснованы, т.е. употребляются дискретные другие данные (Да 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной.../Нет), удается написать довольно ординарную программку для получения определенных выводов. Но может быть использовать и непрерывные переменные. Если они носят вероятностный нрав, то нужен определенный способ обработки этих вероятностей. Есть разные подходы к реализации 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... неопределенностей в задачках поиска5.

Один из ранешних подходов к представлению неопределенностей использовал теорию вероятностей, позднее это механизм был заменен применением так именуемого коэффициента определенности импликации, либо убежденности (certainty factor 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., CF):

Если есть S то имеется D с уверенностью CF.

Значения коэффициента определенности лежат в спектре [ -1, +1 ].

С другой стороны, признак S тоже может проявиться с некой «силой», т.е. имеет собственный CF 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной.... Правило комбинирования, позволяющее вычислить коэффициент определенности заключения, когда известен коэффициент определенности посылки, лежащей в его базе, записывается так:

^ CF (заключение) = CF(посылка) * CF(импликация)

Посылка правила может состоять из нескольких атомарных посылок 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной..., любая из которых имеет собственный коэффициент определенности. Они могут быть связаны меж собой логическим операциями типа И, Либо, НЕ. Принято, что коэффициент определенности посылки равен коэффициенту определенности менее надежной из посылок:

CF( S1 И 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... S2) = min(CF( S1 ), CF( S2)).

Коэффициент определенности дизъюнкции посылок равен коэффициенту определенности наисильнейшей ее части:

CF( S1 Либо S2) = max(CF( S1 ), CF( S2)).

Если сделать допущение, что действия 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... независимы друг от друга, программка может быть реализована довольно легко. Продукционным правилам можно приписать числа, указывающие относительную значимость (вес) фактов:

rule(hypothesis A, AND((cond1, CF1), (cond2, CF2), …) .

Для реализации механизма вывода на 3.9. Представление множеств двоичными деревьями - Программы классификации 49 9 Программа классификации с обратной... таких познаниях полностью можно использовать рекурсивный метод, дополненный неким методом комбинирования посылок.


3v-kinematograficheskom-podpole-dzh-d-lasika-darknet-vojna-gollivuda-protiv-cifrovoj-revolyucii.html
3vipolnenie-raboti-metodicheskie-ukazaniya-dlya-studentov-3-5-kursov-fakulteta-matematiki-i-informacionnih-tehnologij.html
3zadachami-obrazovatelnogo-proekta-yavlyayutsya.html