Лучшие статьи журнала ╚Компьютеры+Программы╩

Здравствуйте, уважаемые читатели!

В этом выпуске рассылки публикуется статья, занявшая по результатам голосования третье место.

Владимир ТРОФИМОВ,
vovic@ukr.net

База данных + CLIPS = База знаний

Как придать базе данных интеллектуальность? Как включить в нее сведения о том, что следует делать с хранящимися в ней данными для последующего формирования суждений и выводов? Как превратить ее в базу знаний по своей предметной области? Отличным инструментом для решения указанных задач является язык проектирования экспертных систем CLIPS

Рождение языка CLIPS относится к 1984 году, когда в Отделе искусственного интеллекта Центра космических исследований NASA начались работы по созданию компьютерных программ, моделирующих человека-эксперта во время мониторинга и диагностики космических систем и комплексов различного назначения. Название языка представляет собой аббревиатуру от «C Language Integrated Production System», язык этот имеет интерпретируемое исполнение, а его назначение состоит в решении задач искусственного интеллекта — в частности, разработки экспертных систем.

Применительно к теме данной статьи из всех возможностей CLIPS нас, в первую очередь, будут интересовать те из них, что связаны с представлением знаний и взаимодействием с базой данных. Согласно Д. Кнуту (Кнут Д.Э., Искусство программирования. Том 3. Сортировка и поиск., 2-е изд.: Пер. с англ.- М.: Издательский дом «Вильямс», 2001.- 832 с.), элементом данных является запись или список. Несколько записей (списков) образуют таблицу или файл. Большой файл есть база данных. По Джексону (Джексон П., Введение в экспертные системы.: Пер. с англ.: Уч. пос.- М.: Издательский дом «Вильямс», 2001.- 624 с.), чтобы данные стали знаниями, они должны быть охарактеризованы функционально, то есть в терминах действия, а не в терминах структурной организации, как это делается в базе данных. База знаний — это база данных, в которой содержатся сведения о том, как эти данные могут быть использованы. Именно такой смысл будет вкладываться в понятия «база данных» и «база знаний» в дальнейших рассуждениях.

CLIPS располагает тремя механизмами представления знаний: процедурным, эвристическим и объектно-ориентированным. Рассмотрение последнего оставим на будущее — основное же внимание уделим первым двум.

Процедурный механизм позволяет пользователю при помощи встроенных в язык функций разрабатывать или конструировать новые функции, выполняющие некоторые полезные действия или возвращающие некоторые значения. В этом смысле CLIPS напоминает такие известные языки программирования, как С, С++ или Pascal. Так, для создания пользовательских функций используется конструктор deffunction, имеющий следующий синтаксис:

(deffunction имя_функции [необязательный комментарий] (список формальных параметров) (действие_1) (действие_2) ...... (действие_N))

Например, определим функцию om (x,y), которая возвращает целую часть частного от деления переменной y на переменную x:

(deffunction om ( ?x ?y) (div ?y ?x))

Обратите внимание на то, что в CLIPS имя переменной начинается с символа « ?», что для вызова функции (в данном случае — встроенной функции деления нацело div) используется префиксная нотация, а также на то, что вся конструкция представляет собой список, состоящий из четырех полей. Так что у CLIPS «ноги растут» не только из С (см. расшифровку аббревиатуры), но и из LISP.

Эвристический механизм представления знаний в CLIPS реализуется при помощи правил в форме

ЕСЛИ условие_1 и... и условие_N удовлетворяются, ТО ВЫПОЛНИТЬ действие_1 и... и действие_N.

Список условий называется левой частью правила (Left-Hand Side или LHS). Список действий называется правой частью правила (Right-Hand Side или RHS). Возможность применить конкретное правило определяется тем, удовлетворяются ли условия, которые сформулированы в его LHS. Удовлетворение или неудовлетворение происходит в момент сопоставления условий с так называемыми фактами, которые образуют ни что иное, как базу данных. В CLIPS такая база данных может представлять некоторую предметную область, исходное или текущее состояние какой-либо проблемы, может моделировать в пространстве или во времени поведение какой-либо системы или любой сущности, которую можно описать посредством множества записей в виде списков.

Существует несколько способов создания базы данных, один из них — использование конструктора deffacts. Его синтаксис таков:

(deffacts имя_базы_данных [необязательный комментарий] (факт_1) (факт_2) ..... (факт_N))

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

Если каждое условие в LHS находит себя среди фактов — происходит удовлетворение, активизация правила и выполнение ВСЕХ действий, записанных в его RHS. В противном случае правило не активизируется.

Работа правила очень напоминает условный оператор if-then, присутствующий во многих процедурных языках программирования. Принципиальная разница заключается в том, что оператор if-then выполнится в любом случае, когда до него дойдет очередь в программе. Что касается правила, то интерпретатор CLIPS еще подумает, выполнять его или нет. Так, при старте программы, содержащей множество фактов и правил, интерпретатор CLIPS запускает машину логического вывода, которая выясняет, какие из правил можно активизировать. Это выполняется циклически, причем каждый цикл состоит из трех шагов:

• сопоставление фактов и правил;
• выбор правила, подлежащего активизации;
• выполнение действий, предписанных правилом.

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

Для создания правила используется конструктор defrule, который имеет следующий синтаксис:

(defrule имя_правила [необязательный комментарий] [необязательное объявление] (условие_1) (условие_2) ...... (условие_M) => (действие_1) (действие_2) ...... (действие_N))

Обратите внимание: LHS отделяется от RHS комбинацией символов «=>» и количество условий и действий в правиле в общем случае не совпадает.

Самое время перейти к примерам — но прежде добавим еще одну мысль. В CLIPS процедурный и эвристический механизмы представления знаний могут тесно взаимодействовать путем вызова пользовательских функций как из LHS, так и из RHS.

Пример 1

Рассмотрим предметную область, которая представляет участников некоторой конференции, приехавших из разных городов Украины — например, Одессы, Киева и Львова. На подобных мероприятиях все участники обычно проходят регистрацию. Пусть эта процедура представляет собой ввод сведений об участниках в базу данных, в которой на каждого участника выделяется одна запись (факт), состоящая из списка с тремя полями. Пусть первое поле имеет символьное значение rep — сокращение от «representative» (представитель). В общем случае это значение может быть любым, а поле может отсутствовать. Во втором поле списка хранится фамилия участника, а в третьем — город, из которого участник прибыл. Содержимое фактов базы данных с именем rep может быть, например, таким:

(deffacts rep (rep Alejnov Odessa) (rep Ladak Odessa) (rep Slobodjanjuk Lvov) (rep Klitka Lvov) (rep Bojko Kiev) (rep Pustovit Odessa) (rep Spokojnij Odessa) (rep Shamis Odessa) (rep Lobovko Kiev) (rep Zadorozhna Lvov) (rep Javorskij Lvov)) (Примечание. Все приведенные выше фамилии выбраны абсолютно случайно и без какой-либо связи с реальными лицами.)

Используя любой текстовый редактор, создадим и сохраним базу данных в виде текстового ASCII-файла с именем, повторяющим имя базы данных (то есть rep). Это позволяет легко редактировать данные, независимо от каких-либо других программных модулей, добавляя новых участников или удаляя убывших.

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

(defglobal ?*odessa* = 0) (defglobal ?*kiev* = 0) (defglobal ?*lvov* = 0) (defrule start (initial-fact) => (printout t crlf «REPRESENTATIVES» crlf) (defrule odessa (rep ? Odessa) => (bind ?*odessa* (+ ?*odessa* 1))) (defrule kiev (rep ? Kiev) => (bind ?*kiev* (+ ?*kiev* 1))) (defrule lvov (rep ? Lvov) => (bind ?*lvov* (+ ?*lvov* 1))) (defrule result (declare (salience —1)) (initial-fact) => (printout t «from Odessa: « ?*odessa* crlf) (printout t «from Kiev: « ?*kiev* crlf) (printout t «from Lvov: « ?*lvov* crlf))

В первых трех строках программы при помощи конструктора defglobal объявляются и зануляются три глобальные переменные: ?*odessa*, ?*kiev* и ?*lvov*. Эти переменные есть счетчики. В CLIPS переменная может быть и локальной — но тогда она связывается только с тем правилом, в котором объявляется.

Далее следует правило с именем start, LHS которого представляет собой запись (initial-fact). Так обозначается системный начальный факт, который создается в рабочей памяти интерпретатора CLIPS по команде (reset) до запуска программы на выполнение. Для чего он нужен ? Дело в том, что в CLIPS-программах распространенными правилами являются такие, которые добавляют факты в базу данных — либо, наоборот, удаляют их. Типичной является ситуация, когда при старте программы в базе данных нет фактов, удовлетворяющих хотя бы одному правилу. В этом случае программа ничего не выполнит. Для того чтобы начать вычисления и используется системный начальный факт, который, независимо от фактов в базе данных, активизирует некоторое правило, добавляющее такие факты, которые, в свою очередь, активизируют правила, неудовлетворенные в начальный момент.

В данной программе (initial-fact) запускает правило start, которое активизируется независимо от фактов в файле rep и присутствует в программе только с одной целью — вывести заголовок. Для этого в его RHS вызывается встроенная функция printout с ключом t, выводящая на стандартное устройство вывода (монитор) заголовок, заключенный в кавычки. Комбинация символов crlf — аналог манипулятора endl в С++.

Следующие три правила с именами odessa, kiev и lvov можно назвать ядром программы. В них производится подсчет количества участников — соответственно, из Одессы, Киева и Львова.

Рассмотрим, например, правило lvov. Оно активизируется в том случае, когда в базе данных находится факт (rep ? Lvov). Не трудно догадаться, что символ « ?» во втором поле этого списка означает символ универсальной подстановки и заменяет собой любую фамилию. Отсюда следует, что правило lvov активизируется столько раз, сколько раз факт (rep ? Lvov) присутствует в базе данных. При этом столько же раз выполнятся действия, содержащиеся в RHS правила. Встроенная функция bind — аналог оператора присваивания. Следовательно, в RHS содержимое переменной ?*lvov* увеличивается на единицу и результат сохраняется в этой же переменной. Аналогично работают правила odessa и kiev.

Действия, которые выполняются в последнем правиле программы, отражены в его названии. RHS правила особых комментариев не требует, в то время как LHS заслуживает подробного рассмотрения. В CLIPS существует несколько стратегий очередности выполнения правил, а сами правила могут иметь приоритет, который задается встроенной функцией declare с параметром salience (выпуклость). Этот параметр может принимать целочисленные значения от —10000 до +10000. По умолчанию для всех правил величина salience равна нулю. Если в правиле result не указать приоритет, оно будет конфликтовать с правилом start за очередность выполнения, так как у этих правил одинаковая LHS. Для устранения конфликта в правиле result приоритет указан явно и со знаком минус, в связи с чем это правило выполнится последним.

Используя любой текстовый редактор, наберем и сохраним текст программы в ASCII-файле со стандартным для CLIPS-программ расширением.clp и с именем represent. Дальше посмотрим, что из всего этого получилось при работе с консоли в среде Linux. Командой clips вызовем интерпретатор CLIPS, командой (load имя_файла) загрузим в интерпретатор файлы rep и represent.clp, командами (reset) и (run) запустим программу represent.clp на выполнение.

[vovic@localhost vovic]$ clips CLIPS (V6.10 07/01/98) CLIPS> (load rep) ......... TRUE CLIPS> (load represent.clp) ......... TRUE CLIPS> (reset) CLIPS> (run) REPRESENTATIVES from Odessa: 5 from Kiev: 2 from Lvov: 4 CLIPS>

Сообщение интерпретатора TRUE означает, что в файле нет синтаксических ошибок и команда загрузки выполнена корректно. Многоточием представлены другие сообщения интерпретатора, которые в данном случае опущены.

Как следует из описанных действий, в интерпретаторе CLIPS находятся два файла. Первый, с именем rep, является базой данных. Второй, с именем represent.clp, содержит сведения (правила) о том, как эти данные могут быть использованы. Таким образом, вместе файлы образуют базу знаний, которая содержит, по крайней мере, два знания. Первое — общий состав участников конференции. Его можно посмотреть, не выходя из интерпретатора по команде (facts). Второе знание — количество участников от каждого города.

Такая база способна обучаться. Каким образом ? Путем добавления новых правил. Пусть имеющиеся знания надо дополнить знанием об участниках (пофамильно), приехавших на конференцию из Одессы. Алгоритм решения очевиден — надо удалить из базы данных все факты, в которых третье поле списка имеет значение Kiev или Lvov. Следующие правила выполняют такое действие.

(defrule whithout-kiev ?kiev <- (rep ? Kiev) => (retract ?kiev)) (defrule whithout-lvov ?lvov <- (rep ? Lvov) => (retract ?lvov)) (defrule result (declare (salience —1)) (initial-fact) => (retract 0) (facts) (save-facts «odessa»))

В CLIPS удаление факта выполняется командой retract с указанием индекса удаляемого факта либо переменной, с которой факт связывается. Значение индекса (целое число) факты получают автоматически при загрузке базы данных в интерпретатор или при их добавлении в уже загруженную базу. Системный начальный факт всегда имеет индекс «0». Связывание факта с переменной выполняется в LHS правила указателем «<-».

Теперь все понятно. Поясним только действия, выполняемые последним правилом. Вначале из рабочей памяти интерпретатора CLIPS удаляется initial-fact. Если этого не сделать, программа зацикливается. Затем факты выводятся на стандартное устройство вывода (монитор). В последнем действии факты сохраняются в файле с именем odessa.

Допустим, программа с этими правилами записана в файле odessa-only.clp. Тогда, находясь в интерпретаторе CLIPS, загрузим его в дополнение к уже загруженным файлам rep и represent.clp и запустим на выполнение:

CLIPS> (load odessa-only.clp) ............... TRUE CLIPS> (run) f-1 (rep Alejnov Odessa) f-2 (rep Ladak Odessa) f-6 (rep Pustovit Odessa) f-7 (rep Spokojnij Odessa) f-8 (rep Shamis Odessa) For a total of 5 facts CLIPS>

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

Пример 2

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

(deffacts resistors; This is database (resistor Ra 2) (resistor Rb 5) (resistor Rc 7)) (deffunction om; This is function om (x,y) ( ?x ?y) (div ?y ?x)) (defrule input; This is current & strait input (initial-fact) => (printout t crlf «Input current value: «) (bind ?i (read)) (printout t «Input strait value: «) (bind ?u (read)) (assert (numbers ?i ?u))) (defrule take; Get resistor from database (numbers ?i ?u) (resistor ?r =(om ?i ?u)) => (printout t crlf «You must take resistor « ?r».» crlf crlf) (reset) (halt)) (defrule nothing; There is nothing (numbers ?i ?u) (resistor ?r ~=(om ?i ?u)) => (printout t crlf «There is nothing for You in my database!» crlf crlf) (reset) (halt))

Программа состоит из нескольких частей: базы данных с именем resistors, объявления пользовательской функции om и трех правил с именами input, take и nothing.

В базе данных содержатся сведения о резисторах. Они представлены в виде списков, состоящих из трех полей. Первое поле имеет значение resistor, которое отражает тип радиодетали. Во втором поле списка содержится тип резистора. Последнее поле хранит значение сопротивления.

О функции om подробно говорилось ранее. В данном случае она используется для представления процедурного знания — закона Ома. Деление нацело — исключительно для упрощения.

Правило input предназначено для ввода исходных данных. Оно активизируется системным начальным фактом и требует от пользователя ввести ток и напряжение. Встроенная функция read возвращает значение, введенное со стандартного устройства ввода (клавиатуры), которое сохраняется в переменных ?i и ?u.

В RHS правила выполняется еще одно действие. Команда assert добавляет в рабочую память интерпретатора CLIPS факт (numbers ?i ?u). Для чего ? Для того чтобы можно было обращаться к локальным переменным ?i и ?u, связанным с правилом input, из других правил программы.

В следующих двух правилах пользователю либо предлагается тип подходящего резистора (правило take), либо сообщается об отсутствии такового (правило nothing).

Рассмотрим правило take. Его LHS состоит из двух условий, поэтому правило активизируется, если оба условия будут удовлетворены. Первое условие удовлетворяется, так как соответствующий факт уже создан правилом input. Второе условие удовлетворится, если будет точно соответствовать какому-либо факту (списку) в базе данных. Первое поле условия вопросов не вызывает. Во втором поле условия находится переменная ?r, которая может принять значение Ra, либо Rb, либо Rc — в зависимости от содержимого третьего поля условия. В этом поле осуществляется вызов функции om и сохраняется возвращаемое функцией значение. Так, если возвращаемое значение будет равно 7, то условие удовлетворится, переменная ?r примет значение Rc, правило активизируется и выведет на экран монитора предложение выбрать резистор Rc. Если возвращаемое функцией om значение равно 5, то пользователю будет предложен резистор Rb и т.д.

В LHS правила nothing вроде бы полная аналогия — за исключением одной маленькой модификации. В третьем поле второго условия перед вызовом функции om стоит символ «~», означающий логическое отрицание. Таким образом, условие удовлетворится и правило активизируется, если возвращаемое функцией om значение будет не 2, не 5 и не 7.

Находясь в интерпретаторе CLIPS, командой (clear) очистим его от данных предыдущего примера, загрузим файл resistor.clp и запустим программу на выполнение. Получим нечто следующее:

CLIPS> (clear) CLIPS> (load resistor.clp) ............. TRUE CLIPS> (reset) CLIPS> (run) Input current value: 3 Input strait value: 15 You must take resistor Rb. CLIPS> (run) Input current value: 3.5 Input strait value: 5.44 There is nothing for You in my database! CLIPS>

Таким образом, файл resistor.clp также представляет собой базу знаний, поскольку содержит и базу данных, и сведения (правила) о том, как данные могут быть использованы. Эта база располагает, по крайней мере, тремя знаниями. Первое — общий список резисторов с указанием типа и сопротивления. Второе — закон Ома. Третье знание — предлагаемый тип резистора.

Интеллект базы знаний можно существенно повысить добавлением новых данных и правил. Так, вместо закона Ома можно использовать более серьезные методики определения сопротивления резистора, например схемотехническую САПР PSpice. Результаты ее работы можно сохранить в текстовом файле, а затем вызвать из третьего поля второго условия правила take.

Другой путь — добавление новых типов резисторов в базу данных. Например, интересный результат получается при внесении в базу данных записи (resistor Rd 2). При некоторой доработке правил take и nothing, если возвращаемое функцией om значение равно 2, правило take отработает два раза и предложит резисторы Ra и Rd. Затем можно пойти дальше: добавить правило (правила), которое выберет из резисторов Ra и Rd предпочтительный для некоторых конкретных условий и т.д. и т.д.

В заключение несколько слов об интерпретаторе CLIPS. Это свободно распространяемая программа, которая предоставляется на условиях «как есть» и к NASA не имеет уже никакого отношения. В настоящее время в ходу версии 6.10 под Linux и 6.20 под DOS/Windows. Последняя снабжена простым GUI, напоминающим NOTEPAD. Ее можно загрузить с www.ghg.net. Оттуда же можно получить разнообразнейшую и подробнейшую документацию в PDF-формате (но на английском языке). Версия под Linux предназначена для работы с консоли. Мне она встречалась в RPM-библиотеках дистрибутивов Mandrake 8-9. Это файл clips-6.10-6mdk.i586.rpm. В Mandrake 9.0 к нему добавлен файл clips-X11-6.10-6mdk.i586.rpm с GUI для работы в иксах. Но о нем ничего сказать не могу — не пробовал.

Владимир ТРОФИМОВ,
vovic@ukr.net

До следующего выпуска!
Елена Полонская, редактор "К+П"
www.comizdat.com

Перепечатка материалов этой рассылки разрешается только по согласованию с редакцией журнала "Компьютеры+Программы"