Адаптация нечёткого вывода к аппарату таблиц решений1




Скачать 130.82 Kb.
НазваниеАдаптация нечёткого вывода к аппарату таблиц решений1
Дата публикации28.03.2013
Размер130.82 Kb.
ТипДокументы
skachate.ru > Информатика > Документы


Адаптация нечёткого вывода к аппарату таблиц решений1

О.В. Виноградов2, А.П. Еремеев3

Введение

Создание современных интеллектуальных (экспертных) систем поддержки принятия решений (ЭСППР) требует применения эффективных моделей представления знаний. Существует достаточно большое количество различных классов моделей представления знаний. При этом выразительность и гибкость моделей представления знаний находятся, как правило, в обратной зависимости от их эффективности. Является целесообразной разработка полного инструментария для работы с табличными моделями представления знаний. Относительно невысокая выразительность этого класса моделей компенсируется широкими возможностями их верификации и оптимизации, а также возможностью эффективного принятия решений по ним. Предлагается расширить классический аппарат таблиц решений средствами оперирования плохо определённой информацией на основе методов теории нечётких и приближённых множеств. Предлагается обобщённая формальная модель такого класса табличных моделей, описывается базовый алгоритм принятия решений по ним, основывающийся на схеме вывода Цукамото для нечётких правил. Также показан способ повышения эффективности вывода на основе концепции деревьев активации. Данная работа выполнялась в плане НИР кафедры Прикладной математики МЭИ (ТУ) и в сотрудничестве с факультетом Информатики Дрезденского технического университета (Германия).

^ Нечёткие таблицы решений

Классические таблицы решений (ТР) известны с конца 60-х годов XX века. В 1979 году был принят Европейский стандарт DIN 66241 «Обработка информации. Таблицы решений в качестве описательных средств в процессе принятия решений», действующий до сих пор. В своей базовой форме язык ТР позволяет задавать набор простых продукционных правил на основе пропозициональной логики: [1 5]. Множества входных термов (условий) и выходных термов (действий) являются общими для всех правил в ТР. Такой набор правил может быть представлен в табличной форме, что и дало название данному формальному аппарату. Несмотря на существование стандарта, в различных работах приводятся отличающиеся описания как структуры ТР, так и их семантики.

Целью данной работы было построение формального описания нечётких таблиц решений (НТР), базирующихся на классических ТР, но способных работать как с дискретными, так и с непрерывными и нечёткими входами и выходами. Идея такой гибридизации появилась в литературе в середине 90-х годов XX века [6-7], однако в имевшихся публикациях не была чётко сформулирована формальная модель аппарата НТР, нечёткие входы таблиц рассматривались в отрыве от стандартных дискретных, что не позволяет говорить об эффективном обобщении аппарата ТР на нечёткий случай. Для вывода по НТР использовались стандартные общие схемы нечётких рассуждений, не использующие особенности НТР для построения более эффективных специализированных алгоритмов вывода.

Определим атрибут как тройку: , где

  • множество входных значений (домен) атрибута (потенциально несчётное);

  • – конечное множество выходных значений атрибута ;

  • – тотальная функция соответствия значений атрибута , оценивающая степень истинности выходного значения для элемента домена ;

  • – множество всех атрибутов указанной структуры.

В эту структуру укладываются несколько базовых классов атрибутов:

  • булевы атрибуты вида , где



      • ;

  • N-значные дискретные атрибуты вида , где

      • ;

      • ;

      • ;

  • вещественные атрибуты вида , где

      • ;

      • , , где является разбиением ;

      • ;

  • нечёткие атрибуты вида , где

      • ;

      • , где – стандартное определение нечёткой переменной с именем , характеризуемой нечётким множеством с функцией принадлежности [8];

      • .

Пример набора трапециевидных функций принадлежности значений нечеткого атрибутов приведён на рис. 1. Пример описывает нечёткий атрибут «#Jobs in Queue», принимающий три значения: Low, Normal и High. Доменом атрибута является отрезок [0, 8].



Рис. 1. Пример функций принадлежности

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

Определим формально понятие нечёткой таблицы решений (НТР). НТР есть тройка , где

  • – конечное множество условных атрибутов (условий);

  • – конечное множество решающих атрибутов (решений, действий);

  • – обобщённая решающая функция (функция уверенности).

Введём дополнительные понятия:

  • Входным вектором (ситуацией), принадлежащим множеству возможных ситуаций , называется вектор .

  • Выходным вектором (решением), принадлежащим множеству решений , называется вектор .

Тогда процесс принятия решения на основе НТР можно представить как отображение входных ситуаций на решения при посредстве НТР:

.

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

IF THEN с коэффициентом. уверенности .

Здесь в антецеденте и консеквенте правила записываются нечёткие конъюнкции оценок значений атрибутов НТР, а само правило является не достоверным, а правдоподобным с коэффициентом уверенности , равным значению функции уверенности от значений атрибутов. При правило является достоверным.

Как и в случае классических ТР, такие правила могут быть представлены в табличном виде, где решающие правила записываются в столбцах, а строки таблицы соответствуют условным и решающим атрибутам НТР. Во входах условной части НТР применяется символ безразличия «*», если значение условного атрибута несущественно в правиле. В последней строке записываются коэффициенты уверенности правил. В табл. 1 приведён пример НТР, описывающей выбор стратегии упорядочивания задач в очереди обслуживающего устройства. Для принятия решения используются 3 условных атрибута: количество задач в очереди (#Jobs in Queue, нечёткий атрибут, описан выше), уровень загрузки устройства (Tool Load, вещественный атрибут с доменом [0.0, 1.0] и двумя значениями: [0.0, 0.7) и [0.7, 1.0]) и признак наличия в очереди высокоприоритетных задач (Has Priorities, булевый атрибут). Возможные значения дискретного решающего атрибута Strategy включают FIFO, PR-FIFO, RANDOM, SPTF, и PR-SPTF.




1

2

3

4

5

6

#Jobs in Queue

Low

Low

Low

Mid

High

Mid /

High

Tool Load

*

*

[0.0, 0.7)

*

*

*

Has Priorities

No

Yes

*

No

No

Yes

Strategy

FIFO

PR-FIFO

RANDOM

FIFO

SPTF

PR-SPTF

cf

0.8

1.0

0.4

1.0

1.0

1.0

Табл. 1. Пример НТР

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

Вывод на нечётких таблицах решений

Хотя НТР содержат как нечёткие, так и дискретные и непрерывные входы, процесс принятия решений должен базироваться именно на схеме нечёткого вывода, обобщающей остальные случаи. Для нечётких пропозициональных правил произвольной формы известны несколько основных схем нечёткого вывода [8]. В качестве базовой схемы для вывода на НТР возьмём схему Цукамото (Tsukamoto). Она обладает невысокой вычислительной сложностью, что позволяет применять её в ситуациях с ограниченным лимитом времени на принятие решения, в том числе в ЭСППР реального времени. Кроме того, она широко используется в существующих приложениях нечёткой логики, её надёжность и эффективность проверены практикой. Прямое использование вывода по Цукамото для принятия решений по НТР невозможно, требуется адаптация базового алгоритма. Рассмотрим основные шаги предлагаемого в работе алгоритма вывода по НТР.

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

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

Последующие этапы активации заключений и вычисления выходных значений выполняются отдельно для каждого решающего атрибута в НТР. Этап активации заключений применим только к нечётким и вещественным атрибутам. В ходе него для каждого активного правила вычисляется предварительное выходное значение решающего атрибута по значению атрибута в заключении этого правила как центр его интервальной оценки по формуле . Сама интервальная оценка вычисляется по формуле . На заключительном этапе производится окончательное вычисление компонентов вектора решения . Для нечёткого либо вещественного решающего атрибута значение решения задаётся формулой , где суммирование ведётся по всем активным правилам в НТР (принцип центра тяжести для одноточечных множеств, Centre of Gravity for Singletons, [8]). Для булевого либо дискретного решающего атрибута решение получаем в соответствии с формулой . За решение принимается тот элемент домена решающего атрибута, который характеризуется максимальной суммой коэффициентов активации правил, в которых указано значение атрибута, ассоциированное с данным элементом домена.

^ Концепция деревьев активации

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

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

  • – условие нормальности;

  • – условие локальной полноты (обобщённое условие исключённого третьего);

  • .

Пример нечёткого атрибута на рис. 1 удовлетворяет перечисленным требованиям. Из наложенных ограничений следует, что для любого входного значения не более двух функций принадлежности нечёткого атрибута могут одновременно принимать ненулевое значение. Если таковая функция только одна, то она принимает значение 1.0, иначе сумма значений двух функций принадлежности также даёт 1.0.

Построим разбиение домена нечёткого условного атрибута на интервалы с выполнением условия:

.

В зависимости от выполнения первой или второй альтернативы в последнем условии будем говорить, что интервал помечен значением или выражением соответственно. Применительно к набору функций принадлежности на рис. 1 разбиение будет иметь вид . Метками элементов разбиения будут являться «Low», «Low  Mid», «Mid», «Mid  High» и «High» соответственно. Если все функции принадлежности являются унимодальными (как в примере), то выполняется неравенство .

Определим дерево активации как помеченное ориентированное дерево, в котором все дуги ориентированы в направлении от выделенной корневой вершины к листьям, а внутренние узлы помечены условными атрибутами НТР. Каждая дуга помечена значением атрибута, связанного со стартовой вершиной дуги (для булевых, дискретных и непрерывных атрибутов), либо меткой элемента разбиения такого атрибута (для нечётких атрибутов). Имея заданный вектор ситуации , можно пройти по дереву активации от корня до некоторого его листа. В каждом внутреннем узле делается однозначный выбор ветви для дальнейшего перехода на основании компонента вектора ситуации, соответствующей условному атрибуту, которым помечен данный узел. С каждым листом дерева активации свяжем список правил, активных для комбинации значений условных атрибутов, соответствующей проходу по дереву от корня до данного листа. Применяя дерево активации можно избежать просмотра всех условий всех правил в НТР в процессе отбора активных правил. При проходе по дереву активации список активных правил может быть получен за время , где – количество условных атрибутов в НТР. Более того, для этого могут быть использованы не все условные атрибуты, а только их подмножество, встречающееся на пути от корня до листа дерева активации. На рис. 2 приведено дерево активации для приведенного выше примера НТР. Названия атрибутов (в нетерминальных вершинах дерева) сокращены до JIQ, TL и HP соответственно. Листовые вершины содержат номера правил в НТР, активируемых данной ветвью дерева.



Рис. 2. Пример дерева активации

В зависимости от выбора последовательностей проверок условий в ветвях для одной НТР можно построить множество деревьев активации. В качестве критерия оптимальности дерева активации будем рассматривать его высоту. На основе известных результатов по трансляции классических ТР в деревья решений можно сделать вывод, что построение оптимального дерева активации для заданной НТР является NP-полной задачей. Рассмотрим подкласс деревьев активации, где на каждом ярусе дерева во всех ветвях производится ветвление по одному и тому же условному атрибуту (т.н. последовательности активации). Можно показать (по аналогии с соответствующим подклассом деревьев решений), что в классе последовательностей активации оптимальная структура может быть найдена за полиномиальное время. Однако оптимум для последовательности активации является локальным и, как правило, не совпадает с глобальным оптимумом для деревьев активации.

Заключение

Описанные выше модель НТР и алгоритм принятия решений по ней реализованы в виде динамической библиотеки, ориентированной на интеграцию с Системой моделирования принятия решений СИМПР-Windows, разрабатываемой на кафедре Прикладной математики МЭИ (ТУ) ».) [5, 9]. Разработка производилась на языке C++ в интегрированной среде разработки Microsoft Visual Studio 2005 с ориентацией на IBM-совместимые компьютеры с операционными системами Microsoft Windows Vista/XP/2000. Система была апробирована при построении нечёткого контроллера для решения задачи диспетчеризации лотов на производстве микроэлектронных компонент совместно с научной группой Имитационного моделирования факультета Информатики Дрезденского технического университета (Германия) в рамках международной обменной программы «Михаил Ломоносов. Описанный аппарат планируется использовать в составе инструментальных средств конструирования ЭСППР реального времени.

Литература

  1. А.П. Еремеев. Продукционная модель представления знаний на базе языка таблиц решений // Известия АН СССР. Техническая кибернетика, 1987, №2, с. 196-209.

  2. А.П. Еремеев. О корректности продукционной модели принятия решений на основе таблиц решений // Автоматика и Телемеханика, №10, 2001, с. 78-90.

  3. Э. Хамби. Программирование таблиц решений. М: Мир, 1976. - 86 с.

  4. M. Engelien. Rekursive Projektierung von Algorithmen und Entscheidungstabellentechnik // Wissenschaftliche Zeitschrift der TU Dresden, Jg. 29, Heft 3/4, 1980, s. 873-880.

  5. О.В. Виноградов. Анализ таблиц решений с расширенным входом на основе теории приближённых множеств в системе «СИМПР-Windows» // Тезисы докладов XV Международной студенческой школы-семинара «Новые информационные технологии» – М.: МИЭМ, 2007, с. 166-167.

  6. G. Chen, J. Vanthienen, G. Wets. Fuzzy decision tables: extending the classical formalism to enhance intelligent decision making // Proc. of the Fourth IEEE International Conference on Fuzzy Systems, 1995, vol. 2, pp. 599 - 606.

  7. F. Witlox, T. Arentze, H. Timmermans. Constructing and consulting fuzzy decision tables // Decision support systems in urban planning, 1997, pp. 156-174.

  8. А.В. Леоненков. Нечёткое моделирование в среде MATHLAB и fuzzyTECH. – СПб.: БХВ-Петербург, 2003.

  9. О.В. Виноградов. Представление нечётких баз знаний на основе табличных моделей. // Радиоэлектроника, электротехника и энергетика. 14 я Международная научно-техническая конференция студентов и аспирантов: Тез. докл.: В 3-х т. — М.: МЭИ, 2008, т.1., с. 293-294.

1 Работа выполнена при финансовой поддержке РФФИ (проект № 08-01-00437), а также DAAD и Министерства образования и науки РФ в рамках программы «Михаил Ломоносов»

2 111250, Москва, ул. Красноказарменная 14, МЭИ (ТУ), VinogradovOV@gmail.com

3 111250, Москва, ул. Красноказарменная 14, МЭИ (ТУ), eremeev@appmat.ru


Похожие:

Адаптация нечёткого вывода к аппарату таблиц решений1 iconСхемы нечеткого вывода
Исследование применимости различных схем нечеткого вывода в иерархических нечетких системах
Адаптация нечёткого вывода к аппарату таблиц решений1 iconСхемы нечеткого вывода
В работе описываются основные принципы построения экспертных систем и способ решения задачи анализа экологической безопасности с...
Адаптация нечёткого вывода к аппарату таблиц решений1 iconДсм-подобные системы, использующие аппарат нечеткого вывода
В статье рассматривается разновидность систем интеллектуального анализа данных, в работе которых комбинируются подходы дсм-метода...
Адаптация нечёткого вывода к аппарату таблиц решений1 iconИсследование многошагового нечеткого вывода на примере построения...
В работе описывается механизм многошагового (иерархического) нечеткого вывода и его применение в решении задач эколого-экономического...
Адаптация нечёткого вывода к аппарату таблиц решений1 iconСравнение системы нечеткого вывода и обучаемой дсм-системы при планировании...
Д. А. Добрынин, к т н., старший научный сотрудник винити ран, г. Москва
Адаптация нечёткого вывода к аппарату таблиц решений1 iconД. А. Добрынин, к т. н., старший научный сотрудник винити ран, г. Москва
Сравнение системы нечеткого вывода и обучаемой дсм-системы при планировании движения мобильного робота
Адаптация нечёткого вывода к аппарату таблиц решений1 iconС применением методов иад
Система снабжена интеллектуальными функциями: кластеризация посетителей относительно выделенного целевого атрибута при помощи правил...
Адаптация нечёткого вывода к аппарату таблиц решений1 iconВариант №2 Задача Пусть имеется следующее правило: если Х – маленькое,...
Найти значения у, использую последовательно все четыре правила нечеткого вывода (максиминное, арифметическое, размытое бинарное и...
Адаптация нечёткого вывода к аппарату таблиц решений1 iconКонтрольная работа №2 по дисциплине «Системы искусственного интеллекта»
Проиллюстрировать графически механизм прямого и обратного логического вывода факта А. Обратите внимание на изменение содержимого...
Адаптация нечёткого вывода к аппарату таблиц решений1 icon2. модель нечеткого временного ряда на основе элементарных тенденций определение   1
Лингвистические оценки, полученные по лингвистической acl-шкале (см статью «Моделирование лингвистических оценок по acl-шкале» в...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница