Разработка программы построения нечеткого классификатора на основе наблюдаемых данных

 

1.Нечеткое моделирование: основные понятия и принципы

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

нечеткая спецификация параметров системы (функционирование системы может быть описано алгебраическим или дифференциальным уравнением, в котором параметры являются нечеткими числами);

нечеткое (лингвистическое) описание входных и выходных переменных системы, которое обусловлено неточной информацией, получаемой от ненадежных датчиков, или качественной информацией, получаемой от эксперта;

нечеткое описание системы в виде совокупности если-то - правил, отражающих особенности функционирования на качественном уровне.

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

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

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

Нечеткая переменная задается тройкой

<a, U, A>,

где a - название переменной, U - универсальное множество (область определения a), А - нечеткое множество на U с функцией принадлежности , описывающее ограничения на значение нечеткой переменной.

Лингвистическая переменная задается кортежем

<b, T, U, G, M>,

где b - название переменной; Т - базовое терм-множество или множество основных лингвистических значений (термов) переменной b, причем каждому из них соответствует нечеткая переменная с функцией принадлежности, заданной на U; G - синтаксическое правило, описывающее процесс образования из множества Т новых значений лингвистической переменной ( называется расширенным терм-множеством); М - семантическое правило, согласно которому новые значения лингвистической переменной b, полученные с помощью G, отображаются в нечеткие переменные (это может быть процедура экспертного опроса, позволяющая приписать каждому новому значению, образованному процедурой G, некоторую семантику путем формирования соответствующего нечеткого множества). Шкала U, на которой определена лингвистическая переменная, может быть числовой или нечисловой.

Нечеткое число - это нечеткая переменная, определенная на числовой оси функцией принадлежности . Самые простые нечеткие числа - треугольные и трапециевидные.

Треугольным нечетким числом А с центром в точке а, левой шириной и правой шириной называется нечеткое множество А с функцией принадлежности вида

Трапециевидное нечеткое число А с отрезком толерантности [a, b], левой шириной и правой шириной задается функцией

Треугольное нечеткое число с центром в точке а можно рассматривать как нечеткое значение высказывания х приблизительно равен а, в то время как трапециевидное число обозначает нечеткое значение высказывания х находится приблизительно в интервале [a, b]. Величины l и r также называются соответственно левым и правым коэффициентами нечеткости и показывают насколько неточно (нечетко) определены границы числа. Трапециевидное нечеткое число обозначается кортежем ; при получим треугольное нечеткое числа .

Рассмотрим класс операторов пересечения и объединения, известных как треугольные нормы: t-норма и t-конорма (s-норма) . T служит основой для определения пересечения нечетких множеств, а S - объединения нечетких множеств. Принимая во внимание свойства классических множеств, можно сформулировать следующие свойства для t-норм:. - ограниченность. - коммутативность.Если и , то и - монотонность. - ассоциативность

и для s-норм:

S1.граничные условия. - коммутативность.Если и , то и - монотонность. - ассоциативность

где .

Другими словами, функция есть t-норма тогда и только тогда, когда она удовлетворяет условиям T1-T4, а - s-норма тогда и только тогда, когда она удовлетворяет условиям S1-S4. С точки зрения алгебры, T - полугруппа в [0,1] с единицей 1, а S - с единицей 0. Наиболее важные параметры t-норм и s-норм приведены в таблице 1.

Таблица 1 - t-нормы и s-нормы

t-нормаs-нормаЗаде Алгебраическая Лукашевич Фодор Глубокая Теперь введем оператор дополнения нечеткого множества. Пусть в соответствии с минимальными требованиями, необходимыми для определения отрицания, мы имеем невозрастающую функцию такую, что . Введем следующие условия:

1.n - строго убывающая

2.n непрерывна

3. для любого

Отрицание строгое, если оно удовлетворяет условиям 1 и 2. Отрицание называется сильным, если для него также выполнено условие 3.

Наконец, введем понятие импликации. Функция , удовлетворяющая следующим условиям, называется импликацией:

.Если , то монотонность по первому аргументу

.Если , то монотонность по второму аргументу

.

.

.

Наиболее важные нечеткие импликации представлены в таблице 2.

Таблица 2 - Нечеткие импликации

НазваниеВидЛукашевичФодорРайхенбахКлине-ДинсЗадеИмпликация применяется для получения нечеткого логического вывода. В его основе лежат классические схемы правильных рассуждений modus ponens и modus tollens.

Классический modus ponens - это правило вывода следующего вида: если посылки и истинны, то предпосылка также верна, то есть , или:

Предпосылка I - факт А

Предпосылка II - правило если A, то B

Заключение B

Нечеткая интерпретация позволяет перейти к обобщенному modus ponens, который может быть записан так:

Предпосылка I - факт А

Предпосылка II - правило если A, то B

Заключение B

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

Пусть существует набор правил:

…

Каждому правилу соответствует импликация . Существует два подхода к формированию функции принадлежности заключения:

1.Сначала все правила агрегируются, а затем применяется композиция.

2.Вначале формируется заключение для каждого правила вывода, а затем применяется оператор агрегирования.

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

·метод центра тяжести (Center of Gravity - COG):

·метод центра площади (Center of Area - COA)

·метод левого модального значения (Left Most Maximum - LM)

·метод правого модального значения (Right Most Maximum - LM)

где - модальное значение нечеткого множества.

2.Задача нечеткой классификации

2.1 Постановка задачи

Пусть имеется N объектов, каждый из которых характеризуется n свойствами, так что объекту соответствует векторная оценка . - множество векторных оценок. Требуется определить разбиение множества на подмножества , такие что и для (, для . Подмножества будем называть классами (или кластерами). Если разбиение определено, то для любого нового объекта определить, к какому классу он принадлежит.

2.2Алгоритм решения

Замечание: Данная задача связана с поиском на множестве векторных оценок А отношения эквивалентности Е, которое однозначно определяет искомое разбиение. Оно представляет собой фактор-множество отношения А по отношению эквивалентности Е.

Для решения задачи предлагается построить нечеткую систему, которая содержит базу знаний в виде совокупности если-то правил.

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

Блок задание векторной оценки нового объекта представляет объект классификации как вектор, состоящий из n компонент (характеристик).

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

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

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

В блоке вывод о принадлежности к классу определяется наиболее вероятная принадлежность объекта к одному из заданных классов.

3.Формирование базы правил для нечеткого классификатора

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

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

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

3.1Классификация нечетких моделей

Лингвистическая нечеткая модель имеет вид

где , - входная и выходная лингвистические переменные; - лингвистические термы (им соответствуют нечеткие переменные с определенными функциями принадлежности).

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

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

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

и

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

Модель Takagi - Sugeno (TS-модель) можно рассматривать как комбинацию лингвистической и регрессионной модели. Она задается в следующем виде:

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

Структура модели

Мы применяем нечеткие правила классификации, каждое из которых описывает один из классов в наборе данных. Априорное правило является нечетким описанием в n-мерном пространстве свойств и последовательность правил является свежей (нечеткой) меткой класса из множества :

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

Выход классификатора затем определяется правилом, которое имеет наивысшую степень активации:

В дальнейшем мы предполагаем, что число классов соответствует числу правил, т.е. M=. Степень уверенности в решении дана нормализованной степенью запуска правила:

Управляемая данными инициализация

Из К доступных входящих-выходящих пар данных мы строим n-мерный шаблон матрицы и соответствующий вектор-метку . Нечеткие антецеденты в начальной базе правил теперь определены алгоритмом с тремя шагами.

Шаг 1: М функций принадлежности многих переменных определяются в пространстве функций продукта. Каждая описывает область, где система может быть приближена единственным нечетким правилом. Это разбиение может быть реализовано итерационными методами, такими как кластеризация. Здесь предложен одношаговый подход. Это предполагает, что каждый класс описывается единственной компактной конструкцией в пространстве функций. Если дело обстоит не так, могут быть применены другие методы, такие как, например, реляционные классификации. Подобный нечеткому алгоритму объединения в кластеры, подход, предложенный здесь, также предполагает, что форма нечетких множеств может быть приближена эллипсоидами. Таким образом, каждый прототип класса представляет собой центр его ковариационной матрицы :

Здесь i обозначает индекс классов, , и обозначает число образцов, принадлежащих i-му классу.

Шаг 2: Вычисляется нечеткая матрица разделения U, ik-е элементы которой, , являются степенью принадлежности объекта данных классу . Эта принадлежность основана на расстоянии между высказыванием и центром класса:

Используя расстояние, принадлежность становится:

где m - весовой показатель, определяющий размытость полученных разделений (m = 1,8 применяется в примере).

Строки U теперь содержат поточечные представления многомерных нечетких множеств описания классов в пространстве функций.

Шаг 3: Одномерные нечеткие множества в классификации правил (1) получаются путем проектирования рядов U на входные переменные , а затем приближением проекций параметрическими функциями. Для простоты мы применяем треугольные нечеткие числа:

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

3.2Сокращение модели

Отбор свойств, основанный на межклассовой отделимости

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

Шаг 1: Строится матрица

- число случаев в каждом классе. Общая матрица разброса может быть представлена как:

Критерий выбора отделимости межклассовой особенности является обменом между и .

Шаг 2: Ранжирование особенности делается многократно, не учитывая худшую особенность в каждом шаге, и применяется в открытом цикле выбора особенности:

где det - определитель и - значение критерия, включая j особенностей.

Метод упрощения базы правил использует меру сходства для определения количественной избыточности среди нечетких множеств в базе правил. Применяется меры сходства на основе теоретико-множественных операций пересечения и объединения:

где обозначает мощность множества, а и операторы представляют собой объединение и пересечение соответственно. Если , то две функции принадлежности эквивалентны. S (A, B) становится 0, когда функции принадлежности не накладываются.

Нечетких множества объединяются, когда их сходства превышают определяемый пользователем порог (применяется = 0,5). Слияние уменьшает количество различных нечетких множеств (лингвистических терминов), используемых в модели, и тем самым увеличивает прозрачность. Если все нечеткие множества для высказывания сходны с универсальным набором или если слияние привело только к одной функции принадлежности для высказывания, то это высказывание исключается из модели. Метод иллюстрируется на Рис. 4

Рис. 4 - Упрощение базы правил

Здесь нечеткие множества A11, A21 и A31 подобны, следовательно, они объединяются в одно нечеткое множество, которое исключаются из модели. Нечеткое множество A32 является объединением множеств A12 и A22, поэтому его исключают из модели. Множества A13 и A23 сходны, поэтому они тоже объединяются.

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

4.1 Основные понятия эволюционного программирования

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

Генетический алгоритм - это новая область исследований, которая появилась в результате работ Д. Холланда и его коллег. Генетические алгоритмы, описанные Д. Холландом, заимствуют в своей терминологии много из естественной генетики. Впервые генетические алгоритмы были применены к таким научным проблемам, как распознавание образов и оптимизация. Генетический алгоритм представляет собой адаптивный поисковый метод, основанный на селекции лучших элементов в популяции, подобно эволюционной теории Ч. Дарвина.

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

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

Цель генетических алгоритмов в том, чтобы:

Абстрактно и формально объяснять адаптацию процессов в естественной системе и интеллектуальной исследовательской системе

Моделировать естественные эволюционные процессы для эффективного решения задач науки и техники

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

Генетические алгоритмы отличаются от других оптимизационных и поисковых процедур следующим:

Работают в основном не с параметрами задачи, а с закодированным множеством параметров.

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

Используют целевую функцию, а не ее различные приращения для оценки качества принятия решений.

Применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

Символьная модель

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

Структура данных генетического алгоритма состоит из одной или более хромосом. Как правило, хромосома - это битовая строка, так что термин строка часто заменяет понятие «хромосома». В принципе, ГА не ограничены бинарными представлениями. Известны другие реализации, построенные исключительно на векторах вещественных чисел. Несмотря на то, что для многих реальных задач больше подходят строки переменной длины, в настоящее время структуры фиксированной длины наиболее распространены и изучены.

Каждая хромосома (строка) представляет собой объединение ряда подкомпонентов, называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген-бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин «генотип» относится к полной генетической модели особи и соответствует структуре в ГА. Термин «фенотип» относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Чрезвычайно простой, но иллюстративный пример - задача максимизации следующей функции двух переменных:

Обычно, методика кодирования реальных переменных и состоит в их преобразовании в двоичные целочисленные строки достаточной длины - достаточной для того, чтобы обеспечить желаемую точность. Предположим, что 10-ти разрядное кодирование достаточно для и . Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное число на . Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизированная структура данных - 20-ти битная строка, представляющая конкатенацию кодировок и . Переменная размещается в крайних левых 10-ти разрядах, тогда как размещается в правой части генотипа особи (20-ти битной строке). Генотип - точка в 20-мерном хемминговом пространстве, исследуемом ГА. Фенотип - точка в двумерном пространстве параметров.

Чтобы оптимизировать структуру, используя ГА, нужно задать некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели используется функция приспособленности. В функциональной максимизации, целевая функция часто сама выступает в качестве функции приспособленности; для задач минимизации, целевую функцию следует инвертировать и сместить в область положительных значений.

Канонический генетический алгоритм (Canonical GA)

Данная модель алгоритма является классической. Она была предложена Джоном Холландом в его знаменитой работе «Адаптация в природных и искусственных средах» (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:

·Фиксированный размер популяции

·Фиксированная разрядность генов

·Пропорциональный отбор

·Особи для скрещивания выбираются случайным образом

·Одноклеточный кроссовер и одноклеточные мутации

Кроссовер

Оператор кроссовера (crossover operator) является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Кроссовер моделирует процесс скрещивания особей.

Пусть имеются две родительские особи с хромосомами и . Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими. Назовем эту точку точкой разрыва. Вообще говоря, в англоязычной литературе она называется точкой кроссовера (crossover point). Описанный процесс изображен на рисунке 5.

Родительские особи Потомки

Данный тип кроссовера называется одноточечным, так как при нем родительские хромосомы разрезаются только в одной случайной точке. Также существует 2-х и n-точечный операторы кроссовера. В 2-х точечном кроссовере точек разрыва 2, а n-точечный кроссовер является своеобразным обобщением 1- и 2-точечного кросоеверов для n>2.

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

Мутация

Оператор мутации (mutation operator) необходим для вывода популяции из локального экстремума и способствует защите от преждевременной сходимости. Это достигается за счет того, что инвертируется случайно выбранный бит в хромосоме, что показано на рисунке 6.

До мутации После мутации

Так же как и кроссовер, мутация проводится не только по одной случайной точке. Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N, где L - длина хромосомы, N - размер популяции.

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

Постановка задачи

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

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

Алгоритм генерации базы знаний - эволюционная стратегия.

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

Идея эволюционных стратегий была предложена Инго Рехенбергом (Ingo Rechenberg) в 1960-70 годах. Так же, как и генетические алгоритмы, они работают с популяцией решений и основываются только на целевой функции и ограничениях. Основные отличия от классического генетического алгоритма заключаются в том, что эволюционная стратегия работает с векторами действительных чисел и использует только оператор мутации. При мутации каждому элементу вектора добавляется случайная нормально распределенная величина.

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

Здесь и - трапециевидные функции принадлежности с четырьмя параметрами.

В нашей задаче один вход и один выход, поэтому правила представлены в следующем виде:

Если x есть , то y есть ,

где i - номер правила.

Получение «родительского» элемента

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

Мутация

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

Нечеткие операторы

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

Отмена. Если функция принадлежности становится слишком «узкой», она не должна больше использоваться. Данный критерий записывается следующим образом:

где и - длины медиан функций принадлежности заданных входных и выходных переменных в i-м и j-м правилах;

- параметр отмены. Чем он больше, тем критерий более строгий.

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

Для слияния существует два критерия:

где и - длины медиан функций принадлежности заданных входных и выходных переменных в i-м и j-м правилах;- расстояние между центром и .

Для выполнения слияния оба критерия должны быть удовлетворены, при этом используется только один параметр . Чем меньше значение , тем критерий строже. Параметры объединенной функции принадлежности будут иметь вид:

где

Удаление правил. При использовании метода центра тяжести для дефазификации, удаление правила влечет за собой рост ошибки. Чтобы избежать этого, мы будем увеличивать важность правила. Например, если i-е и j-е правила идентичны, то j-е правило убирается, а параметры функции принадлежности i-го правила меняются следующим образом:

где - исходные параметры трапециевидной функции принадлежности;

- новые значения и ; параметры не меняются.

Условие останова

Работа алгоритма представляет собой итерационный процесс, который продолжается до выполнения одного из условий останова:

выполнение заданного числа поколений;

прекращение улучшения популяции.

Когда была получена начальная нечеткая модель, она была упрощена и оптимизирована итерационным методом. Комбинации GA с инструментами сокращения модели, описанными выше, могут привести к различным схемам моделирования. Три разных подхода показаны на Рис. 5.

Моделирование схемы в результате сочетания инструментов

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

где MCE является средней ошибкой классификации:

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

где n - число входов и - количество наборов для каждого входной переменной. Функция надбавки определяет, поощрено ли подобие () или наказано (). В примере для двух случаев применено неподвижное -0.2 и 0.2.

4.2 Описание генетического алгоритма

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

Нечеткое представление модели

Для описания решения, используются хромосомы. С численностью населения L мы кодируем параметры каждой нечеткой модели (решения) в хромосоме , как последовательность элементов, описывающих нечеткие множества в прошлых правилах. Классификатор с М нечеткими правилами закодирован следующим образом:

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

Функция выбора

Метод выбора колесо рулетки используется, чтобы выбрать хромосомы для операции. Шаг на колесе рулетки адаптивный и дан как , где:

и является представлением модели, закодированном в хромосоме . Обратная к функции выбора используется, чтобы выбрать хромосомы для удаления. Лучшая хромосома всегда сохраняется в популяции (элитарный выбор). Шанс, что отобранная хромосома используется в переходной операции, составляет 90% и шанс мутации составляет 10% (в данной работе). Когда хромосома отобрана для перехода (или мутации), с равной вероятностью применяется один из трех переходных (или мутационных) операторов.

Генетические операторы

В GA используются два классических оператора: простой арифметический переход и однородная мутация, и четыре специальных закодированных оператора. Далее,- случайное число (равномерное распределение), - номер поколения, и - хромосомы, выбранные для операции, - положение элемента в хромосоме, и и - нижняя и верхняя границы, соответственно, параметра, закодированного элементом k: одиночные хромосомы () отобраны для мутации, и пары хромосом (отобраны для перехода:

(1)Однородная мутация; случайный отобранный элемент заменяется , являющимся случайным числом из диапазона []. Результирующие хромосомы

(2)Множественная единая мутация; единая мутация n случайно
выбранных элементов, где n также выбрано случайно из {1,…, N}.
(3)Мутация Гаусса; все элементы хромосомы видоизменены таким образом что , где , k =1,2,…, N. Здесь - случайное число из распределения Гаусса с нулевым средним и адаптивной дисперсией Настройка параметра, выполненная этим оператором, становится все лучше и лучше с увеличением счетчика поколения.

(4)Простой арифметический переход; и пересечены в k-й позиции. Получающееся потомство: , где k выбрано случайно из {2,…, N-1}

(5)Полный арифметический переход; линейная комбинация и превращается в и .

(6)Эвристический переход; и объединяются так, что и

Ограничения

Оптимизация, представленная GA, подвергнута двум типам ограничений: разделение и область поиска. Ограничение разделения запрещает пробелы в частях входных данных (антецедентов) переменных. Кодирование нечеткого множества должно соответствовать (9), т.е. . Для того чтобы избежать пробелов в частях, пары соседних нечетких множеств ограничены: , где L и R обозначают левый и правый набор, соответственно.

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

4.3 Генетический алгоритм

Учитывая модель матрицы Z и базу нечетких правил, выберите число поколений Т, численность населения L, число операций и ограничения и - нынешнее число решений , и пусть - вектор соответствующих значений функции оценки:

(1)Создайте начальную хромосому из начальной базы нечетких правил.

(2)Вычислите векторы ограничений и , используя .

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

(4)Повторите генетическую оптимизацию для t = 0,1,2,…, T-1:

(a)Оцените и получите

(b)Выберите хромосом для операции.

(c)Выберите хромосом для удаления.

(d)Воздействуйте на хромосомы, обращая внимание на ограничения области поиска.

(e)Осуществите раздел ограничений.

(f)Создайте новую популяцию , заменяя хромосомы, выбранные для удаления управляемыми хромосомами.

(5)Выберите лучшее решение из , оценивая .

Заключение

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

основы нечеткого моделирования

модель и принцип работы нечеткого классификатора

процесс проектирования нечеткого классификатора и формирования базы правил

Была разработана программа, выполняющая построение нечеткого классификатора на основе наблюдаемых данных.

Целью дальнейших исследований является изучение и применения генетического алгоритма для оптимизации базы правил

Список литературы

нечеткий импликация эквивалентность классификатор

1.Леденева Т.М. Основы нечеткого моделирования в среде MatLab: учебное пособие / Т.М. Леденева, Д.С. Татаркин, А.С. Тарасова. - Воронеж: ЛОП ВГУ, 2006. - 51 с.

.Леденева Т.М. Обработка нечеткой информации / Т.М. Леденева. - Воронеж: ВГУ, 2006. - 232 с.

3.Roubos J.A. Learning Fuzzy Classification Rules from Labeled Data. / J.A. Roubos, M. Setnes, J. Abonyi. // Elsevier Preprint, 2001.

4.Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы. / Рутковская Д., Пилинский М., Рутковский Л. - Москва: Горячая линия - Телеком, 2004. - 315 с.

.Тэрано Т. Прикладные нечеткие системы. / Тэрано Т., Асаи К., Сугено М. - Москва: Мир, 1993. - 386 с.

.Гладков Л.А. Генетические алгоритмы: Учебное пособие. - 2-е изд. / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. - М.: Физматлит, 2006. - 320 с.

.Рыжков А.П. Элементы Теории нечетких множеств и измерения нечеткости. / А.П. Рыжков - М.: Диалог-МГУ, 1998.

1.Нечеткое моделирование: основные понятия и принципы Нечеткая система - это система, для описания которой используется аппарат теории нечетких множеств

Больше работ по теме: