На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

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

Fuzzy classifier base rule collective forming
Статья опубликована в выпуске журнала № 4 за 2012 год. [ на стр. 118-121 ]
Аннотация:Рассматривается подход к коллективному формированию базы правил нечеткого классификатора ансамблем нечетких классификаторов, сгенерированных самонастраивающимися коэволюционными алгоритмами. Представлены результаты применения данного подхода при решении практических задач классификации. Основной результат работы – новый метод коллективного формирования нечеткого классификатора. При наличии нескольких заранее сгенерированных нечетких классификаторов появляется возможность сформировать с использованием самонастраивающихся коэволюционных алгоритмов нечеткий классификатор, превосходящий по эффективности первоначаль- ные. При этом число используемых нечетких правил не увеличивается. Разработанный метод имеет следующие свойства: позволяет получать классификаторы, превосходящие по точности классификации исходные при сохранении ограничения на число используемых правил; снижает разброс в значениях эффективности нечетких классификаторов при многократном запуске, то есть обладает повышенной статистической устойчивостью; наиболее эффективен для сложных задач классификации (по числу классов или атрибутов). Значения точности классификации, вычисленные с помощью разработанного метода, превосходят значения, полученные многими современными алгоритмами классификации.
Abstract:An approach of fuzzy classifier base rule collective forming with generated with self-tuning coevolutionary algorithms fuzzy classifier ensemble is observed. Results of the approach applying for practical classification problems are presented. The main result of our work is collective fuzzy classifier forming method. Having generated some fuzzy classifiers we are able to construct more effective classifier from previous classifiers using again cooperative-competitive coevolutionary algorithm. A number of using fuzzy rules isn’t increasing with this method. The approach of multistep fuzzy classifier forming has the following features: the method improves classification performance without increasing number of rules, the method reduces diversity of performance values for multiple algorithm runs, i.e. the method has higher statistical stability, the method is more effective for more complicated classification problems (more attributes and classes).Fuzzy classifier forming methods comparison with alternative classification methods by performance value demonstrates that both fuzzy classifier forming methods have better efficiency that present-day classification algorithms.
Авторы: Сергиенко Р.Б. (romaserg@list.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, г. Красноярск, Россия
Ключевые слова: коэволюционный алго ритм., ансамбль алгоритмов, коллективный выбор, нечеткий классификатор
Keywords: coevolutionary algorithm, algorithm ensemble, collective decision, fuzzy classifier
Количество просмотров: 6260
Версия для печати
Выпуск в формате PDF (9.63Мб)
Скачать обложку в формате PDF (1.26Мб)

Размер шрифта:       Шрифт:

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

Автором разработан и исследован новый подход к формированию нечетких классификаторов, использующий самонастраивающиеся коэволюционные алгоритмы и гибридизирующий основные подходы к формированию нечетких систем генетическими алгоритмами – Питтсбургский (индивид – база правил целиком) и Мичиганский (индивид – отдельное нечеткое правило) [2]. Процедура включает следующие основные этапы.

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

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

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

Подробно результаты исследования эффек- тивности метода формирования нечеткого классификатора самонастраивающимися коэволюционными алгоритмами и преимущества метода описаны в [2].

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

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

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

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

Для исследования предлагаемого коллективного метода формирования базы правил нечеткого классификатора ансамблем исходных нечетких классификаторов взяты следующие практические задачи классификации из репозитория UCI [4]:

1.     Credit (Australia-1) (задача о выявлении подозрительных транзакций c кредитными картами, австралийский вариант, 14 признаков, 2 класса);

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

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

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

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

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

7.     Landsat Images (распознавание типов земель по спутниковым изображениям, 36 признаков (методом главных компонент размерность задачи сокращена до 4 признаков), 6 классов).

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

Из таблицы 1 видно, что метод коллективного формирования базы правил нечеткого классификатора позволил статистически значимо повысить точность классификации для всех задач при сохранении ограничения на число используемых правил. Отметим, что эффективность метода в большей мере проявляется при увеличении сложности задачи (увеличении числа признаков или классов). Так, для задач Iris (4 признака, 3 класса) или LandSat Images (4 признака, 6 классов) прирост по точности классификации около 1 %, тогда как для задачи Glass Identification (9 признаков, 7 классов) средние и максимальные показатели точности классификации увеличены на 8–9 %. Кроме того, почти во всех задачах отмечено существенное сокращение разброса в значениях показателей при многократном запуске алгоритма, что свидетельствует о повышенной статистической устойчивости коллективного метода формирования нечеткого классификатора.

В таблице 2 приведено сравнение максимальных значений точности классификации, полученных коллективным методом формирования базы правил нечеткого классификатора, со значениями, полученными исходным (базовым) методом формирования нечеткого классификатора, а также рядом современных алгоритмов классификации согласно данным, приведенным в [5] и [6].

Таблица 1

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

Задача

Значения

Среднеквадратичные уклонения

Максимальные

Средние

Минимальные

Исх.

Кол.

Исх.

Кол.

Исх.

Кол.

Исх.

Кол.

Glass Identification–20

0,757

0,836

0,737

0,824

0,706

0,813

0,01388

0,00737

Glass Identification–30

0,827

0,874

0,782

0,861

0,757

0,827

0,01831

0,01354

Liver Disorder–10

0,687

0,713

0,666

0,705

0,632

0,699

0,01500

0,00449

Liver Disorder–15

0,710

0,739

0,682

0,731

0,655

0,719

0,01669

0,00608

Liver Disorder–20

0,725

0,757

0,692

0,748

0,655

0,739

0,01731

0,00554

Iris–3

0,947

0,980

0,908

0,980

0,767

0,980

0,05643

0

Iris–4

0,973

0,980

0,951

0,980

0,900

0,980

0,02623

0

Iris–5

0,987

0,987

0,971

0,987

0,940

0,987

0,01303

0

Iris–6

0,987

0,993

0,975

0,993

0,933

0,987

0,01073

0,00211

Landsat Images–10

0,849

0,851

0,839

0,850

0,821

0,848

0,00783

0,00107

Landsat Images–15

0,857

0,861

0,847

0,859

0,836

0,856

0,00416

0,00144

Landsat Images–20

0,857

0,864

0,849

0,863

0,835

0,862

0,00546

0,00090

Yeast –20

0,598

0,609

0,573

0,605

0,540

0,602

0,01801

0,00241

Yeast–30

0,606

0,641

0,587

0,633

0,555

0,625

0,01710

0,00431

Yeast–60

0,626

0,674

0,593

0,668

0,542

0,662

0,02207

0,00429

Credit (Australia-1)–10

0,870

0,891

0,827

0,888

0,758

0,886

0,02482

0,00174

Credit (Australia-1)–20

0,890

0,919

0,861

0,918

0,841

0,910

0,01231

0,00269

Credit (Australia-1)–30

0,891

0,926

0,873

0,924

0,854

0,922

0,01035

0,00171

Credit (Germany)–50

0,767

0,795

0,761

0,791

0,755

0,783

0,00357

0,00431

Credit (Germany)–80

0,794

0,821

0,790

0,815

0,784

0,809

0,00296

0,00534

Примечение: исх. – значения для исходного множества нечетких классификаторов; кол. – значения, полученные после генерации нечеткого классификатора из коллектива нечетких классификаторов; число после наименования задачи обозначает значение ограничения на число используемых правил; жирным шрифтом выделены наилучшие показатели (максимальная точность классификации, минимальное среднеквадратичное уклонение).

Таблица 2

Сравнительная таблица эффективности различных методов классификации

Алгоритм

Credit Australia-1

Credit Germany

Liver Disorder

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

0,926

0,821

0,757

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

0,891

0,794

0,725

Байесовский подход

0,847

0,679

0,629

Многослойный персептрон

0,833

0,716

0,693

Бустинг

0,760

0,700

0,656

Бэггинг

0,847

0,684

0,630

Метод случайных подпространств

0,852

0,677

0,632

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

0,866

0,746

0,644

Разработанный алгоритм реализован в виде программной системы, созданной в интегрированной среде разработки Microsoft Visual Studio 2008, язык C++. Программная система предусматривает унифицированный формат ввода исходных данных, не зависящий от предметной области решаемой задачи классификации.

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

Литература

1.     Ishibuchi H., Nakashima T. and Murata T. Performance Evaluation of Fuzzy Classifier Systems for Multidimensional Pattern Classification Problems, IEEE Trans. on Systems, Man, and Cybernetics, 1999. Vol. 29, pp. 601–618.

2.     Сергиенко Р.Б. Метод формирования нечеткого классификатора самонастраивающимися коэволюционными алгоритмами // Искусственный интеллект и принятие решений. 2010. № 3. С. 98–106.

3.     Sergienko R.B. and Semenkin E.S. Competitive Cooperation for Strategy Adaptation in Coevolutionary Genetic Algorithm for Constrained Optimization // WCCI 2010 IEEE World Congress on Computational Intelligence. CCIB, Barcelona, Spain (July, 18–23), 2010, pp. 1626–1631.

4.     UCI Machine Learning Repository. URL: http://kdd.ics. uci.edu/ (дата обращения: 23.03.2011).

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

6.     Тестирование многослойного персептрона. URL: http:// poligon.machinelearning.ru/Report/View.aspx?reportId=4&page=1&from=list (дата обращения: 12.04.2011).


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=3323&lang=
Версия для печати
Выпуск в формате PDF (9.63Мб)
Скачать обложку в формате PDF (1.26Мб)
Статья опубликована в выпуске журнала № 4 за 2012 год. [ на стр. 118-121 ]

Назад, к списку статей