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

Размещено на http://www.allbest.ru/

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ГИБРИДНОЙ СХЕМЫ ФОРМИРОВАНИЯ НЕЧЕТКОГО КЛАССИФИКАТОРА С ИСПОЛЬЗОВАНИЕМ КОЭВОЛЮЦИОННОГО АЛГОРИТМА

Р.Б. Сергиенко

Сибирский государственный аэрокосмический университет им. ак. М.Ф. Решетнёва, Красноярск

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

Нечеткий классификатор [Ishibuchi, 1999] - алгоритм классификации, основанный на извлечении нечетких правил из массивов данных.

При использовании нечеткого классификатора как инструмента извлечения знаний предпочтительнее получать базы нечетких правил с небольшим числом правил и минимальным числом условий в предикатной части правил. В [Ishibuchi, 2001] задача генерации нечеткого классификатора формулируется как многокритериальная задача оптимизации с тремя критериями: максимизация надежности классификации, минимизация числа правил в базе, минимизация среднего числа условий в предикатной части нечетких правил.

Распространенным методом генерации нечетких баз правил является использование для этой цели эволюционных (в частности, генетических) алгоритмов. Существует два основных подхода в использовании генетических алгоритмов (ГА) в задачах конструирования нечетких систем: Питтсбургский и Мичиганский [Cordуn, 2001]. В Мичиганском методе индивиды генетического алгоритма представляют собой отдельные правила, в Питтсбургском - базу нечетких правил в целом. Недостаток Мичиганского метода - противоречие между целевой функции для индивидов и эффективностью базы правил в целом. Питтсбурсгкий метод лишен этого недостатка, однако требует значительных вычислительных ресурсов - размерность решаемой задачи оптимизации возрастает многократно. Поэтому гибридизация Питтсбургского и Мичиганского методов в задачах генерации нечетких систем является актуальной научно-технической задачей. Например, в [Ishibuchi, 2000] предлагается гибридизация Питтсбургского и Мичиганского методов на основе использования Мичиганского метода как оператора мутации в реализации Питтсбургского подхода.

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

На обоих стадиях генерирования нечеткого классификатора предлагается применять коэволюционный алгоритм для адаптации поисковой стратегии генетического алгоритма [Емельянова, 2004]. Данный подход позволяет решить трудоемкую задачу выбора оптимальных настроек ГА.

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

1. Новая схема гибридизации Мичиганского и Питтсбургского методов в формировании нечеткого классификатора

В [Ishibuchi, 2001] задача генерирования нечеткого классификатора эволюционными алгоритмами сформулирована в виде трехкритериальной задачи оптимизации (критерии - надежность классификации, число правил, суммарная длина правил). В работе предлагается использование Питтсбургского подхода с использованием Мичиганского метода в качестве оператора мутации [Ishibuchi, 2000]. Недостатками предлагаемой схемы являются: алгоритмическая и вычислительная сложность реализации многокритериальной оптимизации, отсутствие строго формализованного метода отбора правил для «стартовой» базы; (в [Ishibuchi, 2001] предлагается, например, отбор только правил с незначительной длиной предикатной части - их число существенно меньше общего числа всех возможных правил - однако, данный подход не является целесообразным для всех задач), отсутствие этапа строго направленного улучшения стартовых правил (за исключением оператора мутации).

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

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

Пусть n - число нечетких правил, необходимое для заполнения популяции для Мичиганского этапа генерирования, k - число классов, l - число информативных признаков в задаче классификации. Последовательность шагов:

1) вычислить m = int (n/k);

2) отсортировать элементы обучающей выборки по номеру класса в порядке возрастания и определить границы для каждого класса в отсортированном массиве;

3) от i:=1 до k

от j:=1 до m

выполнить случайный выбор элемента класса iиз обучающей выборки;

от t:=1 до l

определить ближайший центр нечеткого числа по признаку t;

назначить соответствующее нечеткое число в нечеткое правило;

изменить нечеткое число на терм «игнорирование» с вероятностью 0,33;

4) заполнить популяцию сгенерированными нечеткими правилами.

Мичиганский этап генерирования нечеткого классификатора. Индивиды представляют собой отдельные нечеткие правила. Длина хромосомы равна числу информативных признаков, каждый ген - число от 1 до 6, соответствующее нечеткому числу. Функция пригодности индивидов - доверительный уровень правила, вычисляемая по обучающей выборке [Ishibuchi, 1999]. Используется генетический алгоритм безусловной оптимизации. Модифицирован метод формирования нового поколения. Среди родителей и потомков для каждого класса отбирается необходимое число неповторяющихся правил с наибольшим значением пригодности (отбор с вытеснением для каждого отдельного класса). Такой метод обеспечивает поддержание разнообразия правил для каждого отдельного класса и разнообразие классов в популяции. На каждом поколении вычисляется надежность классификации по обучающей выборке множества правил в целом. Популяция с наибольшей надежностью классификации используется на следующей стадии генерирования нечеткого классификатора.

Питтсбургский этап генерирования нечеткого классификатора. Индивиды представляют собой базу нечетких правил целиком. Длина хромосомы равна числу правил, найденных на Мичиганском этапе. Хромосомы бинарные, бит «1» означает использование соответствующего нечеткого правила, найденного на предыдущем этапе, бит «0» - исключение правила из базы. Пригодность - надежность классификации базы правил. Вводится ограничение на максимально допустимое число правил, используемых в базе. Используется генетический алгоритм условной оптимизации.

2. Коэволюционный алгоритм для автоматизации выбора настроек генетического алгоритма при формировании нечеткого классификатора

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

Для решения указанной проблемы предлагается использование так называемого коэволюционного алгоритма, представляющего собой группу стандартных генетических алгоритмов, конкурирующих и взаимодействующих между собой. Кооперация и конкуренция между алгоритмами обеспечивает эффективность, превосходящую эффективность алгоритма со средними настройками на задачах безусловной однокритериальной оптимизации [Емельянова, 2004] и превосходящую эффективность алгоритма с наилучшими настройками на задачах условной однокритериальной оптимизации [Сергиенко, 2009]. Таким образом, отпадает необходимость в ручном выборе настроек генетического алгоритма. На Мичиганском этапе формирования нечеткого классификатора используется коэволюционный алгоритм безусловной оптимизации, на Питтсбургском этапе - условной оптимизации.

3. Результаты исследований на практических задачах

Для апробации гибридной схемы генерирования нечеткого классификатора с использованием коэволюционного алгоритма были взяты следующие практические задачи классификации из репозиторияUCIMachineLearning (http://kdd.ics.uci.edu/):

Credit (Australia-1) (задача о выдаче банковского кредита, австралийский вариант, 14 признаков, 2 класса);

Credit (Germany) (задача о выдаче банковского кредита, немецкий вариант, 24 признака, 2 класса);

LiverDisorder (диагностирование заболевания печени, 6 признаков, 2 класса);

Iris (классификация видов ириса, 4 признака, 3 класса);

Yeast (классификация типов дрожжей, 8 признаков, 10 классов);

GlassIdentification (классификация сортов стекла по содержанию химических элементов, 9 признаков, 7 классов);

LandsatImages (распознавание типов земель по спутниковым изображениям, 36 признаков, 6 классов).

Для всех задач приводятся результаты применения алгоритма генерирования нечеткого классификатора (параметры, надежность классификации после каждого этапа) при варьировании уровня ограничения на число используемых правил. Для первых трёх задач классификации приведено сравнение надежности классификации, полученной при использовании сгенерированных баз нечетких правил с эффективностью других алгоритмов классификации (Байесовский подход, многослойный персептрон, бустинг, бэггинг, метод случайных подпространств (RandomSubspaceMethod, RSM), коэволюционный метод обучения алгоритмических композиций) по данным в [Воронцов, 2005].

Сравнение различных алгоритмов классификации на задачах из репозитория UCI по надежности классификации в таблице 1.

классификатор обучение алгоритмический генерирование

Табл. 1.

Табл.2.

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

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

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

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

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

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

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

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

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

1. Коэволюционный метод обучения алгоритмических композиций / К. В. Воронцов, Д. Ю. Каневский // Таврический вестник информатики и математики. 2005. №2.

2. Исследование эффективности коэволюционного алгоритма / М.Н. Емельянова, Е.С. Семенкин // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. 2004. № 6.

3. Сергиенко Р.Б. Исследование эффективности коэволюционного генетического алгоритма условной оптимизации // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнёва. 2009. №3 (24).

4. Cordуn O., Herrera F., Gomide F., Hoffmann F. and MagdalenaL.. Ten years of genetic-fuzzy systems: a current framework and new trends // Proc. of Joint 9th IFSA World Congress and 20th NAFIPS International Conference. - Vancouver, Canada, 2001.

5. H. Ishibuchi, T. Nakashima, and T. Murata. Performance evaluation of fuzzy classifier systems for multidimensional pattern classification problems // IEEE Trans. on Systems, Man, and Cybernetics. May 1999. Vol.29.

6. [Ishibuchi, 2001]Ishibuchi H., Nakashima T., and Murata T. Multiobjective optimization in linguistic rule extraction from numerical data // Evolutionary Multi-Criterion Optimization, Springler-VerlagBerlin, 2001.

7. Ishibuchi H., Nakashima T., and Kuroda T. A hybrid fuzzy GBML algorithm for designing compact fuzzy rule-based classification systems // Proc. of 9^th IEEE International Conference on Fuzzy Systems, 2000.

Размещено на Allbest.ru