Software & Systems

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

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

Нечеткая экспертная система с использованием формальной модели дерева решений модифицированного алгоритма Rete

Нечеткая экспертная система использует для вывода решения вместо булевой логики совокупность нечетких функций принадлежности и правил. Поведение исследуемой системы описывается на ограниченном естественном языке в терминах лингвистических переменных [8]. Входные и выходные параметры системы рассматриваются как лингвистические переменные, а описание процесса задается набором правил [9]. Формальная модель базы правил разработанной экспертной системы имеет вид

L1 : A11 и/или A2 и/или ... и/или A1m® B11 и/или ... и/или B1n,

L2 : A21 и/или A22 и/или ... и/или A2m® B21 и/или ... и/или B2n,                                                       (1)

…

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 – нечеткие высказывания, определенные на значениях выходных лингвистических переменных. Эта совокупность правил носит название нечеткой базы знаний [3].

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

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

В настоящее время алгоритм Rete является эффективным алгоритмом сопоставления с образцом для продукционных экспертных систем [10]. Rete стал основой многих популярных экспертных систем, включая CLIPS, Jess, Drools, BizTalk Rules Engine и Soar. Классический алгоритм работы экспертных систем заключается в проверке применимости каждого правила вывода к каждому факту базы знаний при необходимости его выполнения и переходе к следующему правилу с возвратом в начало базы знаний в случае исчерпания всех правил [11]. Даже для небольшого набора правил и фактов такой метод работает неприемлемо медленно. Алгоритм Rete обеспечивает более высокую эффективность [12]. При использовании Rete экспертная система выполняет формирование специального графа, узлам которого соответствуют части условий правил. Путь от корня до листа образует полное условие некоторой продукции.

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

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

M = (X, R, P, Y),                                                      (2)

где X – множество вершин-условий графа; Y – множество вершин-следствий графа; R – множество отношений между вершинами; P – множество отношений для описания правил нечеткой экспертной системы. Каждая вершина-условие представляет собой условия из правил нечеткой базы знаний: X = {

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

   

  Множество R отношений между вершинами из объединения множеств X и Y имеет вид: RÌ((XÈY)´ ´ (XÈY)) или R: (XÈY) ® (XÈY). R может принимать следующие значения: R = {T, ^, Ø}. Для операций Т-норм, Т-конорм и отрицания приняты следующие обозначения: xi и xi – условия из (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) xY) или P: (XÈY) ®Y. В рассматриваемой модели P может принимать одно значение: P = { ® }, где ® связывает значения в левой части и вершины-следствия в правой части и означает, что при истинности значений в левой части (то есть при степени уверенности в них > 0,5) выполняются утверждения, которые расположены в правой части.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  TP = «Температура пациента» = {«низкая», «нормальная», «высокая»};

  NL = «Количество лейкоцитов в крови» = = {«низкое», «нормальное», «высокое»};

  LS = «Уровень сахара в крови» = {«низкий», «нормальный», «высокий»}.

  Выходные лингвистические переменные:

  DN = «Дозировка лекарства N» = {«низкая», «стандартная», «высокая»};

  DM = «Дозировка лекарства M» = {«низкая», «стандартная», «высокая»}.

  Также система содержит следующий набор правил:

  ((TP = «высокая») и (NL = «высокое») и («LS» = = «низкий»)) ® (DN = «высокая»);

  ((TP = «высокая») и (NL = «высокое») и («LS» = = «нормальный»)) ® (DN = «низкая»);

  ((TP = «низкая»)) ® (DM = «низкая»);

  ((TP = «высокая») и (NL = «высокое»)) ® ® (DM = «высокая»).

  Рассмотрим работу экспертной системы на примере пациента со следующими симптомами: температура = 37,5 ºC, количество лейкоцитов в крови = 9,5·109/л, уровень сахара в крови = 4,8 ммоль/л.

  В начале работы алгоритма следует выполнить фаззификацию исходных данных на основе значений заданных функций принадлежности:

  –      температура = 37,5 ºC, тогда

  ϻTP_высокая(37,5 ºC)=0,9,

  ϻTP_низкая(37,5 ºC)=0,01,

  ϻTP_нормальная(37,5 ºC)= 0,2;

  –      количество лейкоцитов в крови = 9,5·109/л, тогда при норме 5,5–8,8·109/л получим:

  ϻNL_высокое(9,5·109/л)= 0,7,

  ϻNL_низкое(9,5·109/л)=0,02,

  ϻNL_нормальное(9,5·109/л)=0,4;

  –      уровень сахара в крови = 4,8/л, тогда при норме 3,3–5,5 ммоль/л получим:

  ϻLS_высокий(4,8 ммоль/л)=0,3,

  ϻLS_низкий(4,8 ммоль/л)=0,1,

  ϻLS_нормальный(4,8 ммоль/л)=0,8.

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

  В начале алгоритма устанавливается i=1. Из базы правил извлекается следующее непомеченное условие «TP = высокая» и формируется вершина Xi. Осуществляется просмотр базы правил и отмечаются все позиции в правилах, на которых встреча- ется данное условие. Формируется вершина для описания отношений из R, с которыми связана вершина Xi: T(X1, X2). Если в базе правил не закончились непомеченные условия, то i увеличивается на 1 и процесс формирования вершин для описания отношений из R продолжается. Если новое условие является второй частью одного из отношений из R, то оно связывается с уже сформированной вершиной для первой части данного отношения. Так будут сформированы T(T(X1, X2), X3), T(T(X1, X2), X4).

  Затем устанавливается j=1. Из базы правил извлекается следующее непомеченное следствие «DN = высокая» и формируется вершина Yj. Осуществляется просмотр базы правил и отмечаются все позиции в правилах, на которых встречается данное следствие. Формируется вершина для описания отношений из P, с которыми связано Y1. Устанавливается отношение между данными вершинами. Если вершины, с которыми связаны отношения из P, уже сформированы, устанавливаются связи с ними. Связываем вершины T (X1, X2) и Y1. Если их нет, то данные вершины формируются. Если в базе правил не закончились непомеченные условия, то j увеличивается на 1 и процесс построения следствий продолжается.

  Таким образом, после работы механизма вывода нечеткой экспертной системы будет сформирован следующий ответ: «Для пациента со следующими симптомами: температура = 37,5 ºC, количество лейкоцитов в крови = 9,5·109/л, уровень сахара в крови = 4,8/л, назначить высокую дозировку лекарства M с уверенностью 0,7, низкую дозировку лекарства N с уверенностью 0,8».

  Затем выполняется этап дефаззификации. На данном этапе значения полученных лингвистических переменных преобразуются в числовые характеристики.

  Например, лингвистическая переменная DN имела следующие значения: DN = «Дозировка лекарства N» = {«низкая», «стандартная», «высокая»}; и нечеткая переменная «низкая» соответствовала 1 таблетке, «стандартная» – 2 таблеткам, «высокая» – 3 таблеткам. Тогда построенное решение соответствует дозировке 1 таблетка с уверенностью 0,9.

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

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

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

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

  Литература

  1.     Прикладные нечеткие системы; [под ред. Тэрано Т., Асаи К., Сугэно М.]. М.: Мир, 1993. 368 с.

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

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

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

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

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

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

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

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

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

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

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