Программные продукты и системы

В основе функционирования экспертных систем (ЭС) лежит модель знаний. Она содержит набор принципов, которые описывают состояние и поведение объекта исследования [1]. Наиболее широко применяемой моделью ЭС является продукционная модель в силу своей простоты обработки и понятности конечному пользователю [2].

Однако в последнее время большое распространение приобретают нечеткие ЭС [3]. Данный тип ЭС базируется на наборе правил, в которых используются лингвистические переменные и нечеткие отношения для описания состояния и поведения исследуемого объекта [4]. Правила, представленные в таком виде, наиболее приближены к естественному языку, поэтому нет необходимости в отдельном специалисте – инженере по знаниям для создания и редактирования правил [5]. Они могут быть отредактированы самим экспертом практически без специальной подготовки [6].

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

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

Нечеткие ЭС

В основе правил работы нечетких ЭС лежит понятие лингвистической переменной [7]. У каждой из них есть набор значений – нечеткие переменные, образующие ее терм-множество [8]. Лингвистическая переменная L характеризуется следующим набором свойств:

L = (X, T(X), U, G, M),                                            (1)

где X – название переменной; T(X) – терм-мно­жество переменной X, то есть множество названий лингвистических значений переменной X, причем каждое из таких значений является нечеткой переменной x’ со значениями из универсального множества U с базовой переменной u; G – синтаксическое правило, порождающее названия x’ значений переменной X; M – семантическое правило, ставящее в соответствие каждой нечеткой переменной x’ ее смысл M(x’), то есть нечеткое подмножество M(x’) универсального множества U.

Нечеткая переменная характеризуется тройкой , где x – название переменной; U – универсальное множество; X – нечеткое подмножество множества U, представляющее собой нечеткое ограничение на значение переменной uÎU, обусловленное x [3].

Поведение исследуемой системы описывается на ограниченном естественном языке в терминах лингвистических переменных. Входные и выходные параметры системы рассматриваются как лингвистические переменные, а описание процесса задается набором правил. Формальная модель базы правил разработанной ЭС имеет вид:

L1 : A11 и/или A2 и/или ...

и/или A1m ® B11 и/или ... и/или B1n,

L2 : A21 и/или A22 и/или ...

и/или A2m ® B21 и/или ... и/или B2n,                        (2)

…

Lk : Ak1 и/или Ak2 и/или ...

и/или Akm ® Bk1 и/или ... и/или Bkn,

где Ai,j, i = 1, 2, …, k, j = 1, 2, …, m – нечеткие высказывания, определенные на значениях входных лингвистических переменных; Bi,j, i = 1, 2, …, k, j = 1, 2, …, n – нечеткие высказывания, определенные на значениях выходных лингвистических переменных. Эта совокупность правил носит название нечеткой базы знаний.

В общем случае нечеткий вывод решения происходит за четыре этапа.

1.     Фаззификация. Преобразование с помощью функций принадлежности ϻ точных входных данных в нечеткие значения лингвистических переменных.

2.     Непосредственный нечеткий вывод. На основании набора правил нечеткой базы знаний вычисление значения истинности для условий каждого правила по правилам вычисления Т-норм, Т-конорм и отрицаний.

3.     Композиция. Формирование значений выходных лингвистических переменных для каждого сработавшего правила.

4.     Дефаззификация. Преобразование нечетких значений выходных лингвистических переменных в точные значения.

Для вычисления T-норм и T-конорм были выбраны следующие правила: TM(x, y) = min{x, y} и ^M(x, y) = max{x, y}. Для вычисления отрицания утверждения был выбран вариант классического отрицания Ø(x) = 1 – x.

Формальная модель дерева решений модифицированного алгоритма Rete

Алгоритм Rete является эффективным алгоритмом сопоставления с образцом для продукционных ЭС [9]. Rete стал основой многих популярных ЭС, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar.

Классический алгоритм работы ЭС заключается в проверке применимости каждого правила вывода к каждому факту базы знаний при необходимости его выполнения и в переходе к следующему правилу с возвратом в начало базы знаний в случае исчерпания всех правил [10]. Даже для небольшого набора правил и фактов такой метод работает неприемлемо медленно. Алгоритм Rete обеспечивает более высокую эффективность [11].

При использовании Rete ЭС формирует специальный граф, узлам которого соответствуют части условий правил. Путь от корня до листа образует полное условие некоторой продукции.

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

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

M = (X, R, P, Y).                                                      (3)

X – множество вершин-условий графа; каждая вершина представляет собой условия из правил нечеткой базы знаний, X = {

• }, где li – название лингвистической переменной; ki – отношение сравнения, ki Î K, где K = {=, ≠}; Txi – значение лингвистической переменной, то есть нечеткая переменная из ее терм-множества; zi – значение степени уверенности ϻ в том, что рассматриваемое условие li, ki, Txi истинно. Данное значение вычисляется и означивается при проверке рассматриваемого условия во время работы нечеткой ЭС; i = 1, ..., n, где n – количество условий в базе знаний.

   

  Y – множество вершин-следствий графа; каждая вершина – это присваивание определенной лингвистической переменной ее значения, и она представляет собой условия из правил нечеткой базы знаний: Y = {< li = Tyi, zi>}, где li – название лингвистической переменной; Tyi – значение лингвистической переменной, то есть нечеткая переменная из ее терм-множества; zi – значение степени уверенности ϻ в том, что рассматриваемое следствие li = Tyi истинно. Данное значение вычисляется и означивается при определении степени уверенности в истинности правила, в которое входит данная лингвистическая переменная; i = 1, …, n, где n – количество условий в базе знаний.

  R – множество отношений между вершинами из объединения множеств X и Y, RÌ((XÈY)´(XÈY)) или R: (XÈY) ® (XÈY), R может принимать следующие значения: R = {T, ^, Ø}.

  В рассматриваемых далее T, ^, Ø приняты следующие обозначения: xi и xj – условия из (XÈY), xi Î (XÈY), xj Î (XÈY), zi – значение степени уверенности в истинности условия xi = , zj – значение степени уверенности в истинности условия xj = , zk – значение степени уверенности в истинности результатов вычисления нормы, конормы или отрицания.

  ·       Отношение T-нормы определяется следующим образом: zk = T(xi, xj); значения вычисляются по правилу: T(xi, xj)= min{zi, zj}.

  ·       Отношение T-конормы определяется следующим образом: zk = ^(xi, xj); значения вычисляются по правилу: ^(xi, xj) = max{zi, zj}.

  ·       Отношение отрицания определяется следующим образом: zk= Ø(xi); значение вычисляется по правилу: Ø(xi)= 1 – zi.

  P – множество отношений для описания правил нечеткой ЭС. PÌ((XÈY)´Y). Или P: (XÈY) ® Y. В рассматриваемой модели P может принимать одно значение: R = { ® }, где ® связывает значения в левой части и вершины-следствия в правой части и означает, что при истинности значений в левой части (то есть при степени уверенности в них > 0,5) выполняются утверждения, расположенные в правой части.

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

  Модификация алгоритма Rete для формирования дерева решений нечеткой продукционной базы правил

  Данный алгоритм обрабатывает правила нечеткой базы правил и преобразует их в формат формальной модели дерева решений модифицированного алгоритма Rete. Рассмотрим схему данного алгоритма.

  Входные данные алгоритма: правила из базы правил.

  1.     Начало алгоритма.

  1.     Установить i=1.

  2.     Извлечь из базы правил следующее непомеченное условие и сформировать вершину xi.

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

  4.     Сформировать вершины для описания отношений из R {T, ^, Ø}, с которыми связано xi. Установить отношения между данными вершинами.

  5.     Если в базе правил не закончились непомеченные условия, увеличить i на 1 и осуществить переход к шагу 3.

  6.     Установить j=1.

  7.     Извлечь из базы правил следующее непомеченное следствие и сформировать вершину yi.

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

  9.     Сформировать вершину для описания отношения из P {®}, с которым связано yj. Установить отношения между данными вершинами.

  10. Если вершины И, ИЛИ, НЕ, с которыми связаны отношения из P, не сформированы, сформировать их.

  11. Если вершины И, ИЛИ, НЕ, с которыми связаны отношения из P, уже сформированы, установить связи с ними.

  12. Если в базе правил не закончились непомеченные следствия, увеличить j на 1 и осуществить переход к шагу 8.

  13. Конец алгоритма.

  Выходные данные: дерево решений, построенное на основе правил.

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

  Основные преимущества разработанного алгоритма

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

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

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

  Это позволяет формулировать условия и следствия в базе правил на ограниченном естественном языке. Заключения формируются алгоритмом также на ограниченном естественном языке.

  Вторым преимуществом является то, что одинаковые условия объединяются при построении дерева решений на основе правил базы знаний. Это дает ускорение обработки дерева решений по сравнению с последовательным просмотром правил ЭС.

  В заключение отметим, что в работе получены следующие результаты.

  Исследованы основные понятия нечеткой логики и процесса создания и функционирования нечетких ЭС продукционного типа. Изучены процессы и технологии разработки БД. Полученные навыки применены на практике при создании БД для тестовых примеров. Разработана формальная модель дерева решений модифицированного алгоритма Rete для нечеткой продукционной базы знаний.

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

  Литература

  1.     Искусственный интеллект. В 3-х кн. Модели и методы: справочник. М.: Радио и связь, 1990. Кн. 2. 304 с.

  2.     Вагин В.Н., Еремеев А.П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени // Изв. РАН. ТиСУ. 2001. № 6. С. 114–123.

  3.     Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976. 166 c.

  4.     Заде Л. От обработки чисел к обработке слов – от манипулирования измерениями к манипулированию восприятием // Международный журнал прикладной математики и компьютерной науки. 2002. Т. 12. № 3. С. 307–324.

  5.     Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб: Питер, 2001. 384 с.

  6.     Аверкин А.Н. Нечеткое отношение моделирования и его использование для классификации и аппроксимации в нечетких лингвистических пространствах // Изв. АН СССР: Техническая кибернетика. 1982. № 2. С. 21.

  7.     Аверкин А.Н., Батыршин И.З., Блишун А.Ф., Си- лов В.Б., Тарасов В.Б. Нечеткие множества в моделях управления и искусственного интеллекта; [под ред. Д.А. Поспелова]. М.: Наука. Глав. ред. Физматлит, 1986. 312 с.

  8.     Блюмин С.Л., Шуйкова И.А., Сараев П.В., Черпа- ков И.В. Нечеткая логика: алгебраические основы и приложения: монография. Липецк: Изд-во ЛЭГИ, 2002. 111 с.

  9.     Форги Ч. Rete: быстрый алгоритм для многошаблонных/многообъектных задач сопоставления с образцом // Искусственный интеллект. 1982. № 19. С. 17–37.

  10.  Рассел С., Норвиг П., Искусственный интеллект: современный подход. М.: Вильямс, 2006. 1407 с.

  11.  Вакин В.В., Корухова Л.С., Любимский Э.З., Малыш- ко В.В. Ассоциативные методы планирования решений сложных задач. М.: Препринт ИПМ им. М.В. Келдыша РАН. 1997. № 81. 26 с.