Диссертация (Методы и программные средства ускорения поиска решения в базах знаний нечетких экспертных систем), страница 11

Рассматриваемая модель допускает использованиене только лингвистических переменных, но и классических переменных. В этомслучае их значение может сравниваться также и с константами[74].R – множество отношений между узловыми вершинами. R  ( Cl x Cr ). ИлиR: Cl  Cr. R может принимать следующие значения: R = { T, ┴, ┐, Null}.В рассматриваемых далее T, ┴, ┐приняты следующие обозначения: xi и xj –условия, xi є Cl, xj є Cr, zi – значение степени уверенности в истинности условияxi, zj – значение степени уверенности в истинности условия xj, zk – значениестепени уверенности в истинности результата вычисления нормы, конормы илиотрицания. Отношение T-нормы определяется следующим образом zk = T(xi, xj).Значения вычисляются по правилу:T(xi, xj)= min( zi, zj ),(3.10) Отношение T-конормы определяется следующим образом zk= ┴(xi, xj).Значения вычисляются по правилу:┴ (xi, xj) = max( zi, zj ),(3.11) Отношение отрицания определяется следующим образом zk= ┐(xi).Значение вычисляется по правилу:67┐(xi)= 1 – zi,(3.12)Аналогично параметру C определяется параметр S - следствие правила.S = <Sl, R, Sr >,(3.13)где Sl - левый узел следствия правила, R - отношение между узлами следствияправила, Sr - правый узел следствия правила.Sl = FSl || Null || S,(3.14)Sr = FSr || Null || S,(3.15)где FSl - левая концевая тройка следствия правила, FSr - правая концевая тройкаследствия правила.

Формулы (3.14) и (3.15) позволяют описать следствия сразличной степенью вложенности.FSl = <L, Op, W>,(3.16)FSr = <L, Op, W>,(3.17)где L - лингвистическая переменная, Op - операция, Op = { := }, W - значениеследствия, которое определяется следующим образом (3.18):W = L || V,(3.18)где L - лингвистическая переменная, V - фиксированное значение (3.19).V = Ti || Const(3.19)где Ti - значение нечёткой переменной из терм-множества лингвистическойпеременной, Const - константа.Лингвистическая переменная L представляется следующим образом (3.20)L = (X, T(X), U, G,M),(3.20)Данное определение лингвистической переменной было рассмотрено в главе 1.68На модель представления нечёткой базы правил накладываются следующиеограничения.

Для выбранного i-го поддерева условия или следствия элементаправила должны выполняться следующие условия:1. Если (Ri = Null), то (Cli != Null) и (Cri = Null) и (FCri = Null).2. Если (Ri = ┐), то ((Cli = Null) и (Cri != Null)).3. Если (Ri = T) или (Ri = ┴), то ((Cli != Null) и (Cri != Null)).Формирование индекса узла формальной модели заключается в следующем.Верхний индекс соответствует номеру правила в базе правил.

Нижний индексведётся по порядку для каждой новой вершины одного уровня. Нижний индексявляется составным и отображает глубину вложенности условий в правиле. Присоздании новой вершины типа C, S, FCl, FCr, FSl, FSr, добавляется новый нижнийиндекс, начинающийся с единицы.3.2. Пример представления правила из нечёткой базы правил в видеформальной модели дерева решений алгоритма Fuzzy ReteРассмотрим пример представления правила с номером i из нечёткой базыправил в виде формальной модели дерева решений алгоритма Fuzzy Rete.Если (Температура=низкая) и (Расход=малый),то (Давление=низкое)(3.21)где: "Температура", "Расход" и "Давление" - лингвистические переменные, а"низкая", "малый" и "низкое" - нечёткие переменные.

Данное правило,представленное в виде формальной модели алгоритма Fuzzy Rete будет иметь вид.69Ci1 → Si2<Cli1, Ri1, Cri1><Sli2, Ri2, Sri2>FCli1 T FCri1FSli2 T FSri2<Li1,1, Zi1,1, Wi1,1>="Температура"<Li1,2, Zi1,2, Wi1,2><Li2,1, Opi2,1, Wi2,1> Null==Vi1,1Null"Расход"Vi1,2"Давление"Vi2,1Ti1,1Ti1,2Ti2,1"низкая""малый""низкое"Рис. 3.1. Пример представления правила из нечёткой базы правил в форматеформальной модели алгоритма Fuzzy ReteТакже в базе знаний присутствует правило с номером j и имеет вид:.Если (( Температура=высокая) и (Расход=малый)) или(┐(Расход< средний)), то (Давление=высокое)(3.22)Представление правила (3.22) будет иметь вид, представленный на рисунке3.2.70Рис. 3.2.

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

При этом на каждом шаге вначале выполняютсябазовые проверки для выявления несоответствия узлов на ранних этапах.Процедура проверки близости поддеревьев различных правил имеетрекурсивный характер. Вначале определяются близкие концевые тройки дляразличных правил.Для оценки близости одной концевой тройки FCl1 (или FCr1) к другой FCl2(или FCr2) выполняются проверки соответствия их элементов, а именно:1. Проверка соответствия лингвистических переменных. L1=L2.2.

Проверка соответствия знаков условий: Z1=Z2.3. Если последним элементом тройки является лингвистическая переменная,то осуществляется проверка аналогичная пункту 1. Если аргументом являетсяконстанта, то выполняется проверка Const1=Const2. Если аргументом являетсязначение нечёткой переменной, то запускается процедура проверки близостиконцевых узлов T1 и T2.Для оценки близости одной концевого узла T1 дерева правила другому узлуT2, используется процедура оценки соответствия нечётких утверждений другдругу. При этом предельное значение меры соответствия узлов, при котором узлыещё считаются близкими, задаётся пользователем.

Процедура оценки имеет вид:1. Выполняется проверка типов узлов. При выявлении несоответствия типовузлов формируется заключение о том, что узлы не совпадают, и осуществляетсяпереход к проверке следующей пары узлов. Если типы узлов совпадают, товыполняются следующие проверки.2. Сопоставление границ интервала.

Если пересечение границ интерваловузлов не пусто, то проверки продолжаются. В противном случае формируетсязаключение о несовпадении узлов.723. Вычисление пересечения графиков функций принадлежности узлов μ1 иμ2. В зависимости от того, какую часть от площади μ1 занимает μ1∩μ2формируется заключение о степени близости данных узлов.r(T1, T2) = P(μ1∩μ2) / P(μ1)(3.23)где r - мера близости узлов T1 и T2, P - функция, вычисляющая площадь подграфиком функции принадлежности. Если P(μ1) = 0, то r(T1, T2) = 0.Алгоритм проверки близости концевых узлов (Final Nodes Proximity - FNP)представлен на рисунке 3.3.73Блок-схема проверки близости концевых узлов.НачалоПроверка типов узлов-+Проверка границинтервала областизначений-+Вычисление пересечения функцийпринадлежности узлов.Вычисление функции оценки близостиузлов.+Оценка близости узлов-+Заключение осоответствии узлов.Заключение онесоответствии узлов.КонецРис.

3.3. Блок-схема алгоритма проверки близостиконцевых узлов для алгоритма Fuzzy Rete743.4. Оценка близости промежуточного узла дерева другому узлуПосле оценки близости двух концевых троек алгоритм ускорения работыдерева решения выполняет переход на верхний уровень модели, к родительскимузлам тех узлов, для которых было успешно установлено соответствие.Выполняется проверка соответствия данных родительских узлов и ихвторых дочерних концевых троек.В случае успешного установления соответствия между ними процедураповторяется: осуществляется переход к их родительским узлам и проверкасоответствия между родительскими узлами.Процесс повторяется до тех пор, пока не будет установлено несоответствиемежду узлами или пока не будет достигнут корень дерева решения. Данныйпроцесс (Intermediate Nodes Proximity - INP) представлен в виде блок схемы нарисунке 3.4.

Для определённости допустим, что установлено соответствие междулевыми концевыми тройками FClik1,...,kn и FCljp1,...,pm двух правил i и j (и,следовательно, между узлами Clik1,...,kn и Cljp1,...,pm), n и m - глубина вложенностиусловий в соответствующих правилах.Необходимо отметить, что проверка соответствия узлов Crik1,...,kn и Crjp1,...,pmтакженоситрекурсивныйхарактер.Привыполненииэтойпроверкиосуществляется проверка соответствий всех узлов поддеревьев решений,начинающихся с узлов Crik1,...,kn и Crjp1,...,pm, правил i и j. Проверка продолжается дотех пор, пока не будет найдено несоответствие узлов (неуспешный результат) илипока не закончатся узлы поддеревьев (успешный результат).75НачалоУстановление соответствия междуClik1,...,kn и Cljp1,...,pmПроверка соответствияузлов Rik1,...,kn и Rjp1,...,pm-+Проверка соответствия узловCrik1,...,kn и Crjp1,...,pm-Заключение онесоответствииузлов и выход изпроцедурыпроверки+Заключение о соответствии узловCik1,...,kn и Cjp1,...,pmПереход к родительскимузлам возможен?(n>0, m>0)+Переход к родительским узламn=n-1, m=m-1Заключение осоответствииэлементов правилаj элементамправила i и выходиз процедурыКонецРис.

3.4. Блок-схема алгоритма проверки близостипромежуточных узлов для алгоритма Fuzzy Rete763.5. Алгоритм Fuzzy Rete для формирования дерева решенийнечёткой продукционной базы правилРазработанный алгоритм состоит из трёх этапов.На первом этапе алгоритм обрабатывает правила нечёткой базы правил ипреобразует их в формат разработанной формальной модели.На втором этапе работы алгоритма Fuzzy Rete выполняется поиск близкихконцевых троек во всех правилах продукционной базы знаний. Найденныесоответствиямеждуконцевымитройкамипомечаются.Вправилахустанавливаются ссылки такие концевые тройки для обеспечения их однократнойобработки.На третьем этапе выполняется рекурсивная процедура проверки близостипромежуточных узлов деревьев решений.