Программные продукты и системы

Нечеткий классификатор – это алгоритм классификации, основанный на извлечении нечетких правил из массивов данных [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

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

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

Таблица 2

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

Разработанный алгоритм реализован в виде программной системы, созданной в интегрированной среде разработки 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).