Разработка и исследование генетических алгоритмов обучения в моделях вычисления оценок (стр. 1 )

на правах рукописи

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ОБУЧЕНИЯ В МОДЕЛЯХ ВЫЧИСЛЕНИЯ ОЦЕНОК

специальность 05.13.18

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2007

Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного университета)

Научный руководитель:

доктор физико-математических наук, член-корреспондент РАН,

профессор

Официальные оппоненты:

доктор физико-математических наук

кандидат физико-математических наук

Ведущая организация:

Факультет вычислительной математики и кибернетики Московского государственного университета имени (ВМК МГУ)

Защита состоится « 26 » октября 2007 г. в 9.00 часов на заседании диссертационного совета К 212.156.02 при Московском физико-техническом институте (государственном университете), Московская область, г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ

Автореферат разослан « 19 » сентября 2007 г.

Ученый секретарь диссертационного совета

кандидат физико-математических наук

Общая характеристика работы

Актуальность темы

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

Цель работы

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

Практическая ценность работы

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

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

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

2. Разработан алгоритм генетического поиска экстремума критерия оптимальности предикатов. Исследована роль параметров генетического алгоритма при решении данной задачи.

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

4. Для задач с неразличимыми классами получена теоретическая оценка количества локальных экстремумов критерия оптимальности.

5. Разработаны новые типы оценок объекта за классы и построены решающие правила для этих оценок.

Публикации

Результаты диссертации опубликованы в [1-8], работа [2] – из списка изданий, рекомендованных ВАК РФ. В совместных работах автору принадлежит разработка и исследование математических моделей обучения и распознавания по прецедентам, модификации генетического алгоритма, а также их программная реализация и тестирование.

Апробация

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

· Математические Методы Распознавания Образов ММРО-11 (Пущино 2003);

· 7th International Conference on Pattern Recognition and Image Analysis PRIA-7 (St. Petersburg, Russian Federation 2004);

· Научные конференции МФТИ (Долгопрудный, );

· Технологии Microsoft в теории и практике программирования (Москва, 2005);

· 6th WSEAS Int. Conf. on Applied Computer Science ACS06 (Tenerife, Canary Islands, Spain 2006);

· Научные семинары кафедр вычислительной математики и информатики МФТИ (Долгопрудный, );

· Научные семинары отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного центра РАН (Москва, ).

Структура и объем диссертации

Диссертация состоит из введения, пяти глав и заключения. Общий объем диссертации составляет 131 страницу, включая 28 иллюстраций и 25 таблиц. Список использованных источников содержит 92 публикации отечественных и зарубежных авторов.

Краткое содержание работы

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

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

Задача распознавания произвольного объекта некоторым алгоритмом распознавания записывается в следующем виде:

, , . Здесь

· соответствует отнесению объекта в класс

· - решению

· - отказу от распознавания данного объекта.

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

Здесь , - параметры предикатов. Определение. Предикат

(1.1)

называется допустимым для класса, если

(1.2)

Предикат называется логической закономерностью класса , если

(1.3)

где - критерий оптимальности предиката. Критерий

называется стандартным критерием оптимальности.

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

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

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

- Принцип построения покрытия класса признаковыми интервалами (предикатами), в том числе определение критерия оптимальности для предикатов.

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

- Принцип вычисления оценок .

- Применение решающих правил.

Пусть фиксирован некоторый класс, содержащий обучающих объектов. Предлагается рассматривать предикаты определенного типа, а именно предикаты, которым соответствуют признаковые интервалы минимального объема, содержащие при этом некоторый фиксированный (свой для каждого предиката) набор объектов. Устанавливается взаимное соответствие между предикатами данного типа и бинарными векторами длины . При этом каждому предикату будет соответствовать бинарный вектор, в котором на i-й позиции будет стоят «1», если объект находится внутри соответствующего признакового интервала и «0», иначе. Рис. 1-а, 1-б и комментарий к ним иллюстрируют принцип создания и кодирования предикатов, а также показывают, что установленное соответствие не является взаимно однозначным.

Рис. 1-a Рис. 1-б

Рис. 1-а, 1-б: иллюстрация принципа построения и кодирования предикатов. Точками обозначены объекты рассматриваемого класса, крестиками – объекты остальных классов. На рис. 1-б изображены объекты двух классов, причем объекты первого класса пронумерованы. Изображенному на рис. 1-б предикату будет соответствовать бинарный вектор , а сам изображенный предикат будет соответствовать векторам , , , .

Для создания покрытия класса введем нумерацию предикатов в порядке их построения, и для каждого предиката кроме первого переопределим критерий оптимальности (1.4) следующим образом:

(1.5)

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

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

Кодирование хромосом генетического алгоритма осуществляется согласно принципу, обозначенному в главе 1. Хромосомами представлены проекции предикатов на множество бинарных векторов фиксированной длины. Гены хромосом соответствуют объектам обучающей выборки. Целевая функция ГА соответствует критерию оптимальности (1.4).

Задача поиска оптимального предиката в признаковом пространстве с ЦФ вида (1.4) обладает несколькими характерными особенностями, требующими особого подхода к получению решения. Среди характерных особенностей задачи следует отметить

1) Сильное взаимное влияние генов друг на друга. Наличие или отсутствие некоторого гена может отличать лучшую хромосому популяции от хромосомы с нулевой ЦФ.

2) Сравнительно малое число хромосом ГА, на которых ЦФ отлична от нуля. Для подавляющего большинства задач общее количество хромосом с нулевым значением ЦФ будет многократно превышать количество хромосом с ненулевой ЦФ.

3) Большое количество локальных экстремумов задачи.

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

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

(2.1)

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

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

Количество признаков	Количество объектов
5	10	16	24	50	100
2	2.2	5.1	10.8	18	47	100
5	1.8	5.1	24.4	52	873	4324
10	1.2	3.4	18.8	109	4394	9.1e+5
15	1	2.1	8.4	69	5624	1.1e+7
25	1	1.2	3.2	20	5139	3.6e+7
50	1	1	1.1	3	698	3.1e+7
100	1	1	1	1	10	5.3e+5

Таблица 1. Зависимость значения теоретической оценки количества локальных экстремумов от параметров и . В ячейках таблицы – значения, полученные по формуле (2.1).